纠错码Lecture10-LDPC

1、信道编码理论信道编码理论邢莉娟，李卓，西安电子科技大学邢莉娟，李卓，西安电子科技大学Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论2 LDPC码的简介码的简介 Tanner图图 LDPC码的几何构造方法码的几何构造方法 LDPC码的译码方法码的译码方法Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论3LDPC码是另外一类逼近码是另外一类逼近Shannon-Limit的码，是的码，是由由Gallager在在1960s提出的提出的,与与Turbo码相比，码相比，LDPC码有如下优点：码有如下优点： (1)不需要长的交

2、织器来达到好的译码性能不需要长的交织器来达到好的译码性能. (2)误比特率误比特率(BER)达到更低达到更低. (3)错误平层在更低的误比特率错误平层在更低的误比特率(BER)出现出现. (4)译码不需要译码不需要Trellis.Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论4 Gallager提出了提出了LDPC码，但并没有给出方法来系码，但并没有给出方法来系统的构造统的构造LDPC码，只给出了一类随机码，只给出了一类随机LDPC码的码的构造方法，被发现的好的构造方法，被发现的好的LDPC码都是由计算机码都是由计算机搜索得到的，搜索得到的，LinSh

3、u给出了一类基于有限域的给出了一类基于有限域的LDPC码代数构造方法，这类码代数构造方法，这类LDPC码有着相对较码有着相对较好的好的 ，并不存在短环，译码性能也不错，此，并不存在短环，译码性能也不错，此外，这类码都是循环或准循环的，编码器可用线外，这类码都是循环或准循环的，编码器可用线性移存器来实现。性移存器来实现。mindLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论5第二章中讲到，一个线性分组码可由其生成矩阵第二章中讲到，一个线性分组码可由其生成矩阵G及校验及校验矩阵矩阵H唯一的确定，并且唯一的确定，并且G是是H的零空间，一个在二元域上的零空间，

4、一个在二元域上的的n-维矢量维矢量 V= ( ) 是码字的充要条件是是码字的充要条件是 。 LDPC是根据其校验矩阵定义的：是根据其校验矩阵定义的：1210.nnvvvvTVH 0Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论6定义定义1：给定校验矩阵：给定校验矩阵H，若其零空间为，若其零空间为LDPC码，码，则该则该H的结构具有以下特征。的结构具有以下特征。 (1)每一行包含每一行包含 个非零元（个非零元（1）。）。 (2)每一列包含每一列包含 个非零元。个非零元。 (3)任意两列有相同任意两列有相同1的个数记为的个数记为 ，=0或或1。 (4) 与

5、与 与码长与与码长与H的行的个数比较起来非常小。的行的个数比较起来非常小。 说明：说明：(1)与与(2)说明说明H具有恒定的行重具有恒定的行重 和列和列重重 ,(3)说明说明H中任意两行相同中任意两行相同1的个数不超过的个数不超过1。(4)说明说明H中非零元的密度非常少，中非零元的密度非常少，H是一个是一个Low-Density Parity-Check Matrix，由这样的，由这样的H所确定所确定的码就是的码就是LDPC码。码。Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论7H的密度的密度r定义为定义为r= = 。 J为为H中的行数，中的行数，H的

6、低密度说明的低密度说明H为稀疏矩阵。为稀疏矩阵。 由上述由上述定义定义得到的得到的LDPC码称为码称为( , )-规则规则 LDPC码码，如果，如果H的行重与列重都不相同，得到的的行重与列重都不相同，得到的 是是非规则非规则-LDPC码码，本章主要讨论规则码一类，本章主要讨论规则码一类， H中每一行并不是线性独立的，因此要求码的维中每一行并不是线性独立的，因此要求码的维 数，需要首先确定数，需要首先确定H的秩。的秩。nJLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论8 H = 00000001101000110000000110100001000000

7、0110100001000000011010000100000001101100010000000110010001000000011101000100000001110100010000000011010001000000001101000100000000110100010000000011010001000000001101000100000000110100010Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论9 例例1： 上图给出的上图给出的H(见书见书P853图图17.1),每行与每每行与每列包含列包含4个个1,是一个是一个(4,4)-规则规

