基于哈密尔顿图的低密度奇偶校验码的纠错编码方法

摘要

基于哈密尔顿图的低密度奇偶校验码的纠错编码方法属于数字信号传输与存储领域，其特征在于，本发明的低密度奇偶校验码的校验矩阵为连接的简单哈密尔顿图的关联矩阵，可以分为两部分，能够实现线性时间编码。校验矩阵的描述可利用哈密尔顿图的Lederberg－Coxeter－Frucht表示与方向矢量得到，进一步降低了编码复杂度。本发明的低密度奇偶校验码基于的哈密尔顿图，特别是笼子图，特征在于具有大的围长。本发明设计的低密度奇偶校验码校验矩阵的描述简单，具有低的编码复杂度，并具有大的围长与最小距离，在高信噪比下性能优越，误码平台低。

说明书

技术领域

本发明属于数字信号传输与存储领域，特别涉及一种利用基于哈密尔顿图的线性时间可编码的、低复杂度的低密度奇偶校验码的纠错编码方法。

背景技术

在现代数字信号传输与存储系统中，由于传输信道噪声或存储媒介的物理损伤等，常会造成数字信号的传输或者存储的错误，因此，为保证数字信号传输或存储的可靠性，纠错编码技术是一项标准技术。

低密度奇偶校验(LDPC)码是1962年美国麻省理工学院的Gallager教授提出的，但是由于计算机技术与微电子技术等硬件技术的限制，很快就被学术界遗忘了，没有得到应用。幸运的是，随着Turbo码的发明和迭代译码算法的深入研究，1996年英国剑桥大学的Mackay等重新证实了LDPC码优越的纠错性能，从而使LDPC码迅速成为研究与应用的热点。LDPC码的最大优势是：在码长很长时，能够获得逼近理论极限的性能；当采用迭代译码算法时，其译码复杂度较低，并且能够并行实现，非常适合当前高速的数据传输与存储应用领域。因此，LDPC码已成为一种非常有应用价值的纠错编码技术，在很多通信标准或系统中得到了或将要得到应用，例如第二代数字卫星广播、无线城域网等。

但是，LDPC码虽具有强大的纠错能力，在码长很大时，能获得逼近纠错编码的理论极限香农极限的性能，但是在实际应用中也存在很多问题。

一方面，信道编码通常用达到某个误比特率的信噪比来衡量其纠错能力。一般而言，随着信噪比的增加，信道编码的译码器输出的误比特率迅速下降，满足用户的需求。但是，LDPC码在采用迭代译码算法时，由于LDPC码结构的限制与译码算法的次最优性，常存在较高的误码平台。LDPC码的“误码平台”是指随着输入到LDPC码译码器的信噪比的增加，误比特率的下降非常缓慢的现象。因此，当采用的LDPC码出现误码平台现象时，为达到用户需要的误比特率，就需要非常高的信噪比或根本无法达到要求的误比特率，这样就造成了极大的功率浪费，限制了LDPC码在一些要求非常低的误码比特的系统中的应用，例如数字广播、高速存储或者高速的光纤通信系统。LDPC码的误码平台与LDPC码的结构，例如最小距离、环分布特性、陷阱集、停止集等组合参数有非常重要的关系。根据本发明提出的信道编码方法，对LDPC码的环参数，主要是最小环的围长，进行了优化设计，因此使得设计的LDPC码具有非常低的误码平台。

另一方面，LDPC码是定义在维数非常大的稀疏校验矩阵上的线性分组码，一般而言，其编码具有复杂度O(N²)，这里N为LDPC码的码长。因此，LDPC码的低复杂度的编码问题成为LDPC码应用中的主要困难之一。

为实现LDPC码的低复杂度编码，主要有以下两类方法：

