袁遼， 倪衛(wèi)明(復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院，上海 200433)

極化碼的連續(xù)消除譯碼性能改進(jìn)方法

袁遼， 倪衛(wèi)明
(復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院，上海 200433)

研究了極化碼的連續(xù)消除譯碼性能改進(jìn)方法。提出了兩種改進(jìn)算法，分別為雙路徑判決延遲譯碼和含閾值可變路徑判決延遲譯碼。傳統(tǒng)的連續(xù)消除譯碼算法為碼樹上貪婪算法，不能修正在當(dāng)前節(jié)點(diǎn)之前的判決錯誤。利用判決延遲譯碼來為當(dāng)前譯碼節(jié)點(diǎn)提供修正上一個節(jié)點(diǎn)判決錯誤的機(jī)會。提出的雙路徑和含閾值可變路徑的判決延遲譯碼通過增加譯碼碼樹中的計算節(jié)點(diǎn)和增加存儲空間來提升譯碼性能。仿真結(jié)果顯示雙路徑判決延遲譯碼比較于傳統(tǒng)的連續(xù)消除譯碼方式，對譯碼性能有1.1 dB左右的增益，含閾值可變路徑判決延遲譯碼有進(jìn)一步的譯碼增益效果。

極化碼； 連續(xù)消除譯碼； 判決延遲譯碼； 雙路徑判決延遲譯碼

0 引言

極化碼[1]是由Arikan在信道極化的基礎(chǔ)上首次提出，在保證信道總?cè)萘坎蛔僛2]的情況下，二元離散無記憶信道產(chǎn)生極化現(xiàn)象: 一部分子信道表現(xiàn)出無噪信道的特征，另外一部分子信道表現(xiàn)為純噪聲信道的特征。無噪子信道的信道容量能趨于1，將需要傳輸?shù)男畔⒃跓o噪子信道上傳輸。剩余的子信道信道容量趨于0，該部分子信道傳輸收發(fā)方均已知的比特。由此信道極化從整體上提高信道傳輸?shù)目煽啃浴?/p>

對于極化碼的編碼，I. Tal 和A. Vardy[3]提出2種近似量化的構(gòu)造方法，有效降低碼長較大時編碼的復(fù)雜度。R. Mori 和T. Tanaka[4]提出使用卷積構(gòu)造的方法，進(jìn)一步提高編碼效率，達(dá)到線性的復(fù)雜度。極化碼的提出是基于二進(jìn)制刪除信道(BEC)，而H. Li和J. Yuan[5]提出在加性高斯白噪聲信道下的極化碼編碼的方法。Arikan在極化碼首次提出時同時引入連續(xù)消除譯碼 (successive cancellation, SC)方法。在連續(xù)消除譯碼的基礎(chǔ)上，列表連續(xù)消除譯碼[6]和堆棧連續(xù)消除譯碼[7]相繼提出。

本文以連續(xù)消除譯碼為基礎(chǔ)，提出兩種譯碼算法。在文中兩種方法分別稱為雙路徑判決延遲譯碼和含閾值可變路徑的判決延遲譯碼。兩種方法都采用了對于信息比特譯碼判決延遲的方案[8]，增加碼樹中的計算節(jié)點(diǎn)和路徑選擇，來提高譯碼性能。通過碼樹分析，本文比較了兩種譯碼算法和經(jīng)典的連續(xù)消除譯碼算法以及判決延遲譯碼算法的復(fù)雜度。仿真結(jié)果顯示提出的兩種算法對于譯碼性能有增益效果。

1 連續(xù)消除譯碼

(1)

對于碼長N=2n，1≤i≤n，后驗概率可如下遞歸計算如式(2)、(3)。

(2)

(3)

(4)

對于i∈I，相應(yīng)的遞歸計算方式如式(5)、(6)。

(5)

(6)

(7)

3 判決延遲譯碼

3.1 單路徑判決延遲譯碼

連續(xù)消除譯碼，可以看作是碼樹上的貪婪算法。如圖1所示(節(jié)點(diǎn)下方數(shù)字代表后驗概率)。

圖1 極化碼碼樹的路徑選擇

