一种构造低密度奇偶校验码校验矩阵的方法.doc

《一种构造低密度奇偶校验码校验矩阵的方法.doc》由会员分享，可在线阅读，更多相关《一种构造低密度奇偶校验码校验矩阵的方法.doc（5页珍藏版）》请在三一办公上搜索。

1、第 15卷 ,第 4期2008年 12月中国传媒大学学报自然科学版JOURNAL O F COMMUN ICA T ION UN IV ER S ITY O F CH INA ( SC IENCE AND TECHNOLO GY)Vo l. 15, No. 4D ec. , 2008一种构造低密度奇偶校验码校验矩阵的方法冯云飞1 ,李建平 1 ,赵力帜 2( 11中国传媒大学 信息工程学院 ,北京 100024; 21中国航天科技集团公司第五研究院 ,第五一二研究所 ,北京 100086 )摘要 :本文提出一种构造低密度奇偶校验 (LD PC)码校验矩阵的方法 ,该方法通过半随机产生奇偶校验矩

2、阵后 ,消去周长为 4的短环来实现 。仿真结果表明 ,此方法可以有效避免短环对 LD PC 码的性能影响 ,使得译码性能显著提 高 ,并且性能随着码长的增加而不断改善 。关键词 :低密度奇偶校验码 ;半随机构造 ;短环 ;码长 ;对数域内的置信传播算法中图分类号 : TN911122 文献标识码 : A 文章编号 : 1673 - 4793 ( 2008) 04 - 0052 - 05A M e thod on Con struc t ion of LD PC Par ity2Check M a tr ixFEN G Yun2fe i1 , L I J ian2p ing1 , ZHAO L

3、i2zh i2( 11Schoo l of Info rm a tion Enginee ring, Comm un ica tion U n ive rsity of Ch ina, B e ijing100024, Ch ina21No1512 R e sea rch In stitu te, No15 A cadem y, Ch ina A e ro sp ace Sc ience and Techno logy Co rpo ra tion, B e ijing 100086 , Ch ina)A b stra c t:A m e thod on con struc tion of L

4、D PC Pa rity2check m a trix wa s p ropo sed, by removing loop s w ithgirth 4 in a sem i2random p a rity2check m a trix1 Sim u la tion re su lts show tha t the p ropo sed m e thod can effec2tive ly avo id the influence on the p e rfo rm ance of LD PC code s exe rted by sho rt loop s, so the decod ing

5、 p e r2fo rm ance is d istinc tive ly imp roved1 Fu rthe rmo re,of code length s1Key word s: low 2den sity p a rity2check ( LD PC )length s; log2bpthe be tte r p e rfo rm ance can be ob ta ined a s the inc rea singcode s; sem i2random con struc tion; sho rt loop s; code前 ,这方面的研究文献开始大量地出现 , LD PC 码已成

6、为编码领域中的一个研究热点。理论研究表明 : 在二元输入 AW GN 信道下 , 采 用码率为 1 /2 ,码长为 107 的非规则 LD PC码用置信 传播迭代方法译码 ,在错误概率为 10 - 6时距离信息 论中的香农限仅差 010045 dB 1 ,是目前距离香农限 最近的纠错码。大量研究工作证明 , LD PC 码具有 非常好的特点是 :在许多场合下性能优于 Tu rbo 码 ; 具有 较 大 灵 活 性 和 较 低 的 差 错 平 底 特 性 ( e rro r floo r) ;描述简单 ,对严格的理论分析具有可验证性 ; 译码复杂度低于 Tu rbo码 ,且可实现完全的并行操1

7、引言低密 度 奇 偶 校 验 ( LD PC, Low D en sity Pa rityCheck,又称为 Ga llage r码 ) 码是 Robe rt G1 Ga llage r 于 1962年提出的一种性能接近香农 ( Shannon)限的 好码。然而由于各种原因 , 在很长的一段时间里 , LD PC码并未受到人们的重视 , 直到 1993 年 Tu rbo码提出来以后 , D1J1M ackay, M 1N ea l和 N 1W ibe rg等 人才对 LD PC 码重新进行了研究 , 他们发现 LD PC 码与 Tu rbo 一样具有逼近 Shannon 限的性能 。目收稿日期