一类方法是对LDPC码的校验矩阵进行某种限制，从而实现LDPC码的线性或近似线性编码，该类方法的主要优点是：该类LDPC码可获得非常好的纠错性能，同时编码复杂度适中。例如，为实现LDPC码的线性编码，降低硬件系统的复杂度，一种被称为重复累加(RA)码的LDPC码被提出了，该类LDPC码能够实现线性复杂度的编码，已经在欧洲的第二代数字卫星广播中得到了应用。

另一类方法是采用结构化的LDPC码构造方法，也即采用准循环等的构造方法，例如基于欧氏几何或者射影几何的LDPC码等。构造的该类LDPC码的编码复杂度很低，非常适合利用移位寄存器实现。但是，利用这类方法设计的LDPC码的码率和性能常存在限制。

基于第一类方法设计的LDPC码的译码门限性能常常很优越，但基于这类方法设计的LDPC码的校验矩阵的描述仍需要较多的参数，需要较大的存储空间，因此复杂度仍然很高。在本发明中，融合了这两类设计LDPC码的方法的优点，基于哈密尔顿图设计的LDPC码能够实现线性时间编码，并且其校验矩阵的描述可借助一类特殊的具有很好的对称性的哈密尔顿图的旋转对称性，因此该类LDPC码的校验矩阵的描述非常简单，编码算法也非常简单，适合利用移位寄存器等硬件电路实现。

另外，LDPC码为定义在校验矩阵H上的线性分组码，可以利用其校验矩阵H完全描述，并且LDPC码的编译码复杂度与其校验矩阵H有非常重要的关系。为降低LDPC码编译码算法的计算量，一般要求LDPC码的校验矩阵具有非常好的稀疏性。同时，为保证LDPC码有优越的纠错性能，还要求校验矩阵H具有非常好的随机性。

如果LDPC码的校验矩阵H中的每一行或每一列中“1”的个数都相同，就称为规则码。对于规则码，每一行中所含“1”的个数称为其行重量，每一列中所含“1”的个数为列重量。如果LDPC码的行重和列重都是比较小的，则该LDPC码的校验矩阵具有很好的稀疏性，编译码的运算量就非常小，适合硬件实现，便于在实际系统中应用。一般而言，对于码长为几千到几万的LDPC码，其行重量和列重量一般少于几十，例如在第二代数字卫星广播中应用的LDPC码，其行重量与列重量都不是很大。本发明的主要目的是设计一类列重量为2的LDPC码。

列重量为2的LDPC码，也称为环码，具有非常低的译码复杂度，并且在一些应用环境下，如部分响应信道，具有非常优越的性能。虽然列重量为2的LDPC码的译码复杂度非常低，并且性能优越，但是其编码复杂度，尤其是校验矩阵的描述仍然较为复杂。本发明针对列重量为2的LDPC码，设计一类具有线性时间编码复杂度的列重量为2的LDPC码，并且其校验的矩阵的描述非常简单，可以借助一些简单参数在编码时在线实时生成。

基于以上考虑，本发明设计了一类列重量为2的LDPC码，该类LDPC码在高的信噪比下具有低的误码平台，并且能够线性编码，矩阵的描述也非常简单，因此具有非常低的编码复杂度。和已有的类似LDPC码相比，利用本发明设计的LDPC码的复杂度低，性能优越。

发明内容

本发明的目的是提供一种利用基于哈密尔顿图的低密度奇偶校验码的纠错编码方法。

本发明的特征是该低密度奇偶校验(LDPC)码的纠错编码方法可以利用超大规模集成电路实现，在超大规模集成电路内至少包含一个LDPC码编码器与一个LDPC码译码器。

LDPC码编码器实现输入信息比特流的编码，至少包括一个输入比特缓存单元、一个编码运算单元、一个输出编码比特缓存单元以及一个控制电路。

本发明的LDPC码编码器的输入比特缓存单元和输出比特缓存单元可以利用随机存储器(RAM)或者先入先出存储器(FIFO)实现。

