极化码低时延列表连续删除译码算法

王美洁，郭　锐

(杭州电子科技大学 通信工程学院，浙江 杭州 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