无短环不规则QC_LDPC码的快速编码及联合译码

刘蕾等

摘 要： 基于不规则部分并行结构设计了一种高吞吐量，低复杂度，码长码率可变且去除四环的低密度奇偶校验LDPC码及其译码结构实现方案，该编码结构可针对不同码长的不规则部分并行结构LDPC码进行扩展，译码器采用缩放最小和定点（Sum?Min）算法实现译码，中间信息节点存储器地址采用格雷码编码，降低动态功耗；采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片设计了一款码长1 270，码率[12]的不规则部分并行LDPC码的编码器和译码器。综合结果表明：该编码器信息吞吐量为2.52 Gb/s，译码器在10次迭代的情况下信息吞吐率达到44 Mb/s。

关键词： 低密度奇偶校验码； 不规则码； 部分并行结构； FPGA

中图分类号： TN911.22?34 文献标识码： A 文章编号： 1004?373X（2015）17?0034?04

Fast coding and joint decoding of irregular QC_LDPC codes without short?cycle

LIU Lei1， SUN Shulong1， CHANG Liang2， LI Huawang2

（1. Shanghai Institute of Microsystem and Information Technology， Chinese Academy of Sciences， Shanghai 200050， China；

2. Shanghai Engineering Center for Microsatellites， Shanghai 200120， China）

Abstract： The low density parity check （LDPC） codes and the implementation scheme of the decoding structure were designed based on irregular semi?parallel structure. LDPC codes without four cycles have high throughput and low complexity， whose length and rate are variable. This coding structure can extend irregular semi?parallel LDPC codes with different code length. The decoder adopts Sum?Min algorithm to realize decoding. The memory address of middle information nodes applies Gray coding to reduce dynamic power consumption. Based on this structure， encoder and decoder of irregular semi?parallel LDPC codes were designed by using Xilinx Virtex?5 XC5VtX150T?ff1156 FPGA， whose code length is 1 270 bit and code rate is [12.] The comprehensive results show that the information throughput of this encoder can achieve 2.52 Gb/s and the information throughput rate of the decoder can reach 44 Mb/s in the case of 10 iterations.

Keywords： LDPC code； irregular code； semi?parallel structure； FPGA

0 引 言

低密度奇偶校验码（Low Desity Parity Check，LDPC）又被称为Gallager码，是Gallager在1960年提出的，LDPC码在AWGN信道下具有非常好的性能，目前最好的仿真结果表明，随机LDPC码在AWGN白噪声下距离Shannon限仅0.004 5 dB。LDPC码是一类逼近Shannon限的随机码，其译码复杂度低，信息吞吐量大，灵活性高，可以避免Turbo码类似的错误平层，且完全可并行实现，更适合高速的无线数据业务。LDPC面临的最主要问题是它的编码复杂度高，是码长的O（[N2]），而Turbo码的编码复杂度与码长线性相关。现在结构化准循环LDPC码是编码结构的研究热点，可以在译码性能保持的前提下，用来简化编码器的复杂度， 已经被业内广泛采用，目前，由于结构化LDPC码性能优越，已经被IEEE 802.16e，IEEE 802.11n，IEEE 802.3an和DVB?S.2等标准采用，并被广泛应用于卫星通信，深空通信，光通信和下一代移动通信系统中。

为了在工程实践中降低编译码器的复杂度，研究人员系统地研究了结构化LDPC码的硬件实现技术，发现了一些制约LDPC码的编码器和译码器高速实现的因素，具体包括：编码器如果直接由生成截止实现，工程复杂度过高；全并行译码器结构实现时内部联系过多，运算单元过于复杂；对于串行结构，LDPC码的高速并行特点很难发挥。

