译码迭代次数约束下累积无率码的优化设计

雷维嘉, 陈胜男

(重庆邮电大学移动通信技术重庆市重点实验室, 重庆 400065)



译码迭代次数约束下累积无率码的优化设计

雷维嘉, 陈胜男

(重庆邮电大学移动通信技术重庆市重点实验室, 重庆 400065)

以最大化码率为目标设计的无率编码通常能够实现逼近容量的性能,但是这种编码在译码时需要进行非常多次(理论上是无穷多次)的迭代才能达到预期的误比特率性能。基于外部信息转移图的渐近收敛分析,提出一种在有限译码迭代次数约束下的非系统累积无率码编码度分布的优化设计方法,给出此优化问题的数学模型。通过求解该优化问题可得到满足要求的编码度分布函数。仿真结果表明,与以最大化码率为目标设计的编码相比,在有限的译码迭代次数下,所提出的方法设计的编码能获得更好的纠错性能,且译码迭代次数越小,性能优势越明显。

累积无率码; 迭代译码; 外部信息转移图; 迭代次数约束

0　引　言

数字喷泉码[1]最初是为了实现删除信道中高效可靠的传输而提出的。与传统的固定码率的编码不同,它在发送端编码时不需要事先固定码率,而是可以不断产生编码符号,直到接收端译码成功并反馈确认(acknowledge, ACK)信息给发送端后停止编码和发送。由于码率并不固定,因此是一种无率编码(rateless codes,RC)。无率码非常适合用于时变信道中信息的传输。

Luby传输(Luby transform, LT)码[2]是Luby在2002年提出的第一种实用的喷泉码,其在删除信道下有很好的性能。LT码的基本结构和非规则非系统的低密度生成矩阵(low density generator matrix, LDGM)码[3]类似,也可以用于噪声信道。但在噪声信道下,正如文献[4]中所指出,LDGM码存在高错误平层,且不会随着分组长度的增加而有所改善。文献[5]的研究也发现LT码在二进制对称信道(binary symmetric channel, BSC)和二进制输入加性高斯白噪声(binary input additive white Gaussian noise, BIAWGN)信道中存在明显的错误平层。Raptor码[6]通过级联一个高码率的预编码,有效地改善了错误平层的问题,但同时也增加了编码和译码复杂度。为了进一步降低Raptor码级联预编码带来的高复杂度,文献[7]提出了累积无率(accumulate rateless, AR)码的概念,它由在LDGM无率码编码器后级联一个累加器构成。这种码在高斯白噪声(additive white Gaussian noise, AWGN)信道下与Raptor码有着相当的性能,但编译码的复杂度更低。

无率编码在AWGN信道下的译码一般采用置信传播(belief propagation, BP)译码算法[8]。这种算法通过在变量节点和校验节点间迭代地传递消息进行译码。在无率码设计的相关文献中,多以最大化码率为目标设计优化的校验节点度分布以获得逼近容量的性能。这种码设计中优化的方向是获得逼近信道容量的最大码率,它的错误概率会随着码长和译码迭代次数的增加而减小。这种编码在设计时没有考虑译码迭代时的收敛速度,在BP译码时需要进行非常多次(理论上是无穷多次)的迭代才能获得预期的性能,这无疑带来了很大的译码复杂度。如果通过减小最大译码迭代次数从而减小平均译码迭代次数,该码的纠错能力又会有较大的下降。

实现译码复杂度和码率折中的编码的设计已成为近年来无率码设计中的研究问题之一。文献[9]针对码率固定的非规则重复累积(irregular repeat accumulate, IRA)码在删除信道下的译码复杂度和码率折中问题进行了研究。文献[10]给出了给定目标错误概率时,BIAWGN信道下译码迭代次数最小的非规则低密度奇偶校验(low-density parity-check, LDPC)码的设计。文献[11]从信息论的角度分析了无率码的性能和复杂度折中。文献[12-13]则给出了LT码的低复杂度译码算法。