8、则LDPC码码,可以看到任可以看到任意两列意两列(行行)相同相同1 的个数都不超过的个数都不超过1,密度密度r= =0.267,该矩阵的零空间给出一个该矩阵的零空间给出一个(15,7)LDPC码码,其其 =5.nmindLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论10下面给出构造随机下面给出构造随机LDPC码的码的H的方法的方法 令令 且且 为正整数。为正整数。 给定给定 与与 ,构造一个构造一个 维的矩阵维的矩阵H。 H包含包含 个个 维子矩阵维子矩阵 ,每个子每个子矩阵中的每行有矩阵中的每行有 个个1,每个子阵的每列只包含每个子阵的每列只包含1个

9、个1,因此因此,每个子阵每个子阵1的个数为的个数为 。 当当 时时, 的第的第 行在第行在第 列列到第到第 列的位置上为列的位置上为1,其余为其余为0。其它子阵只是。其它子阵只是的列置换。的列置换。1kkkkk k12HHHk1ik1Hi(1)1ii1HLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论11 H = 由上述方法构造的由上述方法构造的H矩阵矩阵,有以下的几个结论。有以下的几个结论。 (1)在在H的每个子矩阵中的每个子矩阵中,任意两行都不存在有相同任意两行都不存在有相同1的情况。的情况。 (2)H的每个子阵中的每个子阵中,任意两列相同任意两列相

10、同1的个数的个数 。12HHH1Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论12 在在H中中1的个数共有的个数共有 位位,而而H共有元素共有元素 ,H的密度为的密度为 ,当当 取值远远大于取值远远大于1,则则H为小密度，为小密度，也就是稀疏矩阵。也就是稀疏矩阵。 H是否满足是否满足定义定义 第三条的性质取决于对第三条的性质取决于对 采取哪采取哪种方式进行列置换得到其余种方式进行列置换得到其余 个子阵个子阵, 的零的零空间可能确定的是一个空间可能确定的是一个 的线性分组码的线性分组码,不一不一定是一个定是一个LDPC码码,因此因此LDPC码是线性分组码

11、的码是线性分组码的一个子类。一个子类。 Gallager并没有给出一种有效的置换方式使得并没有给出一种有效的置换方式使得 得到其他子阵得到其他子阵 ,并且并且H满足定义的满足定义的所有性质。目前，都借助于计算机来搜索好的所有性质。目前，都借助于计算机来搜索好的LDPC码，尤其在码，尤其在n较大的时候。较大的时候。k2k1kk1H11Hnk1H12HHHLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论13令令 构造一个构造一个 的的H矩阵如下所示矩阵如下所示 H =5,4,3,k15 201111000000000000000000001111000000

12、00000000000000111100000000000000000000111100000000000000000000111110001000100010000000010001000100000010000010001000000100010000010000001000100010000000010001000100011000010000010000010001000010001000010000001000010000100000100001000010000100100000001000010000100001Lecture 10 LDPCLecture 10 LDPC码码信道

13、编码理论信道编码理论14H包含包含3个个 的子阵的子阵 ， 中每行包含中每行包含4个个1，任意两行没有相同的，任意两行没有相同的1. 与与 由由 置换得到。置换得到。H中任意两列中任意两列(行行)相同相同1的个数不超过的个数不超过1，而，而H的密度的密度 =0.20,因此因此,这样的这样的H确定的是一个确定的是一个LDPC码码,码的参数是码的参数是(20,7)，最小距离最小距离 =6.5 20123,HHH1H2H3H1H1rkmindLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论15一个图一个图(Graph)G包括顶点集合包括顶点集合 ,与与边集合边

14、集合 ,并且每条边并且每条边 确定，确定，这样的图这样的图G由由G= 来标记。边来标记。边 的顶点的顶点 称为称为 的终端顶点。的终端顶点。 顶点顶点 所连接边的个数称为该顶点的度，记所连接边的个数称为该顶点的度，记 例例 2：一个图包括：一个图包括6个顶点个顶点,10条边条边,如下图。如下图。 12vvv12ee(,)ijvv( , )vke(,)ijvvkeiv( )id vLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论16Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论17边边b连接点连接点 和和 ,顶点顶

15、点 连接边连接边b,c,d。 所以所以 =3。 连接同一顶点的两条边称为相邻连接同一顶点的两条边称为相邻(adjacent)。 连接一条边的两个顶点也可称为相邻连接一条边的两个顶点也可称为相邻(adjacent)。 例如，上图中边例如，上图中边a和和b，顶点，顶点 和和 相邻。相邻。 有限个顶点与边组成的图是有限个顶点与边组成的图是有限图有限图。 路径：由某个顶点开始，到某个顶点结束，经过路径：由某个顶点开始，到某个顶点结束，经过这些顶点所连接的边，并且每个顶点出现的不超这些顶点所连接的边，并且每个顶点出现的不超过一次，这样的组合称为路径。过一次，这样的组合称为路径。1v2v2v2()d v1

