（通信与信息系统专业论文）g9751中两种efec算法的研究与实现.pdf

中文摘要 摘要：随着光通信技术向更长距离、更大容量和更高速度的进一步发展，各路光 信号之间的串扰，信号的同步、定时、恢复等问题也随之而来。这一切都会引起 光通信中误码的产生，从而降低了通信的可靠性。通信可靠性的降低最终又制约 了通信质量的提高，通信距离的延长、多路复用的大规模应用，以及通信设备成 本的精简，因此大大阻碍了光通信的进一步发展。因此，在随机噪声的信道中如 何克服干扰，减小信息传输的差错，同时又不降低信息传输的效率，即如何解决 系统的有效性与可靠性之间的矛盾，成为目前光通信技术研究的热点。一种具有 更强纠错能力的新s u p e r - f e c 码型逐渐成为人们研究的热点。r r u t 也制定了 g 9 7 5 1 标准，详细介绍了8 种超强纠错性能的码型。 另外，b c h 码是迄今为止所发现的一类很好的线性纠错码类，在移动通信、 无线寻呼系统以及光纤通信等领域应用广泛。本文结合b c h 码的特点，对s u p e r - f e c 的两种算法分别进行了研究。 第三章先对传统的级联码与改进的级联码分别进行了介绍，接着对i 3 中描述 的级联型的b c h 码的帧结构进行了详细研究，并给出了相应的编译码方案。通过 m a t l a b 编程实现了编译码以及帧结构的变换。 第四章对i 7 中描述的正交级联的b c h 码的帧结构进行研究，给出了帧的行码 字与列码字的分配方案，以及g 9 7 5 兼容帧结构的映射方案。其次，本章又介绍了 扩域的构造与域元素运算，为接下来的译码算法做准备。在编译码的概念介绍中， 重点介绍基于多项式除法电路的编码及基于b m 算法的迭代译码。通过m a t l a b 编 程实现了b c h 码的编译码，并分析了不同结构的b c h 码的误码性能。 实验结果表明：在相同的误码信道中，i 3 与i 7 中介绍的两种b c h 码的帧结构 相比普通的b c h 码具有更加优秀的纠错能力。分析结果对提高通信可靠性的进一 步研究与设计具有一定的参考价值。 关键词：s u p e r - f e c 算法；b c h 码；m a t l a b 编程；编码；迭代译码 分类号：t n 9 1 9 3 a bs t r a c t a b s t r a c t ：w i mt h eo p t i c a lc o m m u n i c a t i o nt e c h n o l o g yt ot h ed e v e l o p m e n to fl o n g d i s t a n c e ，h i 曲c a p a c i t ya n dh i g hs p e e d ，t h ep r o b l e m st h a te r o s s t a l kb e t w e e no p t i c a l s i g n a l s ，s i g n a ls y n c h r o n i z a t i o n ，t i m i n g , r e c o v e r y , w o u l df o l l o w a l lo ft h e s ew o u l dl e a d t op r o d u c t i o no fo p t i c a lc o m m u n i c a t i o ni ne r r o r , a n dr e d u c et h e r e l i a b i l i t y o f c o m m u n i c a t i o n t h er e d u c t i o no fc o m m u n i c a t i o nr e l i a b i l i t yh a su l t i m a t e l yr e s t r i c t e dt h e i m p r o v e m e n to fc o m m u n i c a t i o nq u a l i t y t h ee x t e n s i o no fc o m m u n i c a t i o nd i s t a n c e ， l a r g e - s c a l em u l t i p l e x i n ga p p l i c a t i o n s ，a n d s t r e a m l i n et h ec o s to fc o m m u n i c a t i o n s e q u i p m e n t ，t h e s e w o u l d g r e a t l y h i n d e rt h ef u r t h e r d e v e l o p m e n t o f o p t i c a l c o m m u n i c a t i o n t h e r e f o r e ，h o wt oo v e r c o m et h en o i s ei nt h er a n d o mc h a n n e l ，a n dh o w t or e d u c et h ee r r o r si ni n f o r m a t i o nt r a n s m i s s i o nw i t h o u tr e d u c i n gt h ee f f i c i e n c yo f i n f o r m a t i o nt r a n s m i s s i o n ，t h a ti sh o wt os o l v et h ec o n t r a d i c t i o nb e t w e e nt h es y s t e m s e f f e c t i v e n e s sa n d r e l i a b i l i t y , w o u l db e c o m e t h e h o t p r o b l e mo f t h e o p t i c a l c o m m u n i c a t i o nt e c h n o l o g y ak i n do fs t r o n g e re 玎r o rc o r r e c t i o nc a p a b i l i t yo ft h en e w s u p e r - f e cc o d et y p eh a sb e c o m e af o c u sf o rr e s e a r c h e r s n u - tg 9 7 5 1s t a n d a r da l s o i n t r o d u c e st h ee i g h tk i n d so fs u p e re r r o rc o r r e c t i o np e r f o r m a n c ep a t t e r ni nd e t a i l i na d d i t i o n , b c hc o d ei sag o o dl i n e a re r r o r - c o r r e c t i n gc o d et h a tw o u l df f y 6 1 1 b e f o u n d ，i tw o u l db ew i d e l yu s e di nm o b i l ec o m m u n i c a t i o m ，w i r e l e s sp a g i n gs y s t e m sa n d f i b e r - o p t i cc o m m u n i c a t i o n i nt h i sp a p e r , t h ec h a r a c t e r i s t i c so fb c hc o d e s ，t w oo ft h e s u p e r - f e ca l g o f i t h r n sa r es t u d i e ds e p a r a t e l y i nc h a p t e rt h r e e ，t h et r a d i t i o n a lc o n c a t e n a t e dc o d e sa n di m p r o v e m e n to f c o n c a t e n a t e dc o d e sa r ei n t r o d u c e df i r s t l y t h e nt h ef r a m es t r u c t u r eo ft h ec o n c a t e n a t e d b c h s u p e rf e cc o d e sh a sb e e ns t u d i e di nd e t a i li n1 3 ，a n dt h ec o r r e s p o n d i n gc o m p i l e d c o d es c h e m ei sg i v e n 1 1 1 eb c he n c o d i n g , d e c o d i n ga n dt h ef r a m es t r u c t u r eo ft h e t r a n s f o r m a t i o nh a v eb e e ni m p l e m e n t e dt h r o u g ht h em a t l a bp r o g r a m m i n g i nc h a p t e rf o u r , t h ef r a m es t r u c t u r eo ft h et w oo r t h o g o n a l l yc o n c a t e n a t e db c h s u p e rf e cc o d eh a sb e e ns t u d i e di n1 7 ，a n dt h er o wa n dc o l u m nc o d e w o r d sa l l o c a t i o n a n dm a p p i n gf r o mg 9 7 5c o m p l i a n tf r a m i n gs c h e m e sa r eg i v e n m o r e o v e r , t h i sc h a p t e r i n t r o d u c e st h es t r u c t u r eo fe x t e n s i o nf i e l do p e r a t i o n sa n df i e l de l e m e n t s ，a sp r e p a r a t i o n f o rt h en e x td e c o d i n ga l g o r i t h m i nt h ec o n c e p to ft h ee n c o d i n ga n dd e c o d i n g , t h e e n c o d i n gb a s e do np o l y n o m i a ld i v i s i o nc i r c u i ta n di t e r a t i v ed e c o d i n ga l g o r i t h mb a s e d o nb ma n dm a i n l yi n t r o d u c e d t h eb c he n c o d i n ga n dd e c o d i n gh a v eb e e n l v i m p l e m e n t e dt h r o u g ht h em l a bp r o g r a m m i n g , t h eb c hc o d e t h ee r r o rr a t e p e r f o r m a n c eh a sb e e na n a l y z e di nd i f f e r e n ts t r u c t u r e s t h er e s u l t ss h o wt h a t ：w i t ht h es a m ee r r o rc h a n n e l ，t h ef r a m e ss t r u c r l r eo ft w o b c hc o d e sr e 向明c e di n1 3a n d1 7 h a v em o r ee x c e l l e n te ll o rc o r r e c t i o nc a p a b i l i t y c o m p a r e dt oo r d i n a r yb c hc o d e s t h er e s u l t sh a v es o m er e f e r e n c ev a l u et oi m p r o v e c o m m u n i c a t i o nr e l i a b i l i t yf o rt h ef u r t h e rr e s e a r c ha n dd e s i g n i n g k e y w o r d s ：s u p e r - f e ca l g o r i t h m ；b c hc o d e ；m a t l a bp r o g r a m m i n g ；e n c o d i n g ； i t e r a t i v e l yd e c o d i n g c i 。a s s n o ：t n 9 19 3 v 致谢 光阴荏苒，转眼间硕士生活即将结束。在北京交通大学两年半的研究生学习 中，我收获颇丰。回想起来，除了自己的努力之外，更多的是现代通信网实验室 的老师及同学们的支持和帮助。在本文即将完成之际，我衷心地向他们表示谢意。 感谢我的导师李兴华副教授，本论文的工作是在李老师的悉心指导下完成的， 李老师严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感 谢两年多来李兴华老师对我的关心和指导。 感谢实验室荆涛教授给予我的指导。在我攻读硕士学位期间，在学习上和生 活上都给予了我很大的关心和帮助，并悉心指导我们完成了实验室的科研工作， 在此向荆涛老师表示衷心的谢意。 在实验室工作及撰写论文期间，霍炎博士在专业知识的学习和研究工作中给 予了热情帮助，并对我的科研工作和论文提出了许多宝贵意见，在此向他表达我 的感激之情。霍炎师兄学而不厌、诲人不倦以及致力于攀登学术高峰的工作精神 也在潜移默化中影响着我，是我终身学习的榜样。还要感谢现代通信网实验室的 所有师兄师弟们，特别是仲丽嫒、蒙海光和李伟杰同学，他们对我论文的研究工 作给予了极大地帮助，在此向他们表达我的感激之情。 另外，感谢一直以来支持我、鼓励我的家人，他们的理解和关心使我能够在 学校专心完成我的学业。特别是我的父母，他们默默地支持与不尽地关爱，见证 了我成长的每一步，二十多年来为我付出的一切都是我一生无法报答的。 最后，再一次对大家给予我的帮助表示诚挚的谢意。 1 引言 1 1 研究背景和意义 通信是人与人之间、人与机器之间的信息传输、处理或再现信息的过程。它 涉及信息的发送者、接收者和传输媒体。其中，凭借着丰富的带宽资源和相对低 廉的制造成本，光纤通信系统被很多专家誉为是下一代宽带通信网的基础。目前， 全球通信数据的业务呈指数型增长，这极大地拓展了电信网对光通信技术的需求 空间。从上世纪8 0 年代至今，仅仅在一对光纤上的信息传输总速率就从之前的每 秒1 5 兆比特，猛增到每秒数太比特，提高了数百万倍，而且这个数字预计在未来 十年里还将再次被打破。现在，光纤通信系统己被世界诸多国家所认可，成为世 界的主导传送网络，而光纤通信的技术也逐渐发展到包含光交换技术的全光网络 技术。 但是，随着光传输系统速率的不断提升，系统容量的成倍增大，这也引发了 一些新的问题【l l 。传输速率的大幅提高加剧了光纤的色散和非线性效应，容量的扩 大也引起一系列如各路光信号之间的串扰，信号的同步、定时、恢复的问题，这 些都会产生误码，从而使通信的可靠性降低。通信可靠性的降低又会产生一系列 的连带关系，比如通信距离的延长、通信质量的提高、多路复用技术的大规模应 用、以及通信设备德费用问题都将受到制约，这极大地减缓了光通信技术的前进 步伐。 现阶段，对器件的硬件性能的研究已遇到瓶颈，而改善硬件的性能必然会增 加系统的成本，这显然不是专家们所需要的方案。专家们发现，采用f e c 技术可以 解决之前的问题，这种技术能够用较为低廉的系统成本，通过降低光通信中的误 码率，改善光传输系统中的误码率性能。目前，随着光传输速率的逐步提高，f e c 技术在光通信系统中的重要性会越来越重要。 通信系统的质量评估包括有效性、可靠性、安全性、经济性、标准性、可维 护性等【2 】。这里，有效性是指在单位时间内能够传输多少信息；而可靠性是指发送 的信息是否无误地从接收端获得。因此，目前很多专家在设计一个通信系统时， 如何能够更加合理的解决可靠性与有效性这一对矛盾，成为他们设计得关键【3 1 。 1 9 4 8 年，香农在他的一篇论文通信的数学理论【4 】中，提出了著名的有扰 信道编码定理，就是目前所被人熟知的香农定理，这个定理也首次阐明了在有扰 信道中实现可靠通信的方法，这也奠定了纠错编码的基石，香农也因此被人们称 为“信息论之父 。 根据香农的信息理论，数字通信系统的基本组成如图1 1 所示【5 】【6 】。 图i - 1 数字通信系统 f i g 1 - 1d i g i 【t a lc o m m u n i c a t i o ns y s t e m 在图1 1 中，信源编码器的作用是把从信源发出的诸如语音、图像、文字这类 消息转换成二进制或者多进制形式的信息序列。在传输过程中为了能够抵抗各种 干扰，往往要人为地增加一些冗余度，使其能够自行检错与纠错，实现这种功能 就得需要信道编码器。在信道传输的过程中，数字信号经常会遇到各种干扰，造 成信号的失真，而这些信号经过数字解调器后，变成了二进制或者多进制形式的 信息序列。由于存在信道的干扰，该信息序列中可能已经出现了错误，通过接下 来的信道译码器对序列中的错误进行纠正，再经过信源译码器恢复成原来的消息， 并发送给用户。 1 2发展现状 香农编码定理以后汉明等人在5 0 年代初，根据香农的思想，给出了一系列有 效译码的方法。纠错码越来越受到大家的重视，同时无论在理论还是实际中都得 到了飞速发展。 纠错编码的发展可大致分为以下几个主要阶段【7 1 ，如图1 2 所示： 发 展 状 况 图l - 2 纠错编码的发展阶段 f i g 1 - 2t h ed e v e l o p m e n t a ls t a g eo ff e c 5 0 年代至6 0 年代初，这是纠错编码从无到有得到了迅速发展的阶段，为日后 的线性分组码奠定了理论基础。汉明率先提出可以纠正一个独立错误的线性分组 卜汉明码。不久之后，莫勒提出一种能纠正多个错误的码，里德则立即给出它 的译码方法。1 9 5 7 年，e 普勒齐引入了循环码的概念。之后，又相继出现b c h 码及 有限域的概念。 6 0 年代至7 0 年代，这是纠错编码发展过程中最为活跃的一段时期，以代数方 法特别以有限域理论为基础的线性分组码理论己日趋成熟。期间，诸多专家们提 出了许多有效的编译码方法，如门限译码、迭代译码、软判决译码和卷积码的维 特比译码等。此外，还针对纠错编码的实用化问题进行相关研究及讨论，例如译 码错误概率、码的重量分布、信道的模型化等，所有这些问题的研究为纠错编码 的实用打下了坚实基础。 7 0 年代初至8 0 年代，这是纠错编码发展过程中具有重要意义的时期。以戈帕 为首的一派学者构造了一类子码，并能达到香农在信道编码定理中所提出的码一 香农码所能达到的性能，这在纠错编码历史上具有划时代的意义。在这期间大规 模集成电路和微机的迅速发展，为纠错码的应用打下了坚实的物质基础，因而与 实用相关的各种技术及有关的问题得到极大的关注，并在实际应用中取得了巨大 的成功。美国发射的“旅行者 号宇宙飞船中，发现了天王星的9 个卫星和光环以 及海王星的6 个卫星和光环，便是纠错编码技术的成功应用。 f l s o 年代初以来，戈帕等从几何观点讨论了分析码，利用代数曲线构造了一 类代数几何码。在这些码中，某些码的性能达到了香农码所能达到的性能。在这 期间，美国学者昂格尔博克把编码与调制相结合提出的网格编码调制技术是编码 理论的又一重要里程碑。 2 1 世纪以来，针对光传输网势不可挡的发展趋势，i t u t 推出了一系列标准， 其中尤其以2 0 0 1 年2 月推出的g 7 0 9 建议具有重大意义，它指出了光联网的技术基础 哺j 。随着光通信技术向更长距离、更高速度的进一步发展，对更高增益的f e c 技术 的呼声也越来越耐9 1 。基于g 9 7 5 和g - 7 0 9 的r s ( 2 5 5 ，2 3 9 ) 已经不能满足这种新的要 求，在这种背景下人们开始研究具有更强纠错能力的s u p e r - f e c 码型，目前比较热 门的s u p e rf e c 技术o 有r s ( 2 5 5 ，2 3 9 ) + r s ( 2 5 5 ，2 2 3 ) ，r s ( 2 5 5 ，2 3 9 ) + c s o c ， r s ( 1 0 2 3 ，1 0 0 7 ) + b c h ( 2 0 4 7 ，1 9 5 2 ) ，b t c ( b l o c kt u r b oc o d e s ) 碉j t 和l d p c 码【1 2 】等几种。 目前，基于s u p e r f e c 技术已经推出了部分相应的芯片，如：i n t e l 公司推出了 i x f 3 0 0 0 7 ，采用中间加交织器的两级r s 码级连，也具有较高的编码增益。m u t i l i l l l 【 公司推出了m t c 6 1 3 1 ，也采用了级联码，使用r s ( 2 5 5 ，2 3 9 ) 码做外码，b c h 码做内 码，中间加入了交织器，而译码器则采用了迭代译码法，具有很好的纠错性能。 另外，l a t i c e 和a g e r e 等公司也正在研究s u p e r - f e c 技术。针对这种百家争鸣的技术 现状，n u - t 开始讨论制定g 9 7 5 x ，该建议草案将推出两种具有超强纠错能力的 s u p e r - f e c 码型：b c h ( 3 8 6 0 ，3 8 2 4 ) + b c h ( 2 0 4 0 ，19 3 0 ) 和r s ( 2 5 5 ，2 3 9 ) + t 2 s o c ( k 0 n 0 = 6 7 ，j = 8 ) 。此外，基于近香农限码型( 如b t c 码和l d p c 码) 的具有更强纠错能 力i 拘s u p e r - f e c 技术【i3 】也引起了人们的研究兴趣。 1 3 本文结构安排 本论文的结构是这样安排的： 第一章( 引言) ：介绍了本论文的研究背景和意义。首先分析了f e c 技术在光 传输系统中的重要性，然后介绍了f e c 技术在国内外的发展现状及它的应用前景。 f e c 技术本身存在着瓶颈，当随着光通信技术向更高速率、更大容量的方向发展时， 具有更强纠错能力的s u p e r - f e c 技术将会逐渐取代f e c 技术，来提高光传输系统的 可靠性，提高通信速率，增加通信容量，延长通信距离。最后，重点介绍了本人 在研究生毕业设计阶段所做的工作以及本论文的总体结构安排。 第二章( 纠错编码基础) ：介绍b c h 码以及b c h 码编译码相关的数学基础知识 和纠错编码基础理论。另外，介绍了循环码和乘积码的基本概念。 第三章( g 9 7 5 1 中i 3 算法的研究与编译码方案) ：本章与下一章分别从级联码 形式与乘积码两种形式对s u p e r - f e c 进行改进。本章针对g 9 7 5 1 建议中i 3 算法进行 详细的分析，得出了相应的实现方案。以及i 3 算法中b c h 码的编译码以及帧结构 4 变换的实现。， 第四章( q 9 7 5 1 中i 7 算法的研究与编译码方案) ：本章针对g 9 7 5 1 建议中i 7 算法进行详细的分析，得出了相应的实现方案。以及i 7 算法中b c h 码的编译码实 现。系统b c h 码的编码算法以及基于b m 算法迭代译码的实现。 第五章( 结论及展望) ：总结了本人所做的工作，并结合目前光传输系统中 s u p c r - f e c 技术的研究现状，指出- j s u p e r - f e c 技术进一步研究的研究方向。 5 2 纠错编码基础 b c h 码的构造及编译码原理是建立在近世代数和数论的基础上的，要设计与 实现b c h 码编译码器，必须研究有关的数学基础知识，本章将阐述与b c h 码编 译码相关的数学基础知识和纠错编码基础理论【1 】【1 4 】【15 1 。 2 1代数基础 2 1 1 群和域 l 、群 定义2 1 对于一个非空集合g 以及定义在g 上的一种运算“”( 泛指任何 一种代数运算，如+ ，一，x ，模m 加o ，模m 乘0 等) ，若满足以下4 个条件： 封闭性：对任意的a ，b g ，恒有：a 6 g ： 结合性：对任意的口，b g ，有：似6 ) c = a ( 6 c ) ； 单位元：存在一个元素p ，即a g ，对任意元素有：a e = e 口= a ； 逆元：对任意a g ，存在一个逆元a - 1 g ，使a a 一= a - 1 a = g ； 则称g 构成一个群。若对任意的口，b g ，有a 6 = b 口，则g 称为交换群或 a b e l 群。 2 、域 定义2 2 非空集合f 中定义了加法和乘法两种运算，若满足下述条件： 关于加法运算构成交换群，其加法恒等元记为o ； f 中所有非零元素对乘法构成交换群，其乘法恒等元记为l ； 对加法和乘法满足分配律，即对任意a , b ，cef ，有：口( 抖c ) = a b + a c 则称f 是一个域。域中的元素个数叫做域的阶。若域中的元素个数有无限多 个，则称为无限域。域中的元素个数有限，称为有限域或伽罗华( g a l o i s ) 域。含有 口个元素的有限域记为g f ( q ) 。 称瞅g ) 为g f ( q ”) 的基域，g f ( q 肼) 为g f ( q ) 的扩域。 定义2 3 域中非0 元素所构成的乘法群之阶定义为域中该元素的级。 若在g f ( q ) 的中，某一元素a 的级为g 1 ，则称a 为本原域元素。 6 2 1 2 有限域上多项式 有限域鲫的上的以次多项式定义为： f ( x ) = 厶x 4 + 以1 x 4 _ 1 + + 石x + f o z g f ( q ) i = 0 ，1 ，2 ，n 称系数不为零的工的最高次数为多项式州的次数，记为a o f ( x ) 或d e g f ( x ) 。 而最高次的系数为l 的多项式称为首一多项式。g f ( q ) 的上x 多项式的全体组成的 集合记为疋i x 】。 定理2 1 对t f ( x ) i x 】，若用某一多项式g ( x ) i x 】去除，有唯一的一对 多项式鼋，满足： ( x ) g ( 功g ( x ) + ，( 力a 。，( x ) o o g ( x )( 2 一1 ) 式中口( x ) 为删被荆除所得商式，删为余式。式( 2 2 ) 称为多项式带余除法， 亦记为 厂( 神暑r ( x ) m o d g ( x ) 或 ，( 力= 如，【厂( x ) 】 我们也称删为似) 按模酬运算所取的余式。 定义2 4 设州是次数大于零的多项式，若除常数和常数与本身的乘积以外， 再不能被【z 】上菇色多项式除尽，则称斛为g f ( q ) i - _ 的既约多项式。 定义2 5 设为g f ( q ”) 中的某一元素，系数在g r g ) 的上且满足m ( f 1 ) = 0 的最 低次多项式r e ( x ) 称作的最小多项式。 定义2 6 系数在g f ( q ) l ：f f - j 以g f ( q m ) 上本原元为根的最小多项式，称为本原 多项式。 定理2 2 若g f ( 2 ) 上的m 次既约多项式p 除尽，+ 1 的最小正整数满足 刀= 2 ”- 1 ，则p 为本原多项式。 2 1 3本原元 定义2 7 在g f ( 2 ) 中，某一元素口的阶为q - 1 ，即口g 一等e ( q l 是使等式成立 的最小正整数) ，则称口为本原元。 2 2纠错编码的基本原理 由于受到不理想的信道传输特性以及加性噪声的影响，在实际信道上传输信 7 号的过程中，在接收端收到的信号难免会产生错误，这在移动通信领域中尤为常 见。对于移动通信来说，复杂、恶劣的传播条件是其信道的特征，是不可回避的 问题。如果想要在这样的传播条件下仍要保证传输质量的话，就必须采取一定的 技术措施。 纠错编码技术就是其中一种有效的抗衰落技术。纠错编码又称信道编码，它 与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直 接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。 为了使一种码具有检错或纠错能力，必须对原码字增加多余的码元，以扩大 码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一 个码字。准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个 码字的码元问有一定的关系。关系的建立称为编码。码字到达接收端后，用编码 时所用的规则去检验。如果没有错误，则原规则一定满足，否则就不满足。由此 可以根据编码规则是否满足以判定有无错误。当不能满足时，在可纠能力之内按 一定的规则确定错误所在的位置，并予以纠正。纠错并恢复原码字的过程称为译 码：码元间的关系为线性时，称为线性码；否则称为非线性码。检错码与其他手 段结合使用，可以纠错。检错反馈重发系统( a r q 系统) 就是一例。 在构造纠错码时，将输入信息分成k 位一组以进行编码。若编出的校验位仅 与本组的信息位有关，则称这样的码为分组码。若不仅与本组的k 个信息位有关， 而且与前若干组的信息位有关，则称为格码。这种码之所以称为格码，是因为用 图形分析时它象篱笆或格架。线性格码在运算时为卷积运算，所以叫卷积码。 纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间 的汉明距离d ( x ，y ) 来衡量。它的定义为码字x 与y 之间的对应位取不同值的码元 个数。一种纠错码的最小距离d 定义为该种码中任两个码字之间的距离的最小值。 一种码要能发现p 个错误，它的最小距离d 应不小于什l 。若要能纠正t 个错误，则 d 应不小于2 什1 。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中 非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小 重量与其最小距离在数值上是相等的。 在构造线性码时，数字上是从n 维空间中选一k 维子空间，且使此子空间内 各非零码字的重量尽可能大。当构造循环码时，可进一步将每一码字看成一多项式， 将整个码看成是多项式环中的理想，这一理想是主理想，故可由生成多项式决定；而 多项式完全可由它的根规定。这样，就容易对码进行构造和分析。这是b c h 码等循 环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联 系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。 若一种码的码长为刀，码字数为脱或信息位为h ，以及最小距离为d ，则可把此码记 作伽批d ) 码。若此码为线性码，常简记作( 万，妨或( ，l ，屯回码。人们还常用r = l o g ：m n 表示码的信息率或简称码率，单位为比特码元。尺越大，则每个码元所携带的信息量 越大，编码效率越高。 信道容量是信道能够传输的最大信息率【1 6 】。如果噪声的单边功率谱密度为 n o ( w h z ) ，信道的带宽为s ( h z ) ，信号功率为双、聊，则该信道的信道容量c ( b i t s ) 为： c = 肌g ( 1 + 南( 2 - 2 ) 即著名的香农公式。在高斯信道中，若信道的信息率为r ( b i t s ) c ，令 邑= 导为每比特的信号能量，则有 尝 型 l n 2 叫5 9 d b ( 2 - 5 ) v 0 厂 即高斯信道传输信息在功率受限的情况下，必须要保证信噪比e d n o 的下限， 通常称为香农极限，但是在实际的通信过程中往往达不到这个极限。 在数字通信过程中，即便采用相同的调制方式，由不同的编码方案得到的解 调信噪比也是不同的。通常采用的编码方式有线性分组码、循环码、l d p c 码以及 b c h 码等等。在信道编码中，有两个非常重要的概念，一个是码重，即码组中非 零码元的数目为码组的重量。例如0 1 0 码组的码重为l ，1 0 1 码组的码重为2 ，1 1 1 码组的码重为3 ；还有一个就是汉明距，即两个码组中对应码位上具有不同二进制 码元的位数，汉明距又称码距。码距的概念规定： ( 1 ) 在一个码组内检测e 个错码，要求最小码距之升l ； ( 2 ) 码组内纠正t 个错误要求最小码距d m 砬2 t + l ； ( 3 ) 码组内纠正t 个误码，同时检测p ( p f ) 个错码要求最小码距。 f + p + l 。 2 3 线性分组码 2 3 1 差错控制系统的分类 9 在信道传输中，我们所关心的是传输的可靠性问题【1 7 1 ，信息传输系统模型如 图2 1 所示。 图2 1 信息传输系统模型 f i g 2 - 1i n f o r m a t i o nt r a n s m i s s i o ns y s t e mm o d e l 图中，等效信源是指原来的信源和信源编码器，它的输出是二进制信息序列”， 纠错编码器按一定的编码规则将“编成码字c 遣入信道，信道是包括调制器、传 输媒质和解调器在内的数字信道( 也称编码信道) ，它的输入时码字c ，输出时接 受码字y ，纠错译码器根据编码规则对接受码字进行译码，输出估值y ，信宿包括 信源译码器和用户，它的输入是经过了纠错的估值序列y 。 按照码的纠错能力的不同，可分为检错码和纠错码。其中，能发现错误但不 能纠正错误的码称为检错码：不仅能发现错误而且还能纠正错误的码称为纠错码。 检错码和纠错码之间并不存在严格意义上的界限，有时纠错码也可用于检错，而 一些检错码也有一定的纠错能力。 检错码和纠错码可应用于不同的差错控制系统中。在数字通信系统中，利用 纠错码或检错码进行差错控制的方式大致分为前向纠错( f e c ) 、重传反馈( a r q ) 、 混合纠错( h e c ) 三种方式。如图2 2 所示。 f e c a r q p 佃j 塑型l 沥，o 眦江 能够发现错误的码 应答信号 可以发现和纠正错误的码 应答信号 跏。 物一。 图2 2 差错控制的基本方式 f i g 2 - 2b a s i cm o d eo fe r r o rc o n t r o l ( 一) 前向纠错方式( f e c ) 前向纠错方式是增加数据通讯可信度的方法。在单向通讯信道中，一旦错误 被发现，其接收器将无权再请求传输。f e c 是利用数据进行传输冗长信息的方法， 1 0 当传输中出现错误，将允许接收器再建数据。其特征是信息字段和校验字段的长 度可以任意选定。这种方式的优点是不需要反馈信道，能进行一个用户对多个用 户的同播通信。其缺点是译码设备比较复杂，所选用的纠错码必须与信道的干扰 情况相匹配，因而对信道的适应性较差。 ( - - ) 重传反馈方式( a r q ) 重传反馈方式是指发送端发出可以检测错误的码，通过信道送到接收端，译 码器只须判决码组中有无错误出现，再将判决信号通过反馈信道送回发端。发送 端根据这些判决信号，把接收端认为有错的消息重新进行传送，如此反复，直到 接收端认为正确为止。这种方式需要一个反馈电路，因此控制电路比较复杂。其 优点是：编译码设备比较简单；在一定的冗余度码元下，编码的检错能力一般要 明显高于纠错能力，整个系统具有极强的纠错能力，并能获得极低的误码率。其 缺点是传送消息的连贯性和实时性较差。若信道干扰很频繁，则系统会经常处于 重发消息的状态。 ( 三) 混合纠错方式( h e c ) 这种方式下发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错 能力。在接到序列之后，接收端首先要检验错误的数目情况，看是否在纠错码的 纠错能力以内，以便可以自行纠正。但是，如果错误的数目超过了码的纠错能力， 也可以检测出来，不过需要通过反馈信道，要求发送端重新传送这段出错的消息。 这种方式可以达到较低的误码率，因此在实际中得到广泛的应用。 值得指出，在设计差错控制系统时，选择何种实现方式，应综合考虑各方面 的因素，主要有： ( 1 ) 满足用户对误码率的要求； ( 2 ) 有尽可能高的信息传输速率； ( 3 ) 有尽可能简单的编译码算法且易于实现； ( 4 ) 可接受的成本。 2 3 2 超强前向纠错简介 超强前向纠错( e f e c ，e n h a n c e df o r w a r de r r o rc o r r e c t i o n ) i s 】，通常也被称做 s u p e rf e c 、h i g hf e c 或a d v a n c e df e c ，这是针对g 7 0 9 和g 9 7 5 所规定的标准 f e c 而言的。由于目前还没有统一的标准，诸多厂家所采用超强前向纠错的算法 也不尽相同。目前，实现超强前向纠错的方法可以大致分为两种：一种是采用两 级矩阵式编码，例如r s r s 、r s b c h 、b c h b c h 编码等，这也完全突破了g 7 0 9 标准所规定的帧结构，；另一种是保留了g 7 0 9 标准所规定的帧结构，只是替换了 帧结构中冗码部分的算法，而不采用规定的r e e d - - s o l o m o n ( 2 5 5 ，2 3 9 ) 5 j g 法b 9 】。这 两种方法各有利弊，第一种方法可以获得较高的净编码增益，可以达到7 - - - 8 d b ， 但是同时也付出了1 5 - 2 5 的带宽，这种方法目前已开始使用；第二种方法保持 了原来7 的冗码比例，通过算法的优化来获得比标准前向纠错更好的编码增益。 当然，相对于第一种方法，这种方法获得的编码增益略低。 2 3 3 线性分组码的概念 目前，绝大多数的数字计算机和数字通信系统中广泛采用二进制形式的码， 因此以下对线性分组码的讨论都在有限域g f ( 2 ) 上进行。域中元素为 o ，1 ) ，域中运 算为模2 加法和模2 乘法。 信源所给出的二元信息序列首先分成等长的各个信息组，每组的信息位长度 为k ，记为 “= ( u t - ! u i 一2 u o ) 显然，信息组m 可能有2 种取值。编码器按一定规则，将输入的信息组编制 成长为刀的码字，记为 c = ( q i q - 2 c o ) 在c 的r t 个元素中，有k 位是信息元，n - k 位是校验元，如果各校验元与k 位 信息元之间的关系是线性的，则称这样的码为线性分组码。 2 3 4 生成矩阵和校验矩阵 ( 厅，助线性分组码的2 个码字组成了个k 维子空间，因此这2 个码字完全可 由k 个独立矢量所组成的基底而张成。设基底为： c l = 【g i , n - ig 一2 ， 6 l go j c 2 = 【9 2 川，9 2 柚，9 2 oj ： g = k 枷巾g 如一2 ，g 柚) 若把这组基底写成矩阵形式，则有 g = g l ， 一i , g t 一2 ，, 9 1 0 9 2 。p i , 9 2 卜2 ，, 9 2 0 ： g i 扩i , g k 扩2 ，, g k 0 ( 疗，助线性分组码中任何码字，都可由这组基底的线性组合生成，即： 1 2 c = m g = 川m 棚 9 1 0 9 2 0 gk 0 ( 2 - 6 ) 式中，m = 似川埘棚m 枞) 是k 个信息元组成的信息组。因此，若邑知信息 组m ，通过式( 2 7 ) 可求得相应的码字，称式( 2 7 ) 的g 为( ，l ，p 线性分组码的生成矩 阵。 ( 以，d 线性分组码的编码问题就是在满足给定码的最小距离或码率的条件下，如 何从已知的k 个信息元来求出产以k 个校验元。这相当于建立了一组线性方程组， 即已知k 个未知数，求n k 个未知数。建立这组方程组需要用到线性分组码中的一 致校验矩阵。 任何一个( 疗，助线性分组码的一致校验矩阵日可表示为： h = j i l l 。- i l l 。吨j i i i 。o j j l 2 。_ lj 1 2 j i 一2 h 2 o ； ； ； 九一t - 一l 丸一t j i 一2 h n 吨。 由h 矩阵可以建立码的线性方程组： 或 简写成 或 。一。 一一z 啊，o h 2 一lh 2 。h 一2 h 2 o iii h 一七， 1j i l 一七。 一2 h h i ，o ( c “c n 一2 c o h c r = 0 r c h7 = 0 q l 、i i - 屯| - 0 r ：i c o ) 九一b l 吃- 七j ，一2 九叱o = 0 式( 2 8 ) 与( 2 - 9 ) 表明，c 中各个码元如果满足由h 所确定的，个线性方程的解， 则c 是一个码字；反之若c 中码元组成了一个码字，则一定满足由日所确定的， 个线性方程。由于生成矩阵g 中每一行