ldpc 订阅
LDPC是Low Density Parity Check Code英文缩写,意思是低密度奇偶校验码,最早在20世纪60年代由Gallager在他的博士论文中提出。 展开全文
LDPC是Low Density Parity Check Code英文缩写,意思是低密度奇偶校验码,最早在20世纪60年代由Gallager在他的博士论文中提出。
信息
外文名
Low Density Parity Check Code
提出时间
20世纪60年代
中文名
低密度奇偶校验码
提出人物
Robert G. Gallager
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

    千次阅读 2016-12-16 17:32:56
    SSD控制器芯片中采用的纠错编码...然而,对更为廉价及密度更高的NAND闪存的需求意味着BCH不再够用,为了寻求替代方法,多数人目前都选择了低密度奇偶校验码(LDPC)。  本篇博文将讲述这场演变的意义所在及其对我们P

              SSD控制器芯片中采用的纠错编码(ECCs)的类型正在发生一场演变,相信许多这篇博文的读者对此都有所了解。传统上采用的纠错码是基于群变换的博斯-查德胡里-霍昆格母(BCH)码,对于大尺寸的NAND闪存而言完全胜任。然而,对更为廉价及密度更高的NAND闪存的需求意味着BCH不再够用,为了寻求替代方法,多数人目前都选择了低密度奇偶校验码(LDPC)。

       本篇博文将讲述这场演变的意义所在及其对我们PMC称之为Software Defined Flash(软件定义闪存)这一领域的影响。如需了解更多LDPC码的背景,请参看Kent Smith 的精彩博文。

      从BCH向LDPC转变的原因有若干条,但最终都归于一点:LDPC码在相同的用户数据与ECC校验码之比下可以纠正更多的错误。这句话中提到相同的用户数据与ECC校验码之比非常重要。原因是我们不想增加SSD中的ECC校验位数,因为增加ECC校验位数会带来各种难以处理的问题,如写放大(Write Amplification , WA)及数据格式的低效利用等。

      你也许会说,“如果LDPC码这么棒,那为什么不打一开始就用它呢?”这个问题也在情理之中,答案在于几个因素:

      · 虽然LDPC码最早由Robert Gallagher于1960年提出,其真正价值直到90年代才真正实现,那是在NAND闪存已经采用了BCH码之后。

      · 解码LDPC码的电路与相当的BCH码电路相比,通常体积与功耗都需要更大

      · LDPC码的优势只在能从NAND闪存中提取软信息是才真正彰显出来,而这种信息提取只在最新一代技术中才刚刚实现

      但是,现在任何LDPC码应用的阻碍都不复存在,因此面世的多款SSD控制器中

      都已经集成了LDPC码。我们因此可以从若干新角度来讨论SSD的问题。

      LDPC提供的耐久度与/或数据留存

      BCH码向LDPC码演变带来的一个显著益处是控制器可以借此来延长SSD的使用寿命。NAND闪存随着编程-删除(PE)周期而逐渐损耗。举例而言,改成LDPC码可能将闪存周期从10,000提到15,000个PE周期,这样一来,就可以实现SSD在耐久性上50%的提升,而无须更换NAND闪存。类似地,改为LDPC码也可以提升SSD的留存率。

    闪存随着编程-闪存周期而损耗。LDPC与BCH相比,可以在每页中纠正更多错误,因此可以维持闪存更长的寿命,从而带来更高耐久度的SSD。

      LDPC带来容量改善

      从BCH码变为LDPC码带来的一个不那么明显的好处是每个闪存页面上的出错数目因此增加了。“为什么竟然会想要增加闪存页面上的出错数目呢?”有意思的是,如果接受每个NAND闪存页面上出错增加能换取NAND闪存上页面数目的提升不是很好吗?从MLCNAND闪存向TLCNAND闪存过渡恰好会实现这一点。

      TLC NAND闪存比MLC NAND闪存的页数多出50%,比SLC NAND闪存多出150%,因此可以提供$/GB方面巨大的改善。每页出错数增加当然会带来负面影响,但对于某些应用而言是可以接受的。

      从BCH码向LDPC码的演进促成了NAND闪存的TLC市场,并将NAND闪存的$/GB降至更低。

      LDPC带来延迟改善

      如果说企业级和数据中心用户对其使用的SSD只有一点要求,那一定是延迟。对某些应用而言,延迟及延迟的稳定性要求至关重要。我会在将来的博文中更详细地讨论这个问题。在这里,我想提一下,采用LDPC码——尤其是速率适应型的LDPC码——可以实现延迟控制,甚至对延迟的变化幅度作出限定。

      LDPC对软件定义闪存的意义

      有意思的是,如若精心设计,上述所有场景中采用的LDPCIP可以完全相同。通过对控制LDPC IP的固件进行微调,可以使控制器适用于多种应用。这一点对于Software Defined Flash(SDF) 很有价值。

      SDF允许用户通过改变运行于SSD之上的固件及软件的行为来调整SSD的属性。这就使物理上完全相同的SSD可以以完全不同的属性运作,这一点不管从静态还是动态的角度来看都很有意思:

      · 静态配置——假设某人想要在其数据中心中部署大量SSD。设想一下,这些SSD中有些需要高耐久度,而另外一些需要$/GB较低。支持SDF的SSD可以通过在SSD上安放不同的固件及软件来满足单个驱动中这些多样化的器件需求。

      · 动态配置——假设某人想要在其数据中心中部署大量SSD。设想一下,他们需要一种昼夜交替的负载模式,白天需要低延迟,夜晚则需要低功耗。那么,支持SDF的SSD又可以根据置于SSD之上的软件管理层上的指令来调整其一天当中的行为。

      结论

      由此可见,从BCH码变为LDPC码可以促成SSD 内部的许多精彩改变。有些改变一目了然(耐久度提高),有些比较隐讳(延迟控制),另一些则更为激进(如SSD的属性在一天中变化不定)。

      该项技术的普及将会带来些什么,我们拭目以待。Software Defined Flash 及其对SSD在企业级和数据中心环境中如何部署会带来的影响,在未来很长一段时间,将会引发种种讨论。

      你认为这一演变将带来的最为激动人心的变化是什么呢?


    展开全文
  • 为了比较多元LDPC码与二元LDPC码的性能,文章从校验矩阵、Tanner图、BP译码算法等方面将两者进行有效的分析,并结合具体的Monte Carlo 仿真实验,得出多元LDPC码的性能确实优于等长度码长的二元LDPC码。
  • LDPC编译码

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

    LDPC最新文章地址https://blog.csdn.net/sinat_38151275/article/details/98102699

    LDPC码简介

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

    1.1.1 LDPC码的特点

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

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

    1.1.2 LDPC码的构造

    构造二进制LDPC码实际上就是要找到一个稀疏矩阵H作为码的校验矩阵,基本方法是将一个全零矩阵的一小部分元素替换成1,使得替换后的矩阵各行和各列具有所要求的数目的非零元素。如果要使构造出的码可用,则必须满足几个条件,分别是无短环,无低码重码字,码间最小距离要尽可能大。

    1.1.3 Tanner图

    LDPC码常常通过图来表示,而Tanner图所表示的其实是LDPC码的校验矩阵。Tanner图包含两类顶点:n个码字比特顶点(称为比特节点),分别与校验矩阵的各列相对应和m个校验方程顶点(称为校验节点),分别与校验矩阵的各行对应。校验矩阵的每行代表一个校验方程,每列代表一个码字比特。所以,如果一个码字比特包含在相应的校验方程中,那么就用一条连线将所涉及的比特节点和校验节点连起来,所以Tanner图中的连线数与校验矩阵中的1的个数相同。以下图是矩阵

    的Tanner图,其中比特节点用圆形节点表示,校验节点用方形节点表示,加黑线显示的是一个6循环:

    Tanner图中的循环是由图中的一群相互连接在一起的顶点所组成的,循环以这群顶点中的一个同时作为起点和终点,且只经过每个顶点一次。循环的长度定义为它所包含的连线的数量,而图形的围长,也可叫做图形的尺寸,定义为图中最小的循环长度。如上图中,图形的尺寸,即围长为6,如加黑线所示。

    1.2 LDPC编码

    方法一:设H=[A | B],对H进行高斯消元可得到H=[I| P],设编码完成的码字为u=[c| s],其中c为监督位,s为信息位。因为H*u' = u*H' = 0,可以得到I*c' + P*s' = 0 即 I*c' = P*s' (在GF(2)上),从而可求 c' = P*s'。如果高斯消元过程中进行了列交换,则只需记录列交换,并以相反次序对编码后的码字同样进行列交换即可。解码时先求出u,再进行列交换得到u1=[c| s],后面部分即是想要的信息。

    方法一示例:

     

    方法二:首先推导出根据校验矩阵直接编码的等式。将尺寸为m*n校验矩阵H写成如下形式:H=[H1 | H2],其中H1矩阵的大小为m*k,H2的大小为m*m,设编码完成的码字为u=[s | p],s为信息位,p为监督位。因为H*u' =u*H' = 0求得p*H2'=s*H1',最后得p=s* H1'* (H2')-

    上述两种方法可以不通过生成矩阵而直接由校验矩阵进行编码的等式,一切只依赖校验矩阵的编码都是通过这两个式子实现的。但方法二要考虑H2是否满秩(可逆)。

    1.3 LDPC码H矩阵的构造

    规则的LDPC码和非规则的LDPC码

    如果校验矩阵中各行非零元素的个数相同,各列中非零元素的个数也相同,这样的LDPC码称为规则码,与规则码对照,如果校验矩阵的各行中非零元素的个数不同或各列中非零元素个数不同,此时的LDPC码称为非规则的LDPC码。

    1.3.1 非规则的LDPC码

    构造方法:码率R=M/N=0.5,构造的H矩阵列重固定,而行重是随机的。下面通过一个大小为6*12,列重为2的H矩阵来说明。因为列重固定为2,所以其列坐标集合为[1,1,2,2,3,3,4,4…….12,12],而行坐标可以随机构造。

    1.       先构造一个6*12,每一列为1到6随机排列的矩阵onesInCol。

    2.       选取onesInCol的前2行(和列重一致),如上图所示。

    3.        将所选取的矩阵按列依次排列如下

     

    4.       构造矩阵tmp

    5.       矩阵tmp重排成c1

    6.       full 把稀疏矩阵转换为满阵显示, sparse 创建稀疏矩阵生成M*N阶稀疏矩阵H在以向量r1和c1为坐标的位置上的对应元素值为向量1的对应值。

    1.3.2 规则的LDPC 码

    对于码率R=0.5的规则的LDPC码其行重与列重有关,行重是列重的2倍。以6*12的H矩阵为例,假设其列重为2,每列1的个数为2,总的1的个数为2*12=24,H矩阵有6行,行重相同则每行1的个数为24/6=4,即行重为4。假设其列重为3,其行重为6。

    构造方法:与构造行重类似,行重列重固定之后,其在矩阵中的位置坐标集合固定,如列重为2,行重为4,列坐标集合为[1,1,2,2,3,3,…..],行坐标集合为[1,1,1,1,2,2,2,2,3,3,3,3,……],下面考虑的就是如何将行列坐标组合起来而不重复。这里采用的是保持行坐标集合不变,列坐标集合打乱重排。以构造大小5*10,列重为2,行重为4的H矩阵为例说明。

    1.       先构造一个5*10,每一列为1到5随机排列的矩阵onesInCol。

    2.       选取onesInCol的前2行(和列重一致)构成1*20的矩阵

    3.       将r按升序排列得到

    4.       记录下排列前的位置索引

    5.       因为列坐标集合为[1,1,2,2,3,3,4,4,……9,9,10,10],将列坐标集合根据上面的位置索引重新排列,得到c

     

    6.       行坐标集合如下,与列坐标一一对应,确定矩阵H中1的位置。

    7.       最后结果

     

    1.3.3 LDPC码的环

    在 LDPC 码的 Tanner 图中,从一个顶点出发,经过不同顶点后回到同一个顶点的一些“边”组成的回路称为“环”。经过的边的个数称为环的长度。所有环中周长最小的环称为 LDPC码的围长(girth) ‎。

    Tanner 图中的环不可避免的会对译码结果造成非常大的干扰。由于迭代概率译码会使信息在节点间交互传递,若存在环,从环的某一个节点出发的信息会沿着环上的节点不断传递并最终重新回到这个节点本身,从而使得节点自身信息不断累加,进而使得译码的最终结果失败的概率变大。显然,环长越小,信息传递回本身所需走的路径就越短,译码失败的概率就变得越高。Tanner 图形成一个环至少需要 4 个节点组成4 条相连的边,即环长最小为4,这类短环对码字的译码结果干扰最大。定义 LDPC码的行列(RC)约束为:两行或两列中不存在元素 1 的位置有 1 个以上相同的情况。显然,满足 RC 约束的 LDPC 码最低就是 6 环,去除了4 环的干扰。由于4环的检测以及避免最为简单并且必要,因此绝大部分构造方法都会满足 RC 约束。而构造大圈长的码字则需要精确的设计。

     

    1.4 LDPC译码

    Gallager 在描述 LDPC 码的时候,分别提出了硬判决译码算法和软判决译码算法两种。经过不断发展,如今的硬判决算法已在 Gallager 算法基础上进展很多,包含许多种加权比特翻转译码算法及其改进形式。硬判决和软判决各有优劣,可以适用于不同的应用场合。

    1.4.1 比特翻转算法(BF)

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

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

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

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

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

    BF 算法的理论假设是若某个比特不满足校验方程的个数最多,则此比特是最有可能出错的比特,因此,选择这个比特进行翻转。BF 算法舍弃了每个比特位的可靠度信息,单纯的对码字进行硬判决,理论最为简单,实现起来最容易,但是性能也最差。当连续两次迭代翻转函数判断同一个比特位为最易出错的比特时,BF 算法会陷入死循环,大大降低了译码性能。

    图50*100

    图 500*1000

    1.4.2 置信传播算法(BP)

    置信传播(Belief Propagation)译码算法是消息传递(Message Passing)算法在 LDPC译码中的运用。消息传递算法是一个算法类,最初运用于人工智能领域,人们将其运用到 LDPC 码的译码算法中,提出了LDPC 码的置信传播算法。置信传播算法是基于 Tanner 图的迭代译码算法。在迭代过程中,可靠性信息,即“消息”通过 Tanner图上的边在变量节点和校验节点中来回传递,经多次迭代后趋于稳定值,然后据此进行最佳判决。

    置信传播译码算法的基本流程如下:

    在迭代前,译码器接收到信道传送过来的实值序列y=(y1,y2,….yn),所有变量节点bi接收到对应的接收值yi。

    第一次迭代:每个变量节点给所有与之相邻的校验节点传送一个可靠性消息,这个可靠性消息就是信道传送过来的值;每个校验节点接收到变量节点传送过来的可靠性消息之后,进行处理,然后返回一个新的可靠性信息给与之相邻的变量节点,这样就完成了第一次迭代;此时可以进行判决,如果满足校验方程,则不需要再迭代,直接输出判决结果,否则进行第二次迭代。

    第二次迭代:每个变量节点处理第一次迭代完成时校验节点传送过来的可靠性消息,处理完成后新的消息发送给校验节点,同理,校验节点处理完后返回给变量节点,这样就完成了第二次迭代。完成后同样进行判决,如果满足校验方程则结束译码,否则如此反复多次迭代,每次都进行判决,直到达到设定的最大迭代次数,译码失败。在每次迭代过程中,无论是变量节点传送给校验节点的信息或者校验节点传送给变量节点的信息,都不应该包括前次迭代中接收方发送给发送方的信息,这样是为了保证发送的信息与接收节点已得到的信息相互对立。

     

                                                                                             图50*100

    图500*1000

     

     

    结束语

    目前LDPC码研究领域的主要工作集中在译码算法的性能分析、编码方法、码的优化算法等,经过研究人员的努力,LDPC码的研究取得很大进展,但仍有许多问题需要进一步研究:

    (1)LDPC码校验矩阵的构造,尽管在构造最优的LDPC码方面取得了一些进步,但目前还没有一套系统的办法来构造所需要的好码,特别是在码字长度有限、码率一定的条件下,构造性能优异的好码是一个非常具有挑战性的课题。

    (2)LDPC编码系统的联合优化设计,将编码技术与调制技术、均衡技术、时空编码技术、OFDM技术结合进行性能优化是当前及将来的发展方向之一。

    (3)无线衰落信道及MIMO技术下LDPC码的性能分析方法及优化设计准则。目前LDPC码字的优化设计主要在加性高斯白噪声信道下得到的,而无线衰落信道下,特别是时变信道非线性环境下码字的性能分析方法、优化设计准则和信道估计的影响也是非常关键的课题,需要进一步的研究探索。

    此外,基于LDPC码的链路自适应技术,LDPC码在集成通信网物理层、应用层联合优化系统中的应用,LDPC码在无线局域网和深空宇航中的应用,基于LDPC码的图像传输、图像数字水印系统中的应用以及寻找更适合硬件实现的LDPC码编译码方法等都是非常值得研究的课题。

    展开全文
  • LDPC simulation

    2015-07-01 20:41:33
    ldpc simulation spa and msa decode
  • ldpc matlab代码5g ldpc 代码 要测试LDPC编码和解码功能,请在matlab下运行以下功能 test_all_ldpc_cases LDPC解码函数decLDPC_layered.m来自,作者是Christoph Studer。 我对其进行了一些小的修改以加速其执行。 ...
  • ldpc matlab代码LDPC_code matlab中有ldpc代码
  • awgn 通道的 ldpc 代码
  • 规则LDPC

    千次阅读 2020-12-02 07:36:34
    本系统分为两个部分进行,首先对比分析规则LDPC与非规则LDPC,然后再在协作MIMO的平台上进行仿真分析。 整个系统的理论,我想您一定比较清楚,所以本说明文档主要以介绍仿真结果和代码设计概要为主: 由于在误码率...

    本系统分为两个部分进行,首先对比分析规则LDPC与非规则LDPC,然后再在协作MIMO的平台上进行仿真分析。

    整个系统的理论,我想您一定比较清楚,所以本说明文档主要以介绍仿真结果和代码设计概要为主:

    由于在误码率仿真的时候,仿真时间比较长,为了节约时间,我们在每个模块之后都将仿真结果保存在mat中,您在调用仿真结果的时候,可以直接load,然后plot得到仿真结果图:

    规则LDPC

    规则LDPC,其主要性能仿真曲线如下,这里的主要设置参数如下:

    调用然后plot画图:

     

     

    非规则LDPC

    注意,不规则仿真,其性能非常好,所以仿真无码统计的信噪比只到4,如果需要仿真EbN0>4的情况,将消耗数小时甚至数天,这里就不做仿真了,由于,本系统主要是研究非规则,所以,我们讨论了不同迭代次数的性能图,其效果如下所示:

     

     

     

     

     

     

    对比非规则与规则LDPC,其性能对比如下所示:

    显然,非规则性能比规则性能更好,且迭代次数越多,性能越好。

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • ldpc matlab代码LDPC-MATLAB-代码 用于闪存的 LDPC 用法 只需在此目录中运行ldpc_demo0.m代码即可获得 ldpc 编码/解码结果。
  • LDPC编码Verilog代码

    2019-08-25 14:42:31
    LDPC编码Verilog代码 LDPC编码Verilog代码
  • LDPC简介 LDPC的BP译码算法 各参数对LDPC码性能的影响 ;LDPC历史;什么是LDPC码;Tanner图;Hnpq=824;LDPC译码; 建立在Tanner上的LDPC码其BP译码的每次迭代包括两步校验节点的处理和变量节点的处理 在每次迭代中 ,所有...
  • ldpc matlab代码LDPC-Matlab LDPC 码的编码 codeWord = ldpcEncoding(H,u): 输入变量: H:奇偶校验矩阵。 u:信息位向量。 输出变量: 码字:为信息位向量 u 生成的码字。 史莱玛尼·贾梅尔 (2020)。 LDPC 编码器...
  • 完成LDPC误码率仿真M文件调用SIMULINKMATLAB完成LDPC误码率仿真M文件调用SIMULINKMATLAB完成LDPC误码率仿真M文件调用SIMULINKMATLAB
  • LDPC

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

    LDPC码简介

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

    1.1.1 LDPC码的特点

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

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

    1.1.2 LDPC码的构造

    构造二进制LDPC码实际上就是要找到一个稀疏矩阵H作为码的校验矩阵,基本方法是将一个全零矩阵的一小部分元素替换成1,使得替换后的矩阵各行和各列具有所要求的数目的非零元素。如果要使构造出的码可用,则必须满足几个条件,分别是无短环,无低码重码字,码间最小距离要尽可能大。

    1.1.3 Tanner图

    LDPC码常常通过图来表示,而Tanner图所表示的其实是LDPC码的校验矩阵。Tanner图包含两类顶点:n个码字比特顶点(称为比特节点),分别与校验矩阵的各列相对应和m个校验方程顶点(称为校验节点),分别与校验矩阵的各行对应。校验矩阵的每行代表一个校验方程,每列代表一个码字比特。所以,如果一个码字比特包含在相应的校验方程中,那么就用一条连线将所涉及的比特节点和校验节点连起来,所以Tanner图中的连线数与校验矩阵中的1的个数相同。以下图是矩阵

    的Tanner图,其中比特节点用圆形节点表示,校验节点用方形节点表示,加黑线显示的是一个6循环:

    Tanner图中的循环是由图中的一群相互连接在一起的顶点所组成的,循环以这群顶点中的一个同时作为起点和终点,且只经过每个顶点一次。循环的长度定义为它所包含的连线的数量,而图形的围长,也可叫做图形的尺寸,定义为图中最小的循环长度。如上图中,图形的尺寸,即围长为6,如加黑线所示。

    1.2 LDPC编码

    方法一:设H=[A | B],对H进行高斯消元可得到H=[I| P],设编码完成的码字为u=[c| s],其中c为监督位,s为信息位。因为H*u' = u*H' = 0,可以得到I*c' + P*s' = 0 即 I*c' = P*s' (在GF(2)上),从而可求 c' = P*s'。如果高斯消元过程中进行了列交换,则只需记录列交换,并以相反次序对编码后的码字同样进行列交换即可。解码时先求出u,再进行列交换得到u1=[c| s],后面部分即是想要的信息。

    方法一示例:

     

    方法二:首先推导出根据校验矩阵直接编码的等式。将尺寸为m*n校验矩阵H写成如下形式:H=[H1 | H2],其中H1矩阵的大小为m*k,H2的大小为m*m,设编码完成的码字为u=[s | p],s为信息位,p为监督位。因为H*u' =u*H' = 0求得p*H2'=s*H1',最后得p=s* H1'* (H2')-

    上述两种方法可以不通过生成矩阵而直接由校验矩阵进行编码的等式,一切只依赖校验矩阵的编码都是通过这两个式子实现的。但方法二要考虑H2是否满秩(可逆)。

    1.3 LDPC码H矩阵的构造

    规则的LDPC码和非规则的LDPC码

    如果校验矩阵中各行非零元素的个数相同,各列中非零元素的个数也相同,这样的LDPC码称为规则码,与规则码对照,如果校验矩阵的各行中非零元素的个数不同或各列中非零元素个数不同,此时的LDPC码称为非规则的LDPC码。

    1.3.1 非规则的LDPC码

    构造方法:码率R=M/N=0.5,构造的H矩阵列重固定,而行重是随机的。下面通过一个大小为6*12,列重为2的H矩阵来说明。因为列重固定为2,所以其列坐标集合为[1,1,2,2,3,3,4,4…….12,12],而行坐标可以随机构造。

    1.       先构造一个6*12,每一列为1到6随机排列的矩阵onesInCol。

    2.       选取onesInCol的前2行(和列重一致),如上图所示。

    3.        将所选取的矩阵按列依次排列如下

     

    4.       构造矩阵tmp

    5.       矩阵tmp重排成c1

    6.       full 把稀疏矩阵转换为满阵显示, sparse 创建稀疏矩阵生成M*N阶稀疏矩阵H在以向量r1和c1为坐标的位置上的对应元素值为向量1的对应值。

    1.3.2 规则的LDPC 码

    对于码率R=0.5的规则的LDPC码其行重与列重有关,行重是列重的2倍。以6*12的H矩阵为例,假设其列重为2,每列1的个数为2,总的1的个数为2*12=24,H矩阵有6行,行重相同则每行1的个数为24/6=4,即行重为4。假设其列重为3,其行重为6。

    构造方法:与构造行重类似,行重列重固定之后,其在矩阵中的位置坐标集合固定,如列重为2,行重为4,列坐标集合为[1,1,2,2,3,3,…..],行坐标集合为[1,1,1,1,2,2,2,2,3,3,3,3,……],下面考虑的就是如何将行列坐标组合起来而不重复。这里采用的是保持行坐标集合不变,列坐标集合打乱重排。以构造大小5*10,列重为2,行重为4的H矩阵为例说明。

    1.       先构造一个5*10,每一列为1到5随机排列的矩阵onesInCol。

    2.       选取onesInCol的前2行(和列重一致)构成1*20的矩阵

    3.       将r按升序排列得到

    4.       记录下排列前的位置索引

    5.       因为列坐标集合为[1,1,2,2,3,3,4,4,……9,9,10,10],将列坐标集合根据上面的位置索引重新排列,得到c

     

    6.       行坐标集合如下,与列坐标一一对应,确定矩阵H中1的位置。

    7.       最后结果

     

    1.3.3 LDPC码的环

    在 LDPC 码的 Tanner 图中,从一个顶点出发,经过不同顶点后回到同一个顶点的一些“边”组成的回路称为“环”。经过的边的个数称为环的长度。所有环中周长最小的环称为 LDPC码的围长(girth) ‎。

    Tanner 图中的环不可避免的会对译码结果造成非常大的干扰。由于迭代概率译码会使信息在节点间交互传递,若存在环,从环的某一个节点出发的信息会沿着环上的节点不断传递并最终重新回到这个节点本身,从而使得节点自身信息不断累加,进而使得译码的最终结果失败的概率变大。显然,环长越小,信息传递回本身所需走的路径就越短,译码失败的概率就变得越高。Tanner 图形成一个环至少需要 4 个节点组成4 条相连的边,即环长最小为4,这类短环对码字的译码结果干扰最大。定义 LDPC码的行列(RC)约束为:两行或两列中不存在元素 1 的位置有 1 个以上相同的情况。显然,满足 RC 约束的 LDPC 码最低就是 6 环,去除了4 环的干扰。由于4环的检测以及避免最为简单并且必要,因此绝大部分构造方法都会满足 RC 约束。而构造大圈长的码字则需要精确的设计。

     

    1.4 LDPC译码

    Gallager 在描述 LDPC 码的时候,分别提出了硬判决译码算法和软判决译码算法两种。经过不断发展,如今的硬判决算法已在 Gallager 算法基础上进展很多,包含许多种加权比特翻转译码算法及其改进形式。硬判决和软判决各有优劣,可以适用于不同的应用场合。

    1.4.1 比特翻转算法(BF)

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

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

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

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

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

    BF 算法的理论假设是若某个比特不满足校验方程的个数最多,则此比特是最有可能出错的比特,因此,选择这个比特进行翻转。BF 算法舍弃了每个比特位的可靠度信息,单纯的对码字进行硬判决,理论最为简单,实现起来最容易,但是性能也最差。当连续两次迭代翻转函数判断同一个比特位为最易出错的比特时,BF 算法会陷入死循环,大大降低了译码性能。

    图50*100

    图 500*1000

    1.4.2 置信传播算法(BP)

    置信传播(Belief Propagation)译码算法是消息传递(Message Passing)算法在 LDPC译码中的运用。消息传递算法是一个算法类,最初运用于人工智能领域,人们将其运用到 LDPC 码的译码算法中,提出了LDPC 码的置信传播算法。置信传播算法是基于 Tanner 图的迭代译码算法。在迭代过程中,可靠性信息,即“消息”通过 Tanner图上的边在变量节点和校验节点中来回传递,经多次迭代后趋于稳定值,然后据此进行最佳判决。

    置信传播译码算法的基本流程如下:

    在迭代前,译码器接收到信道传送过来的实值序列y=(y1,y2,….yn),所有变量节点bi接收到对应的接收值yi。

    第一次迭代:每个变量节点给所有与之相邻的校验节点传送一个可靠性消息,这个可靠性消息就是信道传送过来的值;每个校验节点接收到变量节点传送过来的可靠性消息之后,进行处理,然后返回一个新的可靠性信息给与之相邻的变量节点,这样就完成了第一次迭代;此时可以进行判决,如果满足校验方程,则不需要再迭代,直接输出判决结果,否则进行第二次迭代。

    第二次迭代:每个变量节点处理第一次迭代完成时校验节点传送过来的可靠性消息,处理完成后新的消息发送给校验节点,同理,校验节点处理完后返回给变量节点,这样就完成了第二次迭代。完成后同样进行判决,如果满足校验方程则结束译码,否则如此反复多次迭代,每次都进行判决,直到达到设定的最大迭代次数,译码失败。在每次迭代过程中,无论是变量节点传送给校验节点的信息或者校验节点传送给变量节点的信息,都不应该包括前次迭代中接收方发送给发送方的信息,这样是为了保证发送的信息与接收节点已得到的信息相互对立。

     

                                                                                             图50*100

    图500*1000

     

     

    结束语

    目前LDPC码研究领域的主要工作集中在译码算法的性能分析、编码方法、码的优化算法等,经过研究人员的努力,LDPC码的研究取得很大进展,但仍有许多问题需要进一步研究:

    (1)LDPC码校验矩阵的构造,尽管在构造最优的LDPC码方面取得了一些进步,但目前还没有一套系统的办法来构造所需要的好码,特别是在码字长度有限、码率一定的条件下,构造性能优异的好码是一个非常具有挑战性的课题。

    (2)LDPC编码系统的联合优化设计,将编码技术与调制技术、均衡技术、时空编码技术、OFDM技术结合进行性能优化是当前及将来的发展方向之一。

    (3)无线衰落信道及MIMO技术下LDPC码的性能分析方法及优化设计准则。目前LDPC码字的优化设计主要在加性高斯白噪声信道下得到的,而无线衰落信道下,特别是时变信道非线性环境下码字的性能分析方法、优化设计准则和信道估计的影响也是非常关键的课题,需要进一步的研究探索。

    此外,基于LDPC码的链路自适应技术,LDPC码在集成通信网物理层、应用层联合优化系统中的应用,LDPC码在无线局域网和深空宇航中的应用,基于LDPC码的图像传输、图像数字水印系统中的应用以及寻找更适合硬件实现的LDPC码编译码方法等都是非常值得研究的课题。

    展开全文
  • LDPC MATLAB仿真代码

    2019-08-30 20:39:17
    LDPC MATLAB仿真代码 This LDPC software is intended as an introduction to LDPC codes computer based simulation. 仿真
  • nonbinary LDPC

    2014-04-14 10:48:59
    多元LDPC码的硬件设计及译码算法 非常实用,是英文文献
  • ldpc matlab代码LDPC解码器 在面向对象的 Matlab 中编码的 LDPC 解码器。
  • ldpc ms算法

    2018-12-10 10:21:36
    ldpc的译码迭代算法,这里仅包含ms算法,下载请注意。
  • ldpc编译码

    2017-10-08 19:41:04
    多进制纠错码LDPC编译码,matlab算法,算法算法;多进制纠错码LDPC编译码,matlab算法,算法算法
  • ldpc迭代算法

    2018-12-10 10:20:24
    ldpc译码迭代matlab译码算法的LLR译码算法,这里只包含llr算法注意
  • LDPC 算法 Paper

    2018-04-13 15:36:47
    LDPC 5G Decoder Encoder Modulation 译码编码算法与架构英文
  • ldpc soft decoder

    2018-10-14 14:42:10
    ldpc soft decoder,包括编译码程序,有注释,可直接用于AWGN信道
  • LDPC-1.rar

    2020-10-11 22:33:52
    Method of decoding LDPC code for producing several different decoders using parity-check matrix of LDPC code and LDPC code system including the same Low-density parity-check (LDPC) encode using an ...
  • LDPC-3.rar

    2020-10-11 22:33:27
    Method of decoding LDPC code for producing several different decoders using parity-check matrix of LDPC code and LDPC code system including the same Low-density parity-check (LDPC) encode using an ...
  • LDPC-2.rar

    2020-10-11 22:28:08
    Method of decoding LDPC code for producing several different decoders using parity-check matrix of LDPC code and LDPC code system including the same Low-density parity-check (LDPC) encode using an ...
  • LDPC 卷积码基于 Feltstrom 和 Zigangirov 的论文:“Periodic Time-Varying Convolutional Codes with Low-Density Parity-Check Matrix”。 LDPC-CC Matlab 文件: makeBaseLdpccc.m 编码Ldpccc.m 奇偶校验矩阵...
  • LDPC-开源

    2021-04-30 23:08:17
    LDPC(低密度奇偶校验码)工具的集合。 包括:代码构造; 密度演化; 解码算法; 周长平均计数器; 停止设定和错误楼层等
  • LDPC project.rar

    2019-06-13 14:47:41
    码长 列重 编码 误码性能 LDPC码的编码方法及其实现本文首先回顾了数字通信系统和信道编码的内容,简单了解了LDPC编码的研究现状和发展前景之后,从第二章开始从校验矩阵构造方法、LDPC编码方法、LDPC译码方法这三个...
  • turbo ldpc

    2011-04-06 10:11:46
    ldpc的系统介绍,关于ldpc的编码解码原理及技术介绍

空空如也

空空如也

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

ldpc