16、v2vLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论18路径中边的个数称为该路径的长度路径中边的个数称为该路径的长度(length)。 在例在例2中，中， ,b, ,c, ,h, ,g, 是一条长度为是一条长度为4的路径，如下图。的路径，如下图。 1v2v4v5v3vV1V5V2V3V4abcdefghijV6Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论19环：若路径的起始与结束顶点相同环：若路径的起始与结束顶点相同,这样的闭合路这样的闭合路径成为环。除了起始与结束顶点径成为环。除了起始与结束顶点,环中的其余

17、顶点环中的其余顶点出现的次数不超过一次。出现的次数不超过一次。 在例在例2中，中， ,f, ,g, ,j, ,i, 是长度为是长度为4的环，的环，如下。如下。1v5v3v1v6vV1V5V2V3V4abcdefghijV6Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论20长度为长度为1的环称为自环的环称为自环,图中最短欢的长度称为图图中最短欢的长度称为图的围长的围长(grith),在例在例2中中,图的围长为图的围长为3。树：一个不存在环的图成为树。树：一个不存在环的图成为树。 例例 3 连接的图：连接的图：G中每对顶点至少有一条边相连，该中每对顶点至少

18、有一条边相连，该图称为连接的图称为连接的(connected)。 例例2, 3中的图都是连接的。中的图都是连接的。Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论21双向图双向图(bipartite graph)：图：图G= ，若将其顶，若将其顶点点 划分成划分成 和和 两部分两部分,使得使得 中的每条边都连中的每条边都连接的是接的是 中的一个顶点与中的一个顶点与 中的一个顶点，并且中的一个顶点，并且 与与 中任意两个顶点不相连中任意两个顶点不相连,这样的图不存在自环。这样的图不存在自环。 例例 双向图双向图 ( , )v1VV2V1V2V1V2V112

19、3Vvvv245678VvvvvvLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论22如果双向图中存在环，则环的长度必为偶数。如果双向图中存在环，则环的长度必为偶数。Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论23 线性码关于图的应用非常多线性码关于图的应用非常多,例如卷积码中的例如卷积码中的Trellis,网络编码中的树表示及网络编码中的树表示及LDPC码的码的Tanner 图表示。图表示。 Tanner图：表示的是码字比特与其校验比特和之图：表示的是码字比特与其校验比特和之间的关系。间的关系。 一个码长为一

20、个码长为n的线性分组码，其校验矩阵为的线性分组码，其校验矩阵为H，H的每行表示为的每行表示为 ,共共J行。行。 根据码字与根据码字与H，可构造一个图，可构造一个图 , 包含两组顶包含两组顶点点 和和 。 中包含中包含n个顶点个顶点,代表代表n位码字比特位码字比特,标记为标记为12,Jh hh TGTG1V2V1V011nvvvLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论24 称为称为码字顶点集合码字顶点集合。 定义定义2： 则则 称为校验和。称为校验和。1V,0,1,2,1jjjjj nhhhhh1jJ0121nvvvvv1,00njjlj llsv

21、 hv h jSLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论25若若 ,则称码字比特则称码字比特 被被 校验。校验。 中包含中包含J个顶点，分别是个顶点，分别是 , 称称为校验和顶点集合。为校验和顶点集合。 当且仅当码字比特当且仅当码字比特 被被 校验，在校验，在 图中码字节图中码字节点点 和校验节点和校验节点 通过一条边项链，标记为通过一条边项链，标记为 显然显然 为一双向图，由为一双向图，由Tanner在在1981年提出，主年提出，主要用于要用于LDPC码的迭代译码研码的迭代译码研,称为称为Tanner图图 。lv,1j lhjS2V12Jsss

22、2VlvjSTGlvjS( ,)ljv sTGLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论26Tanner图中图中 的度等于校验和中包括的度等于校验和中包括 的个数。的个数。 的度等于被的度等于被 校验的码字比特的个数。校验的码字比特的个数。 对于对于LDPC码来说码来说,每个码字节点的度都相同每个码字节点的度都相同,等于等于 (即即H的列重的列重),每个校验节点的度都等于每个校验节点的度都等于 (H的的行重行重). 这样的图成为规则这样的图成为规则Tanner图。图。 *由定义由定义1(3)可知可知,不存在两个码字节点同时被两个不存在两个码字节点同

