極化碼低時(shí)延列表連續(xù)刪除譯碼算法

王美潔，郭　銳

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

?

極化碼低時(shí)延列表連續(xù)刪除譯碼算法

王美潔，郭銳

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

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

極化碼；SCL譯碼；時(shí)延；并行譯碼

0　引　言

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

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

1　極化碼

1.1極化碼簡介

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

1.2極化碼SCL譯碼

(1)

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

2　改進(jìn)SCL譯碼

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

(2)

根據(jù)式(1)，有：

(3)

由上述推導(dǎo)，可以得到合并遞推信道轉(zhuǎn)移概率的遞推公式：

(4)

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

1)初始化：path=1。

2)fori=1：N/M。

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

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

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

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

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

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

(5)

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

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

3　仿真結(jié)果與性能分析

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

表1　種譯碼算法不同碼長的時(shí)延

圖3　三種譯碼器不同碼長的時(shí)延比較

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

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

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

4　結(jié)　語

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

[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]李斌, 王學(xué)東, 王繼偉. 極化碼原理及應(yīng)用[J]. 通信技術(shù), 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—)，女，碩士研究生，主要研究方向?yàn)闊o線通信、信道編碼；

郭銳(1980—)，男，博士，副教授，主要研究方向?yàn)闊o線通信、信道編碼。

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