一種2 維內核與3 維內核極化碼的鑿孔算法

陳 晨

（中國聯合網絡通信有限公司濟南軟件研究院，山東濟南 250000）

0 引言

隨著第五代移動通信技術（5thGeneration，5G）的發展，對通信系統傳輸速率及傳輸可靠性的要求更高。香農第二定理［1］證明，信息傳輸速率在小于信道容量的前提下，通過合理的信道編碼可以提高傳輸速率，實現更可靠的傳輸。極化碼就是第一個被嚴格證明可在二進制離散無記憶信道（Binary-Discrete Memoryless Channel，B-DMC）下達到信道容量的編碼方法。

早期的信道編碼技術是把信息序列劃分成不同的組，每組中增加冗余比特表示信息比特之間的代數關系。1949 年，第一個實用的差錯控制編碼方案是由漢明（Rich?ard Wesley Hamming）提出的漢明碼（Hamming Code）［2］。漢明碼一組包含4 個連續的信息比特，將組內4 個比特之間的線性組合用3 個比特表示，并將計算結果放在4 個比特后面一同發送。漢明碼最多可糾正1 個比特的錯誤或檢測出2 個比特的錯誤。弗蘭克·格雷（Frank Gray）在1953 年提出了格雷碼（Gray Code）［3］。格雷碼是通過對每個碼字增加一位總的奇偶校驗位進行擴展，連續的兩個數只有一個位元變化。由于這種特性，格雷碼目前常用于數字信號與模擬信號之間的轉換。1954 年，Reed［4］和Muller［5］提出通過分組保證最大碼字距離的RM 碼（Reed-Muller code）。BCH 碼是由Hocquenghem［6］和Bose 等［7］在20 世紀60 年代分別獨立發明的碼字，其具有的循環特性可糾正多個錯誤符號。BCH 碼在衛星通信和磁盤驅動器等領域作出了重要貢獻。Reed 和Solomon［8］在1960 年發明RS 碼（Reed-Sol?omon code）。RS 碼是一種前向糾錯的編碼方式，該碼字目前常應用于商業的光碟領域。

隨著信道編碼技術的發展，概率編碼成為了研究熱點。概率編碼不是尋找較大的碼字距離，而是設計一種平均性能最優且復雜度較低的碼字。1954 年，Elias［9-10］提出乘積碼，第二年又提出卷積碼（Convolutional code），通過依次連續地進行編碼，編碼器的輸出與此刻以及之前的輸入都有相關性；1966 年，Forney［11］提出級聯碼，首先將簡單的短碼單獨進行編碼作為內碼，然后將內碼串行級聯構成長碼作為外碼，并對外碼繼續編碼。在級聯的思想下，1993年，法國教授Berrou 等［12］在日內瓦舉行的國際通信大會（ICC）上提出一類稱為Turbo 碼的并行級聯碼，開啟了Tur?bo 碼研究的熱潮。Turbo 碼中的兩個編碼器分別進行編碼，并將編碼結果通過偽隨機的交織方式并行級聯。譯碼時為了緩解門限效應，兩個解碼器之間進行迭代譯碼，譯碼過程與渦輪增壓的工作流程相似，所以被稱為Turbo 碼。Turbo 碼也被應用于3G 和4G 蜂窩網絡。

1962 年，Gallager［13］提出低密度奇偶校驗碼（Low Den?sity Parity Check Code，LDPC），因無法實現譯碼，1981 年Tanner［14］通過Tanner 圖更形象地解釋了LDPC 的譯碼步驟。1996 年，MacKay 等［15-16］實現了LDPC 的譯碼，同時延伸LDPC 的思想提出非正則的LDPC 碼，性能甚至超過Tur?bo，一度成為性能最佳的編碼方案。LDPC 碼具有譯碼復雜度低、碼率靈活、具備更低的錯誤平層（Error Floor）等優點，在較大容量的通信以及對誤碼率要求苛刻的環境中表現優異。但LPDC 硬件資源消耗大，編碼復雜度高。

雖然Tanner 圖的發現可幫助編碼研究人員更形象地分析編碼過程，但是仍然沒有發現容量可達的編碼方案。土耳其Bilkent 大學教授Arikan［17-18］發現信道容量通過一系列信道變換會產生兩極分化的效果，并利用這一現象提出極化碼（Polar Codes）。極化碼可在碼字無限長的情況下，經過B-DMC 信道進行傳輸，其是信道容量可達的。極化碼一經提出就受到全世界矚目，眾多學者不斷對極化碼進行研究與改進。如今極化碼的性能已與LDPC 碼和Tur?bo 碼相近，甚至更好。極化碼結構簡單，具有編譯碼復雜度低、低延遲等特點，更符合未來5G 的要求。2016 年，美國當地時間11 月17 日，經過中國華為等公司的努力，極化碼成為了5G 標準之一。

