英语原文共 83 页，剩余内容已隐藏，支付完成后下载完整资料

---

1.1引言

低密度奇偶校验（LDPC）码是一种前向纠错码，首先在1962年由麻省理工学院的Gallager在他的博士论文中提出。当时，在那个真空管刚刚被第一个晶体管所替代的时代，计算能力的限制使他们难以置信的潜力仍然未被发现，自此以后35年里LDPC码基本上被忽视了。同时，在前向纠错码领域，高度结构化代数分组码和卷积码独领风骚。尽管这些代码在实用性方面很成功，但是，他们的性能远远低于香农在他1948年具有开创性的论文中所提出的达极限。20世纪80年代以后，尽管花费了几十年的努力，研究人员还是基本上放弃去跨越理论与实际的这条鸿沟。

在1993年，由Berrou, Glavieux 和 Thitimajshima提出的turbo码使得相对停滞的编码领域重新焕发生机，其中成功纠错码的所有关键要素被取代：Turbo码很少涉及代数，采用迭代、分布式算法，关注与平均（而不是最坏）的性能，并从信道中提取的依靠软件（或概率）的信息。通过使用解码器，一夜之间，与香农极限之间的巨大鸿沟几乎完全消失。当研究人员在上世纪90年代努力思考为什么Turbo码性能这么好时，两名研究人员,McKay和Neal介绍了一种新的分组码，这种码拥有许多与Turbo码相同的特征。很快研究人员就认识到，这些块码实际上是早些年由Gallager 提出的LDPC码的重新发现。事实上，这种用于解turbo码的算法随后被证明是一种特殊的LDPC码解码算法，这种算法Gallager 在许多年前就已经提出了。

包括Luby, Mitzenmacher, Shokrollahi, Spielman, Richardson and Ur-banke在内的许多研究人员对LDPC码作出的新的概括产生了新的不规则LDPC码，这种码轻易的超越了最好的Turbo码，并且拥有相当的实践优点，对于理论结果来说，也有着更整洁的设置。今天，对于LDPC码的设计技术已经使得编码的构建十分逼近香农极限了。

仅仅在十多年前，编码领域能有如此快速的进步是完全无法想象的。除了理论方面对LDPC码的继续研究，这种编码已经被采纳为基于卫星的数字视频广播和长距离光通信标准编码，并且很有可能被采纳为IEEE无线局域网标准编码，LDPC编码正被考虑是否用于长期进步的第三代移动电话。

1.2使用奇偶校验的纠错方法

这里我们只考虑二进制消息，所以传输的消息由0和1的字符串组成。前向差错控制编码的基本思想是故意地引进额外检查位形式式的冗余项来增加这些消息位从而为消息构建出码字。这些检查位通过这种方式增加使得码字之间有效的区别开来，所以传送的消息能够被译码器正确的翻译出来，即使在信道传输过程中码字的某些位损坏了，译码器也能准确的翻译出码字的意义。

最简单的编码方案可能就是单奇偶校验码（SPC)了。SPC是将一个额外的位加到二进制消息中，增加的值依赖于消息的各个位。在一种奇偶校验码中，加入每个消息中的额外位确保每个码字中有奇数个“1”或“0”。

例子1.1______________________________________________________________

消息S的7位的ASCII码串位1010011，增加一位奇偶校验位使得码字有8位。消息S的码字串有4个“1”，所以奇偶校验位的值为“0”，S的码字为10100110.

_____________________________________________________________________

更加正式的说明，对于7位的ASII码加奇偶校验码来说，我们定义一个如下结构的码字c：

c=[c1,c2,c3,c4,c5,c6,c7,c8],

每一位ci要么为0要么为1，并且每一个码字满足约束条件:

c1oplus;c2oplus;c3oplus;c4oplus;c5oplus;c6oplus;c7oplus;c= 0. （1.1）

方程（1.1）称为奇偶校验方程，方程中的符号oplus;代表模2加法。

例子1.2______________________________________________________________

在例子1.1中，一个7位的ASCII信息通过单个奇偶校验码来编码。码字结果通过噪声信道传输，然后字符串y=[10010010]被接收到。为了检查y是否是一个有效的码字，我们通过例子1.1来测试y。

y1oplus;y2oplus;y3oplus;y4oplus;y5oplus;y6oplus;y7oplus;y8=1oplus;0oplus;0oplus;1oplus;0oplus;0 oplus;1oplus;0=1.

既然结果为1，所以y不满足奇偶校验方程，也就是说y是一个无效的码字，我们已经发现在传输过程中至少又一次错误产生。

_____________________________________________________________________

尽管由于信道噪声引起的单个位的变化能够通过奇偶校验码被我们轻易发现，这种码不能够充分的表明哪一位或者哪几位发生了变化。甚至，某些位的变化也有可能产生满足限制方程的码字，所以这种简单的编码不能够有效的发现码字传输中发生的错误。想要检测出更多的位有没有发生错误就必须增加更多奇偶校验位的冗余并且使用更加复杂的代码，如多重奇偶校验方程以及每一个码字必须满足所有方程。

例子1.3______________________________________________________________

一个码字c包含6个位

c=[c1,c2,c3,c4,c5,c6],

并且码字c必须满足以下3个奇偶校验方程：

c1oplus;c2oplus;c4=0

c2oplus;c3oplus;c5=0

c1oplus;c2oplus;c3oplus;c6=0 (1.2)

