（信息与通信工程专业论文）深空通信中rs码的编译码算法研究.pdf

霆防辩学技术大学疆究生院学徒论文 攘霎 本文主要慰农用挚瀑空信遂缓玛豹憝玛进行了獗究。首先铁翁遥续码静基零定理入 手论述了在肖干扰存在的信遒上进行光差镄传输的可能性，这是纠镄编码研究的理论依据 与努力方向。然后介绍了与纠错编码相关的代数基本知识，简单介缁几种常见的纠错编码 码澄，熏点研究了r s 码的辩域编译礴算法，并对其体参数的r s 码的编译码实现过程迸 行了分糖，农建立埝姿豹瘩道摸涎鲍蒸础上对r s 弱性熊遂弦莹寞分瓣，避一步提港了 r s 码频域编译码方法；在文章第三部分中对卷积码与t u r b o 粥做了简单地介绍，文章最 后简单论述了深空通信的信道特点，对国外现有的编译码系统进行了介绍与比较，并在此 基础主针对我国其体蓬情与现实需要撵出。r 这个谍邋即将采用的方粲。 【关键词】：深空通债纠错编码r s 码卷积码t u r b o 码髂道模型 频域时域 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t t h i sw o r km a i n l yi n v e s t i g a t e st h er sc o d e si nt h ed e e ps p a c ec o m m u n i c a t i o n f i r s t l y ，w ei n t r o d u c et h eb a s i ct h e o r yo ft h ec o d i n ga n dd e c o d i n go ft h ec h a n n e l w h i c hd e s c r i b et h ep o s s i b i l i t yo ft h ee r r o r l e s st r a n s m i s s i o ni nt h ec h a n n e l e x i s t i n gi n t e r f e r e n c e i ti st h ef o u n d a t i o nt h e o r ya n dh e a d i n ga s p e c to ft h e c o r r e c tc o d i n g ：t h e nw ei n t r o d u c es o m ec o r r e l a t i v ea l g e b r a i cd e f i n i t i o n s 、 t h e o r e m sa n ds o m ef a m i l i a rc o d e si nb r i e f ，s t r e s s i n gi n r p o r t a n c et od i s c u s s i n gt h e a l g o r i t h mo ft h et i m e f i e l dc o d i n ga n dd e c o d i n g i nt h i sp a p e r ，i ta n a l y s e st h e r e a l i z a t i o np r o c e s so ft h er sc o d ew i t hc e r t a i np a r a m e t e r c o n t e m p o r a r i l yw es e t u pf e l i c i t yc h a n n e lm o d e lt os i m u l a t ea n dt oa n a l y s et h ep e r f o r m a n c eo ft h ec o r r e c t r sc o d e s a d v a n c e d l yw eb r i n gf o r w a r dt h ec o d i n ga n dd e c o d i n gm e t h o di nt h e f r e q u e n c yf i e l du p o nr sc o d e s i nt h et h i r dp a r ti ti n t r o d u c e st h ec o n v o l u t e da n d t u r b oc o d es i m p l ya n da tt h el a s tp a r to ft h ep a p e r ，w ei n t r o d u c et h e s p e c i a li t y o ft h ed e e ps p a c ec h a n n e la n dc o m p a r et h eu s e dc o d i n ga n dd e c o d i n gs y s t e mi nt h e f o r e i g nc o u n t r i e s ，t h e nw eb r i n gf o r w a r dt h es c h e m ew h i c ho u rw o r k i n gg r o u pw il1 a d o p t 【k e yw o r d s1d e e ps p a c ec o m m u n i c a t i o n ； c o r r e c tc o d e s ； r e e d - s o l o m uc o d e s ；c o n v o l u t e dc o d e s ；t u r b oc o d e s ； c h a n n e lm u d e l s ；f r e q u e n c yf i e l d ；t i m ef i e l d 第1 i 页 璧鍪整兰茎鲞盔兰登茎兰堡兰垡笙耋。 图目录 潮i l 奏疆域巾鹣加、乘洼运算。，。，。3 豳l 一2 线性分组码的编码4 圈l 一3 最小距离与纠检错能力的关系5 嘲1 - - 4系统码，7 戴l 一5 奇鼹授骏绽璐。，。8 攒t 一6势蟹交织编码。1 3 嗣l 一7 两级缀联码系统1 4 图2 一lr s 码的编码电路1 9 爨2 - - 2r s 译码嚣原理框图。，。2 l 鬻2 - - 3 g f ( 1 6 ) 域中计算，钕3 ) 的电路。2 5 豳2 4r s 编译码系统框图2 7 鲻2 5纠错码蠢寨仿真模型。3 2 鬻2 5 二遴囊 对稼薅遥8 s 昏+ ，。，。，。，3 2 澍2 7 三态分群辩a r k o v 模型，3 3 圈2 - - 8 b ，与肆，。的关系曲线3 7 粥2 9傍囊滚摆圈。，。，。3 8 翻2 - - 1 08 s ( 3 1 ，1 5 ) 码霉，与稍兼系。4 0 圈3 1 编译码瓣硬件框图4 l 隧3 2i l s 编码嚣的结梅。，。4 2 甏3 3 憝缓璐嚣模凌r s - e n c o d e r 。4 3 圈3 4 伴随式求解电路。4 3 豳3 5 计算错误能嚣多项式的嗽路，4 5 稠3 6c b i e n 搜索法电路。4 6 豳3 7 醛译码嚣块r s - d e c o d e r 。，。，+ 4 6 豳3 8 有限域g f ( 2 5 1 上元素的加法运算单蠢4 7 圈3 - - 9 一种3 缀流水线译码器的结构和时序5 2 蹦4 一l ( 3 ，l ，2 ) 豢积码编码擞。：。5 4 黼4 2 卷积鹅缀褥器。辐 翻4 3t u r b o 码编码原理圈6 0 圈4 4t u r b o 码译码原理图6 l 囝4 5 串行级联码。6 3 爨4 6 潺台缀联豢襄酶。6 3 第i i i 页 国防科学技术大学研究生院学位论文 表目录 表1 1r s 码的基本参数1 2 表2 - - ig f ( 2 3 ) 上的元素2 0 表2 - - 2 求错误位置多项式盯( z ) 表2 - - 3 完成k s 译码需要的运算量 表2 4 骼( 3 1 ，1 5 ) 码纠错性能的仿真结果 表2 - - 5r s 码对随机错误的改善 表2 6r s 码对突发错误的改替 表5 - - 1b 2 1 i l - 卫与b 3 | i c d 译码器性能 第i v 页 孙 n 的盯 独创性声明 本人声明所呈交的学位论文是栽本人在导烯指导下进行的研究工作及墩褥 的研究藏果。尽我掰知，除了文串特魏 加瑷称注和致谢的蟪方外，论文孛不包合 其他人融疑发表和撰写= 过的研究成聚，也不包含为获得国防科学技术大学或其它 教弯惑掬鹣学位鬟证书褥靛蕉遘酶糖精。毒羲一麓_ 譬稼戆嚣惑对本霹究辫散酶经 何贡献均巳在论文中佧了明确的说明并表示谢意。 学像论文题爱邃塞遗整章是基签烫骝鏊基竭塞。 学位论文作者签名：盈i 塞日期：；强乎年月j j 日 学位论文版权使用授权书 本入宠全了解溪掰释学技术夫学有关豫留、便弼学位论文魏规定。本入授粳 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 交整，允诲论文藏查粪察猎阕；胃蒎章摹学位论文魏全部或部分海鏖鬃入鸯美毂器 库进行襁寨，可以采用影印、缩印戚扫描等复制筝段保存、汇编学位论文。 像爨学位论文糖簿塞后遥鼹本授毂书，) 学位论文题目： 巨l i 瘟照l ji i 趁凝簿瑾藿茏豳筵 学侏论文作者篓露：选技舞期：e 年f f 月眵鞋 肆鬻指导蔑舜签名：匐耋萎 ： 疆期：w 年if 蘑，i 弱 国防科学技术大学研究生院学位论文 第一章绪论 1 1课题的提出 随着我国空间技术的发展，以及确保我国在未来空间研究中紧跟世界先进水平，进一 步提高我国的综合国力，目前有必要开展深空探测领域的研究。由于深空探测与一般的空 间通信不同，具体实现涉及到很多关键技术的研究，其中重要的一点就是深空探测中信道 编译码方案及实现的研究。 本文首先介绍了信道编码的基本理论，重点研究了r s 码编、译码的算法，对r s 码编 译码过程中的运算量进行了分析，针对具体的r s 码阐述了编译码过程，并对其性能进行 了仿真与分析，提出了基于谱技术的编译码方法；并简单介绍了卷积码与t u r b o 码，文章 最后在借鉴国外目前实用的深空通信系统所采用的信道编译码方案的基础上，针对未来深 空通信编译码技术的发展方向，根据深空通信的信遒特点和我国未来深空探测系统的要求 提出了我国未来深空探测系统应采用的编译码方案以及即将努力的方向。 1 2信道编码理论 本节主要介绍编码的一些基本理论：信道编码定理、有限域、线性分组码、循环码、 b c h 码、r s 码等几种重要的码以及交织码和级联码。这些内容也是本文在后面将详细讨论 的纠错码方案设计的理论基础。 1 2 1 信道编码定理 s h a n n o n 在其经典论文“am a t h e m a t i c a lt h e o r yo fc o 彻m n i c a t i o n s ”中指出：如果 系统的传信率小于信道容量，则选择适当的编码技术可以实现可靠通信。 s h a n n o n 采用信源和信道的概率模型，将信息可靠传输的基本问题归结为以下公式： c = w l o g ：( 1 + 二) s 1 - 1 其中，c 代表信道容量，信道容量是指单位时间内信道上所能传输的最大信息量；w 代表带宽：s n 代表信噪比( 信号与噪声功率比) 。这就是著名的s h a n n o n 公式。由此， s h a n n o n 建立了对信息通信的基本限制，引出了信道编码定理。 信道编码理论可以简单地描述为：如果信源的信息速率r 小于c ( r c ，则不管在发送端和接收端采用了多少信 号处理措旌，都不可能达到可靠传输；如果一- - m ，差错概率将接近于0 。 第1 页 国防科学技术大学研究生院学位论文 由公式 i - i 可以得到这样的结论： l i 提高信噪比s n 可以增加信道容量c 。 2 当噪声功率斗0 的时候，信道容量c 趋于0 0 ，这表明在无干扰时的信道容 量为o o 。 3 增加信道带宽w 并不能使信道容量c 无限制地增加。当噪声为高斯白噪声的时 候，随着w 增大，噪声功率n = w n 。也随之增大( 其中为噪声的单边功率 谱密度) 。在公式 卜1 两边同时取极限有： ，l i r a c = l i r a w l o g z ( 1 + 黝 = 旷s _ _ l i r a 。等1 0 8 2 0 + 书 ：旦l 。g ：口 。1 4 4 旦 卜2 一o 4 可见，即使信道带宽w 无限增大，信道容量c 仍然是有限的( c 蔓1 4 4 。) 。 5 信道容量c 一定的时候，信道带宽w 与信噪比s n 之问可以彼此互换。 信道编码定理证明了最佳编码方法的存在性，纠错码理论则是为寻找最佳编码方法而 发展起来的。 1 2 。2 有限域 有限域( f i n i t ef i e l d ) 在编码理论中具有重要的地位。包括有限个元素的域称为有限 域或g a l o i s 域，通常把具有q 个元素的有限域记为g f ( q ) 。每个域中必须包含一个零元 素0 和一个单位元素e ，最简单的域是二元域g f ( 2 ) 。一般地，若口是素数，可构成一个 由元素f 0 ，1 ，q - 1 组成的g 元域g f ( q ) 。对任何正整数m ，可以将g f ( q ) 扩展成 g f ( q ”) ，称之为g f ( d 的扩域；反之，称g f ( q ) 为g f ( q ”) 的基域。 在有限域g f ( q ) 中，加、乘运算定义为模窖运算，记为r o o d ( q ) 。例如，域g f ( 7 ) 中的 加、乘运算如图1 一l 所示。 第2 页 国防科学技术大学研究生院学位论文 口 oi 234 5 口o 1 2 ， 4 ， 6 1123蠢56o 223 45 01 ， 3 一 ，o ，2 56 d l 2 3 s5 鑫 1 234 65 ol2 3 4 5 量 矗l2345 od o 0 o00 o l 0 i23456 2 e24五l，s 3036 25i4 叠e4 t 5263 5 t5 耋 l再2 o6， 一 32t 图l l 有限域中的加、乘法运算 在域g f ( q ) 中，满足，l e = 0 的最小正整数n 称为域的特征。域中一切非零元素的特征 都等于域的特征，且域的特征一定为素数。非零元素构成的乘法群的阶定义为域中该元素 的级。若口为域g f ( q ) 中的疗级元素，则称口为厅次单位原根。若某一元素口的级为q 一1 ， 则称口为本原域元素。 域的特征表明了域中加法运算的循环性，而域的级则表明了域中乘法运算的循环性。 为便于后文叙述，在此介绍几种多项式。 域上多项式：即系数取自域g f ( q ) 上的多项式f ( x ) 。在编码理论中，域上多项式的概 念是比较有用的。 既约多项式：设f ( x ) 是次数大于零的多项式，若除了常数和常数与本身的乘积以外再 不能被域g f ( q ) i - 的其他多项式除尽，则称f ( x ) 为域g f ( q ) 上的既约多项式。 最小多项式：系数取自域g f ( g ) 上，且以口为根的所有首一多项式( 即最高次数的系数 为1 的多项式) 中，必有一个次数最低的，称之为口的最小多项式。 本原多项式：系数取自域g f ( q ) 上，且以域g f ( q ”) 上本原域元素为根的最小多项式， 称为本原多项式。 1 2 3 线性分组码： 线性分组码( l i n e a rb l o c kc o d e s ) 是分组码中最重要的一类码，是讨论各类码的基础。 第3 页 里堕型兰垫查查兰堑塞生壁堂堡垒壅 未编码数据流 图l 一2 线性分组码的编码 把信息划分成k 个码元为一段( 称为信息位) ，通过编码器编成。r 1 个码元一组，作为 n ， k 线性分组码的一个码字。若每位码元的取值有窖种( q 为素数幂) ，则有q 。个码字。n 长 的数组共有q ”组，在二进制情况下，有2 ”个数组。显然，矿个斗维数组( 一重) 组成了一 个g f ( q ) _ j z 的，l 维线性空间。如果矿( 2 ) 个码字集合构成了一个k 维线性子空间，则称它 是一个 n ，k 线性分组码。一个行重的线性分组码可用矢量来表示( e _ ，c o 。c ：，c i ，c o ) 。 它的编码过程如图1 2 所示。 线性分组码有三个重要的参数：散w 和d 。 r = k n 表示在码字中信息位所占的比重，称为编码效率或编码速率，简称码率。它表 明了信道利用的效率，故也称为传信率。r 越大，表明码的效率越离或传信率越高。 w 是码字的h a m i n g 重量，简称重量或h 重，表示码字中非零码元符号的个数。在线 性分组码c 中，非零码字重量的最小值，叫做c 的最小重量，表示为： 矸孟= m a n 矽( c ) ，c 。c ，c 。 1 3 3 在 n ，k 】线性分组码中，两个码字u 、v 之间对应码元位上取值不同的符号个数，称 为码字u 、v 之间的h a n u n i n g 距离，简称距离或h 距，用d ( u ，v ) 表示。距离具有对称性 ( d ( c t ，c ：) = d ( c 2 ，c t ) ) 、非负性( d ( c i ，c 2 ) o ) 和满足距离三角不等式 ( d ( c ，c ，) s d ( c l ，c 2 ) + d ( c 2 ，c 3 ) ) 这三个性质。任意两个码字之间距离的最小值，称为码 的最小距离“。若c 和c 是任意两个码字，则码的最小距离可以表示成： d 晌= m i l l d ( c “，c 7 ) i , j = 0 , 1 2 - 1 1 4 码的最小距离d 。是衡量码抗干扰能力的重要参数，码的d 。越大，码的抗干扰能力 越强。如果一个线性码能检出长度f 个码元的任何错误图样，则称码的检错能力为f ；如 第4 页 国防科学技术大学研究生院学位论文 果线性码能纠正长度，个码元的任意错误图样，则称码的纠错能力为t 。 码的最小距离d 坩m 和纠检错能力的关系如下： “n ，k 线性码能纠正t 个错误的充要条件是码的最小距离氏。= 2 ，+ 1 ，如 图l 一3 a 所示。 n ，k 线性码能检出，个错误的充要条件是码的最小距离d 。= “1 ，如图1 - - 3 - b 所示。 n ，k 线性码能纠正t 个错误并发现f 个错误( f t ) 的充要条件是码的最小 距离( = “- ，+ 1 ) ，如图1 3 一c 所示。 图l 一3 最小距离与纠检错能力的关系 在线性分组码中，生成矩阵、校验矩阵和伴随式的概念对于编码和译码是很重要的。 分别叙述如下： 生成矩阵：在由 n ，k 线性分组码构成的线性空间的k 维子空间中，一定存在k 个 线性独立的码字：g 。，g ：，g 。那么线性分组码中其他任何码字c 都可以表示成这k 个码 字的一种线性组合，即： c = m i _ l g l + 。m i 一2 9 2 + + m l g 一i + f o 兽i 1 5 式中m 。g f ( q ) ，i = 0 , 1 , - - - k l 。将公式 卜5 写成矩阵形式得： 第5 页 鼯搿粤撕 国防科学技术大学研究生院学位论文 c?=cf。，f。一：，-“】r兰 = 犯 式中， m k + 坂。m o 】是待编码的信息组，g 是一个七x ，阶矩阵 g = g l 9 2 ： g i l g g l i 9 2 1 ： g i i l g i l 9 1 p 1 一 9 2 ，1 g j m 一1 g h 一1 卜6 卜7 g 中每一行岛= 匮。，9 1 2 , g 。】都是一个码字。对每一个信息组m ，由矩阵g 可以求得 n ，k 线性分组码对应的码字。因而，矩阵g 生成了 1 1 ，k 线性分组码，所以矩阵g 称为 n ，k 线性分组码的生成矩阵。 校验矩阵：对 n ，k 线性分组码，每个码字中的，( ，= t l 一七) 个校验码元和k 个信息码 元之间的关系可以由下面的线性方程组确定： 啊l c 。一l + 魄2 c n 一2 + + 啊。c o = 0 l 。一_ l + 。+ + 一2 0 d - 8 ： 一l 巳一l + 以2 一2 + + k c o = 0 令上式中的系数矩阵为h ，码字矩阵为c ，即： 日= 啊。啊： - 啊。一，啊 如，k。红。 ： 以_ l l 以吐2 h r _ 一lt l m 以。珥： k 一k ， c = 【c 。l ，c m ，c o 】 1 9 故可以将公式 1 - 8 写成： i i c 7 = 0 7 ，c h 7 = 0 卜1 0 式中h 称为校验矩阵或监督矩阵。 1 i ，k 线性分组码的g 和h 之问关系密切，满足以 下关系： h g 7 = o r , , k ，g i - 1 7 = 0 1 1 1 因此，线性分组码的生成矩阵g 和校验矩阵h 的行向量彼此正交。 若信息组以不变的形式出现在码组的任意k 位，通常是前面k 位为信息位，后面 ，= , 一七位为校验位，则称之为系统码，其结构如图1 - - 4 所示。否则，称为非系统码。 第6 页 国防科学技术大学研究生院学位论文 、， 系统码 图1 4系统码 易推知，系统码的生成矩阵g 和校验矩阵h 的形式分别为： g = 【 ，p 】 卜1 2 h = 卜p 7 ，l 一。】 ( 其中p 为j j 一k ) 阶矩阵) e 1 1 3 通常称公式 卜1 2 和 1 - 1 3 中的g 和h 为码的标准生成矩阵和标准校验矩阵。 伴随式：当收到一个接收码字r 以后，可以用校验矩阵h 来检验r 是否满足校验方程， 即：h r 7 = 0 7 是否成立。若关系式成立，则认为r 是一个码字；否则，判为码字在传输中 发生了错误。因此，h r 7 是否为0 是检验码字是否出错的依据。把s = r h 7 或s = h r 7 称 为接收码字r 的伴随式( 校验子或监督子) 。 它具有下述几个特点： 伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图 样决定。 噼随式是错误的判别式：若s = 0 ，则判为无错，接收的是一个码字；若s 0 ， 则判为有错。 不同的错误图样具有不同的伴随式，它们是一对应的。 在线性分组码中，有一类比较简单而又常用的编码一奇偶校验码。 奇偶校验码属于 n ，n 一1 线性分组码，其编码规则是：首先将要传送的信息分成组， 然后将各位二进制信息及校验位用模2 和相加。选择正确的校验位，保证模2 和的结果为 0 或1 。其中，为o 时称为偶校验；为1 时称为奇校验。如图1 5 所示，设码组长度为n ， 表示为( 口h ，口柑，a l ，吼) ，其中：这n 一1 位为信息位，口这l 位为校验位，这种 校验关系可以用公式表示： 第7 页 国防科学技术大学研究生院学位论文 图1 5 奇偶校验编码 偶校验时有：a os a lo s a o a = 0 ，校验码元a 可以由公式 a = a oo 口to s a 。4 产生n 奇校验时有：a oo a lo o 巳一2s a 。_ 1 = l ，校验码元d 。1 可 以由公式一i = a o a io 0 。20 1 产生。 由于这种奇偶校验码的最小码距以。= 3 ，只能够发现单个或奇数个错误，而不能检 出偶数个错误，因此它的检错能力并不高。 1 2 4 循环码 循环码( c y c li cc o d e s ) 是一类重要的线性码。 一个e n ，k 线性分组码c ，若它的一个码矢心+ f ，c l ，c o ) 的i 次循环移位 ( - l - 。，c + c l ，c 0 ，_ l ，c ，o 一) 都是c 的一个码字，则称c 是一个循环码。 它具有以下的性质： 具有严谨的代数结构，其性能也易于分析。特别是目前已经发现的大部分线性 码和循环码都有着密切的关系，大部分的线性码都可以归结为循环码。 具有循环特性，这可以采用反馈移位寄存器( f s r ) 来实现，编译码电路特别是 编码电路简单而易于实现。 因此循环码非常引人注目，对它的研究也比较深入和系统。 通常用多项式来表示循环码。将码矢表示成多项式的形式，即码元多项式c “) 为： c ( 曲= 矗1 x ”1 + 氏_ 2 石”一2 + c i x - c o 1 - 1 4 其i 次循环移位所得的码矢也用多项式表示为 第8 页 国防科学技术大学研究生院学位论文 c ( x ) = c n - | - i x ”一+ c 一2 一，苫”一2 + + c l x 。+ 。+ 由公式 卜1 4 乘以一再除以x ”+ 1 得 卜1 5 等= 巳_ 1 x t - ! + q _ 2 x i - 2 - i p 。， c n - t - i x ”_ 1 + c 。一卜2 x 护2 + + c o 一+ c 。一i 兰二! + 二c 盟 + 1 珥一。1 x h + ，+ g 等 叶阃 由此可知：c ( 曲的i 次循环移位c ( 工) 是c ( x ) 乘以x 后再除以x ”+ 1 的余式。即： c ( x ) = x c ( x ) m o d ( x “+ 1 ) 1 1 7 因此，循环码码矢的j 次循环移位等效于将码多项式乘一再模r + l 。 根据循环码的循环特性，可由一个码字的循环移位特性得到其他的非零码字。在 n ， k 循环码的2 。个码字，取其前k - 1 位皆为0 的码字g ( 力( 其次数为r = n k ) ，在经过k 1 次循环移位后，总共得到k 个相互独立的码字：g ( n 昭( 珐x “g ) ，可作为码生成矩阵 的k 行，于是得到 n ，k 循环码的生成矩阵6 ( x ) ： g ( 力= x k - i g ( x ) x k - 2 9 ( x g ( x ) g ( x ) 卜1 8 码的生成矩阵一旦确定，码就可以确定。这表明： n ，k 循环码可以由它的一个 r ( r = n k ) 次码多项式g ( x ) 来确定。每一个码多项式都是g ( x ) 的倍式，每一个是g ( x ) 倍式 且次数s n l 的多项式都是码多项式。多项式g ( x ) 称为码的生成多项式： g ( x ) = x ”一+ j f - i j “叶一1 + + 蜀z + g o 1 1 9 生成多项式g ( x ) 具有以下的性质： 在 n ，k 循环码中，生成多项式g ( x ) 是唯一的( n - k ) 次多项式，且 次数是最低的。 在 r l ，k 循环码中，每个码字多项式c ( x ) 都是g ( x ) 的倍式，而每个 第9 页 国防科学技术大学研究生院学位论文 为g ( x ) 倍式且次数0 一1 ) 的多项式必为一个码字多项式。 r l ，k 循环码的生成多项式g ( x ) 是r + 1 的因式，即x ”+ 1 = h ( x ) g ( x ) 。 若g ( x ) 是一个( n - k ) 次多项式，且为x “+ 1 的因式，则由g ( x ) 可以生成一个 r l ， k 循环码。 1 2 5 b c h 码 1 9 5 9 年h o c q e n g h e m 以及1 9 6 0 年的b o s e 和c h a u d u r i 发现了b c h 码，b c h 码纠错能力 强，构造方便，编译码简单，有快速的译码算法。这类码具有严格的代数结构，在编码的 理论和实际中都起着重要的作用，也是迄今为止研究得撮为详尽、分析得最为透彻和成果 最为丰富的码类。 b c h 码的循环结构是由p e t e r s o n 在1 9 6 0 年所证明的。1 9 6 7 年，b e r l e k a m p 提出了b c h 码的迭代译码算法，从而将b c h 码由理论研究推向实用阶段，使它成为一类应用广泛而有 效的线性码。 给定任一有限域g f ( q ) 及其扩域g f ( q ”) ，其中g 是素数或素数之幂，m 为某一正整 数。若码元取自g f ( q ) 上的一个循环码，它的生成多项式g ( x ) 的根集合r 中含有以下万一1 个连续根： r i 缸“，口“，口“2 1 - 2 0 则由g ( x ) 生成的循环码称为g 进制b c h 码。 其中，口g f ( q ”) 是域中的n 级元素，口“g f ( q ”) ，( o f 占一2 ) ，m 。是任意整数， 但对于常见的情况，取= 0 或1 ，则称这类b c h 码为狭义b c h 码。 设m ，( x ) 和p ，分别是口m o + t o = o ，l ，2 ，8 - 2 ) 元素的最小多项式和级，则可得b c h 码的 生成多项式g ( 曲和码长n 分别是： g ( x ) = l c m m o ( x ) ，m 1 ( x ) ，m # 一2 ( x ) 1 2 1 一= l c m e o ，8 1 一e 卜2 2 式中，l c m ( ) 表示求取最小公倍数。 如果生成多项式g ( x ) 的根中有一个g f ( q ”) 中的本原域元素，则n = g ”一1 ，称这种 第1 0 页 国防科学技术大学研究生院学位论文 码长r = q ”一1 的b c h 码为本原b c h 码。否则，为非本原b c h 码。 在实际中应用的最多的是二进制b c h 码，其码元取自g f ( 2 ”) 中。取m 。= l ，占= 2 t + l ， 又设口是g f ( 2 ”1 上的本原域元素，若以口，a2 ，a 3 ，口2 。为根二进制b c h 码的生成多项式： g ( x ) = l c m m l ( x ) ，m 2 ( x ) ，m 2 ，( x ) ) 1 2 3 其中m 。( 曲是口。( 1 茎f 2 t ) 的最小多项式，该b c t t 码能纠正t 个错误。 二进制8 c h 码具有这样的性质：对于任何正整数m 和t ，一定存在一个二进制8 c h 码， 它以口，口3 ，o f 2 t - 3 口2 “1 为根，其码长r 是2 ”一1 或者是2 ”一l 的因子，能纠正t 个随机错 误，校验位数目至多为饱( = m t 。 将二进制b c h 码的概念进行扩展可以得到多进制b c h 码。因为码元符号取自二元域 g f ( 2 ) 、纠t 个错误的二元b c h 码的生成多项式是以g f ( 2 ) 的扩域g f ( 2 ”) 上2 t 个相邻元 素为根的多项式。那么，多元b c h 码的码元符号取自多元域g f ( q ) ，其中口为某一素数或 素数之幂，而纠正t 个错误的多元b c h 码的生成多项式是以g f ( q ) 的扩域g f ( q “) 上2 t 个元素为根的多项式： g ( 工) = ( x 一口) ( 工一口2 ) ( x 一口2 ) 1 2 4 式中，口，口2 ，口2 为g f ( q ”) 中的2 t 个相邻元素。 多元b c h 码的校验矩阵为： h = o f ”l 位2 ) “ “2 ) ”1 似“) ”1 卜2 5 式中，口为g f ( q 1 ) 的本原元：码长刀= q 4 1 ；d 为设计距离，d = 2 t + l 。由g ( x ) 确定 的b c h 码是g 元本原b c h 码。 r s 码是多元b c h 码的一种特例，即取m = l ，故r s 码的生成多项式的根和码元符号在 同一域上。下面将讨论r s 码。 第1 1 页 0 ；n n 墨：簿 国防科学技术大学研究生院学位论文 1 2 6 r s 码 r e e d - - s o l o m o n 码首先是由r e e d 和s o l o m o n 两人于1 9 6 0 年提出来的，简称为r s 码。 这是一类具有很强纠错能力的多进制b c h 码，既能纠正随机错误也能纠正突发错误，也是 一类典型的代数几何码。r s 码一直以来都是国际通信领域研究的热点之一。 定义：在g f ( q ) 上，码长玎= g 一1 的本原b c h 码称为r s 码。 纠正t 个错误的r s 码有如下的参数，见表1 1 。 码长 一= g “一1 信息位长 七 检验位长 珂一后= 2 t 字符长 ，行 最大纠错个数 ， 最小距离 d n = 2 t + i 表i - - ir s 码的基本参数 r s 码的最小汉明距离d 。= 2 t + l ，因此它是最大距离可分码( m i ) s 码) ，也就是说：在 所有的线性分组码中，r s 码具有最大的最小汉明距离，所以它的纠错能力是最强的。 当q = 2 ”时，码元符号取自有限域g f ( 2 ”) 上，此时码元符号可以表示成相应的二元 数组，与通常所用的二进制序列对应。因此，o f ( 2 。) 上的r s 码是一类应用相当广泛的 r s 码。 在g f ( 2 ”) 上纠正t 个错误的r s 码的生成多项式为： g ( 曲= ( x 一叻( x 一口2 ) ( x 一盯2 ) 1 - 2 6 其中，岱g f ( 2 “) ，i = 1 , 2 ，2 t 。 r s 码由于具有优良的纠错能力两得到广泛的应用。比如：在军事通信中常以r s ( 3 l ， 1 5 ) 作为首选码。在深空通信中则常以r s ( 2 5 5 ，2 2 3 ) 作为标准码。在c d - - r o i 等存储系统 中也多采用r s 码作为纠错码。目前的高清晰度电视( h d t v ) 系统中通常用r s 码作为其级联 码的外码，例如在大联盟h d t v 方案中选用的是r s ( 2 0 7 ，1 5 7 ) 。 除了作为纠错码，r s 码在其他方面还有许多应用。比如：它可以作为一种最佳的跳频 序列族而用于跳频通信系统中。还可以用来构造某些密码系统。 第1 2 页 国防科学技术大学研究生院学位论文 1 2 7 交织码 大多数用来提高信息传输可靠性的码在信道错误满足统计独立时使用起来是很有效 的；但对于一些具有突发性错误的信道，采用交织( i n t e r l e a v e ) 技术不失为一种简单而有 效的办法。 j 奄飙i 矗出翻d 图1 6 分组交织编码 交织主要有两种：分组交织和卷积交织。这里只讨论分组交织，其一般原理是：交织是 将输入信息序狲按行写入一个所x 甩矩阵中，然后按列读出。编码数据经交织器重新排序 以后在信道上传输。去交织是交织的逆变换，是在接收端解调以后将接收到的信息也存放 到m x 的矩阵中，然后按行读出。如圈1 - - 6 所示。 由于交织去交织的效果，突发错误在肘问上被扩展，于是每个码字上的错误显得独 立了。对给定的一个 n ，k 码，通过分组交织变成一个 m n ，m k 码，即将码长和信息元扩 大了m 倍，通常定义交织度为i ( 这里：i = m ) 。 显然，当且仅当每行中的错误图样是原码中可以纠正的错误图样时，该错误图样对整 个阵列来说才是可以纠正的。长为m 的突发错误无论从哪一位开始，都至多影响每行中的 一位。因此，若原码能纠正长为t 或者更短的任何单个突发错误，则交织码将可以纠正长 为m t 或更短的突发错误。如果 n ，k 码具有最大可能的纠正突发错误的能力，则交织后 的 m n ，i n k 码也具有最大可能的纠正突发错误的能力。把具有最大可能的纠正突发错误能 力的短码进行交织，就能构成实际上任意长的、具有最大可能的纠正突发错误能力的码。 所以，可以认为交织技术是把寻求长而有效的纠突发错误码变成寻求短的好码。 1 2 8 级联码 信道编码定理指出，随着码长的增加，译码错误概率按指数接近于0 ，因此，为了使 码有效就必须使用长码。但是，随着码长的增加，在一个码组中要求纠错的数目相应增加， 第1 3 页 国防科学技术大学研究生院学位论文 译码器的复杂度和计算量也相应增加，以致难以实现。为了解决性能与设备复杂度之间的 矛盾，f o r n e y 于1 9 6 6 年提出了级联码( c o n c a t e n a t e dc o d e s ) 的概念，把编制长码的过程 分成几级来完成，通常分成两级。 级联码不仅有极强的纠正突发错误和随机错误的能力，更重要的是利用级联码的构造 方法，能达到信道编码理论所给出的码限，也就是能构造出渐进好码( s h a n n o n 码) 。 图1 7 是一个两级的级联码的差错控剖系统。该级联码由内码c ，和外码c 。组成。 内码c j 是6 f ( 2 ) 上的一个 n ，k 码，外码e 是g f ( 2 。) 上的一个 n ，k 码，并按照以下的 方法进行编码： 图1 7 两级级联码系统 1 把k k 个信息码元，划分成k 段，每段k 个码元。 2 把一组有k 个信息码元的段，看成是g f ( 2 ) 上的一个符号( 元素) 。将k 个符 号按照外码c 。的编码规则编成一个码字。码长为n ，有k 个信息符号， n k 个校验符号，最小距离为以，码率为矗。= 。 3 再把外码e 的每一个符号，看成是k 个二进制码元的信息组，输入内码c ，的 编码器，得到内码的一个码字。它的码长为n ，有旷k 个校验元，最小距离为 喀，码率为焉= ，由此得到 n ，k 内码的n 个码字序列。因此，总共有砌 个二迸制码元、 兰个信息元，组成了【胁，凰，畋，或】级联码的码字。 可知，两级级联码是一个 协，触，以，d 二进制线性分组码，码率r 。= r 。r ；。级联码 的译码采用分级处理：先按内码e 的译码规则，得到n 个有k 个码元组成的符号后，再送 入外码译码器，按外码e 的译码规则译码，最后得到k 个信息符号，每个符号含有k 个 二进制信息元。所以，最后由外码译码器输出的是经过纠错的鼢：个信息元。 第1 4 页 戮防辩学技术天学研究生院学位论文 1 2 9 本章小结 本章穷绣了编码理论熬一些基磕翔谖。蓄先奔终了 言遵编鹨定溪，然螽讨谂了线性努 级码、循环码、b c h 码、r s 码、交织码以及级联码等几个重要的檄念。在此基础j ：，从下 一章起将介绍本文的主要工作。 国防科学技术大学研究生院学位论文 第二章r s 码的编译码方法 2 1有限域上的运算 域是由加法和乘法两种运算的一些元素组成，在每种运算下都有逆元素存在，这就说 明有减法和除法的另外两种运算存在。域f 内同时满足加法与乘法运算的各个元素需要满 足以下条件： 1 ) 对这两种运算来说，f 是封闭的，即f 内任何两个元素之和或积仍在f 内； 2 ) 对每种运算，各元索满足通常的结合律和交换律； 3 ) 满足通常的分配律； 4 ) f 内的任何元素u 都有一个唯一的加法恒元0 和一个乘法恒元1 ，满足以下关 系： h + 0 = “ “1 = 7 5 ) 域内每个元素u 都有一个唯一的加法逆元一”，有： “+ ( 一“) = 0 当站0 时，有一个唯一的乘法逆元“。存在，有： 域内元素的数目叫做域的阶，可为有限或无限。有限域以g f ( q ) 表示，q 是域内的元 素数目，也称为伽罗华域。对任何的p “，都存在一个有限域g f ( p ”) ，这里p 是素数，m 为整数。有限域最简单的一个例子是素 g f ( p ) ，它由全部模p 的整数集合组成，p 是 任何大于1 的一个素数，加法与乘法运算都是模p 的。g f ( 2 ) 是最简单的素域，它只含有 0 与1 的0 元和1 元。产生加法恒元所需的乘法恒元相加的是最低数目，叫做域的特征。 g f ( p ”) 的特征是p 。 有限域的一个重要性质是每个有限域g f ( q ) 至少要包括一个叫做口的本原元素。该元 素的q - 1 次幂数都是这个域中