LDPC的介绍

LDPC的介绍

LDPC（Low Density Parity Check Codes），低密度奇偶校验码，属于信道编码，是线性分组码的一种。假设码长为n的分组码，信息位为k，校验位码长为r=n-k。其中校验位的产生只与原始长度为k的序列有关。一般来说，如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求：

1、校验矩阵

介绍

假设c是发送序列，校验矩阵为

可以得到：

特点：①H矩阵的行数必须为m行，并且行与行之间必须线性无关。
②H矩阵的各行可以分别对应表示一个校验节点的一次方程式。
③如果c是序列里的某个单元，则它必须符合由校验矩阵H所定义的m个一次方程式。

稀疏矩阵

假设H的每一行1的元素的总和为R，每一列1元素的总和为C，则相较于H的行列大小，R和C的数值都很小，所以是稀疏矩阵。并且校验矩阵的任意两行或者两列不能出现两个或者两个以上相同位置的1，也即不能由4个1构成一个矩形回路。

行重：H中每一行1的个数。
列重：H中每一列1的个数。

其中1元素在总码长的比重称之为此校验矩阵的密度。在一般情况下，每一行中1元素的个数与总码长个数之比的数值是与每一列中1元素的个数与总码长的个数之比是一致的。在奇偶校验矩阵的密度可以用来定义LDPC码的稀疏性。

2、生成矩阵

介绍

设二元LDPC码(n,k)，生成矩阵为G，信息位表示为：

则，可以利用生成矩阵来生成整个码字，生成的码字为：

生成举证特点：
①G的每一行也线性无关。
②G的每一行都是代表LDPC的一个码字，且各码字间相互独立。因此G可以有多种表示，但是这些矩阵都必须生成同一个(n,k)。
③因为生成矩阵的k行表示的是k个线性无关的向量，所以校验矩阵H和生成矩阵G在多维向量中是相互垂直的，即：

校验矩阵与生成矩阵的关系

对于一个校验矩阵维度是m*n的LDPC码来说，它的校验矩阵H可由高斯消元法将其变为：

通过对G做以上变换，可得到G的系统形式：

由该形式生成的码字，成为系统码。

3、Tanner图

Tanner图是一种双向二分图，可以用来表示二元LDPC码，可以直观的表示二元LDPC码置信度传播译码算法的信息在节点之间传递的过程。
Tanner图的校验节点个数=H的行数，变量节点的个数=H的列数。如下面的例子所示，每一行有4个1，对于第一行（即第一个校验节点），对应元素“1”所在H的列的位置，即对应的变量节点的位置，分别与每一个变量节点相连，以此类推。


由于校验矩阵H的稀疏性以及构造时所使用的不同规则，使得不同的LDPC码的编码二分图具有不同的闭合环路分布，这是影响译码性能的重要因素。为了保证LDPC码的Tanner图上不存在长度为4的闭合环路，我们通常要求H的行与行以及列与列之间的交叠部分重量不超过1。满足这个条件最低就是6环，没有4环。

判断LDPC校验矩阵的围长是否存在4环，一般的方法则是将校验矩阵与校验矩阵的转置矩阵相乘，如果结果是一个单位阵，即，则没有4环出现。如果不是单位阵，则出现了4环，此时构造的LDPC码的校验矩阵不成功，需要重新构造。

迭代译码的信息量是根据Tanner图来传递的，其信息量的传递方式是从变量节点传递给校验节点，然后校验节点信息量再传递给变量节点，所以传递路径越大越好。路径的大小一般用围长来定义：以一个变量节点作为起点，经过若干个不同的变量节点之后，又回到了原来的变量节点，此时经过的Tanner图边的个数则是围长的值。一般LDPC码的译码围长越大，译码效果越好。

度

对于LDPC码的每个变量节点来说，当它参与的校验式材多，即度Y 越大，则它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。对于H的每个校验节点来说，当它涉及的变量节点越少，即度数P越小，则它可以更准确的估计变量节点的状态。这种状况对于正则 LDPC来说是一对不可克服的矛盾，于是就引入了非正则LDPC码的概念。

在非正则LDPC码的编码二分图中，两个集合内部的节点度数不再保持相同，即每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保持均匀，而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些参与较多校验式的变量节点迅速得到它们的正确译码信息，这样他们就可以给相邻的校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次数少的变量节点更多的信息。整个译码过程呈现一种波状效应。使得非正则LDPC码获得比正则LDPC更好的译码性能。

每一个校验节点或者变量节点上的所连接 的直线的总个数称之为此节点的度，等于此行或者此列上“1”的总个数。对于规则LDPC码的所有校验节点的度与变量节点的度是相同的。对于非正则LDPC码，每行每列的度数都会变化，节点的度数分布可用如下多项式表示：


当度数分布设计完成之后就确定了对应的码率和校验方程的个数，一组度数分布可以构造出一组校验矩阵，通常根据需要从中选择一个应用于当前场景的LDPC码字的生成。

4、LDPC码的分类

按照LDPC码H矩阵中的元素如何取值可分为二进制码（二元LDPC码）和高阶有限域GF(q)码（非二元LDPC码）。

对于二元LDPC码，按照H举证中每行或每列1的个数是否一样，可分为规则码和不规则码。

按照H矩阵中非0元素位置如何构造可分为随机码和结构型（代数和组合型）。

LDPC码的另一种的分类方式也可以分为QC-LDPC码与非QC-LDPC码。