LDPC编码原理

LDPC码是一种线性分组码，它于1962年由Gallager提出，之后很长一段时间没有收到人们的重视。直到1993年Berrou等提出了turbo码，人们发现turbo码从某种角度上说也是一种LDPC码，近几年人们重新认识到LDPC码所具有的优越性能和巨大的实用价值。1996年MacKay和Neal的研究表明.采用LDPC长码可以达到turbo码的性能，而最近的研究表明，被优化了的非规则LDPC码采用可信传播(Belief Propagation)译码算法时，能得到比turbo码更好的性能。

和另一种近Shannon限的码——Turbo码相比较，DLPC码主要有以下几个优势： 1.LDPC码的译码算法，是一种基于稀疏矩阵的并行迭代译码算法，运算量要低于Turbo码译码算法，并且由于结构并行的特点，在硬件实现上比较容易。因此在大容量通信应用中，LDPC码更具有优势。

2.LDPC码的码率可以任意构造，有更大的灵活性。而Turbo码只能通过打孔来达到高码率，这样打孔图案的选择就需要十分慎重的考虑，否则会造成性能上较大的损失。

3.LDPC码具有更低的错误平层，可以应用于有线通信、深空通信以及磁盘存储工业等对误码率要求更加苛刻的场合。而Turbo码的错误平层在10-6量级上，应用于类似场合中，一般需要和外码级联才能达到要求。

4.LDPC码是上个世纪六十年代发明的，现在，在理论和概念上不再有什么秘密，因此在知识产权和专利上不再有麻烦。这一点给进入通信领域较晚的国家和公司，提供了一个很好的发展机会。

而LDPC码的劣势在于：

1.硬件资源需求比较大。全并行的译码结构对计算单元和存储单元的需求都很大。 2.编码比较复杂，更好的编码算法还有待研究。同时，由于需要在码长比较长的情况才能充分体现性能上的优势，所以编码时延也比较大。

3.相对而言出现比较晚，工业界支持还不够。

目前，LDPC码被认为是迄今为止性能最好的码。LDPC码是当今信道编码领域的最令人瞩目的研究热点，近几年国际上对LDPC码的理论研究以及工程应用和VLSI(超大规模集成电路)实现方面的研究都已取得重要进展。基于LDPC码的上述优异性能可广泛应用于光通信、卫星通信、深空通信、第四代移动通信系统、高速与甚高速率数字用户线、光和磁记录系统等。LDPC码可以用非常稀疏的校验矩阵或二分图来描述，也就是说LDPC码的校验矩阵的矩阵元除一小部分不为0外，其它绝大多数都为0。通常我们说一个(n,j,k)LDPC码是指其码长为n，其奇偶校验矩阵每列包含j个1，其它元素为0；每行包含k个1，其它元素为0。j和k都远远小于n，以满足校验矩阵的低密度特性。校验矩阵中列和行的个数即j和k为固定值的LDPC码称为规则码，否则称为非规则码。一般来说非规则的性能优于规则码。

一、编码部分

LDPC码所面临的一个主要问题是其较高的编码复杂度和编码时延。对其采用普通的编码方法，LDPC码具有二次方的编码复杂度，在码长较长时这是难以接受的，幸运的是校验矩阵稀疏性使得LDPC码的编码成为可能。目前，好的编码方法一般有如下几种情况： 1、T.J.Richardson 和R.L.Urbanke 给出了利用校验矩阵的稀疏性对校验矩阵进行一定的预处 理后，再进行编码。

2、设计LDPC 码时，同时考虑编码的有效性，使Ｈ矩阵具有半随机矩阵的格式。 3、H 矩阵具有某种不变特性所采用的其他编码方法，例如基于删除译码算法

提出的编码方案。

这几种编码方案都是在线性时间内编码的有效算法，初步解决了LDPC 码的应用所面临的一个主要问题。下面对这几种编码方案作一些简单的说明。

Richardson等提出的有效编码方案：

LDPC码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步初等

'?变换得到右边单位阵形式H=?P|I?，由G＝?I|P??得到生成矩阵，从而由C=M*G直接编

码。这样的编码方法是复杂的，主要原因是由于高斯消去法破坏了原有奇偶校验矩阵的稀疏

性。为了保持矩阵的稀疏性，Richardson 提出了有效编码方案，首先可以对矩阵的列做重排，这样虽然不能得到一个完全的下三角形式的矩阵，但可以获得一个近似的下三角矩阵。如图所示，分成六个分块的稀疏矩阵,其中g是一个相当小的数。如下图所示:

图1

对于要发送的信息序列，依然直接作为LDPC 码字的前N-M个信息位比特输出，对于 其生成的校验比特，将其分成两块[p1,p2]，v=[u,p1,p2],根据H?v = 0, ,我们将得到以下的两个关系式

TTAuT?Bp1?Tp2?0 (1)

T??ET??ET?1TA?C?uT???ET?1B?D?p1?0 (2)

由（1）式乘以?ET ?1再加上（2）式，我们可以得到式（3）如下：

?1TA?C?uT???ET?1B?D?p1?0 (3)

通过（3）式求出p1,代入（1）式，就可以得到p2,从而完成编码过程。

编码复杂度的分析，因为这六个分块阵是通过对原有稀疏矩阵的列做重排获得的，所以 这些分块阵依然满足稀疏性，我们可以进一步分析出求解P1 和P2 的运算量分别为o(N + g2 )和o?N?。由此可以看出，当g尽量小的时候，LDPC 码的编码运算量，就可以控制在线性复杂度附近。

在特殊情况下，设计码字时，考虑令Φ = ?ET ?1B + D ,当其为Ｉ阵时，又可以进一步 降低编码的复杂度，此时编码步骤可以参考如下：

步骤1）计算Au和Cu, 步骤2）计算ET?1AuT

T步骤3）计算p1 T步骤4）计算p2

TT??编码结构图如下所示：

图2

定义校验矩阵H??H1H2?，H1是k*(n-k)，H2是(n-k)*(n-k)；设计码字时，令H2矩

阵具有如下的形式：

?1?0?H2??0????0110011000?0??? ?1?1??将生成的码字v分成两部分[u,p]，u代表信息比特，p代表生成的校验比特。考虑G=[I,P]，

TTT?T?TT由GH?0，可以得到IH1?IH2?0，所以P?H1H2，根据H2的特性可知，H2可

以由一个特征多项式为f?D??1/?1?D?的递归卷积码来表示。 此时编码结构如下图所示：

图3

这种编码算法的缺点在于，H2矩阵存在列重为1的列，这对迭代译码过程不利，会产 生误码平台，可以通过改变这一列重的方法来优化，降低误码平台。

二、编码部分

LDPC 码有很多种译码方法，本质上大都是基于Tanner 图的消息迭代译码算法。根据