一种基于QC-LDPC码的低复杂度分层迭代译码器*

2015-03-25云飞龙朱宏鹏

通信技术 2015年11期

关键词：译码器译码校验

云飞龙，朱宏鹏，吕晶，杜锋

(中国人民解放军理工大学，江苏南京 210001)

一种基于QC-LDPC码的低复杂度分层迭代译码器*

云飞龙，朱宏鹏，吕晶，杜锋

(中国人民解放军理工大学，江苏南京 210001)

针对具有准循环结构的LDPC码，设计了一种低复杂度译码器。利用校验矩阵的循环特性以及分层迭代的译码算法，对一般的分层迭代架构进行改进，实现了译码器流水线处理，有效的减少迭代时间，提高吞吐量，最后针对码长为1200的LDPC码，基于FPGA平台Kintex7 xc7k325的芯片实现了该架构设计，结果表明，该译码器只消耗了100多个Slices和几块RAM，有效节省了硬件资源，同时译码时间比一般的分层架构减少了2/3左右，吞吐量提高了约2倍，研究成果具有重要的实用价值，可应用于资源有限的低速通信领域。

QC-LDPC;分层迭代;低复杂度;流水线

0 引言

LDPC码(Low-Density Parity-Check Code)[1]是一类具有稀疏校验矩阵的线性分组码，不仅有逼近Shannon极限的良好性能，而且译码复杂度低、结构灵活、易于在FPGA上实现等特点，成为近年信道编码领域的研究热点，已广泛用于深空通信、光纤通信、卫星数字视频广播和音频广播等领域。QC-LDPC码[2-3]更是由于其校验矩阵拥有准循环结构特点，目前已被多个通信标准采用，如IEEE 802.16e、DVB-S2和802.11等。

目前在导航定位领域，往往传输的只是位置信息，速率比较低，而手持化的终端设备又要求硬件资源消耗少。针对这种领域低资源消耗、低速的特点，文献[4]提出了一种低存储量和简化译码器控制逻辑的低复杂度译码器架构，该架构采用分层思想，将每个校验节点输出的变量节点软信息进行累加，最后将累加值更新变量节点存储器，该方法省去了变量节点处理单元，降低了复杂度，虽然文献中针对的是PEG[5]算法构造的非QC-LDPC码，但对于QC-LDPC码,采用该架构同样适用，然而该架构在译码过程中需要一个n维的累加器，n为码长，随着码长增加，资源会增加。文献[6]介绍了一种经典的分层迭代架构，该架构复杂度低，但时延相对来说比较长，导致吞吐量比较低。针对上述问题，本文设计了一种改进的分层迭代译码架构，可省去n维的累加器，有效降低复杂度，同时将该架构应用到QC-LDPC码中，实现流水线译码，有效的减少了译码时间，提高吞吐量，最后完成了FPGA设计实现。

1 准循环LDPC码译码算法

1.1 准循环LDPC码

准循环LDPC码(QC-LDPC)的校验矩阵具有双对角结构[7]。该类LDPC码的校验矩阵便于存储，且具有线性复杂度的快速编码算法。给定两个常数c和t，且c≤t，准循环LDPC码的奇偶校验矩阵由c×t的大小均为z×z的循环矩阵阵列组成，校验矩阵一般形式为：

(1)

式中，P是z×z的单位循环移位矩阵或者0矩阵。

定义mb×nb的基础矩阵Hb，c=mb×z，t=nb×z,矩阵形式如下式所示，其中，sij为-1～(z-1)之间的整数，称为循环移位因子。

(2)

校验矩阵H可由mb×nb的基础矩阵Hb扩展得到。基础矩阵中对应的元素值为-1时，将其扩展为z×z的0矩阵，若为其它值s，则将其扩展为z×z的单位阵循环右移s次。

1.2 译码算法

采用的算法是修正的最小和译码算法[8]，它是由BP算法[9]演化而来，由于最小和算法易于硬件实现，因此被广泛采用，算法如下：

(2)校验节点更新：更新校验节点Cm向变量节点Vn，n∈B(m)传输的信息，B(m)表示与校验节点Cm相连接的变量节点集合；

(3)

(4)

(5)

式(5)中，m′∈A(n)m表示集合不包括m本身；

(4)一般在硬件实现中，设置最大迭代次数，当一次迭代完成后，若k小于最大迭代次数，则k=k+1，返回第2歩，否则，终止迭代，译码输出。

1.3 分层迭代

假设一个矩阵如下：

(6)

矩阵中，一个行块对应一个校验节点处理模块(CNU)，一个列块对应一个变量节点处理模块(VNU)。通常译码过程是行列结合的过程，只有校验节点全部更新完后，才进行变量节点更新。而在分层迭代架构中，并没有涉及到VNU模块计算，同时CNU模块只有一个，每一行通过这个CNU模块进行更新迭代，该过程如下：先取出矩阵(6)第0行对应的6个变量节点的值a1,a2,a3,a4 ,a5,a6,并串行送入CNU模块进行处理，处理完后得到6个新的变量节点的值a′1,a′2,a′3,a′4,a′5,a′6,并将原来的值覆盖更新，处理下一行时，从已经被更新过的数据中，读取下一行对应变量节点的值，重复上面过程，直到迭代终止。该过程对应的算法如下，同时总结了文献[4]中的算法，并进行了比较。