在本文中,我们考虑BIAWGN信道下非系统AR码的译码复杂度-码率折中,从另一个角度出发,基于外部信息转移(extrinsic information transfer, EXIT)图[14]的渐近收敛分析,设计一种有限译码迭代次数约束下性能最好的非系统AR码。这通过在给定最大译码迭代次数时,以最大化译码器间传递的信息为目标来实现,通过求解凸优化问题可得到最优非系统AR码的校验节点度分布。仿真表明,与以最大化码率为目标设计的非系统AR码相比,在有限的译码迭代次数下,本文提出的编码方案能够获得更好的纠错性能,且译码迭代次数越小,所提方案的性能优势越明显。

1　AR码

1.1编码

图1　AR码的Tanner图

文献[15]指出采用优先选择度值最小的信息节点来产生校验节点的方法,使得各个信息节点的度数基本一致(记为ds),能够有效地改善LT码的错误平层。这样信息节点度分布为λ(x)=xds-1,即绝大多数信息节点的度都为ds(可能会存在极少数的信息节点度为ds+1或ds-1)。本文的仿真中涉及到的LT码的编码都采用该编码方法。

AR码的编码过程如下:

(1) 根据校验节点度分布ρ(x)随机选择一个度值d;

(2) 通过优先选择度值最小的信息节点选择d个信息节点;

(3) 将这d个信息节点进行模2加产生中间比特bk(k=1,2,…);

(4) 编码比特ck由当前中间比特bk和前一编码比特ck-1模2加得到,设c0=0,则

(1)

(2)

1.2译码及EXIT图

AR码采用BP译码算法,译码器包括3个部分:变量节点译码器(variablenodedecoder,VND),校验节点译码器(checknodedecoder,CND)和累加器译码器(accumulatordecoder,AD)。AD能够获得信道中的观测值。通常,将AD和CND作为一个译码单元,即AD&CND。非系统AR码的译码器结构如图2所示。图2中，互信息I的下标中的“A”为输入,“E”为输出。

图2　非系统AR码的译码器结构

(3)

接收符号的对数似然比值(logarithmlikelihoodratios,LLRs)定义为

(4)

式中，p(y|x)表示输入信号Pr(x=±1)=1/2的条件下,AWGN信道的输出信号y的条件概率密度函数。接收符号LLRs的方差为

(5)

AR码的译码器有VND、AD&CND两个分量译码器,所以有两类EXIT曲线,IE,VND～IA,VND和IE,AD&CND～IA,AD&CND曲线。类似文献[16]中的分析方法,可以得到非系统AR码的两条EXIT曲线对应的函数的表达式:

(6)

(7)

式中,IE,VND表示VND的输出互信息;IA,VND表示其先验输入互信息;IE,AD&CND表示合并的AD和CND的输出互信息;IA,CND表示CND的先验输入互信息;AD的输出互信息和先验输入互信息分别由IE,AD和IA,AD表示。J(·)为传输的BPSK符号与接收符号LLRs之间的互信息:

(8)

J(σ)是单调递增函数,存在唯一的反函数σ=J-1(I)。为了简便起见,使用文献[17]中给出的近似表达式来计算J(·)和J-1(·):

(9)

(10)

式中,H1=0.307 3,H2=0.893 5,H3=1.106 4。

图3为非系统AR码的EXIT图。x轴表示VND的输出互信息IE,VND以及AD&CND的先验输入互信息IA,AD&CND。y轴表示VND的先验输入互信息IA,VND以及AD&CND的输出互信息IE,AD&CND。定义AD&CND的EXIT函数为y=f(x),VND的EXIT函数为x=g(y),其中x=IE,VND=IA,AD&CND,y=IA,VND=IE,AD&CND,两者的具体表达式可由式(6)和式(7)得到。

图3　非系统AR码的EXIT图

2　编码度分布的设计

(11)

其中,第一个约束条件为保证译码成功的充分条件,即译码器本次迭代所传递的信息必须大于上次迭代传递的信息。第二个约束条件为非系统AR码的译码开始条件,即必须有度为1的校验节点存在。通过对一系列离散的信息节点度值ds求解问题(11)可以得到优化的校验节点度分布,即使得码率最大的ds和校验节点度分布ρ(x)作为最优解。

