一種兩級Polar碼串行級聯算法研究*

吳東升，劉愛軍，張應憲，張青雙

(解放軍理工大學 通信工程學院,江蘇 南京 210007)

?

一種兩級Polar碼串行級聯算法研究*

吳東升，劉愛軍，張應憲，張青雙

(解放軍理工大學 通信工程學院,江蘇 南京 210007)

摘要：極化碼(Polar)作為目前唯一一種從理論上證明了能夠達到香農(Shannon)極限的碼字，且編譯碼復雜度低，已成為編碼領域的一大研究熱點。然而，受信道極化速度的限制，有限碼長的Polar碼性能劣于當前應用比較成熟的LDPC碼，Turbo碼等。基于此，提出了基于兩級極化的級聯編碼方案，并針對該編碼方案采用了改進的譯碼算法，實現了有限碼長Polar碼的性能提升。仿真結果顯示，性能提升約0.3 dB。文章的研究成果將為提升有限碼長Polar碼性能開辟一條有效途徑。

關鍵詞：有限碼長；系統極化碼；兩級極化碼；改進的譯碼算法

0引言

1948年，Shannon在“通信中的數學理論”研究論文中提出[1]，在有噪聲的信道條件下，如果信息傳輸速率小于信道容量，存在一種編碼方式使得在碼長趨于無窮時，信息傳輸錯誤概率趨近于0。在此基礎上，Shannon采用隨機編碼的方法證明了這個著名的有噪信道編碼定理[2]。近幾十年來，眾多學者一直致力于尋找能夠達到該極限的碼字，直到極化(Polar)碼的出現。

Polar碼的核心思想是建立在信道極化理論的基礎上。信道極化理論最早由Arikan在2005年IEEE國際信息理論研討會上提出[3]，其基本原理是通過信道的重組與拆分提高信道的截止速率。隨后Arikan提出了一種以2為基數的DMC迭代重組與拆分的特殊方法，在理論分析的基礎上，提出了利用該迭代重組與拆分過程進行編譯碼的思想[4]，從而標志著Polar碼的正式問世。由于Polar碼從理論上證明了可獲得香濃(Shannon)極限容量，因此該編碼方案一經提出，立刻引起了科研工作者的廣泛關注。

在文獻[5]，詳細的介紹了離散無記憶信道(Discrete Memory-less Channel，DMC)的Polar編碼方法，分析了其可獲得的最大碼率，并基于信道重組與拆分變換過程給出了Polar碼的第一種譯碼算法，即連續刪除(SC)算法。在此基礎上，分析了基于SC譯碼算法性能界，證明了在保持關于碼長的對數編譯碼復雜度條件下，當碼長趨于無窮時，Polar碼可獲得Shannon極限性能。

然而，從現有研究成果可以看出，雖然Polar碼能夠從理論上證明可獲得Shannon極限性能，但是相比于現有應用相對成熟的近Shannon極限的編碼方案，如Turbo碼、低密度校驗(Low-Density Parity-Check,LDPC)碼，Polar碼在有限碼長時的誤碼率性能還比較差。

圍繞該點，本文首先概述信道極化基本理論，隨后，論文將重點分析影響Polar碼誤碼率性能的主要原因，并提出了通過內碼編碼以實現性能增益的方案。論文的主要結論將為Polar碼的有限碼長性能研究提供新的方向。

2信道極化與系統Polar碼編碼

2.1信道極化

(1)

對于二進制擦除信道和二進制對稱信道，文獻[5]中提出可采用計算各子信道的B-因子(Bhattacharyya因子——信道最大似然檢測錯誤概率的上界)，其定義為：

(2)

式中，對于碼長為N的Polar碼，經過信道極化后，各個比特信道的轉移概率為[4]：

(3)

通過計算上兩式可以得到各個子信道的B-因子，從中選取性能較優的作為。然而實時上在實際應用和仿真中往往遇到的是二進制加性高斯白噪聲(AWGN)信道，而上述方法很難獲得此時各子信道準確的B-因子。本文采用文獻[6]所述的高斯近似的方法。對與高斯隨機噪聲下的各子信道有：

(4)

(5)

(6)

其中:

(7)

文獻[7]給出了此時各子信道誤碼率的計算公式如下：