分层译码算法如下：

4、一个校验节点运算完后(即一行处理完)，更新对应的似然值，然后返回第2歩，处理下一个校验节点：

5、一次迭代完成后(即所有行处理完)，若k小于最大迭代次数，则k=k+1，返回第2歩，开始下一次迭代，否则，终止迭代，译码输出。

文献[4]中的译码算法如下：

若k小于最大迭代次数，则k=k+1，返回第2歩，开始下一次迭代，否则，终止迭代，译码输出。

图1 2种译码架构的不同

针对上述情况，本文进行了改进。由于QC-LDPC码，一个循环子矩阵内的变量节点度为1，而分层迭代算法的核心是：下一行需要利用最近更新的变量节点来进行译码。也就是说当译码的两行没有重叠的变量节点时，两行校验节点关系是互不相干的，可独立进行，因此一个循环子矩阵内的变量节点可流水线处理，而不用等上一行完全更新完后才进行下一行处理，可有效节省译码时间，只有当校验矩阵相邻2行对应列都有循环移位因子时，由于变量节点的不确定性，可能当前需要更新的变量节点，由于之前还未更新完，需进入等待状态。

为此，可对校验矩阵做变换，通常译码时，CNU模块从矩阵的第一行开始，依次往下译码，事实上，CNU模块可从任意行开始迭代，也就是说矩阵的行可任意交换，而不会影响译码性能。于是可将对应列都有循环移位因子的相邻2行隔开，打乱校验矩阵行的次序，当某些行无法隔开时，则同一列的循环移位因子需满足一定的条件。

图2表示的是校验矩阵相邻2行同一列都有循环移位因子的条件下，不同子矩阵间的切换示意图。其中N(N≠0的情况)为矩阵上一行的循环移位因子,M为下一行循环移位因子，假设数据n从读取到更新消耗了k个时钟，期间总共读取了p个数据，z为子矩阵的阶数，由于p比较小，一般p

图2 2个子矩阵切换示意

图2中，M、N、z可直接从校验矩阵中看出，p和FPGA时钟设计有关，一般是固定值，在下文FPGA实现中，p设为3，而n不容易看出，比较复杂，于是下面推导出了的和n无关的结论。

①当N≠0，mod(n+p-1,z)=N-1

若0≤n≤N-1

⟹n+p-1=N-1，n=N-p

⟹0≤N-p≤N-1

若N≤n≤z-1

⟹n+p-1-z=N-1，n=N+z-p

⟹N≤N+z-p≤z-1

②当N=0时，n+p-1=z-1

⟹n=z-p

2 译码器的FPGA实现

译码器的结构框图如图3所示，主要由3个模块组成：地址产生模块、数据存储模块、CNU数据处理模块。其中数据存储模块主要是存储信道似然比信息L值以及产生的中间结果r值，每一行数据处理后，似然比信息被更新，而中间结果需要保存下来，只有当下一次迭代的时候，中间结果才可以被更新。

图3 译码器结构

图3中地址产生模块，用来读取和更新存储器中的数据，为了实现流水线操作，地址产生模块将连续的产生新地址进行读取。其中对L值的读取，采用段首地址与偏移量结合的方法来实现。假设码长为576，按上述矩阵(6)计算，将576的码字分成24段，段首地址就是每段的第一个数据地址，如第一段数据地址是0～23，则段首地址为0，第2段为24～47，则段首地址为24。矩阵(6)中有76个循环移位因子，将它们存入到ROM中，同时每个循环移位因子对应的段首地址也存入到ROM中。

对L值存储器的地址addr_L读取公式如下：

addr_L=mod(addr_first+s+k,24)

(7)

式(7)中，addr_first为段首地址，s为对应的循环移位因子，k为每段读取个数的序号，如读取第1个数，则k为0；读取第2个数，则k为1。

由于对段首地址与循环移位因子的读取操作是完全一样的，因此为了降低资源，将2个值存储到同一块ROM中。假设段首地址位宽为10，循环移位因子位宽为5，则ROM的数据位宽应为15位，高10位存段首地址，低5位存循环移位因子。

同时由于对L值存储器以及r值存储器读和写的地址是一样的，因此在设计时，对读地址进行简单的延迟操作即得到写地址，有效降低了复杂度。

CNU模块主要包括对数据的相减、比较以及相加，如图4所示。

图4 CNU模块

从图4中可看出，CNU模块对数据的处理是流水线操作，串行输入6个L值和r值，处理完成后，同样串行输出6个新的L值与r值。其中比较关键的部分是比较器，要比较出最小值和次小值以及它们所在的位置，图4中比较器采用单一端口输入，串行比较，输出最小和次小值，再与符号位结合，串行输出对应的最小真值。

同时本译码器可接收不连续的数据。如果一帧数据传输的时候，遇到中断事件，要先去处理其他优先级事件，译码器则进入等待状态，只有等一帧数据接收完成后才开始译码。