連續(xù)消除譯碼算法只對當(dāng)前節(jié)點(diǎn)進(jìn)行判決，一旦路徑選擇完成，將進(jìn)行到下一節(jié)點(diǎn)，圖中黑色實心單箭頭所示路徑為連續(xù)消除譯碼算法對于該碼樹的譯碼結(jié)果。但是，實際中，黑色空心雙箭頭所示路徑為后驗概率最大的路徑，連續(xù)消除譯碼在第一判決時，路徑選擇就發(fā)生了偏差，選擇的是當(dāng)前最優(yōu)，而不是全局最優(yōu)的解。

針對上述缺陷，本文采用判決延遲譯碼算法。連續(xù)消除譯碼中如果當(dāng)前節(jié)點(diǎn)的路徑選擇錯誤，算法沒有機(jī)會在對其進(jìn)行修正。而錯誤的路徑選擇，會對隨后的節(jié)點(diǎn)的路徑選擇產(chǎn)生干擾，引發(fā)更多的錯誤。因此，延遲判決譯碼算法，對于每一個節(jié)點(diǎn)，對于判決進(jìn)行延遲，采用后一步的節(jié)點(diǎn)的判決結(jié)果，來替代當(dāng)前節(jié)點(diǎn)的判決，為當(dāng)前節(jié)點(diǎn)的判決增加修正的機(jī)會。

對于i∈I，判決延遲譯碼表達(dá)式如下：

(8)

(9)

(10)

對于i=N，則判決方法和連續(xù)消除譯碼一致。特別指出，ui+1表示為下一個信息比特位。應(yīng)用判決延遲譯碼，對于圖1再次進(jìn)行譯碼判決，即可得到后驗概率最大的空心雙箭頭路徑，修正了連續(xù)消除譯碼的判決錯誤。

3.2 雙路徑判決延遲譯碼

將參與連續(xù)消除譯碼和判決延遲譯碼兩種算法的節(jié)點(diǎn)和路徑從滿二叉樹圖中取出，分別表示如圖2所示。

圖2 連續(xù)消除譯碼(右)，判決延遲譯碼(左)示意圖

顯然，延遲判決譯碼方法的對于算法的增益，源于對于判決節(jié)點(diǎn)計算的增加。將原本單節(jié)點(diǎn)的兩條路徑的比較，拓展為雙節(jié)點(diǎn)，四條路徑的比較，從而獲得對于連續(xù)消除譯碼的修正。單路徑判決延遲譯碼算法，在處理判決結(jié)果時，只保留了下一個節(jié)點(diǎn)中后驗概率最大的路徑。而對于ilt;N每一個判決延遲的每一個計算單元，都含有兩個節(jié)點(diǎn)和四條路徑。因此，考慮保留2條路徑，將算法改進(jìn)為雙路徑判決延遲譯碼。該算法步驟如下：

3.3 含閾值可變路徑的判決延遲譯碼

判決延遲譯碼引入保存雙路徑，為譯碼的進(jìn)一步增加了修正后驗概率最大路徑的能力。而使用最大似然譯碼等同于考慮所有可行路徑，可以找到全局最優(yōu)的路徑，但是算法所需要的復(fù)雜度隨碼長指數(shù)增長，而收益增長甚小。在判決延遲譯碼中，有下一信息位的后驗概率的輔助，考慮對于當(dāng)前保留節(jié)點(diǎn)和路徑數(shù)進(jìn)行動態(tài)修正。顯然，當(dāng)后驗概率值接近時，在隨后的信息比特的概率值比較時，更容易出現(xiàn)概率值大小關(guān)系反轉(zhuǎn)的現(xiàn)象。因此，引入閾值，對于判決延遲譯碼算法，進(jìn)行可變路徑的改變。具體算法如下：

步驟4. 遍歷ilt;N，重復(fù)步驟2, 3；當(dāng)i=N時，比較計算的是最終保留所有序列(2條或3條路徑)的后驗概率值，取較大者為最終譯碼序列。

4 算法分析

4.1 碼樹分析

對于ilt;N，連續(xù)消除譯碼，判決延遲譯碼，雙路徑判決延遲譯碼以及含閾值可變路徑判決延遲譯碼的基本計算單元的變化如圖3—圖5所示。

