精华内容
下载资源
问答
  • 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

    千次阅读 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码的性能,文章从校验矩阵、Tanner图、BP译码算法等方面将两者进行有效的分析,并结合具体的Monte Carlo 仿真实验,得出多元LDPC码的性能确实优于等长度码长的二元LDPC码
  • 5G NR LDPC码(1)—— LDPC码设计原理

    千次阅读 2020-01-08 16:20:33
    5G NR LDPC码(1)—— LDPC码设计原理 5G NR中规定了控制消息和广播信道用Polar码,数据传输用LDPC码的方案。 LDPC属于线性分组码,常用校验矩阵或者Tanner图来描述。 用校验矩阵来描述LDPC码,可以清晰的...

    5G NR中规定了控制消息和广播信道用Polar码,数据传输用LDPC码的方案。

    1. LDPC属于线性分组码,常用校验矩阵或者Tanner图来描述。
    • 校验矩阵来描述LDPC码,可以清晰的看到信息比特和校验比特之间的约束关系,在编码过程中使用较多。
    • Tanner图把校验节点和变量节点分为两个集合,然后通过校验方程的约束关系连接校验节点和变量节点。如果为1,则有连线。圆圈为变量节点,方框代表校验方程。
    1. LDPC为低密度奇偶校验编码,校验矩阵一般是一个稀疏矩阵,即其中只有一小部分元素是1,其余元素皆为0。对于校验矩阵为H的LDPC码,其码字c满足Hc=0。定义列重为 i 的列所占的比例为vi,行重为 i 的行所占的比例为hi,称为度分布
    2. LDPC码基于消息传递算法进行译码,校验矩阵的稀疏性保证了译码算法复杂度随着码长线性增长。

    LDPC码设计原理

    ​ LDPC码的校验矩阵或Tanner图决定了其性能。消息传递算法可以理解为在Tanner图上传递消息的过程,这些消息代表码字中编码比特值的概率分布。通过跟踪Tanner图上传递的消息,采用密度演进算法可以估计LDPC码的性能。另一方面,在实际应用中,LDPC码必须以低复杂度的描述和编译码来实现,支持灵活的资源调度和重传。随着LDPC码技术的发展,一些重要的技术特性涌现以满足这些需求。比如,RL(Raptor Like)结构的出现使得LDPC码可以很好的支持多码率、多码长以及增量冗余混合自动重传请求(IR-HARQ,Incremental Redundancy Hybrid Automatic Repeat request);准循环(Quasi-Cyclic)结构使LDPC码的低复杂度、高吞吐的编译码器易于实现。针对这些关键技术,本节介绍LDPC码的设计原理。

    1. 消息传递算法与密度演进

    (1)消息传递算法

    • 将Tanner图加以推广,可以得到更一般的因子图,用来描述多变量函数的结构,校验节点在因子图中称为函数节点,如果变量节点是某个因子函数(检验方程)的自变量,那么在因子图上各变量节点和函数节点之间通过一条边连接。
    • 求解边缘函数时,利用因子图将一个复杂任务分解成多个子任务,每个子任务对应到因子图上的一个函数节点,这使得计算时不需要因子图其他部分的消息,且传送其计算结果仅由这些局部函数的自变量来承担,从而简化计算。计算边缘函数需要计算乘积和求和,所以基于因子图的这种计算边缘函数的算法也叫做和积(SP,Sum-Product)算法
    • 在LDPC码的译码过程中,消息传递算法计算的是每个比特的后验概率(Posterior Probability),输入是来自于解调模块的各比特的先验概率(Prior Probability),传递的是编码比特的概率分布,如LLR。对于无环的因子图,一次消息传递就可以求出所有变量节点的边缘函数。对于有环的因子图,需要通过多次迭代计算,才能逼近变量节点的边缘函数。 LDPC码的校验矩阵中一般都有环存在,所以消息传递算法是一种次优的逼近最大后验概率(MAP,Maximum A Posteriori)的算法。在设计LDPC码校验矩阵的过程中,增大最小环的环围(girth) ,使得消息传递译码过程中传递消息的相关度降低,是提升LDPC码性能的技术之一。

    (2)密度演进

    • 密度演进算法通过跟踪消息传递过程,可以评估校验矩阵的性能,以指导LDPC码的设计。在消息传递算法中,变量节点到校验节点之间传递的消息是编码比特为1或者0的LLR,其概率密度函数可以表征LDPC码的性能。

    • 假设所有的消息概率密度分布是相互独立的,即信道是无记忆的。根据变量节点向校验节点的消息传递公式,输出消息的概率密度函数可以通过卷积获得。

    • 由于密度演进算法需要非常复杂的概率密度函数计算,往往假设LLR服从高斯分布。由于高斯分布的卷积仍然是高斯分布,这近似 使得密度演进算法只需要追踪随机变量均值和方差的变化即可。密度演进算法可以计算出服从某种度分布的校验矩阵的译码门限,进而评估这种度分布情况下LDPC码的性能。

    2. 速率匹配/HARQ

    为了支持灵活调度和提升系统吞吐量,LDPC码需要支持多码率编码和IR-HARQ

    • 一种方案与Turbo码类似,即先编码得到一个低码率(如LTE Turbo码采用1/3) 的母码,然后通过打孔实现高码率。当需要重传时,重传打孔比特以实现IR-HARQ。该方案使LDPC码和打孔方案的设计复杂度都很高。
    • LT码和Raptor 码的出现提供了另一种方案:Raptor-Like 结构的LDPC码(RL-LDPC)。RL-LDPC码先设计一个高码率的校验矩阵,然后通过扩展校验矩阵以增量产生校验比特,实现多码率编码,重传扩展的校验比特即实现了对IR-HARQ的支持。
    • 在LDPC码的设计中,瀑布区(Waterfal Region,此区域内译码错误奉随信噪比增加快速降低)的性能和错误平层是一对矛盾。 往往瀑布区较好的矩阵具有较高的错误平层,具有较低错误平层的矩阵瀑布区性能较差。

    3. QC-LDPC码

    支持多种信息块大小是LDPC码实用化的另一个设计要求。

    • 如果直接根据信息块大小设计LDPC码的校验矩阵,则需要非常多个校验矩阵以满足5GNR调度的信息块颗粒度的需求,这对于LDPC码的描还和编译码实现都不可行。QC-LDPC 码的提出使这个问题得以解决。

    • QC-LDPC码是一类结构化的 LDPC码,其校验矩阵可以分解为ZxZ的全零矩阵循环移位矩阵。其中循环移位矩阵通过对ZxZ的单位矩阵向右循环移位获得。扩展之前的矩阵称为基矩阵[对应的Tanner图称为基图(BG, Base Graph)],只包含元素“0”和“I”。“0” 的位置替换为ZxZ的全零矩阵,“1” 的位置替换为ZXZ的循环移位矩阵。

    • QC-LDPC码的设计

      首先确定一个mxn的稀疏矩阵作为BG,然后复制这个BG,复制的倍数为Z,即矩阵变为mZxnZ。复制之后,对变量节点和校验节点之间的连线进行交织(这里是循环移位),构成校验矩阵。已经证明, 通过优化设计mxn的BG,可以保证扩展之后的mZxnZ校验矩阵拥有较好的性能。BG的设计过程可以采用常规的LDPC码设计方法,比如通过密度演进算法挑选具有较好译码门限的BG。

    • QC-LDPC码的优点

      第一,通过分析BG就可以对校验矩阵的性能有大致的了解。

      第二,描述复杂度低。对于传统的LDPC码,当其需要支持较长的消息序列时,校验矩阵的规模巨大。然而对于QC-LDPC码,只需要描述BG中非0元素的位置和相应的循环移位大小即可。

      第三,编译码复杂度低。由于其采用ZxzZ的循环移位矩阵,所以编码时可以实现并行度为Z的编码过程,译码时可以实现Z个校验方程相关消息的同时更新和传递,可以大大提升LDPC码译码器的吞吐量。

    展开全文
  • LDPC码编译码原理及算法主要内容1LDPC码简介2LDPC码编码3LDPC码译码LDPC码简介定义 LDPC码是一种校验矩阵H中只有很少的元素为1大部分元素都是0的一种线性分组码稀疏性表示方法二分图分类按照校验矩阵行列重量分规则...
  • LDPC码的PEG构造算法

    2021-01-22 21:00:15
    LDPC码的PEG算法Matlab code LDPC码的PEG算法Matlab code LDPC码的PEG算法Matlab code LDPC码的PEG算法Matlab code
  • LDPC码编译码matlab代码

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

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

    本文主要是解读Gallager关于LDPC码的论文《Low-Density Parity-Check Codes》,也记录了一些论文里不包含但是很重要的相关资料。
    最近研究点涉及到LDPC编码,将学习到的内容在此博客中记录,供学习交流,有错误之处还请指正。
    持续更新中。。。

    Gallager论文解读:低密度奇偶校验码

    Low-Density Parity-Check Codes (LDPC)

    简介

    LDPC码是麻省理工学院Robert Gallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农限,且描述和实现简单,易于进行理论分析和研究,译码简单且可实行并行操作,适合硬件实现。

    定义:(来自百度LDPC码
    任何一个 ( n , k ) (n,k) (nk) 分组码,如果其信息元与监督元之间的关系是线性的,即能用一个线性方程来描述的,就称为线性分组码。
    低密度奇偶校验码图(LDPC码)本质上是一种线形分组码,它通过一个生成矩阵 G G G 将信息序列映射成发送序列,也就是码字序列。对于生成矩阵 G G G,完全等效地存在一个奇偶校验矩阵 H H H,所有的码字序列 C C C构成了 H H H 的零空间 (null space),即 。

    LDPC 码的奇偶校验矩阵H是一个稀疏矩阵,相对于行与列的长度,校验矩阵每行、列中非零元素的数目(我们习惯称作行重、列重)非常小,这也是LDPC码之所以称为低密度码的原因。由于校验矩阵H的稀疏性以及构造时所使用的不同规则,使得不同LDPC码的编码二分图(Taner图)具有不同的闭合环路分布。而二分图中闭合环路是影响LDPC码性能的重要因素,它使得LDPC码在类似可信度传播(Belief ProPagation)算法的一类迭代译码算法下,表现出完全不同的译码性能。
    当H的行重和列重保持不变或尽可能的保持均匀时,我们称这样的LDPC码为正则LDPC码,反之如果列、行重变化差异较大时,称为非正则的LDPC码。研究结果表明正确设计的非正则LDPC码的性能要优于正则LDPC。根据校验矩阵H中的元素是属于 G F ( 2 ) GF(2) GF(2) 还是 G F ( q ) ( q = 2 p ) GF(q)(q=2p) GF(q)(q=2p),我们还可以将LDPC码分为二元域或多元域的LDPC码。研究表明多元域LDPC码的性能要比二元域的好。

    论文摘要部分

    Summary–A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed number j ≥ 3 j \geq 3 j3 of 1’s and each row contains a small fixed number k > j k > j k>j of 1’s. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixed j j j. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixed j j j.
     A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is decribed. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length.
     For j > 3 j > 3 j>3 and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound.

    1. 数据传输编码

    LDPC编码属于信道编码,本质是为了提高信道的可靠性
    LDPC是一种线性分组码,码字由信息位和校验位组成;

    属于信道编码
    码字 = 信息位 + 校验位

    主要测试以下两种信道下的编码效果:

    1. BSC (Binary Symmetric Channel):二进制对称信道
    2. White Gaussian Noise Channel:高斯白噪声信道

    低密度奇偶校验码是奇偶校验码的改进。

    • 问:为什么会出现LDPC?
    • 答:因为奇偶校验码的解码很难应用,而使用低密度则有很合适的解码方案。虽然LDPC码不是最好的码,但是由于存在很简单的解码方案,弥补了不是最优码的缺憾。

    对比:奇偶校验码和低密度奇偶校验码?
    包括:编码方式对比、解码方式对比、编码效果对比、数据率对比等

    2. 编码

    LDPC码的矩阵形式可以用 ( n , j , k ) (n, j, k) (n,j,k)表示

    ( n , j , k ) (n, j, k) (n,j,k) n n n表示码长, j j j表示矩阵每列1的个数, k k k表示矩阵每行1的个数。

    下图是奇偶校验矩阵的一个案例:
    校验矩阵示例
    图二是LDPC码 ( 20 , 3 , 4 ) (20, 3, 4) (20,3,4)的矩阵表示案例,虽然LDPC码的形式不是信息位和比特位组合的形式,但是可以通过一定的线性变换转换成那种形式:
    LDPC矩阵
    LDPC码虽然不是最好的码,但是该编码方案存在非常简单的解码方案,这弥补了它不是最好的码的缺憾。

    These codes are not optimum in the somewhat artificial sense of minimizing probability of decoding error for a given block length, and it can be shown that the maximum rate at which these codes can be used is bounded below channel capacity. However, a very simple decoding scheme exists for low-density codes, and this compensates for their lack of optimality.

    Gallager码的构造

    Gallager码 ( n , j , k ) (n, j, k) (n,j,k)的构造步骤:

    1. 将码集矩阵其分成 j j j 个子矩阵,每个矩阵每列只有 1 个1;
    2. 第一个子矩阵中的1成下降趋势构成,如Fig. 2;
    3. 其它子矩阵由第一个子矩阵通过随机列置换构成。

    除了Gallager的构造方法,还有很多其它构造方法,如下三角法构造。

    Gallager说这种码集的构造方法能够证明含有两个有意思的结果:

    1. 码距
    2. 解码错误的概率

    There are two interesting results that can be proven using this ensemble, the first concerning the minimum distance of the member codes, and the second concerning the probability of decoding error.

    请思考:为什么使用这种方式构造?
    见如下解读:
    (未完待续。。。)

    3. 解码

    Gallager主要提出了两种解码方案:

    1. Probabilistic Decoding
      该方案简单,但是只能用于BSC并且码率远小于信道容量的情况;
    2. Probability of Error Using Probabilistic Decoding
      从信道输出的后验概率中解码。

    在第一种解码方案中:该方案只适用于校验集比较小的情况,此时解码解码过程才合理,因为大部分校验集要么只有一个不满足要么都被满足。解码器计算所有的校验矩阵,当某一位数据位使得多个校验矩阵不满足时,则改变此数据位的值;使用此改变后的值继续计算校验矩阵,直到所有的校验矩阵都满足。

    In the first decoding scheme, the decoder computes all the parity checks and then changes any digit that is contained in more than some fixed number of unsatisfied parity-check equations. Using these new values, the parity checks are recomputed, and the process is repeated until the parity checks are all satisfied.

    当出错的数据位d超过1位该怎么办?见如下分析:
    校验集节点可如下Fig. 6表示,选择一个出错的数据位d,将其作为根节点,与d相关联的边表示包含d节点的校验矩阵;在子节点下重复此过程,直到将全部校验方程表述完为止

    节点:码字
    边:校验矩阵

    此图中包含两层节点,假设节点d和处于第一层的部分节点传输错误,则第二层中无错误的节点和校验矩阵能够解码出第一层的错误节点;重复此过程,节点d能够在第二次迭代后被成功解码。
    校验集的树形表示

    解码方案一:概率解码 Probabilistic Decoding

    理论分析

    已知接收到的符号为 { y } \{y\} {y} 且 发送的码字d满足第 j j j 个校验方程 S S S,则令码字d为1的概率表示如下:
    P r [ x d = 1 ∣ { y } , S ] P_r[x_d=1 | \{y\}, S] Pr[xd=1{y},S]

    定理1: P d P_d Pd 表示已知接收的码字则第 d d d 位为1的概率, P i l P_{il} Pil 表示接收的码字的第 l l l 位满足第 i i i 个校验方程的概率, S S S 表示发送的码字满足所有的校验方程,则:
    P r [ x d = 0 ∣ { y } , S ] P r [ x d = 1 ∣ { y } , S ] = 1 − P d P d ∏ i = 1 j 1 + ∏ l = 1 k − 1 ( 1 − 2 P i l ) 1 − ∏ l = 1 k − 1 ( 1 − 2 P i l ) ( 1 ) \frac{ P_r[x_d=0 | \{y\}, S] } { P_r[x_d=1 | \{y\}, S] } = \frac{1 - P_d}{P_d} \prod_{i=1}^{j} \frac{ 1 + \prod_{l=1}^{k-1} (1-2P_{il}) }{ 1 - \prod_{l=1}^{k-1} (1-2P_{il}) } \qquad\qquad\qquad(1) Pr[xd=1{y},S]Pr[xd=0{y},S]=Pd1Pdi=1j1l=1k1(12Pil)1+l=1k1(12Pil)1

    为了证明定理1,我们需要如下引理。
    引理1:设 m m m 长独立二元序列中第 l l l 位是1的概率为 p l p_l pl,则序列中含偶数个1的概率为:
    1 + ∏ l = 1 m ( 1 − 2 P l ) 2 . . . . . . . . . . P 偶 数 个 1 \frac{1 + \prod_{l=1}^m (1-2P_l)}{2} ..........P_{偶数个1} 21+l=1m(12Pl)..........P1
    含奇数个1的概率为:
    1 − ∏ l = 1 m ( 1 − 2 P l ) 2 . . . . . . . . . . P 奇 数 个 1 \frac{1 - \prod_{l=1}^m (1-2P_l)}{2} ..........P_{奇数个1} 21l=1m(12Pl)..........P1

    引理1证明:设 f ( t ) = ∏ l = 1 m [ ( 1 − p l ) + p l t ] f(t) = \prod_{l=1}^m [(1-p_l) + p_lt] f(t)=l=1m[(1pl)+plt],将其展开成 t t t 的多项式形式。在 f ( t ) f(t) f(t) 的展开式中, t 2 k t^{2k} t2k 项的系数为 m m m 长独立二元序列中出现 2 k 2k 2k 个1的概率。 t 2 k + 1 t^{2k+1} t2k+1 项的系数为n长独立序列中出现 2 k + 1 2k+1 2k+1 个1的概率。因此, t = 1 t=1 t=1 时, f ( t ) f(t) f(t) 中偶此项部分的和就是 m m m 长独立二元序列中含有偶数个1的概率,该值可用下式计算:
    f ( 1 ) + f ( − 1 ) 2 = ∏ l = 1 m [ ( 1 − p l ) + p l ] + ∏ l = 1 m [ ( 1 − p l ) − p l ] 2 = 1 + ∏ l = 1 m ( 1 − 2 p l ) 2 \frac{f(1) + f(-1)}{2} = \frac{{ \prod_{l=1}^m [(1-p_l) + p_l] } + { \prod_{l=1}^m [(1-p_l) - p_l] }}{2} \\ = \frac{1 + \prod_{l=1}^m (1 - 2p_l)}{2} 2f(1)+f(1)=2l=1m[(1pl)+pl]+l=1m[(1pl)pl]=21+l=1m(12pl)
    含奇数个1的概率为:
    1 − f ( 1 ) + f ( − 1 ) 2 = 1 − ∏ l = 1 m ( 1 − 2 p l ) 2 1 - \frac{f(1) + f(-1)}{2} = \frac{1 - \prod_{l=1}^m (1 - 2p_l)}{2} 12f(1)+f(1)=21l=1m(12pl)
    引理1证毕。

    定理1证明:根据Bayes准则有
    P r [ x d = 0 ∣ { y } , S ] P r [ x d = 1 ∣ { y } , S ] = ( 1 − P d P d ) ( P r [ S ∣ x d = 0 , { y } ] P r [ S ∣ x d = 1 , { y } ] ) ( 2 ) \frac{ P_r[x_d=0 | \{y\}, S] } { P_r[x_d=1 | \{y\}, S] } = ( \frac{1 - P_d}{P_d} ) ( \frac{ P_r[S | x_d=0, \{y\}] }{ P_r[S | x_d=1, \{y\}] } ) \qquad\qquad\qquad(2) Pr[xd=1{y},S]Pr[xd=0{y},S]=(Pd1Pd)(Pr[Sxd=1,{y}]Pr[Sxd=0,{y}])2
    (注: P d P_d Pd与迭代次数无关,由信道特性决定。 )
    已知 x d = 0 x_d = 0 xd=0 d d d 所在的校验方程满足当且仅当该方程中其它 ( k − 1 ) (k-1) (k1) 个位置含有偶数个1,由于所有的数据都是统计独立的,因此,所有的 j j j 个校验方程都被满足的概率就是单个校验方程被满足的概率。由引理1可得:
    P r [ S ∣ x d = 0 , { y } ] = ∏ i = 1 j [ 1 + ∏ l = 1 k − 1 ( 1 − 2 p i l ) 2 ] ( 3 ) P_r[S | x_d=0, \{y\}] = \prod_{i=1}^j [\frac{1 + \prod_{l=1}^{k-1} (1 - 2p_{il})}{2}] \qquad\qquad\qquad(3) Pr[Sxd=0,{y}]=i=1j[21+l=1k1(12pil)]3
    同样的,
    P r [ S ∣ x d = 1 , { y } ] = ∏ i = 1 j [ 1 − ∏ l = 1 k − 1 ( 1 − 2 p i l ) 2 ] ( 4 ) P_r[S | x_d=1, \{y\}] = \prod_{i=1}^j [\frac{1 - \prod_{l=1}^{k-1} (1 - 2p_{il})}{2}] \qquad\qquad\qquad(4) Pr[Sxd=1,{y}]=i=1j[21l=1k1(12pil)]4
    定理1证毕。

    解码过程

    从上述结果可以看出,当层数很多时,解码很困难。但是,可以使用简单的迭代技术计算任意层的情况。

    Judging from the complexity of this result, it would appear difficult to compute the probability that the transmitted digit in position d is a 1 conditional on the received digits in two or more tiers of the tree in Fig. 6. Fortunately, however, the many-tier case can be solved from the l-tier case by a simple iterative technique.

    Gallager的分析如下:
    首先考虑只有两层的示例,根据第二层接收到的数据能够得出第一层每个数据为1的概率;然后,根据得到的第一层的数据,可以得到接收到的节点 d d d 为1的概率。这个过程的有效性取决于根据定理1得到的新增的 P i l P_{il} Pil 的独立性。通过归纳,可以根据任意层数的节点得出接收到的节点 d d d 为1的概率。
    对于每个节点 d d d 来说,使用公式(1)能够得出该节点更新后的概率;计算另一个节点的概率时,使用更新后的其它所有节点带入(1)中计算。如果能够成功解码,则随着迭代次数的增加,每个节点的概率都会趋于0或1(取决于发送的数据)。
    迭代过程有效性说明:
    迭代过程的有效性取决于公式(1)中的独立性假设被满足;当树节点出现环时,假设不成立。由于每层节点的个数都比上一层多 ( j − 1 ) ( k − 1 ) (j-1)(k-1) (j1)(k1) 个,当 m m m 特别小的时候,也就是码字很小,这个假设肯定会不成立。然而,基于合理的假设即相关性的影响比较小而且在某种程度上可以消除影响,独立性的假设可以被忽略;并且,即使在 m m m 层不再满足独立性,但是前 m − 1 m-1 m1 次迭代已经能够减少了每个节点 d d d 的不确定性程度,然后可以将 m − 1 m-1 m1 次后的结果作为原始接收序列重新迭代。

    迭代次数

    这种迭代方案的最重要的特点就是每个节点 d d d 的每次迭代计算和块长是独立的。因此,解码过程需要的平均迭代次数由一个与块长度的对数成比例的数量限制。

    实际计算的优化

    为了在实际计算中更方便地计算定理(1),通过对数似然比可以更方便地运算,如下:
    ln ⁡ 1 − P d P d = α d β d , ln ⁡ 1 − P i l P i l = α i l β i l \ln \frac{ 1 - P_d }{ P_d } = \alpha_d \beta_d, \ln \frac{ 1 - P_{il} }{ P_{il} } = \alpha_{il} \beta_{il} lnPd1Pd=αdβd,lnPil1Pil=αilβil
    ln ⁡ [ P r [ x d = 0 ∣ { y } , S ] P r [ x d = 1 ∣ { y } , S ] ] = α d ′ β d ′ \ln[\frac{ P_r[x_d=0 | \{y\}, S] }{ P_r[x_d=1 | \{y\}, S] }] = \alpha_d^{'} \beta_d^{'} ln[Pr[xd=1{y},S]Pr[xd=0{y},S]]=αdβd
    其中, α \alpha α 表示 s i g n sign sign 函数(如下图), β \beta β 表示对数似然比的量级。
    sign函数图
    【此处实际计算过程等待补充。。。】

    解码方案二:使用概率解码的错误概率 (Probability of Error Using Probabilistic Decoding)

    Case1: j = 3 j=3 j=3
    概率译码的数学分析比较困难,但可以很容易地推导出误差概率的一个很弱的界。
    假设BSC信道的交叉概率为 p 0 p_0 p0 和包含所有码字的 j = 3 j=3 j=3 ( n , j , k ) (n, j, k) (n,j,k) 码。参考Fig. 6,从上往下标记层数,即最上层为第0层,需要解码的数据 d d d 处于第 m m m 层。
    按照如下方式改变解码过程:如果与第一层中的某个数据相关的两个校验矩阵都不被满足,则改变此数据;将改变后的数据作为第一层的新数据,在第二层中重复此过程;在其它层中重复此过程,直到得出最后一层 d d d 的概率值。
    采用此过程,数据 d d d 的解码错误概率是方案一中迭代m次后得到的概率的上限。虽然两种方案都是基于m层数中的接收数据,但是方案一的概率译码(Probabilistic Decoding)总是从这些数据中选择最可能的决定。

    问:为什么方案二的错误概率是方案一的上限?
    答:因为方案一总是选择最可能的决定即改变使得校验方程不满足的个数最大的码字,而方案二选择的是当两个校验矩阵不满足的码字,明显方案一更准确。

    如果一个数据位接收错误的概率为 p 0 p_0 p0,那么校验方程不满足的概率为这个校验方程中其它 k − 1 k-1 k1个数据位中有偶数个数据不满足的概率,即 k − 1 k-1 k1个数据位中有偶数个1的概率,概率值为:
    1 + ( 1 − 2 p 0 ) k − 1 2 ( 7 ) \frac{ 1 + (1 - 2p_0)^{k-1} }{ 2 } \qquad\qquad\qquad(7) 21+(12p0)k17

    由于,只有当有两个与该数据位有关的校验矩阵不满足时,才纠正该错误,则第一层中数据位出现错误并且被纠正的概率可表示如下:
    p 0 [ 1 + ( 1 − 2 p 0 ) k − 1 2 ] 2 . . . . . P [ 对 ∣ 错 ] ( 8 ) p_0[ \frac{ 1 + ( 1-2p_0 )^{k-1} }{ 2 } ]^2 .....P[对|错]\qquad\qquad\qquad(8) p0[21+(12p0)k1]2.....P[]8
    类似的,则第一层中数据位本来正确但是被改变的概率可表示如下:
    ( 1 − p 0 ) [ 1 − ( 1 − 2 p 0 ) k − 1 2 ] 2 . . . . . P [ 错 ∣ 对 ] ( 9 ) (1 - p_0)[ \frac{ 1 - ( 1-2p_0 )^{k-1} }{ 2 } ]^2 .....P[错|对] \qquad\qquad\qquad(9) (1p0)[21(12p0)k1]2.....P[]9
    综合公式(8)和(9),通过此方案迭代后,第一层中某个数据的错误率( p 1 = p 0 − P [ 对 ∣ 错 ] + P [ 错 ∣ 对 ] p_1 = p_0 - P[对|错] + P[错|对] p1=p0P[]+P[])可表示如下:
    p 1 = p 0 − p 0 [ 1 + ( 1 − 2 p 0 ) k − 1 2 ] 2 + ( 1 − p 0 ) [ 1 − ( 1 − 2 p 0 ) k − 1 2 ] 2 ( 10 ) p_1 = p_0 - p_0[ \frac{ 1 + ( 1-2p_0 )^{k-1} }{ 2 } ]^2 + (1 - p_0)[ \frac{ 1 - ( 1-2p_0 )^{k-1} }{ 2 } ]^2 \qquad\qquad\qquad(10) p1=p0p0[21+(12p0)k1]2+(1p0)[21(12p0)k1]210
    分析迭代过程,简单表示(后面的公式13是更准确的表示) p i + 1 p_{i+1} pi+1 p i p_i pi 的关系如下:
    p i + 1 = p 0 − p 0 [ 1 + ( 1 − 2 p i ) k − 1 2 ] 2 + ( 1 − p 0 ) [ 1 − ( 1 − 2 p i ) k − 1 2 ] 2 ( 11 ) p_{i+1} = p_0 - p_0[ \frac{ 1 + ( 1-2p_i )^{k-1} }{ 2 } ]^2 + (1 - p_0)[ \frac{ 1 - ( 1-2p_i )^{k-1} }{ 2 } ]^2 \qquad\qquad\qquad(11) pi+1=p0p0[21+(12pi)k1]2+(1p0)[21(12pi)k1]211

    对于特别小的 p 0 p_0 p0,序列 [ p i ] [p_i] [pi] 收敛于0,通过数据图可得出此结论, p i + 1 p_{i+1} pi+1 p i p_i pi 的关系图如下:
    pi迭代收敛图
    从图中可知,
    0 < p i + 1 < p i ( f o r 0 < p i ≤ p 0 ) ( 12 ) 0 < p_{i+1} <p_i \quad\quad (for \quad 0 < p_i \le p_0) \qquad\qquad(12) 0<pi+1<pi(for0<pip0)12
    p i + 1 = p i ( f o r p i = 0 ) p_{i+1} = p_i \quad\quad (for \quad p_i = 0) pi+1=pi(forpi=0)

    Fig. 9展示了不同 k k k 所对应的最大的 p 0 p_0 p0 .
    最大的p0
    对于比较小的 p i p_i pi 来说,当 [ p i → 0 ] [p_i \to 0] [pi0] 时,(11)可以表示如下:
    p i + 1 ≈ p i 2 ( k − 1 ) p 0 p_{i+1} \approx p_i2(k-1)p_0 pi+1pi2(k1)p0
    (提示: lim ⁡ x → 0 ( 1 + x ) 1 x = e 且 e x = 1 + x + x 2 + . . . \lim_{x \to 0} (1 + x)^{\frac{1}{x}} = e 且e^x=1+x+x^2+... limx0(1+x)x1=eex=1+x+x2+...
    因此,当迭代次数 i i i 足够大时,
    p i ≈ c [ 2 ( k − 1 ) p 0 ] i p_i \approx c[2(k-1)p_0]^i pic[2(k1)p0]i
    c c c 是只取决于 i i i 的常数。由于树中独立层的数量随块长度呈对数增长,因此当块长度的负幂次较小时,解码错误的概率趋近于0。这种缓慢的接近0的方法似乎是译码方案修改和严格的独立性要求的结果,而不是概率译码作为一个整体的结果。
    我关于负幂次的理解:块长度的负幂次较小即 n − 1 n^{-1} n1 较小,即 n n n 较大,则独立层的数量越大,则可迭代的次数越大,则解码概率趋近于 0。
    若该理解有误还请批评指正,非常感谢。

    思考:对比上一解码方式,思考此方式中的缓慢接近于0

    Case2: j > 3 j>3 j>3
    同样的论证可以应用于每个数据位多余3个校验集的情况中,对于正整数 d d d ,当且仅当一个数据位不满足的校验方程个数大于等于 d d d 时才改变此数据位(在上面的案例中, d = 2 d=2 d=2 ),因此,使用与(11)相同的证明可得如下更一般的情况:
    p i + 1 = p 0 − p 0 ∑ l = b j − 1 ( j − 1 l ) [ 1 + ( 1 − 2 p i ) k − 1 2 ] l [ 1 − ( 1 − 2 p i ) k − 1 2 ] i − 1 − l + ( 1 − p 0 ) ∑ l = b j − 1 ( j − 1 l ) [ 1 − ( 1 − 2 p i ) k − 1 2 ] l [ 1 + ( 1 − 2 p i ) k − 1 2 ] i − 1 − l ( 13 ) p_{i+1} = p_0 - p_0 \sum_{l=b}^{j-1} \dbinom{j-1}{l} [ \frac{ 1 + ( 1-2p_i )^{k-1} }{ 2 } ]^l [ \frac{ 1 - ( 1-2p_i )^{k-1} }{ 2 } ]^{i-1-l} \\ \qquad\qquad\qquad+ (1-p_0) \sum_{l=b}^{j-1} \dbinom{j-1}{l} [ \frac{ 1 - ( 1-2p_i )^{k-1} }{ 2 } ]^l [ \frac{ 1 + ( 1-2p_i )^{k-1} }{ 2 } ]^{i-1-l} \qquad (13) pi+1=p0p0l=bj1(lj1)[21+(12pi)k1]l[21(12pi)k1]i1l+(1p0)l=bj1(lj1)[21(12pi)k1]l[21+(12pi)k1]i1l(13)
    因此,整数 d d d 可以用来最小化 p i + 1 p_{i+1} pi+1 。最小值的解就是满足下面不等式的最小的整数 d d d
    1 − p 0 p 0 ≤ [ 1 + ( 1 − 2 p i ) k − 1 1 − ( 1 − 2 p i ) k − 1 ] 2 b − j + l ( 14 ) \frac{ 1-p_0 }{ p_0 } \leq [\frac{ 1 + ( 1-2p_i )^{k-1} }{ 1 - ( 1-2p_i )^{k-1} }]^{ 2b-j+l } \qquad\qquad (14) p01p0[1(12pi)k11+(12pi)k1]2bj+l(14)
    从这个公式中可以看出, p i p_i pi 减小的时候, b b b 也减小。Fig. 10刻画了当 b b b 改变时, p i + 1 p_{i+1} pi+1 p i p_i pi 的关系,图中的断点表示 b b b 的变化,
    pi的迭代图

    对于足够小的交叉概率来说,随着迭代次数的增加,解码错误率趋于0的证明和之前的证明相同。但是,序列 [ p i → 0 ] [p_i \to 0] [pi0] 的渐进法和之前的证明不同。参照(14),如果 p i p_i pi 足够小,当 j j j 为偶数时, b b b j / 2 j/2 j/2 ;当 j j j 为奇数时, b b b ( j + 1 ) / 2 (j+1)/2 (j+1)/2 。使用上述定义的 b b b ,(13)可以如下扩展:
    p i + 1 = p 0 ( j − 1 j − 1 2 ) ( k − 1 ) ( i − 1 ) / 2 p i ( i − 1 ) / 2 + 高 阶 项 ( j 为 偶 数 ) ( 15 ) p_{i+1} = p_0 \dbinom{j-1}{\frac {j-1}{2}} (k-1)^{(i-1)/2}p_i^{(i-1)/2} + 高阶项 \qquad(j 为偶数)\qquad (15) pi+1=p0(2j1j1)(k1)(i1)/2pi(i1)/2+j15
    p i + 1 = ( j − 1 j / 2 ) ( k − 1 ) i / 2 p i i / 2 + 高 阶 项 ( j 为 奇 数 ) p_{i+1} = \dbinom{j-1}{j/2} (k-1)^{i/2}p_i^{i/2} + 高阶项 \qquad(j 为奇数)\qquad pi+1=(j/2j1)(k1)i/2pii/2+j
    据此,当选择了正的常数 C j k C_{jk} Cjk 和足够大的迭代次数 i i i 后,
    p i ≤ e x p [ − C j k ( j − 1 2 ) i ] ( j 为 偶 数 ) ( 16 ) p_i \leq exp[-C_{jk}(\frac{j-1}{2})^i] \qquad\qquad (j 为偶数)\qquad (16) piexp[Cjk(2j1)i]j(16)
    p i ≤ e x p [ − C j k ( j 2 ) i ] ( j 为 奇 数 ) p_i \leq exp[-C_{jk}(\frac{j}{2})^i] \qquad\qquad(j 为奇数)\qquad piexp[Cjk(2j)i]j

    两个解码方案的区别

    1. 方案一中根节点为第0层,方案二中根节点为第m层;但都是从上向下执行迭代过程。
    2. 方案二的错误概率是方案一的上限,因为方案一总是选择最可能的决定即改变使得校验方程不满足的个数最大的码字,而方案二选择的是当两个校验矩阵不满足的码字,明显方案一更准确。

    4. 实验结果

    [未完待续。。。]


    参考阅读:

    1. 论文原文:Cancellieri G . Low Density Parity Check Codes[J]. 1963.
    2. 和计算法:置信传播算法
    3. 参考教材:《现代编码理论 赵晓群编》,入门推荐阅读,LDPC码部分已拍照存为PDF,百度云下载
    展开全文
  • LDPC码MATLAB仿真实现

    2019-03-09 16:04:00
    LDPC码MATLAB仿真实现
  • LDPC码由于可以达到更高的译码吞吐量和更低的译码时延,可以更好适应高数据速率业务的传输,从而替代LTE的Turbo码,被采纳为5G NR数据的编码方案。 1. 基图 (BG, Base Graph) 5G NR采用QC-LDPC码,BG是整个LDPC码...
  • 主要内容 1 LDPC 简介 2 LDPC 编码 3 LDPC 译码 LDPC 简介 定义 LDPC 是一种校验矩阵 H 中只有很少的元素为1 大部分元素都是0的一种线性分组 稀疏性 表示方法二分图 ? 分类 ? 按照校验矩阵行列重量分 ? ...
  • LDPC码简介

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

    2012-10-31 10:18:50
    LDPC码介绍,主要讲述LDPC码的和积译码方法。
  • 多进制LDPC码编译码算法研究与硬件实现
  • 为了提高解码前传半双工中继通信系统的编码增益,提出了一种联合LDPC码编码结构及其度分布优化方法。该结构视信源和中继子码为联合LDPC码的一部分,目的端根据从信源和中继接收的消息进行联合译码,同时获得信源和中继...
  • QC-LDPC码源代码

    2021-02-09 15:00:18
    MATLAB中准循环LDPC码编码,避免4环,码长可变,编码速度快 MATLAB中准循环LDPC码编码,避免4环,码长可变,编码速度快
  • LDPC码编译码仿真

    2014-02-28 14:44:45
    LDPC码近似下三角法编码和SPA算法译码的matlab仿真 AWGN信道
  • 提出一种构造低密度奇偶校验码(LDPC码)的新方法—迭代填充法(IF法),在此基础上构造了IF-LDPC码.研究证明了迭代填充法的相关性质,同时给出了一种规则和准规则IF-LDPC码编码器设计算法.IF-LDPC码的码长和码率取值灵活,...
  • 多进制LDPC码的编译码算法及结构研究
  • awgn 通道的 ldpc 代码
  • 文中通过对LDPC码的原理进行分析以及对LDPC码的构造进行研究,对编码、译码算法进行分析比较,得出较优的编码译码方法。随着移动通信的进步,5G技术的出现,使得使用一种优秀的编码技术来满足安全、高可靠性、高吞吐...
  • 完成的Mackay随机构造的LDPC码matlab程序 仿真性能很好 完成的Mackay随机构造的LDPC码matlab程序 仿真性能很好
  • 不同码率的LDPC码用于和新设计的QC-LDPC码进行测试和比较。实验结果表明,所提出的码构造方法可加快LDPC码校验矩阵的构造,同时基于所提出方法构造的QC-LDPC码可提高译码性能,并降低编码复杂度。

空空如也

空空如也

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

ldpc码