3.5 LDPC（低密度奇偶校验码）原理
3.5.1 引言
中国地面数字电视传输系统标准和中国移动多媒体广播标准中的信道编码技术，都采用LDPC（低密度奇偶校验码）。低密度奇偶校验码（Low Density Parity Check，LDPC）码是基于随机编码与迭代译码的新一代高效信道编码技术。这种编码方法的理论最早是在1962年由Gallager提出的，但是，由于当时的计算机计算能力太低，无法仿真出较好的性能，而未受到重视。直到Turbo码被发现后，Mackay和Neal又重新挖掘LDPC，使之成为信道编码领域的热门研究课题。
事实证明，LDPC的性能优于Turbo码，逼近香农限（为给定带宽和给定噪声条件的信道内，无差错数据传输的最高速度而设定的绝对极限值），译码复杂度低于Turbo码，适合于硬件实现。
3.5.2 奇偶校验码
一个二进制码字，如果它的码元有奇数个“1”，就称为具有奇性。例如，码字“10110101”有5个“1”，因此，这个码字具有奇性。同样，偶性码字具有偶数个“1”。
奇偶校验可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。
例如，当有效信息为8位时，奇偶校验码如表3-5-1所示。
表3-5-1 有效信息与奇偶校验码
3.5.3 线性分组码
LDPC码是一种新的线性分组码，因此，有必要说明线性分组码的一些基本概念、码字的生成与译码方法。
二进制分组码是将信息比特序列分为m组，每组k比特，加入r位校验比特，构成包含n=k+r位的码字c。每个码字的r位校验比特只与本码字的k个信息位有关，而与其他码字的信息位无关。
分组码通常表示为（n，k）码，（n-k）=r，即为检验位数。显而易见，分组码的编码率为R=k/n，R越大，表明分组的传输信息的有效性越高。一个码字中非0 码元的个数称为汉明重量，而两个码字之间对应位取值不同的个数称为它们之间的汉明距离。
所谓线性分组码，是指码组的信息位与检验位之间的关系可以用一组代数线性方程来表示。如果信息位在编码保持后不变，则称为系统码。（n，k）系统分组码的结构如图3-5-1所示。
图3-5-1（n，k）系统分组码的结构
设线性分组码为（7，4），4个信息位分别为a6、a5、a4、a3，而3个校验位分别为a2、a1、a0 按下列关系得到：
为方便起见，在以下的表达式中，用+表示⊕，将式（3-5-1）改写为
将式（3-5-2）写成矩阵的形式，即
或
式（3-5-3）和式（3-5-4）用符号可表示为
式中H称为分组码的校验矩阵或监督矩阵，即
C=[a6 a5 a4 a3 a2 a1 a0] 0=[000]
HT是H的转置，对于码字C来说，有下列恒定关系
由式（3-5-6）可以看出，只要给定校验矩阵H，编码时校验位与信息位的关系就完全确定。H矩阵的行数就是校验关系式的数目（即校验位的数目，本例中为r=n-k=7-4=3），H矩阵每一行中“1”的位置表示相应码元之间存在的关系，例如第三行1011001，表示校验位a0是由信息位a6、a4和a3之和决定的。
我们可以将H矩阵分为两个部分，即
式中P为r×k阶矩阵（本例为3×4），Ir为r×r阶方阵（本例为3 ×3）。与将式（3-5-2）改写为式（3-5-3）相同的方法，将式（3-5-1）改写为
或者
式（3-5-10）中的Q矩阵为k×r阶，它正好是P矩阵的转置，即有以下关系
式（3-5-10）表明，校验位可以由信息位的行矩阵乘以Q矩阵而得到。
如果在Q矩阵的左边添加一个k×k阶单位方阵Ik，构成新的矩阵G，G称为生成矩阵，即
整个编码码组可以通过信息位与G矩阵相乘而得到
根据以上的分析，可以用以下公式表示校验矩阵与生成矩阵之间的联系，即
如果码组在传输过程中产生差错，例如接收到的码组为C'，它与发射码组C之间的差为E，C'-C=E（模2），或C'=C+E
接收端译码时，可将C'取代C代如式（3-5-5）中，如E=0，则下式仍成立，即
若E≠0，则上式不一定成立。当错码位数较多时，C'也许变为另一个许用码组，仍能使式（3-5-18）成立，这样的错码就不可检测，已超过了这种编码的检错能力。在尚未超出检错能力的情况下，C'·HT=（C+E）·HT=C·HT+E·HT=S，由于C·HT=0，因此
S称为接收码字C'的校正子（伴随式）。可以看出，S只与E有关，有确定的线性关系，而与C无关。若S与E之间一一对应，那么S就能代表错码的位置。
例如，发射码字为 C=[1110100]，接收码字为 C'=[1010100]，错误矩阵为 E=[0100000]，E中的“1”表示在该位发生错误，这里为第2位。由式（3-5-19）可得
S就是H矩阵的第2列。即E只有一位（第i位）不为0，则S就是H矩阵的第i列。反过来说，如果计算出的S是H矩阵的第i列，就表明接收到的信息的第i位发生错误。
3.5.4 LDPC码
LDPC码是一种特殊的线性分组码，可以用校验矩阵来定义。LDPC码的校验矩阵H是“稀疏”矩阵，也就是说矩阵中的绝大多数元素是0，只有很少一部分元素是1。根据稀疏矩阵的特点，可以将LDPC码分为规则LDPC码（H矩阵中行和列中“1”的密度固定不变）与非规则LDPC码（H矩阵中行和列中“1”的个数不固定）。
（1）校验矩阵H
在规则LDPC码的H矩阵中，每行中“1”的个数为tr，而每列中“1”的个数为tc，“1”的分布是随机的，但要保证矩阵的各行是线性独立的，且任何两列中同为“1”的行数不会超过2（最好不超过1）。（n-k）线性分组码的H矩阵有（n-k）行和n列。设规则LDPC码稀疏矩阵H中“1”的密度为ρ，显然，一行中“1”的个数应为tr=nρ（称为行重），一列中“1”的个数应为tc=（n-k）ρ（称为列重）。通常，LDPC码记为（n，t c，t r），由于t c/t r=（n-k）ρ/nρ=1-k/n，因此，码率R可表示为
举例：一个（16，2，4）LDPC码的H矩阵可以表示为
（2）校验矩阵H的设计
LDPC码必须先设计校验矩阵H，然后，由H得到相应的生成矩阵G。对于规则LDPC码的设计来说，先确定参数tc和tr，然后，根据码长n，按照式（3-5-22）来确定H矩阵的列数（n-k），生成一个n×（n-k）的全0矩阵，再随机地将每行的tr个“0”换成“1”，每列的tc个“0”换成“1”。
（3）LDPC码的编码
先将矩阵H变为定义的系统形式，再根据线性分组码系统形式的校验矩阵H与生成矩阵G之间的关系，得到相应的生成矩阵G。
由式（3-515）可以看出，通过系数矩阵Q，便可以求出G，因此，首要的是通过非系统矩阵H求出Q矩阵。
将非系统形式的（n-k）×n校验矩阵表示为分块矩阵，即
H=[BT︙AT]（3-5-24）式中AT是（n-k）×（n-k）方阵，BT是（n-k）×k矩阵，AT和BT是矩阵A与矩阵B的转置。
如果信息矢量用m表示，校验矢量用b表示，可以将编码矢量C写成分块行矢量（其最高有效位为m的最高有效位，最低有效位为b的最低有效位），即
根据式（3-5-7）和式（3-5-25），得到
即
根据式（3-5-10），可以看出
将式（3-5-28）代入式（3-5-27）中，可解得
式中A-1为A的逆矩阵。
根据式（3-5-12），可求出系统形式的生成矩阵G为
下面以（10，3，5）LDPC码为例，说明编码过程。
设（10，3，5）LDPC码的H矩阵为
将非系统的（n-k）×n（这里为6×10）校验矩阵H分为两个部分，即
式中AT是（n-k）×（n-k）（本例为6×6）方阵，BT为（n-k）×k（本例为6×4）矩阵。右半部分为AT，左半部分为BT，因此有
根据A求出A的逆矩阵A-1为
由矩阵B和矩阵A的逆矩阵A-1得到矩阵Q为
由Q得到生成矩阵G为
当信息矢量m给定时，便可以根据G编码，编码矢量为C=mG。
（4）LDPC码的译码
由于LDPC码的码长n很大，不能使用一般线性分组码的译码方法，而是采用译码信息的传递与迭代过程，找出最大可能的码矢量
，使其满足 
。