鄭昊

摘 要：極化碼是近年來(lái)提出的一種新型編譯碼技術(shù)，是目前唯一能被證明達(dá)到香農(nóng)極限的糾錯(cuò)編碼，是無(wú)線(xiàn)通信領(lǐng)域的重大突破，因此受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注和研究。各國(guó)學(xué)者相繼提出了一些譯碼算法，但這些算法在譯碼性能、延時(shí)、吞吐率、計(jì)算復(fù)雜度等方面表現(xiàn)的并不理想。通過(guò)對(duì)標(biāo)準(zhǔn)BP譯碼算法迭代過(guò)程方程式的改進(jìn)，文章提出了一種改進(jìn)的BP譯碼算法，經(jīng)仿真分析，對(duì)比標(biāo)準(zhǔn)的BP譯碼算法，改進(jìn)算法在保持譯碼性能不降低的前提下，有效降低了計(jì)算復(fù)雜度和時(shí)間復(fù)雜度。

關(guān)鍵詞：極化碼;置信度傳播譯碼;計(jì)算復(fù)雜度;時(shí)間復(fù)雜度;香農(nóng)極限;無(wú)線(xiàn)通信

中圖分類(lèi)號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2019）05-00-03

0 引 言

極化碼[1]由土耳其學(xué)者Arikan于2008年提出，在碼長(zhǎng)趨于無(wú)窮大時(shí)，極化碼可達(dá)到信道容量。極化碼具有結(jié)構(gòu)化、編譯碼復(fù)雜度低等特點(diǎn)，引起了各國(guó)學(xué)者的廣泛關(guān)注和研究。極化碼的核心在于信道極化現(xiàn)象，包括信道組合、信道分裂。通過(guò)對(duì)已知信道的極化處理，部分子信道容量趨近于1，部分子信道容量趨近于0，我們選擇在趨近于1的信道上傳輸有用的信息，在趨近于0的信道上傳輸冗余信息?；诖颂匦?，文獻(xiàn)[2]提出了串行抵消譯碼算法（Successive Cancellation，SC），文獻(xiàn)[3]提出了列表串行抵消譯碼算法（Successive Cancellation List，SCL），文獻(xiàn)[4]提出了置信度傳播譯碼算法（Belief Propagation，BP），但SC，SCL都是串行譯碼算法，存在延時(shí)較高、吞吐率較低的缺陷，而B(niǎo)P譯碼算法又涉及大量乘除運(yùn)算，計(jì)算復(fù)雜度較高。

針對(duì)上述譯碼算法的不足，文章提出了一種改進(jìn)的BP譯碼算法，對(duì)標(biāo)準(zhǔn)BP算法的迭代公式進(jìn)行改進(jìn)，并對(duì)數(shù)域簡(jiǎn)化。經(jīng)仿真分析，在保持譯碼性能不降低的前提下，可有效降低譯碼計(jì)算復(fù)雜度和時(shí)間復(fù)雜度。

1 BP譯碼算法

（N，K）的極化碼迭代譯碼因子圖網(wǎng)絡(luò)由（M+1）N個(gè)節(jié)點(diǎn)組成，其中N=2M，每一個(gè)節(jié)點(diǎn)（i，j）與相鄰節(jié)點(diǎn)進(jìn)行信息傳遞更新，當(dāng)達(dá)到預(yù)置的最大迭代次數(shù)之后，將迭代后的信息輸出再進(jìn)行硬判決譯碼。圖1所示為N=8的極化碼因子圖。

因子圖包括3層，每層包含4個(gè)基本運(yùn)算單元，用來(lái)更新和迭代計(jì)算譯碼信息，通過(guò)相鄰層之間的信息迭代更新，達(dá)到最佳譯碼性能。在相鄰層之間節(jié)點(diǎn)進(jìn)行迭代信息交換的過(guò)程中，包含左向迭代信息和右向迭代信息。在一次迭代過(guò)程中先計(jì)算從右至左的傳播信息，直至最左邊一層，再計(jì)算從左至右的傳播信息，直至最右邊一層，此時(shí)完成一次迭代運(yùn)算。圖2所示為BP譯碼算法的基本計(jì)算單元。

2 改進(jìn)的BP譯碼算法