(8)

由此我們獲得了各個子信道誤碼率的近似值，在此基礎上我們對各子信道進行劃分，性能優異的部分用來傳輸用戶信息，剩下的部分傳輸固定的信息。

2.2Polar系統碼編碼

將式(1)改寫如下：

x=uAGA+uACGAC

(9)

式中，矩陣GA和GAC為GN的子集，且分別以A和AC為索引保留了GN中的各列。

在系統Polar碼中，編碼后的碼字由兩部分組成，xB和xBC。其中，B為整數集的子集，BC為其補集。由此，式(9)可改寫為：

xB=uAGAB+uACGACB

(10)

xBC=uAGABC+uACGACBC

(11)

式中，GAB保留了GA中以B為索引的各列，同理于其他矩陣。由于uAC是一個零向量，因此由信息碼字xB獲得校驗碼字的公式如下：

xBC=xB(GAB)-1GABC

(12)

3Polar碼內碼構造

文獻[8]中指出對于碼長趨于無窮時的Polar碼，其理論性能可到達香農極限。然而，對于有限碼長的Polar碼，尤其是短碼長的時候，由于信道極化速度慢的原因，其性能相比Turbo碼LDPC等一直不理想。

如圖1所示，經過極化后仍有部分子信道的信道容量介于0和1之間，由于完全好的信道數有限，則在傳信息時被迫使用這些不好不壞的信道，而這些差的信道很大程度上決定了Polar碼的誤碼性能。

圖1　信道極化

文獻[9]提出了通過對部分子信道進行漢明碼編碼的形式保護這些相對較差的信道，從而從總體上實現碼字性能的提升。受此啟發，本文提出通過系統Polar碼對不穩定子信道進行二次極化的方式以提高Polar碼的性能。具體做法如下。

3.1內碼構造

對于構造一個碼長為n，信息位數為k的內碼C(n,k)，具體步驟如下：

(1) 首先對Polar碼的各比特信道按照可靠度進行排序。對于碼長為n的內碼J=(j1,j2,…,jn)，若信息位數為k，則從原Polar碼信息位中選出k位最不穩定的作為內碼的信息位，而后從原Polar凍結位中選出n-k位最穩定的作為內碼的校驗位。令信息位的集合為I，校驗位的集合為H，則I∪U=J。

(2) 對指定信息位上的信息進行系統Polar碼的編碼，并將生成的校驗位賦給H中的各信息位。因此內碼的碼率R=k/n，本文采用碼率為0.5的系統Polar碼，則k=n/2。

在完成內碼編碼后，編碼后的內碼碼字連同其他用戶信息一起進行Polar碼的編碼實現串行級聯。如圖2所示。

圖2　碼字構造方案

3.2譯碼

(13)

本文采用文獻[9]中提出的改進后的SC譯碼算法。開始階段該譯碼算法同SC譯碼算法一樣，譯碼進程從第一位開始按照式(13)規則依次向后譯碼，而當譯碼路徑行進到J=(j1,j2,…,jn)中各信息位時，譯碼路徑分裂為并行的復數列，如圖3所示。

圖3　譯碼進程

當譯碼路徑行進到內碼的校驗位時，不再依據接收的信息進行估計，而是根據之前的信息位信息直接賦值。最后當譯至jn位時，根據比較各路徑的似然信息，從2k條路徑里選出一條，接下來的譯碼過程將沿著選出的路徑以SC算法向后譯碼。

4性能分析

仿真過程中采用碼長為256，總體碼率為0.5的polar碼，并在其中構造了三組碼長為8的系統Polar碼，具體選取的用于構造內碼的子信道如下：

經過兩級級聯編碼后的碼字相比原碼字并沒有額外增加冗余，其碼長、碼率與原碼字保持不變。圖4給出了仿真的性能曲線，由圖可以看出通過采用內碼編碼和改進后的譯碼方案，總體性能提升約0.3 dB。圖中虛線所示的性能曲線表征所有內碼涉及的信息位都完全正確譯碼的情況下Polar碼整體的誤碼性能，這也代表了采用內碼編碼所能實現的極限性能。雖然本文中所采用方案的性能與極限性能還有很大差距，但也在很大程度上提升了Polar碼的性能。

圖4　性能仿真曲線