本发明的LDPC码编码器的编码运算单元包含一个由n个单比特累加器并联组成的累加器阵列、一个地址生成单元和一个单比特的校验位累加器。

本发明的LDPC码编码器的编码运算单元的特征在于，编码运算单元按照下面步骤进行处理：

(6)将顶点数为n、边数为m的连接的简单哈密尔顿图的关联矩阵作为低密度奇偶校验码的校验矩阵H，校验矩阵H每列包含2个“1”，每行包含的“1”的个数和矩阵中“1”的位置由连接的简单哈密尔顿图确定；本发明借助的连接的简单哈密尔顿图的特征在于，具有大的围长，可以借助笼子图；笼子图是一类具有最少顶点数、围长为g(g为大于等于6的偶数)的k-规则图，这里k大于等3；

(7)根据哈密尔顿图可以用一个哈密尔顿环路加上弦边的方式描述，将校验矩阵H分为两部分，分别表示为H_c与H_m，并且有H＝[H_m，H_c]；矩阵H_c中每行与每列中只有2个“1”，矩阵仅仅在其对角线、左下的次对角线以及最右上角上的元素为“1”，其它位置的元素均为“0”；矩阵H_m中每列中也包含2个“1”，其中“1”的位置是根据哈密尔顿图的弦边的关联关系决定的，具体的连接关系可以根据哈密尔顿图的Lederberg-Coxeter-Frucht表示与方向矢量来描述获得；

(8)编码运算单元在控制电路的控制下从输入比特缓存单元读取一个信息比特，在矩阵矩阵H_m的控制下进入累加器阵列中的两个累加器；这两个累加器是由地址生成单元控制的，地址生成单元的作用是实时生成矩阵H_m；矩阵H_m是利用哈密尔顿图的Lederberg-Coxeter-Frucht表示与方向矢量生成；本发明的方向矢量的特征是，该方向矢量的元素个数是2(m-n)，每个元素或者是“1”或者是“0”，方向矢量是通过离线设计得到的，存储在单比特的数组中；

(9)当一个LDPC码的码字所有的m-n+1个信息比特全部进入累加器阵列以后，从累加器阵列中的第2个累加器的数据开始依次进入校验位累加器，校验位累加器的输出在控制电路的作用下，进入输出编码比特缓存单元；

(10)在控制电路的作用下，依次输出输入比特缓存单元中的信息比特，输出比特缓存单元中的校验比特，编码器输出了完整的编码码字。

LDPC码译码器完成受到噪声污染的数据的恢复，至少包括一个输入数据缓存单元、一个译码运算单元、一个输出数据缓存单元以及一个控制电路。

本发明的译码器的输入缓存单元和输出比特缓存单元可以利用随机存储器(RAM)或者先入先出存储器(FIFO)实现。

本发明的译码器的运算单元实现标准的和积迭代译码算法。

本发明设计的LDPC码可以按照上述的编码方法进行编码，编码复杂度很低。该发明设计的LDPC码有很大的围长和最小距离，和同种类型的LDPC码相比较，采用和积迭代译码算法，在高信噪比下有非常优越的性能，随着信噪比的增加，误码率迅速下降，没有明显的误码平台现象。

附图说明

图1哈密尔顿图上的LDPC码的校验矩阵。

图2连接的简单哈密尔顿图。

图3矩阵H_c。

图4 k-规则图的LCF表示。

图5哈密尔顿图的生成过程。

图6笼子图。

图7基于哈密尔顿图的低密度奇偶校验码的纠错编码方法框图。

图8编码器框图。

图9编码运算单元框图。

图10译码器框图。

图11设计的LDPC码的误比特率性能曲线。

具体实施方式

下面结合附图，对本发明的具体实施方式说明如下。

本发明的目的是提供一种利用基于哈密尔顿图的低密度奇偶校验码的纠错编码方法。本发明设计的低密度奇偶校验(LDPC)码是基于大围长、具有好的旋转对称性的简单连接的哈密尔顿图，因此设计的LDPC码具有低的编码复杂度，同时具有大的围长和最小距离，在高信噪比下有优越的性能。