雖然極化碼結構簡單、編譯碼復雜度低，但有限的碼長令極化碼的極化效果不夠顯著，若要使用這些信道進行信息傳輸，譯碼性能會有所損失［19-20］。由于極化碼需要進行信道極化操作，結構比較固定，碼長不夠靈活，所以當碼長與實際需求不匹配時，需要對極化碼進行鑿孔操作。但當母碼碼長較長，需要鑿孔的比特則有可能增多，從而增加編碼復雜度以及譯碼的性能損失。本文通過實現碼長更靈活的多維內核極化碼，減少鑿孔比特個數，提出基于多維內核極化碼的鑿孔算法，并建立多維內核極化碼的鑿孔算法模型。該算法相比基于2 維內核極化碼的鑿孔算法具有更好的性能，因此對于多維內核極化碼的實際應用具有重要意義。

1 基于2 維內核與3 維內核極化碼的鑿孔算法

文獻［21］提出一種使用2 維內核與l維內核混合構造的可靈活實現碼長的極化碼。在信道極化過程中，不再固定使用兩個信道進行信道合并操作，而是使用ns信道在相應位置進行信道合并與信道分割操作。信道極化過程中需要使用不同維度的內核，每個ni都對應一個ni×ni內核矩陣Tni，則生成矩陣為GN?Tn1?…?Tns，此時N個碼字序列x可通過x=uGN獲得。當Tni的順序不同，生成矩陣不同，極化碼的極化效果也不同。以2 維內核和3 維內核為例，將T3放在最靠近發送端的一端，構造2 維內核和3 維內核混合的極化碼。以（6，3）極化碼為例，將信道極化過程分為兩階，并建立生成矩陣，如式（1）所示，對應的編碼結構如圖1 所示。

相比Arikan 提出的極化碼，在接收端x與y是通過反序重排進行映射以節省硬件資源，而多維內核極化碼是通過經典排序算法得到信道輸入端與輸出端的對應關系，其排序算法是從接收端開始，將每次的排序結果用矩陣Pi表示，則最終排序結果為P1。由原始極化碼可知，最終排序結果是通過每個RNi進行排序得到的，其中，接收端對應發送端的序列則是所有RNi的逆操作。在多維內核中，接收端序列是所有Pi結果的逆操作，即P1=(P2…Ps)-1。每一階的Pi(i＞1) 可通過Pi=(Qi|Qi+Ni+1|…|Qi+(N/Ni+1-1)Ni+1)得到，最后一階的排序結果Ps=Qs。其中，Qi計算公式如下：

Fig.1 Encoding structure of multi-kernel polar code for G6= T2?T3圖1 G6= T2?T3的多維內核極化碼編碼結構

以N=6 的極化碼為例，若要獲得接收端與發送端的對應位置，先計算P2，具體公式如下：

使用不同的3 維內核進行信道極化，編碼結構也不同，本文后續的T3表示方法均使用式（4）。

2 算法設計

在實際應用中，當確定極化碼的K個信息比特時，如何調整編碼速率以滿足物理信道的信道容量是一個重要問題。雖然可通過使用多維內核以低復雜度實現更靈活的極化碼碼長，但對于極化碼而言，編碼時信道極化每一階的結構固定，僅通過多維內核的調整無法實現任意碼長。鑿孔算法可實現極化碼的任意碼長，并解決了碼率適配等問題。

2.1 構造方法

極化碼通過N個獨立的信道經過信道合并操作引入相關性，并使用其中的M個信道進行傳輸。不傳輸信息的信道是一個容量為零的虛擬信道，故鑿孔比特的個數m=N-M。

設信道接收錯誤的概率為p，通過T3所處的階進行編碼，每個子信道傳輸錯誤的概率分別為1-(1-p)3、1-(1-p) -(1-p)2+(1-p)3和1-2(1-p)+(1-p)2。在BEC 信道下，p=Z(W),I(W)=1-Z(W)，經過信道極化后，信道容量計算公式如下：

通過公式計算，若T3內核與T2內核傳輸鑿孔比特，當且僅當第一個信道或全部信道都進行傳輸時，才能滿足信道容量守恒和鑿孔信道收發兩端信道容量同時為0 的要求。

