（通信与信息系统专业论文）一种新型级联码的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 自从1 9 9 3 年c ，b e r r o u 等人提出t u r b o 码以来，t u r b o 码逐渐成为编码 界研究的热点。 仿真实验表明，t u r b o 码在信噪比接近香农限的情况下，仍能获得较低 的误码率。当信噪比小于3 0 d b 时，传统的t u r b o 码有很强的纠错能力，随 信噪比增加误码率降低迅速；当信噪比大于3 0d b 后，误码率曲线趋于平 缓，这表明纠错能力随着信噪比增加增长变得缓慢。当以传统t u r b o 码为 信道编码传输信息时，要满足实际的误码率的要求( 例如1 0 1 ) 仍然需很 高的信噪比。众所周知，信噪比的增加会带来能源浪费、信息泄漏等一系 列问题。 为了解决这一问题，可以依据级联码编码理论，用两个或者两个以上短 码构造长码，本文提出一种新型级联码，它有t u r b o 码和b c h 码构成，也 就是以b c h 码为外码对t u 曲。码进行扩展。在级联码中b c h 码利用其纠 正多个随机错误的能力纠正t u r b o 码译码残留的错误。 然后，对级联码的编码器译码器进行软件编程，搭建以t m s 3 2 0 v c 5 4 1 0 为核心的硬件平台，并把级联码编、译码器程序分别下载的各自的d s p 芯 片，这样就能够实现这种新型级联码的硬件实时处理。 实验结果表明这种级联码性能优于传统t u r b o 码，利用这种t u r b o 码能 在较低信噪比条件下实现很低的误码率。 关键词：t u r b o 码：b c h 码；级联码；d s p 哈尔滨：程大学硕士学位论文 a b s t r a c t i n19 9 3 ，c l a u d e b e r r o u ，a l a i ng l a v i e u x a n d p u n y at h i t i m a j s h i m a p u b l i s h e dt h ep a p e rw h i c hf i r s td e s c r i b e dt u r b oc o d e s t u r b oc o d e sh a v eb e e n b e c o m i n gap o p u l a r a r e ao fc o m m u n i c a t i o n sr e s e a r c h 。 s i m u l a t i o n ss h o wt h a tt u r b oc o d e sc o u l da c h i e v el o wb e ra ss n r v e r y c l o s et os h a n n o nl i m i t w h e ns n rb e l o w3 0 d b t r a d i t i o n a lt u r b oc o d e sh a s p o w e r f u le r r o r - c o r r e c t i n gc a p a b i l i t y ；b u tw h e ns n rl a r g e rt h a n3 0 d b ，i t sb e r p e r f o r m a n c e b e c o m ef l a t t l i ss h o w st h a tt h ei n c r e m e n t s p e e d o f e r r o r - c o r r e c t i n gc a p a c i t ys l o w i n gd o w na ss i g n a l t on o i s er a t i o s i n c r e a s i n g w h e nu s i n gt h e s ec o d e st og e tl o wb e r ，f o re x a m p l e10 。8 ，t h e ya l s on e e dah i g h s n r a sw ea l lk n o w , h i g hs n rm a y b r i n g sas e r i e so fp r o b l e m s f o re x a m p l e w a s t i n ge n e r g ya n dl e a k a g eo f i n f o r m a t i o n i no r d e rt os o l v et h i sp r o b l e mw ec a nc o n s t r u c tl o n gc o d e sw i t ht w oo r m o r es h o r tc o d e sb a s eo nc o n c a t e n a t e de n c o d i n gt h e o r y t h i sp a p e rp r e s e n t sa n e wt y p eo fc o n c a t e n a t e dc o d e sw h i c hc o n s i s to ft u r b oc o d ea n db c hc o d e t h a ti st o s a yt u r b o c o d e se x t e n d e dw i t ho u t e rb c hc o d e s i nt h e s e c o n c a t e n a t e dc o d e s ，b c hc o d e st h a tc a r lc o r r e c taf e wr a n d o mb i te r r o r s a r e u s e dt or e c t i f yt h er e s i d u a lb i te r r o r sa f t e rt u r b od e c o d i n g t h e nt h ee n c o d e ra n dd e c o d e ro ft h ec o n c a t e n a t e dc o d e sa r cp r o g r a m m e d t h ep r o g r a m sa r el o a d e dt ot m s 3 2 0 v c 5 4 1 0r e s p e c t i v e l y s oi tc a nr e a l i z et h e r e a lt i m ep r o c e s s i n go f t h ec o n c a t e n a t e dc o d e sb yh a r d w a r e s i m u l a t i o n ss h o wt h a t ：c o n e a t e n a t e dc o d e sb e c o m em o r ea n dm o r e p o w e r f u lt h a nt r a d i t i o n a lt u r b oc o d e sa ss n ri n c r e a s i n g t h e yc a l lr e a l i z eal o w b e ra tr e l a t i v e l yl o ws n r k e yw o r d s ：t u r b oc o d e s ，b c hc o d e s ，c o n c a t e n a t e dc o d e s ，d s p 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出。除文中己注明引用的内容外，本 论文不包含任何其他个人或集体已经公开发表的作品成 果。对本文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 作者( 签字) ：矗：重避 日期：加s 年月j o 日 哈尔滨【程大学硕士学位论文 1 1 课题背景 第1 章绪论 通信的根本任务是有效、可靠地传输信息。要把信源输出的信息快速、 可靠地通过信道传给信宿，一般需要通过信源编码和信道编码来完成。数 字通信系统的模型如图1 il 所示： 图1 1 数字通信系统模型 提高信息传输的可靠性和有效性始终是通信领域研究和追求的目标。 信源编码的作用主要是用信道能传输的符号来代表信源发出的消息，使信 源信息适合在信道中传输，并且，在允许失真范围内用尽可能少的符号来 传送信源信息，提高信息传输的有效性；信道编码主要是增加信号的抗干 扰能力，保证信息传输的可靠性。 1 9 4 8 年，信息论的奠基人c e s h a n n o n 他的开创性论文“通信的数学 理论”中首次阐明了在有噪信道中实现可靠通信的方法，提出了著名的 s h a n n o n 第二定理( 也称有噪信道编码定理) ，具体表述为：对于任何信道， 只要信息传输速率r 不超过信道容量c ，就一定存在一种编码方法，在采 用最大似然译码( m l d ) 时，其误码率可以任意小。 该定理包含两个方面的含义：一是当r o o ，则 使译码误比特率只斗0 的好码一定存在；二是指出为达到这一理论上限需 要采用最大似然译码。在极限情况下”趋向无穷，要求带宽趋向无穷，此时 只要信噪比大于- 1 6 d b ，就可实现高斯自噪声信道下的无误传输。这就是 带宽无限高斯白噪声信道的极限传输能力，称为s h a n n o n 限。该界限是随 哈尔滨工程大学硕士学位论文 机选取编码总体上的平均误码率，由于总体中一定存在一些超过平均性能 的好码，因此这个定理保证存在一些能达到s h a n n o n 限的码。 分析香农信道编码定理可知，s h a n n o n 在导出上式时引用了三个基本条 件： 1 采用随机性编码。 2 编码长度玎斗o o 。 3 采用最大似然译码( m l d ) 简而言之，在信道传输速率r 不超过信道容量c 的条件下，码组无限 长并采用最大似然译码算法时，误码率才能够无穷小。定理证明以随机编 码定理为基础，而且最大似然译码复杂性随码长增加而迅速增加，当编码 长度趋于无穷大时，最大似然译码不可能实现。 1 2 信道编码的构造及t u r b o 码的提出 香农定理仅是一个存在性定理，它并未给出使误码率任意小的有效途 径；当要求的误码率很低时，将被迫采用增加码长的方法，这将导致译码 算法异常复杂，以至于物理不可实现。在过去的几十年内，编码领域中的 研究工作主要沿着两条基本方向发展：一是如何构造码长聆趋于无穷的渐进 好码；另一个是在所能接受的复杂性范围内，如何实现最大似然译码。然 而，从定理提出至今，还没有哪种码能达到香农定理的极限。 长期以来，由于译码复杂性的问题，人们将构造信道编码的重点放在 短码上，寻找一种可译码的结构，使短码具有尽可能大的最小码距；对长 码而言，其码距尽可能接近平均码距。由于高维理论不足，编码研究的思 想多局限于低维短码，它们虽能提供一定的编码增益，但是与编码理论要 求还相差甚远。 为了获得可译的高维长码，1 9 6 6 年f o r n e y 首先提出用两个确定的短码 来构造长码的串联式级联码【2 】，希望通过对外码的译码纠正内码尚未纠正的 错误。这一革新思想的引入，给信道编码，特别是长码的性能带来了很大 程度的改善。 哈尔滨工程大学硕士学位论文 1 9 9 3 年的国际会议( i c c 9 3 ) 上p l ，c b e r r o u 和a g l a v i e u x 两位学 者首次提出了一种新型信道编码方案一- - t u r b o 码，由于它很好地应用了香 农信道编码定理中随机性编码的条件，从而获得了几乎接近香农极限的译 码性能。由于自从s h a n n o n 于1 9 4 8 年提出信息论以来，人们虽然不懈地向 逼近s h a n n o n 限努力，但是所得到结果还是与之相距甚远，因此t u r b o 码 一经提出，立即受到了世界范围内信息和编码理论界的关注，并成为该领 域近几年来研究的热点。t u r b o 码与以往所有信道编码不同之处在于它通过 一个交织器的作用，达到接近随机编码的目的，并且使等效分组长度增大。 此外，它所采用的迭代译码策略，使得译码复杂性大大降低。它采用两个 子译码器通过交换称为边信息的辅助信息，相互支持，从而提高了译码性 能。边信息的交换是在迭代译码的过程中实现的，前一次迭代产生的边信 息经交换后将作为下一次迭代的先验信息。t u r b o 码被称为2 l 世纪的纠错 编码，具有接近s h a n n o n 限的优越性能，它的出现是信道编码研究中的一 项重大突破。 1 3t u r b o 码研究的现状 结合最新的研究，可以看出对t u r b o 码的研究主要集中在以下三方面： i 、于t u r b o 码本身的研究是前一段时间的主要方向，主要涉及到t u r b o 码理论的研究，试图通过理论来解释其优异性能的原因及其分析和构造的 理论依据，虽然取得了一些成果，但进展不大。大多数的研究集中在算法 的改进，包括分量码的选择、交织器的设计、译码算法的改进、终止技术 等各个环节，取得大量成果，为实现在其他领域的应用打下了坚实的基础。 2 、于t u r b o 码技术的逐渐成熟，最新的研究大多数集中在t u r b o 码和 其他技术结合的应用上，并且取得了很大进展。目前这方面的研究主要集 中在t u r b o 码和其他纠错码的级联码，t u r b o 码和调制技术的结合( 即t t c m 技术) ，t u r b o 码均衡技术，t u r b o 码多用户检测技术等领域。 3 、任何技术的发展最终要应用到实际中才有价值。由于t u r b o 码延迟 问题的限制，对其应用领域的研究最先集中在对时延不敏感的场合，如卫 哈尔滨工程大学硕十导位论文 星通信和一些非实时的场合。随着硬件技术的发展，t u r b o 码在实时领域中 的应用成为可能，t u r b o 码已经从仿真开始走向应用，许多芯片制造商开发 出了专用的t u r b o 码编、译码器，如x i l i n x 的f p g a 实现方案和t i 的 t m s 3 2 0 c 6 2 0 1 均可满足高速传输的要求。值得一提的是t u r b o 码已经成为第 三代移动通信系统( 3 g ) 高速数据的纠错技术之一。但t u r b o 码在衰落信 道中的应用还有很多问题需要解决，是目前研究的热点。 对于以上几方面，人们研究均很活跃，i e e e 等一些重大的国际性学术 会议和著名学术期刊均发表了大量有关t u r b o 码的研究成果，有关t u r b o 码的专题研讨会也经常在一些国家举行，但是总的看来，研究仍处于初级 阶段。此外，值得一提的是，欧洲数字广播标准中已确定采用o f d m 和t u r b o 码，1 9 9 6 年完成了系统模拟，现在瑞典等国正在进行a s i c 的设计和验证。 在硬件实现方面，t u r b o 码的试验芯片已经开发出来，法国、澳大利亚、美 国的3 家公司均宣称开发出了相应的产品。 对t u r b o 码的研究，目前主要存在以下几个亟待解决的关键问题： 1 、t u r b o 码的编码机理：t u r b o 码的产生是实践的结果，没有确定的 设计准则，这对t u r b o 码的设计和优化带来了一定的困难。因此，有必要 对t u r b o 码的编码机理进行研究，以便为好码的构成提供指导。要完成t u r b o 码编码机理的研究，有待于对t u r b o 码的正确建模，这是极其吸引人又非常 困难的问题。 2 、t u r b o 码交织方法的选择：交织器对t u r b o 码的性能有很大的影响， 选择恰当的交织器，能使t u r b o 码的性能得到充分发挥。什么是最佳的交 织方法，一直没有定论，这是研究t u r b o 码需要解决的一个关键问题。 3 、t u r b o 码的译码算法：目前，t u r b o 码的译码算法主要是m a p 算法 和s o v a 算法。m a p 算法性能很好，但复杂度太高，在实际通信系统的应用 中受到限制：s o v a 算法较简单，性能比m a p 算法差，且译码性能不是很稳 定。而且这两种算法都没有采用快速算法。能否设计简单可行、性能较佳 的译码算法，将决定t u r b o 码的应用前景。 4 、t u r b o 码的时延：t u r b o 码采用了级联译码和迭代译码，从而具有 了优异的纠错性能，但是同时这也大大增加了译码的时延，妨碍了它在要 4 哈尔滨t 程大学硕士学位论文 求实时场合的应用。如何正确估量t u r b o 码时延的影响，以确定最佳编、译 码方法，还有待于进一步研究。 5 、t u r b o 码的应用：对t u r b o 码研究的最终目的是将这种技术应用到 实际中，特别是t u r b o 码被3 g 标准采纳后，t u r b o 码的应用更成为急需解 决的问题。为了减小译码延迟：一方面改进译码算法，降低译码算法的复 杂度，从而降低译码时延；另一方面进一步提高硬件的处理速度，减小处 理延迟。 上面提到了t u r b o 码的研究方面存在的几个问题，也是t u r b o 码研究 中的几个难点。t u r b o 码优异的纠错性能和先进的编、译码方法，使其具有 极其广阔的应用前景。因此，t u r b o 码的出现可望为编码理论与实践带来一 场革命，在通信领域，人们对t u r b o 码及其应用的研究必将日益踊跃。 1 4 本文的主要工作 众所周知，t u r b o 码具有优异的纠错性能，但是大量的仿真试验表明： 利用传统的t u r b o 码来实现较低误码率仍需要较高的信噪比，信噪比的增 加必然会带来能源浪费、信息泄漏等一系列问题，不利于这种新型信道编 码技术的实用化。 掣一唧紫码 i 廿鬻编l + 信道- i | n 嚣译b 唧警码i 驾 级联码编码器级联码译码器 图1 2 级联码差错控制系统 为进一步提高t u r b o 码的纠错能力，使其能在较低信噪比条件保持较强 的纠错能力，本文依据t u r b o 码和级联编码理论，提出一种由传统t u r b o 码和b c h 码( 纠正多个随机错误的循环码) 串联而构成的新型级联码( 如 图1 2 所示) 。本文对这种新型级联码的编码器构造、译码算法进行了深入 细致地分析，在此基础上利用m a t l a b 软件对其性能进行仿真试验，并绘制 出该级联码的误码率性能曲线，然后利用c c s 软件结合e v m 仿真板进行性 哈尔滨工程大学硕十学位论文 能仿真，最后利用t m s 3 2 0 v c 5 4 1 0 来实现对这种新型级联码的编译码。论文 工作的主体可分为以下几部分： 第一、用m a t l a b 软件对这种新型t u r b o 码进行性能仿真：在这部分主 要是利用m a t l a b 对采用不同1 3 c h 码级联的情况进行仿真，并对他们进行性 能分析，从众多级联码中挑选一种性能优异的级联码，最后以该级联码为 研究对象，进行详细地分析。 第二、利用c c s 进行软件仿真：这部分工作主要是把级联码的编、译码 器由m 文件形式改用c 语言和汇编语言程序表达出来，并将其下载到计算 机和e v m 板上进行性能仿真，其目的是生成 o u t 文件为t m s 3 2 0 v c 5 4 1 0 做 软件的准备工作。 第三、统硬件设计：这部分主要是进行t m s 3 2 0 v c 5 4 1 0 的硬件外围电路、 编译码器之间的通信、输入输出设备以及电源的设计，这部分工作完成硬 件平台的搭建，为系统做好硬件准备工作。 第四、硬件系统的调试：硬件系统的调试是课题的最后一步，也是最关 键最难实现的一步。在硬件系统调试过程中把第二、三两部分的成果结合 起来，对整个系统进行综合调试。 哈尔滨丁：程大学硕十学位论文 第2 章级联码、b c h 码基本原理 2 1 级联码的基本原理 信道编码定理指出，随着码长n 的增加，译码错误概率按指数接近于零。 因此，为了降低误码率就应该用长码。但是，随着码长的增加，在一个码 组中要求纠正的错误的数目相应增加，译码器的复杂性和计算量也相应增 加以致难以实现。 为了解决纠错性能与译码设备复杂性之间的矛盾，1 9 6 6 年f o r n e y 首先 提出级联码的概念，它利用两个确定的短码串联起来构造长码，把编制长 码的过程分几级完成，希望通过对外码的译码纠正内码尚未纠正的错误， 达到进一步减小误码率的目的。 从本质上讲，级联码是乘积码的特殊情况，通常也由两级子码组成 2 】， 不同的是这两个予码取自不同的域并串联而成。级联码有极强的纠正突发 错误和随机错误的能力，利用级联码的构造方法，能达到信道编码定理所 给出的码限，也就是能构造出渐进好码。 i 。 蚧? 端2 7 嚣协情道_ 2 7 篇- ：? 篇| 毂 n n , k k 级联每磊码器 n n k k 级联码译西嘉 图2 1 级联码差错控制系统 如图2 1 所示为一个应用两级级联码的差错控制系统。由此图可见， 级联码由内码e 和外码c 。组成，内码c 是g f ( 2 。) 上的一个 n ，k 】码，外码 e 是g f ( 2 ) 上的 ，k 】码，并按以下方法编码： ( 1 ) 把k k 个二进制信息元，划分成k 段，每段有k 个码元。 ( 2 ) 把每组有足个信息元的段，看成g f ( 2 。) 上的一个符号( 元 素) 。将k 个符号按外码c 的编码规则编成一个码字，码长为，有k 个 哈尔滨，l ：程大学硕十学位论文 信息符号，最小距离为d 。，码率r 。= k n 。 ( 3 ) 再把c 0 外码的每一个符号，看成是k 个二迸制码元的信息组， 输入内码c 。编码器，得到内码的一个码字。它的码长为n ，有，j k 个校验 元，最小距离为d ，码率r ，= k 门，由此得到m ，k 】内码的个码字序列。 故共有n n 个二进制码元、戤个信息元，组成了 m ，戤，以d f 级联码的码 字。 可知两级级联码是一个【m ，触，d o d 。】二进制线性分组码，码率 r 。= r 。r 。级联码的译码采用分级处理：先按内码e 的规则译码，得到k 个 有个码元组成的符号后，再送入外译码器，按外码c 。的规则译码，最后 送出七个信息符号，每个符号有足个二进制信息元。所以，最后由外译码 器输出的是已经过纠错的k k 个信息元。 当信道产生少量随机错误时，通过内码c ，就可以纠正；当产生较长的 突发错误或随机错误较多，以至超过c ，码的纠错能力，则内译码器将会产 生错误译码，输出的码字有多个错误。但这仅相当于外码c 。的几个符号错 误，外译码器能比较容易地纠正。从这里可以看出，级联码用来纠正组合 信道错误是非常有效的。 在级联码的实现中，内码既可以用作纠错，也可以用作检错。一般情 况下，级联码用在干扰比较严重的组合信道中，内码中的某些码字内错误 很多，往往超过内码的纠错能力。所以，通常内码仅用来纠正少量错误， 而大部分能力用来检错，指出错误的位置，纠错任务则由外码译码器完成。 这样两级译码的结果，使得内、外译码器均较简单：内译码器主要是检错 误，而外译码器主要是纠正错误。这种译码方法使得译码器的复杂性和计 算量大大低于有相同参数的其他单级分组码。 从本质上讲级联码其实是一种直接序列扩频系统，它把每一个外码的 码元，用码长为7 1 ，的内码码字填充，从而使得系统的带宽扩展，提高了系 统的抗干扰能力。 级联码设备的复杂性主要决定于译码器，可以证明其复杂性并不随码 长玎，= n n 的增长指数增加，而是随玎，以小的幂次增加。最坏情况下，其复 杂性和胛：成正比；如果不用广义最小距离译码，则与n ：成正比。因此，这 哈尔滨工程大学硕士学位论文 比单级译码时的复杂性随码长指数增加要好的多。 1 9 7 1 年乔勃洛夫首先讨论了级联码的渐近性，指出一定存在一类级联 码，当月保持一定，胛一时能做到d n 0 ，并给出了以下渐近性能限： 鲁震骑救一亭) 日文t 一， c z 一， 该限称为乔勃洛夫( z r ) 限，它是在外码用最大距离可分码时得到的。式 中 h 2 ( x ) = 一x l o g2x 一( 1 一x ) l 0 9 2 ( 1 一x ) ( 2 2 ) 是熵函数，r 是级联码的码率，r 是内码的码率。f o r n e y 证明应用级联码 通信系统，其误码率p 能达到 p e - 幔( 8 ) ( 2 3 ) 式中，是级联码的码长；r 是级联码的码率；e 。( 月) 称为级联指数，当 r 0 。由此式看出：随着行_ o o ，p - + 0 。但是由于t ( 只) 通常小于e ( r ) ( s h a n n o n 码误差指数) ，这说明在应用级联码后，在同样 码率下要达到同样的性能，级联码的码长比不用级联码的s h a n n o n 码要长。 通常以 纵耻器 a ， 来衡量级联码的效率。如果仉( r ) 为0 1 ，则说明级联码必须长l o 倍，才 能达到未级联时的性能，这就是级联码所付出的代价。 2 2b g h 码的编译码方法 1 9 5 9 年由h o c q u e n g h e m ，1 9 6 0 年由b o s e 和r a y c h a u d h u r i 分别提出 了纠正多个随机错误的循环码一b c h 码的构造方法。b c h 码是迄今为止所发 现的一类很好的线性纠错码类，其纠错能力很强，特别是在中短码长下， 其性能很接近于理论值，并且构造方便，编码简单。特别是它具有严格的 代数结构，因此它在编码理论中起着重要作用。b c h 码是迄今为止研究的最 为详尽，分析的最为透彻，取得的成果也是最多的码类之一。 9 哈尔滨工程大学硕士学位论文 1 9 6 0 年p e t e r s o n 从理论上解决了二迸制b c h 码的译码算法，奠定了 b c h 码译码的理论基础。稍后，g o r e n s t e n 和z i e r l e r 把它推广到多进制。 1 9 6 6 年b e r l e k a m p 利用迭代算法译b c h 码，从而大大加快了译码速度，从 实际上解决了b c h 码译码问题。由于b c h 码性能优良，结构简单，编译码 设备也不太复杂，使得它在实际使用中受到工程技术人员的欢迎，是目前 用的最为广泛的码类之一。 2 2 1b c h 码定义 b e h 码就是纠正多个随机错误的循环码，可以用生成多项式g ( x ) 的根 描述： 给定任一有限域g f ( q ) 及其扩展域g f ( q “) ，其中q 是素数或素数的幂， m 为某一正整数。若码元取自g f ( q ) 上的一循环码，其生成多项式g ( x ) 的根 集合r 中含有以下万一1 个连续的根： r 口帆，口”。州，口“。+ 5 2 ( 2 5 ) 时，则由g ( x ) 生成的循环码称为q 进制b c h 码。 其中，口g f ( q ”) 是域中的n 级元素，口“g f ( q ”) ( 0 fs 占一2 ) ， m 。是任意整数，但对于常见的情况= 0 或1 。若m 。= l ，则称为狭义b c h 码。 设所。( x ) 和8 ，分别为口“( f - o ，l 2 ，占一2 ) 元素的最小多项式和级， 则b c h 码的生成多项式和码长分别是： g ( x ) = l c m ( m o ( x ) ，m l ( x ) ，m 5 2 ( x ) ) n = l c m ( e o ，e 】，e ) ( 2 - 6 ) 如果生成多项式g ( x ) 的根中，有一个g f ( q ”) 中的本原域元素，则 ”= q 一1 ，称这种码长n = q 一l 的b c h 码为本原b c h 码；否则，称为非本 原b e h 码。g f ( q ) 中元素的级一定是g ”一1 的因子，所以非本原b e h 码的 码长也一定是盯“一l 的因子。 2 2 2b c h 码编码原理 循环码是一种线性代数分组码，记为 n ，k 码，其中”为码长，k 为信 0 哈尔滨工程大学硕十学位论文 息码元数。循环码的特点是：若( c n - i c c c 。) 是一个码字，则它的循环移 位c n _ 2 c c o c ) 也是一个码字a 一个 ，k 】循环码，共有2 个码字，从中取出一个前k 一1 位都是o 的码 字， 以g ( x ) 表示，它的次数为 一1 一( 七一1 ) = n k 。则 g ( x ) ，x g ( x ) ，x 2 9 ( x ) ，x k - i g ( x ) 都是码字，且k 个码字彼此独立，因此 可以作为生成矩阵【g 】的k 行。 g - 一经确定，码也就确定下来了，编码问 题也就解决了。因此，称g ( x ) 为生成多项式。 知道生成多项式g ( x ) 后，生成矩阵【g 可以表示如下： 【g ( x ) = x 2 9 ( x ) x g ( x ) g ( x ) ( 2 - 7 ) 因此，循环码c ( z ) 可以写成 c ( x ) = 朋m m i m o 】 g ( x ) 】 ( 2 - 8 ) 式中 m m h m ，m o 】为k 位信息元矩阵，变换上式可以得到 c ( x ) = ，托 一l x 2 叫g ( x ) + m i 一2 x 。- 2 9 ( x ) + + m 1 x g , ( x ) + m o g ( x ) = ( 坍女一1 x 。- 。+ m 一2 x 。一2 + + m l x + m o ) g ( x ) = ，行( x ) g ( x ) ( 2 9 ) 式中m ( x ) 为信息码组多项式。由式( 2 9 ) 可以看出，所有用【g ( x ) 】生成的 码字c ( x ) 都是生成多项式g ( x ) 的倍式。也就是说，凡是一个码字多项式一 定能被g ( x ) 除尽。反之，能被g ( x ) 除尽的次数不大于( n 一1 ) 次的多项式， 也一定是码字多项式。由此可以得到b c h 码编码方法如下： 首先，将次数小于( k 一1 ) 次的信息码组多项式m ( x ) 乘以x ”，得到 x n - k m ( x ) ，其次数小于等于( 1 1 1 ) 次。然后，用生成多项式g ( x ) 去除 x n - k m ( x ) ，得到的余式为r ( x ) ，它的次数小于g ( x ) 的次数( h k ) ，把此余 式的系数作为监督元附加在信息码组后面，就得到一个必能被g ( x ) 除尽的 多项式，且它必是一个码多项式，运算过程为 力力( ( g g 一 一 x x 哈尔滨t 程大学硕士学位论文 1 x - r 矿n ( x ) 吲m 磊 x n - kr e ( x ) = g ( x ) g ( x ) + ，( x ) 式中g ( x ) 为商式，r ( x ) 为余式。则码字多项式为 f ( x ) = z ”。脚( 曲+ ，( 曲= 9 0 ) 9 0 ) 而余式可以写成 r ( x ) = x n - k m ( x ) 模g ( x ) ( 2 1 0 ) ( 2 一1 1 ) ( 2 1 2 ) ( 2 1 3 ) 2 2 3b c h 码的译码算法 b c h 码是一种线性码，它的译码步骤同样分为三步进行：第一步是由接 收到的r ( x ) 计算出伴随式s ：第二步由伴随式找出错误图样雪( x ) ；第三步 由r ( x ) 一e ( x ) 得到最可能发送的码字e ( x ) ，完成译码。 对二进制b c h 码q = 2 ，设g f ( 2 ) 上的阮k ，d b c h 码的根为 口“，口“，口册o “，则其生成多项式为： g ( x ) = ( x 一掰) ( x a 十1 ) ( x a m o + 2 t - i ) d = 2 t + l( 2 - 1 4 ) a g f ( 2 “) 为r l 级域元素。发送的码字c ( x ) = q ( x ) g ( x ) ，接收的n 重为 r ( x ) = c ( x ) + e ( x ) 。设错误图样为： e ( x ) = e n - i x ”q + e n - 2 x ”一2 + + e i 工+ e o ( 2 1 5 ) 若信道产生r 个错误，则 r e ( x ) = x + x l l 。- + + x4 - = y x 7 - ( 2 1 6 ) 百 x 称为错误位置数，说明错误发生在r ( x ) 中的第n 一，( 石”1 的系数算第 位) 位。如果r ( x ) 中有，个错误，则e ( x ) 共有，项x l i ，i = 1 , 2 ，7 。 由伴随式定义可知： s 7 ：h r ：h e 7 哈尔滨工程大学硕士学位论文 位“) ”1 以。“) ” r a ”。) n - 2 r 口“) n - 2 缸“”2 1 ) ”1 “。1 ) ”2 s 。= r ( a ”) = e ( c t 。) j 。，、+ 】= r ( a ”。+ 1 ) = e ( a ”+ 1 ) 口“” “啊j + i s 。十2 r l = r ”2 。1 ) = e ( a “。1 ) ( 2 1 7 ) 式中 r s ，= 叫= r ( a 。) j = m 。，m 。+ 1 ，m 。+ 2 t 一1 ( 2 一1 8 ) i = l 若令x ，= 口“，则上式可写成 o = ( 口。) “= r ( a 。) = x ? j = 脚。，m 。+ 1 ，m 。+ 2 t 一1 ( 2 1 9 ) j - l i = l 通常取m 。= 1 ，则 s l = x 1 + x 2 + + x ，= x 女 = i s 2 = x ? + x ；+ + x ? = x ：( 2 2 0 ) ； 七= 1 屯= x ? 7 + x ；7 + + x ? = “2 上式中j 称为x 的加衩幂和对称函数，我们的目的是要根据2 t 个方程 求出r 个未知数x ，为此引入错误位置多项式 盯( x ) = ( 1 一x l x ) 0 一x 2 x ) ( 1 一x ，x ) ( 2 - 2 1 ) 若第七个错误位置x = x i ，则盯( x ：1 ) = o 。因此，求错误位嚣就是求解位置 0o