精华内容
参与话题
问答
  • LDPC码简介

    千次阅读 2020-03-10 22:24:01
    LDPC码–低密度校验码–是一种前向纠错码,LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,1995年前后MacKay和Neal等人对LDPC...

    LDPC码简介

    LDPC码–低密度校验码–是一种前向纠错码,LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,1995年前后MacKay和Neal等人对LDPC码重新进行了研究,提出了可行的译码算法,从而进一步发现了LDPC码所具有的良好性能,迅速引起强烈反响和极大关注。经过十几年来的研究和发展,研究人员在各方面都取得了突破性的进展,LDPC码的相关技术也日趋成熟,甚至已经开始有了商业化的应用成果,并进入了无线通信等相关领域的标准。

    LDPC码的特点

    • 特点一:LDPC码的检验矩阵的稀疏性。LDPC码是一种分组码,其校验矩阵只含有很少量非零元素。正是校验矩阵的这种稀疏性,保证了译码复杂度和最小码距都只随码长呈现线性增加。除了校验矩阵是稀疏矩阵外,码本身与任何其它的分组码并无二致。其实如果现有的分组码可以被稀疏矩阵所表达,那么用于码的迭代译码算法也可以成功的移植到它身上。然而,一般来说,为现有的分组码找到一个稀疏矩阵并不实际。不同的是,码的设计是以构造一个校验矩阵开始的,然后才通过它确定一个生成矩阵进行后续编码。

    • 特点二:LDPC的译码。译码方法是LDPC码与经典的分组码之间的最大区别。经典的分组码一般是用ML类的译码算法进行译码的,所以它们一般码长较小,并通过代数设计以减低译码工作的复杂度。但是LDPC码码长较长,并通过其校验矩阵H的图像表达而进行迭代译码,所以它的设计以校验矩阵的特性为核心考虑之一。

      本篇文章将从上述两个特点来阐述本人对LPDC码的理解。即一部分为lpdc码的构造与编码,解释其检验矩阵特殊在哪里。另一部分为lpdc码的译码和译码算法。

    LDPC码的构造

    在通信原理这门课程当中,对一种分组码的设计,要先设计一个适合的校验矩阵H,然后根据对偶性,得到其生成矩阵G,再利用信息码组与生成矩阵相乘得到其完整分组码。在LDPC线性分组码,也是同样道理。因为其对校验矩阵稀疏性的要求,H矩阵的构建在LDCP码领域是一个重要的问题,H矩阵的好坏影响着编码解码的性能。H矩阵分为正则H矩阵和非正则H矩阵,Gallager提出LDPC码时构建的H矩阵就是一个正则H矩阵。

    Gallager在其论文中给出一种方法-随机构造法,大体内容如下:
    Gallager码(n,j,k)(n, j, k)(n,j,k)的构造步骤:

    • 将码集矩阵其分成 j 个子矩阵,每个矩阵每列只有 1 个1;

    • 第一个子矩阵中的1成下降趋势构成,如图1;

    • 其它子矩阵由第一个子矩阵通过随机列置换构成。
      在这里插入图片描述

    但是这种方法无法满足无短环要求,故其至少需要消除4环这一步骤,而由于消除4环的效果不理想,则会导致后续的译码性能差(本篇文章不做过多解释)

    因此除了这中随机构造法还有以下这些方法:

    • 组合数学完备循环差集构造法:这种方法构造的H是无4环规则码,且同一行列数要求下的H很多。

    • 对角线法:这种方法主要用于构造规则码(也可以用于不规则码)。

    LDPC的编码

    在得到校验矩阵后,需要进行编码,得到完整码元。编码方法也有如下几种:

    • 一、系统编码法即高斯消元法:

      通过高斯变换将得到的H转化为系统形式,这样编码简单,同样由于破坏了稀疏矩阵的稀疏性导致编码复杂度(主要是高斯变换过程复杂)很高。

    • 二、近似下三角矩阵法:

      –该算法直接通过校验矩阵求取编码码字的校验比特位。

      • 首先,将校验矩阵变换为下图的下三角形式在这里插入图片描述

      • 其中,T为下三角矩阵,然后通过校验矩阵的每一行乘以转置后的码字乘积为0以及下式可以得到后面两个式子:在这里插入图片描述

      • 其中
        -在这里插入图片描述

      • 通过中间的式子求出校验比特部分p1,进而带入最后的式子求得校验比特p2,就得到完整码元,以完成编码。

    LDPC码的译码

    主流的LPDC译码算法有如下两种,一种是比特翻转算法,另一种是置信传播算法

    一、比特翻转算法–BF:

    该算法是硬判决译码算法中最主要的一种算法。基本假设是当校验方程不成立时,说明此时必定有比特位发生了错误,而所有可能发生错误的比特中不满足校验方程个数最多的比特发生错误的概率最大。因此,在每次迭代时均翻转发生错误概率最大的比特并用更新之后的码字重新进行译码,直到校验方程成立。具体步骤如下

    • 设置初始迭代次数 k1及其上限kmax 。对获得的码字y=(y1,y2…yn)按照下式展开二元硬判决得到接收码字的硬判决序列Zn 。

      在这里插入图片描述

    • 若k1=kmax ,则译码结束。不然,计算伴随式s=(s0,s1,…sm-1),sm表示第m个校验方程的值。若伴随式的值均为0,说明码字正确,译码成功。否则说明有比特位错误。继续进行步骤3。

    • 对每个比特,统计其不符合校验方程的数量fn (1<=n<=N)

    在这里插入图片描述

    • 将最大fn所对应的比特进行翻转,然后k=k+1,返回步骤2。

    BF算法的优点在于单纯的对码字进行硬判决,理论最为简单,实现起来最容易。缺点是舍弃了每个比特位的可靠度信息,,性能也最差。当连续两次迭代翻转函数判断同一个比特位为最易出错的比特时,BF算法会陷入死循环,大大降低了译码性能。

    疑问:

    1. 为什么这里通过计算表达式fn就可以得到哪个比特不满足校验方程的个数最多即最有可能出错。
    2. 当同时有两个及两个以上的比特不满足校验方程的数目一样多时,该算法如何处理。
    二、置信传播算法–BP

    –置信传播(Belief Propagation)译码算法是消息传递(Message Passing)算法在 LDPC译码中的运用。

    Tanner图

    首先了解一下Tanner图的概念,Tanner图是迭代译码算法的参考工具,具体的定义这里不给出,以一个例子来说明Tanner图。设发送码字C=(C9,C8,C7,C6,C5,C4,C3,C2,C1),一个监督矩阵H为

    在这里插入图片描述
    则用Tanner来表示校验子S

    在这里插入图片描述

    图中的X0,X1…X9称为变量节点,代表10个比特C0,C1,C2…C9,它们是译码器待求解的未知变量。图中的□成为校验节点,代表线性方程组中的每一个校验方程,连线就代表方程中此变量的系数为1。

    注:此前提到的环可以理解为:一个节点经过多少条线回到该节点的条数。

    置信传播译码算法的基本流程:
    • 在迭代前,译码器接收到信道传送过来的实值序列y=(y1,y2,….yn),所有变量节点bi接收到对应的接收值yi。
      第一次迭代:每个变量节点给所有与之相邻的校验节点传送一个可靠性消息,这个可靠性消息就是信道传送过来的值;每个校验节点接收到变量节点传送过来的可靠性消息之后,进行处理,然后返回一个新的可靠性信息给与之相邻的变量节点,这样就完成了第一次迭代;此时可以进行判决,如果满足校验方程,则不需要再迭代,直接输出判决结果,否则进行第二次迭代。
    • 第二次迭代:每个变量节点处理第一次迭代完成时校验节点传送过来的可靠性消息,处理完成后新的消息发送给校验节点,同理,校验节点处理完后返回给变量节点,这样就完成了第二次迭代。完成后同样进行判决,如果满足校验方程则结束译码,否则如此反复多次迭代,每次都进行判决,直到达到设定的最大迭代次数,译码失败。

    注意:在每次迭代过程中,为保证每次节点接受与发送的信息相互独立,无论是变量节点传送给校验节点的信息或者校验节点传送给变量节点的信息,都不应该包括前次迭代中接收方发送给发送方的信息。

    在上述所说的在节点间传递的可靠信消息中,肯定包含错误比特信息(在S校验子不为0的前提下),但是这个错误信息,与其他节点的正确信息共同传递至某一校验节点,在我看来是一种‘平均’,经过若干次‘平均之后’,所得的到值就为正确的信息。

    关于BP的推导公式较为复杂,参考链接

    非规则LDPC码–qc-LDPC(准循环LDPC码)

    • 非规则矩阵:不满足校验矩阵每行列重相同,每列列重也相同,并且校验矩阵中任意两列中元素1位置相同的个数不能多于1个,这样的LDPC称为不规则LPDC

    • LDPC校验矩阵主要有随机化生成法和结构化生成法,准循环LDPC就是通过循环置换矩阵的结构化构造方法构造出的一类LDPC,更有利于编码和译码。现已被用在5G和eMBB场景中采用。

    • 其构造校验矩阵,编译码原理同规则LPDC码。

    DC

    • LDPC校验矩阵主要有随机化生成法和结构化生成法,准循环LDPC就是通过循环置换矩阵的结构化构造方法构造出的一类LDPC,更有利于编码和译码。现已被用在5G和eMBB场景中采用。

    • 其构造校验矩阵,编译码原理同规则LPDC码。

    展开全文
  • 二进制LDPC码的构造及译码算法

    千次阅读 2018-09-09 16:11:04
    构造好的LDPC码校验矩阵和设计性能优异的译码算法是LDPC码研究领域的重点。  常见的LDPC码一般分为两类,一类是随机LDPC码,一般由随机化方法构造;另一类是准循环LDPC码,一般由半随机方 法或者基于代数的结构化...

            构造好的LDPC码校验矩阵和设计性能优异的译码算法是LDPC码研究领域的重点。
           常见的LDPC码一般分为两类,一类是随机LDPC码,一般由随机化方法构造;另一类是准循环LDPC码,一般由半随机方

    法或者基于代数的结构化方法构造。常见的LDPC码的迭代译码方法包括基于硬判决的译码基于软判决的译码。接下来将介绍

    几种具有代表性的LDPC码构造方法以及经典的硬判决和软判决译码方法。

    1 . PEG构造和QC-PEG构造

            渐进边增长(progressive edge growth, PEG)算法[1][2][3]是一种著名的基于图的随机化LDPC码构造方法,其主要做法是依

    次对每个变量节点添加边连接校验节点来构建出所要的Tanner图,在每次添加边的时候使当前变量节点的本地围长(当前变量节

    点所参与的最短的环的长度)尽可能地大。这样虽然不能保证最终Tanner图对应的LDPC码是最优的,但是其性能一般也非常优

    异。

         一个LDPC码的校验矩阵对应着唯一的一个Tanner图,PEG算法根据给定的码长、码率以及度分布,从头开始构建Tanner

    图。假设需要构建的Tanner图的校验节点数为m,变量节点数为n,变量节点vj相连的所有边所构成的集合记为E_{v_{j}},那么容易得

    到所有的边的集合。记与vj相连的第k条边为,0\leq k\leq d_{s_{j}}-1。以vj为根节点将Tanner图展开,把

    在其展开的树上能达到l层的校验节点集合记为N_{v_{j}}^{l},与之相应的补集为\bar{N_{v_{j}}^{l}},有\bar{N_{v_{j}}^{l}}= N_{c} \setminus N_{v_{j}}^{l}Nc为所有校验节点的集合。

    其展开过程如下图1-1所示。

     

                                   

                                                                                 图1-1  k层树图展开

    根据PEG算法[2][3]的思想,逐个地为每个变量节点选择合适的校验节点,然后在他们之间建立边,这里的索引从0开始,算法

    的具体步骤描述如下:

    1.1  选择一个变量节点vj(一般就按索引的顺序)。如果当前需要添加的是此节点的第0条边,则找到当前Tanner图中具有最低度

    数的校验节点ci,v和 c连起来就可得到此节点的第0条边E_{v_{j}}^{0}。如果变量节点vj已经 添加过边,则首先以vj为根节点把当前

    Tanner图展开为树图直到深度为l,如果发现\bar{N_{v_{j}}^{l}}\neq \varnothing 而\bar{N_{v_{j}}^{l+1}}\neq \varnothing,或者有集合N_{v_{j}}^{l}中的校验节点不再继续增加但N_{v_{j}}^{l}中的校验

    节点的数目仍小于全体校验节点数m, 就在\bar{N_{v_{j}}^{l}}中选取度数最低的校验节点与vj相连。

     

    1.2  重复步骤1.1)直到vj相连的边的条数等于所给定的vj的度数。

     

    1.3  重复步骤1.1) 1.2),直到所有变量节点的边都添加完毕。

           PEG算法构造的LDPC码能有效地减少短环的形成,但是其是一种随机化的构造方法,校验矩阵没有一定的结构和规律,

    因而在硬件实现的时候需要耗费大量的空间和资源,不利于实际的应用;同时无规律的校验矩阵也不能实现快速编码,造成复

    杂度高和效率低下。Li提出了可以构造准循环LDPC码的PEG算法[4],要构造一个维数是m × n,子矩阵维数为L × L的准循环

    LDPC校验矩阵,首先把变量节点和校验节点按每组L个节点进行分组,这样可以得到R组校验节点和C组变量节点,其中

    R = m / LC = n / L。在这个的基础上,Liu等人也做出了深入的研究,初步提出了一种基于PEG的伪随机构造算法[5]。经过深

    入探讨与研究他们提出了一种构造准循环LDPC码的方法,该方法也结合了PEG算法,在保持准循环特性的基础上能够获得比

    PEG算法更佳的译码性能,并且可以灵活地选择码长和码率[6],这里称为QC-PEG算法, 其在添加边时将节点按顺序分组,每

    组包含L个节点,只需要确定一组中的一个节点,那么其它节点所连接的边就可以通过循环移位的特性确定。

            QC-PEG引入一个称之为不可靠因数的系数β用来评估一个节点信息的可靠程度。一个节点的不可靠因数β值越大,表明该

    节点的信息就越不可靠。很容易可以知道,一个节点的β值的大小和节点所参与的环的数目以及相应的环长的大小是密切相关

    的。一个节点参与的环的数目越多,且长度越短,该节点的β值就越大,那么这个算法里给出的β值的计算方法就可以表示为

                                                                                                              (1-1)

    其中,l_{i}为第i个环的长度,k为该节点参与的环的个数。从节点的不可靠系数β出发,该算法还给出了一个环的不可靠因数α的定

    义:α为组成该环所有节点的不可靠因数β之和。在选取合适的校验节点给当前变量节点vj连接新的边的过程中,如果在变量节

    vj和某个校验节点ci之间已经连接过了一条边,那么在校验节点集合Cd中的任何节点都不能和变量节点vj相连,这个集合称为与检验节点ci关联的受限节点集合,其中,每一个检验节点都有一个对应的

    Cd。接下来,将以变量节点vj所在的关键列为例,具体阐述如何确定与vj相连的校验节点,其具体过程如下:

    1. )为变量节点vj添加第一条边时,在当前已构建的Tanner图中寻找度数最小的校验节点ci,连接变量节点vj和校验节点ci这两个节点就可以得到第一条边。在添加变量节点vj的其它边时,以vj为节点将当前Tanner图展开到深度l,如果集合包含节点数停止增长但仍然小于校验节点总数,则ci中随机取一个后与vj相连。如果集合但是,则把校验节点集合定义为F1,如果F1中的校验节点的数目不唯一,那么执行步骤2)。
    2. )考虑到vj添加的当前边也会对将添加的下一条边有影响,集合F1中不同的校验节点和vj相连时产生的当前短环和对vj添加下一条边也会产生影响。把F1中每一个校验节点与vj尝试相连,然后在此基础上再尝试对vj添加下一条边,不断尝试,直到选出F1中使得当前Tanner图形成的本地围长最大且短环数目最少的校验节点组成校验节点集合F2。
    3. )在环不可避免的情况下,选取使得环的外信息度数最高的节点。找出校验节点集合F2中每个节点和vj相连时所形成的环,并计算这些环的外信息度数同时进行比较,将使得形成的环的外信息度数最小的校验节点放入一个新的集合F3。
    4. )对于校验节点集合F3中的节点,搜索出F3中每个校验节点和vj相连时所形成的环,计算每个环的不可靠因数,然后从中选取使得最小的校验节点组成校验节点集合F4。最后从F4中任意选取一个校验节点和vj相连。

           对Tanner图对应校验矩阵中的所有关键列都进行以上的步骤,直到所有的关键列都确定,然后通过准循环性质就可以确定

    整个Tanner图和校验矩阵了。

    2. 基于代数方法的结构化构造

     

            准循环LDPC码更多地是以代数方法构造的[6][7][8],一般都是基于有限域和矩阵论的,具有较强的理论性,虽然每个代数

    构造方法略有不同,但基本原理是一致的,这里简述其一般过程。

           给定有限域GF(q),为GF(q)的一个本原元,则本原元的幂次,即,给定了GF(q)上的q个元素。设P为一个大小为的循环置

    换矩阵,其第0行为一个长度为取值在GF(2)上的向量(0,1,0,,0),此向量的第1个元素为“1”,其它都是“0”。P的其它行都是上一

    行的循环右移向量。P即由(0,1,0,,0)以及(0,1,0,,0)的(q – 2)个循环右移向量组成,\mathbf{P}^{i}=\mathbf{P\times P\times\cdots \times P}iP的乘积,称为

    Pi次幂,这里1\leqslant i< q\mathbf{P}^{i}也是一个大小为\left ( q-1 \right )\times \left ( q-1 \right )的循环置换矩阵,且其首行的向量的第i个元素为“1”。特别

    地,P^{q-1}即为单位阵\mathit{\mathit{\mathbf{I}_{q-1}}}。令,则(q – 1)个循环置换矩阵构成的集合构成了一个(q – 1)阶的GF(2)上的

    矩阵乘法循环群,\mathbf{P}^{i}的乘法逆元为\mathbf{P}^{q-1-i}\mathbf{P}^{0}为单位元。

           对0\leqslant i< q-1,可用表示GF(q)的非零元\alpha ^{i},将\mathbf{P}^{i}映射为 \alpha ^{i}的操作就是前面介绍过的矩阵的分散。\mathbf{P}^{i}与非零 \alpha ^{i}之间有

    一个一一对应的关系。GF(q)中的元素0则对应全零矩阵,记为\mathbf{P}^{-\infty }

          考虑GF(q)上 R\times C的基矩阵,

                           

          其行满足以下约束:对,任意两个qn长序列 \alpha ^{^{c}}\mathbf{\omega _{i}}\alpha ^{^{l}}\mathbf{\omega _{j}}之间的

    Hamming距离至少为(n – 1)。这个约束称为行距 (row-distance, RD)约束,满足此约束的基矩阵W称为行距约束矩阵。通过将

    基矩阵W中的各个GF(q)的元素映射为对应的循环置换矩阵,就能得到最终的R\left ( q-1 \right )\times C\left ( q-1 \right )的奇偶校验矩阵H。由满足

    行距约束的W分散得到的H中不存在4环。H的零空间给定了一个长度为R(q – 1),其码率至少为(R – C) / C。在文献[5]中,归纳

    了几种满足行距约束的校验矩阵的构造方法,通过这些行距约束矩阵以及分散操作,可以构造得到几类常见的准循环LDPC码,

    这里不再赘述。

     

     

    • 参考文献

    [1]  X. Y. Hu, E. Eleftheriou, and D. M. Arnold. Progressive edge-growth Tanner graphs [C]. IEEE Global Telecommunications Conference, San Antonio, TX, USA, Nov. 2001, 2: 995-1001.

    [2]  X. Y. Hu, E. Eleftheriou, and D. M. Arnold. Regular and irregular Progressive edge-growth Tanner graphs [J]. IEEE Transactions on Information Theory, Jan. 2005, 51(1): 386-398.

    [3]  Y. Fang, P. Chen, L. Wang, and F. C. M. Lau. Design of Protograph LDPC Codes for Partial Response Channels [J]. IEEE Transactions on Communications, Oct. 2012, 60(10): 2809-2819.

    [4]  X. Liu, W. Zhang, and Z. Fan. Construction of quasi-cyclic ldpc codes and the performance on the pr4-equalized MRC channel [J]. IEEE Transactions on Magnetics, Oct. 2009, 45(10): 3699-3702.

    [5] Y.-M. Lin, H.-T. Li, M.-H. Chung, and A.-Y. Wu. Byte-Reconfigurable LDPC Codes Design With Application to High-Performance ECC of NAND Flash Memory Systems [J]. IEEE Transactions on Circuits and Systems I: Regular Papers, July 2015, 62(7): 1794-1804.

    展开全文
  • LDPC

    千次阅读 2017-03-09 11:03:03
    LDPC码即低密度奇偶校验码(Low Density Parity Check Code,LDPC)  LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,...


           LDPC码即低密度奇偶校验码(Low Density Parity Check Code,LDPC)


           LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,其间由Tanner在1981年推广了LDPC码并给出了LDPC码的图表示,即后来所称的Tanner图。1993年Berrou等人发现了Turbo码,在此基础上,1995年前后MacKay和Neal等人对LDPC码重新进行了研究,提出了可行的译码算法,从而进一步发现了LDPC码所具有的良好性能,迅速引起强烈反响和极大关注。经过十几年来的研究和发展,研究人员在各方面都取得了突破性的进展,LDPC码的相关技术也日趋成熟,甚至已经开始有了商业化的应用成果,并进入了无线通信等相关领域的标准。

    LDPC码是通过校验矩阵定义的一类线性码,为使译码可行,在码长较长时需要校验矩阵满足“稀疏性”,即校验矩阵中1的密度比较低,也就是要求校验矩阵中1的个数远小于0的个数,并且码长越长,密度就要越低。
    LDPC码即低密度奇偶校验码(Low Density Parity Check Code,LDPC),它由Robert G.Gallager博士于1963年提出的一类具有稀疏校验矩阵的线性分组码,不仅有逼近Shannon限的良好性能,而且译码复杂度较低, 结构灵活,是近年信道编码领域的研究热点,目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域。LDPC码已成为第四代通信系统(4G)强有力的竞争者,而基于LDPC码的编码方案已经被下一代卫星数字视频广播标准DVB-S2采纳。
    对同样的LDPC码来说,采用不同的译码算法可以获得不同的误码性能。优秀的译码算法可以获得很好的误码性能,反之,采用普通的译码算法,误码性能则表现一般。
    LDPC码的译码算法包括以下三大类:硬判决译码,软判决译码和混合译码。
    1. 硬判决译码将接收的实数序列先通过解调器进行解调,再进行硬判决,得到硬判决0,1序列,最后将得到的硬判决序列输送到硬判决译码器进行译码。这种方式的计算复杂度固然很低,但是硬判决操作会损失掉大部分的信道信息,导致信道信息利用率很低,硬判决译码的信道信息利用率和译码复杂度是三大类译码中最低的。常见的硬判决译码算法有比特翻转(bit-flipping, BF)算法、一步大数逻辑(one-step majority-logic, OSMLG)译码算法。
    2. 软判决译码可以看成是无穷比特量化译码,它充分利用接收的信道信息(软信息),信道信息利用率得到了极大的提高,软判决译码利用的信道信息不仅包括信道信息的符号,也包括信道信息的幅度值。信道信息的充分利用,极大地提高了译码性能,使得译码可以迭代进行,充分挖掘接收的信道信息,最终获得出色的误码性能。软判决译码的信道信息利用率和译码复杂度是三大类译码中最高的。最常用的软判决译码算法是和积译码算法,又称置信传播 (belief propagation, BP)算法。
    3. 与上述的硬判决译码和软判决译码相比,混合译码结合了软判决译码和硬判决译码的特点,是一类基于可靠度的译码算法,它在硬判决译码的基础上,利用部分信道信息进行可靠度的计算。常用的混合译码算法有、加权比特翻转(weighted BF, WBF)算法、加权OSMLG(weighted OSMLG, WMLG)译码算法。

    简单介绍一下LDPC码的基本原理,先说一下编码。学过通信原理的人应该有些印象,我们通过构建一个生成矩阵G,就可以进行编码了,当然这里仅仅介绍理论部分,硬件部分暂不介绍,我还没有学习到。具体如何利用生成矩阵编码在一般意义上不是很复杂的事情(只能说一般意义上,后面会提到非课本内容的部分),简单的说就是生成矩阵G和信息码的相乘,结果即为编码过后的码字,包括信息码和校验码。这样的码字在信道上传输可靠性会增大,虽然校验码增加了码长,降低了信息传输速率,可增加了纠错检错的能力,更加有利于解码的正确率即信息的正确传输(具体内容参考信息论的理论)。就我目前看到的为止,LDPC码的编码的问题主要有两类,第一类是校验矩阵H的构建(H矩阵是与G矩阵对偶的一个矩阵,代表了校验特征,也就是LDPC),第二类是编码的实现。H矩阵的构建在LDCP码领域是一个重要的问题,H矩阵的好坏影响着编码解码的性能。H矩阵分为正则H矩阵和非正则H矩阵,Gallager提出LDPC码时构建的H矩阵就是一个正则H矩阵,而理论和事实都证明非正则的H矩阵具有更加优良的特性。构建H矩阵的方法在Gallager第一次提出LDPC码的时候就已经给出一种方法,这在他1963年的那篇文章中给出了,具体内容就不介绍了,有兴趣的同学可以参考刚才提到的那篇文章。接下来就到了1996年,Mac Key开始接管LDPC领域的研究。他提出了一种随机构建H矩阵的方法,有1A、2A、1B、2B四种不同的方面,其实核心是一样的,每种方法有些许改进。这两种方法用于构建正则H矩阵。而随着后来的研究者越来越多,各种方法也都涌现出来,基本都是基于代数方法,也有基于启发式搜索的,有Xiao Yu Hu的PEG方法,这是被认为构建中、短码长低密度校验码当前所知具有参数最好的码,而这句话是Mac Key说得。还有Bit filling法等一系列方法,都是构建H矩阵最为常见的方法,后两者可以构建非正则H矩阵。后面两种方法还没有时间学习,但是构建H矩阵的核心即是围绕避免短的围长和增加码间距离展开,而这两者也有一定关系。从构建低密度校验矩阵方面看来,正则H矩阵的构建已经有了一定理论,而如何构建非正则H矩阵目前还没有严格的理论基础,这是一个值得研究的方面。

           编码研究的另一个方面就是具体编码的实现。课本上的原理前面已经介绍过了,通过H矩阵经过高斯消去很容易得到生成矩阵G,然后就很容易编码。而看到的文章提到由H到G消除了低密度的优点,然后就有不同的编码方法提出,也就引出了不同的理论和硬件实现。这方面暂时还没有开始看,才刚开始看,接触的都是最基本的,以后也许会做这方面的研究,现在先搞清楚有这个方向可以研究这个概念,为以后作准备。

           信道传输略过,这不是我们考虑的问题。再开始介绍解码。Gallager那篇经典文章中提到了两种方法,一种是比特翻转法(Gallager硬判决法),另一种是基于最大后验概率的解码方法(Gallager软判决法)。课本上介绍的解码方法是通过校验矩阵进行解码的,收到的码字和校验矩阵作相乘,如果结果为零矩阵,则收到的是正确码字,反之则不正确,再利用相乘的结果进行分析,进行纠错检错。比特翻转法,和常规的方法类似,主要就是设立门限,某一码字错误超过门限即翻转一次,然后反复迭代,直到解码正确或者超过迭代次数。第二种方法是利用码字每一比特的条件概率计算出另一码字的条件概率,然后又计算出另一个码字的条件概率,通过反复迭代直到每一比特为1的概率趋近于0或者1则译码输出。而迭代期间码字的选择可以通过奇偶校验树进行寻找,具体方法这里又不介绍了,有兴趣还可以参考前面提到的文章。还有基于Turner图的消息传播算法,其中的一种BP(置信传播)算法经过证明和Gallager的软判决算法等价的,可考虑问题的方法是不同的,很多思想是能够借鉴的。这种方法也是最好的最常用的方法,基于后验概率的解码在信息论的很多领域都一样的。不过需要说明的是,这是在BSC无记忆信道下推导出来一些理论,在高斯白噪声信道下以及记忆信道的理论暂时还没有涉及,前者有资料还没看,后者还没看到资料,这都是后期的工作了,既然工作总结就不再说了。

    下来就总结一些学习方法方面的问题。首先对于未知知识的学习应该先从最基本的入门做起,搜索资料的时候没有目标和条理,应该先搜索introduction,然后循序渐进,看资料也应该先看入门的东西,刚开始就看深入的东西真是要被打击死,幸好后来找到了思路。其次,对于经典的态度,对于经典的东西还是应该阅读一下的,看到这一类的文章的参考文献都是某几篇文章,看过之后也惊呼经典就是经典啊。记录下来构建H矩阵的经典文章,解码方法的经典文章,以后要是深入学习还是要阅读一下的。然后就是英语能力和数学能力,英语能力体现在对某些语句的理解方面,很多时候真是不能理解文章中的关键字,百思不得其解,只好通过其他资料进行理解,数学能力体现在对大师们的数学的崇拜,那些费劲才能看懂或者看不懂的东西,大师们可是想出来的啊,先驱就是先驱,再一次惊呼自己的平时接触的数学真是太简单了,数学能力有待提高这就是以后的任务了。最后就说对时间的利用,每天都在浪费时间,不能抓紧时间学习,其实这些东西原本很快就能看完的,拖到了现在。


    展开全文
  • LDPC码简介       低密度校验码(LDPC码)是一种前向纠错码,LDPC码最早在20世纪60年...

    LDPC码简介

          低密度校验码(LDPC码)是一种前向纠错码,LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,其间由Tanner在1981年推广了LDPC码并给出了LDPC码的图表示,即后来所称的Tanner图。1993年Berrou等人发现了Turbo码,在此基础上,1995年前后MacKay和Neal等人对LDPC码重新进行了研究,提出了可行的译码算法,从而进一步发现了LDPC码所具有的良好性能,迅速引起强烈反响和极大关注。经过十几年来的研究和发展,研究人员在各方面都取得了突破性的进展,LDPC码的相关技术也日趋成熟,甚至已经开始有了商业化的应用成果,并进入了无线通信等相关领域的标准。

    • LDPC码的特点
      LDPC码是一种分组码,其校验矩阵只含有很少量非零元素。正是校验矩阵的这种稀疏性,保证了译码复杂度和最小码距都只随码长呈现线性增加。除了校验矩阵是稀疏矩阵外,码本身与任何其它的分组码并无二致。其实如果现有的分组码可以被稀疏矩阵所表达,那么用于码的迭代译码算法也可以成功的移植到它身上。然而,一般来说,为现有的分组码找到一个稀疏矩阵并不实际。不同的是,码的设计是以构造一个校验矩阵开始的,然后才通过它确定一个生成矩阵进行后续编码。而LDPC的编码就是本文所要讨论的主体内容。对于LDPC码而言,校验矩阵的选取十分关键,不仅影响LDPC码的纠错性能力,也影响LDPC编译码的复杂度及硬件实现的复杂度。准循环 LDPC 码(Quasi-Cycle,QC-LDPC)是 LDPC 码中重要的一类,是指一个码字以右移或左移固定位数的符号位得到的仍是一个码字。QC-LDPC 码的校验矩阵是由循环子矩阵的阵列组成,相对于其他类型的 LDPC 码,在编码和解码的硬件实现上具有许多优点。编码可以通过反馈移位寄存器有效实现,采用串行算法,编码的复杂度与校验比特位数成正比,而采用并行算法,编码复杂度与码字长度成正比。对硬件解码实现,准循环的结构简化了消息传递的路径,可以部分并行解码,实现了解码复杂度和速率的折中。这些优点,使得 QC-LDPC 码作为未来通信和存储系统应用的主要 LDPC 码。

    • 译码算法的选择
      译码方法是LDPC码与经典的分组码之间的最大区别。经典的分组码一般是用ML类的译码算法进行译码的,所以它们一般码长较小,并通过代数设计以减低译码工作的复杂度。但是LDPC码码长较长,并通过其校验矩阵H的图像表达而进行迭代译码,所以它的设计以校验矩阵的特性为核心考虑之一。由于 LDPC 码校验矩阵的稀疏性,其译码复杂度与码长不是指数关系,而是线性关系,因而 LDPC 码的码长可以很长,可以达到几千到几万甚至更高,这样带来的一个好处是:一个码字内各比特之间的关联长度比较长,一般通过迭代译码方法进行译码,充分利用码字内各比特的关联性以提高译码准确度,并且还充分利用了信道的特征。本课题采用的译码算法为置信传播(BP)译码算法,置信传播算法是基于 Tanner 图的迭代译码算法。在迭代过程中,可靠性信息,即“消息”通过 Tanner图上的边在变量节点和校验节点中来回传递,经多次迭代后趋于稳定值,然后据此进行最佳判决,BP译码算法有着非常好译码性能。

    • Tanner图
      LDPC码常常通过图来表示,而Tanner图所表示的其实是LDPC码的校验矩阵。Tanner图包含两类顶点:n个码字比特顶点(称为比特节点),分别与校验矩阵的各列相对应和m个校验方程顶点(称为校验节点),分别与校验矩阵的各行对应。校验矩阵的每行代表一个校验方程,每列代表一个码字比特。所以,如果一个码字比特包含在相应的校验方程中,那么就用一条连线将所涉及的比特节点和校验节点连起来,所以Tanner图中的连线数与校验矩阵中的1的个数相同。以下图是矩阵的Tanner图,其中比特节点用圆形节点表示,校验节点用方形节点表示,加黑线显示的是一个6循环:
      ​​​​​​在这里插入图片描述
      Tanner图中的循环是由图中的一群相互连接在一起的顶点所组成的,循环以这群顶点中的一个同时作为起点和终点,且只经过每个顶点一次。循环的长度定义为它所包含的连线的数量,而图形的围长,也可叫做图形的尺寸,定义为图中最小的循环长度。如上图中,图形的尺寸,即围长为6,如加黑线所示。
      在这里插入图片描述

    LDPC编码

    • 基于校验矩阵H直接编码方案
      首先推导出根据校验矩阵直接编码的等式。将尺寸为(m,n)校验矩阵写成如下形式:
      H=[H1 H2]H=[H1 H2]H=[H1 H2]H=[H1 H2]H=[H1 H2] H=[H_1 \ H_2]Kij是校正因子,使每次计算出的
    展开全文
  • LDPC码

    万次阅读 2019-03-21 13:38:19
    低密度校验码(LDPC码)是一种前向纠错码,LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,其间由Tanner在1981年推广了LDPC码...
  • LDPC码Gallager论文解读

    千次阅读 2019-12-30 21:34:32
    LDPC码
  • LDPC码浅谈

    千次阅读 2019-12-14 12:33:21
    香农限:就是在带宽一定、噪声已知(可以根据信道参数算出来)的情况下,一个传输信道能通过的有用的数据量上限能够接近信道所能容量的最大数据量,目前,符合5G网要求的就只有LDPC和PolarLDPC:低密度校验...
  • LDPC的FPGA代码

    2019-03-30 17:42:49
    本课题从理论和硬件实现两方面对LDPC码进行讨论研究,最后完成LDPC码的编码设计。它的直接编码运算量较大,通常具有码长的二次方复杂度.为此,利用有效的校验矩阵 ,来降低编码的复杂度 ,同时研究利用大规模集成电路...
  • LDPC编译

    万次阅读 多人点赞 2018-03-07 19:28:32
    低密度校验码(LDPC码)是一种前向纠错码,LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出,但限于当时的技术条件,缺乏可行的译码算法,此后的35年间基本上被人们忽略,其间由Tanner在1981年推广了LDPC码...
  •  2.1 校验矩阵和生成矩阵   2.1.1 校验矩阵   2.1.2 生成矩阵   2.1.3 系统编码   2.2 重量和距离   2.3 线性分组的译码   2.4 分组的最小距离界   2.4.1 Hamming(汉明)球包...
  • 5G NR LDPC码(1)—— LDPC码设计原理

    千次阅读 2020-01-08 16:20:33
    校验矩阵来描述LDPC码,可以清晰的看到信息比特校验比特之间的约束关系,在编码过程中使用较多。 Tanner图把校验节点变量节点分为两个集合,然后通过校验方程的约束关系连接校验节点变量节...
  • LDPC码MATLAB仿真实现

    2019-03-09 16:04:00
    LDPC码MATLAB仿真实现
  • LDPC码---信道编码理论

    千次阅读 2016-08-19 21:19:12
    LDPC码是最有希望在广泛的信道方位取得香农容量的误差纠正技术...自从LDPC码重新被发现是接近香农限的好码,关于LDPC码的设计、构造、译码、有效编码、性能分析这些码在数字通信与存储系统中的应用就变成了研究焦点。
  • LDPC码编译码matlab代码

    2018-06-27 13:05:27
    本资源是基于matlab平台对LDPC码编译码原理的仿真,编码采用PEG算法,译码采用l积译码,有详细注释。有问题欢迎留言讨论。
  • 通信算法之三:LDPC码的研究

    万次阅读 2013-06-23 01:37:20
    LDPC码的研究现状与发展动态   1 引言 自从Shannon提出信道编码定理以来,编码研究者一直寻找性能尽可能接近Shannon极限,复杂度较低且容易实现的信道编码方案。从早期的循环码、BCH码、RS码、卷积码、
  • 初学者LDPC码扫盲

    2020-11-17 16:39:09
    LDPC码关于LDPC码信道编码奇偶校验优点缺点奇偶校验的改进优点缺点小结进一步的改进后记 关于LDPC码 关于LDPC码的介绍非常的多,有关的期刊论文数不胜数,但是很多人多注重创新点的介绍,在内容上忽略了LDPC码最...
  • LDPC编译MATLAB程序,可以直接运行程序,校验矩阵按照基础的G提出的原理生成的,用了高斯变换的到[I P]矩阵,译码是置信译码算法
  • LDPC编译原理

    千次阅读 多人点赞 2019-08-01 20:45:32
    LDPC码简介 LDPC编码 LDPC译码 结语
  • LDPC码的基础(1)

    千次阅读 2018-04-15 13:59:28
    低密度奇偶校验(low density parity-check, LDPC)码最早由Gallager在1962年提出...相对于Turbo码,LDPC码具有更低的误码平底,译码复杂度相对较低,可以实现完全的并行译码操作,抗干扰能力强,吞吐量较大。因此,L...
  • LDPC码由于可以达到更高的译码吞吐量更低的译码时延,可以更好适应高数据速率业务的传输,从而替代LTE的Turbo码...BG是LDPC码**PCM(Parity-Check Matrix, 校验矩阵)**设计的前提,也决定了LDPC码的宏观特性整体...
  • LDPC码的matlab仿真

    2015-10-22 15:41:08
    PEG算法生成校验矩阵,检验四环,BP算法进行译码,还有最后的仿真。
  • 关于qc-ldpc码校验矩阵的构造,有详细的解释,简单易懂。 关于qc-ldpc码校验矩阵的构造,有详细的解释,简单易懂。 关于qc-ldpc码校验矩阵的构造,有详细的解释,简单易懂。 关于qc-ldpc码校验矩阵的构造...
  • 扫描版PDF,清晰。 学习LDPC码必备,作者袁东风。 第一章绪论 第二章线性分组码 第三章LDPC码概述 第四章LDPC码校验矩阵构造
  • SSD ECC纠错“天网”之LDPC码

    千次阅读 2017-07-18 11:46:51
    在之前的文章中有提到过,SSD FTL层有...主流的SSD ECC纠错技术主要有BCH编码LDPC编码(LDPC码即低密度奇偶校验码,Low Density Parity Check Code,LDPC)。 不过,由于对更为廉价且密度更高的NAND闪存的需求以及3
  • LDPC码译码原理——概率公式推导

    万次阅读 多人点赞 2018-04-08 21:59:17
    近半年多来我一直在学习LDPC码译码上的东西,主要是在FPGA实现上的,所以这次想写一些关于这方面的内容,包括译码的原理、仿真以及实现。(当然是基于准循环LDPC码上实现的)不过呢,我写这个的初衷是为了让初学者...
  • turbo码 ldpc码的编译码

    2009-09-17 19:30:43
    本文首先介绍了一些Turbo码的基础理论知识,在此基础上对Turbo码编...的构造方法,并将其性能传统的基于校验矩阵LDPC码进行了比较。并在 AWGN信道瑞利信道下对其进行性能仿真,探讨了不同因素对译码性能的影 响。
  • 西安电子科技大学硕士学位论文,系统介绍了LDPC码编译码原理,重点研究了围长设计快速编码方法。
  • 关于QC-LDPC码的编码译码程序,之前上传了编码程序,这个是在其基础上,又添加了译码模块,一个主程序main.m,主要是看迭代次数或码长或码率对误码率的影响。这个matlab运行时间会有点长,要有耐心。程序前面...
  • NR-LDPC码知识

    2020-05-26 14:58:04
    QC-LDPC码是一类结构化的 LDPC码,其校验矩阵可以分解为ZxZ的全零矩阵和循环移位矩阵。其中循环移位矩阵通过对ZxZ的单位矩阵向右循环移位获得。扩展之前的矩阵称为基矩阵[对应的Tanner图称为基图(BG,Base Graph)],...
  • LDPC码verilog HDL 实现

    热门讨论 2010-07-12 20:14:00
    LDPC码verilog HDL 实现,包括LDPC编码译码。以及文献资料

空空如也

1 2 3 4 5 ... 20
收藏数 1,173
精华内容 469
关键字:

ldpc码