算法分析
LDPC码的高效译码算法研究
李丹
(沈阳市图林科学研究院辽宁沈阳110016)
热事热十与写真网
摘要：LDPC码印低密度奇债校验础LowDensityParityCheckCode，LDPC,它是一类具有需疏校验矩降的线性分组码，不仅有通近Shannon 限的良好性能，而且译码复杂度较低，结构灵活，是近年信道端码领域的研究热点，目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广矫等领域。Mackay一Neal算法是基于LDPC码的BP译码简化算法，但仍存在大量乘法运算。为了降低锋码算法的运算量，基于Mackay一Neal算法提出一种改进的对数和积译码算法。最后通过计算量复杂度分析结累表明，政进后的对数和积译码算法更简单，运算量大大降低，易于硬件的实现。
关键词：LDPC码端码BP译码对数和积译码
中图分类号：TN911.2 1、简介
文献标识码：A
文章编号：1007-9416(2012)05-0106-01
其中，-4E,/N，道可靠性因子，初始化情况下o，-",O-，令：
LDPC码是一种基于稀疏校验矩阵的线性分组码，由Gallager 于1962年提出的一类可以用非常稀蔬的奇偶校验矩阵或Tanner 图定义的线性分组纠错码。极长的LDPC码在BPSK调制下已经逼近了假性高斯噪声信道下的香农限，因而被认为是Turbo码的有效替代技术，很有可能被用于下一代移动通信，深空通信和数据存储等应用领域。
目前LDPC码的译码方法主要是基于税率的置信传播(Belief Propagation)送代译码算法，简称BP算法也称和积算法。BP算法实现复杂度高，故Mackay和Neal提出了简化的和积算法，称为 Mackay一Neal算法，简化了和积算法中的校验节点和变量节点的处理，然而在送代的过程中仍有大量的乘法运算，由于在硬件实现过程中，乘法运算非常占用硬件资源，加大了硬件实现的复杂度。
本文提出在Mackay一Neal算法的基础上，推导出改进的对数和积算法，将乘除法运算转化为加法运算，从而大大的降低了计算
量，但会增加一些辅助的运算。 2、和积算法
译码信息在多个符号节点和校验节点之间来回传递，符号节点向校验节点传递的信息记为Q，校验节点向符节点传递的信息则记为R，每一次送代中，x节点将Qi作为其置信度传递给和它相连的z节点。Qü表示除节点Zi之外，所有与Xj关联的其他校验节点在所对应校验方程组约束条件下，节点Xj处于状态a的概率。校验节点Zi被激活后，把Rü作为其置信度传递给和它相连的x节点。Ri表示在Xj=a的条件下满足校验方程Zi(该方程与Xj关联，即因子图中Xij与Zi相连接)的概率。在每次送代中，所有节点的可信度都将得到更新。每一次送代结束后，对X1,X2，·...Xn进行
...，，Xn的伪后验概率做尝试判决，
假设译码，计算X1,X2，
得到判决序列x^。指导判决序列x^满足AxA=0,或送代次数达到预设的最大值。
3、和积译码算法的简化
和积译码算法性能优异，但在校验节点的更新步骤中很繁项，对于给定的码字v,P(sj|v)当sj=0时取值为1,当sj≠0时取值为 0即在计算R0，时，在v=0的情况下，与s相邻的变量节点中应有偶数个1，而在计算R1j,时，在vl=1的情况下与$相邻的变量节点中应有奇数个1。为了简化校验节点更新的计算，在基于和积译码算法的基础Mackay和Neal提出了Mackay一Neal算法。为了介绍这个算法，首先引入一个定理1：
设u，V是两个随机变量，概率分布记为f，和，与，则
=(u+V)mod2的概率分布，J满足：
对于AWGV信号，初始概率也可由公式（1）确定：
J" J = (r'fbU Jx1) 1+eJ=1-
fe 106
80,u =Q/, O,, R, R, R, 则由宽理可推出：8R，-1180, 由于R,+R，=1，因此：
R(+8R,AR,(8R,K2)
最后计算码字比特取整位0和的概率p的公式修正为：P=α
其中α,可樱据xp"-1确定，即将p;归一化。在对码字比特缴出告计，校登，H"是否为0，如果为0或者已经达到最大选代译码次数则输出码字，选代运算停止，如果不为0，则继续选代，直到符合译码输出条件为止
4、对数和积译码算法
Mackay一Neal算法虽简化了和积算法中校验节点和初始化的处理，然而在送代的过程中仍然有大量的乘除运算，固此在Mackay 一Neal算法算法的基础上，基于将乘法运算转化为加法运算的思想，运用LOG算术符号的特性，提出了对数和积算法，从而小计算量，但会增加一些辅助的运算。加法运算更易在硬件中实现，大大降低了硬件实现的复杂度和成本问题，还可能提高硬件的整体性能。首先给出算法推导中用到的几个表达式：
(=== 定义三个函数
max (x, y) 1n(e*+e*)=ax (x, y)+1n(1+e+-l) (4)
nin(x, y)=n|e- e|= min(|x-| +|n(1e--Ml)(5)(9)(s31)[=(x)/(r-2 +[) = (r)
5、结语
在实际硬件实现中，乘法运算非常占用硬件资源，乘法运算量过大会加大硬件实现的复杂度，最终会影响系统的整体性能。以上研究表明，对数和积算法相比和积算法以及Mackay一Neal算法，虽然加法运算较多，但省去了乘法运算，于加法运算更易在硬件中实现，因此降低了硬件实现的复杂度，还能提高硬件的整体性能。参考文献
[1JShu Lin,Danie1 J. Costello . Error Control Coding Second Edition[M]. China Machine Press,2007:561 625
[2JD. J. C. MacKay.R. M. Neal. Near Shannon 1limit per-formance oflimit performance of low _ density parity_ check codes[J].IETElectronics Letters _Aug.1996 . Ov1.32(6):457 458[3]肖勇.基于分组混合策略的LDPC置信传据播译码算法[J].重庆邮电大学学报,2010,22(2):192-195
[4]李风飞,郝学飞.胡国荣.一种多效的多码率LDPC译码器的设计[J].微电子学与计算机,2011,28(2):23-27.