偶校验矩阵和低密度奇偶校验码的构造方法

摘要 - 低密度奇偶校验（LDPC）码是具有稀疏奇偶校验矩阵的线性分组码。 在本文中，给出了用于生成LDPC码的一些构造方法的简要描述。 这些方法通常分为两类：随机和分析。 随机构造的代码包括来自Gallager和Mackay的代码。 所描述的分析构造方法是来自有限几何形状的代码。 一种类型是根据Gallager的原始处方随机构建的。 另一个是从欧几里德和投影几何分析建立的。 可以使用基于似然差的解码算法来检查它们的性能。

1.引言

LDPC码概述

在信息论中，Shannon的信道编码定理被认为是刺激了错误控制码的发展。 它表明，所有数据速率r_b小于信道容量C的，都可以实现任意小的误差概率P_e，其中C由Shannon-Hartley公式[1]给出：
ܥ$C = B log_2 [S/N] \quad (Bits per second) \tag{1.1}$C=Blog2​[S/N](Bitspersecond)(1.1)
这里，B是以Hz为单位的信道带宽，S / N是信噪比（SNR）。 SNR与“比特能量与单侧噪声功率谱密度比”有关
$\frac{S}{N}= {r_bE_b\over BN_0}= {r_b\over B}×{E_b\over N_0}\tag{1.2}$NS​=BN0​rb​Eb​​=Brb​​×N0​Eb​​(1.2)
使用公式（1.2），公式（1.1）可以写成：
$\frac{C}{B}= log_2(1+(η_{max}{E_b\over N_0}))\tag{1.3}$BC​=log2​(1+(ηmax​N0​Eb​​))(1.3)
或者
$\frac{E_b}{N_0}= \frac{2^{η_{max}}-1}{η_{max}}\tag{1.4}$N0​Eb​​=ηmax​2ηmax​−1​(1.4)
等式（1.4）被称为香农极限。 它提供所需的E_b / N₀，以接近信道容量的速率传输数据。 该限制始终用作评估编码调制方案的基准。 据报道，Turbo码和LDPC码的性能非常接近香农极限[2]
LDPC码，也称为Gallager码，是由Gallager在60年代早期设计的[3]。 作为一类线性分组码，它们通过稀疏二进制奇偶校验矩阵来区分。在每个矩阵中，每一行有固定的（j）个1，每列也有固定（k）个1。 然而，当时，计算能力还不足以显示它们的有效性，因此LDPC代码直到最近才被遗忘[2]。Mackay和Neal被称为“重新发现”Gallager代码，他们指出了使用基于和积算法的解码算法的代码的出色功能[4]
从Gallager的原始处方中，Luby等人通过引入不规则代码标志了LDPC码的重要进展[5]。 LDPC码的另一个进步是由Davey和Mackay在GF（q）（q> 2）上引入不规则码。 在[6]中，这类LDPC码显示出比GF（2）中的代码具有显着改进的性能。

2. LDPC代码的构建

在这一部分中，我们描述了一些常规和不规则LDPC码的结构。 用于构造LDPC码的奇偶校验矩阵的方法分为两大类：随机和分析方法。但是，根据Johnson和Weller [10]，随机构造方法仍然占主导地位，因为分析创建的LDPC代码只占很小的一部分。 已经表明，如果Tanner图没有周期，迭代和积解码算法可以收敛于最优解[8]。 较短的周期将使算法恶化。
下面介绍了处理LDPC码构造的一些有用概念
Tanner图：Tanner图用于表示线性分组码的码字比特和奇偶校验比特之间的关系。 Tanner图已被推广成因子图[7]。
循环：Tanner图中的循环是一系列连接的码字节点和奇偶校验节点，它们在同一节点处开始和结束，并且序列中不会出现多次其他节点。
长度：循环的长度是循环中的边数。
周长：Tanner图的周长是其最短周期的长度。
度：Tanner图中节点的度数是连接到它的边数。
图1和2分别示出了长度为4和长度为6的两个周期，以及它们对应的奇偶校验矩阵

码字顶点和奇偶校验顶点的作用在形成周期中是相等的。 因此，使用I或其转置，I^T作为奇偶校验矩阵将创建相同的循环集。
特别是，对于长度为4的周期情况，下面的三个语句对于LDPC代码是等效的：
Tanner图中没有长度为4的循环。
任意两行之间的重叠1的数量小于2.
任意两列之间的重叠1的数量小于2.
这些备注将用于简化与LDPC码的周期长度和周长相关的证明，以及 在检查模拟程序中的重叠时也是如此。

3.随机构造的代码

A. Gallager的处方

在Gallager [3]的原始论文中，LDPC码被定义为一种线性块码，其奇偶校验矩阵H是稀疏矩阵，即主要包含0，只有少量1的矩阵。 此外，在此矩阵中，每行具有相同数量的1，并且每列具有相同数量的1。 特别地，Gallager将（n，j，i）LDPC码定义为具有块长度n，奇偶校验矩阵中每列1的数量为j，每行1的数量为i的代码。 这种类型的奇偶校验矩阵如图3所示

该矩阵可以分成三个相等的子矩阵，例如：每列的权重为1，如图3所示。第一个子矩阵是一个特殊的矩阵：1以向下的方式放置，整个子矩阵看起来像一个单位矩阵，每列重复四次。事实上，子矩阵只需要是这种特殊结构的随机列排列。还可以容易地看出，第一子矩阵（或任何后续子矩阵）的随机列置换将在每行中恰好具有四个1并且在每列中具有单个1。反之亦然，每行中具有四个1并且每列中具有单个1的任何（5×20）子矩阵仅是第一子矩阵的列置换。 图4给出了这种奇偶校验矩阵的表示[2]。

图4具有行权重4和列权重3的Gallager结构的表示。具有对角线的正方形表示单位矩阵。 带箭头的椭圆表示随机列排列。
通常，（n，j，i）矩阵可以被划分为列权重为1的j个子矩阵。（n，j，i）矩阵的行数由nj / i给出（j是 每列中的1的数量，因此1的总数是nj，并且i是每行中1的数量）。 因此，每个子矩阵将具有n / i行。
考虑到LDPC码作为一种线性块码，我们可以如下计算（n，j，i）LDPC码的码率R：首先，假设H的所有行是线性独立的（或者H是满秩） ），H的等级（以模2算术计算）将与行数J相同，其为nj / i（J <n，即J = nk）。 然后，生成矩阵G的维数为（n-nj / i）×n（j <i为J <n），码率R为
$R = (n-nj/i)/n = 1 – j/i.$R=(n−nj/i)/n=1–j/i.
当H的行不是线性独立的时，H的秩将小于nj / i，并且G的行数将大于n-nj / i，这导致R> 1-j / i。 所以，一般来说，我们有：
$R≥ \frac{n-n{j\over i}}{n}= 1-\frac{j}{i}\tag{1.5}$R≥nn−nij​​=1−ij​(1.5)

B. Mackay’s构建

LDPC码的Tanner图中存在短周期将降低迭代解码算法。 考虑图5中给出的Tanner图的部分。

图5长度为4的周期及其对迭代解码算法的影响
三个噪声符号连接到五个校验符号，如图5所示。长度为4的循环由粗线绘制。 如果所有这三个噪声符号都是错误的（从1变为0或反之亦然），则只能警告最右边的检查（s5）。根据Davey的说法，这种情况会降低解码过程的性能[2]。