一种兼容结构化与非结构化LDPC译码器及译码算法

摘要

本发明提供一种高效的LDPC译码器结构与数据冲突解决方案，译码器采用了通用的串行处理方式，但对LDPC译码算法与硬件架构都进行了特殊优化。经典的TDMP算法无法适用于非结构化的LDPC码，如DVB-S2和CMMB中的LDPC码。如果直接采用TDMP算法则会引发数据冲突，降低LDPC码性能。本发明针对TDMP算法进行了优化，使其能很好的适用于非结构化的LDPC码。传统上，外信息的读写都是一次一完成，需要大量的存储空间，本发明对此进行了优化，有效地降低了译码器所需的存储空间。在处理单元上，本发明也优化了外信息的恢复与前验信息和后验信息的更新操作。并且为了兼容结构化与非结构化LDPC码，本发明还优化了译码的主时序。通过以上种种优化措施，本发明提高了译码器的硬件使用效率。

说明书

技术领域

本发明属于通信技术领域，具体涉及前向纠错码－LDPC码的译码算法与译码器结构，主要包括TDMP算法的优化、结构化与非结构化LDPC译码的兼容、译码器硬件构架与时序优化。

背景技术

R.Gallager于1962年首先提出了LDPC码（Low Density Parity Check Codes低密度奇偶校验码），但由于当时的计算水平及人们对这种码的认识不足，LDPC码在此后的几十年并未受到重视。在1993年后，MacKay等人重新发现了LDPC码。 该码的性能十分优异，甚至在码长较长时能够逼近Shannon极限，并且LDPC还具有较小的译码错误概率和较低的译码复杂度。上世纪90年代以来，世界进入了信息化、数字化快速发展阶段，各种通信系统不断出现，如宽带无线接入领域的IEEE 802.11n（WLAN）和IEEE 802.16e（WiMAX），数字多媒体广播领域的欧洲数字电视卫星传输标准（DVB-S2），中国数字电视地面传输标准（DTMB）和适用于手持移动设备的中国移动多媒体广播标准（CMMB）等。 由于LDPC码的出色性能，多数通信标准都采用了LDPC码作为其前向纠错码。

LDPC就其构造分成两种：结构化与非结构化LDPC码。其区别在于校验矩阵中是否含有行重大于一的子矩阵。结构化的LDPC码如DTMB和IEEE 802.16m中的LDPC码，其校验矩阵中不包含这类子矩阵，而非结构化的LDPC码如CMMB和DVB-S2中的则包含这类子矩阵。

LDPC的译码算法主要有两种：TPMP（Two Phase Message Passing）算法或TDMP（Turbo Decoding Message Passing）算法。两类算法的区别在于行列更新顺序不同。在TPMP算法中，所有的行与列依序更新，即所有行或列更新完了之后才进行列或行的更新。而TDMP算法的做法是部分的行与列依序更新，通常是先进行某一层的行更新，然后将与此层的行有关联的列更新。一般而言，TDMP算法的收敛速度更快，存储资源占用也更少。但是TDMP在处理非结构化LDPC时将遇到数据冲突的问题，引发性能的损失， 尤其是当LDPC的校验矩阵中行重大于一的子矩阵数目较多时。

由于人们日常生活中在不同的场合需要使用不同的通信标准，通常人们使用需要不同的设备以满足不同的需求，十分不方便。为此未来硬件设计的一种趋势是可重构化，即同一硬件可配置到不同模式以满足不同需要。故LDPC译码器也应支持各种不同的标准，而由于LDPC构造的不同，使高效的经典TDMP算法不能应用于非结构化LDPC码的译码。并且非结构化与结构化的LDPC码之间存在一些差别，使得可配置的译码器在硬件实现上具有一定的难度。

发明内容

本发明的目的在于提供一种算法收敛速度快，硬件使用效率高的LDPC译码器结构及译码算法。

