（计算机系统结构专业论文）基于高斯信道的级联码差错控制系统设计与仿真.pdf

华中科技大学硕士学位论文 摘要 数字化技术的迅速发展使得数据传输、存储的有效性、可靠性和完整性变得越 来越重要，研究者致力于采用新的高效的算法，追求更高的编码增益，更好的纠错 性能，更低的计算复杂度。 r s 码是一类有着广泛应用的纠错码。作为一种多进制码，r s 码有着很强的抗 突发错误的能力，因此在设计数据传输或者存储纠错方案时，r s 码常常被作为首选 纠错码或者作为一个成分码。r s 码的硬判决有着成熟的理论和实践基础，为进一步 提高编码增益，基于输入比特的可信信息，针对r s 码进行软判决译码成为研究者 工作的热点，我们对r s 短码的软判结合调制方式作了探讨，提出改进的c h a s e 算 法和基于调制信号可信度的软判决译码方法，以较小的计算复杂度换取性能的大幅 度提高。 编码调制一体化方案采用卷积码同调制相结合的方式能够在不扩展带宽的情 况下取得较大的编码增益。基于编码调制一体化思想，采用特定的实用编码调制映 射方式，和设计相应的译码器结构，能够达到优越的比特输出性能，并且实现也比 较简单。 结合r s 码高纠错能力和内码相对简单的译码优势，通过将两者级联，能够在 很大程度上改善系统陛能，同时译码的复杂度不会增加很多。我们详细阐述了内码 的设计，提出可行的级联码方案并仿真验证了其可行性。 关键词：软判决译码，理德索罗蒙码，实用网格编码， 级联码 i 华中科技大学硕士学位论文 a b s t r a c t t h ee f f i c i e n c y , r e l i a b i l i t ya n di n t e g r a l i t yo fd a t ai nt r a n s m i t t i n go r s a v i n gd a t a b e c o m em o r ea n dm o r ei m p o r t a n tw i t ht h e r a p i dd e v e l o p m e n t o fi n f o r m a t i o n t e c h n o l o g y t h er e s e a r c h e r sh a v eb e e n t a k i n gt h e i rb e s tt of i n dn e wh i g hp e r f o r m a n c ea l g o r i t h m ，t o g e tm o r ec o d i n gg a i n s ，b e t t e rb i te r r o rr a t ea n dl o w e rc o m p u t a t i o nc o m p l e x i t y r e e d - s o l o m o nc o d ei sac l a s so fe r r o r - c o r r e c t i n gc o d e s e n j o y e d c o u n t l e s s a p p l i c a t i o n s a sr sc o d e sa r es y m b o lb a s e dc o d e s ，t h e ya r eq u i t er o b u s ti nc o r r e c t i n g b u r s te r r o r s a n dr sc o d e sa r ea l w a y sc h o s et ob et h ef e c ( f o r w a r de r r o rc o r r e c t i o n ) c o d e so rs u bc o d e sw h e na l le r r o rc o n t r o ls y s t e mo fd a t ai sc o n s i d e r e d h a r dd e c i s i o n d e c o d i n go f r sc o d e sh a v eb e e nw e l ld e v e l o p e da n dw i d e l yu s e d i no r d e rt og e tm o r e c o d i n gg a i n s ，s o f td e c i s i o nd e c o d i n gt e c h n o l o g yb a s e do nb i tr e l i a b i l i t y o rs y m b o l r e l i a b i l i t yb e c o m e st h em a j o ri n t e r e s to fr e s e a r c h e r s w ed i s c u s s e dt h es o f td e c i s i o no f s h o r tr sc o d e sc o m b i n e dw i t hm o d u l a t i o n , a n dp r e s e n t e da ni m p r o v e dc h a s ea l g o r i t h m a n das o f td e c i s i o na l g o r i t h mb a s e do nm o d u l a t i o ns i g n a lr e l i a b i l i t y t h ep e r f o r m a n c e w a s g r e a t l yi m p r o v e d w h i l et h ec o m p l e x i t yi n c r e a s e do n l yal i t t l e c o d e dm o d u l a t i o nw a sf i r s t p r o p o s e db yu n g e r b o e c ki n1 9 8 2 ，i nw h i c hl a r g e c o d i n gg a i n sc a n b eo b t a i n e dw i t h o u t c o m p r o m i s i n ge f f i c i e n c y b a s e do nt h et r e l l i sc o d e m o d u l a t i o n ( t c m ) t h e o r y , w er e s e a r c h e dap r a g m a t i ct c m ( p t c m ) m a p p i n g m e t h o d ， a n dd e s i g n e dt h es t r u c t u r eo ft h ed e c o d e r a c c o r d i n g l y w eg e tp r e t t yg o o db e r ( b i t e r r o r r a t e ) a n d i ti sa l s os i m p l et op u ti ti n t op r a c t i c e c o n s i d e r i n gt h ea d v a n t a g eo f t h eh i 啦p e r f o r m a n c eo fr so u t e rc o d e sa n dl o w d e c o d i n gc o m p l e x i t yo fp t c m i n n e rc o d e s ，w ec o n c a t e n a t e dt w oc o d e st oi m p r o v et h e p e r f o r m a n c eo f t h es y s t e m t h ed e s i g no ft h e7 i n n e rc o d ew a sp r o p o s e di n d e t a i la n d s i m u l a t i o nr e s u l to f t h e d e s i g n e ds y s t e mw a sp r e s e n t e d i tw a sp r o v e dt ob ef e a s i b l e k e y w o r d s =s o f td e c i s i o nd e c o d i n g ，r e e d - s o l o m o nc o d e s ，p t c m ，c o n c a t e n a t e dc o d e s i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：槛哥泉 日期： 一午年年月；p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密厨。 ( 请在以上方框内打“”) 学位论文作者签名：榜导，亟 f 1 期： 4 年4 月品 指导教师签名：) 马丹 日期：z 一甲年r 月g 目 华中科技大学硕士学位论文 1 绪论 1 1 差错控制编码理论基础及其发展 随着网络技术的发展，数字化技术的广泛应用，人们的生活日益依赖于计算机、 微处理器、互联网络和无线通信等技术，数据传输、存储的有效性性、可靠性和完 整性变得越来越重要，差错控制也因此由最初产生而逐渐成为一个越来越重要的领 域。 所谓差错控制，就是当信息源信号在传输或者存储过程中出现差错的时候，在 接收端能够减少或消除这些差错，尽量减少噪声对信道或者数据存储带来的影响， 以满足人们对数据高效、可靠传输或存储的要求。 1 9 4 8 年，电子工程师、数学家s h a n n o n 在b e l ls y s t e mt e c h n i c a lj o u r n a l 发 表了其奠定信息理论基础的经典论文：am a t h e m a t i c a lt h e o r yo fc b m m u n i c a t i o n i ”， 标志着信息与编码这一学科的创立，因此s h a n n 面被誉为“信息论之父【2 】口1 ”。文 1 中s h a n n o n 正式应用概率理论研究和分析通信系统，开辟了信息论的新研究领域， 半个多世纪来，信息理论不断得到完善、丰富和发展，信息论也被广泛的应用于概 率理论、计算机科学、离散数学、物理学、经济学等诸多领域 4 。 1 中s h a n n o n 将所有的数字传输系统，包括通信、雷达、数字计算机的存储系统和内部运算，以 及计算机之间的数据传递等，都归结为图1 1 所示的模型： 图1 1 信息传输模型 图1 1 有效的给出了信息传输系统的抽象。同时s h a n n o n 指出，任意给定的信 华中科技大学硕士学位论文 道都有一个固有的量，称之为信道容量。只要信息的传输速率低于信道容量，总是 可以找到一种编码方法，使得差错概率任意的小；反之，如果信息的传输速率超过 信道容量，则不存在这样的编码方法倒。该信道编码定理表明，信道容量正好等 于信息传输速率的上确界。s h a n n o n 证明，在加性高斯白噪声( a w g n ) 信道下，系 统容量c 是平均接收信号功率s 、平均噪声功率m 和带宽w 的函数。容量关系式( 香 农一啥特莱定理) 表示为： ，q c 川1 。哪+ 素) 香农公式理论上证明了存在可以提高差错性能或者降低所需e 。n 。的编码方 式。在s h a n n o n 1 以前，人们普遍的认为”：对于数据传输系统而言，要获得任意 小的错误概率的唯一途径就是把传输信息的速率降低到0 ；即，传输系统的可靠性 ( 对应于系统传输信息的误码率或者误比特率) 和有效性( 对应于系统传输信息的 速率比特信道符号) 是一对不可调和的矛盾。s h a n n o n 信道编码定理改变了这一观 念，只要r c ( r 代表传输速率，c 表示信道容量) ，可靠通信是可能的。但是信道 编码定理只是从理论上证明了可靠传输数据的可能性，随后，众多的学者为构造逼 近容量的纠错码做了大量的工作，信道编码也逐渐形成为信息论科学的一个分支。 自s h a n n o n 信道编码存在性定理发表以来，信道编码就开始了迅速的发展，主 要经历了以下的发展历程：第一个分组码是纠正单个错误的h a m m i n g 码，由 h w h a r o m i n 9 1 9 5 0 年正式发表，1 9 5 4 年，m j e 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 码( 蹦码) 。1 9 5 6 年，d s l e p i a n 给出 了线性码，群码的系统描述。1 9 8 7 年，e p r a n g e 发现了循环码。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 码) 口】【“。同年，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 码。七 十年代其间，在构造s h a n n o n 码中一个重要的成果是1 9 7 0 年前苏联学者v d g o p p a 发现了g o p p a 码。6 0 p p a 码不仅包含了当时已知的大部分线性码，而且从理论上讲， 它的最大意义在于证明了g o p p a 码的某个非循环码子类渐进特性很好唧。 在分组码的理论研究中，r s 码扮演着非常重要的角色。r s 码是有限域f q 上的 极大距离可分( 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 ) 码，具有参数( n ，k ，n k + 1 ) ， 达到了s i n g l e t o n 限d s 一：l + l ，从这个意义上来讲，r s 码是最佳的。b c h 码可以 看成某个r s 码的子域子码，r s 码可看成是b c h 码的个特例，只不过符号域于位 置域相同罢了。r s 码的一个码字可以看作是某个多项式( 来自一个特定的多项式的 集合) 在一个特定的点集上( 包含于f q ) 的值。关于r s 码的进一步探讨将在第二 2 华中科技大学硕士学位论文 章中给出。 卷积码的概念是由p e l i a s 于1 9 5 5 年提出的。尽管其代数结构以及相关的理论 结果没有分组码那么丰富，但是由于其译码算法具有很强的实用性，因而在编码理 论中也占有相当重要的地位。线性分组码的特点是每个n 元组码字都是由k 元组输 入消息唯一的决定( n 为码字长度，k 为信息位长度) ，每个码组只同本码组的信息 位和校验位有关，即编码时候码字间是相互独立的。而卷积码不同于分组码的一个 重要特征就是编码器的记忆性，卷积编码过程中产生的n 元组，不仅仅是输入k 元 组的函数，而且还是前面k 1 个输入k 元组的函数( k 为卷积码的约束长度，k n 表示编码效率) s l 。卷积码的另一个显著特点就是软判决译码算法比较硬判决译码 算法的复杂度并不会高多少。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 t e r b i 算法，在通讯工程领域得到 了广泛的应用。 7 0 年代末，8 0 年代初( 2 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 dm 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 。 信道编码定理指出，随着码长n 的增加，译码错误概率按指数接近于零。因此 为了使码有效就必须用长码。但是，随着码长的增加，在一个码组中要求纠错的数 目也会相应的增加，译码器的复杂性和计算量也会相应的增加，跌致难以实现。为 了解决性能与设备复杂性的矛盾，g d 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 ) 的概念，把编制长码的过程分为几级，通常为两级 来完成。级联码一般以r s 码作为外码，而以卷积码作为内码。f o r n e y 的性能分析 表明，级联码的性能改善了很多，而译码复杂度增加的并不多。级联码不仅具有极 强的纠突发错误和纠正随机错误的能力，更重要的是利用级联码的构造方法，能达 到信道编码定理所给出的码限，也就是构造出渐进好码( s h a n n o n 码) 。1 9 7 2 年贾斯 特逊首先用级联码的构造方法，具体的给出了构造类渐进好码- j u s t e s e n 码豹 方法，当n 一一时，其性能能够达到信道缠码定理所指出的限。正是由于级联码好 的渐进性能，后来又发现它可以构造一类具有极好性能的密钥分散保管系统，因此 级联码目益引起人们的极大兴趣口】。 华中科技大学硕士学位论文 1 2 信道编码的应用 随着信道编码理论的不断发展，信道编码技术在计算机，通信工程领域得到了 广泛的应用。特别是数字通信的兴起，为信道编码提供了广阔的应用空间。编码技 术应用在了各种数字通信系统中，对数据传输进行差错控制，大大降低了误码率， 提高了数据传输的可靠性，实现了稳定的通信。纠错码的应用领域包括：深空通信， 卫星通信，数据传输，移动通信，文件传输，数据存储以及数字视频音频传输等。 早期的编码理论主要应用于深空通信和卫星通信中，这主要有以下方面的原 因：深空信道是最为典型的无记忆a w g n ( 加性高斯白噪声) 信道模型，而s h a n n o n 的信道编码定理正是基于此模型提出的一般性结论。理论分析结果和计算机仿真结 果几乎和实际系统一致。深空信道的频带资源丰富，这就允许在系统中采用频带利 用率比较低的码和b p s k 调制方式。由于传输距离比较远，信号衰减比较严重，需要 采用纠错能力很强的码。深空通信一般都具有非实时的，功率受限的特性。这些原 因都使得纠错码技术自问世以来，就和深空通信结下了不解之缘。r m 码十软判决最 大似然译码，卷积码+ 软判决序列译码，卷积码+ 软判决v i t e r b i 译码在深空通信中 都可以找到应用的例子。1 9 8 7 空间数据系统顾问委员会( c c s d s ，c o n s u l t a t i v e c o m m i t t e eo ns p a c ed a t as y s t e m ) 采用r s ( 2 5 5 ，2 3 3 ) 码和( 2 ，l ，7 ) 卷积码 构成串行级联码作为标准。 纠错编码技术还广泛的应用于计算机存储系统，包括高速计算机存储器，以及 磁盘和光盘。在这种应用上比较典型的是r s 码。r s ( 1 5 ，9 ) 码为光存储系统的标 准纠错码。在i b m l 3 6 0 计算机系列光盘存储器中采用r s ( 3 6 6 ，3 0 0 ) 码，在 d i g i t a l c y p r e s s 中采用r s ( 6 1 ，5 0 ) 缩短码。高速计算机系统的存储系统对差错 控制1 1 0 有如下的要求： 1 编译码速度要求要非常快，以保证读写速度，对于纠错码的编译码具有很高 的适时性要求，因此，用于存储系统的纠错码往往利用组合逻辑电路来实现并行的 编译码。同时，尽量降低译码的硬件复杂度和提高译码效率。 2 码率相对较高。对于高速存储而言，码率越低，意味着硬件造价越高。而且， 考虑到存储系统中的适时性，以及相对较低的误码率和良好的传输媒介，采用较高 的编码效率是符合实际和经济的。 3 常见的错误类型是字节型错误。 损伤，比如光盘的划痕等弓f 起的错误， 这与其实现存储的物理机制有关。一些物理 具有突发的特征。 4 华中科技大学硕士学位论文 。因此，在存储系统中用的较多的r s 码常常是高码率，或者是较短的码字，以 利于译码硬件比较简单，译码延迟要短的要求。r s 短码应用到独立磁盘冗余阵列中， 用于纠单个错和纠双个删除错误，比采用n + i 的奇偶校验的阵列系统具有更高的可 靠性【1 1 。 纠错码还广泛的应用于数字视频系统m 1 中。由于在数字视频系统中要求差错控 制能够高速译码，因此直到二十世纪九十年代，强力纠错码才应用到该系统中。1 9 9 0 年制定的i t u th 2 6 1 标准中，建议使用( 5 1 1 ，4 9 3 ) b c h 码。这是第一个采用差 错控制的数字视频标准。在m p g e 一2 数字视频标准中，使用了基于r s 码的复杂差错 控制。在d v b 中使用了级联码，外码采用r s ( 2 0 4 ，1 8 8 ) 码，内码为( 2 ，1 ，7 ) c c s d s 卷积码。目前r s ( 2 0 4 ，1 8 8 ) 已经成为欧洲数字视频广播和日本i s d b ( i n t e g r a t e ds e r v i c e sd i g i t a lb r o a d c a s t ) 中级联系统的标准外码。 从上文我们可以看到，纠错码尤其是经典r s 码在各个领域有着颇为广泛的应 用，或者作为单独的纠错码，或者作为级联码系统中的成分码( 一般为外码) ，这些 同r s 码的特性是分不开的： 1 r s 码码字是多进制符号，而不是二进制符号。例如，对于r s ( 2 5 5 ，2 2 3 ) 码，每个码字符号对应于计算机的一个字节，这对于设计硬件处理电路，以及数据 的转换和处理，进行r s 的硬判决译码，都会带来极大的方便。 2 r s 码具有非常低的错译概率。如果噪声影响超过码字的纠错范围，译码器 一般总是能够查出不能成功译码的情况并作出译码失败的标记。这些信息可以提供 给差错控制系统机制，进行进一步的处理。 3 r s 码是基于分组的码字。有时候处理数据的本身就是具有固定大小的包数 据或者块数据。计量数据的性能，往往是针对整个包或者块，进行b e r 计算，或者 s e r ，p e r 计算，采用适当的r s 码组，将会带来很大的方便。 4 r s 码字符号的结构设计是针对纠正突发错误的。具体来说，对于r s 码，一 个码字符号中出现多个比特的错误，与出现一个比特的错误，对于整个码字的译码 效果的影响是样的( 具体原因将在第二章给出详细论述) ，因此，在数据传输过程 中采用多比特载波调制方式，纠错性能将会比单纯的随机噪声影喻要好。 5 r s 码采用系统码的时候，信息位处在码字的前k 个符号或者后k 个符号， 校验数据附加在码字前面或者后面，对于用户提取数据和进行数据帧同步都会带来 方便”】。 华中科技大学硕士学位论文 1 3 沦文研究内容及结构安排 如上文所述，差错控制编码在通信、计算机系统中有着广泛的应用，已经成为 现代通讯系统、数字处理系统和计算机设计中的不可缺少的一部分。基于分组码和 卷积编码的不同特性，他们在应用方面也有着分别。卷积编码适用于对传输速率和 数据完整性要求都相对较低的系统，卷积码和分组码的级联码多用在传输速率相对 较低，数据完整性要求较高的系统，而单纯的分组码则用在对两者要求都比较苛刻 的系统中【l ”。本文依据数据链控制器的性能要求，对于传输速率不是要求太高，而 要求在尽量低的信噪比下达到较高的数据可靠性的特性，考虑选择级联码作为系统 编码的方案。由于r s 码不仅具有较高的编码增益，而且对于长的突发错误具有很强 的纠错能力，选择r s 码作为级联码系统的外码。同时，内码采用p t c m 编码技术， 在不增加系统功率和降低频带利用率的同时获得编码增益。论文依据高斯信道模型， 分别针对q p s k ，8 p s k 调制方式，对系统内码，外码作出了详细的研究分析和设计， 以期以最小的硬件，软件开销达到数据传输系统所要求的性能参数。 ， 论文具体内容安排如下：第一章介绍了信道编码的基础理论以及纠错码学科产 生发展过程，同时阐述了纠错码的应用领域，以及级联码中关键码的特性。第二章 详细论述了级联码成分码的编译码原理及算法。第三章针对r s 码的软判决译码算 法，重点讨论了两种采用不同硬判决译码器的软判决译码设计，并在原有方法的基 础上作出了一定的改进，提出了基于调制符号可信度的软判决算法，有效的降低了 计算复杂度同时提高了译码性能。第四章针对p t c m 内码，就其编码方法和软判决译 码设计作出了详细的论述，给出了软判决译码器的设计结构，并分析了译码器的译 码性能，和给出了计算机仿真结果。第五章结合系统仿真工具m a t l a b s i m u l i n k ， 对系统的仿真实现做了详细的讨论，给出了实现系统仿真中需要解决的几个关键问 题，本章最后对采用其他进一步提高系统性能的技术做了简要讨论。 华中科技大学硕士学位论文 2 级联码系统编译码 如第一章所述，本章讨论级联码系统采用r s 码作为外码，基于卷积码编译码算 法的p t c m 方式编码作为内码。本章阐述了内外码的编译码过程，级联码系统所采用 的编译码算法。 2 1r s 码编译码 r s 码的全称是r e e d s o l o m o n 码，是i s r e e d 和g s o l o m o n 【1 4 1 在1 9 6 0 年发 现的。同年，r c b o s e 和d k r a y c h a u d h u r i 【1 5 1 独立于a h o c q u e n g h e m “1 发现 了b c h 码。1 9 6 1 年d c g o r e n s t e i n 和n z i e r l e r 注意到r s 码是一类特殊的b c h 码，其位置域和符号域是同一个域。r s 码是迄今为止所发现的一类很好的线性纠错 码类，它的纠错能力强，特别在短码和中等码长下，其性能很接近理论值，并且构 造方便，编码简单，编译设备也不太复杂。正是由于该码的超强纠错能力及各种成 熟、可用、有效的译码算法，它在工程中被广泛的应用。r s 码的编译码均是在特定 的有限域内进行码字的所对应的域元素的计算，因此本章首先介绍域的相关概念及 运算。 2 1 1 有限域及其计算实现 域是由加法和乘法两种运算的一些元素组成，在每种运算下都有逆元素存在， 因此域中同样有减法和除法存在，因为我们可以通过加上或者乘以该元素的逆元来 实现和该元素的减法及除法。构成域的元素必须满足以下一些条件： 1 域元素对于定义在该域上的运算：加法和乘法满足封闭性。即：任何两个域 元素之和或者积仍然是该域的元素。 2 对于每种运算，各元素满足通常的结合律和交换律。 3 乘法与加法间有分配律。 4 域内对于加法运算具有加法逆元和加法恒元。即对于任意域元素k ，存在加 法恒元0 满足：k + 0 = k ，加法逆元一k ，满足k + ( 一k ) = 0 。同时，域内存在乘法恒元l ， 和对非零元素存在乘法逆元，即：k xi = k ，kxk 。= l 。( k o ) 。 7 华中科技大学硕士学位论文 域内元素的数目叫做域的阶，记为q ，可为有限或者无限。有限域又称为伽罗 华域，记为g f ( q ) ，g f ( q ) 的一个重要的特征就是每个有限域至少包括一个叫做口 的本原元素，该元素的( 0 一q 一2 ) 次幂就是这个域中的( q - i ) 个非零元素，它们互 不相等。因此g f ( q ) 内所有域元素可以表示为：( o ，1 ，口，口2 ，口g 一2 ) 。( 口= 口o = l ，因为域元素的周期等于域的特征q ，a 的级为q l ，关于域的详细论述请参 阅文献 5 ) 由于r s 码编译码运算通常定义在特征为q = 2 ”的域上，同时计算机数据存储 及计算都是基于二进制数据，因此取q 为2 的幂指数，对于实际使用是非常方便的。 由于域上共有q 个元素，对应于所有m 维空间的矢量元素。在进行域元素的加法运 算时，通过将域元素转换成二进制数据进行异或，然后再转化成对应的域元素保存。 进行域元素的乘法时，选用本原元指数形式来表示每个域元素，这样域元素间的乘 法转化为本原元指数的加法，然后对域的阶减一即( q 1 ) 求模就得到了两者相乘的 结果，这时候的结果还是以本原元指数的形式保存的，可以再通过相应的表格映射 到二进制或者十进制数据。在以上的域元素运算的过程中，域元素二进制表示蓟本 原元指数形式的表示之间的相互转化需要建立相应的映射方式，在程序中通过建立 两个数组来实现，一个数组数值保存该数组下标所对应的本原元幂指数的十进制数 值，另外一个数组保存下标为十进制数据时所对应的本原元幂指数值，例如，针对 g f ( 2 4 ) 域相应建立的两个数组为： a l p h a - t o 1 6 = 】，2 ，4 ，8 ，3 ，6 ，1 2 ，l l ，5 ，l o ，7 ， 4 ，1 5 ，1 3 ，9 ，1 ) ； i n d e x t o 1 6 = 一1 。0 ，1 ，4 ，2 ，8 ，5 ，l o ，3 ，1 4 ，9 ，7 ，6 ，1 3 ，1 1 ，1 ( 这里 定义口= 0 ，程序实现的时候取一1 作为标志，数组下标从零开始) 。 2 i 2 r s 码编码过程 r s 码的编码原理及编码器的实现比较简单，而译码相对来讲要复杂的多。就r s 码的编译技术而言 1 ，存在时域和频域两种算法，其中时域算法出现较早，比较成 熟，用的较为广泛。因此，r s 码的编译码存在：时域频域，时域时域， 频域时域，频域频域等不同的结合方式，文献 i s 给出了一种时域编码， 频域译码的编译码方式，本文主要讨论基于对域的编译码方式，作为后文进行级联 码设计的基础。r s 码的时域编码主要是围绕码的生成多项式g ( x ) 进行的。对于能 够纠正t 个错误的r s ( n ，k ，d ) 码，具有如下的特征： 1 码长：n = 2 ”一1 ； 8 华中科技大学硕士学位论文 2 信息符号数目：k = n 一2 t ； 3 校验符号数目：2 t = t 一k ； 4 码字最小距离：d = 2 t + 1 = 月一k + 1 。 最小距离为d 的本原r s 生成多项式为： g ( x ) = ( x 一口) ( 工一口“) ( x a + 2 ) ( x a “+ 4 以) 。 式中m 是一个任意整数一般情况下我们取m = l ，则生成多项式为： g ( x ) = ( x - - 口) ( z 一口2 ) ( x 一口3 ) ( 工一口2 ) 下面考虑系统码编码方式，令信息符号多项式表示为： z ( 功= q - a l x + a 2 2 2 + + 口工“，其中啦g f ( 2 ”) 域元素。 编码过程为将信息多项式乘以多项式x ”。除以生成多项式，将得到的余式同原信息 多项式乘以z ”后的多项式相加就得到编码后的码字多项式。公式表示为： 1 x - k x f ( x ) 叫砷+ 器( r ( x ) 为余式) 编成的码多项式为：c ( x ) 鼍x n - k z ( 曲- t - r ( x ) 。 在程序中利用g f ( 2 “) 域上的乘法和加法实现竖式除法求出k 位校验位附加在 x ( x ) 之后即可完成编码。 程序中实现该竖式除法的相关代码如下： f o r ( i = 0 ：i k k ：i + + ) f e e d b a c k = d a t a i b b 0 3 ： f o r ( j = 0 ：j n o _ p 一1 ：j + + ) b b j = b b j + 1 “g f m u l t a b ( g g _ p o l y n o _ p - i j ，f e e d b a c k ) ； ) b b n p _ p 一玎= g f l u l t a b ( g g _ p o l y 0 ，f e e d b a c k ) ： ) 代码中d a t a ，b b ，g g _ p o l y 分别保存信息多项式，余式多项式，生成多项式的系数， 均以该域本原元的指数幂的形式来表示，g f m u l t a b 为实现相应的g f ( 2 “) 域元素 相乘的子程序。 2 1 3r s 码的译码过程 9 华中科技大学硕士学位论文 1 9 6 0 年，p e t e r s 6 m 首先解决了二元b c h 码的译码问题，g o r e n s t e i n 与z i e r l e r 推广了p e t e r s o n 的算法，三人给出的算法虽然从概念上晟容易理解，但是在译码的 过程中需要计算矩阵的逆，工程上计算量比较大。1 9 6 8 年，e r b e r l e k a m p i i ”提 出的迭代译码算法绕过了这一障碍，随后j l m a s s e y 从序列综合的角度重新推导 了b e r l e k a m p 算法，因而后人称之为b m 迭代译码算法。由于该算法能够很方便的通 过计算机编程实现，并且计算量也相对较小，很快被广泛应用于r s 译码工程实践中。 采用b m 算法进行代数译码的基本框图如图2 1 所示。 图2 1r s 译码器译码结构流程图 1 计算伴随式 经过编码器编码的码字记为： c ( 曲= 一1 z 肛1 + 巳一2 x 俨2 + c t x + c o ( 2 1 ) 码字经过信道传递，有可能发生错误，错误图样e ( x ) 记为： e ( x ) = e n l z ”1 + 巳一，工”2 + e t x + e o ，其中e ( x ) 多项式中至多有t 项系数不为零， 否则错误不在r s 码纠错能力范围内，这里不予讨论。从而接收的码字多项式为： r ( x ) = c ( 工) + e ( 力= r 。_ s x 卜1 + 一2 x 卜2 + r l x + r o ( 2 2 ) 由r s 码的编码原理，口为g f ( 2 “) 域上的本原元，则相应的a ，口2 ，味“， 均为码字多项式的根，从而校验矩阵为： 口n - t 钕2 ) “ _， ( 口2 ) 乎1 若信道产生t 个错误，则 口n _ 2 妇2 n - 2 ( a 2 ) 2 口2 缸2 ) 2 + ( 口2 。) 2 a1 p 2 ) 1 - 似2 。) l 华中科技大学硕士学位论文 e ( 石) = i + i - 1 z 一+ + x x = 誓， ( 2 3 ) i = 1 式中，i g f ( 2 ”) ，称为错误位置数，说明错误发生在r ( x ) 中的第n t ( z ”1 的 系数算第一位) 位，错误值为。如果r ( x ) 中有y 个错误，则e ( x ) 共有y 项。计算 伴随式： s 7 = 日r 7 = 日e 即： t 0 = i ( a ) ，j 2 1 ，2 ，2 t l 一1 令位。铲= x ，可得 fj 0 = 取，= 1 ，2 ，2 t 。 ( 2 4 ) i = 1 i 由此我们得到关于2 t 个未知数z 和五的由2 i 个方程组成的方程组，称之为r s 译码的关键方程，求解该方程组得到错误值和错误位置即可纠正得到正确的码字。 直接求解上述方程组一般情况下比较复杂，为此，进行译码的第二步。 2 求解错误位置多项式 定义错误位置多项式： 仃( x ) = ( 1 一x , x ) ( 1 - x = x ) ( 1 - x , x ) = 1 + q x + 仃2 x 2 + + q 一 ( 2 5 ) 若第k 个位置错误位置石= ，则有盯( 1 ) = 0 。因此，求错误位置就是求解错误 位置多项式的根。由d ) = 0 ，得到：仃o j = l + q 矗。+ 吒砟2 + + o t x k = o ，乘 以k ，则：矿+ q 耳”1 + + 吒k = 0 ，求和得： e x f “+ q k 工：+ t - 1 + + 吼k “= o ， k = lk = l r t l 依据式( 2 4 ) 可得：。十q 0 。+ + q 0 = o , j = l ，2 ，t ， s ts t - i s 挣ls t s 2 1 is 2 t - 2 s 1 s 2 ： s c q c r 2 - 皿 s ”l s t + 2 吒t ( 2 6 ) 采用b m 迭代算法求解方程组( 2 6 ) 。其基本原理为引入辅助多项式错误值多项式。 定义：( 工) = s ( 曲盯( 曲，由等式两边多项式系数之间的关系可以推出求盯( x ) 的关键 方程： j ( 础，( 砷= 钟g ) ( m o d x 2 “1 ) ( 2 7 ) 1 1 华中科技大学硕士学位论文 ( 详细推导过程请参阅文献 5 ) ，用迭代方法求解式( 2 7 ) 就是首先选择一组或者 两组合理的初值如仃( o ( x ) 和( o ( x ) ，然后开始第一次迭代运算求得盯( 1 ( x ) 和 ( 1 ( 工) ，并用盯( o ( x ) 和国( 0 1 ( x ) 表示它们。这样依次进行，首先计算出满足式( 2 7 ) 的口( 艽) 和c o ( x ) 的低次项，然后通过逐步迭代求得c r ( x ) 和0 4 x ) 的高次项。在求解 o r ( x ) 的过程中，为使得解唯一，必须保证盯( z ) 的次数最小，且珊( d 的次数不大于 盯( x ) 的次数，为此在迭代过程中需要对( 曲加上修正项d ，逐步进行修正求出修 正项d i ，最终求得仃但( x ) 。其迭代算法的流程图如图2 2 所示。 图2 2 迭代算法流程图 华中科技大学硕士学位论文 3 钱搜索求错误多项式的根。 用迭代译码算法求得错误位置多项式之后，进一步的问题就是如何简单的求出 它的根，即错误位置。知道式( 2 5 ) 的各项系数后，要确定接收码字 r ( 工) = c ( 互) + e ( x ) = 一l x 舯1 + 一2 x 卜2 + r l x + r o 中的l 位是否出错，相 佥验t 3 e - 是 否为c r ( x 1 的根，由, g f ( 2 ”) 域本原元的性质，口= 口”i ，即将取不同的i 值的口， 代入盯( x ) 检验结果是否为零便可以确定，相应的口“是否为错误多项式的根。 4 求错误值 在第二步中利用b m 算法求解关键方程的过程中，我们同时得到了错误值多项式 ( z ) ，此时c o ( x ) 是已知的。由f o r n e y 公式求解错误值： ( = 竺! 量：2 t f l 7 ( 1 一x i 。1 巧) 搿 当错误位置和错误值都计算出来以后，也就得到了错误图样e ( x ) ，就可以针对相应 的位置进行纠错，恢复原来的发送码字： c ( x ) = r ( x ) + e ( x ) 以上讨论了后文实现r s 硬判决所采用的译码算法，在纠错码发展中关于r s 码 的译码算法存在着丰富的成果，r s 码的译码关键方程也可以利用e u c l i d e a n 1 算法 求解，同时还有基于余式1 的译码算法和频域译码【1 8 1 等有特色的算法，可参阅相 关文献。 2 2 卷积码编译码 卷积码是1 9 5 5 年由爱里斯提出的，如同在第一章中提到的，它与分组码不同： 分组码中本组的n - k 个校验元仅仅和本组中的k 个信息元有关，与其他组的码元无 关。分组码译码时，也只是从本组中提取有关译码信息。卷积码编码中，编码码字 不仅与本组的信息有关，而且与先前时刻其他组的信息有关。同样，在卷积码译码 的时候，不仅需要从当前时候收到的码组中提取译码信息，同时还要利用保存的以 前一段时间内的码组，来进行译码。卷积码以“位”为单位进行，因此编码设备比 分组码简单。 华中科技大学硕士学位论文 2 2 1 卷积码的编码 设卷积编码器中有m 个寄存器，则m + l = n 为编码约束度，表示编码过程中相互 约束的码元个数；r l 表示编码器的输出码元的个，n x n 表示编码约束长度；k 表示 输入的码元个数，卷积码表示为( r l ，k ，m ) 。目前在国际卫星通信和很多通信系统 中，( 2 ，l ，6 ) 码是首选的使用v b 译码的标准卷积码，由于该码能使误码率达到最 小，属于透明码，对于使用v b 译码中解决码元相位模糊问题非常有用 5 1 ，在工程 实际中有着广泛的使用。因此，本文在设计内码的编码方式时，采用基于这种结构 的卷积码编码方式的t c m 编码( 具体编码方式将在第四章中给出) ，其编码器的逻辑 结构图图2 3 所示。 图2 3( 2 ，1 ，6 ) 卷积码编码器逻辑结构图 如图，该码的两个子生成元分别为( 1 7 1 ，1 3 3 )