LDPC码和Polar码级联系统的发展综述

王秀敏,钱方磊,吴卓铤

(中国计量大学 信息工程学院,浙江 杭州 310018)

如今是一个信息时代、智能时代,身边到处是智能家居、智能手机、电脑等各类智能电子设备.这些设备不仅丰富了我们的生活也拉近了人与人,人与社会之间的距离.随着人们对这种服务的要求越来越高,科技也被激发着急速的更新换代,对信息传输的有效性和可靠性提出了更高的要求.信道编码又称作前向纠错码[1](Forward Error Correcting, 简称FEC)在整个通信系统中担任着重要的角色,通常信道中含有大量的噪声干扰,这些干扰会让信息传输发生错误,因此非常需要信道编码来让系统具有一定的纠错能力以及抗干扰能力.信道编码理论[2]是Shannon在1948年发表的《A Mathematical Theory of Communication》(通信的数学理论)一文中提出的,这是现代信息论研究的开端,Shannon本人也被称为“信息论之父”.随着对信道理论的深入研究,越来越多优秀的信道编码方法纷纷出现,在性能上尽可能地接近Shannon极限,且复杂度较低易于实现,这就是实用好码.而在这漫长发展和不停探索的历史道路上最具有代表意义的就是1962年Robert G. Gallager首次提出的线性分组码LDPC Codes[3]和1993年Claude Berrou等人提出的Turbo Codes[4]. LDPC码在提出伊始,受限制于当时较弱的信息处理能力并没有受到大家的关注.但在三十多年后信息处理能力有了很大的提升,LDPC再次被学者提出,并给出了优秀的译码方案.自此,LDPC码的优势逐渐开始被开发利用.而Viterbi译码算法和网格编码调制(Trellis Coded Modulation, TCM)技术的出现使得卷积码被广泛运用.另一方面,2008年Erdal Arikan教授首次提出的信道编码新说Polar Codes[5],为第一个在理论上被证明可以达到香农极限的编码方法,并且拥有可以实用的线性复杂度的编译码算法,也因此被国际移动通信标准化组织3GPP在5G增强移动宽带场景的编码技术方案中确定为控制信道的编码方案.

1　LDPC码和Polar码级联结构研究现状分析

1.1　LDPC码和极化码的研究现状

首先LDPC码的编码方式是通过生成矩阵和信息序列相结合来进行编码,这种方法使得编码复杂度与码长的平方成正比,随着码长的增加这种复杂度很难被接受.针对编码复杂度较高这个问题,学者们做了一系列的改进研究.Mackay提出的下三角的编码方法[6]充分利用了低密度的特性.Neal提出的基于LU分解的编码方法[7]将矩阵进行LU分解.Richardson提出的近似下三角形的编码方法[8]则初步解决了高复杂度以及时延的问题.在编码过程不断被简化的过程中,译码也在逐步向着高性能低复杂度的方向改善.译码算法在软判决方向主要是BP算法,BP算法有着优异的性能但是硬件消耗较大难以实现.因此学者纷纷对BP译码算法中最为复杂的非线性计算过程的简化方法进行了研究.Fossorier提出了最小和(Min Sum, MS)算法[9],他用最小值代替了非线性计算,简化了算法却降低了性能.Jinhu Chen在最小和算法的基础上对性能做了改进,提出了归一化最小和算法(Normalized Min Sum, NMS)以及偏移最小和算法(Offset Min Sum, OMS)[10-11].学者对这两种改进的最小和算法中归一化因子和偏移因子的选取方式也是不断的创新,文献[12]对归一化因子的选取给出了理论上更加可行的方案.Mansour提出了TDMP算法(Turbo Decoding Message Passing)[13]对LDPC码的发展也起到了至关重要的作用.

