LDPC码的代数构造及译码算法研究_甜梦文库
LDPC码的代数构造及译码算法研究
西安电子科技大学 博士学位论文 LDPC码的代数构造及译码算法研究 姓名：刘原华 申请学位级别：博士 专业：通信与信息系统 指导教师：王新梅
摘要低密度奇偶校验码（Ｌｏｗ－Ｄｅｎｓ时Ｐ撕锣．Ｃｈｅｃｋ’ＬＤＰＣ，Ｃｏｄｅｓ）是一种基于图模型和迭代译码的纠错编码方案，性能非常接近Ｓｈ锄ｏｎ容量限，且译码算法复杂度较低，近年来逐渐成为人们的研究热点。本文对ＬＤＰＣ码的代数构造及其迭代译码算法进行了深入研究，在以下几个 方面获得了关键性研究成果：１．研究了基于中国剩余定理的由短分量码设计长码的准循环ＬＤＰＣ码构造方法，指出该方法中由于分量码的结构特征导致所构造的新码包含很多短环，在迭代译码下影响了纠错性能。基于上述研究，对原ＣＲＴ方法进行了推广和改进，减少了新码中短环的数量，从而使所构造的准循环ＬＤＰＣ码具有更好的纠错性能，同时通过放宽参数选择的条件，构造出了更多具有优异性能的准循环ＬＤＰＣ码。２．利用欧氏几何的结构特征，提出了一种基于循环置换矩阵的准循环ＬＤＰＣ 码构造方法，该方法构造的码对应的ＴａＩｌｌｌｅｒ图中包含较少的短环，具有与已有的 欧氏几何码几乎相同的纠错性能。 ３．研究了一种已有欧氏几何准循环ＬＤＰＣ码的最低重量码字分布后，找到了一个产生最低重量码字的充分条件，提出了一种准循环ＬＤＰＣ码构造方法，该方 法可以减少满足该充分条件的最低重量码字，设计出的准循环ＬＤＰＣ码具有更低的错误平层，在低误码率区域具有更好的纠错性能。４．研究了ＬＤＰＣ码基于软信息的各种比特翻转译码算法，给出了一种具有极低计算复杂度的改进比特翻转译码算法，该算法译码速度很快，时延很短。 ５．基于卷积ＬＤＰＣ码连续数据编译码传输的结构特性，给出了一种迭代反馈译码算法，该算法运用反馈信息，在更新当前变量节点消息时及时应用相关历史变量节点的最新消息，加快了信息的传递速度。新算法仅需很少的迭代次数，即 可获得比已有算法更好的纠错性能，有效降低了卷积ＬＤＰＣ码的译码复杂度并减 小了译码时延。 ６．根据研究成果５，设计了一种卷积ＬＤＰＣ码的快速收敛译码算法，在不损失纠错性能的前提下，译码器具有更低的译码复杂度及译码时延，从而使卷积ＬＤＰＣ码更适于实际应用。关键词：低密度奇偶校验码准循环码卷积码迭代译码ＡｂｓｔｒａｃｔＢｅｉｎｇａｐｏｗｅｒ如ｌ ｃｌａｓｓ ｏｆ ｅｒｒｏｒ－ｃｏｎＩｅｃｔｉｌｌｇ ｃｏｄｅｓ ｂ２Ｌｓｅｄ ｏｎ伊．ａｐｈｉｃａｌ ｍｏｄｅｌｓ锄ｄｉｔｅｒａｔｉＶｅ ｄｅｃｏｄｉｎｇａｌｇｏｒｉ恤Ｉｌｓ，ｌｏｗ―ｄｅｎｓ毋ｐ撕妒ｃｈｅｃｋ（ＬＤＰＣ）ｃｏｄｅｓ ｃａｐａｃ时印ｐｒｏａｃｈｉｎｇ ｐｅｒｆ．０ｍ姗ｃｅｈａｖｅ ｒｅｃｅｎｔｌｙ ａｎｄｒｅｃｅｉＶｅｄ ｎｍｃｈ ａｔｔｅｎｔｉｏｎ ｄｕｅ ｔ０ ｔｈｅｉｒ ｌｏｗ ｄｅｃｏｄｉｎｇｒｅｌａｔｉｖｅｌｙｃｏｒｎｐｌｅｘｉ够Ｔｈｉｓ ｄｉｓｓｅｎａｔｉｏｎ ｉｓ ｉｎｔｅｎｄｅｄ ｔ０ ｉＩⅣｅｓｔｉｇａｔｅ ｔｌｌｅ ａｌｇｅｂｒａｉｃ ｃｏｎ殉ｒＩｌｃｔｉｏｎ ａｎｄ ｔｈｅ ｉｔｃｒａｔｉｖｅ ｄｅｃｏｄｉｎｇａｌｇｏｒｉｔｌ蚰ｏｆ ＬＤＰＣｃｏｄｅｓ．Ｔｈｅ ｍａｉｎ ｒｅｓｕｌｔｓ ａｒｅ羽ｌｍｍａｒｉｚｅｄ觞ｆｏｌｌｏｗｓ．１．Ａ ｍｅｔｈｏｄ ｏｆ ｃｏｎｓｔｍｃｔｉｎｇ ｃ０１１１＿ｂｉｎｉｎｇ Ｒｅｍａｉｎｄｅｒｑｕａｓｉ?ｃｙｃｌｉｃ（ＱＣ）ＬＤＰＣａｓｃｏｄｅｓ ｏｆ ｌａ唱ｅｌｅｎｇｔｈ ｂｙＱＣ－ＬＤＰＣｃｏｄｅｓ ｏｆ ｓｍａＵ ｌｅｎｇｔｈｍｅｉｒ ｃｏｍｐｏｎｅｍ ｃｏｄｅｓ ｖｉａ ｔｈｅ ＣｈｉｎｅｓｅＴｌｌｅｏｒｅｍ（ＣＲＴ）ｉｓｒｅｓｅａｒｃｈｅｄ．Ｄｕｅ ｔｏ ｔｈｅｓｉｍｉｌａｒ咖ｌｃｔｕｒａｌｇｒａｐｈｐｒ叩ｅｎｙｏｆ ｔｈｅｃｏｎｌｐｏｎｅｎｔ ｃｏｄｅｓ，ｔｈｅｒｅ ｅｘｉｓｔａｌｏｔ ｏｆ ｓｈｏｒｔ ｃｙｃｌｅｓ ｉｎ ｔｈｅ Ｔａｒｍｅｒｏｆ ｔｈｅ ｄｅｓｉｇｌｌｅｄｃｏｄｅ ａｎｄ ｔｈｅ ｐｅｒｆｏｎｎａｎｃｅ ｉｓ ｎｏｔ ｇｏｏｄ ＣＲＴ ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｉｍｐｒ０Ｖｅ ｔｈｅ ａｎｄ ｂｅｔｔｅｒｅｎｏｕｇｌｌｗｉｔｈ ｉｔｅｒａｔｉＶｅ ｄｅｃｏｄｉｎｇ．Ａ ｇｅｎｅｒａｌｉｚｅｄ ａｎｄ ｄｅｓｉｇｌｌ ｍｕｃｈ ｍｏｒｅａｒｅＣＩ玎ｃｏｒｎｂｉｎｉｎｇ ｍｅｔｈｏｄＱＣ－ＬＤＰＣｃｏｄｅｓ ｗｈｅｎ ｔｈｅｐ撕哆ｃｈｅｃｋｍａｔｒｉｃｅｓ ｏｆ ｔｈｅ ｃｏｍｐｏｎｅｎｔ ｃｏｄｅｓｇｉＶｅｎ．Ｂｙ ｐｅｍｍｔｉｎｇ ｔｈｅ ｂｌｏｃｋ ｒｏｗｓ ｏｆ ｔｈｅ ｐａｒｉｔ）ｒ ｃｈｅｃｋ ｍａｔｒｉｃｅｓ ｏｆ ｃｏｍｐｏｎｅｎｔ ｃｏｄｅｓ，ａ ｌｏｔ ｏｆ ｓｈｏｒｔ ｃｙｃｌｅｓ ｉｎ ｔｈｅ Ｔａｎｎｅｒ ｇｒａｐｈ ｏｆ ｔｈｅ ｄｅｓｉｇｎｅｄ ｃｏｄｅｃ加ｂｅ ｅｌｉｍｉｎａｔｅｄｃａｎａＩｌｄａｌａ唱ｅ ｎｕｎｌｂｅｒ ｏｆ ＱＣ―ＬＤＰＣ ｃｏｄｅｓ ｗｉｔｈ ｂｅｔｔｅｒ ｐｅＩ．ｆｂｌｌ：ｎａｎｃｅｂｅｄｅｓｉｇｎｅｄ．Ｂｙ１００ｓｅｌｌｉｎｇ恤ｃｏｎｄｉｔｉｏｎ ｆｏｒ ｄｅｔｅ衄ｉｎｉｎｇ ｔｈｅ ｉｎｔｅｍｅｄｉａｔｅ ｐａｒａ衄ｅｔｅｒＳ，ａ ｍｕｃｈ ｌａｒｇｅｒ ｃｌａＳｓｏｆＱＣ－ＬＤＰＣ２．Ｂａｓｅｄｃｏｄｅｓ ｗｉｔｈ ｂｅｔｔｅｒ ｐｅｒｆｏｎｎａｎｃｅｃａｎｂｅ ｄｅｓｉｇｎｅｄ．ａｎｏｎｔｈｅ曲ｎｌｃｔＩｌｒａｌ ｐｒｏｐｅｒｔｉｅｓ ｏｆ Ｅｕｃｌｉｄｅａｎ ｇｅｏｍｅｎＸａａｌｇｅｂｒａｉｃ ｍｅｔｈｏｄ ｉｓｐｒｏｐｏｓｅｄ ｔｏ ｃｏｎｓ仃ｕｃｔ Ｔｈｉｓ ｃｌａｓｓ ｏｆｃｌａｓｓ ｏｆＱＣ―ＬＤＰＣｃｏｄｅｓ ｗｉｔｌｌ ｃｉｒｃｕｌａｎｔ ｐｅｍｌｕｔａｔｉｏｎ ｍａｔｒｉｃｅｓ．ＱＣ―ＬＤＰＣｃｏｄｅｓ ｃｏｎｔａｉｎｓ ｓｍａｌｌｅｒ ｎｕｌｎｂｅｒ ｏｆ ｓｈｏｒｔ ｃｙｃｌｅｓ ｉｎ ｔｌｌｅ １’ａＩｍｅｒｇｒａｐｈ锄ｄｃｏｄｅｓ． ３．Ｔｈｅｈａｓ ｓｉｎｌｉｌａｒｐｅ响聊ａｎｃｅｗｉｔｈ ｔｈｃ ｅＸｉｓｔｉｎｇ ＱＣ Ｅｕｃｌｉｄｅａｎｇｅｏｍｅ时ＬＤＰＣＱＣｄｉｓｔｒｉｂｕｔｉｏｎｓ ｏｆ ｃｏｄｅｗｏｒｄｓ ｗｉｔｈａｒｅｍｉｎｉｍｕｍ ｗｅｉｇｈｔ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇａＥｕｃｌｉｄｅａｎ ｇｅｏｍｅ仃ｙ ＬＤＰＣ ｃｏｄｅｓｔｏ ｈａｖｅａ１１ａｌｙｚｅｄ ａｎｄｓｕ伍ｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎ ｆｏｒｃａｎａｃｏｄｅｗｏｒｄｍｉｎｉｍｕｍ ｗｅｉｇｌｌｔ ｉｓ ｆ．０ｕｎｄ．Ａ ｃｏｎｓｔｍｃｔｉｏｎ ｍｅｔｈｏｄ，ｗｈｉｃｈｒｅｄｌｌｃｅ ｔｈｅ ｎｕｍｂｅｒｏｆ ＩＩｌｉｎｉｍｕｍ ｗｅｉｇｈｔ ｃｏｄｅｗｏｒｄｓｓａｔｉｓ母ｉｎｇ ｍｉｓ ｓｕｍｃｉｅｎｔｅｎ．０ｒｃｏｎｄｉｔｉｏｎ，ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ｎｅｗＱＣ－ＬＤＰＣｃｏｄｅｓ ｈａＶｅ ｍｕｃｈ ｌｏｗｅｒｆｌｏｏｒ ａｎｄ ｐｅｒｆｂｎｎ ｂｅｔｔｅｒ ａｔ ｌｏｗ ＢＥＲ．ｏｎ４．Ｓｏｍｅ ｗｅｉｇｈｔｅｄ ｂｉｔ－ｆｌｉｐｐｉｎｇ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｓｔｕｄｉｅｄ ａｎｄａｓｏＲｉｎｆ０姗ａｔｉｏｎａｒｅｍｏｄｉｆｉｅｄｂｉｔ―ｆｌｉｐｐｉｎｇｄｅｃｏｄｉｎｇａｌｇｏｒｉｔｈｍｗｉｔｈｓｉｇｎｉｆｉｃａｎｔｌｙｌｏｗｃｏｍｐｌｅｘｉ哆ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｍｍ ｈａｓｓｈｏｒｔ ｄｅｃｏｄｉｎｇ ｄｅｌａｙ．ｓｉ印ｉｆｉｃａｎｔｌｙ ｈｉｇｈｄｅｃｏｄｉｎｇ ｓｐｅｅｄ锄ｄ５．Ｂａｓｅｄ ｉｔｅｒａｔｉｖｅｏｎｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｃｏｎｔｉｎｕｏｕｓ缸．ａｎｓ觚ｓｓｉｏｎ ｆｏｒ ＬＤＰＣ ｃｏｎｖｏｌｕｔｉｏｎａｌｃｏｄｅｓ．姐ｎｅｗｆｅｅｄｂａｃｋ ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ ｄｅｃｏｄｉｎｇａｌｇｏｒｉｍｍｉｓｐｒｏｐｏｓｅｄ．Ｔｌｌｅａｌｇｏｒｉｔｈｍ ｕｔｉｌｉｚｅｓ ｔｈｅ ｍｏｓｔ ｃｕｒｒｅｎｔ ｖ习ｕｒｉａｂｌｅ ｔｌｌｅ Ｖａｒｉａｂｌｅ ｎｏｄｅｓＩｎｏｒｅｉｎｆ０肌ａｔｉｏｎ ｏｆ ｔｈｅｐａＳｔ ｃｏｄｅ ｂｉｔｓ ｔ０ ａｃｔｉｖａｔｅａｔｅｍｃｉｅｎｔｌｙ ｂｙ印ｐｌｙｉＩｌｇ佗ｅｄｂａｃｋ ｉｎｆｏｍａｔｉｏｎｅａｃｈ ｄｅｃｏｄｉｎｇｉｔｅｒａｔｉｏｎ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｎｍｍ ｗｉｔｈ ｓｍａＵ ｎｕｎｌｂｅｒ ｏｆ ｉｔｅｒａｔｉｏｎｓ ｃ龃ａｃｈｉｅｖｅ ｂｅｔｔｅｒ ｐｅｒｆ．０ｎｎａｎｃｅ ｔｈａｎ ｔｈａｔ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍ，ｗｈｉｌｅ ｔｈｅ ｄｅｃｏｄｉｎｇ ｃｏｍｐｌｅｘｉ哪ａ１１ｄｌａｔｅｎｃｙａｒｅｅｆｒｅｃｔｉＶｅＩｙ ｒｅｄｕｃｅｄ．５，ａ ｆ．ａｓｔ ｃｏｎＶｅ唱ｅｎｃｅ Ａａｒｅ６．Ｉｎｓｐｉｒｅｄ ｂｙ ｃｏｎｃｌｕｓｉｏｎ ｃｏｎＶｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ ｉｓｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＬＤＰＣ ｉｓ ａｃｈｉｅｖｅｄ，ｗｈｉｌｅ ｍａｋｅｓｄｅＶｅｌｏｐｅｄ． ｄｅｌａｙｂｅｔ研ｐｅ墒ｍ锄ｃｅｅ日’ｅｃｔｉｖｅｌｙｔｈｅｃｏｍｐｌｅｘｉ够ａｎｄｄｅｃｏｄｉｎｇｒｅｄｕｃｅｄ，ｗｈｉｃｈＬＤＰＣｃｏｎＶｏｌｕｔｉｏｎａＩ ｃｏｄｅｓ ｂｅ ｍｏｆｅ ｓｕｉｔａｂＩｅ ｆｏｒ ｐｒａｃｔｉｃａＩ ａｐｐｌｉｃａｔｉｏｎｓ． Ｋｅｙｗｏｒｄｓ：ｌＯ、’ｒ．ｄｅｎｓｉｔｙ ｐａｒｉｔｙ―ｃｈｅｃｋ ｃｏｄｅｓ ｃｏｎＶｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ ｑｕａｓｉ．ｃｙｃＨｃ ｃｏｄｅｓ ｉｔｅｒａｔｉｖｅ ｄｅｃＯｄｉｎｇ独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。本人签名：刘匠竿关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。本人签名： 导师签名：日期：塑ｆ翌：主！隆 日期：丝Ｚ垒：ｉ：！ｚ第一章绪论第一章绪论本章从Ｓｈ锄１０ｎ的信道编码定理出发，概述了信道编码的发展历程。然后对ＬＤＰＣ码的提出、发展以及当前研究的热点问题等进行了综述．最后给出了本文的 研究范围以及全文的章节安排．１．１信道编码的发展历程１９４８年，美国贝尔实验室的Ｃ．Ｅ．Ｓｈ锄ｏｎ在其开创性的权威论文《通信的数学理论》（Ｔｈｅ Ｍａｔｈｅｍａｔｉｃａｌ Ｔｈｅｏ巧ｏｆＣｏｍｍｕｎｉｃａｔｉｏｎｓ）【１】中提出了著名的信道编码 定理，即：对于一个给定的有噪信道，存在一个确定的信道容量Ｃ，如果信道的信 息传输速率尺小于Ｃ，则当码长Ⅳ足够大且采用最大似然译码时，总存在一种编 码方法，使接收端译码错误概率任意小，反之，如果信息传输速率尺大于信道容 量Ｃ，则不可能实现无差错通信。这个存在性定理告诉我们可以以接近信道容量的传输速率进行可靠通信，标志着信道编码这一学科的创立。但遗憾的是，该定理虽然指出了可以通过一定的编码方法在传输速率不大于信道容量的前提下实现可靠通信，但并没有给出具体实现逼近Ｓｈａ妯ｏｎ限的编码方法。从ＳｈａＩｌＩｌｏｎ信道编码定理可知，随着分组码的码长或卷积码的约束长度的增 加，系统可以取得更好的性能（即更大的保护能力或编码增益），而译码应该采用最大似然译码。但是，最大似然译码算法的复杂性随码长呈指数增加，当码长较大时，最大似然译码几乎不可实现。因此，几十年来，信道编码研究者们一直致 力于寻找纠错能力尽可能接近Ｓｈａｎｎｏｎ极限且编译码复杂度较低的可以实际应用 的信道编码方案。 线性分组码是发展最早的一类纠错码，它以代数中的群、环、域理论和有关的几何理论作为数学基础【２１。第一个线性分组码是由汉明（ＨａＩｌｌ］【Ｉｌｉｎｇ）在１９５０年发 现的，它能纠单个错误【３１。五十年代又陆续发现了Ｇｏｌａｙ码吲以及ＩＵⅥ码【５’６】，Ｂｏｓｅ和Ｈｏｃｕｅｎ曲ｅｍ在１９５９年及Ｒａｙ．Ｃｈａｕｄｈ嘶在１９６０年分别独立发现能纠正多个错误 的ＢＣＨ码■Ｒｅｅｄ和Ｓｏｌｏｍｏｎ在１９６０发现了非二进制ＲＳ码【引。卷积码是另一类重要的信道编码，它最早是由Ｅｌｉａｓ等人于１９５５年提出【引，在相同复杂度的条件下可以获得比分组码更高的编码增益，但同时也增加了分析和设 计的复杂性。随后，出现了卷积码的各种译码方法：１９６３年Ｍａｓｓｅｙ提出的门限译码【ｌｏ】是一种利用码代数结构的代数译码，１９６１年由ｗｏｚｅｎｃｒａＲ提出，１９６３年由Ｆａｌｌｏ改进的序列译码…＇１２】是一种实用的概率译码方法，ｌ ９６７年Ｖｉｔｅｒｂｉ提出的Ｖｉｔｅｒｂｉ译码【１３】是一种最大似然译码算法。当比特差错概率（ＢＥＲ）是１０。５时，非编码传输下，最２西安电子科技大学博士学位论文――Ｉ，ＤＰＣ码的代数构造及译码算法研究佳相干ＰＳＫ系统的比特信噪比（眦）与理论极限情况相差１１ｄＢ。而二进制卷积编码配合序列译码，可以使历／Ⅳｏ与理论极限仅差４．６．６．６ｄＢ。随着卷积码的各种译码方 法尤其是Ｖｉｔｅｒｂｉ译码算法的出现，卷积码逐渐得以广泛应用。 在传统的信道编码技术中，代数编码理论占据了主导地位，传统的纠错码都 不是实用好码，受到截止速率（ｃｕｔｏｆｒｒａｔｅ）的限制。Ｆｏｍｅｙ在１９６６年提出了级联码（ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｄｅｓ）【１４１，通过内码和外码的级联来获得接近信道容量的性能，同时降低了实现复杂度，向实用好码的方向前进了一大步。将ＲＳ码与卷积码级联，当ＢＥＲ为ｌｏ＿５时，系统的性能达到与理论极限大概相差１．８ｄＢ。 １９９３年，Ｂｅ盯０ｕ等人提出了Ｔｕｒｂｏ码【１５，１６１，为信道编码理论带来了突破性的革 命，打破了将截止速率作为可靠通信速率门限的概念。ＢｅｎＤｕ等人很好的应用了 ＳｈａＩｌＩｌｏｎ信道编码定理中随机编码的条件，将卷积码和随机交织器结合起来，同时采用软输出迭代译码算法来逼近最大似然译码，获得了相当接近Ｓｈ锄ｏｎ极限的译码性能。码率为ｌ／２的Ｔｕｒｂｏ码在ＢＥＲ为ｌＯ‘５时，可以获得与理论极限仅相差０．７ｄＢ的优异性能。然而，ｎ曲。码也存在一些缺点：如译码复杂度高，译码时延长，存在 错误平层现象等。Ｔｕｒｂｏ码的研究引发了人们对图模型和迭代译码的研究热潮，在研究过程中，ＭａｃＫａｙ，Ｎｅａｌ和Ｗｉｂｅ略几乎同时发现早在１９６２年由Ｇａｌｌａｇｅｒ提出的低密度奇偶 校验码（Ｌｏｗ．Ｄｅｎｓ时Ｐ撕西．Ｃｈｅｃｋ，ＬＤＰＣ，Ｃｏｄｅｓ）【１７’博Ｊ也是一种实用好码，具有比 Ｔｕｒｂｏ码更低的线性译码复杂度。在ＢＥＲ为１０击的情况下，码长为ｌＯ‘、速率为ｌ／２的ＬＤＰＣ码的性能与理论极限仅仅相差０．０４ｄＢ。与Ｔｕｒｂｏ码相比，ＬＤＰＣ码具有 译码复杂度低，更强大的纠错能力和更低的错误平层等优点，同时由于ＬＤＰＣ码 迭代译码算法为并行算法，译码时延远远小于Ｔｕｒｂｏ码。这些都为ＬＤＰＣ码的应 用提供了广阔的前景。１．２ＬＤＰＣ码的发展与现状早在１９６２年Ｇａｌｌａｇｅｒ就提出了规则低密度奇偶校验码（也称Ｇａｌｌａｇｅｒ码）和 迭代译码的概念【１７’１引。Ｇａｌｌａｇｅｒ证明了这类码具有很好的距离特性，经过迭代译码可以获得随码字长度呈指数降低的比特错误概率，虽然ＬＤＰＣ码表现出了非常好的纠错性能，但由于当时计算能力和存储能力的限制，人们并没有认识到ＬＤＰＣ 码的优越性。在ＬＤＰＣ码被提出后的三十多年时间里，并未受到应有的重视，只 有少数几篇论文对其进行了进一步的研究。这期间，最重要的成果可能就是Ｒ．Ｍ．Ｔａｎｎｅｒ提出的ＬＤＰｃ码的双向图表利１９】，在Ｔａｎｎｅｒ图上可以直观理解ＬＤＰｃ码的译码过程。 直到上世纪９０年代中期，ＭａｃＫａｙ和Ｎｅａｌ利用随机构造的Ｔａｎｎｅｒ图研究了第一章绪论３ＬＤＰＣ码的性能【２０，２¨，发现采用和积译码算法的规则ＬＤＰＣ码具有和ＴＵ曲。码相似的译码性能，长码时甚至超过了Ｔｕｒｂｏ码，这一结果引起了信道编码界的极大关注。１．２．１ＬＤＰＣ码校验矩阵的构造在ＬＤＰＣ码的构造方面，许多学者提出了各种构造方法，主要可以分为两大 类，（１）随机构造方法：根据一定的设计准则和围长、度分布、止集等条件用计 算机随机搜索出所需要的校验矩阵；（２）结构化构造方法：利用代数方法或组合 方法构造出所需要的校验矩阵。在ＭａｃＫａｙ和Ｎｅａｌ重新发现ＬＤＰＣ码优异性能的同时，Ｓｐｉｅｌｍａｎ和Ｓｉｐｓｅｒ提出了基于二部图的扩展码【２２，２３１。在对扩展码的研究中，他们证明了一个随机构造 的Ｔａ皿ｅｒ图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是渐进好码，从而证明了采用随机Ｔａｌｌｌｌｅｒ图构造的ＬＤＰＣ码以很大概率是渐进好码。Ｌｕｂｙ等人将采用非规则Ｔａｎｎｅｒ图构造的扩展图用于删除信道，称之为Ｔｏｍａｄｏ码 【２４】。由于采用了非规则的Ｔａｍｅｒ图，Ｔｏｍａｄｏ码具有更大的扩展性以及更好的收敛性，纠错能力更强。此后，采用优化度序列设计的非规则ＴａｌｌＩｌｅｒ图被用于构造 ＬＤＰＣ码，称为非规则ＬＤＰＣ码，与规则ＬＤＰＣ码相比，非规则ＬＤＰＣ码的性能得到了显著的提高。ＭａｃＫａｖ等人提出的随机ＬＤＰＣ码构造方法【２雌１】可以使码所对应的Ｔａｎｌｌｅｒ图中环数目较少，码字具有很好的纠错性能。Ｘｉａｏ．Ｙｕ Ｈｕ等学者采用 逐步最优思想提出了一种称为ＰＥＧ（Ｐｒｏｇｒｅｓｓｉｖｅ Ｅｄｇｅ Ｇｒｏｗｔｈ）的构造方法。该算 法可以在给定度序列条件下构造较大围长的ＬＤＰＣ码【２５１。ＰＥＧ算法是一种逐个建立变量节点和校验节点之间关联的构造有大环ＴａＩｌｎｅｒ图的方法。事实上，影响迭代译码性能的因素，不仅有环的长度还有环的连通性，因此Ｔａｏ Ｔｉａｎ等提出了ＡＣＥ 构造方法【２们，在构造ＬＤＰＣ码时抑制掉连通性差的环，提高了译码性能。Ｃａｍｐｅｌｌｏ 等学者提出的比特填充（Ｂｉｔ－Ｆｉｌｌｉｎｇ）【２７】及Ｅｘｔｅｎｄｅｄ Ｂｉｔ－Ｆｉｌｌｍ一２８】构造方法可以在给定校验矩阵大小，列重及最大行重时，使得围长尽可能大，或者在给定码长，围长及行列重时使得码率尽可能大。 在结构化构造方法方面，Ｓｈｕ Ｌｉｎ等学者提出了基于有限域构造ＬＤＰＣ码的方 法【２９】以及基于有限几何构造ＬＤＰＣ码的方法【３０】，这类码均为循环码或准循环（ＱＣ）码，具有较好的最小距离，消除了Ｔａｎｎｅｒ图中的４环，在高码率时可以获得较好 的性能，并且可以用简单的反馈移位寄存器实现线性时间编码。同时，ＱＣ．ＬＤＰＣ 码的代数结构也有利于高速大规模集成电路（ＶＬＳＩ）的实现。此外，他们还提出 了基于ＲＳ码构造ＬＤＰＣ码的方法，这类码也具有良好的最小距离特性【３ｌ】。Ｔａｎｎｅｒ 和Ｆｏｓｓｏｒｉｅｒ等人提出了基于循环置换矩阵构造的Ｑｃ．ＬＤＰＣ码【３２，３３】，并推导了构 造给定围长的Ｑｃ―ＬＤＰＣ码的充分必要条件。这类码容易消除小环，并且同样适宜４西安电子科技大学博士学位论文．――Ｉ，ＤＰｃ码的代数构造及译码算法研究用反馈移位寄存器实现线性编码。在此基础之上，Ｔａ皿ｅｒ利用ＱＣ．ＬＤＰＣ码的循环 矩阵构造了卷积ＬＤＰＣ码。此外，还有一些基于其他数学工具构造结构化ＬＤＰＣ 码的方法，包括平衡不完全区组设计（ＢＩＢＤ）【３４１、循环差集、二进制序列等。对于随机构造的码，校验矩阵是随机生成的，码长和码率比较灵活，纠错性能好，但是由于校验矩阵的随机性，无法实现简单编码，并且校验矩阵的存储复杂 度较高，而复杂度决定了系统结构和设计。结构化构造的码，可以克服短环的产 生，具有确定的结构，生成的ＬＤＰＣ码是循环码或准循环码，可以实现线性时间 编码，而且可以设计Ｇｉｎｈ较大的码。结构化ＬＤＰＣ码在中短码长时性能与随机构造的ＬＤＰＣ码相当，长码时略差于随机构造的码。此外，Ｄａｖｅｙ和Ｍａｃｋａｙ从减少Ｔａ衄ｅｒ图上小环的概念出发提出了基于ＧＦ（ｇ）， 印＞２的多元ＬＤＰＣ码陬３６１，进一步提高了ＬＤＰＣ码的译码性能，同时也带来了译码复杂度的提高。１．２．２ＬＤＰＣ码的编码 ＬＤＰＣ码是通过其稀疏的校验矩阵来定义的，编码也可以根据校验矩阵的校验方程实现。ＭａｃＫａｖ首先给出了ＬＤＰＣ码作为线性分组码的编码方案，利用高斯消去法通过校验矩阵得到生成矩阵，再对信息序列进行系统编码，然而利用高斯消去法得到的生成矩阵一般不是稀疏的，编码复杂度通常与码长的平方成正比。随后ＭａＣＫａｙ又提出了基于校验矩阵下三角形式的线性复杂度编码方法【３１７１，但这种 方法对校验矩阵行列重及矩阵形式进行了一定的限制，导致了一定程度的性能损 失。Ｎｅａｌ提出了基于矩阵ＬＵ分解的编码方法ｐ引，但是复杂度依然很高。 黜ｃｈａｕｒｄｓｏｎ等学者提出了基于校验矩阵近似下三角形式的低复杂度编码方法 【”】，通过对校验矩阵进行行列变换获得近似下三角矩阵，保持了校验矩阵的稀疏 性，从而在不损失性能的同时有效降低了编码复杂度。ＬｉＰｉｎｇ等提出了一类基于 半随机矩阵的编码方法ｍ】，该方法要求校验矩阵的右半边为双对角方阵，左半边为随机矩阵，可以实现线性时间编码。一类具有良好代数结构的ＬＤＰＣ码一准循环ＬＤＰＣ码具有更低的编码复杂度， 可以通过反馈移位寄存器实现线性编码【４１１，在ＬＤＰＣ码的研究领域受到了广泛的关注。１．２．３ＬＤＰＣ码的译码 Ｇａｌｌａｇｅｒ在提出ＬＤＰＣ码的同时，给出了两种迭代译码算法：硬判决Ｂｉｔ―Ｆｌｉｐｐｉｎｇ（ＢＦ）算法和软判决算法。硬判决算法操作简单，易于硬件实现，但 是性能较差；软判决算法性能较好，但实现复杂度太高。第一章绪论在硬判决算法方面，为了改善硬判决译码的性能，Ｙ Ｋｏｕ等提出了一种基于软信息的加权比特翻转（ＷＢＦ）算ｉ去【３０ｌ，在每轮迭代中，对每个变量节点按某种方法计算其可靠性，将可靠性最小的变量节点进行翻转，ＷＢＦ算法在性能上优于硬 判决ＢＦ译码算法，但引入了可靠性的计算，导致译码复杂度增加。由于ＷＢＦ算 法在计算变量节点的可靠性时仅考虑了校验节点的信息，Ｊ．Ｚｈａｎｇ等人提出了改进的加权比特反转（ＭｗＢＦ）算法【４２１，在计算变量节点可靠性时加入了变量节点的 信息，提高了译码性能。Ｆ．Ｇｕｏ等人注意到ＷＢＦ和ＭＷＢＦ算法中只考虑了校验节点的特定信息，其提出的ｌ湛ＷＢＦ考虑了校验节点的全部信息【４３】，进一步提高了性能，而没有增加复杂度。在软判决算法方面，Ｇａｌｌａｇｅｒ提出了消息传递算法（ＭＰＡ，ＭｅｓｓａｇｅＰａｕｓｓｉｎｇＡ１９０ｒｉｔｈｍ）【１７】，也称置信传播算法（ＢＰ，ＢｅｌｉｅｆＰｒｏｐａｇａｔｉｏｎＡｌｇｏｒｉｔｌｌＩｌｌ），Ｋｓｃｌｌｉｓｃｈａｎｇ等对消息传递算法作了推广ｍ１，将它扩展为一种更加通用的算法一和积算法（ＳＰＡ，Ｓｕｍ―ＰｒｏｄｕｃｔＡ１９０ｒｉｔｈｍ），并指出和积算法实际上包含了大量的实用译码算法（如前向／后向算法、Ｐｅａｒｌｓ传播算法、ｖｉｔｅｒｂｉ算法等）。和积算法在迭代过程中需计算 三种中间变量消息，即变量消息，校验消息和软判决消息。如果将软判决消息作为变量消息进行迭代，则和积算法简化为迭代ＡＰＰ（ａｐｏｓｔｅｒｉｏｒｉｐｒｏｂａｂｉｌｉｔｙ）算法，可以在损失一点性能的基础上减少运算复杂度。和积算法在计算校验消息时需要用到双曲正切运算，实现较为复杂，Ｆｏｓｓｏｒｉｅｒ研究了低复杂度的迭代译码算法【４５，４６】， 将校验消息的计算简化为简单的求符号运算和求最小值运算，提出了ＢＰ．Ｂａｓｅｄ算法（也称最小和算法（ＭｎＳｕｍＡｌｇｏｒｉｔｈｍ））和ＡＰＰ．Ｂａｓｅｄ算法。由于校验消息计 算的简化，ＢＰ．Ｂ雏ｅｄ算法的性能受到了一定的影响，修正ＢＰ―Ｂａｓｅｄ算法一 Ｎｏｍａｌｉｚｅｄ ＢＰ．Ｂａｓｅｄ算法和Ｏ凰ｅｔ ＢＰ．Ｂａｓｅｄ算法通过对校验消息计算的进一步修正可以在不太增加复杂度的基础上获得性能的较大提高。综上所述，ＬＤＰＣ码采用迭代译码算法，在复杂度和性能上可以得到很好的折 中，既可以选择实现简单、性能稍差的ＢＦ算法，也可以选择实现复杂、性能优越 的ＢＰ算法，又可以选择趋于中间的各种改进算法。 在译码性能分析方面，Ｔａ加ｅｒ在文献［１９］中详细分析了最小和算法与和积算法 两种信息传递算法，并证明了基于有限无环Ｔａ衄ｅｒ图的最小和译码算法与和积译 码算法的最优性。但在实际当中，Ｔａ皿ｅｒ图中不可避免的存在小环路现象，小环 路会造成译码信息的重复传递，使译码过程中的消息不满足独立性假设，从而影 响了迭代译码算法的收敛性。Ｒｉｃｈａｒｄｓｏｎ等学者利用密度进化理论来测度ＬＤＰＣ码的译码性能【４７．４８１。Ｒｉｃｈａｒｄｓｏｎ等在对ＬＤＰＣ码的研究中发现，译码信息的迭代传递 过程中存在着译码阈值（ｔｈｒｅｓｈｏｌｄ）现象，即当信噪比大于译码阈值时，迭代译码 可使误码率趋于零，反之当信噪比小于译码阈值时，无论采用多长的ＬＤＰＣ码，经过多少次迭代译码，总存在一定的错误概率。应用中心极限定理，Ｒｉｃｈａｒｄｓｏｎ等６西安电子科技大学博士学位论文――Ｉ，ＤＰＣ码的代数构造及译码算法研究证明了有限随机有环图的译码阈值可以逼近无环图的译码阈值。通过建立在无环 图上的密度进化理论，可以精确地计算无环图上ＬＤＰＣ码的译码阈值，分析其译 码收敛条件，从而近似估算有环Ｔａｒｕｌｅｒ图上ＬＤＰＣ码的性能。研究表明，译码阈 值的大小与ＬＤＰＣ码的构造参数密切相关，采用优化度序列设计的非规则ＬＤＰＣ 码可以有效地改善阈值，因此密度进化理论不仅可以分析译码性能，还可以用于 指导ＬＤＰＣ码的优化设计。Ｃｈｕｎｇ等人通过对密度进化理论的研究【４９巧¨，进一步提出了应用高斯逼近原理来简化译码阈值计算和收敛性分析，从而使测度ＬＤＰＣ码性能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高斯逼近模型。１．３论文的内容安排及研究成果本文研究了分组ＬＤＰＣ码的代数构造，比特翻转译码算法以及卷积ＬＤＰＣ码的迭代译码算法等问题，获得了几个关键性的研究成果。全文共分为七章，其余章节具体安排如下。 第二章给出了ＬＤＰＣ码的定义及其分类，重点介绍了ＬＤＰＣ码的Ｔａｎｎｅｒ图模型表示，最后分析了ＬＤＰＣ码的迭代译码算法一和积算法及其简化形式一最小和算法。 第三章主要介绍了准循环ＬＤＰＣ码的基本原理，分析了阵列ＬＤＰＣ码的结构特征，推广并改进了基于中国剩余定理的由短分量码设计长码的准循环ＬＤＰＣ码构造方法，获得了一类具有更好纠错性能的准循环ＬＤＰＣ码。第四章研究了欧氏几何ＬＤＰＣ码的构造技术，提出了两种准循环ＬＤＰＣ码的 构造方法。第一类准循环ＬＤＰＣ码是基于循环置换矩阵设计的，其相应的Ｔａｌｌｌｌｅｒ 图中具有较少的短环。第二类准循环ＬＤＰＣ码是基于循环矩阵设计的，该类码具有较低的错误平层性能。 第五章分析了ＬＤＰＣ码各种基于软信息的比特翻转译码算法，提出了一种具有极低计算复杂度的改进比特翻转译码算法，该方法运用两个译码门限，从而有效地提高了译码性能。第六章基于卷积ＬＤＰＣ码连续数据编译码传输的结构特性，给出了两种高效 的迭代译码算法。算法一为迭代反馈译码算法，利用反馈信息有效加快了信息传 递速度，降低了译码复杂度并减小了译码时延；算法二将算法一与已有译码算法 相结合形成一种卷积ＬＤＰＣ码的快速收敛译码算法，译码器具有更低的译码复杂度及译码时延，从而使卷积ＬＤＰＣ码更适于实际应用。 第七章为全文的总结与展望。第二章ＬＤＰＣ码的编译码原理７第二章ＬＤＰＣ码的编译码原理本章首先介绍了ＬＤＰＣ码的定义，并且阐述了ＬＤＰＣ码的分类；然后给出了 ＬＤＰＣ码的图模型表示；最后分析了ＬＤＰＣ码的迭代译码算法一和积算法及其简化 形式一最小和算法。２．１ＬＤＰＣ码的定义ＬＤＰＣ码最初由Ｇａｌｌａｇｅｒ于ｌ ９６２年提出，然而之后的三十年里却被人们所遗 忘，仅有少数学者对其进行了少量研究。直至Ｔｕｒｂｏ码的出现，ＬＤＰＣ码才又重新 受到人们的关注。 域ＧＦ（ｇ）上的ＬＤＰＣ码是一种线性分组码，由其校验矩阵日的稀疏性而得名，即校验矩阵中大部分元素为“０＂，仅包含很少的非零元素。码长为疗，信息序列长为七的ＬＤＰＣ码Ｃ可以由校验矩阵Ｈ唯一确定，码Ｃ就是日的零空间，日的每一 行对应一个校验方程，每一列对应码字的一个比特，满足如下方程的刀维向量ｌ，：纠７Ｔ：０（２－１）即为码Ｃ的一个码字。日的每一行中非零元素的个数称为日的行重，每一列中非零元素的个数称为日的列重。根据校验矩阵行列重的不同，ＬＤＰＣ码可分为两类： 规则（ｒｅｇｕｌａｒ）ＬＤＰＣ码和非规则（ｉｒＴｅｇｕｌａｒ）ＬＤＰＣ码。若校验矩阵日每行的非零元素个数相同，且每列中非零元素个数也相同，则该ＬＤＰＣ码称为规则ＬＤＰＣ码，否则称为非规则ＬＤＰＣ码。下面给出规则ＬＤＰＣ码的定义。定义２．１：（厂，ｐ）．规则ＬＤＰＣ码定义为具有如下结构特性的校验矩阵日的零空间： （１）Ｈ的每行行重为常数ｐ； （２）日的每列列重为常数ｙ； （３）与码长和日的行数相比，ｐ和ｙ都很小。上述特性（３）表明校验矩阵日中非零元素的密度很小，即校验矩阵具有稀疏性。例２．１给出了一个码长为１５的（４，４）．规则ＬＤＰＣ码的校验矩阵。例２．１考虑式（２．２）给出的矩阵何，该矩阵的行重和列重均为４，与码长和Ⅳ 的行数相比，行重和列重都比较小，非零元素“ｌ’’所占的比例为０．２６７，日是～个稀疏矩阵，其零空间为一个码长为１５的（４，４）．规则ＬＤＰＣ码。８西安电子科技大学博士学位论文――ＬＤＰｃ码的代数构造及译码算法研究０ １ ０ Ｏ ０ ｌ ０ Ｏ ０ １ Ｏ Ｏ Ｏ ｌ ０ １ １ ０ ０ Ｏ ０ Ｏ Ｏ Ｏ ０ ｌ ０ ０ ０ ｌ Ｏ ｌ ｌ Ｏ ０ Ｏ ０ Ｏ ０ ０ ０ ｌ ０ Ｏ ０ ｌ ０ ｌ ｌ ０ ０ Ｏ Ｏ ０ ０ ０ Ｏ ｌ Ｏ Ｏ Ｏ １ Ｏ １ ｌ ０ ０ ０ ０ Ｏ Ｏ Ｏ ０ １ ０ Ｏ Ｏ １ Ｏ ｌ １ Ｏ Ｏ Ｏ Ｏ Ｏ Ｏ Ｏ ０ １ ０ Ｏ ０ ｌ ０ ｌ １ ｌ Ｏ Ｏ Ｏ Ｏ Ｏ Ｏ Ｏ １ ０ Ｏ ０ ｌ ０ ｌ ｌ １ Ｏ ０ ０ Ｏ ０ Ｏ ０ ｌ ０ ０ ０ １ ０ ０ １ ｌ ０ ０ ０ Ｏ Ｏ ０ ０ ｌ Ｏ Ｏ ０ ｌ ｌ Ｏ ｌ ｌ ０ ０ Ｏ Ｏ Ｏ Ｏ ０ ｌ ０ Ｏ Ｏ Ｏ ｌ Ｏ １ １ ０ Ｏ ０ Ｏ ０ ０ ０ ｌ ０ ０ Ｏ ０ １ Ｏ ｌ １ ０ Ｏ ０ ０ ０ ０ ０ ｌ ０ Ｏ Ｏ ０ ｌ Ｏ ｌ １ Ｏ ０ ０ ０ ０ Ｏ Ｏ １ ｌ ０ ０ ０ １ Ｏ １ ｌ Ｏ ０ ０ ０ ０ ０ Ｏ日＝１ ｌ ０ ０ Ｏ Ｏ ０ Ｏ（２．２）根据校验矩阵中元素取自的域不同，ＬＤＰＣ码可分为二元ＬＤＰＣ码和ｇ元ＬＤＰＣ 码。口元ＬＤＰＣ码可获得比二元ＬＤＰＣ码更好的纠错性能，但同时具有更高的译码复杂度，本文主要考虑ＧＦ（２）上的二元ＬＤＰＣ码。根据校验矩阵的构造方法不同，ＬＤＰＣ码还可以分为随机ＬＤＰＣ码和结构化ＬＤＰＣ码。随机ＬＤＰＣ码构造比较灵活，给定任意码长码率，可较容易构造出一类随机ＬＤＰＣ码，结构化ＬＤＰＣ码具有确定的结构，可实现简单编码且存储复杂度较低。２．２ＬＤＰＣ码的图模型表示ＬＤＰＣ码由于其优异的纠错性能及其简单的迭代译码而备受研究学者们的青 睐，其迭代译码是基于图模型【１９朋，５２，５３】进行消息传递及消息更新的，因此，有必要 介绍一下ＬＤＰＣ码的图模型表示。定义２．２：图（ｇｒａｐｈ）Ｇ定义为一个三元组（ｙ，Ｅ，①），其中ｙ≠ａ，是图Ｇ的节点集合，Ｅ是边的集合，①是边集到节点对ｙ×ｙ上的关联函数。如果节点ｖ∈ｙ是边Ｐ∈Ｅ的端点，则称１，和Ｐ是相连的。与节点１，∈ｙ相连的边的个数称为节点’，的度，记为ｄ（１，）。若节点与边的交替序列（ｖｌ，Ｐｌ，屹，Ｐ２…．，坛，％ 峙１）满足：与“ｌ≤ｆ≤七）相连的节点为¨和ｖｆ＋ｌ，则称此序列为一条路径，其中 ’，ｌ和％１分别称为起始节点和终止节点。若一条路径的起始节点和终止节点为同一节点，并且路径中其他节点仅出现一次，则此路径构成一个环（ｃｙｃｌｅ）。环的长度 为环所经过的边的数目，图Ｇ中最短环的长度称为图Ｇ的围长（百ｎｈ）。定义２．３：若图Ｇ的节点集合ｙ可以划分为两个子集Ｋ和％，且满足第二章ＬＤＰＣ码的编译码原理９Ｋ ｕ％＝矿，Ｋ ｎ圪＝ａ，使得任意边Ｐ∈Ｅ的一个端点属于集合Ｋ， 另一个端点 属于集合砭，则称图Ｇ为二部图（ｂｉｐａＩｔｉｔｅ伊印ｈ）。 若Ｋ中所有节点的度都相等，并且圪中所有节点的度也都相等， 则称Ｇ为规 则二部图，否则称为非规则二部图。 定义２．４：ＧＦ（２）上的ＬＤＰＣ码的Ｔａ咖ｅｒ图，与其校验矩阵日＝（％）…一一对应，可以表示为如下二部图：（１）日的每一行对应于一个校验节点，记为ｃｌ，乞，…，ｃ册； （２）Ｈ的每一列对应于一个变量节点，记为Ｖｌ，Ｖ２，…，Ｋ； （３）当且仅当％＝１（１≤ｉ≤加，１≤，≤，ｚ）时，变量节点吩和校验节点Ｑ之间有一条边相连，该边记为（吩，∞。由定义２．４可以看出，校验节点的度即为Ｈ的行重，即参与该行对应校验方 程的变量节点的个数，变量节点的度即为日的列重，即该列对应码字比特参与的校验方程的个数。若变量节点吻与校验节点ｃ，相连，即％＝ｌ，我们称变量节点吻 参与了校验节点（校验方程）臼。例２．２考虑式（２．３）给出的矩阵麒其零空间为一个（７，４）线性分组码。它的Ｔａｎｎｅｒ图如图２．１所示。其中左边的圆圈代表变量节点，右边的方框代表校验 节点（校验方程）。变量节点１，ｌ的度为ｌ，１，ｌ仅参与了一个校验节点ｃｌ，变量节点 如的度为２，怕参与了两个校验节点ｃ２和ｃ３。如图２．１中黑色粗线条所示，节点（ｃ２， ｖ５，ｃ３，Ｖ６，ｃ２）构成了一个长度为４的环。巧哆哆吩吩修哆月＝ｌＩ１ ｏ ｏｏ ｌ ｏｏ ｏ ｌ１０ ｌ ｏ ｌ １１１ ｌ １ ｏ ｌＩＩｃｌ’ ｃ２ ｃ３（２－３）ＩＩ坼 吃 吩 以 略 诈 ｎ巧ｊ巧手吩＋屹＋哆＝Ｄｃ２：屹＋Ｋ＋坞＋％＝０巳：匕＋ｖ５＋心＋ｖ７＝０图２．Ｉ（７，４）线性分组码对应的Ｔａｎｎｅｒ图１０西安电子科技大学博士学位论文――Ｉ，ＤＰＣ码的代数构造及译码算法研究对于（，，，ｐ）．规则ＬＤＰＣ码，其ＴａＩｌｌｌｅｒ图中所有校验节点的度都相同，等于尸，所有变量节点的度也都相同，等于厂。而对于非规则ＬＤＰＣ码，其Ｔａ衄ｅｒ图中校 验节点的度不一定相同，变量节点的度也不一定相同，一般用其度分布序列｛肛）和｛以｝或者多项式ｐＯ）和五Ｇ）来表示‘５４’５５１：尸（ｘ）＝∑生ｌ房ｘ“Ａ（ｘ）＝∑皂。旯，ｘ，．１（２４） （２．５）其中ｐ，表示与度为ｆ的校验节点相连的边的个数与总边数之比，名，表示与度为，的变量节点相连的边的个数与总边数之比，以和Ｚ，分别是最大校验节点度数和最大变量节点度数。易知∑生。辟＝１并且∑篙Ａ，＝１。 ‘Ｊ…’’‘Ｊ，一’，一个ＬＤＰＣ码Ｃ有多个不同的校验矩阵，即不同的校验矩阵的零空间可能给出同一个码，因此码Ｃ具有多个ＴａＩｌＩｌｅｒ图表示，尽管这些Ｔａｎｎｅｒ图对应同一个码， 但基于不同Ｔａｎｎｅｒ图的迭代译码将会给出不同的译码性能，所以构造ＬＤＰＣ码的校验矩阵时需遵循一定的准则，以获得较好的纠错性能。由于Ｔａ衄ｅｒ图为二部图， 并且任意两节点之间最多有一条边相连，因此图中的环长度均为偶数且大于等于４，其围长也为偶数且大于等于４。短环尤其是４环会严重影响基于图模型的迭代译码算法的性能，因此在构造ＬＤＰＣ码时需尽量避免短环尤其是４环的出现。２．３ＬＤＰＣ码的译码ＬＤＰＣ码的迭代译码算法相对简单，译码复杂度与码长成正比，并且可实现全 并行译码，有利于硬件实现。ＬＤＰＣ码的和积译码算法是一种基于Ｔａ衄ｅｒ图的迭 代概率译码算法，每轮迭代中，变量节点与校验节点沿着ＴａＩｌＩｌｅｒ图上的边进行概率信息传递。已经证明，和积算法是基于有限无环图的最优迭代译码算澍１９１。２．３．１和积算法 考虑加性高斯白噪声信道（ＡｗＧＮ），信道模型如图２．２所示，其中＂＝（“。，“：，…，‰）为信息序列，编码后的码字序列为ｌ，＝（Ｍ，屹，…，屹），经过ＢＰＳＫ调制后得到序列ｘ＝（ｊｃｌ，也，…，‘），进入加性高斯白噪声信道，信道输出序列 Ｊ，＝（Ｍ，耽，…，只）送入译码器进行译码，得到估计序列玎＝（玩，五：，．．．，玩）。图２．２信道模型第二章ＬＤＰＣ码的编译码原理和积译码算法主要分为三个步骤：初始化，迭代过程及译码判决。首先进行初始化，每个变量节点根据信道输出值计算其先验消息，然后进入消息迭代过程。 每轮迭代中，每个校验节点根据收到的最新消息进行消息更新并将更新后的消息 传递给与其相连的每个变量节点；然后每个变量节点利用初始消息及收到的最新 校验节点消息进行消息更新，并将更新后的消息传递给与其相连的每个校验节点。每轮迭代后，每个变量节点进行译码判决，若得到的判决序列满足所有的校验方 程则退出译码过程并显示译码成功，否则继续进行新一轮的迭代直至译码成功或 者达到预先设定的最大迭代次数并显示译码失败。令Ｍ（，）＝｛ｑ：％＝１）表示变量节点巧参与的所有校验节点的集合，即校验矩阵 Ｈ第ｊ『列中非零元素“ｌ’’所在行的集合，膨（／）＼ｆ表示集合Ｍ（＿，）中除去校验节点白后的子集，Ⅳ（ｆ）＝｛Ｖ，：％＝１）表示参与校验节点白的所有变量节点的集合，即校验矩阵日第ｆ行中非零元素“ｌ＂所在列的集合，Ⅳ（ｆ）＼／表示集合Ⅳ（ｆ）中除去变 量节点’，，后的子集。 下面给出概率测度下和积译码算法的具体步骤：?初始化：初始消息∥定义为在接收到乃的条件下■＝口（口∈｛＋ｌ，一ｌ｝）的概率： 疗＝尸（■＝口Ｉ乃）：＝?―－－－－－－二－－―－－二―??－－－－－－－－－－－－―＝－－－－－?－一厂（ｙ，Ｉｘ，＝口）Ｐ（ｘｆ＝口） 尸（少，）均值为零，方差为仃２的ＡＷＧＮ信道的转移概率满足：／（Ｊ，ｌｘ）＝兀：。厂（咒Ｉｔ）其中，他肾加击ｃｘｐ｛一譬｝，口∈｛＋１，－１）。因此，疗＝等去卅譬，假设巧为等概传输，即Ｐ（而＝＋１）＝Ｐ（而＝一１）＝１／２，在给定ｙ，的条件下，有霄七ｆ＿１４＝、因此ｒ可由下式（２―６）计算得到。１２西安电子科技大学博士学位论文叫ＤＰＣ码的代数构造及译码算法研究肛蠢赤志ｅＸｐ｛＿譬）２Ｐ（＂）√２万盯‘‘ ’―――产＝．ｅ）【Ｄ｛一Ｉ＝－二―＿―一｝ ２盯２（２－６）令缮为变量节点哆向与其相连的校验节点。传递的变量消息，定义为变量节 点吁根据信道输出值及与其相连的其他校验节点｛仅：七∈Ｍ（／）＼Ｄ向白宣称而＝口的概率。鳞＝Ｐ（而＝口Ｉ”，｛“｝ｔ。Ｍ（，）、ｆ） 令彤是校验节点Ｄ向与其相连的变量节点吁传递的校验消息，定义为校验节 点。根据与其相连的其他变量节点愀：七∈Ⅳ（ｆ）＼ｎ的当前状态，向而宣称在而＝口 的条件下校验关系Ｄ满足的概率。 霹＝Ｐ＠Ｉ而＝口） 由变量消息和校验消息的定义可知，初始化时，应将变量消息荡初始化为片， 将校验消息群初始化为１／２（因为在迭代开始时认为ｘ，－一ｌ和ｘ，＿ｌ使得校验关系 成立的概率是相同的）。 ?迭代过程：迭代过程包括两个步骤，第一步为校验节点的消息更新，校验节点与校验矩 阵的行一一对应，因此这一步也称为水平步骤；第二步为变量节点的消息更新，变量节点与校验矩阵的列一一对应，因此这一步也称为垂直步骤。 （１）校验节点消息更新（水平步骤）：每一个校验节点Ｑ根据与其相连的变量节点的最新消息计算新的校验消息，并向与其相连的变量节点Ⅵ传递更新后的校验消息嬲，校验消息更新公式的推导过程由式（２．７）给出。这里需要说明的是，式（２．７）的第五行是在假设各个比特相互独立（独立性假设）的情况下得到的，如果不满足独立性假设，则式（２．７）计算的校验消息就不是真正的校验消息了，即和积译码算法就不是最优了。ＴａｌｌＩｌｅｒ图中的环会使传 递的消息产生一定的相关性，因此，在设计校验矩阵时应使其对应的Ｔａ衄ｅｒ图的围长尽可能大，从而保证消息具有最大可能的独立性。第二章ＬＤＰｅ马的缠译码原理１３巧＝Ｐ（ｑ Ｉ一＝口）＝∑尸（ｑ，ｘＩ乃＝口）ｌ：’５口之∑尸（ｑ ｌ而＝¨）尸（ｘｌ＿＝口）：∑Ｐ（ｑ Ｉ工）Ｐ（ｘｌ＿＝口）ｘ：勺２４（２－７’＝∑Ｐ（ｑ ｌ工）ｎ尸（吒）ｚ：０５４ Ｉ∈Ⅳ（ｆ）、Ｊ＝∑户（ｑ ｌ ｘ）ｎ黠（２）变量节点消息更新（垂直步骤）： 每一个变量节点Ｖ，根据信道输出值及与其相连的校验节点的最新消息计算新的变量消息，并向与其相连的校验节点ｃ，传递更新后的变量消息鳞，变量消息更新公式的推导如下：饼＝Ｐ（■＝口ｌ乃，｛ｑ：七∈Ｍ（，）＼叫Ｐ（ｘ，＝口，ｙ，，｛ｑ：后∈Ｍ（，）Ｕ））尸（ｙ，，｛ｑ：七∈Ｍ（，）＼ｆ｝）Ｐ（■＝口，乃）Ｐ（｛ｑ：后∈Ｍ（，）＼圳■＝口，乃）户（夕，，｛ｑ：后∈Ｍ（，）＼ｆ｝）Ｐ（■＝口ｌ乃）Ｐ（｛ｑ：七∈膨（，）Ⅵｌｔ＝口，乃）户（｛ｃＩ：七∈肘（『）Ｖ｝Ｉｙｆ）：――――――型型生―Ｔ―一 Ｐ（｛ｑ：七∈ＭＵ）＼ｆ）ｌｙ，）Ｐ（＿＝口Ｉ乃）兀Ｐ（ｑＩ＿＝口）２赢忑切而∥。瓢Ⅳ喵＝％Ｆ兀弼（２．８）其中，嘞＝１／Ｐ（奴：七∈Ｍ（『）＼ｆ）ｌ乃）为归一化因子。注意到式（２―８）的第五行也是在独立性假设的条件下得到的，即假设各个校验关系相互独立。 ?译码判决 码字比特ｘ，（／＝ｌ，２，…，，ｚ）的最终变量消息研定义为该码字比特关于信道输出 值和码结构的后验概率尸（ｘ，＝口Ｉ ｙ，，奴）。“（，））。每轮迭代完成后，对每个码字比特 ｘ；计算其最终变量消息。计算公式推导如下：１４西安电子科技大学博士学位论文＿Ｉ ＤＰＣ码的代数构造及译码算法研究ｇ＝Ｐ【■＝口ｌ乃，｛ｑ）ｔ“（一 Ｐ【｛ｑ）Ｉ。村ｆ∥一＝口Ｉ乃） ＪＰ【｛ｑ）ｔ“（刊乃）：！！坠！！竺塑！羔三竺：丝！！！兰三竺！丝２Ｐ【｛ｑ）删（Ｄ Ｉ乃）＝＝＿＿―＿―――＿＿－＿＿＿?－――＿＿―？。－＿＿＿－－?＿－－＿＿＿－－＿?＿‘？’＿－＿＿?＿＿＿－＿＿－?＿一（２．９）～二‘了，２雨去厕Ｐ（铲Ｉ驯。现，尸（ｑ肾口）＝哆疗兀弼其中口，是归一化常数。计算得到后验概率之后，作出如下硬判决：Ｉ＝鹕峄ｇ＝ａｒｇｍ≯哆∥兀筋。 。（２－ｌｏ）ＩＥ肘（，）这样就得到了对发送码字的一个估计移＝（Ｅ，也，…，吃）。计算伴随式；＝婀Ｔ，如果伴随式为全零向量，则宣告译码成功，终止迭代过程并输出译码结果痧；否则，继续迭代过程直至译码成功或达到预定的最大迭代次数为止。如果经过最大迭代 次数之后译码仍然没有成功，则宣告译码失败并输出最后一轮迭代的译码结果移。 二元随机变量ｘ的概率测度有两个取值ｎ。＝ＰＯ＝＋１）和见。＝ＰＯ＝一１），为 了将这两个概率取值用一个度量值替代，减少和积算法中所需传递的消息数量， 通常使用概率差，似然比（ＬＲ）和对数似然比（ＬＬＲ）这三种度量：概率差：△（石）＝ｎｌ一正ｌ 似然比：上Ｒ（ｘ）＝以Ｉ／ｎｌ对数似然比：儿尺（ｘ）＝ｈｌ（ｐ＋ｌ／ｐ．Ｉ）基于概率测度的和积译码算法涉及很多乘法运算，硬件难以实现，而对数似然比度量的和积译码算法可以将乘法运算转化为加法运算并且可省去归一化的计算，在实际应用中比概率度量和似然比度量的和积译码算法更有优势。下面给出 对数似然比度量下的消息更新公式的推导过程。 考虑一个度为三的变量节点石，，根据消息更新规则，当从两个校验节点发出的消息（以。，ｎ。），（ｇ＋。，吼。）到达该变量节点时，该变量节点向第三个校验节点传递的消息纪，为已知接收的两个校验节点消息时，ｚ『－口的概率，可表示为：纯（几ｌ，ｎｌ，吼ｌ，ｇ＿１）：（――鱼笪±Ｌ，――竺扣ｐ＋ｌｇ＋ｌ十ｐ―ｌｇ―ｌ（２．１１）ｎＩｇ＋Ｉ十Ｊ卫ｌｇ一１考虑一个度为三的校验节点，根据消息更新规则，当从两个变量节点发出的消息第二章ＬＤＰＣ码的编译码原理（以。，ｎ。），（ｇ＋。，乳。）到达该校验节点时，该校验节点向第三个变量节点传递的消息 仍为已知接收的两个变量节点消息时，第三个变量节点却＝口使该校验关系成立的 概率，可表示为： 织（ｎＩ，ｐ－ｌ，吼ｌ，乳１）＝（ｎｌｇ＋ｌ＋ｐ．１９．１，ｎｌｇ－ｌ＋ｎｌｇ＋１）（２－１２）消息更新规则很容易推广到度数更高的节点。此时，变量节点和校验节点的消息更新公式为： 吼（而，ｘ２，…，工。）＝仇（■，纯（屯，…，‘）） 织（工ｌ，也，…，ｘ。）＝纯（ｘｌ，织（屯，…，‘））（２－１３） （２－１４）如果使用对数似然比度量，大量乘法运算则转变为加法运算，可以大大减少运算量，初始消息，变量消息和校验消息分别定义为￡（乃）＝ｌｌｌ（∥１／ｆ１），三（ｇ）＝ｌＩｌ（鲂１／绣１）和￡（吩）＝ｌＩｌ（巧１／巧１）。 三（乃）＝ｌＩｌ（∥１／疗１）＝２乃／盯２纯（‘，乞）＝ｈｌ（ｎ。ｇ＋。／正。乳。）＝‘＋乞州㈣乩（觥）ｎｌｇ－ｌ＋ｎｌ吼１校验消息更新公式稍微复杂一些，推导如下，由ｔａ】血（叫２）＝吾吾有：删枞）／２卜笠兰若：丝！丝！±丝ｌ丝！＝丝！丝ｌ二丝！纽ｐ＋ｌｇ＋ｌ＋ｐ．１９―ｌ＋ｐ＋ｌｑ『＿Ｉ＋ｐ―ｌｇ＋ｌ：！丝！二垦！丛丛！二垡＝１２酗鼬刚２）＝嬲＝等等’所％以ｌ／见ｌ＋ｌ ｔ以ｌ＋ｎｌＪ 如下：（ｐ＋ｌ＋ｎ１）（ｇ＋ｌ＋ｇ．Ｉ）ｔａＩｌｌｌ（敛（ｆｌ，乞）／２）＝ｔａｎｈ（ｆｌ／２）（ｔａｌｌｈ（乞／２）将更新公式推广到度数更高的节点，则对数似然比度量的和积算法具体实现步骤１）初始化：变量消息上（Ｑ：ｆ『）初始化为由信道输出乃计算得到的变量节点先验１６西安电子科技大学博士学位论文――ＬＤＰＣ码的代数构造及译码算法研究消息三（‘），校验消息三（Ｒ）初始化为ｏ。 三（ｇ）＝三（乃）＝２乃／仃２，三（局）＝ｏ。２）迭代过程： ?校验节点更新：（２一１５）啦）瑚划（。飘ｕ蛐（兰￡（级））］＼★ＥⅣ（ｊ）Ｕ＼‘协㈣／／◆变量节点更新：三（９）＝￡（乃）＋∑三（如）３）译码判决： ?计算最终变量消息：（２?１７）三（９）＝三（办）＋∑三（岛）?硬判决：（２―１８）睁ｊ１’’以ｇ）＜ｏ ￡（９）≥ｏ（２－１９）【ｏ，如果讲Ｔ＝Ｏ，说明已找到一个正确码字，终止迭代，显示译码成功并输出译码结果痧，否则返回第２）步继续迭代过程直至译码成功，或者达到最大迭代次数停止迭代显示译码失败并输出最后一轮迭代的译码结果痧。２．３．２最小和算法 对数似然比度量的和积算法具有优越的性能和较低的复杂度，得到了广泛的应用。为了进一步降低译码复杂度，文献［４５，５２］提出了一种简化的对数域和积算法，即最小和（Ｍｉｎｉｍ蚰．Ｓ眦）算法，仅需要进行加法运算就可以完成ＬＤＰＣ码的译码，大大降低了译码的实现复杂度。 在对数似然比度量的和积算法消息更新中，变量消息更新只需要加法运算， 实现比较简单，而校验消息更新需要双曲正切运算，实现较为复杂，最小和算法 运用双曲正切函数的性质，可以简化计算。双曲正切函数具有以下性质： ｔａｎｈ（ｘ）＝ｓｇｎ（工）ｔａｎｈ（１ ｘ Ｉ） ｔａｎｈ叫（工）＝ｓ印（ｘ）ｔａｎｌｌ叫（Ｊｘｌ） 因此，对数似然比度量的和积算法中校验消息更新公式可写为：第二章ＬＤＰＣ码的编译码原理１７三（岛）２鼬一（飘，ｔａｎｎ（圭￡（ｇ）））ｔａｎｈ―ｌ兀ｓ驴（三（级））ｎ ｔａｌｌｌｌＩ毒Ｉ三（级 兀ｓｇｎ（三（级））ｔａｎｈ―ｌ兀ｔａＩｌｈｌ专ｌ￡（级、ｌ，、ｌ，一、●，●、 、●，●／２＝２、，● ，、● ．／令痧（力＝一１０９ｔａｎｈ（主）＝１０９吾等，≯（砷具有如下性质：矽（曲＝≯．１（力，即矽（矽（ｘ））＝ｘ，贝ｌＪ２鼬一（取，蛐（扣级）Ｉ）］、￣七Ｅ＾ｒ（ｆ）、Ｊ４ ｎ ＼厶一，／２ｔａｒｌｌｌ一１昭 ｇ／●●＿／ “一、札（ｇ―；＝２ｔａｎｈ一１昭ｎ －ｌＯ Ｖ ．）厂●●●一／扯（级二、－，、ｌ，《＝≯Ｉ∑ “ 陋 ｇ、＝Ｈ＼ ＬｔＥ．ｖ（Ⅲ呵∑一慨 １ ｎ㈣崦厂三…量心¨∥＂图２．３给出了函数≯（工）的曲线，可以看出，随着ｘ的增大，函数烈ｘ）的值迅速减小，ｘ越小，矽（ｘ）的值越大，由此可知三（岛）更新公式中起主要作用的是绝对值最小的 三（锄），因此，矽（。。磊、，矽（Ｉ￡（级）Ｉ））≈≯（。骢，≯（Ｉ三（级）１））＝。骢，ＩＬ（甄）Ｉ图２．３函数矽（ｘ）的示意图１８西安电子科技大学博士学位论文――Ｉ ＤＰｃ码的代数构造及译码算法研究校验消息的更新公式最终简化为：三（岛）＿。飘ｕｓ矗（三（级））（。哿豫，ｋ（甄）１）最小和算法的实现步骤如下：１）初始化：（２－２。）三（岛）＝三（ｇ）＝２乃／盯２，三（毛）＝ｏ?２）迭代过程： ?校验节点更新：……’７ ￡（岛）＝。］［：｜｜、．ｓｇＩｌ（三（级））（。珊弧，陋（级）１）ＩｅⅣ（ｆ）、，７（２－２１）‘２－２２）?变量节点更新：三（９）＝￡（办）＋∑￡（如）３）译码判决（２―２３）●计算最终变量消息：三（９）＝三（办）＋∑￡（如）ＩＥ肘（，）（２－２４）?硬判决：蜘Ｊ１’ ｌｏ，７以ｇ）＜ｏ三（Ｑ，）≥ｏ（２－２５）如果触Ｔ＝Ｏ，终止迭代，显示译码成功并输出译码结果痧，否则返回第２）步继续迭代过程直至译码成功，或者达到最大迭代次数停止迭代显示译码失败并 输出最后一轮迭代的译码结果痧。 与和积算法相比，最小和算法在进行消息更新时，只涉及比较运算和加法运算，大大降低了运算量，实现了性能与复杂度之间很好的折中。最小和算法由于函数近似降低了译码复杂度，然而却带来了译码性能的降低。鉴于最小和算法性 能损失的缺点，归一化最小和算法利用归一化因子进行修正，提高了译码性能。修正后的校验节点更新公式为： … 三（蜀）＝口。职，ｓｇＩｌ（三（级））（。珊陈肛（甄）Ｉ）ＩＥⅣＩｆ）、，、 ７‘２―２６）其中０＜口≤ｌ为归一化囚子，口应该随不同的信噪比（ＳＮＲ）和迭代次数而改变 以得到最优的结果，但为了简单起见口通常保持为一个常量。将最小和算法中校 验消息更新公式（２．２２）换成公式（２．２６）即为归一化最小和算法。实践表明，归第二章ＬＤＰＣ码的编译码原理１９一化最小和算法的性能与和积算法相当接近，在高信噪比下甚至优于和积算法， 更好地实现了性能与复杂度之间的折中，在实际系统中得到了广泛应用。２．４小结本章简要介绍了ＬＤＰＣ码的概念及其Ｔａｎｎｅｒ图表示形式，推导了基于图模型 的和积算法在概率及对数似然比度量下的消息更新公式，并给出了复杂度低适于 硬件实现的最小和算法。 ＬＤＰＣ码由其校验矩阵的稀疏性而得名，因其基于图模型的简单迭代译码算法及优异纠错性能而受到广泛关注。ＬＤＰＣ码的迭代和积译码算法是基于独立性假设 的最优算法，若独立性条件不满足，会导致性能下降，因此构造ＬＤＰＣ码时需优 化其Ｔａｍｌｅｒ图中的环分布，避免短环尤其是４环的出现。下面两章给出的ＬＤＰＣ 码构造方法均可有效地避免４环。第三章基ｆ循环置换矩阵的Ｑｃ。ＬＤＰＣ码设计２Ｉ第三章基于循环置换矩阵的ＱＣ．ＬＤＰＣ码设计本章介绍了基于循环置换矩阵的准循环（ＱＣ）ＬＤＰＣ码，分析了一类ＱＣ．ＬＤＰＣ 码一阵列ＬＤＰＣ码的结构特征，对基于中国剩余定理（ＣＲＴ）的ＱＣ．ＬＤＰＣ码构造 方法进行了推广和改进，提出了一种新的由短分量码设计长ＱＣ―ＬＤＰＣ码的构造方 法，获得了一类具有更好纠错性能的ＱＣ．ＬＤＰＣ码。３．１引言ＬＤＰＣ码是一种性能逼近ＳｈａＩｌＩｌｏｎ限的好码，通过精心设计的ＬＤＰＣ码在迭代 和积译码下可以获得接近ＳｈａＩｌＩｌｏｎ容量的纠错性能。近几年来已涌现了各种ＬＤＰＣ码的构造方法，根据构造方式的不同，ＬＤＰＣ码大致可以分为两类：一类是随机ＬＤＰＣ码【２ｌ，４８】：根据一定的设计准则和围长、度分布、止集等条件用计算机随机搜 索出所需要的校验矩阵；另一类是结构化ＬＤＰＣ码：利用代数方法或组合方法构造出所需要的ＬＤＰｃ码校验矩阵【２９。３４，５岳７１１。随机ＬＤＰＣ码的设计比较灵活，任意给定码长和码率，很容易构造出随机ＬＤＰＣ码。通过适当地选取度分布序列，随机ＬＤＰＣ码的最小距离和最小止集随码长线性增加【７２’７３１。一般情况下，在瀑布区域（ｗａｔｅ血ｌｌ ｒｅｇｉｏｎ），随机构造的ＬＤＰＣ长码具有很好的纠错性能，比相同码长的结构化ＬＤＰＣ码更逼近Ｓｈ猢ｏｎ理论限。由文献【５６．７ｌ】可以看出，对实用码长（中短码长）的ＬＤＰＣ码来说，好的结构化ＬＤＰＣ码可以获得与随机ＬＤＰＣ码相近的纠错性能。事实上，结构化ＬＤＰＣ码具有 比随机ＬＤＰＣ码更低的错误平层，这在要求误码率很低的数字通信和存储系统中 尤其重要，并且结构化方法比随机方法更容易构造出最小距离较大的ＬＤＰＣ码。另一方面，随机ＬＤＰＣ码需要很大的内存空间来存储其校验矩阵，而结构化ＬＤＰＣ 码的校验矩阵由循环矩阵和零矩阵组成，具有循环或准循环结构，因此可以有效 地降低存储需求，若循环矩阵和零矩阵的维数为三×￡，则只需要ｌ亿的存储空间。 另外，结构化ＬＤＰＣ码可以通过简单的移位寄存器实现线性编码，而随机ＬＤＰＣ码的编码复杂度一般与码长的平方成正比。对中短码长的ＬＤＰＣ码来说，结构化 ＬＤＰＣ码比随机ＬＤＰＣ码具有更大的吸引力。 Ｇａｌｌａｇｅｒ在文献［１８】中给出了一种构造准循环ＬＤＰＣ码的方法，近几年来，很多学者对Ｑｃ．ＬＤＰＣ码进行了研究，并提出了ＱＣ．ＬＤＰＣ码的各种构造方法【难７１】， 他们利用循环置换矩阵来构造校验矩阵，通过恰当地选择循环置换矩阵可以避免相应Ｔａｎｎｅｒ图中的短环。２２西安电子科技大学博士学位论文――Ｉ，ＤＰＣ码的代数构造及译码算法研究 本章的其余内容安排如下，第二节中首先对基于循环置换矩阵的ＱＣ―ＬＤＰＣ码的基本原理做简单介绍。第三节研究了阵列ＬＤＰＣ码的结构特征。第四节提出了一种改进的基于中国剩余定理（ＣＲＴ）的由短分量码设计长ＱＣ―ＬＤＰＣ码的构造方法，获得了一类具有更好纠错性能的ＱＣ―ＬＤＰＣ码，并对该类码字的结构进行了分析。 然后，仿真了实际构造出的几个码。仿真结果表明，在迭代和积译码算法下，与原ＣＩ汀方法相比，改进方法构造的ＱＣ―ＬＤＰＣ码获得了Ｏ．５ｄＢ的编码增益。３．２基于循环置换矩阵的ＱＣ―ＬＤＰＣ码基于循环置换矩阵的ＱＣ．ＬＤＰＣ码的校验矩阵日由循环置换矩阵和零矩阵组 成，首先给出循环置换矩阵的定义。定义３．１：具有以下特征的方阵尸称为循环置换矩阵：１）方阵Ｐ的每行每列有且仅有一个元素为ｌ，其余元素均为Ｏ；２）方阵Ｐ的每一行是其上一行向右循环移位一位，第一行是最下面一行向右循环移位一位。 由定义可知，每个循环置换矩阵Ｐ均可由相同维数的单位阵每行向右（左）循 环移位相同的位数ｆ得到，记为Ｐ＝，（ｆ）。因此，当矩阵维数刀已知时，每个循环 置换矩阵可由单位矩阵每行的循环移位次数ｆ（Ｏ≤ｆ≤，ｌ一１）唯一确定。同时，容易看出，循环置换矩阵Ｐ的每一列是其前一列向下循环移位一位，第一列是最右面 一列向下循环移位一位。 例３．１：式（３．１）给出的矩阵是一个５×５的循环置换矩阵。０ ０ 尸＝ ０ ｌ Ｏ Ｏ Ｏ ０ ０ １ ｌ ０ Ｏ ０ Ｏ ０ ｌ Ｏ ０ ０ Ｏ ０ ｌ Ｏ ０（３．１）该矩阵尸可由５×５的单位阵厶ｘ５每行向右循环移位２位得到，记为Ｐ＝，（２），该矩阵可由其维数刀＝５和循环移位次数待２唯一确定。定义３．２：基于厅×力循环置换矩阵的ＱＣ．ＬＤＰＣ码为循环置换矩阵和零矩阵组成 的校验矩阵Ｈ的零空间。日可写成式（３―２）的形式。 ，（口１１）日＝，（口１２） ，（口２２）ｒ』，ｏ』（口２１）Ｄ（３．２），（口加 ，（ｑｚ）似＠；∞ 钆锄；％ｎ其中口｛『∈｛Ｏ，ｌ，２，…，力一１，∞），，（％）（１≤ｆ≤ｙ，１≤＿，≤尸）表示～个刀×刀的循环置换矩第三章基于循环置换矩阵的ＱＣ―ＬＤＰＣ码设计阵，可由刀×，ｌ的单位阵厶×。每行向右循环移位口。位得到。刀×，ｌ的全零矩阵用，＠）来表示。易知，，（Ｏ）就是单位阵厶。。。记式（３．２）给出的日维数为膨×Ⅳ，其中肘＝刀厂，Ⅳ＝刀ｐ，矩阵日的零空间为一个ＱＣ．ＬＤＰＣ码，码长为Ⅳ＝刀ｐ。每个循环置换矩阵的每行每列有且仅有一个元素为ｌ，因此若日不包含全零矩阵，（∞），则日的列重和行重分别为ｙ和ｐ，日的零空间为一个（厂，户）一规则ＱＣ―ＬＤＰＣ码。如无特殊说 明，下面仅考虑不包含全零矩阵的日给出的ＱＣ．ＬＤＰＣ码，即（厂，ｐ）一规则ＱＣ―ＬＤＰＣ码。此类ＱＣ．ＬＤＰＣ码的校验矩阵日中每个循环置换矩阵均可由其维数ｎ和循环移位次数口。唯一确定，因此日所需要的存储空间非常小。定义３３：形如式（３．２）（即由循环置换矩阵和零矩阵组成）的矩阵日的母矩 阵Ｍ（Ｈ）定义为ＧＦ（２）上的ｙ×ｐ矩阵，将日中每个循环置换矩阵用１代替，零矩阵用０代替得到的矩阵即为Ｍ（日）。 由母矩阵的定义可知，若矩阵日不包含全零矩阵，（ｏＤ），则日的母矩阵Ｍ（日） 为一个全１矩阵，即矩阵中的元素均为ｌ。’定义３．４：形如式（３．２）（即由循环置换矩阵和零矩阵组成）的矩阵日的移位 矩阵Ｓ（日）定义为由日中每个循环置换矩阵的移位次数组成的ｙ×ｐ矩阵。式（３．２）矩阵Ｈ的移位矩阵为：ｑＩ ｑ２４２２…口ｌ口 …口２口?． ●Ｓ（日）＝口２ｌ：●（３?３）哆Ｉ口，２…％由定义３．４可知，当循环置换矩阵，（口，，）的维数靠已知时，矩阵Ｈ可由其移位矩阵Ｓ（日）唯一确定。将Ｓ（日）中的每一元素％用甩×甩的循环置换矩阵，（口｛『）代替，即可得到日，该操作称为矩阵扩展。记校验矩阵日＝（％）肘。Ⅳ，日中长为２尼的环由满足如下条件的２七个Ｊ｝ｌ｛『＝１的位 置构成：１）相邻的两个位置在同一行或者同一列；２）除初始位置和结束位置相 同外，其余位置均互不相同。容易看出，环中两个相邻位置必定处在两个不同的 循环置换矩阵中，并且这两个不同的循环置换矩阵要么在同一块行（ｂｌｏｃｋｒｏｗ）要么在同一块列（ｂｌｏｃｋ ｃｏｌｕｎｍ）。因此，日中长为２七的环可以由循环置换矩阵组 成的序列表示，即 （，（气＾），Ｊ（吒止），，（气＾），．．．，，（气＾），，（气＾））其中‘≠ｆ，小Ｚ≠丘ｌ，ｌ≤，≤七一ｌ，ｔ≠‘，五≠＾，同样，Ⅳ中长为２尼的环可以简单地由Ｓ（日）中的如下序列表示： （口ｌ，口２，口３，…，口２Ｉ）＝（口＾＾，口＾止，口如止，…，口ｔ＾，口‘＾）（３－４）西安电子科技大学博士学位论文――Ｉ，ＤＰＣ码的代数构造及译码算法研究其中ｑ∈Ｓ（日），ｌ≤ｆ≤２Ｊ｜｝，ｑ和ｑ＋ｌ在同一行或者同一列，口ｊ和ｑ＋２在不同行且不同列（注意，这里ｑ和口，＋４可以为Ｓ（日）中的同一元素，即序列（ｑ，口：，口，，．．．，口：。）中的元素允许重复出现）。表示日中长为２Ｊ｜｝环的序列（口。，口２，吩，．．．，％）满足如下定理。定理３．１【３３】：对于移位矩阵Ｓ（日）中的序列（口。，口２，吩，．．．，口：Ｉ），其中ｑ和ｑ＋．在同一行或者同一列，口ｆ和口ｍ在不同行且不同列，若，．是使（口ｌ，哆，口３，．．．，呸。）满足如 下等式的最小正整数：２七厂．５１（一ｌｙ口；三ｏｍｏｄ刀 ●●＿’（３．５）ｆ－ｌ则序列（ｑ，心，口３，．．．，口２Ｉ）使日产生长为２扫的环。 由定理３．１易知，．Ｉ刀，即，是刀的因子，事实上，当（３．５）式成立时，序列（口。，口：，心，．．．，口：。）将使日中产生Ⅳ，个长为２ｂ的环。相对于日来说，ｓ（日）是一个很小的矩阵，利用定理３．１对Ｓ（Ｈ）中的元素进行测试，很容易统计出Ｈ中的短环数目。同时，通过选取适当元素来构造Ｓ（Ⅳ），可避免甚至消除短环的出现，即可通过构造很小的矩阵Ｓ（日）来获得具有良好环性能的大矩阵何，在很大程度上减小了构造 ＱＣ．ＬＤＰＣ码的复杂度。３．３阵列ＬＤＰＣ码及其结构特征Ｆａｎ在文献［６３】中提出了一种阵列（锄．ａｙ）ＬＤＰＣ码，其校验矩阵由循环置换 矩阵组成，是一类ＱＣ－ＬＤＰＣ码。对于任意奇素数ｐ，可构造出一个由ｐ×ｐ的循环置换矩阵构成的ｐ×ｐ的阵列，如式（３．６）所示。Ⅳ（ｐ，ｐ）＝，（ｏ） ，（ｏ） ，（ｏ）ｉ吣Ｄ芍 “““；ｐ一． 、ｌ，，（ｏ） ，（２） ，（４）…… …‘．，（ｏ） ，（ｐ一１） ，（２（ｐ―１））！（３－６）』（ｏ）Ｈ（ｐ，ｐ）的移位矩阵为：，（２（ｐ一１）） …，（（ｐ一１）（ｐ―１））０ Ｏ０ １ ２Ｏ ２ ４… … …Ｏｐ―ｌＳ（Ｈ（ｐ，ｐ））＝０２（ｐ一１）（３―７）０ｐ一１２（ｐ―１）…（ｐ―１）（ｐ一１）定理３．２：对于任意奇素数ｐ，（３．６）式所示矩阵Ｈ（ｐ，ｐ）不包含４环。证明：由定理３．１可知，若日（ｐ，ｐ）中存在４环，必是由满足等式第三章基于循环置换矩阵的ＱＣ．ＬＤＰＣ码设计口２一口ｌ＋口４一口３兰０Ｉｎｏｄｐ的移位序列（口ｌ，吒，口３，口４）构成，其中口ｌ和口２在同一行，ｑ和 毛在同一行，口：和口，在同一列，ｑ和口４在同一列。假设日（ｐ，ｐ）的移位矩阵Ｓ（日（ｐ，ｐ））中的第‘，ｆ２行五，五列相交的４个元素产生日（ｐ，ｐ）中的４环，则气办一气＾＋％＾一气办兰０珈１０ｄｐ 因为％三Ｏ一１）（／一１）ｍｏｄｐ，１≤ｆ，／≤ｐ，所以 （‘一１）（五一１）一（‘一１）（石一１）＋（ｆ２―１）（＾一１）一（之一１）（五一１）三Ｏｍｏｄｐ 整理后得 （之一‘）（五一石）兰Ｏｍｏｄｐ 因为之≠‘，左≠五，１≤‘，之，五，五≤ｐ并且ｐ为奇素数，所以上述等式不可能成立，因此，矩阵日（ｐ，ｐ）中不存在４环，即证。 对任意小于等于ｐ的正整数ｙ（厂≤ｐ），可构造出一类阵列ＬＤＰＣ码，记为Ｃ（ｙ，ｐ），其校验矩阵胃（厂，ｐ）是由ｐ×ｐ的循环置换矩阵构成的ｙ×ｐ阵列，如式 （３－８）所示。Ｈ（７，ｐ）＝，（ｏ） ，（ｏ） ，（ｏ），（ｏ） Ｊ（１） ，（２），（ｏ） ，（２） 』（４）● ●… … …● ●，（ｏ） 』（ｐ―１） ，（２（ｐ―１））（３―８），（ｏ） ，（ｙ一１） ，（２（７一１））… ，（（厂一１）（ｐ一１））日（ｙ，ｐ）的母矩阵为ｙ×ｐ的全１矩阵，日（厂，ｐ）的列重为厂，行重为ｐ，因此 日（ｙ，ｐ）的零空间是一个（厂，ｐ）一规则ＱＣ―ＬＤＰＣ码。易知日（ｙ，ｐ）的秩为ｐ厂一厂＋ｌ， 所以ＱＣ―ＬＤＰＣ码Ｃ（厂，ｐ）的维数为ｐ２一ｐｙ＋厂一ｌ。当相对于ｐ来说ｙ较小时， Ｃ（厂，ｐ）具有较高码率。日（ｙ，ｐ）是日（ｐ，ｐ）的子阵列，日（ｐ，ｐ）中不存在４环，所以ｃ（ｙ，ｐ）的Ｔａ皿ｅｒ图中无４环，适于基于图模型的迭代和积译码。对于中短长的高码率码，阵列ＬＤＰＣ码与好的随机ＬＤＰＣ码【７４】具有相同的纠错性能【硎。３．４由短分量码设计长码的ＱＣ～ＬＤＰＣ码构造方法本节给出了一种利用短分量码设计长码的ＱＣ―ＬＤＰＣ码构造方法，该方法是 对文献［６６】中ＣＲＴ方法的推广和改进，简称为ＧＣｌ盯方法。与原ＣＲＴ方法相比， ＧＣＲＴ方法可获得更多具有更好纠错性能的ＱＣ―ＬＤＰＣ码。记ｓ个Ｑｃ―ＬＤＰＣ码为Ｃ（后＝ｌ，２，…，ｓ），其校验矩阵为风，日。是由厶×厶的循环置换矩阵构成的ｍ×ｎ阵列，满足ｇｃｄ（厶，厶）＝ｌ，（１≤后，，≤ｓ，七≠，）且这ｓ个校验矩阵的母矩阵Ｍ（Ｈ。）相同。令Ｌ＝厶厶…ｔ，且风（１≤七≤ｓ）的移位矩阵记为西安电子科技大学博士学位论文――Ｉ ＤＰＣ码的代数构造及译码算法研究ｓ（ｑ）＝（口≯’），（１≤ｆ≤聊，ｌ≤＿，≤咒）。利用这ｓ个Ｑｃ－ＬＤＰｃ码Ｃ（１≤七≤ｓ）作为分量码，我们可构造出一个具有更长码长的ＱＣ．ＬＤＰＣ码Ｃ，其校验矩阵大小为础×儿。下面给出由短分量码设计长码的ＧＣＲＴ构造方法：１．首先根据式（３―９）计算矩阵Ｓ（Ｈ）＝（口｛，），（１≤ｆ≤聊，１≤／≤刀）。ｒｏ％：｛荟够’４耳ｍｏｄ￡，若够ｋ嗡（Ｋ后如）。（３．９）【∞，其他其中乓＝叫厶，４与厶互素，即ｇｃｄ（４，厶）＝１。２．通过矩阵扩展将Ｓ（日）中的元素％用三×三的循环置换矩阵，（口ｆ，）代替，即 可得到日，日的零空间即为码长为比的ＱＣ－ＬＤＰＣ码Ｃ。 易知，用上述ＧＣＩ玎方法构造的ＱＣ．ＬＤＰＣ码Ｃ，其校验矩阵日的母矩阵满足Ｍ（日）＝Ｍ（巩），（１≤尼≤ｓ），下面给出的定理说明码Ｃ对应ＴａＩｌＩｌｅｒ图的围长大于等于每个分量码Ｃ。（１≤七≤Ｊ）对应Ｔａｎｎｅｒ图的围长。定理３．３：假设移位矩阵Ｓ（日）中长为２，的序列（口ｌ，口：，口３，．．．，口：，）∈Ｓ（日），ｑ≠∞，（１≤ｆ≤２，）与ｓ（也）中的移位序列（口：ｎ，口∥，∥’，．．．，口筹’）∈ｓ（珥），口；‘’≠ｏｏ，（１≤ｆ≤２，）对应，其中哆和％。在同一行或者同一列，哆和口ｆ＋２在不同行且不同列，彰。’和口搿在同一行或者同一列，彰”和口盘在不同行且不同列。如果咯，（后＝１，２，…，ｓ）和，．是满足如下等式的最小正整数：吃?∑（一１）‘∥考ｏｍｏｄ厶２，（３－１０）ｒ?∑（一１）。ｑ三ｏｍｏｄ三ｆ；Ｉ（３－１１）则，．＝兀：：。％。证明：因为￡＝厶厶…丘，Ｅ＝叫厶，所以耳兰ｏｍｏｄ厶，（七≠ｆ）。因此，２， ２，，，Ｊ、―，．?∑（一１）‘ｑ暑，．?∑（一１）‘Ｉ∑以～■Ｉｆ＝ｌ ｆ＝ｌ＼ｆ＝ｌ／三，．?∑（一１）‘口；”４乓兰Ｏｍｏｄ厶 由于ｇｃｄ（４，厶）＝ｌ并且ｇｃｄ（厶，Ｅ）＝ｌ，上式可进一步推导为：，．?∑（一１）ｊ∥三ｏｍｏｄ厶因为％，（七＝ｌ，２，…，ｓ）是满足上式的最小正整数，所以％Ｉ厂。由‘Ｉ厶且第三章基于循环置换矩阵的ＱＣ－ＬＤＰＣ码设计ｇｃｄ（厶，厶）＝１，（后≠ｆ）可得ｇｃｄ（气，，；）＝ｌ，（七≠ｆ），因此，ｎｏ卜另一方面，，（３．１２），，２，、Ｊ，，２，ｆ、ｎ，：?Ｉ∑（一１）‘ｑ ｌ＝ｎ，；．Ｉ∑（一１）‘∑∥４乓Ｉｆ＝ｌ＼ｆ＝ｌ／ｆ＝Ｉ＼扛：ｌ七＝ｌ／＝∑Ｉ兀‘４乓∑（一１）‘砖”ＩＪ厂ｊ，，２，、、／／兰∑ｌ兀，；４乓Ｉ％∑（一１）‘砖Ｄ ｌＪ七＝Ｉ＼ｆ＝ｌ，ｆ≠七＼ｆ＝ｌＩ２ｆ厂２，、由于厶ｌ咯?∑（一１）７口∥，并且￡＝厶乓，所以乓Ｉ％?∑（一１）‘∥’Ｉ＿ｏｍｏｄ￡，则有ｌｆ＿Ｉ＼ｆ＝Ｉ／Ⅱ，；?ｌ∑（一１）‘ｑ｜＿ｏｍｏｄ三ｒ５ｌ、、扛ｌ／又因为ｒ是满足上式的最小正整数，所以，，．１ｎ：：。咯由式（３―１２）和式（３－１３）可得，．＝兀：：。咯，即证。（３－１３）由定理３．１可知，满足（３．１０）的移位序列（口ｒ’，口≯’，ａ｝’，．．．，口筹’）∈ｓ（以）使风中存在长为２峨的环，满足（３－１１）的移位序列（口ｌ，口：，口３，．．．，口：，）∈Ｓ（日）使日中存在长为２咖的环。定理３．３说明，Ⅳ中的２咖－环长度大于等于风中的２以－环，当且仅 当每个咯（１≤七≤ｓ）均为ｌ时，日中的２肛一环与巩中的２哌一环长度相等。由此可知，码Ｃ的围长大于等于每个分量码Ｃ（１≤七≤ｓ）的围长。给定厶，共存在缈（厶）个正整数４满足ｇｃｄ（４，厶）＝１，这里伊（工）为欧拉函数。当分量码的校验矩阵给定时，ＧｃＲＴ构造方法可构造出兀：：，妒（厶）个码长为儿的ＱＣ．ＬＤＰＣ码。本节给出的ＧＣＩ玎方法可以构造出很多不包含４环的ＱＣ―ＬＤＰＣ码，下面利用阵列ＬＤＰＣ码作为分量码为例给出详细说明。例３．２：令见，（七＝１，２，…，ｓ）为奇素数，且Ｂ≠ｐ，，（ｆ≠／），ｍ≤以，（七＝１，２，…，ｓ）为正整数。阵列ＬＤＰＣ码Ｃ（朋，九）的校验矩阵日（历，仇）是由仇×仇的循环置换矩 阵构成的所×仇阵列。根据式（３?１４）构造出ｓ个由仇×见的循环置换矩阵构成的ｍ×ｐ阵列吼（七＝１，２，…，ｓ），其中ｐ＝ｎ：：。既西安电子科技大学博士学位论文――ＬＤＰＣ码的代数构造及译码算法研究以＝［日（ｍ，鼽），日（聊，以），…，日（，，ｌ，仇）】，七＝１，２，…，ｓ丌二．埔Ａ（３－１４）以这ｓ个校验矩阵风（七＝１，２，…，Ｊ）作为分量码的校验矩阵，利用ＧＣＩ盯方法可构造出由ｐ×ｐ的循环置换矩阵组成的矩阵阵列日，矩阵日维数为唧×ｐ２。定理３．４：以（３．１４）的ｓ个校验矩阵风（七＝ｌ，２，…，ｓ）作为分量码的校验矩阵，ＧＣＩ玎方法构造出的矩阵日不包含４环。 证明：由第３．３节可知，阵列ＬＤＰＣ码Ｃ（聊，以）不包含４环。皿中第毛，屯列 （毛≠乞）存在４环，当且仅当墨一如兰ｏＩｎｏｄ研。当，Ｉ≠乞时，Ｅ中的４环存在于其 第，＋‘只列与第，＋乞只列中，其中ｏ≤‘，乞≤ｎ‰；，乃一ｌ，１≤，≤仍由于只≠ｐ，，Ｏ≠ｊ『）且ｏ＜Ｉ卜乞Ｉ＜兀乙≠，岛则对于所有的１≤，≤ｓ，，≠ｆ，等式厶一厶三ｏｍｏｄｐ，不可能全部同时成立，因此存在 ／使（，＋‘只）一（，＋如只）＝（‘一乞）Ｂ≠ｏＩｎｏｄｐ，，也就是说存在日，，其第，＋‘见列与第，＋厶所列不存在４环。由定理３．３可知，当且仅当每个吒（１≤七≤Ｊ）均等于１时，即每个日。在相同位置都存在４环时，日中对应的位置才会出现４环。因为式（３．１４） 中的Ｊ个校验矩阵日。（七＝ｌ，２，…，ｓ）不可能在同一位置都存在４环，所以以日。（七＝１，２，…，ｓ）作为分量矩阵构造出的矩阵日不包含４环，即证。下面分析矩阵日中６环的分布情况。例３．２中风（七＝ｌ，２，…，ｓ）的移位矩阵记为ｓ（以）＝（口≯’），（１≤ｆ≤朋，１≤／≤ｐ），日的移位矩阵记为ｓ（日）＝（口，，）， （１≤ｆ≤肌，１≤／≤ｐ）。由口箩’兰Ｏ一１）（／一１）ｍｏｄ见可知，当且仅当下式成立时，（Ｚ一五）（ｆＩ一１）＋（五一五）（之一１）＋（五一五）（ｆ３一１）兰０埘【ｏｄ以Ｓ（峨）中的移位序列（口崭，口发，口发，口器，础，础）使日。中产生６环，就意味着如果下式（３．１５）成立，（Ｚ一五）（ｆｌ一１）＋（以一五）（ｆ２一１）＋（五一Ｚ）（ｆ３一１）兰ｏＩｌ】ｌｏｄＩ Ｉ：：，以（３一１５）则所有的Ｈ。，（１≤七≤ｓ）在同一位置均存在６环，则矩阵日在该位置也存在６环。根据以上分析的结果，找到如下～种有效地减少Ｈ中６环的方法：通过对Ｓ（钒）的 行进行重新排列（行置换）来减少Ｈ中的６环数。通过下面的方法选择每个Ｓ（风）的行置换，从而确定一个行置换的组合使日中包含较少的６环。对每个Ｓ（以）进行行置换之前，可以统计所有使吼中存在６环的移位序列的第三章基于循环置换矩阵的ＱＣ．ＬＤＰＣ码设计２９位置，即满足∑：。（一１）‘∥兰ｏｍｏｄ既（３－１６）的移位序列（口：ｎ，口≯’，∥’，露’，∥１，口≯’）的位置，然后计算使所有凰在同一位置均存 在６环的移位序列的个数，记为Ⅳ，则进行置换前得到的码Ｃ包含肋个６环。然后对每个ｓ（以）进行随机行置换得到ｓ（《），统计所有使珥中存在６环的移位序列的位置，即满足（３－１６）的移位序列（口，，ａ≯’，拶’，群’，《ｎ，露’）的位置，计算使所有日：在同一位置均存在６环的移位序列的个数，记为Ⅳ’。如果Ⅳ’＜Ⅳ，则说 明这个行置换的组合对应的码Ｃ’包含更少的６环，是一个“好’’组合；反之，如果Ⅳ’＞Ⅳ，则说明这个行置换的组合对应的码Ｃ’比不进行置换得到的码Ｃ包含更多的６环，是一个“坏”组合。通过随机选择置换的组合，可以得到很多“好＂组合，然后从中选择一个“最好”的组合，即Ⅳ’最小的组合。仿真结果表明，与不进行置换得到的码Ｃ相比，对Ｓ（见）进行行置换可以构造 出很多具有更好纠错性能的ＱＣ―ＬＤＰＣ码。每个Ｓ（峨）有聊！种行置换，共存在（ｍ！）’个行置换的组合，而存在聊！个行置换的组合将对应同一个码Ｃ，因此通过行置换 的方法可以构造出（肌！）”１个不同的码。当分量码的校验矩阵给定时，例３．２给出的 方法可构造出（ｍ！）”１兀：：。妒（厶）个码长为ｐ２的ＱＣ―ＬＤＰＣ码。 例３．２是以阵列ＬＤＰＣ码作为分量码，这种方法同样适用于其他ＱＣ．ＬＤＰＣ码 作为分量码的情形，不过分析和搜索好的置换组合的复杂度将会因分量码的结构 特征而变化。 矩阵Ｈ的任意两列最多有一个分量“ｌ＂在同一位置出现（因为日不包含４ 环），且日每列有聊个“ｌ”，若从日中选择一些列的集合使集合中的列之和为０， 则集合中列的个数不可能小于ｍ＋１，因此码Ｃ的最小距离至少为脚＋１。日为由 ｐ×ｐ的循环置换矩阵组成的册×ｐ的矩阵阵列，日每列有，，１个部分，每部分仅包 含一个“１”，因此，若从日中选择奇数个列，其之和不可能为Ｏ，所以码Ｃ的最小距离必为偶数。因此，若ｍ为奇数，码Ｃ的最小距离大于等于聊＋ｌ；若垅为偶数，码Ｃ的最小距离至少为肌＋２。３．５仿真结果本节对ＧＣＲＴ方法和文献［６６】给出的ＣＩＨ方法进行了仿真比较。在ＡｗＧＮ信道和ＢＰＳＫ调制方式下，对两种方法构造出的多个ＱＣ．ＬＤＰＣ码用和积算法进行译码，和积算法的最大迭代次数均设为５０次。仿真结果表明，与ＣｌＨ方法构造的码３０西安电子科技大学博士学位论文――ＬＤＰＣ码的代数构造及译码算法研究相比，ＧＣＩ江方法构造的码获得了０．５ｄＢ的编码增益。以阵列ＬＤＰＣ码Ｃ（３，７）和Ｃ（３，１１）为分量码，两种方法均可构造出由７７×７７的 循环置换矩阵组成的３×７７的矩阵阵列，选择阵列最左边的３×７的子阵列作为校验 矩阵，则可得到（５３９，３１０）ＱＣ．ＬＤＰＣ码（其中码长为５３９，信息位为３１０位，码率 为０．５７５），其校验矩阵的行重和列重分别为７和３。选择阵列最左边的３×１２的子 阵列作为校验矩阵，则可得到码率为０．７５２的（９２４，６９５）ＱＣ．ＬＤＰＣ码，其校验矩阵 的行重和列重分别为１２和３。图３．１给出了这两种码在和积算法下的纠错性能。 ＧＣＲＴ方法的构造过程中，所选择的参数为：４＝１，４＝６；选择的行置换组合为：Ｓ（且）不进行置换，Ｓ（皿）的第一行和第二行进行置换。利用文献［７５】中提出的统计环的方法，我们计算了所构造码对应ＴａＩｌｌｌｅｒ图中６环的个数。ＣＩ汀方法构造的（５３９，３ｌＯ）ＱＣ．ＬＤＰＣ码有１３８６个６环，而ＧＣＩ汀方法构造的（５３９，３１０）码仅包含１５４个６环。对于（９２４，６９５）码，ＧＣＲＴ方法构造的码包含的６环比ＣＲＴ方法构造的码 少了３６９６个。图３．１ ＣＲＴ方法和ＧＣＲＴ方法构造的（５３９，３１０）和（９２４，６９５） ＱＣ－ＬＤＰＣ码在和积算法下的纠错性能以阵列ＬＤＰＣ码Ｃ（３，１１）和Ｃ（３，１３）为分量码，两种方法均可构造出由１４３×１４３ 的循环置换矩阵组成的３×１４３的矩阵阵列，选择阵列最左边的３×１１的子阵列作为第三章基于循环置换矩阵的ＱＣ．ＬＤＰＣ码设计３ｌ校验矩阵，其行重和列重分别为ｌｌ和３，则可得到码率为Ｏ．７２９的（１５７３，１１４６） ＱＣ．ＬＤＰＣ码，选择阵列最左边的３×２０的子阵列作为校验矩阵，则可得到码率为 Ｏ．８５的（２８６０，２４３３）ＱＣ―ＬＤＰＣ码，其校验矩阵的行重和列重分别为２０和３。图３．２ 给出了这两种码在和积算法下的纠错性能。ＧＣＩ玎方法的构造过程中，所选择的参数为：４＝１，４＝８；选择的行置换组合为：Ｓ（目）不进行置换，Ｓ（风）的第一行和第二行互换位置。利用文献【７５】中提出的统计环的方法，我们计算了所构造码字 ＴａＩｌｎｅｒ图中６环的个数。ＣＲＴ方法构造的（１５７３，１１４６）ＱＣ．ＬＤＰＣ码有７１５０个６环， 而ＧＣＩ玎方法构造的（１５７３，１１４６）码仅包含８５８个６环。ＣＲＴ方法构造的（２８６０，２４３３） ＱＣ－ＬＤＰＣ码有２５７４０个６环，而ＧＣＲＴ方法构造的（２８６０，２４３３）码包含的６环比 ＣＲＴ方法构造的码少了２０８７８个。图３．２ ＣＲＴ方法和ＧＣＲＴ方法构造的（１５７３，１１４６）和（２８６０，２４３３） ＱＣ－ＬＤＰＣ码在和积算法下的纠错性能从以上两个图中可以看出，与Ｃｌ订方法相比，ＧＣＲＴ方法构造的ＱＣ―ＬＤＰＣ码具有更好的纠错性能，在误比特率（ＢＥＲ）为１０“时，ＧＣＲＴ方法构造的码获得 了Ｏ．５ｄＢ的编码增益。３２西安电子科技大学博士学位论文――Ｉ ＤＰＣ码的代数构造及译码算法研究３．６小结本章介绍了基于循环置换矩阵的ＱＣ―ＬＤＰＣ码，对ＱＣ―ＬＤＰＣ码的ＣＲＴ构造 方法进行了推广和改进，提出了一种由短分量码设计长码的ＧＣＲＴ构造方法。当分量码Ｃ，（后＝１，２，…，ｓ）的校验矩阵风是由厶×厶循环置换矩阵组成的阵列时， ＧｃＩ盯方法可构造出（ｍ！）”１丌：．烈厶）个Ｑｃ―ＬＤＰｃ码（册为所构造校验矩阵的列重），通过对分量码的移位矩阵进行行置换，可以消除大量６环，从而使所构造的 码在基于图模型的迭代和积算法下具有更好纠错性能。在迭代和积译码算法下，与Ｃｌ玎方法相比，ＧＣＩ玎方法构造的码获得了０．５ｄＢ的编码增益。基于循环置换矩阵的ＱＣ―ＬＤＰＣ码具有很好的代数结构特性，可以根据其代 数结构进一步研究和分析ＧＣＲＴ方法所构造码的性能参数，如最小距离等。第四章基于欧氏几何的ＱＣ―ＬＤＰＣ码设计３３第四章基于欧氏几何的ＱＣ．ＬＤＰＣ码设计本章基于欧氏几何的结构特性提出了两类规则ＬＤＰＣ码的构造方法，这两类 码均为准循环（Ｑｃ）码，可以通过线性移位寄存器实现线性时间编码。在迭代译 码算法下，第一类Ｑｃ―ＬＤＰＣ码与已有的欧氏几何码具有几乎相同的纠错性能；而 与已有的欧氏几何码相比，第二类ＱＣ．ＬＤＰＣ码具有更低的错误平层（ｅ玎。卜ｎｏｏｒ）性能．４．１引言根据构造方法的不同，ＬＤＰＣ码主要可以分为两大类：随机ＬＤＰＣ码和结构化 ＬＤＰＣ码。随机方法构造的ＬＤＰＣ码的校验矩阵不具有结构性，一般情况下编码复 杂度与码长的平方成正比，并且其高维校验矩阵的硬件存储也较为复杂，这已经 成为ＬＤＰＣ码实用化的一个主要瓶颈。为了实用的目的，需要设计性能优良、校验 矩阵具有一定结构特性的ＬＤＰＣ码。作为一种结构化ＬＤＰＣ码，有限几何ＬＤＰＣ码因 其优异的编译码特性已经得到很多学者的研究和关注。 有限几何码具有很好的最小距离特性，并且可以通过简单的大数逻辑译码算 法进行译码，早在二十世纪六十年代，就已经得到很多学者的研究和青睐ｒ陲８３】。 然而之后的三十年里，有限几何码却被人们所忽略。直到最近几年，有限几何ＬＤＰＣ 码【３０】的出现才使其得到研究者们的重新关注。Ｙ Ｋｂｕ等学者利用有限几何的点与线构造了有限几何ＬＤＰＣ码【３们，该类码具有良好的最小距离特性并且相应的Ｔａｎｎｅｒ图中不包含长度为４的环，可以通过迭代和积译码算法获得逼近Ｓｈａ蚰ｏｎ限的性能。除了和积译码算法之外，有限几何ＬＤＰＣ码可以通过不同复杂度的多种译码算法进行译码：ＭＬＧ（ｍａｊｏｒｉｔｙ－ｌｏｇｉｃ）译码算法，ＢＦ（ｂｉｔ．ｎｉｐｐｉｎｇ）译码算法，加权ＭＬＧ译码算法，加权ＢＦ译码算法，ＡＰＰ（ａｐｏｓｔｅｒｉｏｒｉｐｒｏｂａｂｉｌ时）译码算法等，可以实现译码复杂度，译码速度以及纠错性能之间很好的折衷。同时，Ｙ Ｋｏｕ等构造的有限几何ＬＤＰＣ码均为循环码或者准循环码，因此可以通过线性移位寄存器实现线性时间编码。 有限几何ＬＤＰＣ码的出现验证了可以通过代数方法构造逼近Ｓｈａ胁ｏｎ限的 ＬＤＰＣ码，代数方法构造的ＬＤＰＣ码具有其固有的结构特性，有利于大规模集成电 路实现编译码器，并且有利于降低硬件存储复杂度，从而引起研究者们致力于寻找各种代数方法来构造具有优异性能的ＬＤＰＣ码。此后，便掀起了对有限几何ＬＤＰＣ 码的构造‘６８州】，高效译码方法【弭８７１及结构性能分析等方面的研究热潮。西安电子科技大学博士学位论文――Ｉ ＤＰＣ码的代数构造及译码算法研究本章的其余内容安排如下，第二节首先对欧氏几何（Ｅｕｃｌｉｄｅ觚ｇｅｏｍｅｎｙ）的 概念及性质做简单介绍。第三节采用欧氏几何的结构特性给出了一种基于循环置 换矩阵的ＱＣ．ＬＤＰＣ码构造方法，与文献［７ｌ】中的码相比，该方法构造的码具有更 少的短环。仿真结果表明新构造的码具有与文献［７ｌ】中的码相当的性能。第四节采用欧氏几何的结构特性给出了另一类ＱＣ．ＬＤＰＣ码构造方法，并对该类码字的结构进行了分析，发现了一个最低重码字存在的充分条件，虽然该条件只是一个充分 条件而非充要条件，但仿真结果表明，通过一定的参数约束减少了满足该充分条件的最低重码字个数后，新构造的ＱＣ．ＬＤＰＣ码具有比文献［３０】中的码更低的错误 平层性能。４．２欧氏几何令ｐ为素数，ｍ≥２和ｓ≥１为两个正整数。考虑域ＧＦ（ｐ’）上的ｍ维向量 （口。，口ｌ，．一，％一。），其中ｑ∈ＧＦ（ｐ５），因为向量中的每个元素基于ＧＦ（ｐ’）有∥个取值， 所以总共存在（ｐ‘}