（信号与信息处理专业论文）ldpc码编码算法研究与改进.pdf

中文摘要 摘要：纠错码是一种信道编码，它的目的是保证信息在信道中传输的可靠性， 并能够自动检测和纠正误码。1 9 4 8 年香农发表了通信的数学理论，其中给出了 设计纠错码的几个基本原则，为纠错码技术的发展指明了方向。从那以后，信道 编码技术就蓬勃发展起来。时至今日，信道编码仍然是通信领域一项重要的技术 和研究热点之一。1 9 6 2 年麻省理工学院的r o b e r tq g a l l a g e r 在其博士论文中提出 了一种新型的纠错码，称为l d p c 码( l o wd e n s i t yp a d 哆c h e c kc o d e ) 配合b p ( b a c kp r o p a g a t i o n ) 算法译码技术，在一定的条件下，这种纠错码的纠错能力可 以超过任何一种已知的纠错码。l d p c 码的最显著特点是其校验矩阵是大稀疏矩 阵，从而直接导致了其庞大的运算量。所以，由于当时计算机的发展水平并不高， 也由于人类科学眼光的历史局限性，l d p c 码在相当长的一段时间内没有得到合理 的重视。2 0 世纪9 0 年代初，随着计算机技术的不断改进和纠错码技术的不断发展， l d p c 码从新走进了人们的视野。l d p c 码作为一种纠错码的优越性逐渐为人们所 认识，对它大规模的深入研究才真正开始并一直延续到今天。可以说，l d p c 码是 从它被再发现的那一天才开始真正登上历史舞台。 本文有5 章。第1 章介绍了纠错码的发展历史及基本原理，并以纠错码的基 本原理为基础介绍了l d p c 码的结构，特点，构造方法，编码算法，译码算法等 内容，还简单介绍了关于l d p c 码的研究发展方向。第2 章主要关注l d p c 码的 编码算法，在介绍各种l d p c 码编码算法的同时，重点介绍i e e e 8 0 2 1 6 e 标准和 d v b s 2 标准中的l d p c 码的编码算法，并分析了各种编码算法的运算复杂度。另 外，本章解决了i e e e 8 0 2 1 6 e 标准的l d p c 码的校验矩阵右半边子矩阵的可逆性推 导，还通过严格的论证形式，推导出了d v b s 2 标准的l d p c 码的参数的取值规 则。第3 章的工作集中在对d v b s 2 标准的l d p c 码的误码性能的改进上，包括 推导出了校验矩阵和生成矩阵的求法，介绍影响码性能的因素及判断方法，然后 是3 种改进方案及其运算量分析，最后提出基于d v b s 2 标准的l d p c 缩短码， 并将所提到的各种改进方法用到此处。第4 章推导出d v b s 2 标准的l d p c 码的 快速迭代算法，并给出实现方法。第5 章是结论。 关键词：l d p c 码；误码性能；迭代编码算法 分类号：t n 9 1 9 3 + 3 a b s t r a c t a b s t r a c t ：e r r o rc o r r e c t i n gc o d e s ，av a r i e t yo fc h a n n e le n c o d i n gt e c h n i q u e ， a i m e dt og u a r a n t e et h er e l i a b i l i t yo ft h em e s s a g et r a n s m i t t e di nt h ec h a n n e l ，a r ea b l et o d e t e c ta n dc o r r e c tt h ee r r o n e o u sc o d e sa u t o m a t i c a l l y i n19 4 8 ，c l a u d ee s h a n n o n p u b l i s h e dh i sf a m o u st r e a t i s eam a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n t h i s t r e a t i s eg a v eo u ts e v e r a li m p o r t a n tp r i n c i p l e sf o rd e s i g n i n ge r r o rc o r r e c t i n gc o d e s ， s h o w i n gt h er i g h tr o a df o r t h ea d v a n c e m e n to f t h ee r r o rc o r r e c t i n gc o d et e c h n i q u e s i n c et h e n ，t h ee r r o rc o r r e c t i n gc o d et e c h n i q u eh a se n j o y e dag o l d e na g eo f d e v e l o p m e n t t o d a y , t h ec h a n n e le n c o d i n gi s s t i l la ni m p o r t a n tt e c h n i q u ea n da h o t s p o tf o rt e c h n i e a lr e s e a r c h i n19 6 2 ，r o b e r tg g a l l a g e rp r o p o s e dan e w e r r o r c o r r e c t i n gc o d ei nh i sd o c t o r a t ed i s s e r t a t i o n ，t e r m e dl o wd e n s i t yp a r i t yc h e c kc o d e ( l d p c ) u n d e rs o m ec o n d i t i o n ，w i t ht h ea i do fb a c kp r o p a g a t i o n ( b p ) a l g o r i t h m ，t h i s n e we r r o rc o r r e c t i n gc o d ep o s s e s s e sa ne r r o rc o r r e c t i n gp o w e rs u r p a s s i n gt h a to fa n y o t h e rk n o w ne r r o rc o r r e c t i n gc o d e t h em o s tr e m a r k a b l ef e a t u r eo ft h el d p cc o d ei si t s p a r i t y - c h e c km a t r i x ，ag i g a n t i c s i z e ds p a r s em a t r i x ，w h i c h d e t e r m i n e st h el a r g e c o m p u t a t i o ni nt h ep r o c e s so fe n c o d i n g a sar e s u l t ，o na c c o u n to f t h ec o m p a r a t i v e l y l o wd e v e l o p m e n ts t a n d a r do fc o m p u t e rs c i e n c ea n dt h eh i s t o r i c a ll i m i t a t i o no fh u m a n e y e s i g h ti nt e c h n o l o g y , t h eg r e a ti n v e n t i o n ，i nal o n gp e r i o do ft i m e ，w a sn o tp a i dd u e r e c o g n i t i o nb yt e c h n o l o g i c a lr e s e a r c h e r s i n19 9 0 s ，w i t ht h ec o n t i n u o u sd e v e l o p m e n ti n c o m p u t e rs c i e n c ea n da d v a n c e m e n t i ne r r o rc o r r e c t i n gt e c h n o l o g y , t h el d p cc o d ea g a i n c a r r i ei ns i g h t t h el d p cc o d e ，a sam a r v e l o u se r r o rc o r r e c t i n gc o d e ，b e g a n t or e v e a li t s a d v a n t a g e sg r a d u a l l yt or e s e a r c h e r s t h ev a s t - s c a l er e s e a r c ho nt h ec o d eb e g a na tt h a t t i m ea n dh a sl a s t e du n t i lp r e s e n t i ts t a n d st or e a s o nt h a ti tw a so nt h ed a yw h e nt h e l d p cc o d ew a sr e d i s c o v e dt h a ti ta s c e n d e do nt h es t a g eo fh i s t o r y t h i sd i s s e r t a t i o ni n c o r p o r a t e s 6 c h a p t e r s t h e1 吼c h a p t e r i n t r o d u c e st h e d e v e l o p m e n th i s t o r yo ft h e e r r o rc o r r e c t i n gc o d ea n di t sf u n d a m e n t a lp r i n c i p l e sa n d i n t r o d u c e st h es t r u c t u r e ，f e a t u r e s ，c o n s t r u c t i o nm e t h o d s ，e n c o d i n ga l g o r i t h ma n d d e c o d i n ga l g o r i t h mo ft h el d p cc o d eo nt h eb a s i so f t h ea b o v e - m e n t i o n e df u n d a m e n t a l p r i n c i p l e s t h ed i r e c t i o no f t h er e s e a r c hd e v e l o p m e n ti sa l s ob r i e f l yi n t r o d u c e d t h e2 n d c h a p t e rc e n t e r sa r o u n dt h ee n c o d i n gm e t h o d so fl d p c c o d e i nt h es a m et i m ew h e na v a r i e t yo fl d p ce n c o d i n gm e t h o d s a r ei n t r o d u c e d ，m o r ew o r kf o c u s e so nt h e i n t r o d u c t i o no ft h el d p ce n c o d i n gm e t h o do ft h ei e e e 8 0 2 16 es t a n d a r da n dt h e d v b s 2s t a n d a r d t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h ee n c o d i n gm e t h o d si sa n a l y z e d t h i sp a r to fd i s s e r t a t i o ng o e sf u r t h e rt oh a v ed a n o n s t r a t e dt h en o n - s i n g u l a r i t yo ft h e r i g h tp a r ts u b m a t r i xo ft h ep a r i t y - c h e c km a t r i xo ft h ed v b - s 2s t a n d a r da n dh a v e d e t e r m i n e dt h er a n g ew i t h i nw h i c ht h ef a c t o ro ft h ed v b - s 2s t a n d a r dl d p cv a r i e s t h r o u g hs t r i c tt h e o r e t i c a ld e d u c t i o n t h e3 mc h a p t e rc o n c e n t r a t e so ni m p r o v i n gt h eb e r p e r f o r m a n c eo f t h el d p cc o d eo ft h ed v b s 2s t a n d a r d ，i n c o r p o r a t i n gt h ed e d u c t i o no f t h ea l g o r i t h mt oc a l c u l a t et h ep a r i t y - c h e c km a t r i xa n dt h eg e n e r a t i n gm a t r i xf r o mt h e f a c t o r so ft h ed v b - s 2s t a n d a r d , i n t r o d u c t i o no ft h ef a c t o r si n f l u e n c i n gt h eb e r p e r f o r m a n c ea n dt h em e t h o d st oj u d g et h e m i nt h el a s ts t a g eo ft h i sp a r t , 3i m p r o v i n g m e t h o d sa r ep r o p o s e d ，w i t ht h ec o m p u t a t i o n a lc o m p l e x i t ya n a l y s i s t h e4 md e d u c e st h e f a s ti t e r a t i v ee n c o d i n ga l g o r i t h mo ft h ed v b - s 2s t a n d a r dl d p cc o d ea n dg i v e so u ti t s i m p l e m e n t a lm e t h o d t h e5 mc h a p t e rp u tf o r w a r da l ll d p cs h o r t e n e dc o d eb a s e do i lt h e l d p cc o d eo ft h ed v b s 2s t a n d a r da n dt r a n s p l a n tt h ei m p r o v i n gm e t h o d sf r o mt h e3 i d c h a p t e ri n t ot h ei m p r o v e m e n to ft h eb e rp e r f o r m a n c eo ft h el d p cs h o r t e n e dc o d e t h e6 t hc h a p t e ri sc o n c l u s i o no ft h ed i s s e r t a t i o n k e y w o r d s ：l d p cc o d e ；b e rp e r f o r m a n c e ；i t e r a t i v ee n c o d i n gm e t h o d c l a s s n o ：t n 9 1 9 3 + 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：- 多名 签字日期： ) 。，年6 月f3 日 导师签名： 勿 签字眺z 口。声衫月侮 致谢 历时5 个月，终于完成了我的硕士学位论文。倘若没有下面的人们的帮助， 我的工作是难以顺利完成的。 首先要感谢的是我的导师，肖扬教授。在整个研究生阶段里，他在学术上给 了我大量的指导，我跟他之间的学术谈论常常持续一个多小时，他所表现出来的 大量的创意总是使我感到斗志昂扬而情绪激荡。更重要的是，他勤劳，严谨的学 术精神使我深为感动并获益良多。每当我学术上遇到困难，他总能让自己被我轻 易找到。再次感谢肖教授。 非常感谢尹华镜，他常常将自己的论文工作与我交流，不吝于与我分享资料， 他优秀的工作给了我很大的启发。感谢黄晗，教我用v c h 6 0 感谢毛鹏轩，帮我 照看了很久我的风尾竹。感谢马红霞，总是记得第一时间告诉大家关于工作招聘 和学校政策事务方面的新消息。感谢潘光玮和颜罗，他们风趣幽默的言谈让我紧 张工作之余感觉到每一天都焕然一新。感谢杜永娜，尹珊在找工作方面的经验交 流。感谢倪煜，杜会军，李瑞的关照。感谢苏庆，文心灵两位学长，他们都在学 术上给我支持，尤其是文学长，在离校奔赴工作岗位的前几天还忙里抽空与我讨 论小波变换。感谢我的父母，每每通电话，总是问及论文之事，给予关心和慰问。 感谢计算机学院研究生科的郭神华，王延超和平洋三位老师，他们所组成的工作 团队活力十足，魅力四射，给我许多关照。最后要感谢的是孔令军学长，邹涵， 卫婧和诸位学弟学妹们，是他们一起创造了良好的实验室学术氛围。 论文虽由我一人来写，却远非我一人之力而成。除了上述己感谢的各位，还 有许多人给予了我支持与关照，虽难以一一列举，但在此一并向你们致以最真诚 的感激与敬意。 序 本文是我的学位论文。文中集中讨论了低密度校验码( l d p c 码) 的各种问题， 主要精力还是放在l d p c 好码探寻方面。本文在如何改进码性能，如何实现快速 编码等问题上做了大量的实验，并且提出了一些新见解。这些结论在l d p c 好码 设计方面能起到一定的理论和实践指引作用。 文中既有前人科学研究的成果总结，也有我辛苦钻研的创意发挥，虽远算不 上是什么惊世骇俗之作，但对于我这样一个科学研究道路上的新手和后行者，可 以藉此文为机会，瞻仰前辈科学家们的伟岸形象，了解他们在浩浩汤汤的科研历 史长河中提出的诸多天才思想与高深理论，又可仅凭自己所做的一点工作而与前 辈忝列同文，实在算是莫大的荣幸。 现代社会，国际环境瞬息万变，风云变迁本应以平常记之。然论文写作之时， 适逢国际金融危机变生肘腋，颇感惊慌而几近失措。人生变幻无常，深有“壮志 未酬再未酬”之悲。然古语有云：老当益壮，宁移白首之心；穷而亦坚，不堕青云 之志。人生虽多变，只要能有“宁移白首”的情怀和“不堕青云 的志气，总能 够在跌倒后立刻起身，卷土再来，人生目标总是目之能及，不会离你远去。先哲 有训：不以物喜，不以己悲。要以平静的心态，清醒的头脑，来面对人生的成败 得失，不被盲目的冲动所左右。成而不骄，败而不馁，得而不止，失而不退，才 能够忘记伤痛和悲哀，始终脚踏实地向目标前进。人生路途险阻颇多，而所学甚 微，不免忧思难掩，特此识之以自省。 第1 章绪论 伴随着通信技术的飞速发展以及各种传输方式对可靠性要求的不断提高，差 错控制编码技术作为抗干扰技术的一种重要手段，在数字通信领域和数字传输系 统中显示出越来越重要的作用。如今，各种通信手段日新月异，手机，数字电视， 因特网，c d 和d v d 播放机设备等等，在人们的日常生活中无处不在。在所有的 这些设备中，信息都是由数字信号来传递的。这些数字信号或者是从一处被传送 到另一处，或者是在需要时在数据存储设备之间被存取。由于通信信道固有的噪 声和衰落特性，信号在经过信道传输到达通信接受端的过程中不可避免地会受到 干扰而导致信号失真。所以，所有这些应用到数字信号的系统，只有在数据传输 过程中所发生的错误达到足够低的时候，才有可能正常运作，而这个目标可以通 过信道编码技术有效地达到。信道编码，在信息码序列中引入冗余，使得由于信 道所导致的比特错误能够被修正，因此确保了传输的可靠性。信道编码技术通常 需要采用差错控制编码来检测和纠正有信道失真引起的信息传输错误。从这一点 意义上说，信道编码常常被称作纠错码。 最早的纠错码主要是用于深空通信和卫星通信，随着数字蜂窝电话、数字电 视以及高分辨率数字存储设备的出现，编码技术的应用已经不仅仅局限于科研和 军事领域，而是逐渐在各种现实的信息交流和存储的设备中得到越来越成功的应 用。其中一种纠错码技术就是l d p c 码( t h el o w d e n s i t yp a r i t y - c h e c kc o d e ) ，它可 以保证数据传输或数据存取的可靠性。在l d p c 码所设计的各种技术中，编码技 术是最为关键的几项技术之一。分析l d p c 码的编码技术和设计l d p c 码的编码 方案是本文的核心内容。 本章共有3 部分，其中1 1 介绍纠错码的发展，1 2 关注的是纠错码理论的基 本术语和一些基本原理，为后续深入探讨各个问题做铺垫，1 3 将会把纠错码的介 绍具体应用到l d p c 码上，为论文的后续部分做基础。 1 1 纠错码的发展 1 9 4 8 年，c e s h a n n o n 发表的著名的通信的数学理论一文，为信道编码 技术的发展指明了方向。s h a n n o n 在著名的有噪信道编码定理中，给出了在数字通 信系统中实现可靠通信的方法以及在特定信道上实现可靠通信的信息传输速率上 限。s h a n n o n 在他的证明中引用了三个基本条件： ( 1 ) 采用随机的编译码方法； ( 2 ) 构造码长的渐近好码或者s h a n n o n 码； ( 3 ) 译码采用最佳的最大似然译码算法。 5 0 多年来，构造好码的思想基本上基本上是按照s h a n n o n 所引用的基本条件 的后两条为主线进行研究的。经过5 0 年的不懈努力，各种差错控制编码方案不断 涌现。 在2 0 世纪4 0 年代，r h a m m i n g 和m g o l a y 提出了第一个实用的差错控制编 码方案，极大地推动了编码理论这个应用数学分支的发展。h a m m i n g 码不仅能够 检测到是否有错误发生，同时还可以找到发生单个比特错误的比特位置，该码最 多可以纠正7 个比特中所发生的单个比特错误。更重要的是，这个编码方法塑造 了分组码的基本思想。 虽然汉明码在构造码的思想上是比较先进的，但是汉明码存在许多难以接受 的缺点，其中最突出的两个是：编码效率低和在一个码组中只能纠正单个比特错 误。后来m g o l a y 发明了可以纠正3 个错误的二元g o l a y 码和可以纠正2 个错误 的三元g o l a y 码。 1 9 5 4 年r e e d 在m u l l e r 提出的分组码的基础上提出了一种新的分组码，称为 r e e d m u l l e r 码( 简称为r m 码) 。r m 码是一类参数选择范围很广的分组码，在码字 长度和纠错能力方面具有更强的适应性，是在汉明码和g o l a y 码的基础上的一大 进步。1 9 6 9 年到1 9 7 7 年之间，r m 码广泛用于火星探测技术。即便在今天，r m 码也具有很高的研究价值，值得一提的是，它的快速译码算法非常适合光纤通信 系统。 在r m 码之后，人们提出了循环码的概念。循环码不同于分组码，但是在更 广泛的角度来看，它其实也是一类分组码，但是它的码字具有循环位移特性，即 码字比特经过循环移位后仍然是码字集合中的码字。这种循坏结构极大地拓展了 码字的设计范围，也极大地简化了编译码的结构。 几乎同时，h o c q u e n g h e m 在19 5 9 年，b o s e 和r a y - c h a u d h u r i 研究组在19 6 0 年提出了b c h ( b o s ec h a u d h u r ih o c q u e n g h a m ) 码，这种码是循环码的一个非常重 要的子集。若b c h 码的码长为n = q ”一l ，其中m 是一个整数，则二元b c h 码的 纠错能力限度为f ( 2 ”一1 ) 2 1 9 6 0 年，r e e d 和s o l o m o n 将b c h 码扩展到了非二 元的情况，得到了r s ( r e e d s o l o m o n ) 码。r s 码的最大优点是其非二元特性可以纠 正突发错误。自从b e r l e k a m p 丌发出r s 码的高效泽码算法后，r s 码得到广泛应 用，在c d 播放器，d v d 播放器以及d c p d ( c e l l u l a rd i g i t a lp a c k e td a r a ) 标准中 都得到很好的应用。 1 9 5 5 年，e l i a s 等人提出了卷积码。卷积码与分组码的不同在于，分组码在编 码之前先将信息序列按照一定的数据块长度进行分组，然后对每一组信息进行独 立编码，而卷积码各码字的校验码之间并不是相互独立的。 2 1 9 6 6 年，f o m e y 提出由两个较短码构造长码的串行级联思想。其基本思想是， 将编制长码的过程分级完成，从而通过用短码级联构造长码的方法来提高纠错码 的纠错能力。级联码的目标是构造具有较大等效分组长度的纠错码，并且允许将 最大似然译码分为几个较简单的译码步骤，这样便得到了一个次最优但实际可行 的译码策略。级联码纠错能力强，译码也不复杂，展现了构造s h a n n o n 码的美好 前景。 2 0 世纪7 0 年代中期，在构造s h a n n o n 码中的一个重要成果是1 9 7 2 年由j u s t e s o n 用级联构造的j u s t e s o n 码，另一个重要的成果是前苏联学者g o p p a 在用有理分式 表示码字的基础上所构造的g o p p a 码，其渐进性很好，但码长很大，真正构造出 这种好码仍显困难。构造s h a n n o n 码的一个重要突破是8 0 年代初期由g o p p a 提出 的代数几何码。他将代数几何的理论和方法系统地应用于编码理论中，使得原来 线性码中的重要参数如码长、码距、维数等具有全新的几何意义，代数几何码的 研究成为8 0 年代和9 0 年代编码领域中研究热点之一。 在传统的通信系统的最佳接收机中，调解器和译码器是独立的两个部分。在 处理接收信号的过程中，调解器首先对调制器输入符号做最佳判决，然后将硬判 决结果送给译码器；译码器再对编码器输入消息做最佳判决，纠正解调器可以发 生的错误判决，这是硬判决的译码思想。事实上，经过解调器对符号的硬判决， 丢失了很多有利于译码的信息。为了提高编码通信系统的性能，人们从信息论的 角度对接收机中的解调器与信道译码器的功能划分和接口进行了审视，提出了软 判决译码方法，即解调器对输出不进行判决，送到译码器的是判决符号可能的概 率值或未经量化的输出，而非硬判决值，则译码器就可以利用这些信息与编码信 息综合作出判决，从而提高了系统的性能。研究表明，在接收机中解调器采用软 输出可以得到比硬输出高2 d b 左右的附加编码增益。 软判决译码算法主要分为两大类：一类是使符号错误概率最小的逐位软判决 译码算法，另一类是使码字错误概率最小的逐组软判决译码方法。 1 9 7 4 年j m a s s e y 提出了将编码与调制作为一个整体看待可能会提高系统性能 的设想。此后，许多学者研究了将此设想付诸实践的途径。其中，1 9 8 2 年u n g e r b o e c k 提出的t c m 概念是解决带宽和纠错这对矛盾的一个理想方案，他将纠错编码技术 与调制技术有机结合，在不增加系统带宽要求的条件下，通过扩展符号映射空间 来达到提高编码增益的目的。t c m 技术奠定了限带信道上编码调制技术的研究基 础，被认为是信道编码发展中的一个里程碑。另外，几乎在同一时期，日本学者 i m a i 提出了一种采用分组码的编码调制技术，称为b c m ( b l o c kc o d i n gm o d u l a t i o n ) 技术。他在衰落信道中的性能比较突出。 虽然软判决译码、级联码和编码调制技术都对信道码的设计和发展产生了深 3 远的影响，但是其增益与s h a n n o n 理论极限始终都存在2 - 3 d b 的差距。因此，在 t u r b o 码提出以前，信道截止速率r 一直被认为是差错控制码性能的实际极限， s h a n n o n 极限仅仅是理论上的极限，是不可能达到的。 直到1 9 9 3 年，t u r b o 码的提出以及1 9 9 6 年的低密度校验码( l d p c 码) 的再 发现，才让人们看到了逼近s h a n n o n 限的可能。 1 2 纠错码的基本原理 朦 最简单而可行的差错控制码方案叫做单比特校验码( s p c ) 。s p c 将单个附加 比特加到二进制信息码中，而整套差错控制码的价值所在就是消息中的这些附加 码。在偶校验码中，加到每个信息码中的附加比特能够确保该码字中的1 的数目 是偶数。每个码中1 的数目叫做码的码重量，简称为码重。 例如，待传输的7 比特信息码向量为s = l o10 01 1 1 ，附加在s 上的校 验比特是第s l y , 特。向量s 已经有偶数个( 指4 个) l 了，所以校验比特的值应为o ， 所得到的码字是1 0 1 0 0 11 0 更为严格的情况是，对于7 比特的信息码向鼍具有偶校验码，我们定义一个码 字向量弓，它具有如下结构： c = l c ( 1 )c ( 2 )c ( 3 )c ( 4 )c ( 5 )c ( 6 ) c ( 7 )c ( 8 ) i 其中每个c ( f ) ( 江1 ，2 ，8 ) 非o 则为l ，每个码字满足以下约束关系： c ( 1 ) o c ( 2 ) o c ( 3 ) oc ( 4 ) o c ( 5 ) o c ( 6 ) 0 c ( 7 ) o c ( 8 ) = 0 ( 1 1 ) 4 等式( 1 1 ) 叫做奇偶校验方程，简称校验等式，其中符号。代表模2 加。 又，一个7 比特的信息经过单比特奇偶校验码编码后，所得到的码字在有噪信 道中传输，接收端受到的向量为y = 【l 0 0l0 01 o 】根据式( 1 1 ) 来检 验夕是否是有效码字： 少( 1 ) o y ( 2 ) o y ( 3 ) o y ( 4 ) o y ( 5 ) o y ( 6 ) oj ，( 7 ) o y ( 8 ) = l o 0 0 0 0 1 0 0 0 0 0 1 0 0 = l 由于和是l ，说明奇偶校验方程不成立，所以y 不是一个有效码字。到现在， 至少我们已经能够检测出一位的传输误码了。 虽然由于信道噪声所导致的单比特反转可以很容易被单比特奇偶校验码检测 出来，但是这种单比特校验码不能够指出到底是那一比特，实际上或者应当说， 是那些比特，发生了反转。更进一层，由于任意偶数个比特反转都能够使接收到 的码字符合奇偶校验等式( 1 1 ) ，所以如果码字发生偶数个比特反转现象，单比 特校验码是无法将这种误码检测出来的。如果要检测多于1 比特的误码，则要求增 加冗余，即增加校验比特，同时将会有多个奇偶校验方程，每个码字都必须复合 所有的校验等式。 例1 1 ： 设一个已编码的向量为 c = i c ( 1 ) c ( 2 ) c ( 3 ) c ( 4 ) “5 ) c ( 6 ) i ， 其中包括了r i l l 3 位信息码和后3 位校验码。规定该向量的元素要满足下述3 个奇 偶校验方程： c ( 1 ) o c ( 2 ) o c ( 4 ) = 0 c ( 2 ) o c ( 3 ) o c ( 5 ) = 0 ( 1 2 ) d 1 ) o c ( 2 ) o c ( 3 ) o c ( 6 ) = 0 码字的约束关系方程又可以写为矩阵的形式，所以式( 1 2 ) 又可以表示成： 并记 010o q i 10l 0f 1001 l j c ( o c ( 2 ) c ( 3 ) c ( 4 ) c ( 5 ) c ( 6 ) = 罔 f 1 1010 o l h = i ollol o 1 i l1l00l i 矩阵h 叫做奇偶校验矩阵，简称为校验矩阵。矩阵h 的每一行对应一个校验 5 方程，每一列对应码字中的一比特。因此，对于一个二进制码，如果它有m 个奇 偶校验约束关系，码字的长度为，l ，则校验矩阵是一个尺寸为m t l 的二进制矩阵。 如果校验矩阵为h ，当且仅当向量 x = 石( 1 ) 工( 2 )x ( 3 )石( 4 )x ( 5 )x ( 6 )x ( 7 ) x ( 8 ) 】 满足： h x t = 0( 1 3 ) 时，它才是该码的一个有效码字。 1 2 2 编码 为了区别码字中的信息比特和校验比特，我们把校验方程( 1 2 ) 改写为如下 形式，使得每一个等式都以一个校验码为核心： c ( 4 ) = c ( 1 ) o c ( 2 ) c ( 5 ) = c ( 2 ) o c ( 3 ) ( 1 4 ) c ( 6 ) = c ( 1 ) o c ( 2 ) o c ( 3 ) 其中码字比特c ( 1 ) ，c ( 2 ) 和c ( 3 ) 是3 个信息比特，而c ( 4 ) ，c ( 5 ) 和c ( 6 ) 则是3 个 校验比特。写成这样的形式是为了说明如何对信息比特进行编码。根据约束关系 ( 1 4 ) ，信息码11 0 可以导出校验码如下： c ( 4 ) = l o l = 0 ， c ( 5 ) = 1 0 0 = l ， c ( 6 ) = 1 0 1 0 0 = 0 ， 所以，最终得到的码字为c = 10 010 0 1 0 1 再次将以上的约束关系方程写为如下的矩阵形式： 【c ( 1 ) c ( 2 )c ( 3 )c ( 4 ) c ( 5 ) c ( 6 ) 】= c ( 1 ) 0 010l q i 10111i 01011i j 并汜 10 0l0 1 g = l0 1011l i l o olo11 l 其中矩阵g 叫做码的生成矩阵。信息码一般记为向量 s = 卜( 1 ) s ( 2 ) s ( 尼) 】，其中向量u 包含后比特信息码。因此与信息码向量u 对 应的码字c 可以写为如下矩阵相乘的形式： c = s g ( 1 5 ) 若一个二进制信息码向量的长度为k ，编码后码字长度为，l ，则生成矩阵g 是 6 一个尺寸为七刀的二进制矩阵。式( 1 5 ) 的意义在于，它表现了编码的过程，即 编码器的输出码字c 是输入编码器的信息码向量s 与生成矩阵g 的乘积。显然，生 成矩阵g 是行满秩矩阵，因为它的各行以信息码向量s 的各分量为系数的线性组合 构成了所有的码字，也就是说，它的各行其实是该码的码字集合的一组基。 如果一套码具有k 个信息比特，则总共有2 七个码字。这2 个码字是2 4 个长度 为以的信息向量的一个子集。在式( 1 2 ) 所属的例子中，信息码的比特数为后= 3 ， 所以厅的可能取值有2 3 个，它们分别是： 00o 】， 00l 】， 111 】另外还有3 位 校验比特，则根据编码式子( 1 5 ) ，可以生成的有效码字为： 【00 0 0 00 】【00 l01 l 】【0l01 1l 】【01 1100 】 ，八 f 10 0101 1f 101 110 1f l10 010 1r l110 01 1 ki o ， 式( 1 5 ) 中的生成矩阵g 可以写为如下形式： g 。 g lg 2 】2 1 3 。3g 2 】 其中i ，。，是一个尺寸为3 x 3 的单位矩阵，g ：的尺寸为3 x 3 。设信息码向量为 s = 【s ( 1 ) s ( 2 ) s ( 3 ) 】，校验码向量为p = 【p ( 1 ) p ( 2 ) p ( 3 ) 】，则由式( 1 5 ) 可得： c = s g = s 【g lg 2 】 = s 【1 3 。3g 2 】 = 【s 1 3 。3s g 2 】 = 【ss g 2 】 = i sp 】 如上式所示，码字c 可以被分离为两部分，其一是信息码s ，另一部分是校验 码p 类似地，如果一种码，它的码字的信息码和校验码可以被分离为独立的两部 分，则称这样的码为系统码，也称为可分码。本论文所要讨论的内容都是关于可 分码的。 显然，对于可分码，若信息码向量s 的长度为后，校验码向量p 的长度为聊， 而编码后码字的长度为r l = k + m ，则生成矩阵具有如下形式： g 2 i 枞g 2 】( 1 7 a ) 其中g 的尺寸为k x n ，l m 是尺寸为k x k 的单位矩阵，g ：的尺寸为k x m ，而 且有p = u g ，根据前面所述的内容，设码的校验矩阵为h ，则它的尺寸为m x , t 设编码后的任一码字向量为c ，则有： h c t = 0 h ( u g ) t = 0 h g t u t = 0 根据有限域代数的理论，从上式可以得到： 7 h g = 0 类似地，将校验矩阵h 也写为如下形式： h 2 【h li - 1 2 】 其中子矩阵h ，的尺寸为m x k ，子矩阵h ：的尺寸为m x m ，则可以得到： h g t = 0 【h 。h ：】 i 枞g ：】1 = o 叩i h 2 】博l _ o l + h 2 g 2 t = 0 根据g f ( 2 ) 的运算法则，上式可得： h 2 g 2 t = 1 4 l 若校验矩阵h 行满秩，则可以设h ，可逆，则有 g 2 = h l t h 2 一t ( 1 7 b ) 若h ，不可逆，因为矩阵h 行满秩，则对校验矩阵h 做列置换就一定可以得到 可逆的子矩阵h ，另外，若矩阵h 本身就不是行满秩矩阵，则应当预先对h 进行 行简化，将其化为行满秩矩阵，则上面的推导仍然可行，并且对h 做这样的行简 化并不会改变矩阵h 的校验性能。 设矩阵h 行满秩，如果它不是行满秩，则通过行简化即可化为行满秩矩阵。 如果知道校验矩阵h ，就可以根据式( 1 7 a ) 和式( 1 7 b ) 就出相应的生成矩阵g 但是，如果只知道生成矩阵g ，是不能根据式式( 1 7 a ) 和式( 1 7 b ) 求出校验矩 阵的。然而，仍然可以根据高斯消元法将校验矩阵h 化为如下形式： i - i = 【h li 。j 而不改变其校验性能。从上式得知i - i ：= i 。，代入式( 1 7 b ) 可得： g 2 = h l t 综上，对于可分码，若有h = 【h 。h ：】，则一定可以得到g = i 腓h 。t h ：一t ； 若有g = 【i 枞g ：】，则可以，但并不一定有h = lg ：ti 。1 另外，对校验矩阵h 进行初等行变换是不会改变它的校验性的，所以对h 做初等变换后，再根据变换 后的h 和h ：求解生成矩阵g ，将会使g 具有不同的外观，但是它仍然是原来的 l d p c 码的生成矩阵。 注意到，分组码可以用不止一套校验方程组来定义。只有当所有码字都满足 式( 1 3 ) 时，由该式所定义的校验方程组才是有效的。对于日后要讨论的低密度 校验码，校验矩阵的选取是至关重要的。例1 1 中，约束关系方程组可以用以下的 校验方程组代替： c 0 ) o c ( 2 ) o c ( 4 ) = 0 c ( 2 ) o c ( 3 ) o c o ) = 0 c ( 1 ) o c ( 2 ) o c ( 3 ) o c ( 6 ) = 0 c ( 3 ) o c ( 4 ) o c ( 6 ) = 0 但是第4 个方程是第l 和第3 个校验方程的线性组合，即第4 个方程是线性依赖 于其它方程的。总的来说，一套码可以有任意数目的校验方程，但是它们之中只 有m = 刀一k 个方程是线性独立的，即校验矩阵有无限多的形式，但是它的秩只可 能是m 1 2 3 误码检测和纠错 假设一个码字在二进制对称信道中传输，其中的一个或多个比特出现反转。 纠错码的任务就是找出发生反转的比特位，还要尽可能纠正误码。首先，我们已 经知道，任何码字都必须满足式( 1 3 ) ，所以，如果接收端受到的任何一个码字 不满足该式，则说明传输过程中发生了错误。 设例1 1 中，传输的码