一種兩級Polar碼串行級聯(lián)算法研究*

吳東升，劉愛軍，張應(yīng)憲，張青雙

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

?

一種兩級Polar碼串行級聯(lián)算法研究*

吳東升，劉愛軍，張應(yīng)憲，張青雙

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

摘要：極化碼(Polar)作為目前唯一一種從理論上證明了能夠達(dá)到香農(nóng)(Shannon)極限的碼字，且編譯碼復(fù)雜度低，已成為編碼領(lǐng)域的一大研究熱點(diǎn)。然而，受信道極化速度的限制，有限碼長的Polar碼性能劣于當(dāng)前應(yīng)用比較成熟的LDPC碼，Turbo碼等?；诖?，提出了基于兩級極化的級聯(lián)編碼方案，并針對該編碼方案采用了改進(jìn)的譯碼算法，實(shí)現(xiàn)了有限碼長Polar碼的性能提升。仿真結(jié)果顯示，性能提升約0.3 dB。文章的研究成果將為提升有限碼長Polar碼性能開辟一條有效途徑。

關(guān)鍵詞：有限碼長；系統(tǒng)極化碼；兩級極化碼；改進(jìn)的譯碼算法

0引言

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

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

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

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

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

2信道極化與系統(tǒng)Polar碼編碼

2.1信道極化

(1)

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

(2)

式中，對于碼長為N的Polar碼，經(jīng)過信道極化后，各個(gè)比特信道的轉(zhuǎn)移概率為[4]：

(3)

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

(4)

(5)

(6)

其中:

(7)

文獻(xiàn)[7]給出了此時(shí)各子信道誤碼率的計(jì)算公式如下：

(8)

由此我們獲得了各個(gè)子信道誤碼率的近似值，在此基礎(chǔ)上我們對各子信道進(jìn)行劃分，性能優(yōu)異的部分用來傳輸用戶信息，剩下的部分傳輸固定的信息。

2.2Polar系統(tǒng)碼編碼

將式(1)改寫如下：

x=uAGA+uACGAC

(9)

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

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

xB=uAGAB+uACGACB

(10)

xBC=uAGABC+uACGACBC

(11)

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

xBC=xB(GAB)-1GABC

(12)

3Polar碼內(nèi)碼構(gòu)造

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

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

圖1　信道極化

文獻(xiàn)[9]提出了通過對部分子信道進(jìn)行漢明碼編碼的形式保護(hù)這些相對較差的信道，從而從總體上實(shí)現(xiàn)碼字性能的提升。受此啟發(fā)，本文提出通過系統(tǒng)Polar碼對不穩(wěn)定子信道進(jìn)行二次極化的方式以提高Polar碼的性能。具體做法如下。

3.1內(nèi)碼構(gòu)造

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

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

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

在完成內(nèi)碼編碼后，編碼后的內(nèi)碼碼字連同其他用戶信息一起進(jìn)行Polar碼的編碼實(shí)現(xiàn)串行級聯(lián)。如圖2所示。

圖2　碼字構(gòu)造方案

3.2譯碼

(13)

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

圖3　譯碼進(jìn)程

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

4性能分析

仿真過程中采用碼長為256，總體碼率為0.5的polar碼，并在其中構(gòu)造了三組碼長為8的系統(tǒng)Polar碼，具體選取的用于構(gòu)造內(nèi)碼的子信道如下：

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

圖4　性能仿真曲線

5結(jié)語

本文在Polar碼的基礎(chǔ)上進(jìn)行內(nèi)碼編碼形成兩級串行級聯(lián)的編碼結(jié)構(gòu)旨在通過利用原本凍結(jié)的比特信道對不穩(wěn)定的信息位進(jìn)一步約束，以提高不穩(wěn)定信息位的可靠性，從而從整體上提升Polar碼的性能。相比原碼字級聯(lián)編碼后并未增加額外的冗余，其碼長以及碼率保持不變。本文以碼長256，碼率0.5 的Polar碼為例進(jìn)行了仿真，對特定信息位進(jìn)行內(nèi)碼編碼，并針對該級聯(lián)結(jié)構(gòu)采用了改進(jìn)的譯碼算法，仿真結(jié)果顯示整體性能提升約0.3 dB，且復(fù)雜度并沒有明顯提高。雖然性能提升的空間和幅度有限，但本文為提升Polar有限碼長性能提供了新的思路并為將Polar碼推向?qū)嶋H應(yīng)用做出了貢獻(xiàn)。

參考文獻(xiàn)：

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

[2]王志文，徐以濤，江漢等.基于USRP平臺的寬帶頻譜感知系統(tǒng)設(shè)計(jì)與實(shí)踐[J].通信技術(shù)，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

基金項(xiàng)目：國家自然科學(xué)基金(No.61501508)

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

中圖分類號：TN927.2

文獻(xiàn)標(biāo)志碼：A

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

作者簡介：

吳東升(1994—),男，碩士研究生，主要研究方向?yàn)镻olar編譯碼技術(shù)；

劉愛軍(1970—)，男，博士生導(dǎo)師，教授，主要研究方向?yàn)樾l(wèi)星通信系統(tǒng)；

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

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