极化码的置信传播译码算法优化

罗娜

摘要：极化码是信道编码的里程碑成果。串行抵消列表（SCL）译码取得较好的误码性能，但译码时延较大。置信传播（BP）算法可以有效减少译码时延和计算复杂度，然而现有的BP算法的译码因子图存在大量短环，其译码性能远远不及SCL译码算法。本文在详尽分析现有的BP译码算法后，提出了基于置换因子图的置信传播列表（CA-BPL）译码算法。仿真表明，该算法可以有效提高极化码的译码性能。

关键词：极化码;置信传播算法;短环;置换因子图;置信传播列表译码算法

中图分类号：TN911.22 文献标识码：A 文章编号：1007-9416（2018）12-0104-03

0 引言

极化码是5G中eMBB场景的编码方案标准[1]。二进制离散无记忆信道中，码长趋于无穷时信道容量逼近香农极限。串行抵消（SC）算法复杂度低，码长足够大时，可很好地还原信息比特。有限码长时由于信道未完全极化，信息比特难以正确判决且时延长。SCL算法[2]保留至多L条路径，若路径大于L，保留路径度量值最小的L条路径，L越大误码率越低。L≥N时等效为最大似然译码算法。CA-SCL算法显著提高了译码性能，但计算复杂度随L增大而增大，译码时延较大。

极化码的BP算法[3]实现并行译码，减小了译码时延，实现了软信息交互，但译码性能与SCL有很大差距。通过对中间信道增加LDPC保护的编码方案[4]可提升极化码BP误码性能，但改变了极化码的编码结构，增加了编码复杂度。的极化码有不同译码因子图[5-6]。当译码在当前因子图失败时，使用另一因子图直到译码结束，译码性能优于SCL，但与CA-SCL算法仍有差距。

本文提出的置信传播列表（CA-BPL）译码算法不调整极化码编码结构，采用不同置换因子图并行排列，增加CRC校验。仿真表明：CA-BPL算法的誤码性能显著优于目前已有的BP算法，L足够大时，译码性能优于CA-SCL算法。

1 极化码

个独立不相关的二进制离散无记忆信道经过信道组合和分离出现信道极化现象，转化为个相互关联的极化信道。当时，信道将趋于完全极化（一部分子信道趋于完全无噪信道即信道容量为1，另一部分子信道趋于完全噪声信道即信道容量为0）。信道容量为1的子信道为“好”信道，信道容量为0的子信道为“坏”信道，由于极化后信道的总容量不变，因此“好”信道占信道总数的比值为。极化码是基于极化现象提出的，“好”信道传输信息比特，“坏”信道传输冻结比特（一般为全0比特）。表示“好”信道个数即信息比特位数，则，表示码率，。当时，信息比特可通过“好”信道完全可靠传输，从理论上证明极化码是香农信道容量可达的信道编码。给定码长，极化码的编码结构就唯一确定了，可通过生成矩阵实现编码：      （1）

其中：，是的次克罗内尔幂，为信息比特，为编码码字。

2 BP算法

BP算法用于极化码译码有译码时延小，吞吐量大，实现软信息交互的优势。极化码的BP因子图由级构成，图1给出的极化码因子图。每级包含4个处理单元（PE）。处理单元如图2所示。每个节点需双向接收和发送消息（右传播消息和左传播消息），和表示节点位置，表示迭代次数。消息值为对数似然比，第级的左传播消息为译码器接收的值，，第1级的右传播消息为先验消息，，其他节点和设为0。定义，译码过程用式（2）表示。

（2）

3 基于置换因子图的BP译码算法

极化码的生成矩阵使得因子图存在大量短环。短环使得无论传输信道参数有多好，译码算法都会陷入因子图结构固有的错误模式。置换级数得到的因子图称为置换因子图，置换因子图会对变量节点进行混洗，避开停止集从而提升译码性能。