8、 : 2008 - 06 - 03基金项目 :教育部科学技术重点项目 ( 106042 )作者简介 :冯云飞 ( 1984 - ) ,男 (汉族 ) ,辽宁沈阳人 ,中国传媒大学硕士研究生 1E - m a il: p h il cuc1edu1cn作 ,便于硬件实现 ;吞吐量大 ,极具高速译码潜力。从k个校验节点得到信息。2 LD PC码的关键技术211 校验矩阵 HLD PC码是一种线性分组码 , LD PC 码是由监督(校验 )矩阵 H 定义的 , 不同的 H 矩阵对应不同的 码字集合 ,所以矩阵 H 的构造是编码的关键。生成 矩阵 G与校验矩阵 H 相互对应 , 且满足 GHT = 0

9、。原始信息 s = s1 , s2 , 111sM 与生成矩阵 G 相乘就得 到了传输码字 x = x1 , x2 , 111, xN (N M ) 。LD PC 码可以用稀疏校验矩阵来描述 , 也就是 说 LD PC 码的校验矩阵的矩阵中的元素除一小部分 不为“0 ”外 , 其它绝大多数都为“0 ”, 即“1 ”的密度很低 , 故称低密度奇偶校验码 。通常我们说一个 ( n, j, k )的 LD PC 码是指其码长为 n, 其奇偶校验矩阵每 列包含 j个 1, 其它元素为 0, 即行重为 j; 每行包含 k 个 1, 其它元素为 0, 即列重为 k。并且 j和 k 都远远 小于 n, 以满

10、足校验矩阵的低密度特性 。校验矩阵中列和行的个数即 j和 k 为固定值的 LD PC 码称为 规则码 , 否则称为非规则码。一般来说非规则的性 能优于规则码。校验矩阵 H 有 N 列 M 行 , M 表示码字的校验 方程个数 , 且有 2k 个码字 , 这里 K是消息长度 K = N- M 。码率 P = K /N = 1 - M /N = 1 - j/ k。由于校验矩阵的规律性 , 可以用Tanne r图表现出来 。一组节点表示 N 个变量比特 (矩阵中的列 ) ,另一组节点表示 M 个校验约束 (矩阵中的 行 ) , Tanne r图中的边根据奇偶校验方程连接着变量节点和校验节点 。 Ta

11、nne r图中的环是 指连 接变量节点和校验节点的 , 起始和结束于同一节 点并且不重复包括同一个节点的路径 。环的长 度也就是边的数量 ,而 Tanne r图的周长也就是最 小的环的长度 。212Tanne r图如图 1 所示的是 Ga llage r ( 20 , 3 , 4 )码的检验矩阵。这是一个码长 N = 20, 码率 R = 1 / 4, 行重 j = 4,列重 k = 3 的规则 LD PC 码 。对于一个 LD PC 码校 验矩阵而言 ,每一行对应一个校验方程 ,每一列对应 码字中的一个比特。如果分别将列和行作为变量节 点和校验节点这两类节点的集合 ,“1 ”代表对应的 两个

12、节点存在连通的边 ,显然 ,同类节点之间是不可能有边的 。这样校验矩阵也可以用一个双向图 , 即 Tanne r图来表示。图 1 的 H 矩阵相对应的 Tanne r 图如图 2所示。图中变量节点用圆形表示 ,校验节 点用方块表示。定义一个节点的度数为与此节点相 连接的边的数目。行重量 j表示每个校验节点的度数 ,即每个校验节点向 j个变量节点发送猜想值 ; 列例如 :一个 LD PC 码( 8 , 2 , 4 ) 的校验矩阵如下 :01011010001101011100110000111010H =4 8其中 v5 c2 v6 c1 v5 就构成一个长度为 4 的环 。LD PC 码校验矩

