张佳岩，张士伟，吴 玮，张 弛，王 硕

(哈尔滨工业大学 通信技术研究所，黑龙江 哈尔滨 150001)

快速收敛的EG-LDPC译码算法设计实现

张佳岩，张士伟，吴 玮，张 弛，王 硕

(哈尔滨工业大学 通信技术研究所，黑龙江 哈尔滨 150001)

欧氏几何构造的LDPC码属于不可分层的LDPC码，无法采用TDMP算法译码结构，针对该问题设计实现了一种新型分层译码器。在Xilinx V5FPGA上实现了码长为1 023、码率为0.781 EG-LDPC码的译码器设计。仿真验证表明：理论上该方法与优化的规范化最小和译码算法相比，迭代次数减少一倍，存储资源消耗得到降低，而误码性能几乎相同。FPGA实现上，译码输出与MATLAB定点仿真给出的结果相同，误码性能由于量化和限幅处理与理论值相比约有0.3 dB的损失。在时钟频率为50 MHz串行处理各分层时，吞吐量为49.7 Mbit/s。

EG-LDPC；分层最小和译码；FPGA

低密度奇偶校验码(LDPC)是由Gallager在19世纪60年代提出的逼近香农限的信道编码[1]，但其并没有给出高性能LDPC码校验矩阵系统的构造方法。Shu Lin和Forssorier基于有限域欧氏几何理论首次提出了一种系统的构造高码率LDPC码的方法[2]，这类码具有不可分层、准循环形式的校验矩阵，编码简单且适用不同的传统译码算法。LDPC码在无线通信中应用广泛，在LTE中使用可保证系统性能[3]。

LDPC码译码算法的研究主要集中在提升误码性能，减少译码复杂度及加快收敛速度3个方面。文献[4]提出了一种低复杂度的BP译码算法，在迭代过程中只更新可靠度低的节点消息，省去高可靠度的节点消息的计算，从而来提高译码算法的收敛速度，但仍避免不了概率域BP算法中乘法运算及对数域BP中的双曲正切、反正切计算，收敛虽然较快但资源消耗大，不适合硬件实现。文献[5]提出了整数量化最小和译码算法，易于硬件实现，通过新增额外校验因子使误码性能提高，但在高信噪比下与连续译码存在差距。文献[6]首次提出把Turbo译码消息传递机制应用到LDPC译码中的TDMP算法，误码性能良好，收敛速度快，但不适用不可分层LDPC码。针对该问题，结合TDMP的消息传递机制与NMSA算法[7]提出了一种分层NMSA算法并对其进行FPGA实现。该算法误码性能较好，最大迭代5次即可，较文献[8]中迭代30次相比，能够有效减少译码延迟和资源消耗。

1 EG-LDPC校验矩阵的构造

本设计基于m=2，s=5的欧氏几何构造的校验矩阵。构造EG-LDPC码校验矩阵具体步骤如下：

步骤1：根据码长和码率等参数确定欧氏几何的参数m和s，计算GF(2ms)的本原元α及其子域GF(2s)本原元β。

步骤2：创建一个向量v，向量的元素为子域GF(2s)中的所有元素，v向量记录了EG(m,2s)中一条过原点的直线上的点。

步骤3：构造出EG(m,2s)欧氏空间中所有过原点的直线所对应的向量。

α·v,α2·v,…,αn·v(n=2ms/2s)

(1)

步骤4：取出任意一条过原点直线对应的向量αi·v，进行以下计算

x+αi·vx∈GF(2ms)

(2)

即可得到与直线αi·v平行的所有直线对应的向量。取不同的值计算结果可能出现重复，如果重复则去掉，不重复则保留。遍历步骤3中的所有向量，即可求出EG(m,2s)欧氏几何上所有直线对应的保存着直线上点的向量。

步骤5：计算EG(m,2s)欧氏几何上所有直线的关联向量L。创建一个向量，向量的大小与欧氏几何中点的数目相同，L的每个元素与GF(2ms)域上的元素一一对应，取出步骤4中的一个向量Γ，把L中与Γ中元素相对应的位置置1，其他位置置0，遍历步骤4中的所有向量，就构造出了EG(m,2s)欧氏几何中所有直线的关联向量。