上節(jié)詳細(xì)描述了標(biāo)準(zhǔn)BP譯碼算法，可以看出，標(biāo)準(zhǔn)算法在迭代計(jì)算的過(guò)程中，第i次迭代計(jì)算需要第i-1次迭代計(jì)算的數(shù)據(jù)作為輸入，增加了運(yùn)算成本。同時(shí)，標(biāo)準(zhǔn)算法是基于概率域的運(yùn)算，涉及大量乘除運(yùn)算，計(jì)算復(fù)雜度高且可能造成數(shù)據(jù)溢出。為了改善以上問(wèn)題，本文提出了一種改進(jìn)的BP譯碼算法，所有信息傳遞過(guò)程都在本次迭代內(nèi)完成，不涉及之前的迭代輪次，迭代過(guò)程如圖4、圖5所示，同時(shí)將概率域內(nèi)的運(yùn)算變換至對(duì)數(shù)域，以有效降低計(jì)算復(fù)雜度，并防止數(shù)據(jù)溢出。改進(jìn)的BP譯碼算法在對(duì)數(shù)域內(nèi)經(jīng)過(guò)min-sum[5]簡(jiǎn)化后，得到迭代過(guò)程方程式，見(jiàn)式（7）～式（10）。譯碼流程與標(biāo)準(zhǔn)BP譯碼算法相同。

3 譯碼算法仿真

對(duì)碼長(zhǎng)N=1 024，碼率R=0.5的極化碼，在BPSK（二進(jìn)制相移鍵控）和AWGN（加性高斯白噪聲）信道下對(duì)標(biāo)準(zhǔn)BP譯碼算法和改進(jìn)的BP譯碼算法進(jìn)行譯碼性能仿真，如圖6所示。從圖中可以看出，在迭代次數(shù)為40次，信噪比較小時(shí)兩種算法性能幾乎一致，隨著信噪比增大，改進(jìn)算法性能略?xún)?yōu)于標(biāo)準(zhǔn)算法。

迭代譯碼算法通常根據(jù)最差噪聲情況來(lái)設(shè)置固定的迭代次數(shù)，但是在實(shí)際信噪比情況下，較少的迭代次數(shù)就可以達(dá)到收斂條件。我們使用基于CRC的迭代終止準(zhǔn)則[6]對(duì)兩種譯碼算法進(jìn)行對(duì)比，如圖7所示。從圖中可以看出，相同條件下，改進(jìn)的BP譯碼算法所需要的迭代次數(shù)隨著信噪比的增加遠(yuǎn)小于標(biāo)準(zhǔn)BP譯碼算法，因此在時(shí)間復(fù)雜度上優(yōu)于標(biāo)準(zhǔn)BP譯碼算法。

4 結(jié) 語(yǔ)

本文對(duì)極化碼標(biāo)準(zhǔn)BP譯碼算法進(jìn)行了簡(jiǎn)要概述，通過(guò)分析不足對(duì)其進(jìn)行了改進(jìn)，提出一種改進(jìn)的BP譯碼算法，并對(duì)兩種算法進(jìn)行仿真比較。仿真結(jié)果表明，在譯碼性能略?xún)?yōu)于原算法的情況下，改進(jìn)的BP譯碼算法可以有效降低計(jì)算復(fù)雜度和時(shí)間復(fù)雜度。

參 考 文 獻(xiàn)

[1] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE trans. Inf. theory，2009，55（7）：：3051-3073.

[2] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes[C]// IEEE International Symposium on Information Theory（ISIT）， 2008：1173-1177.

[3] TAL I，VARDY A. List decoding of polar codes[C]// in Proceedings of the IEEE International Symposium on Information Theory Proceedings （ISIT11），2011：1-5.

[4] ARIKAN E. A performance comparison of polar codes and Reed-Muller codes[J]. IEEE communications letters，2008，12（6）：447-449.

[5]黃勝武.Polar Code譯碼算法的研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2017.

[6]刑超，趙生妹，鄭寶玉.極化碼置信傳播算法早期終止準(zhǔn)則的研究[J].信號(hào)處理，2016，32（3）：253-259.

[7]田佳佳.極化碼的譯碼算法研究[D].成都：電子科技大學(xué)，2016.

[8]吳道龍.極化碼構(gòu)造與譯碼算法研究[D].西安：西安電子科技大學(xué)，2016.

[9]刑超，徐順頻，趙生妹.一種基于整數(shù)操作的極化碼最小和譯碼算法[J].南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，35（1）：52-55.

[10]王繼偉.極化碼編碼與譯碼算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.