本发明提出的LDPC译码器，采用通用的串行处理方式，而且对LDPC译码算法与硬件架构都进行了特殊优化，使得LDPC译码器能够完全兼容结构化与非结构化LDPC码。TDMP算法的优化提高了可配置LDPC译码器的算法收敛速度，LDPC译码器的存储策略、主时序和处理单元的优化提高了译码器的硬件使用效率。

一、译码算法

如附图1(a)所示，每个LDPC码都由一个M x N的奇偶校验矩阵所定义。每一行代表一个校验节点，而每一列代表一个信息节点。校验矩阵大部分都是0，而每一个1代表着相应的信息节点与校验节点在Tanner图上有连接关系，如附图1(b)所示。

本发明提出的译码算法的具体步骤如下：

（1）初始化

                     （1）

（2）前验信息更新

a.  当子矩阵的行重为一时：

                      （2）

b.  当子矩阵的行重为二时，在进行式（2）的同时，额外产生一个信息如式（3）所示：

          （3）

（3）外信息更新：

       （4）

（4）后验信息更新

a. 当子矩阵的行重为一时，则按式（5）所式进行更新：

                       （5）

b.  当子矩阵的行重为二时，则按式（6）和（7）所式进行更新：

             （6）

     （7）

（5）重复步骤（2）和步骤（4）直到所有层都完成更新；

（6）硬判决

                       （8）

（7）当达到最大迭代次数或时，完成迭代，并输出，否则k加1并重复步骤（2）到步骤（6）；

其中，是经过信道后信息节点V的本征信息，是信息节点V在第k次迭代中的后验信息，是校验节点C到信息节点V在第k次迭代中的外信息，是信息节点V到校验节点C在第k次迭代中的前验信息，是归一化因子， 是所有与校验节点C有连接关系的信息节点的集合，是所有与信息节点V有连接关系的校验节点的集合，是除去符号，是信息节点V在第k次迭代中的硬判结果。

作为比较，基于归一化最小因子算法，经典TDMP算法可表述为：

1）初始化

                     （9）

2）校验节点更新

                      （10）

       （11）

3）信息节点更新：

                       （12）

4）重复步骤2）和步骤3）直到所有层都完成更新；

5）硬判决

                       （13）

6）当达到最大迭代次数或时，完成迭代，并输出，否则k加1并重复步骤2）到步骤6）。

经典的TDMP算法在译码非结构化LDPC时，会遇到数据冲突问题。如在译码如附图1(a)时，在更新信息节点时，根据式（10）将会发生两个后验信息如式（14）和（15）所示。而由于译码器采用的是串行结构，其中的一个值将会被另一个值所取代，造成信息的损失，最终导致译码性能的损失。

                      （14）

                      （15）。

为了解决这一问题，申请号为200910054350的《一种基于ＳＩＭＤ结构的多标准ＬＤＰＣ译码器电路》技术方案中采用了SIMD结构以同时支持TPMP算法与TDMP算法，在译码非结构化的LDPC码时选用TPMP算法，以避开这种数据冲突问题。但这样降低了收敛度，将增加硬件的功耗，并且由于采用SIMD结构，硬件需要支持各种指令，必将消耗额外的硬件资源。为此本发明对经典的TDMP算法做出调整。在进行外信息更新时仍按式（10）和（11）进行，但在进行前验信息更新时按式（3）所示额外产生一个信息，对于如附图1(a)所示的LDPC码，其结果如式（16）所示。然后在进行后验信息更新时如式（6）和式（7）所示。对于如附图1(a)所示的LDPC码，其结果便如式（17）与（18）所示。

         （16）

                     （17）

（18）

本发明的优化使得TDMP能够有效的译码非结构化的LDPC码，为了验证本发明的可行性，我们基于CMMB和DTMB的LDPC码进行了验证，附图2显示了误码率（Bit Error Ratio, BER）曲线与传统算法的对比。所有仿真都采用了AWGN (Additive White Gaussian Noise) 信道和BPSK（Binary Phase Shift Keying）调制方式。归一化因子为0.75， 在定点化仿真中后验信息与前验信息被量化为8比特，外信息被量化为6比特。其中本发明的算法只使用了15次迭代，而经典的算法使用了25次迭代。从图中可以看到，无论是在浮点还是定点仿真中，本发明的算法的性能都高于经典的TDMP算法。

