汪汉新，尹 超

(中南民族大学电子信息工程学院，武汉430074)

低密度奇偶校验码(LDPC)具有较大灵活性及较低的错误平层特性［1］，在码长较长时，其译码性能甚至超过了Turbo码，LDPC译码采用了线性复杂度的置信传播(BP)算法，能够实现并行译码以及具有译码错误可检测的特点，与目前3G移动通信中使用的Turbo码相比，LDPC码更易于硬件实现.然而短码长的LDPC码的Tanner图中往往会出现短环，使得变量节点之间的信息不再相互独立，导致BP算法的性能下降.针对此问题，本文提出了一种改进的译码算法，可以加快算法的收敛速度，降低运算量，减小译码延时，是一种兼顾性能与复杂度的折中译码算法.

1 LDPC码的译码

LDPC码的译码算法主要是基于双向图的消息传递算法(MPA)，其中最常用的是和积译码算法(SPA)，也称为置信传播(BP)算法［2］.

BP译码算法是基于Tanner结构的信息传递算法，其核心思想在于利用从信道中接收到的信息在变量节点和校验节点之间进行迭代运算，从而获得最大的编码增益.图 1为(10，2，4)LDPC码的Tanner图，每个变量节点只和校验节点直接相连，而每个校验节点也只和变量节点直接相连.

1.1 对数域LLR BP译码算法

LLR BP算法将BP算法转化到对数域，使大量的乘法运算变为加法运算，减少了运算量.LLR BP算法在每次的迭代过程中，所有校验节点从相邻的变量节点接收信息，将这一信息处理后反馈给相邻的变量节点，然后变量节点再对从校验节点反馈回来的信息进行处理，并再次将处理后的信息反馈给相邻的变量节点，最后根据变量节点的信息进行判决.

图1 (10，2，4)LDPC 码的 Tanner图Fig.1 Tanner graph for(10，2，4)LDPC

1.2 UMP BP-based 译码算法

虽然LLR BP算法性能优异，但是在校验节点的更新过程中存在有非线性函数的计算，硬件实现时，主要是采用查找表的方法来实现，对非线性函数的量化直接影响到查找表的精度及复杂度，从而会影响到译码的性能与硬件的复杂度［3］.为了平衡译码的性能与硬件实现的复杂度，人们提出了很多简化的BP译码算法，文献［3-5］提出的UMP BP-based算法(最小和算法)，对校验节点消息进行了简化处理，用比较运算代替了非线性运算，同时避免了各变量节点的初始化计算，大大降低了运算量.

2 改进的LDPC译码算法

UMP BP-based算法与LLR BP算法相比，其运算复杂度得到了降低，但是其抗干扰能力也有一定程度的降低［3，6］.文献［7］针对其性能的损失，在对校验节点信息处理时，分别通过乘性因子和加性因子进行修正，使UMP BP-based算法的抗干扰能力性能有所改善，但其主要是针对校验节点信息进行处理.本文改进的译码算法主要是针对变量节点的信息处理，即在BP-Based算法的基础上，对变量节点的处理通过偏移因子来校正变量节点信息的迭代更新，用于降低由短环引入的变量节点消息之间的相关性，从而改善译码性能.设 c=(c1，c2，…，cN)码字经过BPSK调制映射为传输序列x=(x1，x2，…，xn)送入到 AWGN信道传输，接收序列为 y=(y1，y2，…，yn).根据y译码得到译码序列为.改进的译码算法步骤为:

(1)初始化.对每一个变量节点i，设变量节点传向校验节点的初始消息:

(2)迭代处理.

a)校验节点处理.

b)变量节点处理.

c)译码判决.

对所有的变量节点消息进行硬判决，若L(Qi)＞0，则ci=0，否则=1.

(3)迭代停止准则.如果H=0或达到设定的最大迭代次数，则迭代结束，否则回到步骤(2).

