（电路与系统专业论文）fire码译码算法研究及其在gsm中的应用.pdf

m st h e s i so f 2 0 l o u n i v e r s i t yc o d e ：1 0 2 6 9 r e g i s t e rn u m b e r ：5 10 712 0 2 0 4 8 ea s tc h i n an o r m a l u n i v e r s i t y r e s e a r c ho nf i r ec o d e d e c o d i n g a l g o r i t h ma n d i t sa p p l i c a t i o no ngs m m a j o r ： s t u d e n tn a m e ：s h u qi nx i a o 一。i 。- 。_ _ - - - - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ - - - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - - - _ _ _ - 一 a p r i l2 0 1 0 、 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文往y e 褐译桷算 爻硒凌风去在白s m 中僦脚， 是在华东师范大学攻读碌博士( 请勾选) 学位期间，在导师的指导下进行的研究工作 及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名：茎数墨日期：如阳年上月2 6 日 华东师范大学学位论文著作权使用声明 耳坨钓浮矛马算i 幺研锵经白s m 中仇勉龋系本人在华东师范大学攻读 学位期间在导师指导下完成的硕矽博士( 请勾选) 学位论文，本论文的研究成果归华东 师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管 部门和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允 许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入 全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部或“涉密 学位论文木， 于年月日解密，解密后适用上述授权。 ( 、 o 不保密，适用上述授权。 导师签名本人签名篮造丑鉴本人签名且趋叉签 如f d 年f 月2 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 岜邋茎硕士学位论文答辩委员会成员名单 姓名职称单位备注 薛燕陵教授华东师范大学主席 刘一清高级工程师华东师范大学 王蔚生副研究员华东师范大学 摘要 f i r e 码是一种用于检测和纠正突发错误的循环码。由于这种纠错码可以根据 不同的要求很方便地设计所需要的码型，且译码很简单，因而它被广泛运用于计 算机系统和通信系统的突发错误纠错，例如：磁盘纠错和g s m 的差错控制系统。 在g s m 控制信道中，f i r e 码通常作为信道外编码，与内编码卷积码联合使用， 可以有效地捕捉和纠正遗漏的组误差。 f i r e 码的生成多项式的一般形式为g ( x ) = p ( x ) ( 一1 ) 。其中，p ( x ) 是定义在 g f ( 2 ) 上的一个m 次既约多项式，根的阶数e = 2 ”一l ，且c 和e 互素。f i r e 码的 码长疗应该是e 和c 的最小公倍数，即刀= l c m ( e ，c ) ，监督位个数，= m + c ，信 息位个数k = 胛一m c 。传统的译码方案能运用f i r e 纠正一个码字内的一处长度 不大于b 和检测长度不大于d ( d 6 ) 的任何突发错误，其中c b + d 一1 且b 柳。 本文拟议一种用于f i r e 码译码的新方案，该译码方案能够纠正一个码字中的 两处突发错误，一处长度不大于b 的主突发错误和一处长度不大于厂的次突发错 误( f r 2 一b ) 。在充分阐述了该译码算法原理的基础上，以( 2 2 4 ，1 8 4 ) 缩 短f i r e 码为例描述了译码器的设计方法，并在g s m 仿真平台上测试了系统的误 码特性。仿真试验证明新译码方案的使用明显降低了系统的误码率。该译码方案 能够充分发挥f i r e 码的纠突发错误能力。 关键字：f i r e 码；突发错误；译码算法 a b s t r a c t f i r ec o d ei sak i n do fc y c l i cc o d e ，w h i c hi su s e dt od e t e c ta n dc o r r e c tb u r s te r r o r s f o rt h i sk i n do fe r r o r - c o r r e c t i n gc o d e ，i ti se a s yt od e s i g nd i f f e r e n tc o d ea c c o r d i n gt o d i f f e r e n tr e q u i r e m e n t s ，a n dt h ed e c o d i n gi sv e r ys i m p l e ，s oi ti sw i d e l yu s e dt oc o r r e c t b u r s te r r o r si n c o m p u t e rs y s t e m s a n dc o m m u n i c a t i o n s y s t e m s ，s u c h a s e r r o r - c o r r e c t i n go fd i s ka n de r r o rc o n t r o ls y s t e mi ng s m f i r ec o d eo f t e nu s e da s o u t e rc h a n n e lc o d i n g ，c o m b i n e dw i t ht h ec o n v o l u t i o nc o d ea si n n e rc o d s ，c a n e f f e c t i v e l yc a p t u r ea n dc o r r e c tt h eg a n g e de r r o rm i s s e do u t af i r ec o d eh a sag e n e r a t o rp o l y n o m i a l so ft h ef o r mg ( x ) = p ( x ) ( x 。一1 ) ， w h e r e p ( x ) i sa ni r r e d u c i b l ep o l y n o m i a l so fd e g r e em a n dp e r i o ded e f i n e do ng f ( 2 ) ， ca n dea r er e l a t i v e l yp r i m e t h en u m b e ro ft h ec o d e w o r db i t s 刀i se q u a lt ot h el e a s t c o m m o nm u l t i p l eo fca n d e ，t h a t st os a yn = l c m ( c ，p ) ，t h en u m b e ro fs u p e r v i s i o n b i t si s r = 脚+ c ，a n dt h en u m b e ro fi n f o r m a t i o nb i t si sk = ”一m c t h et r a d i t i o n a l d e c o d i n gm e t h o dc a nu s ef i r ec o d et oc o r r e c tab u r s te r r o rw i t hal e n g t ho fn o tm o r e t h a nb ，a n dd e t e c tab u r s te r r o rw i t hal e n g t ho fn o tm o r et h a nd ( d 6 ) i no n e c o d e w o r d ，w h e r ec b + d 一1a n db m t h i sp a p e rp r o p o s e dan e wm e t h o do fd e c o d i n gf i r ec o d e ，w h i c hc a nc o r r e c tt w o b u r s te r r o r si no n ec o d e w o r d ，am a i nb u r se r r o ri nal e n g t ho fn o tm o r et h a nbb i t sa n d as u b b u r s te r r o ri nal e n g t ho fn o tm o r et h a nfb i t s ( 厂r 2 - b ) a f t e ra ne x p o s i t i o n o ft h ed e c o d i n g a l g o r i t h mh a sb e e nm a d e ，t h e ( 2 2 4 ，18 4 ) s h o r t e n e df i r e c o d ei s d e s c r i b e da b o v ea sa ne x a m p l ef o rt h ed e s i g nm e t h o do ft h ed e c o d e r ，a n dt h es y s t e m b e rp e r f o r m a n c eh a sb e e nt e s t e do nt h eg s ms i m u l a t i o np l a t f o r m t h es i m u l a t i o n p r o g r a m ss h o w e dt h a tt h en e wd e c o d i n gs y s t e ms i g n i f i c a n t l yr e d u c e st h ee r r o rr a t e s t h ed e c o d i n gp r o g r a mc a ng i v ef u l lp l a yt ot h eb u r s t e r r o r - c o r r e c t i n gc a p a b i l i t yo f f i r ec o d e k e yw o r d s ：f i r ec o d e ，b u r s te r r o r , d e c o d i n ga l g o r i t h m 目录 摘要兽i a b s t r a c t i i 第一章引言1 1 1 通信系统基本模型1 1 2 差错控制系统与g s m 前向纠错编码2 1 2 1 差错控制系统2 1 2 2g s m 的前向纠错编码3 1 3f i r e 码的应用与译码方法研究现状3 1 4 主要工作及论文组织4 第二章纠错编码理论与循环码编译码系统5 2 1 纠错编码理论。5 2 1 1 纠错编码的基本概念5 2 1 2 纠错码分类6 2 1 3 纠错码的数学理论基础7 2 2 循环码的表述1 0 2 2 1 循环码的多项式表述10 2 2 2 循环码的矩阵表述1 l 2 3 循环码的编码1 2 2 3 1 编码原理1 2 2 3 2 多项式乘法电路l3 2 3 3 多项式除法电路1 4 2 3 4 编码实现电路1 5 2 4 循环码的译码16 2 4 1 循环码通用译码( 梅吉特译码) 1 7 2 4 2 捕错译码18 2 5 缩短循环码及其译码。2 l 2 6 本章小结2 2 第三章纠突发错误循环码及f i r e 码原理2 3 3 1 纠突发错误循环码2 3 3 1 1 突发错误的描述2 3 3 1 2 基本码限2 4 3 2f i r e 码2 6 3 2 1f i r e 码的编码。2 8 3 2 2f i r e 码的一般译码3 0 3 2 3f i r e 码的快速译码3 3 3 3 本章小结3 7 第四章改进的f i r e 码译码方案。3 8 4 1 译码基本原理3 8 4 2 建立校正予查询表4 0 4 3 译码算法流程4 l 4 4 算法仿真4 3 4 4 1 算法仿真代码4 3 4 4 2 算法仿真环境4 7 4 4 3 仿真结果4 8 4 5 本章小结5 4 第五章结论与展望5 5 5 1 全文总结：5 5 5 2 下一步工作展望5 5 参考文献：。5 7 致谢6 0 攻读硕士期间的研究成果6 l i v 1 1 通信系统基本模型 第一章引言 通信系统，即信息的传输系统，如电话、电报、电视、遥控和导航系统等。 实际的通信系统虽然形式和用途都各不相同，但是本质都是相同的。为了便于研 究信息传输和处理的共同规律，将各种通信系统中的共有特征提取出来，概括成 一个通信系统的基本模型 1 ，如图1 - 1 所示。 图1 - 1 通信系统的基本模型 信源产生需要发送的信息，信息可以是比特、字或者码字符号等等。信源编 码的目的有两个：一方面，将不同的信息符号转变成统一格式的信息序列，如二 进制序列，易于信道的传输：另一方面，除去信源中的冗余，使其以最小冗余度 进行传输。信道中引入的干扰会导致接收信号发生错误。信道编码的目的就是在 发送的信息序列中有意的引入一些冗余，以便使信道引入的差错最小化。调制的 目的有两个：一是将信道编码器输出的数据转换成适合信道传输的信号；二是提 高信道的频带利用率，即将多个数字比特映射到一个调制波形上，如多进制q a m 等。信道可以理解为传输或者存储信息的媒介。在实际的信道中主要存在两类约 束，即热噪声和信道的带宽。对于无线信道而言，还存在信号的多径传播与衰落。 这些因素都会对传输的信号产生一定程度的影响。在接收端，译码器利用冗余符 号以及它们与信息符号的关系来纠正信道错误。当纠错编码用于检错时，可以把 它的译码器看成是对接受信息重新编码的编码器，并检测生成的冗余符号与接受 的冗余符号是否相同。 1 2 差错控制系统与g s m 前向纠错编码 1 2 1 差错控制系统 由于信号在传输过程必定存在干扰，致使数字通信过程中将不可避免地会发 生差错。通信系统必须具备检测差错的能力，并采取措施纠正之，使差错控制在 尽可能小的范围内，这就是差错控制系统的功用。 信道中的干扰一般可以分为两种：一是随机噪声，它主要来源于设备的热噪 声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主要噪声；二是脉冲干 扰，它的特点是突发出现，主要来源于雷电、通电、开关、负荷突变或设备故障 等。 一 随机噪声所产生的差错是随机的，差错的出现互不相关，彼此独立。产生随 机错误的信道一般称为随机信道或无记忆信道。而脉冲干扰可以使一大串数字发 生错误，这一错误的出现往往会影响到后面的一串数字，错误之间产生了相关性， 这种产生突发错误的信道称为突发信道或有记忆信道。一般来说，实际信道中的 错误往往不是一种形式，可能是多种形式并存，这种并存错误的信道称为组合信 道或混合信道e 2 。 对于差错控制系统，它的纠( 检) 错误的工作方式一般可以分为以下三种： 前向纠错、反馈重传纠错和混合纠错方式。 ( 1 ) 前向纠错。前向纠错也称为自动纠错。差错控制系统只包含信道编码 器和译码器。信道编码器将发送的数字信息按照一定的数学关系构成具有一定纠 错能力的码组。若传输过程中出现差错，且错误个数在该码的能纠错范围内，接 收端的译码器根据编码规则进行解码，并自动纠正错误。把这种能够实现自动纠 错的编码称为纠错码。由于这种纠错方式不需要反馈，故称为前向纠错。该纠错 方式要求码型和信道匹配。 ( 2 ) 反馈重传纠错。利用检错码以发现传输中带来的差错，同时在发现差 错以后通过反向信道通知发信端重新传输相应的一组数字，以此来提高传输的准 确性。根据重传控制方法的不同，反馈重传法还可以分成若干种实现方式。其中 最简单的一种称为等待重传方式。采用这种方式时，发送端每发送一组数字就停 下来等待接收端的回答。这时信道译码器如未发现差错，便通过接收重传控制器 和反向信道向发送端发送反馈信息，表示已经接收到正确的信号。发送端接收到 2 接收端的反馈信息后，通过发信端重传控制器控制信源传输下一组数字，否则信 源会重新传输原先那组数字。 ( 3 ) 混合纠错。反馈重传纠错和前向纠错相结合的纠错工作方式称为混合 纠错。在信道干扰较大时，单用反馈重传会因不断重传而使消息的传输速率下降 过多，而仅用前向纠错又不能保证足够的准确性。此法所用的信道编码是一种既 能纠正部分差错又能发现大部分差错的码。信道译码器首先纠正那些可以纠正的 差错，只对那些4 能纠正但能发现的差错才要求重传，这会大大降低重传的次数。 1 2 2g s m 的前向纠错编码 g s m 是目前使用最广泛的移动通信系统，也是信道编码最重要的应用之一。 g s m 中使用的编码方式有：奇偶校验码、卷积码、纠错循环码( f i r e 码) 。奇偶 校验码是普遍使用的最简单的检测误码方法。卷积码主要用于纠错，当解调器采 用最大似然估计方法时，可以产生十分有效的纠错效果。f i r e 码主要用于检测 和纠正突发错误，通常与卷积码混合使用，用于捕捉和纠正遗漏的突发错误。f i r e 码是本文的主要研究对象。 1 3f i r e 码的应用与译码方法研究现状 f i r e 码是最早也是最大的一类用分析方法构造出的纠突发错误的二进制循 环码【3 】。由于可以根据不同的要求很方便地设计所需要的码，译码也很简单。 因此，它被广泛运用于计算机系统和通信系统的突发错误纠错，例如：磁盘纠错 和g s m 的差错控制系统。g s m 系统中的一些控制信道如慢速随路控制信道 ( s a c c h ) 、快速随路控制信道( f a c c h ) 、广播控制信道( b c c h ) 、寻呼信道 ( p c h ) 、准许接入信道( a g c h ) 和独立专用控制信道( s d c c h ) 使用截短的 循环码f i r e 码来纠正突发错误。 f i r e 码是一种用于纠正突发错误的循环码，它的生成多项式为 g ( x ) = p ( x ) o 。一1 ) ，其中p ( 是定义在g f ( 2 ) 上的一个朋次既约多项式，根的 阶数e = 2 ”一l ，且c 不能被g 除尽。f i r e 码的码长玎应该是e 和c 的最小公倍数， 监督位个数，= m + c ，信息位个数后= n 一所一c 。若该f i r e 码的最小码距为d ， 则它能够纠正p 处突发错误 4 ，且p ( d 一1 ) 2 。p 处突发错误中最长的错误 图案不能超过b ，而且错误图案的总长度h 应该满足r i e g e r 界，即 h ( 2 b l + m ) 2 ，其中b = m i n ( ( c + 1 ) 2 ，行) 。 3 自1 9 5 9 年p h i l i pf i r e 提出该纠错码以来，国内外曾有多位学者致力于它的 解码算法的研究。p e t e r s o n 于1 9 7 2 年提出了一种基于捕错译码方法的一般译码 器 5 】，硬件结构简单但是译码速度不够快。c h i e n 于19 6 9 年提出了一种基于中 国剩余定理的快速译码器【6 】，在译码速度上比前者更快。陈大有于1 9 8 0 年提出 了基于快速移位的译码器 7 】。w a da d i 于1 9 8 4 年对快速译码器做了一些改进【8 】， 进一步提高了译码速度。以上各种译码器在硬件结构和译码速度等方面都有各自 的优势，它们有一个共同的特点：只能纠正单个突发错误。但是在实际的无线通 信信道传输过程中极有可能在一个码字中发生两处或多处突发错误。本文拟议一 种能纠正两处突发错误的译码方案。 1 4 主要工作及论文组织 本文根据信道编译码的基本原理，参考了大量的文献，分析了f i r e 码的构 造方法和纠错能力。在传统的一般捕获译码器的基础上做了改进，使改进后的译 码器能够充分发挥f i r e 码的纠突发错误能力。以g s m 系统中采用的缩短f i r e 码为例阐述了该译码器的工作原理，最后在g s m 仿真平台上测试比较了译码器 改进前后的误码性能。 g s m 控制信道的外编码采用的是( 2 2 4 ，1 8 4 ) 缩短f i r e 码。其生成多项式 是g ( x ) = ( x 2 3 + 1 ) ( x 1 7 + x 3 + 1 ) = x 4 0 + x 2 6 + x 2 3 + x 1 7 + x 3 + 1 ，其中( z 1 7 + x 3 + 1 ) 是 朋= 1 7 的既约多项式，周期e = 2 1 7 一l = 1 3 1 0 7 1 ，c = 2 3 ，刀= p c = 3 0 1 4 6 3 3 ， m + c = n - k = 4 0 = d e g g ( x ) 】生成的是( 3 0 1 4 6 3 3 ，3 0 1 4 5 9 3 ) f i r e 码，缩短为( 2 2 4 ， 1 8 4 ) f i r e 码，该码能够纠正两处突发错误：一处长度不超过1 2 的主突发错误 和一处长度不超过8 的次突发错误。传统的译码器只能纠正一处突发错误，改进 后的译码器能够纠正两处突发错误，降低了系统的误码率。 本文的章节安排如下： 第二章介绍了纠错编码的基本理论，并重点讲述了循环码的特性：包括循环 码的表述方式、循环码的编码方法和译码原理。 第三章主要介绍了纠突发错误循环的概念和基本码限，并分析了f i r e 码的构 造方法、编码电路以及一般捕错译码器和快速译码器的设计方法。 第四章阐述了译码器的改进的数学原理以及译码器的工作流程，然后编写 m a t l a b 平台上做软件仿真的主要代码，最后对仿真结果做了详细的分析。 第五章总结了全文的工作和算法中值得研究和有待改进的问题。 第二章纠错编码理论与循环码编译码系统 2 1 纠错编码理论 2 1 1 纠错编码的基本概念 纠错编码是在数字传输和通信中用来提高其可靠性的一种编码技术，纠错编 码也被称为信道编码。一个简单的信道编码模型如图2 - 1 所示。i 是信源输出的 信息序列，通过编码器编码得到码字s ，然后进过噪声信道，在接收端为r 。译 码器根据接受信息序列r 来估计i 的取值，输出估计序列i 。信道的输出r 依 赖于相同长度的s ，即它们之间的关系可用对于得条件概率密度函数来描述。从 数学的角度上来说，信道其实是一个从发送空间s 到接受空间r 上的一个概率映 射函数。 图2 - 1 信道编码模型 信道编码的任务是提高数据传输效率，降低误码率。信道编码的基本思 想就是通过在传输信息中加入冗余信息来抵抗信道错误与干扰。信道编码的本 质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少，信道 编码的过程是在原数据码流中加插一些码元，从而达到在接收端进行判错 和纠错的目的，这就是我们常常说的开销。 信道编码的基本形式是，将冗余符号附加在信息符号后面获得编码序列或者 码字。如图2 - 2 所示，是一个经过分组编码后得到的码字。这种码称为系统码， 意味着信息符号总是出现在码字的前面( 左侧) k 个位置，码字剩余的拧一k 个符 号是与通过特定的函数计算得到的与信息符号相对应的冗余位，它用来纠正或检 测错误。所有码序列的集合称为纠错码。 2 i 2 纠错码分类 + 一n 个符号+ 卜k 个符号卜n - k 个符号_ 图2 - 2 系统码结构 信道前向纠错编码的分类方式很多，如图2 - 3 所示彼此之间又互相涵盖。 常见的分类方式有以下几种 9 】： ( 1 ) 根据监督码元与信息组之间的约束关系不同，可以分为分组码和卷积码 两大类。如果本码组的监督码元仅与本码组的信息码元有关，与其它码组的信息 码元均无关，则称这类码为分组码。如果本码组的监督码元不仅和本码组的信息 码元相关，而且还和与本码组相邻的前若干码组的信息码元也有约束关系，则这 类码被称为卷积码。 ( 2 ) 根据编码前后的码字中的信息码元是否发生变化，可分为系统码和非系 统码。若经过编码后的信息码元保持原样不变，则称这类码为系统码。若经过编 码后，信息码元改变了原有的形式，则称这类码为非系统码。在分组码情况下系 统码与非系统码性能相同，因此更多地采用系统码；而在卷积码的情况下有时非 系统码有更好的性能。 ( 3 ) 根据编码构造的数学方法分类，可分为代数码、几何码和算术码。其中， 代数码建立在近世代数的基础上，理论发展最为完善。 ( 4 ) 根据监督码元和信息码元是否存在线性关系，可分为线形码和非线形码。 若编码规则可以用线性方程组来表示，则称为线性码。反之，若两者不存在线性 关系，则称为非线性码。线性码是代数码的一个最重要分支。 ( s ) 根据码的差错控制功能可分为检错码、纠错码以及纠正删除错误的纠删 码。但实际上这三类码并无明显界限，同一类码可以在不同的译码方式下体现出 不同的功能。 ( 6 ) 按照纠正错误的类型不同，可以分为纠正随机错误码和纠正突发错误码。 前者主要用于发生零星独立错误的信道，而后者则用于对付以突发错误为主的信 道。 ( 7 ) 按照每个信息码元的受保护程度是否相等可分为等保护纠错码与不等保 护纠错码。此外还有其他分类，在此不一一列举。常用的前向纠错码有循环码、 卷积码、r s 码、乘积码、t r u b o 码和l d p c 码等。 2 1 3 纠错码的数学理论基础 图2 - 3 纠错码的分类 如果数a 能够被b 整除，则称6 是a 的一个因子，或者说a 有一个因子6 ，记 为 bla 如果b 是素数，称a 有素因子b 。 设以下刀0 2 ) 个整数：a i ，a 2 ，a 。都能被6 整除，即： ala i ，6 i a 2 ，6ia 。 那么称b 为a 。，a ：，a 。的公因子，公因子中最大的一个称为最大公因子， 通常a 。、b l 的最大公因子表示为： g c d ( a l ，a 2 ) 如果对于以下n 2 ) 个整数：a 。，a ：，a 。，存在一个数m ，并且有 a l i 聊，口2m ，a 。i 册 那么称m 为a ，a ：，a 。的公倍数。显然，公倍数有无穷多个，公倍数中最小 的一个称为最小公倍数。通常a ，、b 。的最最小公倍数表示为： l c m ( a i ，a 2 ) 容易得到以下计算结果： l c m ( a l ，a 2 ) = a xb g c d ( a l ，a 2 ) 设a 是整数，刀是正整数，则定义a 除以刀所得的余数为口模珂，记为 am o d 刀 同余：如果a 、b 、所都是正整数，且m10 6 ) ，则称a 和b 模m 同余，记 作 a 三b ( m o d 刀) 同余是数论中最基本的概念之一，使用模运算来定义，a 和b 模m 的余数相 同。由模运算符的定义可得到模运算的性质： ( 1 ) ( 口m o d 刀) = ( bm o d ) 等价于a 暑b ( r o o d 聆) ； ( 2 ) 女果疗l ( 口一b ) ，爿| j 么口三b ( m o d 刀) ； ( 3 ) a 暑b ( m o d 刀) 等价于b 暑a ( m o d n ) ； ( 4 ) 若a 量b ( m o dn ) 与b 兰c ( m o d n ) 同时成立，则a 量c ( m o d n ) 由模运算的定义可知，( am o d 刀) 运算将所有的整数映射n d , 于玎的非负整 数集合。限制在这个集合上进行的算术运算称为模算术。模算术具有以下性质： ( 1 ) 【( 口m o d 刀) + ( bm o d 行) 】m o d 玎= ( 口+ 6 ) m o d 刀； ( 2 ) 【( 口m o d 刀) 一( 6 m o d 刀) 】m o d 行= ( a - b ) m o d 疗； ( 3 ) ( 口r o o d ”) ( 6 m o d 疗) 】r o o d 刀= ( 口6 ) m o d 疗 域的定义：一个域f 就是一些元素的集合，域定义了加法和乘法两种运算。 对于任意a ，b ，c f 应满足以下条件： ( 1 ) f 在加法和乘法下是封闭的，即口b f ，“”为加法或乘法运算。 ( 2 ) 交换律：a + b = b + a ，a b = b a 。 ( 3 ) 结合律：( 口+ 6 ) + c = 口+ ( 6 + c ) ，a x ( b xc ) = ( 口6 ) c 。 ( 4 ) 分配律：a x ( 6 + c ) = a xb + a xc ，( 6 + c = b a + c 口。 ( 5 ) f 中存在元素0 ，使a + 0 = 0 。 8 ( 6 ) f 中存在元素1 ，使口l = a 。 ( 7 ) 对于f 中的任意元素口存在加法逆元一口，使口+ ( 一口) = 0 。 ( 8 ) 对于f 中的任意元素a 0 ，存在乘法逆元口一，使口口= 1 。 以上要求说明域必需满足的性质有：加法和乘法各自的封闭性、结合律、交 换率、单位元和逆元以及加法和乘法的分配律。一个域包含的元素的数日可能是 有限的，也可能是无限的。例如，全体有理数、全体实数和全体复数都可以构成 域，分别称为有理数域、实数域和复数域。由于以上域的元数是无穷的，故称为 无限域。如果域的元数是有限的，则称为有限域，用g f ( p ) 表示，p 表示域的 元素个数。有限域也称为g a l o i s 域，或者伽罗华域。 有限域g f ( p ) 定义为整数 o ，1 ，2 ，p 一1 ) 的集合，相应的运算为模p 的代 数运算。对于a ，b g f ( p ) ，做加法： a + 6 兰，i ( m o dp ) 做乘法： 口b = s ( m o d p ) 可以证明g f ( p ) 中至少存在一个元素仅，使得g f ( p ) 中任意非零元素可以表 示成仅的某次幂的形式，这样的元素仪称为g f ( p ) 的生成元，也称为本原元。 有限域上的多项式：系数属于某数域上的多项式称为该数域上的多项式。比 如，系数为二进制数的多项式称为二元域g f ( 2 ) 上的多项式，系数为p 进制数的 多项式称为g f ( p ) 的多项式。定义在g f ( p ) 上的多项式的一般形式为 厂( x ) = t 2 n x ”+ g n _ 1 x ”- 1 + + a l x + 口。 其中，q g f ( p ) ；净1 ，2 ，刀。着a 。0 ，则称( x ) 为i 1 次首一多项式， 刀为多项式f ( x ) 的阶，记为d e gu ( x ) ) 。用c 叫表示系数在g f ( p ) 上的一切多 项式的集合。c 【叫中的多项式可以按照g f ( p ) 的运算方式进行加法、减法和乘 法运算。 剩余：对于c m 中的任意一对多项式a ( x ) 和f ( x ) 0 ，必定存在唯一的一 对多项式q ( x ) 和r ( x ) ，满足a ( x ) = g ( 力( 功+ ，( 功，d e g ，( 功 d e g f ( x ) 。q ( x ) 和 ，( 力分别称为商和余数。该余数有时又称为剩余，并记作 r ( ，) 【口( x ) 】= ，( x ) 设口( 功、b ( x ) 和( 功都为g f ( p ) 上的多项式，则剩余的两个重要性质为： ( 1 ) r ( ，) 【口( z ) + 6 ( x ) 】= r ，i x ) 【口( 功 + 灭，o ) 【6 ( 工) 】； ( 2 ) r ( ，) 【口( 曲6 ( 力】= 髟( ，) r 夕( ，) 【口( x ) 】尺，( ，) 【6 ( x ) 】) 。 9 同余：设f ( x ) 为g f ( p ) 上的一个固定多项式，g ( x ) 和h ( x ) 也是定义在 g f ( p ) 上的多项式，如果g ( x ) - h ( x ) 能够被f ( x ) 整除，则称g ( x ) 和h ( x ) 关于模 f ( x ) 同余，记为 g ( x ) 暑厅( x ) ( m o d 厂( 工) ) 既约多项式：若f ( x ) 是g f ( p ) 上次数不等于0 的多项式，除了常数和常数 与该多项式本身的乘积以外，不能被g f ( p ) 上的其他多项式除尽，则称f ( x ) 为 既约多项式。 。 本原多项式：f ( x ) 是g f ( p ) 上的历次既约多项式，如果能被它整除的最简 单首一多项式 ”一1 ) 的次数疗p “一l ，则称该多项式为本原多项式。本原多项 式一定既约；但是既约多项式不一定是本原多项式。 2 2 循环码的表述 设c 是一个仞，后) 线性码，如果c 中的任意一个码字经过任意循环移位后 仍然是c 中的一个码字，则称此码是一个循环码。循环码是线性分组码中最重 要的一种子类，是目前研究得比较成熟的一类码。循环码具有许多特殊的代数性 质，这些性质有助于按照要求的纠错能力系统地构造这类码，并简化译码算法， 目前发现的大部分线性码与循环码有密切关系。循环码还有易于实现的特点，其 硬件很容易用带反馈的移位寄存器实现。正是由于循环码具有代数结构清晰、性 能较好、编译码简单和易于实现的特点，因此在目前的计算机纠错系统中所使用 的线性分组码几乎都是循环码。 1 9 5 7 年，普朗格( p r a n g e ) 首先开始研究循环码，此后，人们对循环码的 研究在理论和实践方面都得到了很大的进展 1 0 3 。现在循环码已成为研究最深 入、理论最成熟、应用最广泛的类线性分组码。本文的主要研究对象f i r e 码 也是循环码的一种。 2 2 1 循环码的多项式表述 在代数编码理论中，为了便于计算，把码组中的码元当着是一个多项式的系 数，即把一个长为n 的码组表示成： c ( x ) = c n - i x 一+ q p 2 工“- 2 + + c i x + 1 7 0 ( 2 一1 ) 这种多项式有时称为码多项式。一个加，七) 循环码有2 个不同码组。用码 多项式g ( 曲( 其次数，= r l k ) 表示前( 七一1 ) 皆为零的码组。根据循环码的循环 特性，可知x g ( x ) 、x 2 9 ( x ) 、x k - i g ( x ) 都是码多项式，而且这七个码多项式显 然是线性无关的。这就说明，( 疗，k ) 循环码可以由它的一个n k 次的码多项式 g ( x ) 来确定，或者说g ( x ) 生成了该o ，k ) 循环码。这个唯一的n - k 次多项式 g ( 功称为( 7 1 ，k ) 循环码的生成多项式。当求一个仞，k ) 循环码时，只要分解多 项式石”+ 1 ，从中取出伽一k ) 次因式作牛成多项式g ( x ) 即可。一旦确定g ( x ) 了， 则整个仰，七) 循环码也就确定了。 定理2 - 1 ( a ) 如果码字空间c 是g f ( 2 ) 上的一个( 刀，k ) 循环码。则它的生成多项式g ( x ) 是x ”+ l 的一个因式。设码字矢量c = ( ，c 。9o ，c 川) ，当且仅当该矢量对应的 码字多项式c ( x ) = 铴+ c l x + + c 川x ”1 能够被g ( 功整除时，c 属于码字空间c 。 如果用k 表示c 的维数，则k = 刀- d e gg ( x ) 。 ( b ) 反之，如果o ，k ) 是x ”+ l 的一个因式，则存在一个以g ( x ) 为生成多项 式，且七= n - d e gg ( x ) 的( r t ，k ) 循环码，该码中所有矢量( ，c l ，”，c 川) 的生成 函数都能够被g ( x ) 整除。 设g ( x ) 是x ”+ l 的因式，且为( r t ，k ) 循环码的生成多项式，则有： 石”+ 1 = 厅( x ) g ( x ) 因为以g ( x ) 为生成多项式可以生成一个( r t ，后) 循环码，则g ( 曲为刀一k 次多 项式；而办( x ) 则为k 次多项式，以办( z ) 为生成多项式可以生成，疗一七) 循环码， 这两个循环码互为对偶码。称h ( x ) 为仞，后) 循环码的校验多项式或者监督多项 式，且 h ( x ) = h k x + h k l x _ 1 + + 啊x + h o ( 2 2 ) 2 2 2 循环码的矩阵表述 f l ：l 于( n ，k ) 循环码共有2 。个码字，从码组中取出一个前面( 七一1 ) 位都是0 的 码字，用g ( x ) 表示，不难看出g ( x ) 的多项式次数为( n - k ) 。因为工g ( 力， f = 0 ，l ，2 ，k l 均是码字且相互独立，故可以用x g ( x ) ，f = 0 ，l ，2 ，k 一1 作为生 成矩阵g 的k 行。由多项式g ( x ) 可以构成生成矩阵g ( 功为 g ( 工) = x k - ! g ( 功 x k - 2g ( x ) x g ( x ) g ( x ) g h 一女g 一i _ l 0 g 。 o0 00 ( 2 3 ) 循环码c ( x ) 为 c ( x ) = 【研lm 2 】g ( x ) ( 2 4 ) 式中 m 。m ：m 。】为七位信息码元矢量。 设循环码的监督多项式为办( z ) = h k x + h k l x 扣1 + 年抚x + h o ，则，七) 循 环码的监督矩阵为 h = 厅( x ) 妫( x ) x n - k - l h ( x ) i1 0 h oh l 魂一l 一ih k 0 ；：； h i 以一l 玩0 0 式中乃为h ( x ) 的反多项式。 2 3 循环码的编码 2 3 1 编码原理 ( 2 - 5 ) 由于生成多项式g ) 和校验多项式办( x ) 都可以唯一地确定一组循环码，因 此编码方法既可以基于生成多项式g ( x ) ，又可以基于校验多项式办( x ) 。本文仅 讨论基于生成多项式的编码方案。仰，七) 循环码的编码就是将一个k 位长的信息 组朋( 力= m n x 扣1 + 所柚x 扣2 + 所l z + ，编成长为1 1 的码字c ( 力。由循环码的 编码理论可知，非系统码的码字多项式为c ( x ) = m ( x ) g ( x ) ，a 。g ( 功= i i - - k ，因 此可以用g ( x ) 乘法电路实现非系统码编码。一个系统码的( 疗，七) 循环码的码字多 项式为 1 2 0 0 0 ；g o o o ；品 o o 舒； 0 一；0 o 一0譬：