圖3 判決延遲譯碼(右)和連續(xù)消除譯碼(左)計算單元比較

對于連續(xù)消除譯碼算法，其參與計算的節(jié)點(diǎn)數(shù)VSC很容易給出式(11)。

VSC=2*K+(N-K)+1

(11)

圖4 單路徑延遲判決譯碼(右)和雙路徑判決延遲譯碼(左)計算單元比較

圖5 延遲判決譯碼(右)和含閾值可變路徑判決延遲譯碼(左)計算單元比較

而對于單路徑判決延遲譯碼算法，其節(jié)點(diǎn)數(shù)則與第一個信息比特有關(guān)。設(shè)第一個信息比特之前有VF1個固定比特，之后有VF2個固定比特，滿足VF1+VF2=N-K。不同于連續(xù)消除譯碼算法，在第一個信息比特之后的固定比特，將有傳遞2條路徑，因此，判決延遲譯碼算法所需計算節(jié)點(diǎn)數(shù)VOSDD為式(12)。

VOSDD=4*K+VF1+2*VF2-1

(12)

類似地，雙路徑判決延遲譯碼，相比較于單路徑判決延遲譯碼，只是對其選擇路徑的方式不同，所需的計算節(jié)點(diǎn)V2-OSDD并沒有增加式(13)。

V2-OSDD=4*K+VF1+2*VF2-1

(13)

而含閾值可變路徑判決延遲譯碼，設(shè)K*PK次保留3路徑，對于計算節(jié)點(diǎn)的額外增加，就由這些路徑引發(fā)。因此，其計算節(jié)點(diǎn)數(shù)量VK-OSDD如下式(14)。

VK-OSDD=4*K+2*(K*PK)+VF1+

(14)

雙路徑判決延遲譯碼相比于單路徑判決延遲譯碼，沒有增加額外的計算節(jié)點(diǎn)，只是對于存儲空間提出新的要求。而含閾值可變路徑判決延遲譯碼，則與閾值正相關(guān)的增加了所需的計算節(jié)點(diǎn)，并且同樣對存儲空間提出更多需求。

4.2 復(fù)雜度分析

我們對于提出的算法，進(jìn)行復(fù)雜度的分析，并與傳統(tǒng)的連續(xù)消除譯碼算法進(jìn)行對比。連續(xù)消除譯碼算法的復(fù)雜度已知為Nlog2N。單路徑判決延遲譯碼算法的復(fù)雜度已知為2Nlog2N-(N-1)。

對于雙路徑延遲譯碼算法，如碼樹分析中所示，其計算節(jié)點(diǎn)相較于單路徑延遲譯碼算法并沒有增加，優(yōu)化的部分為延遲譯碼中路徑選擇的方式。因此，雙路徑延遲譯碼算法復(fù)雜度維持為2Nlog2N-(N-1)。雖然計算復(fù)雜度上沒有增加，但是空間復(fù)雜度上，雙路徑延遲譯碼提升了一倍，需要單路徑延遲譯碼2倍的存儲空間。類似地，對于含閾值可變路徑判決延遲譯碼，不同閾值引發(fā)不同的算法復(fù)雜度的增加。顯然地，閾值越小，其引入的額外路徑更多，算法復(fù)雜度增加更多。因此，含閾值可變路徑判決延遲譯碼算法復(fù)雜度，受閾值影響，有上限和下限：當(dāng)不引入額外路徑，算法等同于雙路徑延遲譯碼，算法復(fù)雜度下限為2Nlog2N-(N-1)；當(dāng)全部每一次計算單元，都引入額外路徑，算法等效于三路徑延遲譯碼，算法復(fù)雜度上限為3Nlog2N-(N-1)。同樣的，含閾值可變路徑判決延遲譯碼也需要增加額外的空間復(fù)雜度，對存儲空間有額外需求。含閾值可變路徑判決延遲譯碼的主要貢獻(xiàn)在于，在更可能出現(xiàn)譯碼反轉(zhuǎn)的節(jié)點(diǎn)上增加更多的修正機(jī)會，以小的算法復(fù)雜度增加獲得較大的性能提升增益。

5 仿真結(jié)果

