低密度校验码（LDPC）
2.1 LDPC的产生与发展
| 2.2 LDPC 码的基本原理 |
2.2.1 Gallager 码
LDPC 码是一种分组校验码，由 Gallager 于 1963 年提出 [1-2]。在其博士论 文 [2] 中，除了对性能界的详尽分析之外，Gallager 还建议了两种解码方法：一 种是简单的代数法解码；另一种是基于概率论的解码。
论文 [1-2] 所想表达的一个思想是，尽管 LDPC 的“低重”特性从码距的角 度不具有很强的优势，但稀疏阵结构可以降低解码的计算量，在性能与工程实 现复杂度之间提供一个折中。在之后的近 40 多年，LDPC 经历了一段相对沉寂 的时期。部分的原因是基于概率论解码的复杂度要比代数法解码高很多，即使 采用稀疏权重的设计，对于当时的硬件，其成本还是难以接受。
另一个原因是对概率论解码的认识本身，包括其性能潜力。传统信道编码 理论评判一个码的性能大多是基于码距分析的，通过最小码距及码距的分布， 得到性能界的解析表达式，从而比较“严格”地推断出该信道编码的纠错能力。 这类方法对较短码长且基于代数法解码的分组码十分有效，但当码长较长且采 用概率论的解码，就显得不那么有力。LDPC 码的优势在于长码和运用概率方 法解码。因此在很长的一段时间中，它的潜力并没有被学术界和工业界所广泛认识。
1993 年 Turbo 码 [7] 的出现掀起了业界对概率法解码的热潮。所谓概率法 解码，即采用软的信息比特，而不是代数式译码中的“对”或“错”的硬判决。“软”体现在每个比特位的置信度是一个概率分布，即一个实数，相当于“对” 与“错”之间渐变的“灰度”。概率法解码一般需要与迭代译码相结合，才会 体现其优势。仿照 Turbo 译码原理，大家又重新发现最初 Gallager 所提的 LDPC 的概率法解码就是采用迭代译码的。而且 Turbo 和 LDPC 都可以用因子 图（Factor Graph）[16] 的分析手段统一起来，所用的解码方法也可以归类为人 工智能当中的置信传播（Belief Propagation）算法 [17] 或者信息传递（Message Passing）[18]。
经典的 LDPC 编码器可以按如下描述。一个长度为 k 的二元的信息比特序 列 u，引入 m 个校验比特后，生成 n 个编码比特的序列 t，此 时码率为 k/n。因 为是线性码，码字 t 可以用 u 乘以一个生成矩阵 GT 来表示：
生成矩阵 GT 包含两部分：
如果采用硬判决的代数法译码，相应的校验矩阵可以写成：
当码字在传输中没有错误时，奇偶校验通过，即，
其中，第一个值为t的估值。需要指出的是，LDPC校验矩阵有时不一定写成右边为单位矩阵的形式，尤其当采用概率译码（如软信息的置信度传播）方式。此时需要对校验矩阵做一些线性代数的变换，求出生成矩阵以便编码。
LDPC的特点在于行数为m，列数为n的校验矩阵A具有稀疏性，即多数的元素为0，矩阵A的产生方法有随机生成、结构化设计或者穷举寻找，详细请见后述（第2.3节和第2.5.3节）。
一个LDPC编码后的码块通过AWGN信道的框图如图2-2所示：
在图2-2中，信息比特流u先进行编码。编码后的比特流t经过AWGN信道，输出为观测到的序列 y。LDPC 解码器进行变量节点和校验节点之间的反 复迭代交换软信息，若干次迭代后，解码器输出硬判决结果，即解码后的信息 比特序列u的估计值。
LDPC 校验矩阵 A 的稀疏性的必要性在于：
- LDPC 采用的是“加和乘”（Sum-product）的译码算法。该算法只有当二 分图（Bipartite）中没有环（Cycle-free），或者没有短环（Short Cycle）时才能 达到较好的性能。而稀疏性可以大大降低短环出现的可能性；
- 稀疏性意味着变量节点和校验节点之间的连接密度不高，这样在做“加和 乘”的译码时可以减少累加和相乘的运算，降低译码的复杂度；
- 当校验矩阵 A 是稀疏阵时，其相应的生成矩阵 GT 通常不具有稀疏性，这说明产生的编码序列t的编码权重有可能较高，从而具有较好的编码矩阵。
2.2.2 规则 LDPC 和非规则 LDPC
LDPC编码可以用二分图的方法表述，根据图2-3所示的LDPC二分图（Bipartite）。规则LDPC，每个变量节点（Yi,i=1,2,3,…,9，为列的编号；有 9 个输入变量节点）连接q=2个校验节点（Ai,i=1,2,3,…,6；行的编号；有 6 行 参与校验；q 为列重—这一列中“1”的个数），每个检验节点连接r=3个变量节点（r 为行重，即等于这一行中“1”的个数）。
从图 2-3 中可以看出，节点分成两大类型：变量节点（Variable Nodes）和校验节点（Check Nodes）。同一类型的节点不能直接彼此相连，不能直接互 通信息，但可以通过另一个类型的节点传递信息。这种互联结构体现于网状的 连线，也称“边”（Edge），可以完全由校验矩阵决定。
LDPC 可以分为规则（Regular）和非规则（Irregular）[8] 两种。规则的 LDPC 是指同一种类型的节点具有相同的自由度。这里的自由度是与各节点类 型的边数目，即对于 LDPC 码来说，相当于校验矩阵中每行或者每列上的非零 元素数目。图 2-3 就是一个规则 LDPC 的例子，其中每个校验节点与 3 个变量节 点相连，而每个变量节点与 2 个校验节点相连。对应到校验矩阵，即每行有 3 个非 零元素，dc = 3。每列有 2 个非零元素，dv = 2。与 6×9 的整个校验矩阵来看，还 是比较“稀疏”的。当 LDPC 码非常大时，其稀疏性就更为明显。
非规则 LDPC 的变量节点或者校验节点的自由度可以不一样，只要服从某 种分布即可。用一对参数（λ, ρ）式子表示非规则 LDPC，其中
代表了变量节点的自由度分布。而
代表了校验节点的自由度分布。更精确的讲，系数λi和ρi分别表示自由度为i的从变量节点和校验节点发出的边数所占的比例。上面的两个公式也可以用来描述规则的LDPC，例如，图2-3的LDPC就可以写成λ（x）:=x^1和ρ(x):=x^2。
相比规则LDPC，非规则LDPC有更大的灵活性和优化空间。无论从理论分析还是仿真验证，非规则LDPC的性能更优。因此在工程上所考虑的LDPC都是非规则的LDPC。
2.2.3 置信度传播的基本原理及其应用
置信度传播（Belief Propagation）也被称为信息传送（Message Passing），是概率论中的一种基本算法，guangfanyingyongza广泛应用在数字通信、人工智能、计算机科学、运筹管理等领域。
我们把图2-4一般化成一个因子图（Factor Graph），由变量节点（Variable Notes）和因子节点（Factor Notes）组成。
一般地置信度传播或者信息传送算法的本质就是根据因子图中变量节点和因子节点的连接关系，计算变量节点取值的边缘概率分布。这里有一个基本假设，即变量节点之间、因子节点之间都是不相关的，它们的联合概率分布可 以表示成边缘概率的乘积。边缘概率的求解可以用树状结构图表示。因子图展 开成树状图之后（这里假设不存在环状结构），可以更直观地看出迭代译码的过程，如图 2-5 所示。
从因子节点a到变量节点i的信息mga i(x； ) 可以解释成因子节点a有多大的可能性认为节点i会处于状态x；c而对于变量节点i，它处于状态x，的联合置信度正比于与它相连的因子节点认为变量节点会处于状态x；的概率的乘积，即
对于任意一个因子节点A，它的置信度等价于与它相连的所有变量节点的联合置信度。用式(2-12)表示
注意这里的L是个集合的概念。那么根据式(2-11)，变量节点集合L中的每一个节点的置信度都是由正比于与它相连的因子节点认为变量节点会处于状态x，的概率的乘积，因此这个联合概率可以写成：
一个节点上的置信度，也就是边缘概率，就等于除了它自己，对所有相连的因子节点的联合置信度求和，即：
式(2-15)可以写成迭代形式。对于能够展成树形图的结构，而且不存在局部的环状结构，可以证明：置信度传播算法能够在有限的迭代次数内(两倍的树形结构的最大深度)收敛到边缘概率。
在实际的因子图展开当中， 局部可能会出现迂回环状结构(LoopyGraph) ， 如图2-6所示。当有环结构存在时， 置信度传播算法有可能不收敛，或者即使收敛，也不一定收敛到边缘概率分布。解决环结构不收敛的方法有好几种，对环结构的研究具有更多的理论意义，对工程设计的指导有限，这里不再赘述。
在信道解码方面，置信度传播被用在多种编码当中。这里我们介绍在 LDPC 中的应用。LDPC 校验矩阵的每一行代表一个奇偶校验，传统的代数译 码只考察相对应的比特节点上的值相加之和是否为 0，如果是，奇偶校验通过； 反之，校验不通过。在概率译码当中，校验节点，也就是一般的因子图中的因 子节点，需要计算的是该校验通过的概率。而这个计算是假定某一个相连的变 量比特是 1（或者 0），并且其他变量节点的值符合某种先验的概率分布。变量 节点需要计算的是一个比特是 1（或者 0）的概率，这个计算是基于所有相连的校验节点上的校验通过概率。
用 rij 代表由校验节点确定的信息概率，更具体的，用 rij0 代表当信息比特 ti 为 0 时，校验节点j能够校验通过的概率。同理，用rij1 代表当信息比特ti 为 1 时， 校验节点 j 能够校验通过的概率。那么，根据置信度传播算法的原理，这两个 信息概率可以用式（2-17）来计算：
在式(2-17) 中， 表达式ie row[j] /(表示在第j行的所有为1的比特索引，除去当前的比特索引i。概率qy由变量节点来计算。q，表示在给定所有的校验节点的信息(除去校验节点j)的条件下，t；=0的概率。同理，q；表示在给定所有的校验节点的信息(除去校验节点j)的条件下，t；=1的概率。根据置信度传播的算法原理，概率q；可以表达成：
在式(2-18) 中， j ecol[i] /(j) 表示在第i列的所有为1的校验节点索引，除去当前的校验节点索引j。系数aiy是用来归一化的， 以保证q； +q； =1。式子中的p?和pi是相对于当前一轮迭代译码的第i个信息比特的先验概率，由以前的迭代过程得到。外部信息(Extrinsic Information) e； 和e， 的计算公式为：
