【LDPC码的理论基础综述2800字】

LDPC码的理论基础综述目录TOC\o"1-3"\h\u3770LDPC码的理论基础综述 1226281.1线性分组码 170181.1.1线性分组码的基本概念 139581.1.2校验矩阵和生成矩阵 2257021.2LDPC码的定义及Tanner图表示 2228011.3QC-LDPC码的介绍 51.1线性分组码分组码分为线性分组码和非线性分组码，其中常见的是线性分组码，如汉明码，它们都是建立在代数学的基础上的。其中LDPC码也是属于线性分组码中的一种。1.1.1线性分组码的基本概念一个大小为[n,k]的线性分组码中的码字有2k个，其信息码元为k位，码组长度为n，线性分组码的码率R=k/n，其中校验位的长度为r=n−k有限域，也称为伽罗华域(GaloisFields，简写为GF)，它是纠错码(尤其是BCH码和RS码的基础)理论的重要基础。GF域和其他的域相似，在进行基本运算的过程中都满足定义与规则，它的定义有以下几条：定义1：对于整数0，1，2，……，q。其中1到q为自然数，在模P的加法和乘法运算下，构成了一个有限域（伽罗华域），用GF(q)表示[10]。定义2：若某个分组码M包含N个码字，而这些码字都来源于GF(q)里的元素，那么当且仅当，M组成GF(q)上的一个矢量子空间，此时我们把M称为q进制的线性码。本文主要探讨的是二元线性分组码，也就是q取2时的情况，这个时候二元线性码满足，全零码字在码字集合中和集合中任意码字用模2加后结果依然属于码字集合。1.1.2校验矩阵和生成矩阵监督位和信息位之间的关系是由奇偶校验矩阵H所确定的，也就是说我们一旦知道奇偶校验矩阵H，也就能了解到监督位和信息位的关系，其中奇偶校验矩阵H中的行数就是监督位的数目，每行中“1”的位置表示它们之间的关系。而线性分组码的生成矩阵G也是研究码的编码与译码的一个重要工具，它的每一行是一个码字且其各行线性无关。校验矩阵H和生成矩阵G可以有以下形式：G=IH=[Pk×(n−k)其中I为单位矩阵，P为校验矩阵。同时可以根据式(2-1)与(2-2)可以得出校验矩阵H和生成矩阵G满足式(2-3)：G×H已知信息序列u，则编码后的码字c可以直接由u与生成矩阵G相乘得出，有如下公式：c=u×G(2-4)根据式(2-3)和式(2-4)也可以推得如下公式：c×H1.2LDPC码的定义及Tanner图表示LDPC码(低密度奇偶校验码)是具有稀疏校验矩阵的一组线性分组码，它的稀疏性在于它奇偶校验矩阵只含有少量的非零元素。LDPC码除了具有稀疏性的校验矩阵外，与其他的线性分组码没有本质上的区别。LDPC码具有很好的译码性能极限，译码也十分方便，特别是在GF(q)域上的非规则码，在非规则双向图中，当各变量节点与校验节点的度数选择合适时，其性能非常接近香农极限。LDPC码通常由大小为(n-k)×n的稀疏奇偶校验矩阵H来定义的，类似于分组码的定义，n表示的是码长，k表示的是信息位的长度，(n-k)表示的是校验位长度。如果给出了校验矩阵H，那么H的零空间就是码字c。也就是说在GF(2)域中，有c×HT=0成立。同时根据稀疏矩阵中各列或者各行所包含的1的个数是否相等，可以将LDPC码划分为规则LDPC码和不规则LDPC码[11]。一般LDPC码可由以下4个条件定义：校验矩阵H的每行有p个非零元素；校验矩阵H的每列有q个非零元素；校验矩阵H任意两行（两列），不能同时出现两个以上的非零元素在同一位置；校验矩阵H满足稀疏性，与码长n和H的行数相比，p和q都是非常小的数。其中p为奇偶校验矩阵H的行重，q为奇偶校验矩阵H的列重，我们常用(n,p,q)来表示LDPC码，规则LDPC的校验矩阵的行重和列重是恒定不变的，而不规则LDPC的各行的行重或各列的列重不同。条件(3)通常被称为LDPC码的行列约束条件,也就是满足条件(3)时校验矩阵H的Tanner图没有四环结构，如果不满足该条件LDPC码在迭代译码的过程中会出现较多的错误。由定义可以知道，我们一旦确定了奇偶校验矩阵H，就能得出相应的LDPC码，所以对一个LDPC码的构造实际上就是对它的校验矩阵的构造。线性分组码一般是用校验矩阵来表示，而对于LDPC码我们常用Tanner图来表示，Tanner是一种双向图模型，表示方式对有关LDPC码编码与译码特性的描述是较为普遍和形象的[12]。Tanner图中的内容对应校验矩阵H，它有两种不同类型的节点，分别是校验节点和变量节点。一个r×n的校验矩阵H，变量节点对应的是H中的各列元素，共有n个变量节点，而校验节点对应的是H中各行的元素，共有r个校验节点。当校验矩阵的某个位置的元素为1时，则用连线将该元素对应Tanner图中的位置的校验节点和变量节点相连接，最后的连线总数为校验矩阵H中的所有非零元素的个数。图2-1为式(2-6)中的校验矩阵所对应的Tanner图。校验节点校验节点变量节点图2-1校验矩阵H的Tanner图H=101001100在Tanner图中，度表示与节点相连的边的个数，而由一系列的边构成的封闭路径被称为环。在LDPC码中，如果出现长度为4的环则在基于置信传播的迭代译码的过程中会导致译码失败。围长(girth)是指全部节点中，最短的环的长度。当出现围长为4的情况是，对应的校验矩阵H中，就是存在两行或两列在两个相同的位置都出现了元素1，这与LDPC码的约束条件(3)相矛盾，所以应该尽量避免出现4环的情况，否则会使得LDPC码的迭代译码性能受到严重影响。易知，环的长度只能为不小于4的偶数，否者将会导致译码器不可迅速收敛，乃至不能收敛[13]。也就是说，LDPC码的Tanner图至少为六环。要减少短环的出现，必须增大码长。如果码长不变，是不可能实现码字无环的，所以此时我们应该尽量使得矩阵中环最少，降低短环对译码性能的影响。同时我们也需要一种能够检测4环存在的方法。4环是否存在我们可以通过下式(2-7)来检验，需要添加相应的辅助矩阵O：O=H当且仅当辅助矩阵O除主对角元素外的元素都为0或1时，校验矩阵H无4环结构。1.3QC-LDPC码的介绍QC-LDPC码也是属于线性分组码，QC-LDPC码具有很多优点。首先，与需要二元方程复杂度的随机LDPC码的构造相比，可以通过使用简单的移位寄存器来完成QC-LDPC码的编码，该简单的移位寄存器的复杂度与奇偶校验位的数量成线性关系。其次，QC-LDPC码可以由基校验矩阵表示，其中每个元素都是大小为z×z的正方形子矩阵。当与奇偶校验矩阵相比时，基校验矩阵的大小要小得多(大小减小到z×z)，因此只需要更少的存储空间。此外，通过使用具有适当大小的子矩阵，可以简单灵活地将基矩阵扩展为针对不用码长的奇偶校验矩阵H。此外，QC-LDPC码的奇偶校验矩阵的奇偶校验部分通常以近似下三角(ALT)的形式所建立，以此来实现较低的编码复杂度。一种典型的ALT结构是双对角结构，广泛用于实际系统中。此外，还探索了一些具有双对角线结构的QC-LDPC码的有效编码方法。为了降低编码复杂度，奇