二、译码器结构

为了展示本发明的译码器结构，本发明以CMMB和DTMB标准为例设计了一个译码器，其主框图如附图3所示。该译码器由主控制器、后验信息存储模块、前验信息存储模块、恢复和累加处理单元、外信息存储模块、归一化处理单元、可配置移位处理单元和奇偶校验与输出模块组成；其中：

（一）所述主控制器，由若干逻辑电路组成，用于实现整个译码器的控制功能，主要包括输入输出的控制，各模块的协调等。

（二）所述后验信息存储模块，由两个存储器块和一个本地控制器组成，负责后验信息的读取与写入，包括如式（1）所示的本征信息的输入、在进行如式（2）所示的前验信息更新前的相应后验信息 的读取及在完成如式（5）或式（7）如式后的更新完的后验信息的写入。

（三）所述前验信息存储模块，由若干存储器和一个本地控制器组成，负责完成如式（2）或（3）更新的前验信息的存储及在进行如式（5）或式（6）的后验信息更新前对相应前验信息进行读取。

（四）所述恢复和累加处理单元，其结构如附图4所示，负责完成如式（2）、（3）、（5）、（6）和（7）的更新操作。

（五）所述外信息存储模块，由若干存储器和一个本地控制器组成，负责完成如式（2）、（3）、（5）、（6）和（7）所述操作前对相应外信息的读取，完成如式（4）的外信息更新后的相应外信息的写入。其读写时序如附图5所示。

（六）所述归一化处理单元，其结构如附图（6）所示，负责从恢复和累加处理单元读取更新后的前验信息，然后完成如式（4）所示的外信息更新操作。

（七）所述可配置移位处理单元，其结构如附图（7）所示，负责在处理子矩阵时对相应后验信息或前验信息的循环移位。

（八）所述奇偶校验与输出模块，负责完成步骤（6）与步骤（7），即硬判决、奇偶校验及相应硬判决信息的输出。 

所述恢复和累加处理单元负责完成式（2）、（3）、（5）、（6）和（7）的计算。 由于采用归一化最小和（Normalized Min Sum, NMS）算法,外信息可划为最小值、次小值、最小值位置和所有符号位。因此在进行算法计算时，传统的做法是将这些值恢复成一个补码形式的数字再进行如式（2）、（3）、（5）、（6）和（7）的计算。但这种恢复与将式中的加减法互换没有区别，并且为了减少硬件资源的消耗，本发明中的译码器只采用了一种累加器，并支持加法和减法操作。

为此在本发明的译码器中，外信息的恢复与前验信息和后验信息的更新在同一处理单元中进行，其结构如附图4所示， 由若干选择器、比较器、异或逻辑单元、有限域加法器构成，其输入为最小值、次小值、外信息符号、最小值索引和当前索引。选择器根据当前索引值从外信息符号中提取出相应符号。当当前索引与最小值索引相同时，绝对值取次小值，不同时则取最小值。当符号位与计算模式Cal_mode(1为减法，0为加法)不同时，即减去一负数或加上一正数时，信号Hsub_Ladd将为0，信号temp将取绝对值，有限域加法器将完成正常的加法操作。而符号位与计算模式Cal_mode相同时，即要减一正数或加上负数时，信号Hsub_Ladd将为1，信号temp将为绝对值的按位取反值，有限域加法器将完成减法操作。这样译码器就可以将外信息的恢复和前验信息或后验信息的更新在同一处理单元内进行操作，节省了硬件的使用，提高了硬件效率并能减少功耗。