在噪聲方差為δ2的AWGN 信道下，假設發送全零序列，則對數似然比為：

假設llr值的概率密度函數為，通過分析llr值計算公式，得到使用T3的高斯近似遞歸公式如下：

則SC 譯碼的誤幀率（BLER）上界如下：

在2dB 的情況下，在T3內核中傳輸一位鑿孔比特，通過計算得到各子信道的錯誤概率如表1 所示。當傳輸一個鑿孔比特時，鑿掉T3中的第一個信道可獲得最小的錯誤概率。

Table 1 The error probability of subchannels for T3after puncturing one bit表1 T3內核鑿掉一個比特后各子信道錯誤概率

當使用T3內核編碼進行信道極化后，根據經典排序算法，將每個3 維內核中的第一個信道連續地排序到前Nv3，在此集合中選擇信道傳輸鑿孔比特，則可保證收發端傳輸鑿孔信道的對應關系。此時發送端的鑿孔方案可描述為：若使用2 維內核和3 維內核極化碼執行鑿孔算法，依次使用T3內核中的第一個信道傳輸鑿孔比特。

2.2 信息位選擇

極化碼作為一種線性分組碼，碼的最小距離對譯碼性能有著重要影響。在執行鑿孔算法后，由于m 個信道傳輸鑿孔比特，此時將虛擬信道在生成矩陣中對應的行和列全部置為0，重新計算距離譜，從中選出K 個最大的最小距離對應序號，并使用相應位置的信道傳輸信息。當鑿孔比特m∈[1/4 ?N,1/2 ?N]時，在發送端將T3中的第一個信道用來傳輸鑿孔比特，此時執行鑿孔后的最小距離譜如下：

在T3內核中選擇u1傳輸一位信息比特，選擇u1和u2傳輸兩位信息比特。重新構造生成矩陣時，未經過排序的最小距離譜為=(2,1)?(n-2)?。若在接收端執行鑿孔算法，利用前m個信道傳輸鑿孔比特，得到接收序列=(p1,…,pm,…,pN)，通過排序算法得到發送端執行鑿孔算法的發送序列?=?P1。從距離譜中選取K個最大的最小距離對應序號放入集合I，集合I就是鑿孔后的信息集合，具體算法如下：

2.3 性能分析

本文建立2 維內核與3 維內核模型，在AWGN 信道下進行仿真，采用BPSK 進行調制，發送10 萬幀測試數據，構造了（72，36）極化碼和（192，96）極化碼，生成矩陣分別為。

對于（72，36）極化碼，在2dB 下分別通過高斯近似和距離譜選取信息集合A的性能曲線對比如圖2 所示。圖中分別給出在SCL8 譯碼器下BER 與BLER 的性能，由性能曲線可知，通過距離譜選取的信息集合極化碼BLER 性能優于高斯近似選取的信息集合，但BER 的性能沒有得到提升。當BLER=10-3時，會有0.8dB 左右的增益。

圖3 為（191，96）極化碼的性能曲線，其中（191，96）極化碼是基于（192，96）多維內核極化碼通過執行本文提出的鑿孔算法得出的。由性能曲線可知，當BLER=10-4時，基于多維極化碼的鑿孔算法有0.55dB 左右的增益。

Fig.2 Performance curve of selection information set A GA and distance spectrum圖2 高斯近似與距離譜選取信息集合A 性能曲線

Fig.3 The performance curve of（191，96）polar code圖3（191，96）極化碼性能曲線

3 總結與展望

本文對2 維內核與3 維內核極化碼進行了深入研究，通過發送端和接收端傳輸鑿孔比特信道的對應關系獲得鑿孔模式，從而實現任意碼長的極化碼。在執行鑿孔后的生成矩陣中重新計算距離譜，重新選擇最大的最小距離信道作為信息集合A。實驗結果表明，基于多維極化碼的鑿孔算法與基于原始極化碼的鑿孔算法具有相似的性能，甚至超過了基于原始極化碼的鑿孔算法性能。

隨著數字時代的發展，人們對移動通信的要求越來越高。極化碼是近年來信道編碼領域的研究熱點之一。本文在實現更靈活的碼長和碼率方面進行了一定改進，但多維極化碼的編譯碼仍有改進的空間。在構造多維內核極化碼時，高維內核處于不同的階，對極化碼的性能有著很大影響。為獲得更好的譯碼性能，需要對高維內核編碼時處在什么位置等問題作進一步研究。