步骤6：去掉所有过原点的直线的关联向量并去掉原点，就得到了EG-LDPC码的奇偶校验矩阵H。

对于m=2，校验矩阵H只有一个循体。当m大于2时，校验矩阵存在(2(m-1)s-1)/(2s-1)个循环体。取出校验矩阵H的一个行向量γ，对其进行2ms-2次循环移位，对所得向量纵向排列就得到了一个循环体。从校验矩阵H中去掉该循环体中的所有向量，在校验矩阵H余下的向量中再取出一个向量，进行同样的处理，直到处理完矩阵H的所有向量。然后对每个循环体进行横向排列就得到了基于有限域欧氏几何的QC-LDPC码的校验矩阵Hqc。通过以上步骤得到了EG-1 023 LDPC码的校验矩阵H。

2 改进的分层最小和译码算法

记R,q,r分别为变量节点后验概率对数似然比，校验节点到变量节点消息，变量节点到校验节点消息。yi,σ2分别为信道输入的采样值，信道中高斯白噪声的方差。采用BPSK的调制方式。l为迭代次数，k为第几层。校验矩阵的一行即为一个分层。对于高行重的EG-LDPC码，规范化系数一般取值较小[9-10]，大约为0.25。为了节省硬件资源减少开销，本设计中规范化系数α取0.5。

1)初始化

(3)

2)迭代过程

(4)

(5)

(6)

3)判决译码

在每次迭代结束时，根据对接收码字做出硬判决

(7)

如果HCT=0成立，终止迭代，否则进行下一次迭代，直到达到最大迭代次数。该算法以规范化最小和译码算法为基础，采用Turbo译码消息传递机制，使上层更新的信息及时得到利用，从而加快收敛速度。只需通过实时的加法运算即可更新变量节点，节省了存储资源，更利于硬件实现。

3 译码器结构设计、仿真及分析

3.1 校验节点处单元

图1 校验节点处理单元结构图

3.2 最小值计算模块

该模块输出32个CTV绝对值中的最小值、次小值和最小值编号[11]。该结构由比较器和连接单元构成，详见参考文献[11]。仿真结果如图2所示，输入data0～data31，data1为0是最小值，可以看到index为1，求出最小值min_1st为0，次小值min_2st也是0。计算结果存储到RAM中，绝对值量化为4 bit，共有1 023层，最小值和次小值消耗8 kbit的存储资源，Index用5 bit来表示，供需消耗5 kbit的存储资源。还需存储的符号，每层32个，需要消耗32 kbit。需要的存储单元共为45 kbit，存储资源的消耗相当小，而码长更长如(4 599， 4 227)的EG-LDPC码存储资源的消耗与本文中的(1 023， 781)的EG-LDPC码存储资源消耗是相同的。

图2 最小值计算模块结果(截图)

3.3 译码器工作过程

图3 译码器结构图

图4 译码输出结果(截图)

理论误码性能(α=0.5)与硬件实现的误码性能对比如图5所示。由于初始化信息与变量、校验节点信息量化的影响，硬件实现与理论大概有0.3 dB的误码性能损失。

图5 理论与硬件误码性能

对于(1 023，781)的EG-LDPC码，规范化系数取0.25时，此算法误码性能最优，在迭代5次时比概率域BP译码算法迭代50次时有0.2 dB的编码增益，比对数域BP算法约有0.3 dB的增益，比最小和译码算法(min-sum)约有2 dB的编码增益，如图6所示。所以该算法误码性能良好且具有较快的收敛速度，从而减小了硬件实现时的译码延迟。

图6 与其他译码算法误码性能对比图

4 小结

该译码器在平均迭代2～3次即可收敛，硬件实现时误码性能由于量化和计算过程中的限幅处理，与理论相比仅有0.3 dB的损失，资源消耗仅为45 kbit，译码延迟小，在串行情况50 MHz时钟下吞吐量达到49.7 Mbit/s，进行一定的并行处理吞吐量将更高。如果初始化信息和中间计算结果量化位数增多，可以选择修正因子为0.25，误码性能会得到进一步提高。