所述归一化处理单元负责完成式（4）的计算，其结构如附图6所示，由绝对取值器、乘法器、溢出检查模块及两个比较器组成。当前验信息完成如式（2）的更新后，便被传递到该模块。先取得前验信息的绝对值，然后再乘上归一化因子。由于前验信息为8位，其绝对值为7位，而外信息只有6位，其绝对值为5位，故在乘于归一化因子后，仍需要进行溢出检查，以便将截位到外信息所需要的位宽。最后是将截位后的值先与当前的最小值比较，将其中最小值作为输出最小值，而其中的次小值则与当前次小值做比较，将其中最小值作为输出次小值。

所述可配置循环移位器采用如附图7所示的可配置循环移位网络，采用了三级流水半并行结构， 每一级都由若干选择器组成，分别负责一定位数的移位。由于LDPC校验矩阵的子矩阵为循环移位阵，而外信息的存储是按照自然顺序进行的，故在进行前验信息或后验信息更新时，需要将相应的后验信息或前验信息进行一定的移位才与能相应的外信息一一对应，故需要循环移位器。由于不同标准的LDPC码子矩阵大小不同，且子矩阵的循环移位序数不同，循环移位器需要支持不同的宽度与移位序数，故该移位器必须是可配置的。

本发明的可配置循环移位网络，采用了三级流水半并行结构。其移位宽度根据译码的标准可设置成不同值，实现宽度的可配置。向左移m位赞同于向右移位P-m位，故循环移位器可只支持一个方向。而移位序数offset本身为8位，被划分成三部分： offset[2:0]、offset[5:3]、offset[7:6]。第一级负责移位a= offset[2:0]位，而第二级负责移位b= 8 x offset[2:0]位，最后一级负责移位c= 64 x offset[2:0]位。

附图说明

图1 LDPC校验矩阵示意图。

图2算法性能对比图。

图3译码器总体结构图。

图4恢复和累加模块示意图。

图5外信息存储时序图。

图6  归一化处理单元结构图。

图7 可配置循环移位器。

图8  行重大于一的子矩阵划分示意图。

图9  主时序图。

图10  译码器后端版图。

具体实施方式

根据发明内容中提供的解决方案，以译码结构化LDPC码时采用经典TDMP算法，在译码非结构化LDPC码时采用采用了本发明的经调整后的TDMP译码算法。本发明还优化了外信息存储策略。下外将分别介绍本发明的外信息存储策略、主时序及与其他译码器的比较。

外信息存储策略

通常译码器会将某一层的外信息的读写操作在一个周期内完成，但不同标准不同码率之前的校验矩阵构造不同。附表1列出了CMMB和DTMB中外信息存储的主要参数。如果采用传统的存储策略，那么相关参数需要采用各码率之前的最大值，即为36 x 128 x 42=193,536比特。这将极大地浪费存储空间。

为此本发明将外信息的存储划分到若干个周期，每个外信息在每周期只处理若干比特，时序图如附图5所示。这样在CMMB码率1/2和DTMB码率2/5时需要三个周期，CMMB码率3/4和DTMB码率3/5时需要四个周期，DTMB码率4/5时需要6个周期。这样存储器的深度将为层数乘于所需周期，最大值为36 x 3＝108。每个周期处理的比特为7 x 128＝896。 总共需要的存储空间为108x896=96,768比特，仅为传统存储策略的一半。

译码主时序

关于CMMB的校验矩阵，可以给出两点声明：1）某一层中只可能含有一个行重大于一的子矩阵；2）行重大于一的子矩阵可被划分为一个标准单元阵和一个循环移位阵。附图1的校验矩阵具有类似的特点，其可被划分为附图8所示的子矩阵，其中子矩阵0和子矩阵1共享相同的后验信息。下面将以附图1所示的LDPC码为例说明本发明的译码主时序。

当层中没有行重大于一的子矩阵时，如DTMB中的LDPC，则硬件按经典的TDMP算法进行操作，其主时序为附图9(a)所示。

1、在进行前验信息和外信息更新时，译码器首先从后验信息存储模块中读取相应的后验信息（外信息的读取与写入分成若干个周期，在附图9中未显示）， 并从Hrom中读取出相应的移位序数。然后可配置循环移位器将完成对后验信息的移位。移位完成后，恢复和累加处理单元将读取移位后的后验信息，并完成如式（2）所示的前验信息更新。 最后归一化处理单元将读取更新后的前验信息并完成如式（4）所示的外信息更新，与此同时更新后的前验信息将被存入前验信息存储模块。