23、时被两个校验节点检验的情况校验节点检验的情况,即即LDPC码的码的 不包括长度不包括长度为为4的环。的环。lvlvjSjSTGLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论27由于对由于对LDPC码采用基于码采用基于belief propagation(置信置信传播传播)的迭代译码算法的迭代译码算法,要求在要求在Tanner图中不存在图中不存在短环短环,尤其是长度为尤其是长度为4的环的环,4环为译码有很大的影响。环为译码有很大的影响。例例6 (7,3)LDPC码。码。 *不包括不包括4环环 但包括但包括6环环 Tanner图围长是图围长是6 11010

24、00011010000110100001101100011001000111010001HLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论28校验节点校验节点Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论29本节介绍两种基于有限几何本节介绍两种基于有限几何(finite geometry)的的LDPC码的构造方法，码的构造方法，方法一：方法一： Q：有限几何，包括：有限几何，包括n个点个点,J条线。条线。 具有以下的性质：具有以下的性质： (1)每条线包含每条线包含 个点。个点。 (2)每个点由每个点由 条线确定

25、。条线确定。 (3)任意两点仅由一条线相连。任意两点仅由一条线相连。 (4)任意两条线要么是不相邻的任意两条线要么是不相邻的(即没有共同点即没有共同点),要要么只相交于一点。么只相交于一点。Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论30将将Q中的点集合标记为中的点集合标记为 ,线集合表示线集合表示为为 ,令令 为为GF(2)中的中的n维矢量。维矢量。 与与Q中的顶点集合相对应。中的顶点集合相对应。 若若L为为Q中的某条线中的某条线,定义如下向量定义如下向量 当当 ,若若 是是L线上的点线上的点 ,否则否则 12nPPP12nLLL12nvvvvvi

26、ivP12lnvvvv10iviPLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论31 显然该向量的重量为显然该向量的重量为 。 构造构造 ,该矩阵为该矩阵为 维。维。 其：每行代表其：每行代表Q中的中的J条线。条线。 每列代表每列代表Q中的中的n个点。个点。 由由Q的性质得到关于的性质得到关于 的一下结论。的一下结论。 (1)每行有每行有 个个1。 (2)每列有每列有 个个1（由以上（由以上(2)得到）。得到）。 (3)任意两行相同的任意两行相同的1的个数不超过的个数不超过 1。（由以上。（由以上(4)得到）得到） (4)任意两列相同任意两列相同1的个

27、数不超过的个数不超过1 。(由以上由以上(3)得得到到)。 1QH Jn 1QH Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论32 的密度的密度r= = 。若。若 ，则，则 为为一低密度矩阵。一低密度矩阵。 所以所以 的零空间确定是码长为的零空间确定是码长为n的的LDPC码码,该码该码称为称为 -型型Q元元-集合集合LDPC码码,用用 ,该码的该码的 Tanner图为双向图图为双向图,包含包含n个码字节点与个码字节点与J个校验节个校验节点。点。 码字节点的度为码字节点的度为 。 校验节点的度为校验节点的度为 。 该图不包括该图不包括4环环,但包括但包

28、括6环。环。 1QH nJ, n J 1QH 1QH (1)QCmin1dLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论33方法二：方法二： 同样同样Q,包含包含n个顶点个顶点P,Q条线条线L。 令令 为为GF(2)上的上的J维矢量。维矢量。 与与Q中的中的J条线一一对应，条线一一对应， P为为Q中的某个点，定义中的某个点，定义J维矢量维矢量 其中其中 ,Q中的第中的第i条线包含该点条线包含该点P ,否则否则 12JvvvviivLpv12pJvvvv10ivLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论34

29、表示的是相交于表示的是相交于P点的所有线的信息点的所有线的信息,显然显然 重重量为量为 . 构造构造 ,是一个是一个 维的矩阵。维的矩阵。 每行代表每行代表Q中的中的n个点。个点。 每列代表每列代表Q中的中的J条线。条线。 具有以下几点性质：具有以下几点性质： (1)每行行重为每行行重为 。 (2)每列列重为每列列重为 。 (3)任意两列相同任意两列相同1的个数不超过的个数不超过1 。 (4)任意两行形同任意两行形同1的个数不超过的个数不超过1 。pvpv(2)QH nJ(2)QH Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论35 与与 有如下的关系

