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

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

2.1信道極化

(1)

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

(2)

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

(3)

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

(4)

(5)

(6)

其中:

(7)

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

(8)

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

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

將式(1)改寫(xiě)如下：

x=uAGA+uACGAC

(9)

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

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

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]中指出對(duì)于碼長(zhǎng)趨于無(wú)窮時(shí)的Polar碼，其理論性能可到達(dá)香農(nóng)極限。然而，對(duì)于有限碼長(zhǎng)的Polar碼，尤其是短碼長(zhǎng)的時(shí)候，由于信道極化速度慢的原因，其性能相比Turbo碼LDPC等一直不理想。

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

圖1　信道極化

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

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

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

(1) 首先對(duì)Polar碼的各比特信道按照可靠度進(jìn)行排序。對(duì)于碼長(zhǎng)為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) 對(duì)指定信息位上的信息進(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)串行級(jí)聯(lián)。如圖2所示。

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

3.2譯碼

(13)

本文采用文獻(xiàn)[9]中提出的改進(jìn)后的SC譯碼算法。開(kāi)始階段該譯碼算法同SC譯碼算法一樣，譯碼進(jìn)程從第一位開(kāi)始按照式(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條路徑里選出一條，接下來(lái)的譯碼過(guò)程將沿著選出的路徑以SC算法向后譯碼。

4性能分析

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

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

圖4　性能仿真曲線

5結(jié)語(yǔ)

本文在Polar碼的基礎(chǔ)上進(jìn)行內(nèi)碼編碼形成兩級(jí)串行級(jí)聯(lián)的編碼結(jié)構(gòu)旨在通過(guò)利用原本凍結(jié)的比特信道對(duì)不穩(wěn)定的信息位進(jìn)一步約束，以提高不穩(wěn)定信息位的可靠性，從而從整體上提升Polar碼的性能。相比原碼字級(jí)聯(lián)編碼后并未增加額外的冗余，其碼長(zhǎng)以及碼率保持不變。本文以碼長(zhǎng)256，碼率0.5 的Polar碼為例進(jìn)行了仿真，對(duì)特定信息位進(jìn)行內(nèi)碼編碼，并針對(duì)該級(jí)聯(lián)結(jié)構(gòu)采用了改進(jìn)的譯碼算法，仿真結(jié)果顯示整體性能提升約0.3 dB，且復(fù)雜度并沒(méi)有明顯提高。雖然性能提升的空間和幅度有限，但本文為提升Polar有限碼長(zhǎng)性能提供了新的思路并為將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ái)的寬帶頻譜感知系統(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)目：國(guó)家自然科學(xué)基金(No.61501508)

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

中圖分類號(hào)：TN927.2

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

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

作者簡(jiǎn)介：

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

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

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

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