3 仿真结果及资源消耗情况

3.1 性能分析

在实际设计中，采用了12x24的校验矩阵(并非上述矩阵(6))，码长为1 200的LDPC码，图5给出了经过BPSK调制后的误码率性能，采用分层译码算法，利用软件仿真，迭代次数为20次，6 bit量化．

图5 性能仿真

从图5中可看出，在2.3 dB条件下，误码率就达到了10-6级别，完全可以满足实际中的应用。

3.2 资源消耗

针对码长为1 200的LDPC码，分别对改进前后的架构进行了FPGA的实现，FPGA采用Kintex7系列xc7k325t芯片，设计实现后分别测试了100帧数据(信噪比为2.3 dB)，均无错，最后经过ISE软件环境下的布局布线后，资源消耗情况如表1所示。

表1 资源消耗情况

吞吐量的计算公式如下：

(8)

式(8)中，fmax是处理模块能达到的最高工作主频，nLDPC是LDPC编码帧包含的信息比特数，C是译码器迭代一次的主时钟周期数，Iter是迭代次数。

从表1中可看出，改进后时钟周期为改进前的1/3左右,有效降低了译码周期，同时吞吐量也提高了2倍左右，而资源相差不大。

4 结语

本文针对QC-LDPC码设计了一种改进的低复杂度分层迭代译码器，该架构可实现流水线操作，有效的降低了译码周期，提高了吞吐量，且适用范围广，具有准循环结构的LDPC码几乎都适用。同时针对码长为1 200的LDPC码进行了FPGA实现，最后表明只消耗了100多个Slices和几块RAM，同时也看到，虽然对传统的分层迭代架构进行了改进，但由于其本身译码时间长的特性，导致吞吐量比较低，因此需应用于低速、低资源消耗的领域。

[1] Gallager R G. Low-Density Parity-Check Codes[J]. Information Theory, IRE Transactions on,1962,8(1):21-28.

[2] CHEN L, XU J, Djurdjevic I, et al. Near-Shannon-Limit Quasi-Cyclic Low-Density Parity-Check Codes[J]. Communications, IEEE Transactions on, 2004, 52(7): 1038-1042.

[3] Fossorier M P C. Quasi-Cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices[J]. Information Theory, IEEE Transactions on. 2004, 50(8):1788-1793.

[4] 王建辉,李井源,倪少杰等.GPS L1C 信号LDPC译码器设计[J] .国防科技大学学报,2013(01):014. WANG Jian-hui ,LI Jing-yuan, Ni Shao-jie, et al. Design of LDPC Decoder on GPS L1C Signal[J].Journal of National University of Defense Technology.2013.1:014.

[5] 胡应鹏,王健,程雯.LDPC短码的编译码研究[J].通信技术,2013,45(09):25-28. HU Ying-peng, WANG Jian, CHEN Wen. Modified Coding/Decoding Algorithm for Short LDPC Code[J].Communications Technology,2013, 45(09):25-28.

[6] Kim S, Sobelman G E, Lee H. A Reduced -Complexity Architecture for LDPC Layered Decoding Schemes[J],Very Large Scale Integration (VLSI) Systems. IEEE Transactions on, 2011 19(6): 1099-1103.

[7] Tanner R M, Sridhara D, et al. LDPC Block and Convolutional Codes based on Circulant Matrices[J] . Information Theory, IEEE Transactions on, 2004, 50(12):2966-2984.

[8] 姜明.低密度奇偶校验码译码算法及其应用研究[D]. 南京: 东南大学, 2006. JIANG Ming. Decoding Algorithm and Applied Research of Low-Density Parity-Check Code[D] . Nanjing: Southeast University, 2006.(in China)

[9] CHEN J, Dholakia A, Eleftheriou E, et al .Reduced-cComplexity Decoding of LDPC Codes[J].Communications, IEEE Transactions on,2005,53(8):1288-1299.

A Low-Complexity Layer-Iterative Decoder based QC-LDPC

YUN Fei-long1，ZHU Hong-peng2，LV Jing3， DU Feng4

(PLA University of Science and Technology, Nanjing Jiangsu 210001, China)

In light of LDPC with quasi-cyclic structure, a low-complexity decoder is designed. Circulation of check matrix and layer-iterative decoding algorithm are applied to improving the common layer-iterative architecture,and thus achieving pipeline processing of decoder, and this could effectively reduce the iteration time and increases the throughput. Finally, based on FPGA platform of Kintex7 xc7k325 for LDPC with code length of 1200,the architecture design is realized. Results show that this decoder merely consumes over 100 Slice and several RAMs, thus effectively saving the hardware resource. In addition, the decoding time is only one third of that of the common architecture, while the throughput increases almost two times. The research is of important practical value, and the result could be applied to the low-speed communication field with limited resources.

QC-LDPC; layer-iterative; low-complexity; pipeline

10.3969/j.issn.1002-0802.2015.11.005

2015-06-10；

2015-09-23 Received date:2015-06-10；Revised date：2015-09-23

TN911.22

1002-0802(2015)11-1228-06