_____________________________________________________________________

码字的限制方程通常写成矩阵形式，所以限制方程（1.2）可以表示成

（1.3）

矩阵H称为奇偶校验矩阵。H矩阵的每一行分别对应每个奇偶校验方程并且H矩阵的每一列分别对应码字的每一位。因此对于一个有m个奇偶校验方程和n个位的二进制码字来说，奇偶校验矩阵是m*n的二进制矩阵。字符串y=[c1,c2,c3,c4,c5,c6]的矩阵表示对于编码来说是一个有效的码字，通过奇偶校验矩阵H如果或者说仅仅当它满足矩阵方程：

Hy^T=0. (1.4)

1.2.1编码

为了区分例子1.3中码字的消息位和奇偶校验位，我们重写码的奇偶校验方程以便每一个方程分别限制一个码字位。

例1.4________________________________________________________________

例子1.3的码字限制可以被重写为：

c4=c1oplus;c2

c5=c2oplus;c3 （1.5）

c6=c1oplus;c2oplus;c3

_____________________________________________________________________

码字位c1,c2和c3包含3个位信息，尽管码字位c4，c5和c6包含三个奇偶校验位。这种码字限制方程表明了如何去编码信息。

例子1.5______________________________________________________________

消息110如果使用例子1.5的限制方程，就会产生奇偶校验位

c4=1oplus;1=0，

c5=1oplus;0=1，

c6=1oplus;1oplus;0=0，

所以编写这个消息的码字c=[1 1 0 0 1 0].

_____________________________________________________________________

这些限制方程可以再次表示成矩阵形式：

（1.6）

在这里矩阵G被称为码的生成矩阵。这个消息的位通常被记为u=[u1,u2,u3,u4,...uk],在这里矢量u有k个消息位。因此对应这个二进制消息u=[u1,u2,u3]的码字可以通过方程1.7求得：

c=u*G （1.7）

对于一个k位消息位，码字长度为n的二进制码，其生成矩阵G是k*n的二进制矩阵。k/n的比率叫做代码速率。

一个有k位消息位的码包含有2^k个码字。这些码字这些码字是所有可能的2^n个长度为n的二进制向量的子集。

例1.6________________________________________________________________

将2^3=8个不同的消息c1，c2，c3=000，001,hellip;hellip;，111带入等式1.7，对于例子1.3的码来说可以得到以下码字：

（1.8）

这个代码叫做系统因为码字的前k位包含信息位。对于系统码来说，其生成矩阵是k*k形式的，记作Ik，（矩阵Ik是一个2进制方阵，方阵的左上到右下的对角线上的数字全为1，其余位子全为0）。

一个码带奇偶校验矩阵H的生成矩阵可以通过对H矩阵使用 Gauss-Jordan消元法求得：

H=[A,In-k] （1.9）

这里A是一个（n-k）*k的二进制矩阵，而In-k是

（n-k）*（n-k）阶矩阵，且对角为1，其它位为0的方阵。所以生成矩阵G：

G=[I,A] （1.10）

矩阵G的行向量和矩阵H正交。因此如果矩阵G是一个码的带奇偶校验矩阵H的生成矩阵的话，那么应该有：

G*H^T=0

在总结这部分之前，我们注意到一个码块能被一个或者多个奇偶校验方程描述。对一个带有等式（1.4）码来说，一组约束方程是足够有效的。对于低密度奇偶校验码来说，奇偶校验矩阵的选择特别的重要。

例子1.7______________________________________________________________

例子1.3中的码C可以由四个奇偶校验等式描述：

（1.11）

_______________________________________________________________________________

而例子1.7中额外的限制方程其实就是第一和第三个奇偶校验等式的线性组合，所以新的方程等式线性相关于已有的奇偶校验方程。一般来说，一个码的奇偶校验方程可以由任意个，但是，其中只有n-k个方程式线性无关的，其中k是每个码字中的消息位的位数。矩阵符号n-k等于矩阵H的阶数

n-k=rank2（H） （1.12）

这里rank2（H）是与GF（2）线性相关的H矩阵的行数。

1.2.2 误差检测与校正

假设一个码字已被送到一个二进制对称信道但是码字的一个或者多个位发生了反转。这部分以及之后介绍的方法将发现所有反转位，如果可能的话，甚至可以更正它们。

首先，我们知道码中的每一个码字一定是满足

等式（1.4）的，所以不满足等式（1.4）的任何码字一定存在着误码位。

例子1.8________________________________________

例子1.3中的码的码字c=[1 0 1 1 1 0]通过一个二进制对称信道传输并通过二进制数字字串y=[1 0 1 0 1 0]接收。代入方程（1.4）得到：

（1.13）

结果是非零的，所以字符串y不是这个码一个码字。我们因此断定在信息传输过程中一定发生了位反转错误。

_______________________________________________________________________________

矢量s=H*y^T,被称为y的校验子。这个校验矢量可以表y不能满足哪个奇偶校验方程。

例子1.9________________________________________________________________________

在例子1.8中的等式1.13的结果表明，字符串y不满足矩阵H的第一个奇偶校验方程。由于这个奇偶校验方程包含第一，第二和第四个码字位，所以我们可以断定在信道传输过程中，这三个位中至少有一位发生了反转。

___________________________________________________________________________

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[138679]，资料为PDF文档或Word文档，PDF文档可免费转换为Word