（电路与系统专业论文）多种级联码纠错系统的研究与设计.pdf

南京师范大学硕士学位论文 摘要 移动通信是当今通信领域内最为活跃、发展最为迅速的领域之一，在新世纪 内对社会发展和人类生活产生了重大影响。然而，随着民用移动通信的用户数量 的不断增加，业务范围不断扩大，频率资源和可用频道数之间的矛盾日益尖锐， 这个时期的移动通信发展重点在于开发新的频段、论证新方案和有效利用频谱等 方面的研究工作。 信道编码是数字移动通信中的关键部分，它可以使得信号能够更好地抵抗如 噪声和衰落等信道损耗的影响，从而改进通信系统的性能。信道编码的目的是为 了降低所需要的信噪比，或者可以选择为给定的能够达到的信噪比降低误差概 率。为了达到这个目标需要花费更大的带宽。 本文引入级联码，目的是为了将它应用于信道编码以改进系统的纠错性能。 本文对四种常用的纠错码如h a m m i n g 码、b c h 码、r s 码、卷积码根据级联 码的构成原理，引入交织器，讨论了五种级联码分别在b p s k 、q p s k 、7 d 4 q p s k 的调制方式下的蒙特卡罗仿真实验。仿真结果表明：在所要达到的误码率条件下， 级联码与单个码相比，尤其与未编码的情况相比，获得了较大的编码增益，而系 统的复杂度并没有增加。同时，我们也得出，在不同的调制方式下，误码率的性 能也是存在一定的差别。此外，基于数字移动通信中编码及调制的特点，着重分 析了在7 d 4 - q p s k 调制下的不同级联码的性能差别，旨在找出误码性能较好且频 谱利用率较高的级联编码。以上的仿真实验为级联码能应用在移动通信系统的前 向信道编码中提供了理论基础，具有一定的实际意义。 关键词：级联码纠错编码调制解调交织器数字移动通信 南京师范大学硕士学位论文 a b s t r a c t m o b i l ec o m m u n i c a t i o ni so n eo f t h em o s ta c t i v ea n dr a p i dd e v e l o p m e n tf i e l d si n t h ec o m m u n i c a t i o n , i tp r o d u c e sg r e a ti n f l u e n c eo nt h es o c i e t yd e v e l o p m e n ta n d h u m a nl i f ei nt h en e wc e n t u r y h o w e v e r , w i t ht h ei n c r e a s e dn u m b e ro fu s e r sa n d e x t e n d e do p e r a t i o na r e a s ，t h ec o n t r a d i c t i o nb f f w e e nf r e q u e n c y1 皑s o u r c ea n dc h a n n e l s t m n am o r ea c u t e l y d u r i n g 也i sp e r i o d , t h ee m p h a s e so ft h em o b i l ec o m m u n i c a t i o n d e v e l o p m e n ti s ，t h a tb c g i m 】i n gt h er e s e a r c hw o r kw i t hd e v e l o p i n gn 朋c h a n n e l s ，n e w d e m o n s t r a t i o nm e t h o d sa n du s i n gf r e q u e n c ys p e c t r u me f f e c t i v e l y c h a n n e lc o d ei st h ek e y p o i mo ft h ed i g i t a lm o b i l ec o m m u n i c a t i o n , i tc 柚m a l c c t h es i g n a l sw i t h s t a n di n f l u e n c es u c ha sn o i s ea n df a d i n gm o 犯e f f e c t i v e l y , w h i c hc a n i m p r o v e st h ep e r f o r m a n c eo f t h ec o m m u n i c a t i o ns y s t e m t h ep u r p o s eo f c h a n n e lc o d e i 3t om a k et h es n rr e d u c e d , o rr e d u c et h eb e rf o rt h eg i v e ns n i 乙f o rt h i s w eh a v e t oe x p e n dl a r g e rb a n d w i d t h i nt h ea r t i c l e ，w ei n t r o d u c et h ec o n c a t e n a t e dc o d e ，w h i c hi su s e di nc h a n n e lc o d e t oi m p r o v et h es y s t e mc o r r e c t i o na b i l i t y f i r s t , w en l a k et h es i m u l a t i o no nf o u rt y p e s o fc o d e ss u c ha sh a m m i n gc o d e ，b c hc o d e ，r sc o d e ，c o n v o l u t i o nc o d e s e c o n d , a c c o r d i n gt o t h ec o n s t i t u t i o np r i n c i p l eo ft h ec o n c a t e n a t e dc o d e ，w em a k ef i v e d i f f e r e n tk i n d so fc o n c a t e n a t e dc o d e ss i m u l a t i o nw i t hi n t e r l a c ea n dt h r e ed i f f e r e n t w a y so fm o d u l a t i o ns u c ha sb p s k , q p s k , 1 d 4 q p s i c1 1 地r e s u l t si n d i c a t e s , c o m p a r e dw i t ht h es i n g l ec o d i n g , e s p e c i a l l yt h eu n - e n c o d i n g , t h ec o n c a t e n a t e dc o d i n g a c q u i r e dm u c hc o d i n gp l u si nt h et e r mo f g i v e nb e r , h o w e v e r , t h es y s t e mc o m p l e x i t y i sn o ti n c r e a s e d m e a n w h i l e w eg e td i f f e r e n tb e rr e s u l t so nd i f f e r e n tm o d u l a t i o n m e t h o d s m o r e o v e r , b a s e do nt h ec h a r a c t e r so ft h em o b i l ec o m m u n i c a t i o ns y s t e m , w e a l s oa n a l y s e st h ed i f f e r e n tp e r f o r m a n c eb c l w v nd i f f e r e n tc o n c a t e n a t e dc o d i n gw i t h ，蚴一q p s km o d u l a t i o n t h ep u r p o s ei st os p l i tt h ed i f f e r e n c eb e t w e e nb e t t e rb e ra n d b e t t e ru s eo ff r e q u e n c ys p e c t r u m a b o v eo f t h es i m u l a t i o ne ) 【p e r i 髓c 懿p r o v i d et h e o r y b a s i sf o rt h ec o n c a t e n a t e dc o d i n g ，w h i c hi su s e di nt h em o b i l es y s t e m , i ti sm e a n i n g f u l a c t u a l l y k e y w o r d s ：c o n c a t e n a t e d - c o d i n ge r r - c o r r e c t - c o d i n gm o d u l a t i o n & d e m o d u l a t i o n i n t e r l a c em o b i l ec o m m u n i c a t i o n 果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名：汤蹇，幺耻作者签名：王銎臼坠 日期翘：! ! ： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论文 进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行 检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解 密后适用本规定。 南京师范大学硕士学位论文 1 1 课题背景 1 1 1 移动通信概述 第一章前言 移动通信就是指通信双方至少有一方在运动状态中进行信息交换。例如：运 动的车辆、船舶、飞机或人在固定点之闻进行信息交换，或者移动物体之间的通 信都属于移动通信。最初的移动通信是为军事的需要而建立并不断发展起来的 n 】 第二次世界大战极大地促进了移动通信的发展。各国武装部队大量采用了无 线电系统。军事上的需求导致了移动通信事业的巨大变化，其中涉及到了系统设 计、可靠性和价格等。在五十年代之后，各种移动通信系统相继建立，在技术上 实现了移动电话系统与公众电话网的连接。例如美国b r i t s 系统，实现了自动拨 号和移动台信道的自动选择。在通信理论上也相继出现了香农信息论、纠错码理 论、调制理论、信号检测理论、信号与噪声理论、信源统计特性理论等，这些理 论使得现代移动通信技术日趋完善。尤其是晶体管、集成电路相继问世后，不仅 加倍促进了像电话通信这样的模拟技术的高速发展，而且出现了具有广阔前景的 数字通信，并相继出现了脉码通信、微波通信、卫星通信、光缆通信等新的通信 手段钔 从2 0 世纪7 0 年代中期开始，人们就致力于研究在频带有限的情况下，如何 进一步提高频谱利用率以增加系统容量。由此提出了小区制大容量系统。这种系 统是美国贝尔实验室最早提出来的。它就是蜂窝状移动通信系统，这是一种更有 效的信道频率复用系统 1 1 2 移动通信系统的发展 现代移动通信技术是- - i 复杂的高新技术，尤其是蜂窝移动通信，不但集中 了无线通信和有线通信的最新技术成就，而且集中了网络技术和计算机的最新成 果。蜂窝移动通信经历了由模拟到数字的三个重要的阶段船： 南京师范大学颈士学位论文 ( 1 ) 第一代模拟蜂窝移动通信系统 1 9 7 1 年1 2 月，b e l l 公司向美国联邦委员会( f c c ) 提交了蜂窝移动通信系统 h c m s 的建议，就是将大区域划分为几个小区，相邻的小区使用不同的频率进 行传输，以避免相互干扰，并在8 5 0 m i - i z 频段提供了4 0 m h z 的通信资源。1 9 7 8 年，安装了h c m t s 系统，并于1 9 8 3 年开始商业服务。此系统在频率复用、多 波道共用技术、全自动地接入公共电话网的小区制、大容量蜂窝式等方面发展了 蜂窝和移动通信技术，由此到了2 0 世纪8 0 年代演变成了美国模拟系统的国家标 准先进的移动电话业务( a m p s ) ，与此同时，基于不同标准的其他模拟蜂窝 移动通信系统也得到了很大的发展，如英国的全接入通信系统( t a c s ) 、日本的 电报和电话系统( n a m t s ) 、北欧移动电话系统( n m r s ) 和原联邦德国的n e t z c 等。 尽管模拟蜂窝系统取得了巨大的成功，但是在实际使用过程中也暴露了一些 问题：如频谱效率低，有限的频谱资源和无限的用户容量的矛盾十分突出，业务 种类比较单一，主要是话音业务；其次，模拟系统存在同频干扰和互调干扰；此 外，模拟通信系统盼保密性比较差。当然最重要的因素是有限的容量与日益增长 的市场要求之间的矛盾。因此，9 0 年代推出了数字蜂窝系统。 ( 2 ) 第二代数字蜂窝移动通信系统 1 9 8 2 年，欧洲邮电管理委员会( c e p t ) 成立了移动通信特别小组( g s m ) ，开 发数字蜂窝式移动通信技术，即全球通移动通信系统( g s m ) 。1 9 9 1 年，g s m 数 字蜂窝式移动通信系统在欧洲问世，接着以t d m a 标准为基础的其它第二代数 字蜂窝移动通信系统如d a m p s 、y d c 等也相继投入使用。同时以i s 9 5 技术标 准为基础的c d m a 商用系统已分别在香港、韩国等地区和国家投入使用并取得 良好的用户反映。 第二代数字蜂窝移动通信系统最大的特点是抗干扰能力强和潜在的大容量， 也就是说它可以在环境更为恶劣和需求量更大的区域使用。在一定的带宽范围 内，数字系统良好的抗干扰能力使得第二代蜂窝系统具有比第一代蜂窝移动通信 系统更大的通信容量、更高的服务质量。由于数字处理技术和大规模集成电路及 其加工技术的发展，伴随着数字系统综合处理能力不断提高，使得系统成本、价 格和功也在不断下降。 2 南京师范大学硕士学位论文 鉴于数字移动通信系统的特点，在过去几年内获得了前所未有的研究和发展， 并在实际应用中逐步占领并且大大地扩充了过去的模拟系统市场。在信息时代， 图像、话音和数据相结合的多媒体业务和高速率数据业务量大大增加，人们对通 信业务多样化的要求与日俱增，现有的系统已远远不能满足未来用户的业务需 求，因此第三代移动通信系统的研究和发展成为电信领域的一个新的研究热点。 ( 3 ) 第三代数字蜂窝移动通信系统 1 9 8 5 年，国际电信联盟( i t u t ) 最先提出了第三代移动通信系统，当时被称 为未来公众陆地移动通信系统( f p l m t s ) ，1 9 9 6 年正式更名为m f r 2 0 0 0 ，即国际 移动通信系统。i m t - 2 0 0 0 支持的网络被称为第三代移动通信系统，简称3 g ，它 支持高达2 m b i t 4 s 速率的业务，而且业务种类将涉及声音、数据、图像和多媒体 等各种业务。 第三代数字蜂窝移动通信系统最大的特点是它可以提供一个全球的覆盖，使 得移动终端能在多个网络间无缝漫游；它具有支持多媒体业务的能力，便于过渡 演进。由于第二代通信网络已具有相当的规模，所以在引进第三代移动通信时， 是建立在第二代的基础上逐渐灵活演进，对它的要求则是应与圃定网兼容，还应 具有更高的频谱效率、高的信道效率、高的服务质量、高的保密性等。 1 1 3 数字通信系统的基本结构 一个完整的数字通信系统的基本结构如图卜1 所示，由于要求第三代移动系 统能够提供各种综合业务，这里的信源包含了话音、数据、图形及活动图像等。 通信系统中信源编码的主要作用是用能在信道中传输的符号来表示信源发出的 信息，即将模拟或数字信源的输出有效地变换成二进制数字序列的处理过程，使 得信源信息适合在信道中传输，而且在允许失真的范围内用尽可能少的二进制数 字表示信源输出，提高信息传输的有效性”1 。 信道编码的作用主要是在二进制信息序列中以受控的方式引入一些冗余，以 便在接收机中用来克服信号在信道中传输时所遭受的噪声和干扰的影响，增加信 号的抗干扰能力，保证信息传输的可靠性。而此处的信道编码部分正是本课题所 要研究的主要内容，本文将基于移动通信系统中的特点，引入级联码，从频带利 南京师范大学硕士学位论文 用效率及误码率性能方面入手，对五种形式的级联码结合不同的调制方式进行整 体的误码率仿真分析，结合不同级联码的各自特点，目的是为了寻求合适的编码 方法，来提高整个系统的有效性和可靠性。 图1 - 1 数字通信系统的基本结构 1 2 信道编码定理及其发展应用 1 2 1 信道编码定理 1 9 4 8 年耵，信息论的奠基人ce s h a n n o n ，他的开创性论文“通信的数学理 论”嘲中首次阐明了在有噪声的信道中实现可靠通信的方法，提出了著名的 s h a n n o n 第二定理( 也称有噪信道编码定理) ，具体为：对于任何信道，只要信息 传输速率r 不超过信道容量c ，则存在一种编码方法，在采用最大似然译码 ( m l d ) 时，其误码率可以任意小该定理包含了两个方面的含义：一是当r f ) 。 2 1 2 线性分组码的编码原理 ( 玲，k ) 线性分组码编码就是要在n 维向量空间中找出满足一定规则的、由q 个向量组成的k 维向量子空间。或者在给定码的最小距离d 二和码率r 条件下， 从已知的k 个信息元求出，= ，l k 个校验元，然后将校验元附于信息元之后便德 l o 南京师范大学硕士学位论文 到一个码字。 i 一致校验矩阵 对于( n ，七) 线性分组码，可以锝到下面的线性方程 岛，啊：啊。 如：如。 以。h ，：k c 月一l c p 2 ： c o = 0 ( 2 5 ) 上式可以简化为h c 7 = 0 ( 2 - 6 ) 或凹= 0 ( 2 - 7 ) ，其中码字向量为 c = 【q - l ，c 0 2 ，c o 】，c 7 是c 的转置。h 是一个，行以列矩阵。 h 1 2 h l 。 h 2 2 h 2 。 h ，2 h ，。 ( 2 - 8 ) 日称为线性分组码的一致校验矩阵( p a r i t yc h e c km a t r i x ) ，它的意义为： ( 1 ) 日矩阵每一行代表一个线性方程的系数，即求一个校验元的线性方程。 ( 2 ) 日矩阵有，行，且各行之间必须线性无关。 ( 3 ) 若c 中各元素是满足由所确定的，个线性方程的解，故c 是一个码 字，反之，若c 中的各元素组成一个码字，则一定满足由何所确定的，个线性方 程。所以c 是方程( 2 - 5 ) 的解的集合。显然，日一定，便可由信息元求出校验元， 编码问题也就解决了。 一生成矩阵 由于( 刀，七) 线性分组码的2 个码字组成了，z 维向量空间的一个后维子空间， 所以2 。个码字完全可以由i 个独立的向量所组成的基底构成，设这忌个向量为 化成矩阵形式为： c i = ( 9 1 l g l 2 g i l 9 1 j + l g i 。) c 2 亍9 2 1 9 2 ：g ：罗2 t + t g ：一 ( 2 9 ) c i = ( g i i g 2 g 肚g t j + 1 g b ) 坨； 一 矗厅 知 _。_-_i-_-_-【 1 1 日 南京师范大学硕士学位论文 g = & l9 1 2 g u 轧“鼠 9 2 1g 墨g 毖9 2 埘9 2 札 g k lg k 2 g tg k “gb i ( 九，七) 码中的任何码字，均可由这组基底的线性组合生成。即 c = m g = 沏一朋柚埘“) & l9 1 2g l 。 9 2 1 如g z , g k lg , 2 ( 2 一l o ) ( 2 - 1 1 ) 式中所= ( 肌，一柚一朔麟) 是k 个信息元组成的信息组。 也就是说，只要给定一个信息组，就可以根据上式( 2 - 1 1 ) 求出编码后的码字。 所以称k 个基底构成的k x 刀阶矩阵g 为( n ，j | ) 码的生成矩阵，并且称这k 个线 性无关的基底为生成码( 刀，后) 。g 的含义为：( 1 ) 一般情况下，( 刀，七) 码的生成 矩阵是一个k 行刀列的矩阵。( 2 ) 一个( 行，后) 码的生成矩阵的k 行就是指k 个线 性无关的码字。它们的线性组合生成( 珂，七) 码的全部g 个码字。因此，g 求得 了，也就解决了编码的问题。( 3 ) g 作为码的生成矩阵，形式并非固定，但是都 生成同一个，后) 码。( 4 ) 日和g 彼此正交，即g h 7 = 0 或者h g 7 = 0 。 2 1 3 线性分组码的译码原理 灯矩阵或g 矩阵得到后，就解决了编码问题，经过编码以后将码字发送，由 于信道的干扰，导致码字出错，收方要发现或纠正错码，这就是译码的问题。 设发送的码字记为c = ( c 川c 棚c 。co ) ，信道产生的错误记为 e = ( e e 。一2 g l ) ，接收到的码字记为r = ( ，棚，i ，o ) ，所以 r = c + e ，则有，= c4 + p ，c7 ，p ，g f ( q ) 或g f ( 2 ) 。译码的任务就是 要从r 中求得e ，从而得到c = r e 。 由于( 行，j i ) 码的任何一个码字c 均满足( 2 - 6 ) 式，将接收的码字用此式检验， 例如： r h 7 = ( c + e ) h 7 = c h 7 + e h 7 = e h 7( 2 - 1 2 ) 1 2 南京师范大学硕士学位论文 定义2 1 2 ：设( 以，i ) 码的的一致校验矩阵为日，r 是发送码字c 的接收向 量，称 s = r 7 = e 7 ( 2 - 1 3 ) 为接收向量r 的伴随式或校正子( s y n d r o m e ) 显然，若e = 0 ，则s = 0 ，那么r 就是c ，若e 0 ，则s 0 ，若能从s 中 得到e ，则由c = r e 即可恢复发送的码字。可见s 仅与e 有关，它充分反映 了信道干扰的情况，与发送什么样的码字无关 若码字传送时发生了p 个错误，且是码字的第f 。，f2 ，f 位有错，则错误 模式可以表示成： s2 e h l = ( 0 口f 。o g f ：0 - - - 8 0 0 ) ( 2 1 4 ) 那么伴随式为： s = e m 7 = ( 0 岛0 岛：0 q 。0 o ) = p f i 矗 一f i + p f2 h 肛1 2 + + p ，。j i l p l 其中：s 是日矩阵中e 不等于零的 。的线性组合。 由上述讨论，我们得出译码的步骤为： ( 1 ) 计算出接收向量的伴随式s ，- - r 7 ； ( 2 ) 找到对应的错误模式e ，； ( 3 ) 通过c ，= 五，一e ，从而实现纠错。 2 2 循环码 2 2 1 循环码的基本概念 ，1 i l 棚 ： h ： 厅o ( 2 1 5 ) 循环码c 1 2 是一种线性分组码。它有许多特殊的代数性质。由于这些性质便于 运用代数理论来研究，有助于按照所要求的纠错能力系统地构造这类码，从而可 1 3 南京师藕大学硕士学位论文 以简化译码方法，使得循环码的编、译码电路比较简单，因此得到了广泛的应用。 循环码不仅可以纠正独立的随机错误，也可以纠正突发错误。 定义2 2 1 ：一个疗重的七维予空间吁，v c = ( c ，l c ，卜2 c i co ) 吖， 总有c = ( c 。一：c 。c 一。) ey ，则称矿善为循环子空间或循环码。 若把每一个向量的分量看成是一个g f ( q ) 中多项式的系数，则循环码的每一 码字可与一个次数小于等于玎一1 的多项式对应： ( 巳一l c i - 2 c l c o ) j f 加1 + c 0 2 】，卜2 + + c l x + c o ，q g f ( q ) 与码字对应的多项式称之为码多项式。一个( 丹，i ) 循环码的每一个码字都可 以用一个次数小于等于甩一l 的多项式表示，其必处于以x 一一1 为模的某一剩余类 中。 定义2 2 2 ：若一个码的所有码多项式都是一个次数最低的非零首一多项式 g ( x ) 的倍式，则称g ( x ) 为该码的生成元或生成多项式。 定理2 3 ：g f ( q ) 上的( 刀，| i ) 循环码存在唯一的r = 刀一k 次首一多项式 g ( z ) a 定理2 4 ：( 甩，七) 循环码的生成多项式g ( 石) 一定是x ”一l 的因式，即 工“一1 = g ( x ) h ( x ) ( 2 - 1 6 ) 综上所述，不难得出如下结论： ( 1 ) ( 刀，七) 循环码的生成多项式是一个次数最低的唯一的首一多项式，其 次数，= n k 正好是校验元的位数。 ( 2 ) g ( x ) 是x ”一l 的因式。要构造一个( 丹，七) 的循环码，就要找一个 r = n - k 次首一多项式g ( x ) 。 ( 3 ) 循环码的每一个码多项式必是g ( z ) 的倍式。若用c ) 表示码多项式， 则有c 0 ) = 肌g - - - o m o d g ( x ) ；反之亦然。 2 2 2 循环码的编码原理 对于一般的( ，z ，k ) 循环码，需要找到一个多项式g c x ) ，对于系统码，前k 位 是信息元，后，位是校验元，将信息元左移，位，在右边放上校验元，且编码后 的码字所对应的多项式是g ( x ) 的倍式，即完成了编码( 下面将要介绍的b c h 码 1 4 南京师范大学硕士学位论文 和r e e d - s o l o m o n 码即是采用系统码的构造方法) 。 编码的表达式可表示为： c ( x ) = x ”r e ( x ) + r 【x n - k 肌( 功】 ( 2 1 7 ) 其中r e ( x ) = m s r _ l x h + 册一柚+ m i x + m o ，叫作信息多项式，m ( x ) 乘以x ” 相当于将信息元左移r ： 一七位。校验元对应多项式为： ，( x ) = 月 xn - k 脚( x ) 】皇x i - k 埘( 善) r o o dg ( 力( 2 - 1 8 ) 故必有： c ( z ) = x ”一m ( z ) + ，( x ) 暑0r o o dg ( x )( 2 - 1 9 ) 所以，循环码编码关键在于求生成多项式g ( 工) 。 设生成多项式g ( x ) = x 7 + g ，_ l 工“+ + g i 石+ g o ，g ，g f ( q ) ，它的全部的根 必在o f ( q ) 的扩展域g f ( q 。) 上。即g ( 石) 可在g f ( q 4 ) 上分解为： g = 一口l x x 一口2 ) o 一) o 一口，) ，口，eg f ( q 。) ，且都是 g ( x ) 的根。 2 2 3 循环码的译码原理 由于循环码是线性分组码的重要子类，所以循环码的译码方法与线性分组码 的相同，亦分为三步： ( 1 ) 根据接收向量r ( 计算伴随式s ( 习； ( 2 ) 根据s ( x ) 找出对应的错误模式昱( d ； ( 3 ) 将e ( 力与r ( 力相加( 或相减) ，得到码字的估计值仑( 工) 。 2 3h a m m i n g 码的介绍 h a m m i n g 码是1 9 5 0 年由汉明( 尼l 脱g ) 提出的，它是一种高效的能纠单 个错误的线性分组码。面对于线性分组码的定义以及它的编译码方法，我们在上 面几节已经作了详细的介绍，i - i a m i v f f n g 码的编译码方法是与之相同的，这里 我们就不做赘述，简要介绍一下h a m m i n g 码的特点以及它的常用类型。这里 我们只讨论定义在g f ( 2 ) 上的h a m m i n g 码。码字长度为刀，信息位长度为七。 南京师范大学硕士学位论文 我们知道，重量为l 的错误图样的特征就是校验矩阵目的某一列。如果日的 每一列都不相同，且不为零。所以，每一个重量为1 的错误图样所对应的特征都 不相同，且不为零。所以，每一个重量为l 的错误图样都是可以纠正的。反之， 如果每一个重量为1 的错误图样都是可以纠正的，则日的每一列都不相同，且 每一列都不为零。如果要设计一个能纠正所有l 位错误，同时对任何大于1 位的 错误都不能纠正的线性分组码，则校验矩阵目的列由所有长度为r = r - k 的不 为零的列向量构成。综上所述，对于h a m m i n g 码，具有以下特点： 对于任一整数棚：r b 3 ； 监督码元数目： r = m ； 码长：r = 2 ”- 1 ； 信息码元数日：k = 2 4 1 一m ； 最小距离：d m i n = 3 ； 纠错能力：t = 1 。 调整校验矩阵中列向量的排列顺序，可得到系统h a m m i n g 码，进一步研 表2 1 常用的循环h a m m i n g 码 m ( ，l ，i )g ( p ) 3 ( 7 ，4 ) p3 + p + 1 4( 1 5 ，1 1 ) p4 + p + 1 5 ( 3 1 ，2 6 ) p5+p 2 + 1 6 ( 6 3 ，5 7 ) p6+p+1 究表明，h a m m i n g 码等效于循环码，循环h a m m i n g 码是一种b c h 码，循 环h a m m i n g 码的多项式是n - k 次的本原多项式。常用的循环h a m m i n g 码 如表2 1 所示，h a m m i n g 码的性能良好，既具有较高的可靠性，又具有较高 的传输率，而且编译码电路较为简单，易于工程实现，因此得到广泛应用。 2 4b c h 码的介绍 b c h 码是一类二元的并可纠正多个随机错误的循环码，它由彳 h o c q u e n g h e m ，兄cb o s e 和d 足r a y - c h a u d h u r i 于1 9 5 9 年和1 9 6 0 年分别提出， 并以此三个发现者的名字命名。b c h 码是迄今为止研究得最为详尽、了解得最 1 6 南京师范大学硕士学位论文 为透彻、取得成果最多的一类线性分组码。 b c h 码具有严密的数学结构，在代数编码理论中起着重要作用。该码的生成 多项式g ( x ) 与最小距离d = 2 t + 1 之问有着密切的关系，因此可以根据纠错能力 t 的要求，很容易地构造出相应的码。在中等码长和短码长的情况下，b c h 码 的性能接近理论上的最佳值。由于它良好的性能，因此被广泛地应用在各种差错 控制系统中。 2 4 1b c h 码的基本概念 定义2 4 1 ：设口为g f ( 2 ”) 中本原元，t 为整数，则以含有口，口2a 3 ，口2 共2 f 个根，其系数在o f ( 2 ) 内的最低多项式g ( x ) 为生成多项式的循环码，叫作 二元本原b c h 码，简称本原b c h 码，本章中只讨论二元的本原b c h 码。 因为g ( ) = 0 ，1 f 2 t ，所以g ( 工) 的全部根为口，口2 ，口3 ，口2 以及它的共 轭根系令掰，为口。的最小多项式，则g ( x ) 必是所l ( x ) 9 f r l2 ，m2 f ( 力的最 小公倍数，可知： g ( x ) = l c m m 1 ( 工) ，m 2 ( x ) ，坍2 ，( x ) 】 ( 2 - 2 0 ) 因为共轭根系每个元素的最小多项式均相同，所以上式还可以化为： g ( x ) = l c m m l ( 功，m3 ( 功，m 弘i ( 工) 】 ( 2 2 1 ) 本原b c h 码的码长为刀= 2 “- 1 ，校验位数为，= r l - k = o o g ( x ) 2 t + l ，纠错能力至少为f 。由式( 2 - 2 1 ) 可知，本原b c h 码的一致校验 矩阵为 日= 口”一i 口。 3 ) ”1 3 广2 ；i ( 口2 “1 ) ”1 2 “1 ) 州 ( 2 2 2 ) 找到生成多项式，就可以根据式c ( 功= x “呶力+ rb “m 】进行编码。 2 4 2b c h 码的编码原理 b c h 码的编码的重点就是找到它的生成多项式g ( x ) ，而求g ( x ) 的关键在 1 7 南京师范大学硕士学位论文 于找出每一个根的最小多项式。在本文所涉及到的b c h 码的编码方法的步骤如 下： ( 1 ) 根据m 值，生成本原多项式g ( 功； ( 2 ) 构造有限域g f ( 2 。) ； ( 3 ) 根据输入的纠错能力t 值，计算最小距离d ； ( 4 ) 找出口的最小多项式m ，( 功，其中1 f s 2 t ； ( 5 ) 根据最小多项式求生成多项式g = 朐f 晒。( 破m ，o 唬，朋2 t - i o r ) 】； ( 6 ) 根据式( 2 1 9 ) c ( x ) = x n - k 历( 工) + r x ”删( z ) 】进行编码。 2 4 3b c h 码的译码原理 b c h 码的译码原理与循环码的相同，主要分为以下几个步骤： ( 1 ) 计算接收向量r ( 功的伴随式： 其中， s = ( s ，s ：一：，) = r h 7 置= r ( a 4 ) s e ( 口。) m o d g ( x ) 1 i s 2 t 令口的最小多项式为m a x ) ，则有 r ( x ) = q j ( x ) 掰f ( x ) + 岛( x ) 0 0 p i ( x ) 0 0 m f ( x ) 所以 s f = r ( a 1 ) 2p ，( 口) r o o dg ( x ) ( 2 ) 从s 中求错误位置多项式a c x ) ； ( 3 ) 求解仃o ) 的根，并找出错误的位置。，夕2 ， 的尺( 力。 2 5r s 码编译码 ( 2 - 2 3 ) ( 2 - 2 4 ) ( 2 2 5 ) ( 2 2 6 ) 并纠正与之相应位 r s 码2 3 1 全称为r e e d - s 0 1 0 m o n 码，是z r e e dgs o l o 肌d 订在1 9 6 0 年发现 的，同年，尼c b o s e ，di f r a y c h a u d h u r i 和a h o c q u e n g h e m 发现了b c h 码。 南京师范大学硕士学位论文 1 9 6 1 年，d cg o r e n s 地i n 和z i e d e r 注意到r s 码是一类特殊的b c h 码，其位 置域和符号域是同一个域。r s 码是迄今为止所发现的码中一类很好的线性纠错 码类，它具有很强的纠错能力，尤其在短码和中长码下，它的纠错性能接近于理 论值。而且他的构造比较方便，编码结构也比较简单，编译码的设备也不算复杂。 这是综合以上几种优点，它在工程中被广泛地应用。 2 5 1 有限域的概念及实现 域“”是由加法和乘法两种运算的一些元素组成，在每种运算下都有逆元素存 在，因此域中同样有减法和除法运算，所以我们可以通过加上或乘以该元素的逆 元来实现和该元素的减法和除法，构成域的元素必须满足以下几个条件： ( 1 ) 域元素对于定义在该域上的运算：加法和乘法满足封闭性。即任何两个 域元素的和或积仍然是该域的元素。 ( 2 ) 对于每种运算，各元素满足通常的结合律和交换律。 ( 3 ) 乘法和加法见满足分配率。 ( 4 ) 域内对于加法运算具有加法逆元和加法恒元。即对于任意域元素置，存 在加法恒元0 满足：k + 0 = 置，加法逆元一彪，满足置+ ( 一足) = 0 。同时，域内 存在加法恒元l ，和对非零元素存在乘法逆元，即k 1 = k ，k x j 一= l ( k 0 ) 。 域内元素的数目叫做域的阶，记为g ，可为有限或者无限。有限域又称伽罗 华域，记为g f ( q ) ，g f ( q ) 的一个重要特点是每个有限域至少包含一个叫做口 的本原元素，该元素的( o g - 2 ) 次幂就是这个域中g 一1 个非零元素，他们之 问互不相等。因此g f ( q ) 内所有域元素可以表示为( o ，l ，口，口2 ，口p 2 ) ( 口q - i = 口o = 1 ，因为域元素的周期等于域的的特征q ，口的级为g - 1 ) 由于r s 码的编译码运算通常定义在特征为q = 2 “的域上，同时计算机数据 存储及计算都是基于二进制的数据，因此碍为2 的幂指数，对于实际使用是很方 便的。由于域上共有日个元素，对应于所有m 维空间上的矢量元素。在进行域 元素的加法运算时，通过将域元素转换成二进制数据进行异或，然后再转化成对 应的域元素保存。进行域元素的乘法时，选用本原元指数形式来表示每个域元素， 这样域元素问的乘法就变成了本原元指数的加法，然后对域的阶口一l 求模得到 1 9 南京师范大学硕士学位论文 了两者相乘的结果，此时的结果还是以本原元指数的形式保存的，可以再通过相 应的表格映射到二进制或者十进制数据。 2 5 2r s 码的编码原理 r s 码1 4 1 的编码原理及编码器的实现比较简单，而译码相对而言要复杂的多， 就r s 码的编译码技术而言，存在时域和频域两种算法，其中时域算法产生比较 早，也已经很成熟，应用比较广泛。本文主要讨论的是基于时域的编译码方式， 并将此编码方法运用在后面级联码的设计中。 r s 码的时域编码主要围绕码的生成多项式g c x ) 展开，对于能纠正t 个错误 的r s ( ，l ，k ，d ) 码，具有以下特征： ( 1 ) 码长：n = 2 。一l ： ( 2 ) 信息位长度：k = 万一2 t ； ( 3 ) 校验位长度：2 t = n k ； ( 4 ) 码字最小距离：d = 2 t + l = 万一k + l ： 最小距离等于d 的本原r s 码的生成多项式为： g ( z ) = ( x 一口m ) ( x 一口静“) ( x 一口埘+ 2 ) ( x 一口埘+ d 一2 )( 2 2 7 ) 其中：m 是一个任意整数，一般情况下我们取m = l ，则生成多项式可写为 g ( x ) = ( x 一口) ( x 一口2 ) ( x 一口3 ) ( 置一口2 )( 2 2 8 ) 下面对信息符号进行编码，首先信息符号的多项式可以表示成： s ( x ) = 口o + x + 口2 x 2 + 吼一l x 一1 ( 2 - 2 0 ) 其中口。为g f ( 2 ”) 域元素。 将信息多项式乘以多项式x ”一。除以生成多项式，将得到的余式和乘以x ”- k 后的信息多项式相加就得到了编码后的码字多项式。用公式表示为： 等- 口( 小等g 蹦式) ( 2 _ 3 0 ) gt 工j【xj 编码后的的码多项式为： c ( x ) = 石n - k s ( z ) + ，( x )( 2 - 3 1 ) 2 0 南京师范大学硕士学位论文 2 5 3r s 码的译码原理 r s 码的译码方法和其它线性分组码的译码步骤大致上都相同的，基本上可分 为三步：( 1 ) 通过接收到的码字r c x ) 计算伴随式s ；( 2 ) 由伴随式找出错误图样 e ( ，) ；( 3 ) 由r ( 曲一e ( 力得到最大可能发送的码字c ( x ) ，完成译码。 由于r s 码也属于循环码，所以，任何循环码的译码方法都适合r s 码。为了 提高它的译码效率，已经有两种比较好的专门译r s 的译码算法，它们是： ( 1 ) p e t e r s o n g o r e n s t e n - z i e r l 盯译码算法2 0 。 此算法在解构成错误位置多项式系数的线性方程组的时候运算量很大，与系 数矩阵的结束的三次方成正比，码长较长，纠错能力较大时，计算量很大。而且 当实际错误远小于纠错能力时，计算量不但没有减小，反而增加。在很多实际应 用中，常常需要能够纠很多错误的码，因此这种算法在工程上不是很实用，在这 里我们就不作过多描述。我们主要讨论第二种译码算法：迭代译码算法，也是本 文主要采用的算法。 ( 2 ) b e r l e k a m p - m a s s e y 译码算法2 1 3 首先，定义错误位置多项式为： 人( 力= 兀l 一蝎= 1 + a t x + a2 工2 + + 人，x ( 2 3 2 ) 其次，定义构成错误位置多项式系数的线性方程组为： 墨最岛。瓯 s 2s 3s i s 。s 呲 s 3s s s s 州s 眦 ；j；ii s 。s 叭s m s s 却 a ，- l 2 ： a i 一。 一s 毗 一 ： 一 ( 2 - 3 3 ) 假设我们已经知道错误位置多项式( 2 3 2 ) 的系数，那么，从式( 2 - 3 3 ) 可以看出： 第一行用( s ，