極化碼低時延列表連續刪除譯碼算法

王美潔，郭　銳

(杭州電子科技大學 通信工程學院，浙江 杭州 310018)

?

極化碼低時延列表連續刪除譯碼算法

王美潔，郭銳

(杭州電子科技大學 通信工程學院，浙江 杭州 310018)

應用列表連續刪除(Successive Cancellation List，SCL)譯碼算法的極化碼可以取得優異的譯碼性能。然而串行譯碼特性導致該算法的時延很高。提出一種遞歸信道合并的方法，用來構造多位比特同時譯碼的并行譯碼信道。通過遞歸信道的合并，兩位信息比特的聯合轉移概率可直接由極化信道轉移概率計算得到。仿真結果和性能分析表明，在改進譯碼算法與原始SCL譯碼算法相比性能損失可忽略不計情況下，提出的兩比特同時譯碼算法有效的減少了譯碼器的譯碼時延，而且在一定條件下，降低了譯碼復雜度。

極化碼；SCL譯碼；時延；并行譯碼

0　引　言

極化碼是編碼理論上的重大突破，可以實現二進制輸入對稱無記憶信道和任意離散無記憶信道的信道容量[1]。SCL譯碼的譯碼性能優于Arikan提出的連續刪除(Successive Cancellation，SC)譯碼算法，成為最有前途的極化碼譯碼方法之一[2]。但他們都有高譯碼時延的問題，無法設計高吞吐量譯碼器[3]。文獻[4-5]中提出的2b-SCL譯碼算法可以將譯碼時延減少至(2N-2)。文獻[6]中提出一種預計算技術，通過提高硬件利用率將硬件實現譯碼器的時延減少50%。

本文提出的改進SCL譯碼算法采用構造合并信道的方式，直接由Arikan提出的信道轉移概率求得多位比特信息聯合轉移概率。本文提出的兩比特同時譯碼算法譯碼性能在與原始SCL譯碼相比幾乎無性能損失的情況下，譯碼器時延相比原始譯碼器大大減少。同時，提出的譯碼算法相比本文中提到的另一種兩比特同時譯碼算法，譯碼時延有效減少，而且相應譯碼復雜度降低。

1　極化碼

1.1極化碼簡介

Arikan提出，二進制離散無記憶對稱信道進行信道合并和信道拆分后會產生極化信道。將K比特信息位和(N-K)“0”比特分別分配在極化信道可靠位置和不可靠位置，可以構造長度為N碼率為R=K/N的極化碼。通常，這些(N-K)“0”比特叫做凍結比特，K信息比特稱作自由比特[1]。

1.2極化碼SCL譯碼

(1)

由于局部優化搜索的限制，很多情況下SC譯碼器無法找到最優路徑。SCL算法可以解決這個問題。SCL譯碼器中包含列表長度L個 SC譯碼器組件，存活路徑的最大數值為L。因此找到正確譯碼路徑的概率顯著提高[3]。

2　改進SCL譯碼

由于串行譯碼特性，SCL譯碼器譯碼時延較長。為了減少由于按位譯碼導致的高時延問題，提出多位比特同時譯碼的譯碼方案，與文獻[4-5]中多比特同時譯碼方案不同，本文中用遞歸信道合并方式[7]實現多位比特同時譯碼。

(2)

根據式(1)，有：

(3)

由上述推導，可以得到合并遞推信道轉移概率的遞推公式：

(4)

由上述合并遞歸信道公式可以得到本文改進SCL算法，算法描述如下：

1)初始化：path=1。

2)fori=1：N/M。

3)路徑擴展：由path條路徑擴展至2|AMj|·path條候選路徑。

6)比較和篩選：比較所有候選路徑，選擇L條擁有最大合并遞歸信道轉移概率的路徑。

7)輸出：選擇碼字長度為N的擁有最大概率的碼字為譯碼碼字。

2b-SCL譯碼算法即M=2時的2比特同時譯碼算法，N=4極化碼具體譯碼過程如圖1所示。

圖1　2b-SCL譯碼算法的譯碼過程

其中，w1=u1⊕u2，w2=u3⊕u4，w3=u2，w4=u4。節點I和節點II分別對應式(1)中的遞推公式，節點III為乘法器，對應式(4)的信道合并公式。

(5)

圖2　2b-SCL譯碼算法的譯碼過程[4-5]

文獻[4-5]中提出的多位(2K)比特并行譯碼算法最后一個階段需要從22KL候選路徑中選擇L條最可靠路徑，而本文提出的譯碼算法只需要從2AMjL中選擇L條最可靠的路徑，22K的值一般比2AMj的值大，所以在2AMj值小于22K的值時，本文所述方案具有更低的譯碼復雜度。

3　仿真結果與性能分析