30、有如下的关系 且有相同的密度。且有相同的密度。 的零空间确定的是长为的零空间确定的是长为J的的LDPC码码, ,用用 标记标记,称为称为 -型型LDPC码。码。 与与 称为同享码称为同享码(companion codes)。 与与 的的Tanner图互为对偶。图互为对偶。 即即 的图中码字节点变为的图中码字节点变为 图中的校验节点。图中的校验节点。 图中的校验节点变为图中的校验节点变为 图中的码字节点。图中的码字节点。 (2)QH 1QH 1(2)TQQHH 2(1)TQQHH (2)QH min1d(2)QC(2)QC(1)QC(1)QC(2)QC(1)QC(1)QC(2)QC(2)QCLe

31、cture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论36LDPC的译码方法有的译码方法有： majority-logic(MLG) 大数逻辑译码大数逻辑译码 bit-flipping(BF) 比特翻转译码比特翻转译码 weight BF decoding 重量比特翻转译码重量比特翻转译码 posterior probability(APP) 后验概率译码后验概率译码 Iterative decoding based on belief propagation(IDBP) 置信传播的迭代译码置信传播的迭代译码 称为称为sum-product algorithm(S

32、PA) 和积算法和积算法硬判决硬判决软判决软判决介于中间介于中间Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论37译码复杂度译码复杂度性能分析性能分析MLGSimplest一般一般BF比比MLG稍高稍高优于优于MLGWeighted BF介于两者之间介于两者之间 介于两者之间介于两者之间APP高复杂度高复杂度高性能高性能SPA高复杂度高复杂度高性能高性能在在APP与与SPA中中,APP计算机仿真较难实现，计算机仿真较难实现，因此实际中一般用因此实际中一般用SPA算法算法Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码

33、理论38LDPC的码字的码字 经过经过AWGN信道信道,噪声噪声 通过通过BPSK映射：映射： c00,2eNn12nvvvv11ev 01ev 01en021nyyyy 为接收端软判决输出为接收端软判决输出SPA算法：算法：LDPC码码 ，码长为，码长为n，其，其H为为J行行c12,Jh hh ,0,1,1jjjj nhhhh 1jJ定义定义 ,:1,0jj lB hl hln 第第j行行1的位置的位置Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论39SPA算法是基于边缘后验概率的计算算法是基于边缘后验概率的计算,即计算即计算lpvy 0ln 后验概

34、率：后验概率：0(0)llpp v11llpp v定义定义 ： 与与 相连的校验和集合相连的校验和集合lAlv 1,:0,1,0,1Xijj llqlnjJ hA X 1,Xij lq表示第表示第i次迭代译码中，已知次迭代译码中，已知 矢量的校验和矢量的校验和ljAh条件下，条件下， 取值为取值为X的概率值的概率值lvLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论40 1,:1,1,0,1Xijj lllnjJ hA X 1,Xij l表示第表示第i次迭代译码中，已知次迭代译码中，已知(01)lvX或并且已知并且已知满足满足jB h的其它码字比特的独立

35、分布：的其它码字比特的独立分布： 1,:tVij tjqtBhl 的条件下，校验和满足的条件下，校验和满足 的概率值。的概率值。0jS 11,:(0|,:() )tjjtV iX ijj ljltj tt B hlV t B hlp SVX V tB hlqLecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论41 1,Xij l用来计算用来计算11,Xij lq 111(1),ttjlXiXiiXj lj llt lhAhqp1,ij l选择使得选择使得0,11,1,1iij lj lqq计算得到的计算得到的11,Xij lq用来修正用来修正 ，即得到，即得

36、到11,Xij l 1,Xij lq 1,Xij l与与互相修正互相修正,知道译码结束。知道译码结束。在第在第i步译码中步译码中,计算后验概率：计算后验概率：Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论42 11,|jliiXiXlllj lhApvXyp il选择使得选择使得 0|1|1iillpvypvy 计算向量计算向量 011iiiinzzzz 10ilz当当否则否则 1|0.5ilpvy 然后，计算然后，计算 TizH 如果结果等于如果结果等于0，译码结束，输出为码字，否则继续迭代，译码结束，输出为码字，否则继续迭代Lecture 10 LDPCLecture 10 LDPC码码信道编码理论信道编码理论43SPA算法算法初始化初