极化码的编码研究主要分为两个方向,一是选取合适的信息位,二是构造优秀的生成矩阵. E. Arikan教授在提出极化码的同时,提出的信息位选取方式为巴氏参数(Bhattacharyya Parameter)法,Shengmei Zhao[14]对巴氏参数的构造也进行了进一步的深入研究.另一种信息位选取方式为2009年Mori Ryuhei提出的密度进化[15]方法.极化码译码也分两种主要的研究方向,一个是SC译码算法,另一个是BP译码算法.同样,E.Arikan教授在提出极化码的同时提出并详尽地描述了SC译码算法.2011年Ido Tal等人提出的SCL译码算法[16]是对SC译码算法在译码过程中出现的单向性无法纠错的弊端的一种改进,引入L个最优路径作为候选,这极大地改善了SC译码算法的性能,但也因此使得复杂度有所增加.Amin Alamdar-Yazdi等人提出的SSC译码算法[17]则通过对节点进行分类计算大大减少了译码计算的复杂度同时也降低了时延.随着BP算法通过图论理论引入到极化码译码算法之中,学者们对极化码迭代译码算法开始了深入的研究,张青双和刘爱军提出的改进BP译码算法[18]降低了误码率,Yuan Bo[19]等人提出了MS算法以及SMS(Scaled MS)算法,让其在译码算法的硬件上更容易实现.

1.2　基于LDPC和极化码的级联结构的研究现状分析

1966年Forney提出级联码[20],其基本结构如图1所示.

图1　级联系统基本结构Figure 1　Concatenated coding system

它有效地通过短分量码构造出了人们更希望的长码.在LDPC码和Turbo码出现之前,级联码常常采用RS(Reed-Solomon)码作为外码,用卷积码作为内码.这种拆分开的编译码方式大大缩减了级联码译码器的复杂度.在此之后也有学者在Forney的基础上提出了多级级联码[21],是对经典级联码的一种推广,它通过嵌套多个内码,或者说分割多次内码来使多级级联码可以达到最小汉明距离.级联码在纠正随机错误和突发错误的混合错误方面有着出色的表现.

2010年Bakshi M提出了Polar Codes的级联结构[22],其中以RS码为外码,Polar码为内码.2011年Eslami A紧跟着提出了用LDPC码替代RS码作为外码的级联结构[23].2017年Takumi Murata以及Qingshuang Zhang等人提出了基于CRC与极化码的级联[24-25].国内也有许多学者对极化码的级联做了较深入的研究[26-28].

2　级联系统的构造方法

级联码的总体结构基本类似,不过在大多数的级联系统中都不可或缺的需要交织器和解交织器,解交织是交织的逆过程,交织过程也可以理解为一种编码过程.级联码一个重点就是,如果外层编码后的码字之间有较多的相关性紧接着传输给内码编码器得到的最终码字在经过信道传输时产生的随机错误可能会对最终的结果造成成块的误码.因此,降低外码编码后码字序列间字符的相关性尤为重要.交织器采用简单短码来构造随机码长,这样就可以有效地让码字序列间的相关性得到下降.并且让编译码序列在不经过删除的码长范围内有着无记忆性.

极化码的编码原理是基于信道极化理论,N个相互独立的信道经过信道合并和信道分解后,N个信道呈现了极化现象,一部分信道的信道容量趋近于1而另一部分趋近于0.

这种信道极化现象可以用互信息链式法则解释[8]，如图2.

图2　二元传输机制Figure 2　Transmission mechanism basedon GF (2)

在把u1和u2传输进入信道之前,首先经过一个二元域运算得到x2=u1⊕u2和x2=u2.互信息如式(1)所示[8]：

(1)

l(u2:y1,y2,u1)=

l(u2:y2)+l(u2:y1,u1|y2)=

l(W)+l(u2:y1,u1|y2)≥l(W).

(2)

结合式(1)很容易可以得到

(3)

图3中由两个以及一个比特翻转构造而成.

图3　信道合并4阶示例图Figure 3　Example diagram of channel combine, N=4

因此,极化码的本质上依然是一种线性分组码,其生成矩阵[5]可以表示为

(4)

GN=BNF⊗n.

(5)

由于其特殊的生成矩阵的构造方法,可以让生成矩阵最短环不小于12(当n≥3)[22],极化码编码后的码字间没有相关性,因此它是级联码外码的理想编码方案.