LDPC码可以利用其校验矩阵H完全描述。为了说明本发明的发明目的，也即提供一种利用基于哈密尔顿图的低密度奇偶校验码的纠错编码方法，先说明本发明中的LDPC码的校验矩阵H的构造方法，然后说明利用基于哈密尔顿图的低密度奇偶校验码的纠错编码方法。

本发明的是将连接的简单哈密尔顿图的关联矩阵作为LDPC码的校验矩阵。任何连接的简单哈密尔顿图的关联矩阵都可以用于表示LDPC码。图1给出了一个简单的例子，在这个例子中给出的哈密尔顿图参数为顶点数为n＝5，边数为m＝10，其对应的关联矩阵如图1所示，该关联矩阵可以作为LDPC码的校验矩阵，定义了一个长度为10比特的LDPC码，其校验矩阵的维数为5×10。

连接的简单哈密尔顿图是指具有哈密尔顿环路的简单连接图。哈密尔顿环路是包含所有顶点的环路。图2给出的哈密尔顿图包含8个顶点，12条边。哈密尔顿图的特征之一是可以利用一个哈密尔顿环路加上若干弦边的方式描述，而弦边可以利用其连接的两个顶点描述，如图2所示。图2中的哈密尔顿图包含一个哈密尔顿环路与4条弦边。根据上述的LDPC码的校验矩阵构造方法，将该哈密尔顿图的关联矩阵作为LDPC码的校验矩阵H，表示如下：

$H=\left(\begin{array}{cccccccccccc}1& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 1\end{array}\right).$

根据哈密尔顿图哈密尔顿环路加上若干弦边的描述方式，可以看出，校验矩阵H可以分为两部分H_m与H_c，这里有H＝[H_m，H_c]。也就是说关联矩阵对应哈密尔顿环路部分表示为H_c，实际上为验矩阵H的右半部分，其维数为n×n。矩阵H_c中每行包含2个“1”，每列中也包含两个“1”，矩阵H_c对角线、左下的次对角线以及最右上位置处为1，其它位置元素为0，如图3所示。关联矩阵中对应哈密尔顿图的弦边表示H_m，实际上为校验矩阵H的左侧部分，其维数为(m-n)×n。在图2的哈密尔顿图上定义的LDPC码的校验矩阵中，H_m表示为：

$H_m=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right).$

H_c表示为：

$H_c=\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 1& 1\end{array}\right).$

为实现LDPC码的高效编码，将矩阵H_c对应LDPC码的校验比特，H_m对应LDPC码的信息比特。如果一个连接的简单哈密尔顿图的顶点的数量为n，边的数量为m，则利用上述方法得到校验矩阵的秩为n-1。因此，校验矩阵中存在一行为冗余行，假设第一行为冗余行，将其删掉，则得到矩阵$\tilde{H}=[{\tilde{H}}_m,{\tilde{H}}_c].$利用这种方法设计的LDPC|码的码率为：

$R=1-\frac{n-1}{m}.$

利用这种方法得到校验矩阵其右侧为一个双对角线矩阵因此该LDPC码具有重复累加(RA)码的形式，假设LDPC码的码字表示为：c＝[m，p]，这里，m和p分别表示信息位与校验位矢量。根据分组码$\tilde{H}·c^T=0,$可以得到校验位矢量表示为：

$p^T={\tilde{H}}_c·({\tilde{H}}_m·m^T).$

因此，本发明设计的LDPC码具有重复累加码的形式，可实现线性编码。

更进一步，在本发明中，矩阵H_m可以用哈密尔顿图的弦边连接关系与方向矢量得到，这进一步降低了该类LDPC码的编码复杂度。