5結語

本文在Polar碼的基礎上進行內碼編碼形成兩級串行級聯的編碼結構旨在通過利用原本凍結的比特信道對不穩定的信息位進一步約束，以提高不穩定信息位的可靠性，從而從整體上提升Polar碼的性能。相比原碼字級聯編碼后并未增加額外的冗余，其碼長以及碼率保持不變。本文以碼長256，碼率0.5 的Polar碼為例進行了仿真，對特定信息位進行內碼編碼，并針對該級聯結構采用了改進的譯碼算法，仿真結果顯示整體性能提升約0.3 dB，且復雜度并沒有明顯提高。雖然性能提升的空間和幅度有限，但本文為提升Polar有限碼長性能提供了新的思路并為將Polar碼推向實際應用做出了貢獻。

參考文獻：

[1]Shannon C E.A Mathematical Theory of Communication.Bell System Technical Journal,1948,27(6): 379-423.

[2]王志文，徐以濤，江漢等.基于USRP平臺的寬帶頻譜感知系統設計與實踐[J].通信技術，2015，48(06):750-754.

WANG Zhi-wen,XU Yi-tao,JIANG Han,et al.Design and Implementation of Wideband Spectrum Sensing System Based on USRP Platform [J].Communications Technology,2015,48(06):750-754.

[3]Arikan E.Channel Combining and Splitting for Cutoff Rate Improvement [C].In Proc.of IEEE ISIT 2005,2005: 671-675.

[4]Arikan E.Channel Polarization: A Method for Constructing Capacity-Achieving Codes [C].In Proc.of IEEE ISIT 2008,2008: 1173-1177.

[5]Arikan E.Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels [J].IEEE Transactions on Information Theory,2009,52(2): 3051-3073.

[6]Peter Trifonov.Efficient Design and Decoding of Polar Codes[J].IEEE Transactions on Information Theory,2012,60(11):3221-3227.

[7]Proakis J G.Digital Communications[M].America: McGraw Hill,1995,175-176.

[8]Arikan E and Telatar E.On the Rate of Channel Polarization [C].In Proc.of IEEE ISIT 2009,2009: 1493-1495.

[9]Seidl M and Huber J B.Improving Successive Cancellation Decoding of Polar Codes by Usage of Inner Block Codes [C].In Proc.of 6thIS on TC& IIP,2010: 103-10.

An Encoding Algorithm for Two-Stage Serial Cascade Polar Codes

WU Dong-sheng,LIU Ai-jun,ZHANG Ying-xian,ZHANG Qing-shuang

(Communication Engineer College,PLA University of Science and Technology,Nanjing Jiangsu 210007,China)

Abstract：As the first channel correcting of code known to achieve the capacity of symmetric channels,polar code now becomes a hot research topic in coding,and what is more,the coding and decoding complexities of polar code are fairly low.However,on account of the restriction by polarizing speed,the polar code with finite length is worse than some existing codes in performance,such as LDPC and Turbo.For improving the performance of polar code with finite length,a cascade coding scheme based on two-stage polarization is proposed,and for this coding scheme,an improved decoding algorithm is also adopted,and the polar code with finite length thus raised in its performance.Simulation indicates that the polar code with finite length has an improvement of about 0.3dB in performance.The research result described in this paper could open an effective way for improving the performance of polar with finite length.

Key words：finite code length;systematic polar codes;two-stage polar codes;improved decoding algorithm

doi:10.3969/j.issn.1002-0802.2016.02.003

* 收稿日期：2015-09-01；修回日期：2015-12-16Received date:2015-09-01；Revised date：2015-12-16

基金項目：國家自然科學基金(No.61501508)

Foundation Item:National Natural Science Foundation of China (No.61501508 )

中圖分類號：TN927.2

文獻標志碼：A

文章編號：1002-0802(2016)02-0135-04

作者簡介：

吳東升(1994—),男，碩士研究生，主要研究方向為Polar編譯碼技術；

劉愛軍(1970—)，男，博士生導師，教授，主要研究方向為衛星通信系統；

張應憲(1987—)，男，博士，講師，主要研究方向Polar碼編譯碼技術；

張青雙(1990—)，男，博士研究生，主要研究方向Polar碼編譯碼技術。