2、在进行后验信息更新时，译码器将首先从前验信息存储模块中读取出相应的前验信息。然后恢复和累加处理单元将读取前验信息将完成如式（5）所示的后验信息更新。更新后的后验信息将在可配置循环移位网络中被移位回本来顺序。最后相应的后验信息将被存入后验信息存储模块中。

当层中有行重大于一的子矩阵时，如CMMB中的LDPC，则硬件按权利一所示的改进型TDMP算法进行操作，其主时序为附图9(b)所示。

3、在进行前验信息和外信息更新时，子矩阵1的操作与图9(a)所示的子矩阵0的操作一样。而译码器能在时钟一就能完成对子0的前验信息更新，而不需要经过循环移位，因为子矩阵0是一个标准单元阵。然后在时钟二，子矩阵0的前验信息将在可配置循环移位模块中完成移位。接着在时钟三，恢复和累加处理单元将根据移位后的子矩阵0的前验信息完成如式（16）所示对额外信息的生成。最后将在时钟四被当成前验信息存储到前验信息存储模块中。

4、在进行后验信息更新时，译码器将首先从前验信息存储模块中读取出额外信息。然后在时钟6，恢复和累加处理单元将读取将完成如式（17）所示的生成。在时钟7，将在可配置循环移位器中被移回到正常顺序。接着在时钟8，恢复和累加处理单元将读取移位后的完成如式（18）所示的对后验信息的更新。最后相应的后验信息将被存入后验信息存储模块中。

在上述实施方案中，采用本发明提供的调整后的算法，译码器可以使用同一硬件单元完成结构化和非结构化LDPC的译码，并不需要额外的处理单元，节省了硬件资源，提高了硬件使用效率。并且能够实现译码器的可配置化，提高了译码器的灵活性。

结果比较

为了验证本发明方案的效率，基于SMIC0.13um标准CMOS工艺，我们设计了一款支持非结构化CMMB和结构化DTMB的所有码率的LDPC译码器。其后端版图如附图10所示。该译码器的内核面积为2.16x2.20mm². 最高工作频率可达200MHz, 最大吞率可达365.7Mbps。在5次迭代条件下，芯片的后仿功耗为48.4mW工作在25MHz和CMMB标准时，130.9mW工作在50MHz和DTMB标准时。附表2比较了本发明的译码器与一些文献的硬件结果，从表中可以看出，本发明的可以完成支持CMMB和DTMB的LDPC译码器具有比其他支持单标准（CMMB或DTMB）的LDPC译码器更小的芯片面积，由此可以看出本发明的译码器的高效性。

表1 CMMB和DTMB的外信息存储的主要参数

。

表2 本发明译码器与其他译码器的比

。

参考文选：

 [1]Kai Zhang, Xinming Huang, Zhongfeng Wang, "An Area-Efficient LDPC Decoder Architecture and Implementation for CMMB Systems", in PROC.IEEE ASAP, pp. 235-238,July. 2009.

[2]Kai Zhang, Xinming Huang, Zhongfeng Wang, "A dual-rate LDPC decoder for china multimedia mobile broadcasting systems", IEEE Transactions on Consumer Electronices, vol. 56, pp. 399-407, May. 2010

[3]Bo Xiang, Rui Shen , An pan, Dan Bao, Xiaoyang Zeng, "An Area-Efficient and Low-Power Multirate Decoder for Quasi-Cyclic Low-Density Parity-Check Codes", IEEE Transactions on Very Large Scale Integration (VLSI) Systems ,vol.18, pp. 1447-1460, Oct. 2010

[4]M. M. Mansour and N. R. Shanbhag, "A 640-Mb/s 2048-bit programmable LDPC decoder chip," IEEE J. Solid-State Circuits, vol. 41, pp. 634-698, March. 2006。