这种度分布优化问题在设计过程中并未考虑译码复杂度,为在最优码率下实现预期的误比特率(bit error rate,BER)性能,在BP译码时需要进行非常多次(理论上是无穷多次)的迭代,在实际情况下,译码的迭代次数却是有限的。

本文考虑设计一种有限译码迭代次数约束下性能最好的码,从而实现译码复杂度-码率的折中。非系统AR码译码时,在进行L次迭代后的平均BER[7]如下:

(12)

式中,Q(·)定义为

(13)

在L一定时,只需要将问题(11)中的目标函数换为非系统AR码的平均误比特率Pe,就可以使得其经过一定的译码迭代次数后错误概率最小。由于J-1(·)是一个连续单调递增函数,而Q(·)是一个连续单调递减函数,最小化Pe等价于在L次迭代后使译码器间传递的信息y(L)最大化。

(14)

(15)

式中，h(y)=f(g(y))。经过足够多的迭代次数后,译码器会收敛于一个固定点y=f(g(y))=h(y),对于性能良好的码,这个点通常在y值接近于1时出现。

据此,优化问题转换为固定译码迭代次数下,最大化译码器间传递的信息:

(16)

式中,所有的约束条件关于ρj都是线性的。因此,如果目标函数y(L)是凹的,那么上述问题将是一个凸优化问题[18]。AD&CND的EXIT函数f(x)可以用式(17)表示

(17)

式中,fj表示度为j的AD&CND的转移函数。那么

(18)

可见,y是关于校验节点度ρj的线性函数。那么问题(16)中,目标函数和约束条件都是线性的,因此这是一个线性规划。文献[18]中指出,任何线性规划都是凸优化问题,该凸优化问题可用相关的优化工具求解。

对任意L值,都可以通过求解上式得到优化的校验节点度分布。观察式(16),可以看到,约束条件与最大迭代次数L都是相互独立的,且此优化问题只需知道f(x)和g(y)的表达式,而这对许多编码都是可得的。

由于式(16)是以最大化译码器间传递的信息为优化目标,因此将该方案称为最大化译码器间信息传递的方案,简称为最大化信息方案。

3　性能仿真和分析

在本节的仿真中,信息比特长度为K=10 000,采用BPSK调制方式,符号能量Es=1。凸优化问题式(16)通过Matlab的CVX工具箱求解。通过仿真不同信道容量下误比特率随码率的变化情况来验证编码的性能。为更好地反映本文方法设计的编码的性能,我们将其与以最大化码率为目标优化的编码进行性能比较。

图4给出信道容量C=3/4 bit/symbol (噪声标准差σn=0.677 0)的BIAWGN信道下的LT码、Raptor码和非系统AR码的BER性能,最大译码迭代次数设定为150。图中的横坐标为码率的倒数。其中,LT码采用文献[19]中的度分布,Raptor码的预编码为码率为0.95的(3,60)的规则LDPC码,非系统AR码的度分布通过求解本文提出的最大化译码器间传递信息的优化问题式(16)得到。从图4中可以看到,非系统AR码和Raptor码有着相当的BER性能,甚至优于Raptor码。LT码虽然在码率较大时有更好的性能,但是存在较高的错误平层,BER并不能随码率的下降而迅速下降,而非系统AR码和Raptor码则在仿真中没有出现错误平层。这是由于Raptor码通过在LT码编码器前级联一个预编码构成,在译码时,Raptor码先在内层进行LT译码,再在外层进行LDPC译码。一些在LT译码时没有纠正的错误可在LDPC码的译码中纠正,解决了LT码的高错误平层问题,大大改善了LT码在噪声信道中的性能。而AR码则是通过在LT编码器后级联一个累加器构成,解决了LT码的Tanner图中编码节点度值恒为1的问题,有效地改善了LT码的错误平层。与Raptor码级联一个预编码器相比,AR码仅需级联一个累加器,大大降低了编译码的复杂度,更便于实现。