级联码的编码是先由极化码编码器对信息位进行编码得到中间码字,再传入LDPC码编码器.这里可以直接传输中间码字给LDPC码编码器,也可以根据常用的LDPC码标准对中间码字进行补位处理.通常,级联方案需要面对外码编码后的码字是否足够随机的问题;而体现其随机性的标准就是外码的最短环,如果外码编码后码字对于信息较为集中,即最短环较小,则会在级联系统加入交织器和解交织器,来降低码字间信息的关联度.交织过程也可以看作是一个编码过程,它将经过纠错编码后的码字进行一定的排列组合,提高原有纠错编码的突发纠错的能力.本文采用极化码为外码LDPC为内码的级联方式,充分利用了极化码生成矩阵最短环最少为12的特性,不仅为LDPC码提供了很好的译码前提,也在结构上省去了交织解交织的过程.

译码过程则是编码过程的逆过程,利用LDPC码优秀的纠错性能先对信道传来的信息进行译码,接着将软信息LLR值传递给极化码译码器进行BP译码.理论上极化码译码器的输入值和输出值是没有线性关系的,通过BP译码进行双向迭代不断修正LLR值,将达到BP译码算法迭代次数前一次的输入端的LLR值传回给LDPC译码器.译码器之间迭代译码将会大大提高译码性能.

整体的级联码结构如图4.文献[23]则是描述了极化码与偶校验码的一种级联方式,其编码方式采用偶校验码为外码,极化码作为内码,其级联结构如图5.

图4　Polar-LDPC级联结构Figure 4　Structure of concatenation based on Polar codes and LDPC codes

图5　极化码与偶校验码级联的编译码系统Figure 5　Block diagram of encoding and decoding of PCC polar codes

其编码过程如下:

1)偶校验编码;

2)外码码字映射将外码码字中个比特一次映射到极化码信息位中,得到极化码编码器的输入信息;

3)极化码编码.

其译码过程为基于偶校验辅助的SCL译码算法,与经典的SCL译码算法相比,译码校验比特所根据的是其所在偶校验方程中信息比特的判决结果得到,而非概率.其步骤如下:

1)初始化输入,i=1保留路径数量L;

2)判断i≤N是否成立,成立则执行步骤3,否则执行步骤8;

3)判断是否为冻结位,是则执行步骤4,否则执行骤5;

4)设置当前路径上ui判决值为0,令i=i+1,返回步骤2;

5)判断是否为冻结位,是则执行步骤6,否则执行步骤7;

7)统计当前路径数量L′并对其进行分支扩展.当前每条路径在ui处可取值0或1,从而得到条备选路径,2L′条路径的度量值分别为该路径在ui处取值0或1的概率.判断2L′和L的大小,2L′≤L则保留2L′条路径;2L′>L则保留条度量值最大的路径;然后令i=i+1并返回步骤2;

9)结束译码.

另外对LDPC码和极化码以及基于二者的级联等未来发展的方向可以做出一定的预期,随着5G标准对信道编码标准的确定,LDPC码和极化码的研究必将进入新的阶段,如何针对极化码在二进制删除信道和二进制对称信道理论上可以达到Shannon极限的优势,设计出更加优秀更加简易的编码方案依然值得分析研究,相比较LDPC码历经了几十年的研究,多项技术已趋于成熟,相比之下,极化码像是一颗编码界的新星,还需要更深层次的探究.随着多入多出(Multiple-Input Multiple-Output, MIMO)技术的深入发掘,码长可以更长,对译码器硬件的实现可行性要求会更高,级联的方式会被更多的考虑.因此更多的极化码和级联码技术会被引用到其中.

3　发展趋势探讨

目前各大通信标准制定方对5G标准的制定依然在不断的起草更新中,LDPC码和极化码的研究和应用则是信道编码研究的主题.级联等方案依然需要被考虑,其优异的特性必然会被发挥出百分之百的作用.目前对于LDPC-Polar级联码的研究更多是在较高码率和各种特殊环境下,因此,寻找较低码率的级联方案和更适合商用的级联方案值得去探索.另外,在硬件方面,对复杂计算的简化,以及因此产生的修正因子的获取方案将会是而且一直会是研究的热点.