针对以上问题，本文提出了一种高吞吐量，低复杂度并且码速、码率可扩展的非奇异子矩阵的不规则部分并行编码、译码结构，构造了性能优良、结构合理的部分并行译码实现的结构化LDPC码校验矩阵，并采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156 FPGA芯片设计了一款码长1 270，码率[12]的不规则部分并行LDPC码的编码器和译码器，实验结果表明，该编码器可以实现数据吞吐率2.51 Gb/s，译码器在采用10次迭代的情况下，信息吞吐量达到44 Mb/s。

1 不规则QC码快速编码

文献[1]指出，规则QC码的校验矩阵是奇异的，如果将校验矩阵分成两个子矩阵即[H=[Ha Hb]，]则无法得到奇异的子矩阵[Ha或Hb，]参考802.16e中的LDPC码的设计，可以获得快速编码的不规则QC编码的LDPC校验矩阵的子矩阵。

结构化LDPC码的奇偶校验矩阵[H]是[M×N]维的矩阵，由[mb×nb]的标准循环移位矩阵构成，其中[M=mb×z，][N=nb×z，][H]矩阵的形式如式（1）：

[H=[HaHb]=I1Ia…Iak-1Ix1I0…0IbIab…Iak-1b0II…0Ib2Iab2…Iak-1b2Ix20II…?????????Ibk-1Iabk-1…Iak-1bk-1Ix300…I] （1）