图4　LT码、Raptor码和非系统AR码的BER性能

表1为信道容量C=3/4 bit/symbol (σn=0.677 0),C=2/3 bit/symbol (σn=0.766 6)和C=1/2 bit/symbol (σn=0.978 6)的BIAWGN信道下,采用本文提出的最大化信息传递的设计方法得到的不同译码迭代次数限制下的最优非系统AR码的校验节点度分布。图5～图7分别给出3种不同信道下,固定最大译码迭代次数L=20、80、150时,以最大化码率[7]和本文的以最大化译码器间传递信息为目标优化的非系统AR码的BER性能仿真结果。最大化码率的度分布通过求解式(11)得到,该优化结果与译码时限制的最大迭代次数L无关;而通过求解优化问题(16)可以得到在某一固定的L条件下,译码器间传递信息最大化的校验节点度分布。

表1　不同信道条件下的最优校验节点度分布

图5　不同译码迭代次数限制下的BER性能(C=3/4 bit/symbol)

仿真结果表明,在译码迭代次数限制的约束条件下,本文提出的最大化译码器间传递信息的设计方法设计的编码性能优于以最大化码率为目标的设计方法设计的编码。从图中可以看出,在迭代限制次数较小时,本文设计的编码的性能优势较为明显。随着迭代限制次数的增大,该性能优势逐渐减小。如在C=2/3 bit/symbol,迭代次数限制为L=20、80、150时,在获得10-5的误比特率时,与以最大化码率为目标设计的编码相比,本文设计的编码需要接收的码长缩短了0.3%、0.21%、0.09%,换算为减少的信噪比要求分别为0.025 7 dB、0.017 9 dB、0.007 2 dB。注意到以最大化码率为目标设计的编码在L=20、BER为10-5时,距离香农极限也仅为0.947 4 dB,本文方案0.025 7 dB的性能改善已经相当可观。在迭代次数足够大时,以最大化码率为目标设计的编码的性能已接近设计目标性能,因此与本文方案设计的编码性能相近。

图6　不同译码迭代次数限制下的BER性能(C=2/3 bit/symbol)

图7　不同译码迭代次数限制下的BER性能(C=1/2 bit/symbol)

4　结　论

以最大化码率为目标的编码设计方法通常能够实现逼近容量的性能,但是这种设计过程中并未考虑译码复杂度的问题,在BP译码时需要进行非常多次的迭代才能达到预期的BER性能。本文研究了BIAWGN信道中有限译码迭代次数约束下非系统AR码的优化设计。通过对EXIT图的渐近收敛分析,给出了编码校验节点度分布优化问题的数学模型,通过求解该优化问题可以得到任一译码迭代次数约束下纠错性能最好的非系统AR码。这种方法在编码设计时考虑了译码迭代次数,在译码复杂度和译码时延受限的实际应用中有着重要的意义。通过仿真比较了所提方法和以最大化码率为目标的设计方法所设计的非系统AR码的BER性能,结果表明,在有限的译码迭代次数约束下,本文所提出的方案设计的编码具有更好的误码性能,而译码迭代的限制次数越小,性能优势越明显。

[1] Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast[J].IEEEJournalonSelectedAreasinCommunications, 2002, 20(8): 1528-1540.

[2] Luby M. LT codes[C]∥Proc.oftheIEEESymposiumonFoundationsofComputerScience, 2002: 271-280.

[3] Garcia-Frias J, Zhong W. Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix[J].IEEECommunicationsLetters, 2003, 7(6): 266-268.

[4] Mackay D J C. Good error-correcting codes based on very sparse matrices[J].IEEETrans.onInformationTheory, 2002, 45(2): 399-431.

[5] Palanki R, Yedidia J S. Rateless codes on noisy channels[C]∥Proc.oftheInternationalSymposiumonInformationTheory, 2004: 37-42.

[6] Shokrollahi A. Raptor codes[J].IEEETrans.onInformationTheory, 2006, 52(6): 2551-2567.