13、阵的 Tanne r图的周长 都是偶数 ,而该图的周长就是 4 ,也是最短的周长 girth。其 Tanne r图如下 :中国传媒大学学报自然科学版第 15卷54图 3 ( 8 , 2 , 4 ) LD PC码的 Tanne r图性和有效性 ,尤其是短环。环的长度越小 ,也就是说Tanne r的周长越小 ,每次迭代更新的数据的不确定 性减小的越慢 , 防止了 B P 算法收敛到最理想的效 果。如果低密度校验码对应的 Tanne r图中存在环 的话 ,那么由和积算法计算所得的概率并不是真正的后验概率 (因为迭代过程中独立性假设不能成立 ) ,因而译码并不是最优的逐符号最大后验概率 译码。因此 ,

14、环的存在使得译码的最优性得不到满 足。 Tanne r图中长度为 4的环是很容易从校验矩阵 直观地检测出来 , 以校验矩阵的非零元素“1 ”为一 个顶点 ,则校验矩阵中的一个矩形就是一个周长为4 的环 。但并不是对应 Tanne r 图为无环时 , LD PC码的编译码性能最优。假设无环情况下 ,当对应码 的码率大于 1 /2 时 ,码的最小距离小于等于 2; 当对 应码的码率小于 1 /2 时 ,码可以由最小距离小于等 于 2 的码重复某些位生成 ,更进一步 ,记码率为 R , 则最小距离满足 dm in 2 /R。因此 ,无环图对应的码 并不是好码 ,相反环的存在改善了码的性能 4 。将奇

15、偶校验矩阵 H 分解为两个子矩阵 , H =p dt H H 。相应地 , 将码字 c分解为 c = p, d , 其中p和d 分别是校验比特和信息比特 。则pdHC = Hp Hd ( 311 )= 0其中 , Hp 是一个 ( n - k ) ( n - k ) 的方阵 , 称为校验位矩阵; Hd 是一个 ( n - k ) k 的矩阵 , 称为信 息位矩阵。Hp 是双对角线形式的上三角子矩阵 , 具有如下形式 , 即100000000110000000011000000001100000000110000000011000000001100000000110000000011p( 312

16、 )H =下面创建 Hd 。令 t是一个事先设定的整数 , 且满足 :( 1 ) n - k可以被 t整除。( 2 ) k t可以被 n - k 整除 。3 一种构造校验矩阵的方法一个 LD PC码是从一个随机产生的奇偶校验矩阵 H 定义的。为了编码 , 要将 H 转换成 Hsy s , 即 H 的 等效系统形式 , 可以通过高斯消去法得到。码率 R= k / n ( k 为信息长度 , n 为编码长度 ) 时 , H 的大小为 ( n - k ) n。当 n 很大时 , 从存储和涉及的操作 方面看高斯消去法都是代价高昂的 。另外 , 在编码器中 , 需要大量存储器来保存 Hsy s , 这个

17、矩阵并不一 定是稀疏的 , 尽管 H 通常被设计为稀疏矩阵。可以运用半随机技术 , 也就是 , H 仅有一部分是随机产生 的 ,剩余的部分是确定的 。这种方法可以达到与标准 LD PC编码方法一样的性能的 ,而且极大地降低 了编码的复杂程度 4 。d (将 H 有n - k行 )分成 t个均等的子块 , 即d1HdH =( 313 )d tH在每个子块 Hd i , i = 1, 2, t中 , 每一列创建一个元素 1, 每一行创建 k t / ( n - k ) 个元素 1。式( 313 )中的划分最大程度增加了编码中每个比特的 递归距离 , 可以直觉感到降低了解码过程中的相关性 。作为结果