具有好的旋转对称性的哈密尔顿图，弦边的连接关系可以用LCF表示得到。LCF是描述3-规则图的一种简洁方式，该方式利用了哈密尔顿图的旋转对称性。本发明中，将LCF表示方式扩展到一般的k-规则图。这里，对于一般的具有哈密尔顿特性k-规则图的LCF表示的形式如图4所示。在这里，LCF描述的参数r和s是由哈密尔顿图的对称性决定的，对一般k-规则图有n＝r·s。另外，我们定义LCF中的元素c_t，u有-n≤c_t，u≤n，1≤t≤k-1，1≤u≤s＝n/r。例如，图1中的哈密尔顿图的LCF表示为：

$\mathrm{LCF}={\left(\begin{array}{c}2\\ -2\end{array}\right)}^5.$

采用LCF表示，对于具有哈密尔顿性质的k-规则图的弦边生成过程可以利用下面的流程得到：

初始化：将哈密尔顿图的哈密尔顿环路上的顶点依次编号为1，2，….，n；

执行循环：

For t＝1 to k-2

   For p＝1 to n

               b＝((p-1)mod s)+1，

               q＝((p-1)+c_t，b mod n)+1，

               顶点p和顶点q间生成一条边。

   End p；

End t；

图2中的哈密尔顿图的LCF表示为LCF＝[3，-3]⁴，对于该图，利用上述的生成流程，其所有弦边的生成过程如图5所示。

从上面弦边生成过程中，可以看出每条弦边被从不同的方向生成了两次。如果利用关联矩阵的描述方式描述利用上述流程生成弦边的过程，得到矩阵H_LCF。例如图4的弦边生成过程利用矩阵表示如下：

$H_{\mathrm{LCF}}={\left(\begin{array}{cccccccc}1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 1\end{array}\right)}_{8\times 8}.$

在矩阵H_LCF中，每条弦边从不同的顶点、在不同的方向上生成了两次。因此，定义方向矢量来描述如何从矩阵H_LCF得到矩阵H_m。方向矢量d中的每个元素表示矩阵H_LCF中某列是否包含在矩阵H_m中，若方向矢量中的某个元素为“1”，则矩阵H_LCF中的该列包含在矩阵H_m中；否则，若方向矢量中的某个元素为“0”，则矩阵H_LCF中的该列不包含在矩阵H_m中，因为矩阵H_m中已经包含一相同的列。

方向矢量的获得可以借助LCF表示离线获得，存储在数组中。

因此，LCF表示结合方向矢量可以完整描述矩阵H_m，利用这种方式描述矩阵H_m，可以大大降低LDPC码的校验矩阵的描述复杂度。对于顶点数为n、边数为m的连接的简单哈密尔顿图上定义的LDPC码，方向矢量的长度为2(m-n)，其中包含m-n个元素“1”和m-n个元素“0”。

该例子中的方向矢量表示为：

                         d＝[1，1，1，0，1，0，0，0]。

可以看到，利用哈密尔顿图的LCF表示和方向矢量d可以容易得到矩阵H_m。

因此，本发明设计的LDPC码基于哈密尔顿图，将其校验矩阵分为H_m与H_c，并且矩阵H_c描述哈密尔顿环路，具有固定的形式，H_m描述弦边的连接关系，可以利用哈密尔顿图的旋转对称性，利用LCF表示方式结合方向矢量实时生成，因此可以设计具有非常低的编码复杂度的LDPC码。

本发明的另外一个特征是设计的LDPC码具有非常大的围长与最小距离。其主要是方法是利用具有很好的旋转对称性的高围长的哈密尔顿图，设计高围长的LDPC码，在高信噪比下具有优越的性能。笼子图是一类具有最少数量的顶点、围长为g的k规则图。笼子图是一类特殊的哈密尔顿图。例如，图6给出了一个简单的笼子图，该笼子图的围长为，顶点数为。基于该笼子图可设计码率为1/3，码长为比特，围长为的LDPC码。

