（电子科学与技术专业论文）基于宽带多媒体通信卫星的rs编译码器设计与实现.pdf

国防科技大学研究生院学位论文 a b s t r a c t r sc o d eh a se x c e l l e n tc a p a b i l i t yi nc o r r e c t i n gb u r s t i n ge r r o r s r sc o d ec a n r e m a r k a b l yi m p r o v et h er e l i a b i l i t yi nc o m m u n i c a t i o n so fm u l t i m e d i as a t e l l i t ew h e ni t i n t e r l e a v e sa n dc o n e a t e n a t e s 、忻t l lv i t e r b ia so u t e rc o d e n o w , m a n yc o m m u n i c a t i o n s t a n d a r d sa d o p tt h ec o n c a t e n a t e dc o d e so fr sa n dv i t e r b i f o r s a t i s f y i n gt h e r e q u i r e m e n to fm u l t i m e d i as a t e l l i t e ，w eh a v es t u d i e dt h ea l g o r i t h mo fr se n c o d i n g d e c o d i n g ，t h et e c h n i q u eo fr si n t e r l e a v e sa n dc o n c a t e n a t e sw i t hv i t e r b i a n da l s ow e h a v ec o m p l e t e dt h eo p t i m i z a t i o nd e s i g na n dr e a l i z a t i o no fe n c o d e r - d e c o d e r m a i nw o r k a n de f f o r t si nt h i st h e s i sa r el i s t e da sf o l l o w s 1 t h o u g h t f u la n a l y s i so fr se n c o d i n ga n dd e c o d i n ga l g o r i t h m s a f t e rc o m p a r i n g b ma l g o r i t h m 研t he u c l i d sa l g o r i t h ma tc o m p l e x i t y , w eg e tt h ef i r s ti sb e t t e r w eh a v e s t u d i e df o m e ya l g o r i t h m ，ai m p l e m e n t a t i o nm e t h o dh a sb e e np r o p o s e da f t e ra n a l y z i n g t h ec o m p l e x i t yo fi n v e r s eo p e r a t i o ni nf o r n e ya l g o r i t h m 2 o p t i m i z a t i o nd e s i g na n dr e a l i z a t i o no fr s ( 2 4 4 ，2 12 ) e n c o d e r b a s e do ns t u d i e d t h et h e o r yo fl o wc o m p l e x i t yb i tp a r a l l e la r c h i t e c t u r e sf o rp o l y n o m i a lm u l t i p l i c a t i o n o v e rg f ( 2 5 ) ，ah i g hs p e e d ，l o wd e v i c eu t i l i z a t i o ng e n e r a lm u l t i p l i e ra n df i x e dm u l t i p l i e r h a v eb e e nd e s i g n e da n dr e a l i z e d t h ec i r c u i to fe n c o d e rh a sb e e ng i v e n b e s i d e s ，a n i m p r o v e dc i r c u i ts t r u c t u r eo ft h ee n c o d e rh a sb e e np r o p o s e d o nt h i sb a s i s ，w eh a v e d e s i g n e da n di m p l e m e n t e dar s ( 2 4 4 ，2 12 ) e n c o d e ri nv e r i l o gh d l t h es y n t h e s i z e d r e s o u r c e su t i l i z a t i o no ft h ee n c o d e ri s2 8 5s l i c e si nx i l i n xi s e9 1iv e r t e x 2 p ，a n dt h e m a x i m u mt h r o u g h p u tc a nb ea c h i e v e d2 0 g b p s 3 o p t i m i z a t i o nd e s i g na n dr e a l i z a t i o no fr s ( 2 4 4 ，2 12 ) d e e o d e r t h ec i r c u i to f s y n d r o m em o d u l e ，k e ye q u a t i o nm o d u l e ，e r r o r - l o c a t i o na n de r r o r - v a l u em o d u l eh a v e b e e ng i v e n t h ek e ye q u a t i o nm o d u l ec o m p l e t e sam u l t i p l yo p e r a t i o nb yt w o s t e p m u l t i p l i c a t i o n t h e r e f o r e ，n e a r l yh a l fo ft h eg e n e r a lm u l t i p l i e ri sr e d u c e d a f t e r a n a l y z i n gt h et i m i n go ft h r e em o d u l e s ，w eh a v ep r o p o s e dt h r e e - s t a g ep i p e l i n ef o rr s d e c o d e r b a s e do nt h i sm e t h o d ，w eh a v ed e s i g n e da n dr e a l i z e da r s ( 2 4 4 ，212 ) d e c o d e r i n v e r i l o gh d l t h em a x i m u mt h r o u g h p u tc a nb ea c h i e v e d1 4 g b p s ， a n dt h e s y n t h e s i z e dr e s o u r c e su t i l i z a t i o ni s18 3 2s l i c e si nx i l i n xi s e9 1iv e r t e x 2 p 4 s t u d ya n dd e s i g no fr si n t e r l e a v e sa n dc o n c a t e n a t e sw i t h t e r b i w eh a v e s t u d i e dt h ec o n c a t e n a t e dc o d e s a n dh a v ea n a l y z e dt h eb e n e f i to fa d d i n gi n t e r l e a v i n gi n t h ec o n c a t e n a t e dc o d e s c o m p a r i n gw i t hs e v e r a li n t e r l e a v i n gm a t r i xi ne x p e r i m e n t s ，w e g e ta no p t i m a li n t e r l e a v i n gm a t r i xw h i c hi s 12 8 x6 1m a t r i x o nt h i sb a s i s ，w eh a v e d e s i g n e da n di m p l e m e n t e da ni n t e r l e a v e d c o n c a t e n a t e d c o d e sw h i c hi sa c c o r d s 、析t i l t h et d mc a r d e rc o m m u n i c a t i o ns y s t e ms t a n d a r do fu s e rl i n k i nm u l t i m e d i a c o m m u n i c a t i o ns a t e l l i t e k e yw o r d s r sc o d e ，b ma l g o r i t h m ，e u c l i d sa l g o r i t h m ，f o r n e ya l g o r i t h m 第i i 页 国防科技大学研究生院学位论文 图1 1 图2 1 图2 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 l 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图目录 典型的卫星数字通信系统组成框图1 有限域元素2 3 3 与2 0 2 相乘图9 g f ( 2 8 ) 域求逆的电路图2 3 通用乘法器电路图。2 8 r s ( 2 4 4 。2 1 2 ) 编码器电路图2 9 改进后的编码器电路图3 0 r s ( 2 4 4 ，2 1 2 ) 编码器引脚图3 l 编码器引脚时序图3 2 编码器仿真测试图a 3 3 编码器仿真测试图b 3 4 译码流程图3 7 伴随式电路图。4 0 伴随式计算模块时序图4 1 伴随式模块仿真图4 2 计算r r ( x ) 流程图4 3 解关键方程电路图：4 4 移位寄存器图4 5 解关键方程模块时序图。4 6 解关键方程模块测试仿真图。4 7 解错误位置和错误值模块电路图4 8 解错误位置和错误值模块时序图4 9 解错误位置和错误值模块测试仿真图5 0 流水线结构图5 1 译码器时序图51 译码器测试仿真图5 3 单级级联码组成图5 5 ( 五，而，五9 5 2 ) 交织图5 7 r s ( 2 4 4 ，21 2 ) 与v i t e r b i 交织级联图5 9 v i t e r b i 与r s 级联前后及交织级联的性能比较图6 0 1 去码率卷积码删除法得到码率卷积码图。6 1 z 4 t d m 载波组帧图6 1 第v 页 国防科技大学研究生院学位论文 第v i 页 国防科技大学研究生院学位论文 表目录 表2 1 ( 7 ，3 ) 循环码和( 6 ，3 ) 循环码1 0 表2 2以x 4 + x 2 + 1 为模的g f ( 2 4 ) 的元素11 表3 1g ( x ) 的系数。2 4 表3 2 编码模块接口说明。3 2 表3 3编码器资源占用表3 4 表4 1 译码器资源占用表5 3 表5 1t d m 载波帧速率参数6 2 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 基王宽堂垒搓垡通焦里星鲍垦墨编竖璺墨遮进皇塞趣 学位论文作者签名：他锄9 扇日期：砌口占年j 1 月谚日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 国防科技大学研究牛院学何论文 第一章绪论 1 1 课题的意义及应用背景 随着信息技术的发展，通信距离不断扩大和通信速率不断提高，如何保障传 输可靠性特别是卫星通信的高速准确成为当前紧迫的课题。图1 1 是典型的卫星数 字通信系统的组成框图i l l ，信息经过处理通过信道传输会产生错误，可靠的数字通 信系统必须将差错率控制在允许的范围内。因此，为了保证通信成功就必须尽量 减少信道干扰对信息估值的影响。通常有两个方法来解决这个问题：一是增加信 噪比，另一个即采用纠错编码1 2 , 3 , 4 1 。而在实际的通信系统中如果单纯以第一种方 法来提高信息传输可靠性的代价比较大，特别在卫星通信中轨道每瓦功率的费用 比较昂贵。纠错编码技术是提高信息传输可靠性的一种重要手段。随着编码理论 和大规模集成电路技术的发展，纠错编码技术日趋成熟，编译码设备变得比较容 易实现，成本也比单纯的提高信噪比节省很多，因此纠错编码技术在实际数字通 信中逐渐得到更广泛的应用。 图1 1典型的卫星数字通信系统组成框图【1 1 纠错编译码设备是数字卫星通信系统的重要组成部分，它能够显著改善传输 信道的误码性能。在国际卫星通信地球站中，对于中速率数据载波( i d r ) ，无论在 t c m i d r 或q p s k i d r 方式下，都采用级联编码方式，即外码+ 交织+ 内码的编码 方式，其中外码采用里德一所罗门码( 简称r s 码) ，内码采用v i t e r b i 码，这样随机 错误和突发错误都能有效纠正，大大降低了误码率。r s 码是b c h 码中的一个重 要子类，具有优秀的纠正突发差错能力，因此在无线通信和磁、光介质存储系统 中有着广泛的应用，特别在高清电视和卫星通信领域1 5 1 占有重要地位。目前，国 内外r s 译码器仍然是研究的热点，特别是算法简化、低复杂度【6 】、低延迟、低功 第1 页 国防科技大学研究生院学何论文 耗等方面备受关注。 近年来，随着f p g a 技术的发展，在f p g a 中构建r s 编译码器已经成为新的 热点，出现了可定制的f p g a 核( i pc o r e ) ，可以根据不同的需要，选定不同的参数， 方便地移植到不同的设计应用中，并且性能越来越高。目前许多f p g a 供应商都 推出了自己的r s 译码器核，为工程应用提供了方便。 根据项目需求，需要设计一个快速多进制并且能够纠正突发错误的编译码器 作为宽带多媒体通信卫星发射机与接收机纠错系统的外码，并与内码级联。该多 媒体通信卫星采用用户链路t d m 载波通信体制【7 1 ，该体制参考c c s d s 推荐的深 空探测的标准级联码，外码采用r s ( 2 5 5 ，2 2 3 ) 的缩短码r s ( 2 4 4 ，2 1 2 ) ，内码采用卷积 码，总体采用r s + 交织+ v i t e r b i 交织级联编译码技术。本课题基于乘法器的优化设 计与算法的优化选择完成了r s ( 2 4 4 ，2 1 2 ) 编译码器的v e r i l o g 设计实现，并与v i t e r b i 2 编译码器交织级联，误码率在码率等于；、信噪比等于5 1 时为8 5 1 0 。6 ，达到 4 了卫星通信的需求。 1 2 国内外发展情况 r s 码是由r e e d 和s o l o m o n 在1 9 6 0 年通过论文“p o l y n o m i a lc o d e o v e rc e r t a i n f i n i t ef i e l d s ”所提出的1 8 1 。在提出的初期，当时的数字电子技术却未能够根据r s 码的有关内容做出相应的实际应用。为什么在这段时间里没法获得有关的实际应 用，而对于同样的r s 码纠错码理论又能够在现代的数字电子技术领域里发挥如此 重要的作用呢? 其中的主要原因在于把r s 码有效地推向实际应用的关键技术一有 效的r s 码译码算法未能得到实质性的突破。尽管在1 9 6 1 年已经存在了可行的r s 码译码算法，即p g z 算法，但是无论是当时还是现在，该算法的复杂性都不适合 通过数字电子技术的实现来开展有效的应用。然而，到了1 9 6 5 年，由e b e r l e k a m p 以及j m a s s e y 提出的有效译码算法【9 川最终为r s 码的实际应用解决了最后的障 碍。 在r s 算法不断改进的过程中，随着微电子技术的发展，使得r s 译码算法的 硬件实现成为可能，从而推动了r s 译码器结构的研究和发展，8 0 年代中后期， 对r s 编译码器的研究达到了高潮，并且用v l s i 方法实现了r s 译码器。1 9 8 4 年， l i u t l l l 将r s 译码器分成五个部分，采用流水线的处理结构，使得r s ( 2 5 5 ，2 2 3 ) 译码 速率达到4 m b i t s 。随着e d a 综合工具的发展，对r s 编译码器的研究重点转移到 了如何高速有效的硬件实现上来。 经过4 0 多年的发展，国外r s 编译码技术已比较成熟，在许多不同的国际标 准中得到了相应规定，如c c s d s 、i e e e 8 0 2 1 4 a 、i e e e 8 0 2 1 4 b 、w c d m a 、 第2 页 国防科技大学研究生院学位论文 v s b 、i m t 2 0 0 0 、d v b 以及d v d 等。r s 码在数字存储设备( 硬盘，c d ，d v d ) 、 无线通信系统( 移动电话，微波中继) 、数字电视( d v b ) 、卫星通信( 包括深空 通信系统) 、宽带调制解调( a d s l ，x d s l ) 等领域中已广泛应用。生产r s 译码 器的公司很多，但由于r s 码的种类繁多，根据不同的标准有r s ( 2 4 4 ，2 1 2 ) 、 r s ( 6 9 ，5 3 ) 、r s ( 3 1 ，1 5 ) 等，不同的顾客根据自己的需求选择不同的码型，所以大多 数公司采用商品化的i p ( i n t e l l e c t u a lp r o p e r t y ) 核实现，但是其价格不菲，这些公司 主要是f p g a 生产厂商，如a l t e r a 、x i l i n x 和l a t t i c e 公司。新加坡的i n f o c o m m 实 验室提出的r s ( 2 5 5 ，2 3 9 ) 译码器【1 2 】在x i l i n xv i r t e x i ix c 2 v 1 0 0 0 上最高时钟频率能 达到1 5 0 m h z ，电路规模为1 1 9 0 个s l i c e ，其最大可纠错位数为t = 8 位。 随着我国航天事业的日益发展，卫星、载人航天等技术己居于世界前列，对 于卫星等通信可靠性的要求也日益迫切，我国在1 9 9 6 年颁布广播电视数字传输技 术体制、决定采用符合d v b s 标准的数字电视卫星广播系统，标准中采用r s 码 作为外码。在航天工作中，r s 码在许多不同的任务中发挥了重要作用，比如实践 5 号 1 3 1 、神州3 号、神州4 号、神州5 号以及探测l 号等任务。 r s 码作为性能优异的纠错码，被国内许多院校及科研院所列为重点研究对象。 目前多数主要还是用v h d l 和v e r i l o g 语言实现再用f p g a 验证，很少做到a s i c 实现。 上海交通大学电子工程系李高志提出一种高速度流水线型r s 解码器【1 4 1 ，该 解码器在b m 原理基础上加以改进后更适宜用硬件描述语言( v h d l ) 来描述，并用 f p g a 来实现，时序仿真表明该解码器的最高时钟频率为3 0 m h z 。西安交通大学 电信学院吴飞提出流水线全并行有限域乘法器【l5 1 ，有效解决了传统译码器的速度 性能瓶颈。在新的译码器架构基础上，设计了r s ( 2 0 4 ，1 8 8 ) 译码器的门级电路，用 x i l i n xv i r t e x l ix c 2 v 1 0 0 0 进行了实现和仿真，获得了理想的成果。然后采用v e r i l o g 硬件描述语言描述电路，综合得出门级网表，并用f p g a 实现并验证，所设计的 r s ( 2 0 4 ，1 8 8 ，8 ) 译码器的工作时钟频率是1 0 7 m h z ，数据处理速率为8 3 5 m b p s 。 1 3 课题研究的主要内容 多媒体卫星发射机与接收机纠错系统设计方案为r s 码+ 交织+ v i t e r b i 码，本课 题要实现的r s 码将作为纠错系统的外码，该项目的研究是为了实现卫星通信中信 息的可靠传输。卫星通信网络承载的信息类型包括业务、信令和网管三大类，所 有信令、网管和业务信息全部打成5 3 字节长的a t m 信元后在网络内传输，全速 率时信道信息速率为1 6 6 8 5 2 m b p s ，调制符号速率为8 3 4 2 6 m s p s ；本课题紧紧围 绕多媒体卫星发射机与接收机纠错系统【1 6 1 对r s 码的需求，通过对乘法器的优化 设计和对算法及体系结构的的优化选择，完成了r s ( 2 4 4 ，2 1 2 ) 编译码器的设计与 第3 页 国防科技大学研究生院学何论文 实现，并完成了r s 与v i t e r b i 的交织级联。 课题主要完成以下工作： 1 、完成算法的研究并选择了适合本编译码器的算法，主要有b m 算法研究、 欧几里德算法研究、钱搜索和f o m e y 算法研究以及f o m e y 算法中求逆的研究。 2 、根据低复杂度位并行体系结构多项式有限域乘法器原理，设计实现面积小、 速度高的通用乘法器和5 6 个固定因子乘法器。 3 、完成并改进了r s ( 2 4 4 ，2 1 2 ) 编码器的r t l 级设计，并用v e r i l o g 语言对其进 行了实现与仿真。 4 、完成r s ( 2 4 4 ，2 1 2 ) 译码器的r t l 级设计，用两步乘法完成一次乘法运算的 方法减少通用乘法器的数量，优化了其体系结构，实现三级流水，并且用v e r i l o g 语言对其进行了实现与仿真。 5 、研究级联码的特点及级联码加交织的作用，对交织进行分析，根据宽带多 媒体通信卫星用户链路t d m 载波通信体制标准选择了四个编码块形成一个交织 块，并设计了交织矩阵，完成r s ( 2 4 4 ，2 1 2 ) 码与卷积码( v i t e r b i ) 的交织级联，分 析了交织级联码的性能。 1 4 论文组织结构 全文的内容共分六章。 第一章是绪论，介绍课题的背景和研究的主要内容。 第二章简单介绍有限域及循环码基本理论，对b m 算法、欧几里德算法、钱 搜索和f o m e y 算法以及f o m e y 算法中求逆的进行了研究并选择了改进的b m 算 法、钱搜索和f o m e y 算法来实现本编译码器。 第三章基于低复杂度位并行有限域乘法器原理，并根据有限域加法的特性， 设计实现并优化了g f ( 2 8 ) 域的通用乘法器和固定因子乘法器；并详细叙述了 r s ( 2 4 4 ，2 1 2 ) 编码器的设计与实现，说明了对编码电路体系结构的改进，最后给出 m o d e l s i m 测试仿真与x i l i n xi s e9 1 i 综合结果。 第四章详细叙述译码流程及三个模块的设计与实现，给出3 个模块的电路实 现，重点说明两步乘法完成一次乘法运算的方法及其对体系结构的优化，给出了 三级流水的实现方法，最后给出m o d e l s i m 测试仿真与x i l i n xi s e9 1 i 综合结果。 第五章基于对级联码的研究阐述了r s ( 2 4 4 ，2 1 2 ) 码与v i t e r b i 的交织级联，分析 了交织级联码的性能并给出了其在宽带多媒体通信卫星中的应用。 第六章是结束语，对所做的工作做了总结，展望下一步的工作。 第4 页 国防科技大学研究生院学位论文 第二章r s 编译码基础与算法研究 r s 码是一种循环码，是b c h 码的优秀子类，b c h 码是二进制有限域循环码， 而r s 码则是多进制有限域循环码，在信道编码中属于前向系统纠错码。为了更清 楚的了解r s 码的编码，本章首先介绍了信道编码、有限域和循环码m 1 的基本理 论；然后对编译码算法进行了研究，有b m 算法、欧几里德算法、钱搜索和f o m e y 算法，并将b m 算法和欧几里德算法进行了比较，选择了适合本编译码器的算法。 2 1 1 信道编码概述 2 1 信道编码 数字信号在信道的传输过程中，由于实际信道的传输特性不理想以及存在干 扰与噪声，在接收端往往会产生误码。为了提高数字通信的可靠性，首先应合理 设计基带信号，选择合适的调制解调方式及发射功率；其次应采用信道编码方式， 也称为差错控制编码 1 8 , 1 9 1 。信道编码能提高传输质量l 2 个数量级，可见它比制 造高质量的设备要经济适用。 信道编码的目的在于提高数字通信的可靠性，它加入冗余码用来减少误码， 其代价是降低了信息的传输速率，即以减少有效性来增加可靠性。信道编码增加 的冗余度是特定的、有规律的，以实现在发送端进行编码，在接收端进行译码， 纠正信道传输中由于各种噪声及电磁干扰而造成的误码。 2 1 1 1 差错控制的工作方式 差错控制的基本工作方式有4 种，分别是前向纠错( f e c ) 、检错重发( a r q ) 、 混合纠错( h e c ) 和信息反馈( i f ) 。文献 1 8 】中对其作了详细介绍。 在前向纠错系统中，发送端发送纠错码，接收端的译码器能自动发现和纠正 错误。其优点是需要单向信道，它能自动纠错，不要求重发，故实时性好。主要 缺点是传输的可靠性受设备的限制，即所需的纠错能力越强，编、译码设备越复 杂。 检错重发系统又称判决反馈或反馈重发。发送端发出检错码，通过前向信道 送往接收端，接收端译码器判决后将判决信号由反向信道送回发送端，重发有错 的信息，直至正确接收为止。它的优点是系统对译码器的设备要求不高，对突发 错误特别有效，但需要双向通信信道。 混合纠错系统可以认为是前向纠错系统和检错重发系统的结合。当接收端收 到少量错码时，则直接通过译码器进行纠正，而当错误太多，超过了译码器纠错 第5 页 国防科技大学研究牛院学何论文 能力时，则采用纠错重发。这种方式能充分利用自订向纠错和检错系统得特点，获 得较好的综合性能。但需要双向通信信道和较复杂的译码设备以及控制系统。 信息反馈系统是接收端将接收的消息原封不动地送回发送端，由发送端将反 馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法原理和设备简 单，无须纠错编译码系统。缺点是需要双向信道，而且传输效率低、实时性差。 2 1 1 2 信道编码的分类 差错控制系统中使用的信道编码种类很多。文献【1 8 】中对其作了详细介绍。 按照差错控制编码的用途不同可以分为检错码、纠错码和纠删码。检错码可 以检测错误；纠错码可以纠正错误；而纠删码则同时具备检测错误和纠正错误的 能力，当发现不可纠正的错误时，发出错误提示或将其删除。 按照监督码元和信息码元之间的关系可分为线性码和非线性码。监督码元和 信息码元之间满足一定的线性关系，即满足一组线性方程，称之为线性码，反之 称为非线性码。 按照对信息元处理方式的不同可以分为分组码和卷积码。分组码的监督码元 仅与本码组的信息码元有关，它又可分为循环码和非循环码。而卷积码的监督码 元不仅与本码组的信息码元有关，还与前面的几个码组有约束关系。 按照码组中信息码元在编码前后是否相同可分为系统码和非系统码。编码前 后信息码元保持原样不变的称为系统码，反之称为非系统码。 按照纠正错误和检测错误的类型可分为纠正和检测随机错误码、纠正和检测 突发错误码、既能纠正和检测随机错误码同时又能纠正和检测突发错误码。 按照每个码元的取值可分为二进制码和多进制码。 2 1 2 信道编码的基本原理 信道编码的基本思想是在被传输信息中附加一些冗余码，即加一些监督码元， 利用附加码元与信息码元之间的约束关系加以校验，以检测和纠正错误。这种检 测错误和纠正错误的能力是用编码的冗余度来换取的。下面以四种编码为例简述 差错控制编码的基本原理【2 0 1 。 第一种：( 1 ，1 ) 码。要表示“红”和“黑”两种颜色只需要一位编码，即代码“l 表示“红 ，代码“0 表示“黑 。这种编码无冗余度，其效率最高，但同时它也 无抗干扰能力。 第二种：( 2 ，1 ) 重复码。增加了1 位冗余码，即码长为2 ，信息位长度为1 。如 果用代码“1 l ”表示“红 ，代码“o o 表示“黑 ，则传输过程中发生一位错误 时，即码字变为“1 0 或“0 1 时接收端可以检测到错误，但是不能判断发生错 误前“l o ”的正确码字是“1 l 还是“0 0 ”，所以它没有纠错能力。所以这种编码 第6 页 固防科技大学研究生院学位论文 对译码器的性能要求不高，仅限于检错重发系统。 第三种：( 3 ，1 ) 重复码。增加了2 位冗余码，即码长为3 ，信息位为1 。以代码 “1 1 1 表示“红 ，代码“0 0 0 表示“黑”，则传输过程中出现1 位错误时，即码 字变成“1 1 0 ”或者“1 0 1 或者“0 1 1 时，可以判断是“1 1 1 ”出现了一位错误， 同样如果码字变成“0 0 1 可以判断是“0 0 0 ”发生了一位错误，这时便可加以纠 正。如果传输过程中发生了两位错误，比如发送端发送“红”接收到的码字应为 “1 1 l 但发生两位错误变成“1 0 0 ”或者“0 1 0 ，则无法判断，由于它既不代表“红 也不代表“黑 ，所以可以检测到错误，但是无法判断究竟是“1 1 1 产生了两位错 误还是“0 0 0 ”产生了一位错误，这种情况下系统会把它当作产生了一位错误处理， 即译为“0 0 0 ”，所以无法正确纠正错误，只可以检测到错误的存在；也就是说该 编码可以纠正l 位错误，检测两位以内的错误。 第四种：( 7 ，1 ) 重复码。增加了6 位冗余码，以代码“1 1 1 1 1 1 1 表示“红，以 代码“0 0 0 0 0 0 0 表示“黑”，当信道传输过程中产生了低于或等于三位错误时， 比如产生三位错误将代码变为“1 1 1 1 0 0 0 或产生一位错误将代码变成“1 1 1 1 1 1 0 ” 时，可以判断错误并加以纠正，但是超过三个错误时，比如产生六个错误将代码 变成“1 0 0 0 0 0 0 ”时，系统无法作正确判断，去正确纠正错误，只能检测到有错误 发生，所以该编码可以纠正3 位以内的错误，检测6 位以内的错误。 由上面的例子可以看到，增加冗余码的个数，可以增加编码纠错、检错的能 力，检测错误的个数等于冗余码的个数，纠正错误的个数等于冗余码个数的一半。 2 1 3 信道编码的基本术语 码组( 又称码字) 中编码的总位数称为码组的长度，简称码长【1 8 l ，编码的每一个 元素称为码元。码组中“l ”码元的数目称为码组的重量，简称码重。 两个等长码组之间对应位上数字不同的位数称为码组的距离，简称码距，又 称汉明距离。在由多个等长码组成的码组集合中，任意两个码组距离的最小值称 为最小码距( 矾) ，它是衡量编码检错、纠错能力的重要依据。 在分组码中，传递信息的码元称为信息位，用于纠错、检错的冗余码元称为 监督位。分组码一般用( n ，k ) 表示，门是码长，k 是信息位长度，后者与前者的比 值称为编码效率尺。 2 2 有限域 2 2 1 有限域的概念 文献 1 8 】中对有限域作了详细介绍。 第7 页 围防科技大学研究生院学何论文 设g 是非空集合，并在g 内定义了一种代数运算，若满足下述公理： l 、有封闭性。对任意口、b g ，恒有口o b g 。 2 、结合律成立。对任意a 、b g ，有0 6 ) o c = a o ( 6o c ) 。 3 、g 中有一恒等元e 存在，对任意口g ，有口g ，使a op = p o 口= a 。 4 、对任意口g ，存在有a 的逆元a - 1 g ，使a oa 一= a o 口= p 。 则称g 构成一个群。若群g 中，对任何口、b g ，有a o b = bo a ，则称g 为阿 贝尔群( a b e l 群) 。其中运算“o ”可以是通常的乘法或加法。 非空元素集合f ，若在f 中定义了加和乘两种运算，且满足下述公理： 1 、f 关于加法构成阿贝尔群，其加法恒等元记为0 。 2 、f 中非零元素全体对乘法构成阿贝尔群。其乘法恒等元( 单位元) 记为1 。 3 、加法和乘法间有如下分配律：a ( b + c ) = a b + a c ( 6 + c ) 口= b a + c a 则称，是一个域。域中元素的个数称为域的阶，元素个数有限的域称为有限 域【2 l 】，用g f ( q ) 或e 表示g 阶有限域。有限域也称伽逻华( g a l o i s ) 域。 2 2 2 有限域的加法 有限域中的加法运算相当于逻辑代数中的异或运算，与无限域中运算大不相 同，对于无限域来说，偶数个1 相加可能会出现不等于零的情况，而对于有限域 来说，则结果一定是零。有限域的加法具有封闭性，即域中任意元素相加后得到 的结果仍是域中的元素。 例如在域g f ( 2 ) 中，域元素只有两个，域的阶为2 ，1 + 1 = 0 ，1 + 1 + 1 = 1 ，1 + 0 = 1 ， 1 + 1 + 1 + 1 = 0 ，从上面列出的式子和结果说明在g f ( 2 ) 域上，加法运算相当于逻辑运 算中的异或运算，每次运算的结果仍是域中元素。 在域g f ( 2 8 ) 中，域元素有2 8 个，从0 到2 5 5 ，域上的加法运算与g f ( 2 ) 域上 的相似，只是在g f ( 2 8 ) 域上，每个元素需要用8 位二进制数来表示。例如2 3 3 表 示为“1 0 1 0 0 1 ，1 表示为0 0 0 0 0 0 0 1 ，将两者相加，对应位异或得到的结果为 1 1 1 0 1 0 0 0 ，即2 3 2 ，从上面的例子可以清楚地看到，有限域中的加法运算非常简单， 实现也很方便，只要用异或门即可实现。 2 2 3 有限域的乘法 上面介绍了有限域的加法运算，有限域的乘法运算【2 2 1 也具有如同加法运算那 样优良的特性。下面具体介绍。 域中非0 元素所购成的乘法群之阶定义为域中元素的级。若口为域凹( g ) 中的 第8 页 国防科技大学研究生院学位论文 n 级元素，则称口为n 次单位原根。若在g f ( q ) 中，某一元素口的级为g l ，则称 口为本原域元素。 在有限域中，元素的个数为有限，所有非0 元素的全体构成一个有限乘群， 群中每个元素的级为有限。例如g f ( 2 ) 域中，非0 元素为只有l ，阶为2 ，级为l ， 1 1 = 1 ，l 0 = 0 。 在g f ( 2 8 ) 上，阶为2 5 6 ，非0 元素有2 5 5 个，分别是1 ，2 ，3 ，2 5 4 ，2 5 5 。 本原域元素为口，并且满足口2 5 5 = 1 ，下面以两元素相乘来介绍g f ( 2 s 1 域上的乘法。 取2 3 3 ( 1 1 1 0 1 0 0 1 ) 2 0 2 ( 1 1 0 0 1 0 1 0 ) 船1 1 0 1 0 1 10 0 三 0 0 0 0 0 0 0 0 1 l l0 lo o l 0 0 0 0 0 0 0 0 1 llo l0 0 l 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1l l olo o l 11 lo l0 0 l 1 0 0 1 0 0 0 0 l u il u l 0 图2 1 有限域元素2 3 3 与2 0 2 相乘图 图2 1 是有限域元素2 3 3 与2 0 2 相乘图，第一步为相乘，与二进制乘法一样， 各元素依次相与，得到8 组元素相加，与二进制乘法不同的是相加是有限域加法， 而不是普通的加法，即采用异或的方法进行。由上式得到的二进制数位数为1 5 位， 而域元素最多为8 位，超出了域的范围，需要对g f ( 2 8 ) 本原多项式取模，本原多 项式的概念将在下一节介绍，g f ( 2 8 ) 的本原多项式为x 8 + x 4 + x 3 + z 2 + 1 ，值为2 8 5 。 上面的乘法结果可以表示为x 1 4 + x 1 1 + 矿+ x 4 + x 3 + x ，对本原多项式取模后得到最 后结果为：1 6 1 ( 1 0 1 0 0 0 0 1 ) ，可见所得结果仍为域中元素。可以对多组域中元素进 行运算验证，有限域的乘法与加法一样具有封闭性。 2 3 循环码基本理论 一个长度为, ，有2 个码字的分组码，当其2 个码字构成域g f ( 2 ) 上所有n 维 向量组成的向量空间的一个k 维子空间时被称为线性分组码 2 3 1 。循环码 i s i 是线性 分组码的一个重要子类。有两个原因使得该码备受关注：一是通过带反馈连接的 移位寄存器，一般称为线性时序电路，该码的编码和校正子计算能够很容易地实 现；二是由于其具有固定的代数结构，所以能找到多种实用的方法对该码进行译 码。循环码有利于系统按照所要求的纠错能力来编码，并且性能优良，它不仅能 纠正独立的随机错误，而且能纠正突发错误。正因为如此，循环码被广泛的应用 第9 页 国防科技大学研究生院学何论文 于通信系统的差错控制中，在差错检测中的效果尤为明显。 2 3 1 循环码的特点 循环码通常表示为( 刀，k ) 的形式，其中，z 表示为总的码长，k 表示信息码元。 它除了具有线性分组码的一般特点外，最重要的是具有循环性。所谓循环性，是 指循环码中的任一码字循环移动一位后，仍为该循环码中的一个码字。表2 1 列出 了( 7 ，3 ) 循环码和( 6 ，3 ) 循环码【2 0 1 的所有码字。 表2 1 ( 7 ，3 ) 循环码和( 6 ，3 ) 循环码【2 0 i 编号 ( 7 ，3 ) 循环码( 6 ，3 ) 循环码 10 0 0 0 0 0 00 0 0 0 0 0 20 0 1 1 1 0 1 0 0 1 0 0 1 3 0 1 0 0 1 1 l0 1 0 0 1 0 4 0 1 1 1 0 1 00 1 1 0 1 1 51 0 0 1 1 1 01 0 0 1 0 0 61 0 1 0 0 l l1 0 1 1 0 l 71 l o l 0 0 11 1 0 1 1 0 81 1 1 0 1 0 01 1 1 l l l 从表中可知，( 7 ，3 ) 循环码有两个循环圈，一个是由编号为l 的全零码字组成的 循环圈，其码重( 码中l 的个数) w = o ；另一个是剩余7 个码字组成的循环圈，若从 编号为2 的码字开始，每次向左移动一位，可以得到如下的循环圈2 4 8 7 6 5 3 6 2 ，其码重为w = 4 。同样，可以