上述算法中，Rj表示校验矩阵中第j行中包含的比特所形成的集合;Rji表示在Rj中除去第i个比特形成的集合;Ci表示校验矩阵中第i列所参与的校验矩阵形成的集合;Cji表示在Ci中除去第j个校验方程形成的集合;rji(b)表示在码字中第i个比特ci=b和码字中其它比特服从分布{qij'}j'≠j的情况下，第j个校验方程满足的条件概率;qij(b)表示除第j个校验节点之外其它校验节点提供外信息的情况下第i个信息节点ci=b的概率;χ为偏移因子.

3 仿真结果及分析

实验中均采用(1008，3，6)LDPC码，在BPSK调制，AWGN信道环境下进行仿真测试.

3.1 译码算法复杂度比较

采用不同译码算法进行仿真，表1给出了LLR BP算法、UMP BP-based算法以及本文改进BP算法译码迭代一次的运算量.由表1可知，改进的译码算法相比LLR BP算法，减少了复杂的乘法和除法运算量，运算量大大的降低.但与BP-based算法相比，运算量有所增加.

表1 不同译码算法运算量比较Tab.1 Computation for difference decoding algorithms

3.2 不同偏移因子的译码性能分析

在迭代5次，信噪比分别为 2.0dB、2.5 dB 及3.0 dB时，偏移因子χ取不同的值，仿真得到译码性能曲线，如图2所示.在改进的译码算法下，随着信噪比的增加，不同的偏移因子对误码率的影响也加大，而且在等信噪比时当χ的取值为0.7，得到的误码率最小，译码性能达到最佳.

图2 偏移因子的取值对BER性能的影响Fig.2 Effect of different factor for the BER performance

3.3 不同算法的译码性能分析

在最大迭代15次时，分别利用LLR BP算法、UMP BP-based算法以及本文中χ=0.7的改进算法进行译码得到的BER性能曲线，如图3所示.由图可知，3种译码算法在高信噪比时都可呈现出较低的误码率.LLR BP算法的误码率性能相对较好;BPBased算法由于对校验消息节点的处理进行了简化，从而造成性能上的损失，使得性能最差;而改进的译码算法通过变量消息节点处理时的加性校正，使得性能得到了一定的改善.

图3 LLR BP，BP-based和改进算法的性能比较Fig.3 Comparison of performance for different algorithms

3.4 不同算法的平均迭代次数分析

在最大迭代次数设为50次，LLR BP算法、BPBased算法、本文改进算法的误码率为10－7时的平均迭代次数，如图4所示(其中本文改进算法的χ取0.7).由图可知，改进的译码算法相比与BP-Based算法，平均迭代次数大大的降低，从而减小了译码的延时，且相比与LLR BP算法而言，平均迭代次数几乎相当，这表明改进的译码算法与运算复杂度较低的BP-Based算法相比，加快了译码的收敛速度.

图4 不同译码算法下的平均迭代次数Fig.4 Average iteration numbers of different decoding algorithms

4 结语

本文提出的改进LDPC的译码算法，一方面总的运算量比LLR BP算法低，减小了译码的复杂度;译码性能要比BP-Based算法好，提高了抗干扰能力;另一方面平均迭代次数低于BP-Based算法，降低了译码延时，加快了译码收敛速度;本文的改进译码算法具有一定的实用价值.

［1］Gallager G.Low density parity check codes［J］.IEEE Transaction on Information Theory，1962，8(3):208-220.

［2］MacKay C，Neal M.Near shannon limit performance of low density parity check codes［J］.IEEE Electronics Letters，1996，32(18):1645-1646.

［3］Fossorier M，Mihaljevic M ，Imai H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation［J］.IEEE Transaction on Communication，1999，47(5):673-680.

［4］Chen J，Fossorier M.Near optimum universal belief propagation based decoding of LDPC codes［J］.IEEE Transaction on Communication，2002，50(3):406-414.

［5］Zarkeshvari F ，Banihashemi A.On implementation of min-sum algorithm for decoding low-density parity-check(LDPC)codes［C］//IEEE.IEEE Globecom 2002.Ottawa:Carleton University，2002:1349-1353.

［6］Yazdani R ，Hemati S.Improving belief propagation on graphs with cycles ［J］.IEEE Communications Letters，2004，8(1):57-59.

［7］Chen J，Fossorier M.Density evolution for two improved BP-based decoding algorithms of LDPC codes［J］.IEEE Communication Letters，2002，6(5):208-210.