18、 Hd 的列权重为 t, 行权重为 k t / ( n -k ) (一个矢量的权重即为其元素中 1的数量 ) 。 基于式 ( 311 ) 和 ( 312 ) , p = pi 可以容易从已知的 d = di 计算出来 , 即 qij ( 0 )( 413 )L ( qij )= logqij ( 1 )p1 = h1 dj , pi = pi - 1 + hij dj (m od2 )dd( 314 )jj ri j ( 0 )与标准 LD PC 码设计相比 , 上述方法有以下优L ( rij )( 414 )= logrij ( 1 )点 :其中= pi , qij ( 0 ) = 1 -

19、pi 。qij ( 1 )式 ( 314 )中的编码过程比一个完整高斯消去法简单很多 。( 1 ) 一个随机 Hd 可能是奇异的 , 在实现特定速 率时会造成额外的编程复杂程度; 另外 , 式 ( 311 ) 中 的 Hp 总是非奇异的 , 所以新方法可以直接并且准确 地实现任意给定的码率 。( 2 ) 如果 Hd 是稀疏矩阵 (使用较小的 t就能确保这点 ) , 则只需要很少的存储器来保存 Hd 。 在这里我们提出一种为 LD PC 码的校验矩阵 H的消除四环算法。对已经构造为半随机 LD PC 码的一个 H 矩阵 , M 行 N 列 ,x记函数 ( x ) = - log tanh ( x

20、 ) = log e+ 1, 并xe2- 1记 aij = sgn (L ( qij ) )为 L ( qij )的符号 ,ij = abs ( qij ) 为L ( q 的绝对值 。ij )具体译码算法如下 :( 1 ) 初始化对于等概率输入的高斯噪声信道 , 给每个变量 节点初始化 :2 yi2L ( qij ) =, 为噪声方差 。( 415 )2( 2 ) 迭代1 ) 校验点更新第一步 :选取第列 , j = i + 1, i + 2,i列 , i = 1, 2,M 。M ; 再选取第L ( rij ) = ( ij ) (ij )( 416 )b it节点jirj iirj i式中

21、r 表示与第 j个 check 节点相连的ij第二步 :把选取的两列向量对应位置的元素做“与 ”运算 , 记录下结果向量中 1的位置和总数 s。 第三步 :如果检测到结果向量中有 1存在 , 比较第 i列和第 j列中 1 的个数 。第四步 :修改 1 个数较多的那一列 L。修改方 法为 :从 L 列的最后一个在结果向量中为 1 的位置 开始反转 1 为 0。重复此操作 。需要注意的是 , 结 果向量中的第一个 1位不用反转 。的集合 , ir i表示该集合中不包含第 i个 b it节点j的其它元素 。2 ) 比特点更新L ( qij ) = L ( ci ) + L ( rji )( 417

22、)jc i i式中 c 表示与第 i个 b it节点相连的 check 节点i的集合 , jc i表示该集合中不包含第j个 check 节j2点的其它元素 , 其中 L ( ci ) =y 。2i( 3 )判决a. 软判决L (Q i ) = L ( ci ) + L ( rij )基于 对数域 的 B e lief P rop aga24( 418 )tion算法LD PC 的译码算法有多种 , 本文采用的是基于 对数域的 B e lief P rop aga tion算法 (Log - B P) 。该算 法复杂度适中 ,解码性能也较好 ,比较适合于硬件实 现。该算法的关键是迭代计算后验概率

23、 (A PP) 。定义jc ib. 硬判决1, L (Q i ) 00, o thersCj =( 419 )( 4 )中止条件计算是否 CHT = 0 m od 2。如果是 , 则本次译码结束; 若不是 , 判断是否达到最大迭代次数 Lm ax , 如 果已达到最大迭代次数 , 结束译码 , 以最后的结果作为输出; 若没有达到最大迭代次数 , 转入步骤 ( 2 ) 。 1 Pi = P ( ci = 1 | yi ) =( 411 )1 + e21y i /2P ( ci = 0 | yi ) 1 - PiL ( ci ) = log( 412 )= logP ( ci = 1 | yi )