[1] 晏坚，何元智，潘亚汉，等.差错控制编码[M].北京：机械工业出版社，2007.

[2] KOU Yu， LIN Shu，FOSSORIER M P C. Low-density parity-check codes based on finite geometries： a rediscovery and new results[J]. IEEE Trans. Information Theory， 2001，47(7)：2711-2736.

[3] LAO L， LI L， ZHU M， et al. The improved Turbo-decoding Message-passing algorithm and corresponding decoder for LDPC based on LTE[C]//Proc. IEEE International Conference on Signal Processing， Communications and Computing (ICSPCC). [S.l.]：IEEE Press，2014： 890-894.

[4] 郭锐，刘济林.LDPC码的一种低复杂度BP译码算法[J].浙江大学学报：工学版，2008，42(3)：450-455.

[5] 马汇淼，马林华，张嵩，等.基于整数运算的LDPC码改进最小和译码算法[J].电视技术，2013，37(17)：197-199.

[6] MANSOUR M M，SHANBHANG N R. High throughput LDPC decoders[J]. IEEE Trans. Very Large Scale Integration Systems， 2003(11)：976-978.

[7] 杨知行，林之初，王军，等.准循环LDPC码的半并行译码器设计[J].电视技术，2006，30(2)：24-26.

[8] YAN Ying，DAN Bo，HUANG Shuangqu. A cost efficient LDPC decoder for DVB-S2[C]//Proc. IEEE 8th International Conference on ASIC. [S.l.]：IEEE Press，2009：1007-1010.

[9] CHEN Jinhu，MARC P C. Fossorier near optimum universal belief propagation based decoding of low-density parity check codes[J]. IEEE Trans. Communications， 2002，50(3)：406-414.

[10] 马汇淼，马林华，田雨. 基于改进的分层译码算法的QC-LDPC译码器设计[J].电子技术应用，2012，38(7)：51-53.

[11] WEY C-L， SHIEH Ming-Der，LIN Shin-Yo. Algorithms of finding the first two minimum values and their hardware implementation[J]. IEEE Trans. Circuits and Systems I： Regular Papers，2008，55(11)：3430 -3437.

张佳岩(1974— )，副教授，硕士生导师，主要研究方向为信道编解码、扩频、深空通信技术；

张士伟(1990— )，硕士生，主研信道编码技术；

吴 玮(1981— )，博士，讲师，主研无线自组网、LTE/LTE-A移动通信系统；

张 弛(1990— )，硕士生，主研扩频信号快速捕获、跟踪技术。

王 硕(1992— )，女，硕士生，主研跳频系统FPGA实现技术。

责任编辑：闫雯雯

Implementation of Efficient Convergence EG-LDPC Decoding Algorithm

ZHANG Jiayan, ZHANG Shiwei,WU Wei,ZHANG Chi,WANG Shuo

(CommunicationResearchCenter,HarbinInstituteofTechnology,Harbin150001,China)

For TDMP decoding structure is not applicable to LDPC code which is constructed based on finite field Euclidean geometry, a new layered decoder structure is proposed. The design can be able to decode the EG-1023 LDPC which code rate is 0.781 on Xilinx V5 FPGA. The simulation results show that on theory the speed of convergence is twice as quick as the optimal normalized min-sum algorithm and memory resources cost decreases, but the error performance does not change. When implemented on the FPGA, the error performance has a loss about 0.3 dB because of quantization and amplitude limiting. The throughput is 49.7 Mbit/s working on the 50 MHz clock.

EG-LPDC; layered min-sum algorithm; FPGA

国家自然科学基金项目(61201147)；国家科技重大专项项目(2012ZX03003011-004)

TN911

A

10.16280/j.videoe.2015.17.023

2015-04-06

【本文献信息】张佳岩，张士伟，吴玮，等.快速收敛的EG-LDPC译码算法设计实现[J].电视技术,2015，39(17).