快速编码算法，令信息比特[S=[s1s2s3…sk]，]结构化LDPC码根据结果可以分为信息序列和校验序列，由信息序列[S]可以得到校验序列[Vm×1，]其中[si，][i≤k]是一个[Z]维的列向量，编码后的输出[C=[SV]；]根据校验方程，[HaSΤ+HbVΤ=0]。[Ix1+Ix2+Ix3?VT1=i=1kj=1kHi，jSTj，]设中间变量[T（i）=i=1kHi，j?STj，]根据[Vi]计算[Vi+1，][Vi+1=Vi+T（i），i

2 LDPC译码算法选择

LDPC码译码算法分为基于置信传播的BP算法以及在此基础上衍生出的LLR BP算法，另一类译码算法基于比特翻转（BF）算法，由于比特翻转过程损失了信道软信息，译码性能较差，BP算法涉及大量非线性运算，复杂度较高。本文采用一种改进的基于BP原理的归一化最小和积算法实现LDPC的译码，即Normalized MSA。算法描述如下：

（1） 初始化。将变量节点传向校验节点的信息初始化概率为：

[L0Qij=2yiσ2] （2）

式中：[yi]为接收到的信号；[σ2]为噪声方差。

（2） 校验节点更新。在第[i]次迭代时，更新与校验节点[j]相邻的变量节点[i∈Rj]传给校验节点的信息。

[LlRji=i∈Rjisgn（Ll-1（Qij））?minQijα] （3）

式中：[Rji]为除了变量节点[i]外所有与校验节点[j]相邻的变量节点的集合。

（3） 变量节点更新。在第[i]次迭代时，更新与变量节点[i]相邻的校验节点传给变量节点的信息：

[Ll（Qij）=L0Qij+j∈CijLlRji] （4）

式中：[Cij]为除了校验节点[j]外所有与变量节点[i]相邻的校验节点的集合。

（4） 译码判决。

[Ll（Qij）=L0Qij+j∈CijLlRji] （5）

则：

[Ci=0，if LlQij>01，else] （6）

（5） 结束。增加迭代次数，把译码结果代入[HΤ?C=0]进行校验，如果等式成立或已经超过最大迭代次数，输出译码结果，否则返回步骤（2）。

3 LDPC码编码器实现

针对上文提出的编译码算法，选择[H]矩阵中对应的系数[a=2，][b=5，][z=127，][x1=x2=x3=0，]得到快速编码的不规则QC码，采用文献[2]提出的四环检测定理，首先从图1观察[O=HΤH]矩阵，除主对角线元素以外的其他元素都不大于1，所以校验矩阵不存在四环。

结构化矩阵采用[m]路准并行编码结构，硬件编码器按照快速编码算法计算序列的[V=Vim×1，]信息序列分成[k]组，每组[z=127 ]b，输入到编码信息存储器EM中，根据[Ha]移位矩阵将信息循环移位中间变量存储在EM中，首先对每组移位块完全异或，[m]组中间序列再经过异或阵列得到校验序列[V1，]采用流水线同时进行，编码器通过循环移位寄存器完成，如图2所示。流水线设计极大地提高了编码器的信息吞吐率。

对于不同编码长度和编码速率，通过改变[z]值和移位规则，利用以上LDPC编码器架构就可以得到不同码长，码率以及不同并行度的LDPC码的编码，而且可以通过打孔自适应地实现不同码率，因此，以上结构LDPC码具有很好的灵活性。

4 译码器结构设计

本文设计的LDPC译码器总体结构如图3所示。

变量节点处理模块完成变量节点信息更新和译码输出判决，接收的数据一方面来自初始信道似然信息，另一方面是校验节点传递给变量节点的迭代信息，本文变量节点采用10组并行处理，每组127 b，这样在127个时钟周期完成所有变量的软信息更新，每个变量节点的更新输出是所有与之相连的校验节点传递过来的迭代信息和初始信道似然信息的和，再减去其自身的内信息，去所有信息之后最高位作为判决输出。

检验节点处理模块主要是更新校验节点到变量节点的信息，也是在127个时钟周期内完成所有校验节点一轮更新，更新后的输出作为下次变量节点更新的外信息。

从译码算法中可以看出，存储器地址时刻在变换，由于数字电路的动态功耗正比于芯片信号变换频率，因此本译码器存储器地址采用格雷码编码，这样信号每个周期只会翻转一位，大大降低了系统的动态功耗。

5 仿真与实现

本文通过大量的仿真，在信噪比低的环境下，置信传播译码算法译码性能优于位比特翻转算法。在对信息吞吐率，译码性能综合要求高的场合，采用BP算法具有明显的优势，同时对比定点化BP方案和浮点BP算法，定点化BP算法以最小的性能损失换取芯片复杂度的大幅度降低，然后分析仿真定点化不同位格式，确定采用最小和积置信传播算法作为LDPC的译码方案，缩放最小和算法的定点化格式为（8[∶]3），即量化位宽为8 b，其中最高的1 b表示符号，2 b表示整数位，5 b表示小数位，并得到[α=1.25，]图4给出了在AWGN 信道下，采用BPSK调制，码长1 270，固定10次迭代，[12]码率条件下，置信传播算法、最小和算法定点、缩放最小和算法定点及其不同定点格式，以及位翻转算法的误码率性能曲线。由仿真结果可知，缩放最小和算法定点的性能已经非常接近置信传播算法浮点的性能。

图4 不同译码算法的误码率性能曲线

基于上述编码器和译码器的结构，通过硬件描述语言实现了码长1 270，码率[12]的不规则结构化LDPC编码译码电路。通过ISE 14.7进行综合，布局布线，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上实现，编码器最大时钟频率为332 MHz，编码器信息吞吐率达到2.52 Gb/s，译码器的时钟最大频率为78 MHz，译码器在10次迭代后的信息吞吐率达到44 Mb/s，这对于码长为1 270 b的LDPC译码器是很快的。

编码器采用127 b准并行结构，输入比特根据校验矩阵均等切割，每组划分127 b，切割5组，编码器中组合逻辑完全由移位和异或构成，BLOCK RAM用于对输入、输出缓存进行时序调节，在跨时钟域场合用来解决读/写时序的逻辑胶合，本文不仅从系统层面用户角度采用输入、输出FIFO解决时序问题，用户甚至可以直接改变编码器移位矩阵设置不同的码长、码率，具有很强的可扩展性。编码器综合报表如表1所示。

译码器同样采用输入、输出FIFO与外部用户进行交互，数据流同样以1 270 b为一帧，译码开始前首先按编码顺序将序列进行均等切割，每127 b为一组，译码开始时，信道根据输入比特初始化，初始化完成后译码状态机进入校验节点和变量节点软信息更新状态，直到变量节点判别后得出的译码序列满足校验方程或者迭代次数超过最大值，输出译码序列，完成本帧数据的译码，译码结果存入缓冲器，等待用户读取。译码器资源消耗如表2所示。

6 结 语

本文根据IEEE 802.16e中LDPC码的设计规则，提出了一种无短环、高速、部分并行、准循环，不规则LDPC编码器和译码器结构，码长1 270 b，码率[12，]该LDPC编码器采用移位和异或操作完成编码，同时采用流水线结构提高时钟频率，可以通过打孔和参数设置进行扩展，采用对数域缩放最小和定点算法对LDPC码进行译码，采用8 b量化，1 b符号位，2 b整数位，5 b小数位，缩放系数[α=1.25，]中间信息节点存储器地址采用格雷码编码，降低动态功耗，通过硬件描述语言设计相应的编码、译码电路，用ISE 14.7进行综合，布局布线，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上实现，编码器最大时钟频率为332 MHz，编码器信息吞吐率达到2.52 Gb/s，译码器的时钟最大频率为78 MHz，译码器在10次迭代后的信息吞吐率达到44 Mb/s，这对于码长1 270 b的LDPC译码器来说是很快的，针对信息吞吐率，译码性能要求高，可扩展性强，从与外部通信使用便利的角度出发，该编译码结构体现出明显的优势。

参考文献

[1] ZHANG L， HUANG Q， LIN S， et al. Quasi?cyclic LDPC codes： An algebraic construction， rank analysis， and codes on Latin squares [J]. IEEE Transactions on Communications， 2010， 58（11）： 3126?3139.

[2] 肖扬，徐丹.准循环LDPC好码设计[J].系统工程与电子技术，2009，31（5）：1011?1016.

[3] GALLAGER R G. Low?density parity?check codes [M]. Cambridge： MIT Press， 1963.

[4] 徐娟，姚如贵，李路，等.优化稀疏LU分解LDPC编码算法研究[J].西安电子科技大学学报，2015（2）：127?132.

[5] MA Kexiang， LIU Yi， HU Jianhua， et al. Low complexity decoding algorithm for LDPC codes and design of key circuits [J]. Journal of Xidian University， 2013， 40（6）： 6?12.

[6] FALSAFAIN H， ESMAEILI M. A new construction of structured binary regular LDPC codes based on steiner systems with parameter [J]. IEEE Transactions on Communications， 2012， 60（1）： 74?80.

[7] COSTELLO D J， FORNEY G D. Channel coding： the road to channel capacity [J]. Proceedings of the IEEE， 2007， 95（6）： 1150?1177.

[8] IEEE LAN/MAN Standards Committee. IEEE Standard 802.11n. Wireless LAN medium access control （MAC） and physical layer （PHY） specifications： Amendment 4： Enhancements for higher throughputs improvement [S]. New York： IEEE LAN/MAN Standards Committee， 2007.

[9] 袁瑞佳，白宝明，童胜.10 Gbps LDPC编码器的FPGA设计[J].电子与信息学报，2011，33（12）：2492?2497.

[10] 张洋，王秀敏，陈豪威.基于FPGA的低密度奇偶校验码编码器设计[J].浙江大学学报：工学版，2011，45（9）：1582?1586.

[11] CCSDS. CCSDS 131.1.1?0?2. Low density parity check codes for use in near?earth and deep space application [S]. Washington， DC： CCSDS， 2007.

[12] XIAO Y， KIM K. Good encodable irregular quasi?cycle LDPC codes [C]// 2008 11th IEEE Singapore International Conference on Communication Systems. Guangzhou： IEEE， 2008： 1291?1296.