24、Pi式中 Pi 表示接收为 yi 时发送为 1的概率 , qij为比特 bi 的更新值 , 传递给校验 cj , rji为校验 cj 的更新5 仿真中国传媒大学学报自然科学版第 15卷56(LD PC )码的校验矩阵方法的性能 ,本节通过 MA T2LAB 编程进行仿真 。仿真中采用基带 B PSK调制方 式 ,通过二进制加性高斯白噪声信道 (AW GN )传输 , 在接收端用对数域内的置信传播算法 (Log - B e liefP rop aga tion A lgo rithm )进行迭代译码 ,最大迭代次数 为 10。该仿真 ,对采用本文提出的消 4 环前后的 LD PC码的译码性能的进

25、行了比较 。仿真中采用码长为256 ,校验矩阵 H 为半随机矩阵 , 列、行重量分别有3、6。从图 4 可以看出 ,在高斯白噪声信道下 ,仅使 用 ( 256 , 3 , 6 )短码 ,在采用本文提出的消 LD PC的校验矩阵的 4 环算法后 , 译码性能上有明显的提高 。在误码率为 10 - 4 处 , 采用消 4 环算法后 , 可获得大 约有 015 dB 的编码增益。图 5 相同码率 r = 2 /5,码长分别为 16200 和 64800 的 LD PC码的性能比较的实现步骤 。为了分析采用消 4 环算法后的 LD PC 码在译码性能方面提高的效果 , 我们进行了仿真。 仿真结果表明

26、,在高斯白噪声信道下 ,使用 ( 256 , 3 ,6 )短码 ,在误码率为 10 - 4处 ,采用消 4 环算法后 ,可 获得大约有 015 dB 的编码增益 ,可见译码性能有明 显的提高。之后对相同码率不同码长的 LD PC 码进 行性能仿真 ,得出结论 :码长是影响 LD PC 码性能的 一个重要因素 ,编码性能随着码长的增加而明显变好 。在误码率为 10 - 4 ,码长为 64800 的编码较码长 为 16200的编码性能上大约有 0117 dB 的提高。可见 ,本文提出的方法可以有效避免短环对 LD PC 码的性能影响 ,使得译码性能显著的提高 ,并 且性能随着码长的增加而不断改善

27、。在使用长码并消去短环后的 LD PC码在信息可靠传输中具有良好 的性能。图 4 采用消 4环算法前后的误码率性能比较图 5所示为码率为 2 /5 的编码在不同码长时的性能比较 。从图 5中可以看出码长是影响 LD PC 性 能的一个重要因素 ,编码性能随着码长的增加而明 显变好。在误码率为 10 - 4 ,码长为 64800 的编码较 码长为 16200的编码性能上大约有 0117 dB 的提高 。参考文献Ga llage r R G1 Low den sity p a rity check code s J 1 IEEE Tran sac tion s on Info rm a tion

28、Theo ry,1962 , 8 ( 3 ) : 208 2201王新梅 ,肖国镇 1 纠错码 - 原理与方法 M 1西安 :西安电子科技大学出版社 , 20011卢开澄 ,卢华明 1 图论及其应用 M 1 北京 :清华大学出版社 , 19951张忠培 ,史治平 ,王传丹 1 现代编码理论与应 用 M 1 北京 :国防工业出版社 , 20071(责任编辑 :王谦 ) 1 6 结论 2 本文提出了一种构造低密度奇偶校验 (LD PC )码校验矩阵的方法 ,可以有效消去 LD PC 稀疏校验 矩阵中长度为 4 的环 。文章首先介绍了 LD PC 码的 校验矩阵特征 , Tanne r 图表示方法和环的概念 , 分 析短环对 LD PC码的性能的影响。随后提出一种构造可消去长度为 4的环的 LD PC 码半随机校验矩阵 的方法 ,介绍基于对数域的置信传播 B P 译码算法 3 4