LDPC编码原理 下载本文

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 码时,同时考虑编码的有效性,使H矩阵具有半随机矩阵的格式。 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 ,当其为I阵时,又可以进一步 降低编码的复杂度,此时编码步骤可以参考如下:

步骤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 图的消息迭代译码算法。根据