改进的离散字母表迭代译码算法研究

　　摘要：为了优化LDPC迭代译码性能和降低算法复杂度，提出了一种改进的基于Gallager A算法的2 b离散字母表迭代译码算法。在每一轮迭代中，Tanner图上的校验节点与变量节点之间所传递的消息有1 b表示符号值，另1 b反映码字结构特性，其中变量节点更新规则是通过查表法来实现的。在二元对称信道下针对列重为3的规则LDPC码做了仿真实验，仿真结果表明该算法性能明显优于原算法，并且具有较低的复杂度。
　　关键词：LDPC； 迭代译码； 码字； 二元对称信道
　　中图分类号：TN91134文献标识码：A文章编号：1004373X(2012)04000403
　　
　　Research on improved discrete alphabet iterative decoding algorithm
　　GUO Junjun1, WU Daiwen2
　　(1. Department of Computer, Shaanxi Post & Telecommunication College, Xianyang 712000, China;
　　2. Department of Media Engineering, Weinan Teacher's University, Weinan 714000, China)
　　
　　Abstract： To optimize the performance of iterative decoding for LDPC code and reduce the complexity of algorithms, a novel 2bit discrete alphabet iterative decoding algorithm based on Gallager A algorithm is presented in this paper. In every iteration, messages transmitted between check nodes and variable nodes in Tanner graph has two bits: one denotes the value of message and another indicates the characteristic of codeword, in which the update rules for variable nodes are realized by the lookup map table (LUMT). A simulation experiment for 3leftregular LDPC codes on binary symmetric channel (BSC) was conducted. The simulation results show that the performance of the proposed algorithm with lower computational complexity is more significant than that of the original algorithm.
　　Keywords： LDPC; iterative decoding; codeword; BSC
　　
　　
　　收稿日期：20110910
　　基金项目：教育部特色专业建设点项目(TS11772)；陕西省教育科学“十一五”规划2010年立项课题（SGH10154)0引言
　　LDPC(LowDensity ParityCheck)码是Gallager在20世纪60年代首次提出的［1］，它和Turbo码都属于重要的现代纠错编码技术。由于LDPC码具有较好的距离特性和较低的译码复杂度，以及在AWGN信道上逼近信息论的理论极限：香农限［23］，因此，近年来引起国内外编码界广泛的关注［48］。
　　传统的基于消息传递的迭代译码算法包括Gallager A/B算法和置信传播(BP)译码算法，其本质上是消息或置信度沿着Tanner图的边在校验节点与信息节点之间不断更新，逐次逼近正确解。Gallager A/B算法复杂度低，执行速度快，但译码性能较差，而置信传播或和积译码算法译码性能好。但是，BP译码算法复杂度高，存在错误平层现象，这是因为BP译码算法是一种贝叶斯推理问题(BIP)的求解方法，每轮迭代中计算量大，且在有环的Tanner图上存在边缘概率重叠和干扰现象，故其解是次优的。上述这些译码算法都具有通用性和普遍性的特点，没有充分考虑实用码字的结构特性。
　　本文给出了一种基于Gallager A的改进的2 b量化消息译码算法，其中一个比特表示消息符号，另一比特表示量化阶。Tanner图中的变量节点和校验节点的消息更新规则考虑到了图模型的结构特征，其方法简单有效。仿真结果表明，改进后的译码算法性能明显优于原算法。
　　1Gallager A 译码算法
　　Richardson等人在文献［4］中提到Gallager A算法，在迭代译码过程中沿着Tanner边传递的消息来自离散的有限消息字母表M={-1,1},假定从BSC信道中接收(dc,dv)规则LDPC码的二元序列值{yi}i=0,1,2,…,N－1经BPSK调制（ri=1－2yi）后输入到译码器。Gallager A译码算法可以表示为Gad=f(ωc,ωv,R,p)。其中函数ωc(e1,e2,…,edc－1)指的是由校验节点到变量节点更新规则的映射。相应地,函数ωv(m0,m1,m2,…,mdv－1,r)是由变量节点到校验节点规则的映射。R和p分别表示调制后的接收向量和信道参数。每一轮译码结束后，采用如下判决规则：=－r,m1=m2=m3=－r
　　r,otherwise 对于（3,4）规则LDPC码而言，其译码规则可以采用查表法表示，校验节点和变量节点更新规则如图1所示。
　　图1Gad算法中校验节点和变量节点更新规则表图1中，e0=ωc(e1,e2,e3)，m0=ωv(m1,m2,r)。
　　2改进的离散字母表译码算法
　　2.1算法基本思想
　　Gallager A译码算法是基于大数原则进行判决的，纠错能力可以突破码字距离的限制。但对于Tanner图中存在特殊的环状子结构时，会导致译码失败，如图2(a)所示的6环子结构中，如果环上变量节点信息最初是错误的，而从环外进入的信息全部是正确的，经过若干轮迭代译码后，变量节点集V={v1,v2,v3}中判决结果依然保持原值，迭代译码陷入僵局［9］。
　　图2Tanner图模型上的译码结构子图为了进一步提高译码性能，在此基础上提出改进的算法。其基本思想在于：既然有害的Tanner图子结构中并不孕育着纠错信息，可以充分利用子图结构，借助外界进入的信息纠正错误，使其变量节点的值翻转。令M={-2,-1,1,2}，校验节点更新函数参照最小和译码算法实现。ωc(e1,e2,…,edc－1)=
　　∏dc－1j=1sign(mj)minj∈(1,2,…,dc－1)(mj)(1)变量节点更新是进入的信息和信道接收值r求和后量化映射到M空间。ωv(m0,m1,…,mdv－1,r)=ψ(∑dv－1j=1mj+r)(2)式（2）可以表示成如图3所示的映射规则表。
　　
　　图3改进的Gallager A译码算法中变量节点更新规则表采用本文提出的新颖的4阶译码算法，经一轮迭代后，环中变量节点集V的信息由-1翻转为1，从而有效地实现了译码。
　　2.2改进的两比特阶译码算法
　　根据算法分析结果，提出了4阶离散字母表译码算法，变量节点与校验节点之间传递的消息长度为2 b，其字母表可以表示为{11,10,00,01}。
　　输入：校验矩阵H和信道接收向量R
　　输出：估计码字
　　具体算法步骤如下：
　　（1） 初始化， ωv(m0,m1,…,mdv－1,R)=R。
　　（2） while HT≠0 .and. i　　(3) 由式(1)计算由校验节点到变量节点传入的信息值。
　　（4） 由查找映射表函数LuMT(m0,m1,R)或LuMT(m1,m0,R)在表2中得到返回值m0作为变量节点到校验节点传入的信息值。
　　（5） 计算变量节点软判决值=∑dvj=1mj+R。
　　（6） 输出判决结果=0,>0
　　1,<0
　　y,=0 。
　　（7） end while。
　　以上算法适用于BSC信道下，列重dv=3的规则LDPC码。采用该算法，可以译出Gallager A算法不能正确译码的特殊Tanner环结构，图1(b)表明了在两轮迭代译码后6环上的信息传递情形。
　　3实验结果与分析
　　为了便于比较分析，选择了码长为n=96,码率R=0.5的规则LDPC码［9］，分别采用Gallager A、改进的Gallager A和BP译码算法在Windows XP操作系统平台下进行仿真实验，三种算法的最大迭代次数I=100，如图4所示。
　　
　　
　　图4(96,48)规则LDPC码在BSC信道下性能仿真图由上图仿真结果可知，在信道转移概率P较大部分，Gallager A和本文提出的改进译码算法性能比较接近，而随着P的减小，改进的译码算法明显优于原算法。事实上，它们与BP译码算法的性能还有一定的差距。
　　4结语
　　本文所提出的两比特离散字母表迭代译码算法是对原有的Gallager A算法的改进，其仿真性能优于Gallager A算法。目前，该算法只针对在BSC下列重为3的规则LDPC码。因此，设计和实现在不同信道下的不规则LDPC码的离散字母表迭代译码规则是今后的研究方向。
　　参考文献
　　［1］GALLAGER R G. Lowdensity paritycheck codes \[J\]. IRE Trans. on Inf. Theory, 1962, 8 (1): 2128.
　　［2］MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes \[J\]. Electronics Letters, 1996, 32 (18): 16451646.
　　［3］WIBERG N. Codes and decoding on general graphs \[C\]// Proceedings of 1995 IEEE International Symposium on Information Theory. Sweden: IEEE, 1995: 468478.
　　［4］李广森,吴晓栋.LDPC码编译码原理及性能仿真［J］.通信技术，2006(Z1):8690.
　　［5］张谨,苏广川.LDPC比特翻转译码算法的分析与改进［J］.计算机应用,2006(7):17301731.
　　［6］刘向楠,赵洪林,张佳岩,等.一种改进的LDPC码译码算法研究［J］.科学技术与工程,2011(24):58175822.
　　［7］DECLERCQ D, DANJEAN L, LI E, et al. Finite alphabet iterative decoding (FAID) of the (155,64,20) Tanner code \[C\]// Processing of 6th Int. Symp. on Turbo Codes and Iterative Information. \[S.l.\]: ISTC, 2010: 1115.
　　［8］曹建林.LDPC的硬判决译码研究［J］.电子与封装,2006(12):3133.
　　［9］RICHARDSON T J, SHOKROLLAHI M A, URBANKE R L. Design of capacityapproaching irregular lowdensity paritycheck codes \[J\]. IEEE Trans. on Inf. Theory, 2001, 47 (2): 619637.
　　［10］MACKAY D J C. Encyclopedia of sparse graph codes \[EB/OL\]. \[20051201\].http://www.inference.phy.cam.ac.uk/mackay/codes/data.html.
　　作者简介: 郭军军男，1978年出生，陕西横山人，硕士研究生，讲师。主要从事信息安全、LDPC编码研究工作。
　　吴代文男，1979年出生，湖南衡阳人，硕士研究生，讲师。主要从事信息论、教育信息技术研究工作。