本文称[5] [6]中的有效置换因子图为完全随机置换因子图，记为置换集，。图3是极化码有效因子图。本文称保持因子图的第1级和第级不变，中间级数随机置换的因子图为部分随机置换因子图，记为置换集，。

“过完备因子图”BP译码是基于置换集的，直到满足“提前中止”条件或达到最大迭代次数时译码结束。该算法是一种多阶段译码过程，上一阶段译码失败进入下一阶段，译码时延长。没有合适的“提前中止”导致运算量大。未能进一步分析不同因子图，缺乏因子图选择机制。

本文提出多个并行置换因子图的置信传播（BPL）译码算法，BPL算法由L个并行BP译码器组成，每个BP译码器使用不同的因子图。满足“提前中止”（表1）结束译码。

CA-BPL添加了CRC校验码，在译码结束时输出满足CRC的误码率最低的码字，该算法不需调整极化码的编码结构，译码性能优于CA-SCL。如图4所示。

4 仿真与分析

本文给出极化码在中的仿真结果。BP算法最大迭代次数为。图5中BPL-R和BPL-S分别表示采用置换集和置换集。BPL-S译码性能更好，减小了因子图的搜索长度，后续仿真均采用置换集。随着L增长，译码性能显著提升。

图6中，CA-BPL与BPL在BER=10-4，L分别为10和100时，性能提升约0.3dB和0.1dB。CA-BPL与CA-SCL在BER=10-5，L为500时，性能提升约0.2dB。仿真表明，L足够大时，CA-BPL算法的性能优于CA-SCL算法。

5 结语

本文提出的CA-BPL算法是基于多个并行独立置换因子图的BP译码算法，因子图采用置换集，减小因子图的搜索长度，降低了误码率。在L足够大时，该算法达到了与CA-SCL相比拟的误码率性能。通过多个随机置换因子图并行排列，极大降低了译码时延。采用合适的“提前中止”条件减少了运算量。本文缺乏对置换因子图造成译码性能差异的进一步研究，初步探究出不同类别的因子图对译码存在影响，为将来研究提供有效参考。

參考文献

[1]E.Arikan，"Channel Polarization：A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels，"in IEEE Transactions on Information Theory， vol. 55，no.7，pp.3051-3073，July 2009.

[2]I.Tal and A.Vardy，"List Decoding of Polar Codes，"in IEEE Transactions on Information Theory， vol.61，no.5，pp.2213-2226，May 2015.

[3]Arkan E."Polar codes：A pipelined implementation[C]"Proc.4th Int. Symp.on Broad.Commun. ISBC 2010.2010：11-14.

[4]J.Guo，M.Qin，A.Guillén i Fàbregas and P.H.Siegel，"Enhanced belief propagation decoding of polar codes through concatenation，"2014 IEEE International Symposium on Information Theory， Honolulu，HI，2014，pp.2987-2991.

[5]N.Hussami，S.B.Korada and R.Urbanke，"Performance of polar codes for channel and source coding，"2009 IEEE International Symposium on Information Theory，Seoul，2009，pp.1488-1492.

[6]A.Elkelesh，M.Ebada，S.Cammerer and S.ten Brink，"Belief propagation decoding of polar codes on permuted factor graphs，"2018 IEEE WCNC，Barcelona，2018，pp.1-6.

Optimized Belief Propagation Decoding Algorithm for Polar Codes

LUO Na

（Central South University for Nationalities， Wuhan Hubei  430070）

Abstract：Polar codes are a milestone in channel encoding. The successive cancellation list （SCL） decoding algorithm achieves good error performance， it introduces a long decoding delay. The belief propagation （BP） algorithm can avoid large delay. However， the factor graph of the polar codes has a large number of short loops， which make decoding performance much poorer than the SCL algorithm. After analysis of the existing BP decoding algorithm， we propose a belief propagation list （CA-BPL） decoding algorithm based on random permutation factor graph. The simulation show that the scheme can improve the decoding performance of BP algorithm.

Key words：polar codes;BP algorithm;short loops;permuted factor graphs;CA-BPL algorithm