本文提出的2b-SCL譯碼器，文獻[4-5]中提出的2b-SCL譯碼器和原始SCL譯碼器在不同極化碼碼長情況下時延的比較在表1和圖3中給出，通過分析兩種改進SCL譯碼算法的譯碼時延發現，當碼長大于32時，與文獻[4-5]中提出的2b-SCL改進算法相比，本文提出的2b-SCL改進算法將減少約25%的譯碼時延，與原始SCL算法相比，本文提出的2b-SCL改進算法將減少約50%的譯碼時延。

表1　種譯碼算法不同碼長的時延

圖3　三種譯碼器不同碼長的時延比較

為了分析改進譯碼方案的糾錯性能，在AWGN信道下，本文分別采用碼長n=1 024，碼率R=0.5，L=32和碼長n=8 192，碼率R=0.5，L=32的極化碼進行仿真。圖4、圖5中分別繪出了兩種碼長2b-SCL譯碼算法的誤幀率性能曲線，通過比較改進算法與原始SCL譯碼算法的誤碼性能，發現改進譯碼算法的性能幾乎與原始SCL算法相同。在改進譯碼算法譯碼性能損失可忽略不計的情況下，由表1和圖3可以看出，改進譯碼器的譯碼時延大約為原始譯碼器的1/2，為本文中提到的另一種2b-SCL譯碼算法的3/4，譯碼延時得到顯著減少。

圖4　(1 024,512)極化碼糾錯性能比較

圖5　(8 192,4 096)極化碼糾錯性能比較

4　結　語

極化碼的SCL譯碼算法譯碼性能優于SC譯碼，而且通過級聯CRC可以進一步提高極化碼的性能，但高時延問題是設計高吞吐量譯碼器的瓶頸，為了減少SCL譯碼器的高時延，本文提出一種合并遞歸信道的方法，使改進譯碼算法的譯碼性能在與原始SCL譯碼算法相比性能損失可忽略不計的情況下，將譯碼時延減少為原始譯碼器的一半。同時，提出的改進譯碼算法與本文中提到的另一種兩比特同時譯碼算法相比，時延大約減少25%，且譯碼復雜度也降低。

[1]Arikan E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memory Less Channels [J]. IEEE Trans. Inf. Theory, 2009, 55(7): 3051-3073.

[2]李斌, 王學東, 王繼偉. 極化碼原理及應用[J]. 通信技術, 2012, 45(10): 21-23.

LI Bin, WANG Xue-dong and WANG Ji-wei. Theory and Application of Polar Code[J]. Communications Technology, 2012, 45(10): 21-23.

[3]YUAN B and Parhi K K. Successive Cancellation List Polar Decoder using Log-Likelihood Ratios[C]// 2014-48th Asilomar Conference on Signals, Systems and Computers. USA: Asilomar 2014-48th Annual,2014:548-552.

[4]YUAN B and Parhi K. Low-Latency Successive-Cancellation Polar Decoder Architectures Using 2-Bit Decoding [J]. IEEE Transactions on Circuits and Systems I-Regular Papers, 2014, 61(4):1241-1254.

[5]YUAN B and Parhi K. Low-Latency Successive-Cancellation List Decoders for Polar Codes with Multi-Bit Decision[J]. IEEE VLSI Syst.,2015,23(10):2268-2280.

[6]ZHANG C, YUAN B and Parhi K K. Reduced-Latency SC Polar Decoder Architectures[C]// IEEE International Conference on Communications 2012 (ICC 2012). Ottawa: IEEE , 2012: 3471-3475.

[7]XIONG C, LIN J and YAN Z. Symbol-based Successive Cancellation List Decoder for Polar Codes[C]// 2014 IEEE Workshop on Signal Processing Systems (SiPS). Belfast, UK: IEEE, 2014:1-6.

王美潔(1991—)，女，碩士研究生，主要研究方向為無線通信、信道編碼；

郭銳(1980—)，男，博士，副教授，主要研究方向為無線通信、信道編碼。

Reduced-Latency Successive Cancellation List Decoding for Polar Code

WANG Mei-jie，GUO Rui

(College of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018,China)

SCL (Successive Cancellation List) decoding algorithm could enjoy excellent decoding performance of polar code, and however, the characteristics of serial decoding would cause high time-delay. A recursive channel combination method is proposed to construct parallel decoding channel for multi-bit decoding. By this method, joint transition probability of two information bits could be calculated directly from the polarization of channel transition probability. Simulation results and performance analysis indicate that when decoding performance loss of the modified decoding algorithm is negligible, the proposed decoding algorithm could effectively reduce decoding time-delay as compared with the original SCL decoding algorithm, while under certain conditions,reducing the decoding complexity.

polar code; SCL decoding; latency; parallel decoding

10.3969/j.issn.1002-0802.2016.03.004

2015-10-19；

2016-01-28Received date:2015-10-19；Revised date：2016-01-28

TN911

A

1002-0802(2016)03-0270-04