上面介绍了基于哈密尔顿图的LDPC码的校验矩阵的构造方法，也即LDPC码的设计方法。下面说明利用这种LDPC码的纠错编码方法，利用该类LDPC码的纠错编码方法框图如图7所示，该纠错编码方法可以利用超大规模集成电路实现，在超大规模集成电路内至少包含一个LDPC码编码器与一个LDPC码译码器。

LDPC码编码器实现输入信息比特流的编码，至少包括一个输入比特缓存单元、一个编码运算单元、一个输出编码比特缓存单元以及一个控制电路等，如图8所示。

本发明的LDPC码编码器的输入比特缓存单元和输出比特缓存单元可以利用随机存储器(RAM)或者先入先出存储器(FIFO)实现。

本发明的LDPC码编码器的编码运算单元包含一个由n个单比特累加器组成的累加器阵列、一个地址生成单元和一个单比特的校验位累加器，如图9所示。

本发明中的编码运算单元的工作步骤，按照前面所述的利用LCF表示和方向矢量生成H_m的过程动作。在控制电路的作用下，输入的信息比特进入累加器阵列。完成了所有信息比特的输入以后，累加器阵列中的数据进入校验位累加器，得到校验位，完成了该码字的编码过程。

利用基于哈密尔顿图的低密度奇偶校验码的纠错编码方法还包括一个在超大规模集成电路内部实现的译码器，如图7所示。

LDPC码译码器完成受到噪声污染的数据的恢复，至少包括一个输入数据缓存单元、一个译码运算单元、一个输出数据缓存单元以及一个控制电路，如图10所示。

本发明的译码器的输入缓存单元和输出比特缓存单元可以利用随机存储器(RAM)或者先入先出存储器(FIFO)实现。

本发明的译码器的运算单元实现标准的和积迭代译码算法。

总之，本发明设计的LDPC码可以按照上述的编码方法进行编码，编码复杂度很低，编码器的实现简单。本发明的译码器中的译码器运算单元可以采用一般的标准和积算法。因为该发明设计的LDPC码有很大的围长和最小距离，和同种类型的LDPC码相比较，采用译码算法，在高信噪比下有非常优越的性能，误码平台现象不明显。

本发明的一个具体实施例

本发明利用基于哈密尔顿图构造的低密度奇偶校验码的纠错编码方法，实现简单，具有非常有效的纠错能力。本发明提出的基于哈密尔顿图构造的高效编码的LDPC码，其校验矩阵采用LCF表示和方向矢量描述，复杂度低；基于高围长的哈密尔顿图，例如笼子图，设计的LDPC码具有大的围长，在高信噪比下具有非常优越的性能。结合本实施例，可以进一步理解本发明的目的、特征和优点。

下面以一个围长为17的哈密尔顿图上定义的LDPC码为例说明，本发明设计的LDPC码的特点和性能。

该哈密尔顿图的为3-规则图，围长为17，顶点数量为2520，因此基于该LDPC码可以设计码率为1261/3780的LDPC码。该哈密尔顿图的LCF表示为：

LCF＝[61，76，1283，495，2206，-61，1852，-76，-495，382，-1852，-1283，-2206，-382]¹⁸⁰。

因此，基于该哈密尔顿图设计的LDPC码的码率近似为1/3，LDPC码的围长为34，最小距离为17。由于具有较大的最小距离和大的围长，该LDPC码在高信噪比下具有非常优越的性能。

利用该图定义的LDPC码的校验矩阵的生成仅需要存储这14个数，即可在编码过程中利用图所示的流程，借助方向矢量，生成校验矩阵H。

方向矢量是利用离线设计的方法获得的。

本发明的编码器采用如图8的框图，译码器使用如图10的框图。

图11给出了设计的LDPC码在加性高斯白噪声信道下的性能，和其它方法设计列重量为2的LDPC码相比较，本方法设计的LDPC码具有非常优越的性能。