為展示提出的雙路徑判決延遲和含閾值可變路徑判決延遲譯碼對于譯碼性能的提升，在圖6中對比了雙路徑判決延遲譯碼和單路徑延遲譯碼以及傳統(tǒng)連續(xù)消除譯碼的性能對比，在圖7中對比了不同閾值下，含閾值可變路徑判決延遲譯碼與雙路徑延遲譯碼以及四路徑延遲譯碼的性能對比。仿真采用加性高斯白噪聲信道，選取極化碼長，碼率為0.5。

圖6 連續(xù)消除，判決延遲和雙路徑判決延遲的譯碼性能對比

圖7 閾值k=0.1,0.15,0.2下不同譯碼方案對比

仿真結(jié)果顯示的是不同信噪比情況下，不同譯碼算法的誤比特率。特別地，由于雙路徑判決延遲的譯碼性能已經(jīng)比較接近最大似然譯碼，在對比含閾值可變路徑判決延遲譯碼性能時，選用的信噪比跨度較小，來較為明顯地反映性能的提升。

6 總結(jié)

本文提出的雙路徑判決延遲譯碼算法和含閾值可變路徑判決延遲譯碼都可提升極化碼的譯碼性能。碼樹分析和算法分析顯示，本文提出的算法復(fù)雜度增加甚小。仿真結(jié)果顯示，在加性高斯白噪聲信道下，雙路徑判決延遲譯碼對于單路徑延遲譯碼有0.75 dB的增益，而含閾值可變路徑判決延遲譯碼對于譯碼性能有進(jìn)一步的增益。

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

[2] Arikan, Erdal. "Channel combining and splitting for cutoff rate improvement."[J]. IEEE Transactions on Information Theory 52.2(2005):628-639.

[3] Tal, Ido, A. Vardy. "How to Construct Polar Codes."[J]. IEEE Transactions on Information Theory 59.10(2011):6562-6582.

[4] Mori, Ryuhci, T. Tanaka. Performance and construction of polar codes on symmetric binary-input memoryless channels[C]//IEEE International Symposium on Information Theory IEEE, 2010:1496-1500.

[5] Li, Huijun, J. Yuan. A practical construction method for polar codes in AWGN channels, Tencon Spring Conference[C]//IEEE, 2013:223-226.

[6] Tal, Ido, A. Vardy. List Decoding of Polar Codes, Information Theory[J]. IEEE Transactions on 61.5(2012):2213-2226.

[7] Niu, K, K. Chen. Stack decoding of polar codes[J]. Electronics Letters, 48.12(2012):695-697.

[8] Hadi, Ammar, E. Alsusa, K. M. Rabie. A method to enhance the performance of successive cancellation decoding in polar codes. International Symposium on Communication Systems, Networks and Digital Signal Processing[J]. IEEE, 2016:1-5.

MethodsforEnhancingSuccessiveCancellationDecodingofPolarCodes

Yuan Liao, Ni Weiming
(Department of Information Science and Technology，F(xiàn)udan University，Shanghai 200433)

In this paper, we study methods to enhance successive cancellation decoding of polar codes. We propose two improved algorithms: two-path decision delay decoding and variable path decision delay decoding with the threshold. Conventional successive cancellation decoding is greedy algorithm in code tree, it means that successive cancellation decoding can’t correct errors from the former nodes. In this paper, the decision delay decoding is used to provide opportunity to correct previous error for the current node. The proposed two-path and variable path decision delay decoding can improve the decoding performance by increasing the computing nodes and increasing the storage space. The simulation results show that compared to successive cancellation decoding, the two-path decision delay decoding has 1.1dB gain on decoding performance. In addition, variable path decision delay decoding has more gain.

Polar code; Successive cancellation decoding; Decision delay decoding; Two-path decision delay decoding

袁 遼(1993-)，男，寧波人，碩士研究生，研究方向：信道編碼、通信算法優(yōu)化.

倪衛(wèi)明(1970-)，男，上海市人，博士，副教授，研究方向為無線通信和無線網(wǎng)、通信信號處理、編碼技術(shù)等.

1007-757X(2017)11-0042-04

TN911.22

A

2017.03.10)