[7] Chen S L, Zhang Z Y, Zhu L L, et al. Accumulate rateless codes and their performances over additive white Gaussian noise channel[J].IETCommunications, 2013, 7(4): 372-381.

[8] Jenkac H, Mayer T, Stockhammer T, et al. Soft decoding of LT-codes for wireless broadcast[C]∥Proc.oftheISTMobileSummit,2005：369-374.

[9] Grant A, Land I, and Wang G, Iteration-constrained design of IRA codes[C]∥Proc.oftheInternationalZurichSeminaronCommunications, 2012: 67-70.

[10] Smith B, Ardakani M, Yu W, et al. Design of irregular LDPC codes with optimized performance-complexity tradeoff[J].IEEETrans.onCommunications,2010,58(2):489-499.

[11] Dohyung P, Chung S Y. Performance complexity tradeoffs of rateless codes[C]∥Proc.oftheIEEEInternationalSympo-siumonInformationTheory, 2008: 2056-2060.

[12] Hussian I, Xiao M, Rasmussen L K. Reduced-complexity decoding of LT codes over noisy channels[C]∥Proc.oftheIEEEWirelessCommunicationandNetworkingConference, 2013: 3856-3860.

[13] Hussian I, Land I, Chan T H, et al. A new design framework for LT codes over noisy channels[C]∥Proc.oftheInternationalSymposiumonInformationTheory, 2014: 2162-2166.

[14] Ashikhmin A, Kramer G, Ten B S. Extrinsic information transfer functions: model and erasure channel properties[J].IEEETrans.onInformationTheory, 2004, 50(11): 2657-2673.

[15] Hussain I, Xiao M, Rasmussen L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference, 2011: 1-5.

[16] Ten B S, Kramer G. Design of repeat-accumulate codes for iterative detection and decoding[J].IEEETrans.onSignalProcessing, 2003, 51(11):2764-2772.

[17] Brannstrom F, Rasmussen L K, Grant A J. Convergence analysis and optimal scheduling for multiple concatenated codes[J].IEEETrans.onInformationTheory, 2005,51(9): 3354-3364.

[18] Boyd S, Vandenberghe L.Convexoptimization[M]. Cambridge university press, 2004：668-680.

[19] Venkiah A, Poulliat C, Declercq D. Jointly decoded raptor codes: analysis and design for the BIAWGN channel[J].EURASIPJournalonWirelessCommunicationsandNetworking, 2009,16(1): 1-11.

Optimized design for accumulate rateless codes with iterative decoding number constraint

LEI Wei-jia, CHEN Sheng-nan

(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

The rateless codes designed by the methods which aim to maximize the coding rate can usually approach capacity. However a large number of iterations (theoretically infinite) are needed in the process of iterative decoding to achieve the desired bit error rate performance. Based on the asymptotic convergence analysis of extrinsic information transfer charts, an optimization design method for the degree distributions of non-systematic accumulate rateless codes with a fixed number of decoding iterations is proposed and the mathematical model for optimization is formulated. The degree distributions satisfying the requirements can be obtained by solving the mathematical problem. Simulations show that, compared with the codes designed by the traditional maximizing coding rate method, for a given number of decoding iterations, the proposed design scheme can achieve better error correcting performance. What’s more, the less the number of iterations, the more obvious the advantage is.

accumulate rateless code; iterative decoding; extrinsic information transfer chart; iterative decoding number constraint

2015-08-10；

2016-01-16；网络优先出版日期：2016-03-04。

国家自然科学基金(61271259，61301123，61471076)；重庆市基础与前沿研究计划(cstc2015jcyjA40047)；长江学者和创新团队发展计划项目(IRT1299)；重庆市科委重点实验室专项项目资助课题

TN 919.3

A

10.3969/j.issn.1001-506X.2016.08.32

雷维嘉(1969-),男,教授,博士,主要研究方向为无线和移动通信技术。

E-mail: leiwj@cqupt.edu.cn

陈胜男(1993-),女,硕士研究生,主要研究方向为无率码编码。

E-mail: csn_cqupt@163.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160304.1300.002.html