（通信与信息系统专业论文）rs码编译码方法及软判决译码应用的研究.pdf

西南交通大学硕士研究生学位论文第j 页 摘要 纠错码技术是信息论的一个重要分支研究纠错码是一项理论 性与实跤性均狠强的工作。r s ( r e e d s o l o m o n ) 码是差错控制领域中 一类重要的线性分组玛由于具有报强的纠错能力因而被广泛地 应用于各种现代通信系统中以满足对信道可靠性的要求。本文研 究了r s 码的编译码方法和软判决方法。 首先本文讨论了r s 码的代数译码算法，包括纠错能力比较小 的一般译码算法和适用于纠错能力强的迭代译码算法，并针对两种 特定码字r s ( 2 7 ，9 ) 和r s ( 5 4 ，1 8 ) 进行了具体编程实现。结果表明纠 错能力符合理论要求，分别可以达到纠9 个和1 8 个错误，并且误码 率也得到改善。此外在r s 码的编译码基础上讨论了增长码r s ( 1 6 ，1 2 ) 的编译码方法。 然后针对r s 码软判决译码进行了研究。因为软判决可以充分 利用输出波形信息，提高系统的编码增益，所以越来越受到人们的 重视。但是软判决译码比硬判决译码要进行更多的译码计算，复杂 度较高，从而限制了它的应用范围此外虽然已经存在多种软判。决 方法，但都是针对二进制情况没有考虑到非二进制的r s 码。本 文利用c h a s e 算法的思想，将软判决译码应用到r s ( 1 5 ，1 1 ) 码上，降 低了译码的复杂度。最好舶情况可以纠四个错误将原有纠错能力 提高了一倍编码增益也获得相应的增加。 关键词差错控制；r s 码；编译码；软判决 西南交通大学硕士研究生学位论文第l l 页 a b s t r a c t t h e t e c h n o l o g y o fe r r o rc o r r e c t i o ni sa n i m p o r t a n tp a r t o f i n f o r m a t i o nt h e o r y b o t ht h e o r ya n dp r a c t i c es h o u l db ek n o w nb yt h e p e o p l e w h or e s e a r c ho ne r r o r - c o r r e c t i n g c o d e s b e i n g a ni m p o r t a n t 1 i n e a rb l o c kc o d ei ne r r o rc o n t r o lf i e l d ，t h er e e d s o l o m o n ( r s ) c o d e h a sv e r ys t r o n gc a p a b i l i t yo f c o r r e c t i n gr a n d o ma n db u r s te r r o r s ，w h i c h i sw i d e l yu s e di nv a r i o u sm o d e r nc o m m u n i c a t i o ns y s t e m st os a t i s f yt h e r e q u i r e m e n to fc h a n n e lr e l i a b i l i t y a d d i t i o nt ot h em e t h o do fe n c o d i n g a n dd e c o d i n gr sc o d e s ，a na l g o r i t h mo fs o f td e c i s i o n d e c o d i n g i s p r e s e n t e di nt h et h e s i s t h ea l g e b r a i cd e c o d i n ga l g o r i t h m sa r er e s e a r c h e d ，a n ds u c ha st h e c o m m o na l g o r i t h mf o rt h ec o d e sw h o s ee r r o rc o r r e c t i o na b i l i t yi sl o w ， a n dt h ei t e r a t i v ea l g o r i t h mf o rt h o s ew h o s ee r r o rc o r r e c t i o na b i l i t yi s g r e a t p r o g r a m sa r ei m p l e m e n t e df o r ( 2 7 ，9 ) r sa n d ( 5 4 ，18 ) r s j u s t l i k et h et h e o r e t i c a la n a l y s e s ，r e s u l t sd e m o n s t r a t et h a tt h et w oc o d e sc a n c o r r e c tn i n ee r r o r sa n de i g h t e e ne r r o r sr e s p e c t i v e l y t h eb i te r r o rr a t e s h a v eb e e ni m p r o v e dc o r r e s p o n d i n g l y ，f u r t h e r m o r e ，t h ee n c o d i n ga n d d e c o d i n gm e t h o d so f ( 16 ，i2 ) r s a r es i m p l yd i s c u s s e d t h em e t h o do fs o f t - d e c i s i o n d e c o d i n go fr sc o d e i sr e s e a r c h e d s o f t d e c i s i o nd e c o d i n gc a nm a k ef u l lu s eo ft h eo u t p u ti n f o r m a t i o n ，a n d s u b s t a n t i a lc o d i n gg a i nc a nb eg o t t e n ，w h i c hh a sb e e no b s e r v e de a r l y s i n c es o f t - d e c i s i o nd e c o d i n gn e e d sm u c hm o r ec o m p u t a t i o n ，i ti ss o c o m p l e x a st ob ei n f e a s i b l ei n m a n ya p p l i c a t i o n s t h o u g h s o m e s o f t d e c i s i o na l g o r i t h m sf o rb i n a r yf i n i t ef i e l dh a v ee x i s t e d ，- n o n - b i n a r y f i n i t ef i e l di ss e l d o mc o n c e r n e d a n a l g o r i t h m f o rs o f t - d e c i s i o n d e c o d i n g ( 1 5 ，11 ) r s i sp r e s e n t e d ，w h i c hr e f e r st ot h ec h a s ea l g o r i t h m 。 s i m u l a t i o nr e s u l ts h o w st h a tf o u re r r o r sc a nb ec o r r e c t e da tm o s t t h i s a l g o r i t h mc a ni m p r o v ee r r o r - c o r r e c t i o na b i l i t ya n dc o d i n gg a i n k e y w o r d se r r o rc o n t r o l ，r sc o d e ，c o d i n ga n dd e c o d i n g ，s o f t d e c i s i o n 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 本章简单介绍信道编码理论与技术的发展及其应用。重点阐述 了r s 码在编码理论和实际应用中的地位。最后给出本论文的研究 内容。 1 1 信道编码定理及其发展 1 9 4 8 年3 2 岁的电子工程师、数学家s h a n n o n 在b e l ls y s t e m t e c h n i c a lj o u r n a l 上发表了一篇题为通信的数学理论的论文，从 而奠定了信息理论的基础。他正式应用了概率理论研究和分析了通 信系统，将通信系统抽象为图1 1 的基本框图。并且成功地定义了 幽i i 数字传输系统的基本原理 信息量的概念，由此提出了熵和信道容量等概念。关于熵和信道容 量等基本概念的定义及详细的证明可以参阅【1 5 】等信息理论的基础 教材。 根据图1 1 ，信源随机地产生消息。一般用消息的统计特性来刻 画信源；消息通过信源编码，产生一定的数字序列来表示消息，再 通过信道编码增加冗余提高抗干扰能力。由于噪声源的存在，接收 端的信号会有不同程度的畸变这种畸变是由信道的物理特性和噪 声源的统计特性决定的。解调器、信道译码器和信源译码器对接收 到的信号进行译码，试图恢复出正确的消息，这个估计的消息最终 西南交通大学硕士研究生学位论文第2 页 送给信宿。s h a n n o n 指出了任意给定的信源都有一个称为熵的量， 它表征了信源的不确定性正好是信源的下限( 信源编码定理) 。同 时他还提出了著名的信道编码定理：任意给定的信道都有一个固有 的量称为信道容量。只要信息的传输速率低于信道容量，总可以 找到一种编码方法使得差错概率任意的小；反之，如果信息的传 输速率超过信道容量。则不存在这样的编码方法。编码定理表明， 信道容量正好等于信息传输速率的上确界。 加性自高斯噪声( a w g n ) 信道是通信理论研究中最重要的信 道模型之一。噪声的统计特性服从高斯分布n ( o ，盯2 ) ，方差 盯2 = n o 2 ，o 为双边带噪声功率谱密度即单位频带内的噪声功 率。设传输的每符号的平均能量为晟，信号周期为l 信道带宽为 孵在理想情况下( 按n y q u i s t 准则) ，= l ，l 信号平均功率p = 反，r 。则信道的平均信噪比为： 册；生：鼻：盟( 】1 )哺= 二= = = 二二竺r 】1 ) n o w 2 仃 n o 。 式中蜿是每比特的平均能量；r 。为码率表示每编码符号所承载的 平均信息比特数( 信息量) 。由信息论的理论知识可知，在高斯白噪 声信道下，信道容量： c = 刖( 1 + s n r ) = w l o g ： h 制0 卅z 昭：c 1 + 等) 小2 ，。，。o ， 对于可靠通信( 所谓的“可靠”，一般用误比特率b e r 来度量。 理论的“可靠通信”一般以b 职s | 0 4 一1 0 。来衡量的，而实际的通信 系统对b e r 的要求有差别。) 要求r 。 三f 极限情况下三n 生o2 2 墨2 l n 2 = 一1 t 5 9 妨，这就是带宽 无限高斯白噪声信道的极限传输能力，也称为s h a n n o n 限。编码理 论发展至今，就是在不断的寻找性能接近s h a n n o n 限的码。 自从s h a n n o n 发表其论文以来信道编码就开始了迅速的发展。 其发展历程如下：第一个分组码是纠正单个错误的h a m m i n g 码。在 s h a n n o n 以前，h w h a m m i n g 已经发现了这类码只是由于技术专 西南交通大学硕士研究生学位论文第3 页 利的缘故，于1 9 5 0 年才发表。1 9 5 4 年，m j - g o l a y 发现了g o l a y 码。同年，i s r e e d 和d e m u l l e r 发现了r e e d m u l l e r 码( r m 码) 。 1 9 5 6 年，d s l c p i a n 给出了线性码、群码的系统描述。1 9 5 7 年，e p r a n g e 发现了循环码。r c b o s e 和d k r a y c h a u d h u r i 独立于a h o c q u e n g h e m ( 1 9 5 9 年) 发现了纠多个错的码后来人们称之为b c h 码。1 9 6 0 年，i s r e e d 和g s o l o m o n 发现了r e e d s o l o m o n 码( r s 码) 。1 9 7 0 年，v d g o p p a 发现了g o p p a 码。1 9 8 2 年，m a t s f a s m a n ， s 。g ，v 五d u t 和tz i n k 发现了代数几何码。从b c h 码，r s 码，g o p p a 码道代数几何码的发展过程中g v 限( g i l b e r t c a r s h a m o vb o u n d ) 起着不可忽略的作用。g v 限是由e n g i b e r t ( 1 9 5 2 ) 和r r v a r s h a m o v ( 1 9 5 7 ) 独立发现的。假定我们在有限域凡上考虑问题， d 一2 厂。1 、 给定一组非负整数，l ，七，d ，只要q ”。 罗| r k q 1 ) 。就可以构 丽lf 造一个码长为订，维数为t 最小h a m m i n g 距离至少为d 的目元线 性分组码。这就是g v 限，其证明以及有关线性分组码的基本术语、 概念可以在编码理论的基础教材中找到 1 0 t t n i 。记归一化的最小 h a m m i n g 距离为占= d ，拧，编码速率( 对于线性分组码而言) r = 七， 打。渐近的g v 限表明一呻0 0 时，存在线性分组码使得艿和r 均严 格大于0 。渐近的g v 限是街置某类分组码“好坏”的一个标准。已经 证明h a m m i n g 码、r m 码、b c h 码等大部分已知的码都是渐近坏码。 在分组码的理论研究中，r s 码扮演着重要的角色。r s 码是有 限域凡上的极大距离可分( m d s ，m a x i m u md i s t a n c es e p a r a b l e ) 码 具有参数( 疗，七，一一k + 1 ) 4 ，达到了s i n g l e t o n 服ds 一七+ 1 ，从这个 意义上讲，r s 码是晟佳的。b c h 码可以看成某个r s 的子域子码， r s 码又可以看成b c h 码的特铡，只不过符号域与位置域相同罢了。 r s 码的个码字可以看作是某个多项式( 取自一个特定的多项式集 合) 在一个特定的点集上( 含于r ) 的值。 卷积码的概念是由p e l i a s 于1 9 5 5 年发现的。尽管其代数结构 以及相应的理论结果没有分组码丰富，但由于其译码算法的实用性， 因而在编码理论中也占有重要地位。级联码( 或称级连码， c o n c a t e n a t e dc o d e s ) 是由g d f o r n e y 于1 9 6 6 年提出的。级联码一 般多以r s 码作为外码而以卷积码作为内码。f o r n e y 的性能分析 西南交通大学硕士研究生学位论文第4 页 表明，级联码的性能改善了很多而译码复杂度增加的并不多。实 用分组码的代数译码算法是1 9 6 6 年由e r b e r l e k a m p 提出的，1 9 6 9 年j l m a s s e y 从序列综合的角度重新推导了这一算法，后人称之 为b e r l e k a m p m a s s e y 算法。b e r l e k a m p m a s s e y 算法的提出是分组 码走向实用的一个重要里程碑。与分组码相比，卷积码的一个显著 特点是软判决译码算法比硬判决译码算法复杂不了多少。1 9 5 7 年， j m w o z e n c r a f t 提出了序列译码算法1 9 6 4 年。r m 。f a n o 提出的 f a n o 译码算法也属于序列译码算法。1 9 6 7 年，a j v i t e r b i 提出了 卷积码的最大似然译码算法，后人称之为v i t e r b i 算法，在通信工程 领域得到了广泛应用。 7 0 年代束8 0 年代初，g u n g e r b o e c k 把编码与调制相结合提出 了网格编码调制( t c m t r e l l i s c o d e d m o d u l a t i o n ) 技术，这是编码 理论的又一重要里程碑。继t c m 之后，编码理论的重大发现当首推 1 9 9 3 年c b e r r o u ，a g l a v i e u x 和p t h i t i m a j s h i m a 发现的t u r b o 码。 模拟结果表明，t u r b o 码的性能距离s h a n n o n 限仅差零点几个d b 。 尽管t u r b o 的模拟性能卓越，其理论分析还很薄弱。或许正是这个 原因，t u r b o 码的出现，在编码领域掀起了研究热潮。在探究t u r b o 码迭代算法的过程中。出现了一个活跃的研究方向基于图的码 ( c o d e so ng r a p h s ) 。d j c m a c k a y 和r m n e a l 以及别的一些作 者重新发现了r g g a l l a g e r 于6 0 年代提出的低密度一致校验 ( l d p c ，l o w - d e n s i t yp a r i t y c h e c k ) 码其性能与t u r b o 码差不多。 1 2 信道编码的应用 随着信道编码理论的不颟发展，信道编码技术在通信工程领域 得到了广泛的应用。特别是数字通信的* 起，为信邋编码提供了广 阔的应用空间。可以毫不夸张她说，编码技术应用在各种数字通信 系统中。正是由于应用了该技术对数据传输进行差错控制大大 降低了误码率，提高了数据传输的正确率，实现了稳定通信。 纠错码的应用领域包括：深空通信。卫星通信，数据传输，穆 动通信，文件传输数字音频，视频传输等。下面是r s 码的主要应 用。 早勰的编码理论主要应用于深空遥信和卫星通信中。这主要有 西南交通大学硕士研究生学位论文第5 页 以下方面的原因：深空信道是最典型的无记忆a w g n ( 加性白高斯 噪声) 信道模型，而s h a n n o n 的信道编码定理正是基于此模型提出 的一般性结论。理论分析结果和计算机仿真结果几乎和实际系统一 致。深空信道的频带资源丰富，这就允许在系统中采用频带利用率 低的码和b p s k 调制方式。由于传输距离远，信号衰减严重，需要 采用纠错能力强的码，这意味着译码复杂度提高，数据速率降低。 但是一般的深空通信都是非实时的，功率受限。正是由于这些原因， 纠错码技术自问世以来，就和深空通信结下了不解之缘。r s ( 2 5 5 ， 2 3 3 ) 已经成为美国航天局( n a s a ) 和欧洲空问站( e s a ) 在深空 通信的级连系统中采用的标准码；以( 2 ，1 ，7 ) 卷积码作为内码、( 2 5 5 ， 2 2 3 ) r s 码作为外码的串行缀联码( s c c ) 已于1 9 8 7 年被空间数据系统 协调委员会( c c s d sc o n s u l t a t i v ec o m m i t t c eo ns p a c ed a t as y s t e m s ) 推荐为遥测信道的标准编码结构俐。 在计算机存储系统中广泛使用了r s 码差错控制技术，包括高 速计算机存储器以及磁盘和光盘。r s ( 1 5 ，9 ) 码为光存储系统的 标准纠错码。在i b m l 3 6 0 计算机系列光盘存储器中采用( 3 6 6 ，3 0 0 ) r s 码，在d i g i t a l c y p r e s s 中采用( 6 1 ，5 0 ) 缩短的r s 码。c d 所使 用的码字为互交织r s 码( c i r c ，c r o s s i n t e r l e a v e dr sc o d e s ) 它是 在域g f ( 2 3 ) 上两个最小距离为5 的缩短r s 码的组合。在c d r o m 中，由于需要更强的纠错能力，因此除了应用c i r c 码外还附 加了循环冗余校验码( c r c ，c y c l i cr e d u n d a n c yc h e e k ) 和两个缩短 r s 码的乘积码。 近年来r s 码技术不断的应用到无线通信中。w c d m a 是第三 代移动通信标准家族i m t 2 0 0 0 中最重要的标准之一。w c d m a 方 案中采用了对不同q o s 要求的业务进行不同的信道编码的策略。标 准业务仅采用卷积编码，高质量业务在卷积编码的基础上增加r s 编码或采用t u r b o 码的编码方法。i t u 所建议的r s 编码，编码格式 为( 2 5 5 ，2 3 9 ，1 7 ) 。 随着计算机和通信技术的发展，无线移动数据通信在现代社会 中悄然兴起。其中c d p d ( 蜂窝数字分组数据) 被认为是较佳的无 线数据格式之一。1 9 9 8 年我国丌始在北京、上海、广州、深圳、长 沙等5 个城市采用c d p d 技术，使用国家无线电管理委员会规定的 西南交通大学硕士研究生学位论文第6 页 频段，组建公共移动数据网络。在c d p d 系统的m a c 层就使用了 r s 码。数据块用对称的( 6 3 ，4 7 ) r s 码进行纠错编码，生成3 7 8 b i t 固定长度的r s 编码块序列，其中信息段由4 7 个6 b i t 码字构成，校 验段由1 6 个6 b i t 码字构成。 宽带无线接入系统讵成为无线电通信中的一个热点。本地多点 分配系统( l m d s ) 是一种点到多点的宽带固定无线接入技术，是 很有市场潜力的宽带无线接入方式。无线通信传输信道中存在的多 径传播以及随机干扰，使得无线信道的传输特性比较恶劣，因此发 送端一般采取r s 编码加交织的方式，提高系统的纠错性能。2 0 0 0 年2 月，美国e n s e m b l e 通信、n o k i a ，以色列b r c e z e c o m 公司和s i e m e n s 联合向i e e e 8 0 2 1 6 工作组提交了b b w a ( 宽带无线接入) 物理层建 议。p h y 和m a c 的传输控制( t c ) 数据f e c 采用r s 码加c r c 校验，r s 码采用( 1 3 8 ，1 2 8 ) ，c r c 长度为1 6 b i t 。i e e e 8 0 2 15 有关 b l u e t o o t h 的部分建议前向纠错码采用r s 编码和交织1 1 1 。 r s 码还广泛应用于数字视频系统中。数字电视地面广播d t t b ( d i g i t a lt e l e v i s i o nt e r r e s t r i a lb r o a d c a s t i n g ) 中的外码纠错部分，使用 的就是r s 码。平时讲的数字电视均指经过压缩编解码( 遵循m p e g 2 标准) 处理后的电视。在m p e g 2 数字视频标准中，使用了基于r s 码的复杂差错控制，其中m p e g 2 传送包采用缩短r s 编码。在编 码的过程中，每个m p e g 2 传送包增加了1 6 个校验字节，码字为 ( 2 0 4 ，1 8 8 ) ，可以纠正8 个字节的误码。在数字电视传输系统中， 采用r s 码作为前向纠错码。为了与a t m 保持互操作性，采用的r s 码格式为( 2 0 4 ，1 8 8 ) ，目前r s ( 2 0 4 ，1 8 8 ) 已经成为欧洲数字视 频广播和日本i s d b 中级联系统的标准外码d 4 1 。 1 3 毕业设计的内容 本文研究的内容涉及r s 码的编译码算法及其软判决方法，这 些方面的研究问题很多，本文主要考虑r s 缩短码的编译码实现和 短r s 码的软判决方法，为信息产业部电子第三十研究所的军事预 研项目。 第二章研究了r s 码的编译码过程。首先介绍了域的基本知识， 分析如何实现伽罗华域的加法和乘法运算。然后给出了r s 码的编 西南交通大学硕士研究生学位论文第7 页 码方法以及短r s 码的简单译码算法。同时还介绍了频域上实现r s 码的译码算法。 第三章研究修正的r s 码。对于缩短的r s 码，如果码长较长， 简单的译码算法不再适合，需要更简便的计算错误多项式的算法。 本章给出了具体的r s ( 5 4 1 8 ) 和r s ( 2 7 9 ) 的编译码实现过程。 然后讨论了增长码r s ( 1 6 ，1 2 ) 的编译码方法。 第四章研究r s 码的软判决方法。由于是非二进制码，普通的 软判决方法难以适用。本文将，c h a s e 算法使用在原本可以纠正二个 错误的r s ( 1 5 ，1 1 ) 上最多可以纠丁e 四个错误。但是这种算法不 适合码长较长的r s 码。 论文的最后对全文进行了总结，并给出下一步的研究方向。 西南交通大学硕士研究生学位论文第8 页 第2 章r s 码的编译码方法 2 1 有限域上的运算 域是由加法和乘法两种运算的一些元素组成，在每种运算下都 有逆元素存在这就说明有减法和除法的另外两种运算存在。域f 内同时满足加法与乘法运算的各个元素需要满足以下条件： i ) 对这两种运算来说，f 是封闭的即f 内任何两个元素之和 或积仍在f 内； 2 ) 对每种运算各元素满足通常的结合律和交换律； 3 ) 满足通常的分配律； 4 ) f 内的任何元素“都有一个唯一的加法恒元0 和一个乘法恒 元1 满足以下关系 “+ 0 = “ u 1 = ” 5 ) 域内每个元素“都有一个难一的加法逆元一“， “+ ( 一“) = 0 当“o 时，有一个唯一的乘法逆元u “存在， “2 - 1 = 1 域内元素的数目叫做域的阶可为有限或无限。有限域以g f ( q ) 表示，q 是域内的元素数目，也称为佣罗华域。对任何的， 都存在一个有限域g f ( 口”) 这里p 是素数，用为整数。有限域最 简单的一个例子是素域g f ( p ) ，它由全部模p 的整数集合组成，p 是任何大于1 的一个素数，加法与乘法运算都是模p 的。g f ( 2 ) 是最简单的素域，它只食有0 与l 的0 元和l 元。产生加法恒元所 需的乘法恒元相加是的最低数目，叫做域的特征。g f ( p ”) 的特征 是p - 有限域的一个重要性质是每个有限域g f ( g ) 至少要包括一个 叫做吐的本原元素。该元素的口一1 次幂数都是这个域中口一1 个非 零元素，就是说，g 1 个非零元素可表示为a 一口g 。它们互 不相等，所以a 一的g 1 种乘积也应互不相等。域中所有的非零元 素都可以用本原元素的前g 一1 个幂数束表示可用它们各自的指 西南交通大学硕士研究生学位论文第9 页 数表示各个域元素。实际上这些指数是以口为底的对数。 在实际使用中需要将域元素表示为便于计算机计算的形式。 首先可以看出， g f ( q ) 内各元素可以构成m 重的总数为口“个， 并且组成了一个g f ( g ) 上的m 维矢量空间。这样就可以使用g f ( 口) 中的矢量的加减法进行矢量的相加与相减，并得到这个矢量空 间内的另一个矢量。为了进行矢量的乘法与除法，需要将矢量表示 为多项式，其各项豹系数与矢量中的各个元素相对应。与矢量相加 相同，可以对多项式进行逐位相加。每个系数取自有限域g f ( 盯) 的肌次不可约多项式最少有一个元素数目为矿的有限域g f ( q ) 与其对应存在。 在r s 码中。不可避免地要涉及伽罗华域上的代数运算。如何 简单实现这些运算关系着编译码的的速度，下面就几种方法进行讨 论 直接查表法，通过两个域元素直接查找域运算结果，系统中只 需要存放域元素的一种形式当m 小于等于4 时，使用直接查表法 只需一次壹表，算法简单，运算速度最快。但是这种方法的制表存 储量比较大。 二表法，是指矢量形式和指数形式对照表。在二表法中，如果 选用的基本形式不同，效果也会有所不同。 传统算法是选用矢量形式作为数据处理的基本形式，相加是利 用矢量形式中对应位模2 相加：相乘和相除要利用矢量形式和指数 形式转换表，转换为指数形式进行最后将结果转换为矢量形式存 放。这样进行一次加法只需一次异或，但是对于乘除法计算，除 了需要判断和模2 ”一l 相加外，还需要三次查表转换。但是在r s 译码过程中，对乘除法所需计算量要多，所以应降低乘除法运算的 查表转换次数。 另一种方法选用指数形式为基本形式，加法运算需要一次异或 和三次查表转换而乘除法只需要判断和模2 ”一l 运算避免了繁 琐的查表转换。所以当m 4 时，选择指数形式为基本形式进行伽 罗华域上的代数运算 在运算过程中，元素的基本形式是用十进制数表示的，运算过 程如下： 西南交通大学硕士研究生学位论文第1 0 页 加法：将两个十进制数先转化为两个m 个比特的二进制数来表 示，然后将对应位进行异或运算，再将运算的结果转化成十进制数 存储起来。 乘法：把两个元素的十迸制表示化成指数形式，将指数直接相 加取模2 “一1 得到乘积的指数形式然后再化成十进制形式存 储起来。 元素的二迸制形式和指数形式可以互相转化，在程序中用两个 数组来表示。数组t a b l e b 2 e 将= 进制形式对应为指数形式数组 t a b l e e 2 b 将指数形式对应为= 迸制形式。它们都以十进制形式存储， 做加法运算时用其二进制形式，做乘法运算时用其指数形式。两个 数组的内容如下： t a b l e e 2 b = 0 x 0 0 ，0 x 0 1 ，0 x 0 2 ，0 x 0 4 ，0 x 0 8 ，0 x 1 0 ，0 x 2 0 。0 x 0 3 ， 0 x 0 6 ，0 x o c ，0 xl8 ，0 x 3 0 ，0 x 2 3 ，0 x 0 5 ，0 x o a ，0 xl4 ， 0 x 2 8 ，0 x l3 , 0 x 2 6 ，0 x 0 c 0 x l e ，0 x 3 c ，0 x 3 b ，0 x 3 5 ， 0 x 2 9 ，0 x l l ，0 x 2 2 ，0 x 0 7 ，0 x o e 。0 x l c ，0 x 3 8 ，0 x 3 3 ， 0 x 2 5 ，0 x 0 9 ，0 x l2 ，0 x 2 4 ，0 x o b ，0 xl6 ，0 x 2 e ，0 xlb ， 0 x 3 6 ，0 x 2 c 0 x 1d ，0 x 3 a ，0 x 3 7 ，0 x 2 d ，0 xl9 ，0 x 3 2 ， 0 x 2 7 ，o x o d ，o x la ，0 x 3 4 ，0 x 2 b ，0 xl5 ，0 x 2 a ，0 x17 ， 0 x 2 e ，0 x lc 0 x 3 e ，0 x 3 c 0 x 3 d ，0 x 3 9 ，0 x 3 1 ，0 x 21 ； t a b l e b 2 e 6 4 = 6 3 。0 ，1 6 ，2 ，1 2 ，7 ，2 6 ， 3 ，3 2 ，l3 ，3 5 ，8 ，4 8 ，2 7 ，1 8 ， 4 ，2 4 ，3 3 ，1 6 ，1 4 ，5 2 ，3 6 ，5 4 ， 9 ，4 5 ，4 9 ，3 8 ，2 8 ，4 1 ，1 9 ，5 6 ， 5 ，6 2 ，2 5 ，l l ，3 4 ，3 1 ，1 7 ，4 7 。 1 5 ，2 3 ，5 3 ，5 i ，3 7 ，4 4 ，5 5 ，4 0 ， 1 0 ，6 1 ，4 6 ，3 0 ，5 0 ，2 2 ，3 9 ，4 3 ， 2 9 ，6 0 ，4 2 ，2 l ，2 0 ，5 9 ，5 7 ，5 8 ) ； 2 2r s 码的编码方法 r s 码是b c h 码的一个子类，是最大距离可分码( m d s 码) 。 对于能够纠r 个错误的r s ( 疗女d ) 码，具有如下特征： 1 ) 码长n = 2 m i ； 西南交通大学硕士研究生学位论文第1 1 页 2 ) 信息元数k = - n 2 t ： 3 ) 监督元数r 一k = - 2 t ； 4 ) 最小距离d = 2 t + 1 = r 一七+ 1 。 最小距离为d 的本原r s 码的生成多项式为 g ( x ) = ( x 一口”) ( 工一a ”卅) ( x 一口“+ 2 ) ( 善一口“+ d 一2 ) 式中的m 是一个任意整数，我们取肌= l 。生成多项式就写成 g ( 工) = ( 工一a x x a 2 ) ( 工一口”)( 2 1 ) 下面考虑编码方法令信息元多项式为 或者表示为 口( 工) = a o + a l + a 2 x 2 + + 吼一l j 一 口( x ) = o k _ l x + + 口i 2 x 2 + - - + a 2 x 2 + a i 了+ 口。 设 苎：巫! ：6 + 三盟 g ( x )g ( x ) 剩余多项式r ( 对至少比觯) 低一次 ，( x ) = r 2 l _ l x 2 。+ f 2 2 2 卜2 + + 屹x 2 + r i x + r o 则编成的码的多项式为 c ( x ) = x “口( x ) + ，( x )( 2 2 ) 也可以写成 c ( 对= 1 x 肿+ c a 2 x “。2 + + c 2 x 2 + c l x + c o 对于具体实现编码部分的电路见图2 1 ，首先需要知道生成多项 式的各个系数，可以表示为 g ( 工) = ( x + 口) ( z + t z2 ) ( x + 口扫) = g 。+ g l x + 9 2 x 2 + + 9 2 ，- 2 x 2 一2 + g2 , - i x 2 卜+ x 舢 待编码的消息为口o ) ，然后用消息多项式工2 r 口( x ) 除以生成多项式 如) 就得到余项r 扛) ，余项r ( 曲= r o + f i x + + r 2 h x l “的系数也就是 西南交通大学硕士研究生学位论文第12 页 校验位，将它们和消息一同送入信道。 回 g 槲的加法器g 槲的乘法嚣g 呦中的存储器 输 出 图2 - 1r s 码的绷码电路 2 3r s 码的译码方法 编好的码字 c c x ) = o i 石。一1 + 矗一：工肛2 + + c 2 工2 + c l x + c o 当此码在经过信道传递后，有可能发生错误从而被接收为 r ( = c ( 砷+ e ( 工) = 一i x 4 。+ 一2 工”一2 + + 吒工2 + r i 工+ 错误图样 e ( 工) = e # _ l x “一。+ 气一2 x “一3 + + e 2 x 2 + q 工+ e o 其中最多有f 个错误，否则错误不可纠正。 因为对于g f ( 2 4 ) 上的本原元o r ，口1 ，口2 ，a2 均应为码多项式根， 因此监督矩阵 h ( 2 h 岫= 口 i - 。r j 仁。r 庄“一2 b ，r 2 ； b ：。y 口。口1 白z ) ：- z ) 1 p ) 2 仁。) 西南交通大学硕士研究生学位论文第13 页 s = r - t = k i ，2 ，2 ，口 其中 令 s = s ：s ， 矿1 b2 p 矿2 p2 r 口2 q2 ) 2 口岱 l1 1 5 a j gz 守 口2 i 8 j = 如，) = 气k ，) + 气( 口，7 t + + e i , 扛寸j = l ，2 ，2 t ，为实际的错误数 则有 z = 口。表示第i 1 个错误所在的位置数 巧= 气处的错误值 0 ；h x ，+ k x ；+ + r x ；j = l ，2 ，2 t 即 5 i = r , x ? + 匕x ：+ + r , x ： j 2 = r , x ? + l x ；+ 4 - 耳z ； ( 2 3 ) j a = z j ? + x ；+ + r , x 1 4 此处共有2 r ( r s ，) 个未知数要解出。即x 。，z 2 ，x ，k ，e ，t 。 方程组数为2 ，在线性下可解。如果为非线性方程组，则很难解出。 因此通过设置位置多项式 仃( 工) = c o x + c l i 善。+ - + 盯2 善2 + d r i x + l 它的根应与位置数x ，x l , - - , 置有如下关系： o - ( x ) = o 一工) ( 1 一x x 2 ) ( 1 一x x ，) ( 2 - 4 ) rj，l1，l 西南交通大学硕士研究生学位论文第1 4 页 如能设法知道d b ) 的各项系数，则其裉显然为竹，x ，x , - ，取其 根的倒数，即得出x i 。丑，x ，。 通常实际错误数， 的方法仍是b e r l e k a m p m a s s c y 算法只是此时求盯( x ) 是在频域中 进行的。 综上所述，r s 码的频域译码可概括成以下几步； i ) 计算接收矢量，的傅立叶变换r ，得到2 t 个伴随式s j = 毋： 秘用b e r | e k a m p - m a s s e y 算法求d ( x ) ； 西南交通大学硕士研究生学位论文第2 0 页 3 ) 由盯( 苫) 和伴随式s l ，岛，计算e ； 4 ) 求震一e 的逆变换得到正确的码字c 。 但是上述译码方法需要进行正反两次变换。这是由于编码是 在时域中进行的，因而译码时需要先将接收矢量变换到频域再做处 理，然后经逆变换回到时域。实际上可以在频域上对信息矢量进行 编码这样译码时只要进行一次变换就行了。 设c = a ；i = 0 ，1 ，2 ，l - 1 为g f ( 2 ”) 上纠t 个错的本原r s 码字，c = c f ；i = 0 ，l ，2 ，一1 为c 在有限域上的傅立叶变换 a 为g f ( 2 ”) 上的本原元，则a 吐2 ，。吐2 为码的生成多项式的根， 因此下式成立： n = l， c ，= c p 9 = c 仁) ；o o = 1 ，如，2 f ) ，- 0 然后就可以报据此式进行编码。 设f ； j o ，f i ，“一1 ) 为信息矢量，在i o 和i l 之间插入2 r 个零， 得到另一矢量c ： c = i o ，0 ，0 ，0 ，i l ，“一1 ) 把矢量c 看作是频域码矢，对其进行逆变换就可以得到时域码矢c ： c 7 = t - i c 7 = 丁1 ( i o ，o ，0 ，i 2 ，j ) = ，q ，“i y 设接收矢量，= r o ，r l ，h i ，信道的错误图样p = ( e o ，e i ， e 一1 。 译码器首先计算接收矢量，的傅立叶变换r 得到2 ，个伴随式 s j = r ，( ，= 0 1 2 ，2 f ) 。若2 t 个伴随式全部等于零则接收 该矢量，从r 中去掉露j ，r 2 ，r 2 ，就得到了发送豹矢量j ；如果 2 ，个伴随式不全为零，则利用b e r l c k a m p m a s s e y 算法求出盯( 工) ， 再求出e 计算尺一e ，得到频域码矢量c 。从c 中去掉c l ，c 2 ， c 2 ，就可得到发送的信息矢量f 。 下面简单概括一下频域译码的优点： 1 ) 在计算接收矢量的傅立叶变换时，可采用不同形式的快速傅 立叶变换算法，从而提高运算速度； 2 ) 在频域译码中无需求出差错位置数和差错值，可以减少运 算的次数。 西南交通大学硕士研究生学位论文第2 1 页 2 5 r 8 码纠错性能分析 对于任何纠锚码来说，度量其纠错性能的最常用工具便是它的 译码器或者传输过程的差错概率。由于r s 码作用于符号，故主要 考虑的是符号差错而不是比特差错。 在一个给定的码组内，如果接收符号中出错数目超过r 时，便 会出现不可纠差错。当出现不可纠差错时，译码器将会发生如下两 种情况之一：信息码组被识别为不可纠正同时给出标志，这类差错 称为可识别差错；或者是译码器将差错图样当作可纠并且将原始 的正确信息码组纠为错误的信息码组，这种情况称为译码错误。当 发生译码错误时整个码组被错误地译码。 不可纠差错概率，w 是不可纠码组数目与接收码组数目的比 值。决定p o e 的一个重要参数是信道符号差错率p s e 。p s e 是接收符 号中的差错数与接收符号总数的比值，也就是信道在传输信息的过 程中将改变符号的概率。在没纠错机制的信道中信道符号差错率 p s e 也就是介绍符号差错概率。但是当具有纠错机制时，接收符号差 错概率将减小报多个数量级。 为计算差错率改善的数值首先假设符号差错率是独立的。并 且不会出现疑符一个计算不可纠差错概率的公式由下式给出： ，厂。、 = l 一r 陆y ( 1 一r l o ， 其中疗为每个码组的符号数。 例如对于r s 码来说，令行= 1 5 和f - 2 将它们代入上面的公 式。当p s