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

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

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

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

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

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

0 引言

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

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

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

1 連續(xù)消除譯碼

(1)

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

(2)

(3)

(4)

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

(5)

(6)

(7)

3 判決延遲譯碼

3.1 單路徑判決延遲譯碼

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

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

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

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

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

(8)

(9)

(10)

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

3.2 雙路徑判決延遲譯碼

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

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

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

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

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

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

4 算法分析

4.1 碼樹分析

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

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

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

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

(11)

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

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

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

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

(12)

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

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

(13)

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

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

(14)

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

4.2 復雜度分析

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

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

5 仿真結果

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

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

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

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

6 總結

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

[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-)，男，上海市人，博士，副教授，研究方向為無線通信和無線網、通信信號處理、編碼技術等.

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

TN911.22

A

2017.03.10)