（通信与信息系统专业论文）多个码字交叠的编码和译码原理与方法的研究.pdf

摘要 摘要 在信道编码史上出现了不少有力的由已知短码构造有效长码的方法，这不仅 有利于提升单个短码的纠错能力，针对具体信道构造出不同纠错能力新的分组码； 也有利于不同长度消息的传输。 本文在码长较短的分组码编码和译码基础上提出了一种新的编译码算法，即 多个码字的交叠编码和交叠译码，通过多个码字之间部分符号或比特的交叠构造 出新的码字，在译码端循环迭代译码并恢复交叠的符号或比特。本论文力求与原 码截断码和原码相比在性能上有提高，且在一定程度上要好于一些长码，如r s 码。本文主要的研究结果如下： 1 介绍了现有几种的由已知短码构造新的长码的方法。 2 分别讨论了分组码的纠错能力和最大似然译码，并进一步详细论述了系统 循环码的编码原理；介绍了完备码和非完备码的区别了以及本文中用到的两种完 备码和非完备码，即戈莱码和r s 码。 3 详细研究了基于戈莱码的多个码字的交叠编码和译码。论述了提高交叠译 码性能的关键：迭代译码算法，并在此基础上扩展了迭代译码算法。整体上改进 了多个码字交叠译码算法，并讨论和分析了影响其性能的编码参数。通过大量仿 真可以得出，3 个码字交叠编码且交叠位数为6 比特的交叠戈菜码与码率相同的 ( 1 7 ，6 ) 缩短戈莱码相比，在相同的误比特率下，相应的e d n o 会少1 d b ；3 个码字 交叠编码且交叠位数为1 比特的交叠戈莱码与原码相比，当e b n o 为1 0 r i b 时，误 比特率降低了1 0 1 0 。 4 仿真分析了基于r s 码的多个码字的交叠编码和译码方法，并和较长的r s 码进行了性能上的仿真比较。介绍了另一种交叠编码，a 0 - - 维交叠编码和相关译 码原理，并与原r s 码和原r s 码的截断码在a w g n 下进行了比较。通过仿真得 出在误码率为3 x 1 0 - 8 时，基于0 5 ，1 3 ) r s 码的3 x 3 序列交叠码的e b n o 约为1 0 5 2 d b ， ( 1 5 ，1 3 ) r s 码e d n o 约为1 l d b 。 5 总结了多个码字交叠编码和译码的优缺点，提出了交叠编码和译码还有待 改善的部分。 关键词：交叠编码，迭代译码，g o a l y 码，r s 码 a b s t r a c t a b s t r a c t i nt h ec o d i n gf i e l d s ，t h e r ei sm u c hp o w e r f u lt e c h n i q u ef o rc o n s t r u c t i n g l o n g p o w e r f u lc o d e sf i o ms h o r tc o m p o n e n tc o d e s ，a n dt h ep e r f o r m a n c ei sn i c e i ti sn o to n l y g o o df o rp r o m o t i o nt h ep e r f o r m a n c eo ft h eo r i g i n a lc o d e ，b u ta l s ot h et r a n s m i s s i o no f t h ei n f o r m a t i o n , a n dw e 锄c o n s t r u c td i f f e r e n tl e n g t ho fn e wc o d e sw i t hd i f f e r e n t c o r r e c t i n gc a p a c i t yi ns p e c i a lc h a n n e l i nt h i sp a p e r , an e wc o d i n ga l g o r i t h mi sp u tf o r w a r db a s e do nk n o w nb l o c kc o d e t h r o u g he x c h a n g i n gs o m eo fs y m b o lo rb i t si nc o d e s ，e n c o d e st h en e w , a n dg e t st h e i n f o r m a t i o nb yi t e r a t i v ed e c o d i n ga n do v e r l a p p i n gs y m b o lo rb i t s t h ep e r f o r m a n c eo ft h i sn e wm e t h o di se x p e c t e dt ob eb e t t e rt h a nt h eo r i g i n a l c o d e s ，e v e nm o r et h a ns o m el o n gp o w e r f u lc o d e s ，s u c ha sr sc o d e s t h em a i nr e s u l t s i nt h i sp a p e ra r ea sf o l l o w s ： 1 n e wc o d e sa r ec o n s t r u c t e db ye x i s t i n gk n o w ns h o r tc o d e s ，w h a ti sd i s c u s s e di n t h i sp a p e r 2 t h ea b i l i t yt ob l o c kc o d e sa n dm a x i m u ml i k e l i h o o de r r o rd e c o d i n ga r e i n t r o d u c e d ，a n dt h ec o d i n gp r i n c i p l eo fc y c l i cc o d e si s d i s c u s s e d c o m p a r e st h e c o m p l e t ec o d e sw i t hi n c o m p l e t ec o d e s ，a n dt h e ni n t r o d u c e sg o l a yc o d e sa n dr sc o d e s 3 d e t a i l e di n t r o d u c e st h en e wm e t h o do fc o d i n ga n dd e c o d i n gb a s e do ng o l a y c o d e s ，a n dp o i n t so u tt h a tt h ek e yt op r o m o t et h ep e r f o r m a n c ei si t e r a t i v ed e c o d i n g b a s e do nt h ek e ys t e p ，t h ei t e r a t i v ed e c o d i n gi si m p r o v e d t h ew h o l ep r o g r e s so f o v e r l a p p i n gd e c o d i n gi sm a d eb e t t e rb ya d d i n g $ a l ：n es t e p s ，a n dt h ei n f l u e n c eo ft h e d i f f e r e n tp a r a m e t e r so nc o d i n gi sd i s c u s s e d a c c o r d i n gt os i m u l a t i o n , t h ep r o m o t i o no f s i g n a l t o - n o i s eb e t w e e nt h i sn e wm e t h o da n dt h et r u n c a t ec o d e sw i t ht h e $ r m eb i tr a t e i sld b ；w h e nt h ee b i r n 0i s10 d b ，t h ei m p r o v e m e n to ft h eg l t o rb i tp r o b a b i l i t yb e t w e e n t h i sn e wm e t h o da n dt h eo r i g i n a lc o d e si s10 m 4 b a s e do nt h es i m u l a t i o nf o rr sc o d ew i t hd i f f e r e n tc o d e sl e n g t h , a n a l y z e so ft h e n e wm e t h o do fc o d i n ga n dd e c o d i n gb a s e do nr sc o d e an e w o v e r l a p p i n go fp r i n c i p l e o fe n c o d i n ga n dd e c o d i n gi si n t r o d u c e d , a n dt h ep e r f o r m a n c eo ft h i sn e wm e t h o di s c o m p a r e dw i t ho r i g i n a lr sc o d ea n dt h es h o r t e nc o d e a c c o r d i n gt os i m u l a t i o n , w h e n a b s t r a c t t h ee r r o rb i tp r o b a b i l i t yi s3x10 。8 ，t h ee b n 0o ft h el l e wm e t h o di s10 5 2 d b ，a n dt h e o n eo ft h eo r i g i n a lc o d e si slld b 5 f i n a l l ys u m m a r i z e st h eo v e r l a p p i n gm e t h o do f e n c o d ea n dd e c o d e , a n dr e m a i n s t h ep a r t st ob ei m p r o v e d k e y w o r d s ：o v e r l a p p i n gc o d e ，i t e r a t i v ed e c o d e ，g o l a yc o d e s ，r sc o d e s 1 1 1 图表目录 图表目录 图1 1 乘积码g c 的码矩阵2 图2 1 码字和汉明球4 图2 2 ( 以，七) 循环码的系统编码电路1 1 图2 3 ( 7 ，4 ) 汉明码和( 2 3 ，1 2 ) 戈莱码的性能仿真1 2 图3 1 交叠信息16 图3 2 交叠信息编码1 6 图3 3 缩短码字1 7 图3 4 向右交叠译码18 图3 5 向左交叠译码18 图3 - 6 舅和咒+ i 迭代译码输出q 和q 扩1 9 图3 7 迭代译码算法流程图2 2 图3 8 向右交叠译码2 3 图3 - 9 向右交叠译码中，且的三个不同输出2 6 图3 1 0 向右交叠译码2 7 图3 1 1 整体迭代译码算法流程3 0 图3 1 23 码和8 码交叠整体迭代译码性能比较3l 图3 1 3 改进算法总流程3 2 图3 1 4 交叠译码改进前后性能比较3 3 图3 15 步骤1 算法流程图3 3 图3 1 6 交叠信息替换3 4 图3 1 7 步骤l 算法流程图3 5 图3 18 步骤1 比较3 6 图3 1 9 不同起点的交叠译码3 7 图3 2 0 步骤3 算法流程图3 8 图3 2 1 总流程3 8 图3 2 2 不同交叠码字数的性能比较3 9 图3 2 3 不同序列数目的迭代译码性能比较4 0 图3 2 4 不同迭代译码次数的比较4 1 图表目录 图4 13 码字交叠r s 码与较长r s 码的比较4 2 图4 2 交叠码字构成4 3 图4 3 二维交叠编码4 4 图“基于( 1 5 ，1 3 ) r s 码交叠码的仿真性能4 7 图4 _ 5 基于( 1 5 ，11 ) r s 码交叠码的仿真性能4 7 图4 - 6 基于( 1 5 ，9 ) r s 码交叠码的仿真性能。4 8 表3 1 交叠编码与( 2 3 ，1 2 ) 戈莱码仿真数据比较3 1 表4 1 交叠r s 码与( 1 5 ，1 3 ) r s 码的性能比较4 8 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：牡吼籼7 年细7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 日期：砷年r 月f 碉 第一章引言 1 1 研究背景、意义 第一章引言 香农指出：在有噪信道下，使用长度( 或约束长度) 足够长的序列分组可以在不 超过信道容量c 的任意信道速率r 下，使得误码率足够小。在得出上述结论过程 中，香农证明了采用随机选择编码并且译码算法采用最大似然译码，能够获得接 近信道容量的性能；并且随着分组长度( 或约束长度) 的增加，译码后的误码率将会 随着随机选择的一组码字的平均性呈指数下降。基于这一原因，构造好的长码一 直是编码学家在研究的问题。在现今编码领域已经有很多由已知码构造新的长码 的方法。 里德穆勒码( r e d m u l l e r , r m ) 码是一种纠正多个差错的分组码。m u l l e r 于 1 9 5 4 年发现这种码【l 】，但它的第一个译码算法是由r e e d 于同一年设计出来的【2 】2 。 在现代通信系统中，r m 码是一类极其重要的线性分组码【3 】【4 1 。因为该码有着非常 特殊的的结构特性并且非常易于使用软判决或硬判决进行译码，从误码率性能和 译码复杂度两方面考虑，r m 码通常还要优于一些更高效的码。r m 码可以通过同 构平方构造法来产生，长r m 码可由短r m 码通过反复使用平方构造法来得到， 可以说r m 码是由短码来构造高效长码的一个很好例子。 乘积编码( p r o d u c tc o d i n g ) 是由短的分组码构造高效长分组码的一种技术【5 】。设 q 为( n l ，局) 线性系统分组码，g 为( ，如) 线性系统分组码。那么，可以构造一个 ( ，l i ，k , k 2 ) 线性分组码，使得构造后每个新的码字为一个，l i 列玎，行的矩形阵列，其 中每一行都是g 中的码字，每一列都是g 中的码字，如图1 1 所示。该码字的信 息位是位于矩阵右上角的毛哎个符号，其它部分都是校验符号。矩阵的左上角表示 行校验位，它是对毛哎个信息位在行上按照c 的编码规则计算得到，同理矩阵中的 右下角表示列校验位，它是在列上按照c 的编码规则计算得到的，最后，左下角 的符号表示校验位的校验位，因为它是对校验位的编码，可以通过在列上对行校 验位按照g 的编码规则来计算得到，也可以在行上对列校验位按照c 的编码规则 来计算得到。对校验位的编码无论是在行上对列校验位编码还是在列上对行校验 位编码，都可以得到相同的( ，l i 一) ( 毛一岛) ( 证明见附录a ) 个校验码位，并且可 以同时使得所有的行都是q 中的码字，且所有的列都是g 中的码字【5 1 。在发送乘 电子科技大学硕士学位论文 积码的时候，可以按列发送，也可以按行发送。在译码时，对应着编码的顺序就 能得以实现。 行校验位信息位 校验位的校 验位 列校验位 图1 - 1 乘积码qx c 2 的码矩阵 级联码是由f o r n e y 在1 9 9 6 年发现的，它是除乘积码、r m 码以外另一种由短 码构造高效长码的有力技术。随着译码复杂度的降低，在双边通信和数字存储系 统已经广泛得使用非二进制码作为外码、二进制码作为内码的单级级联码来获得 更高的可靠性。在级联码中，内码通常较短并且采用软判决译码算法；而非二进 制的外码则较长，译码时采用代数译码的方法，在很多实际应用中，通常将r s 码 作为外码来使用。级联码也可以多级级联，将多个外码和多个内码级联起来。多 级级联码能够更加灵活的构造出好码，且更加适合针对不同通信系统设计出不同 码率的差错控制系统来。通过使用多级级联，已经由非常简单短小的内码和外码 构造出了大量好码。此外，由短的内码和外码构造长的多级级联码的逆过程是将 已有的长码分解为简单短小分量码的多级级联【6 】。 级联码对克服随机错误和突发错误的组合非常有效。如果级联码要纠正某个 突发错误，那么通过g 码不能被纠正的错误比特可以在多元域上由c 码来纠正。 另外，如果分散的随机错误个数超过e 码的纠错能力，则这较少的几个字节可以 由c 码进行纠正。级联构造长码的方法，对编码学者有很大的启发。为了提高空 时分组码所获得的少量的编码增益，可以和其它信道编码技术级联，级联后的性 能提升明显【7 j 。一个常见的例子就是用t u r b o 码作为外码，空时分组码作为内码， 2 第一章引言 这个方案也被称为空时t u r b o 码【8 】【9 】【1 0 1 。 本文通过在对码长较短的分组码编码和译码基础上提出了一种新的编译码算 法，即多个码字的交叠编码和交叠译码，通过交换添加多个码字之间部分符号或 比特来构造新的码字，从而在译码端通过一定判断条件在多次循环中调用已知码 的硬判决译码来恢复交叠的符号或比特。本论文力求与原码的截断码和原码相比 在性能上有提高，且在一定程度上要好于一些长码，如r s 码。 1 2 本文结构安排 第一章介绍了现有几种的由已知短码构造新的长码的有效方法，并提出了本 文的创新部分，即多个码字的交叠编码和译码。 第二章分别讨论了分组码的纠错能力和最大似然译码，并进一步详细论述了 系统循环码的编码原理；介绍了完各码和非完备码的区别了以及本文中用到的两 种完备码和非完备码，即戈莱码和r s 码。 第三章详细论述了基于戈莱码的多个码字的交叠编码和译码。着重论述了提 高交叠译码性能的关键：迭代译码算法，并在此基础上扩展了迭代译码算法。简 单分析了迭代译码的时间复杂度。从提高性能的角度出发，在整体上改进了多个 码字交叠译码算法，并讨论和分析了影响其性能的编码参数。 第四章仿真分析了基于r 8 码的多个码字的交叠编码和译码方法，并和较长的 r s 码进行了性能上的仿真比较。介绍了另一种交叠编码，即二维交叠编码和相关 译码原理，并与原r s 码和原r s 码的截断码在a w g n 下进行了比较。 第五章对多个码字交叠编码和译码的优缺点进行了总结，并提出了交叠编码 和译码还有待改善的部分。 3 电子科技大学硕士学位论文 2 1 分组码 2 1 1 分组码纠错能力 第二章纠错码简介 不同的编码方案提供了不同的差错控制能力【1 1 1 【1 2 1 【1 3 1 4 1 1 5 】【1 6 1 ，而分组码的纠错 能力又是码距的函数，所以要考察一种码纠错能力的高低往往要先考虑它的码距。 把( 以，后) 分组码的2 个码字看作是位于以维空间的点。如果每个码字都是位于半径 ( 汉明距离) 为t 的球的中心，除去空间中球两两相切的情况，那么t 的最大值可以取 到t = l ( 以岫一1 ) 2i ，这里的l 工i 表示不大于z 的最大整数。任何码字经过信道后可 能会发生差错，如果接收到的有差错的码字与空间中某个码字的汉明距离小于或 等于，它们都会位于以原码字为球心的球内，这样就会将这些点译作该球的球心 处的码字。这就意味着，最小距离为丸如的( 以，k ) 分组码有能力纠正f = i ( 丸妯一1 ) 21 个差错。图2 1 是码字和球的两维示意图。 ，一。、- - - ， 、，- _ ， i i 。、 ，7 。 、 i 、 w f i 、- ，) ，j 7 ( 7 ，：、i ) 、) 、 ， 、， 、，一 、 - ， 、， 、- - ， 图2 - 1 码字和汉明球 从图2 1 可以看出，如果一个码字发生差错，其必将从球心移向空间中的其它 点处，只要不会移动到其它球的球心处( 正确码字) ，就会认为是发生过差错的码字， 所以一个码可以检一1 个差错。同理只要发生差错后的码字不会落到原码字的 球外，就能够被恢复，所以可以纠f 个差错。有的码不仅仅是只纠错或者只检错， 4 第二章纠错码简介 也会纠错和检错功能同时具备。从汉明球之间的距离可以看出，一个最小距离为 的纠错码能检白个差错且纠巳个差错，这里 + 巳d 。i n 一1 ( 2 1 ) 从图中的汉明距离还可以看出，一个码的纠错能力总是要弱于或者等于它的检错 能力及 乞乞( 2 - 2 ) 在理论研究和仿真证明上，要观察不同纠错码纠错能力的好坏是看它的差错 概率，一个纠错码的码字差错概率为 岛窆f ? 1 础1 一) 硝( 2 - 3 ) 其中是信道转移概率。不同分组码译出码字的码字差错概率尼y 无法直接进行 比较。为了比较不同的码，需要将译出的码字的差错概率映射为译出信息的误比 特率，记为只。精确的映射为码字生成矩阵的函数，生成矩阵又决定了码重分布。 幸运的是，已经有了很准确的近1 l ；( 【1 7 1 1 引，这个近似就是 忍丽q 曙d 急d ( 1 ， 1 ) 知砸一尸+ i 1 未。( ：) 砸一广 c 2 q 其中，q 表示g 进制信道，换句话说，对于二进制信道，有g = 2 。而对于常用的 非二进制分组码r s 码，有q = 2 一l 。公式( 2 - 4 ) 可以在理论上很方便的得到很多分 组码的误比特率，从而对验证仿真结果的正确性提供了重要的支持，如图2 3 就是 通过公式( 2 4 ) 计算并绘出，这对本论文中仿真数据的对比提供了依据。 2 1 2 完备码和非完备码 当一个码字的差错个数小于该码最小距离丸h 的一半时，二进制对称信道的最 佳译码器可以正确地译码。也就是说任何一个差错数高达 f = i - ( - 1 ) 2 j( 2 5 ) 的码字都是可被纠正的。由于二进制对称信道是无记忆的，所以比特差错独立地 发生，在刀比特码块中出现m 个差错的概率就是 电子科技大学硕士学位论文 取加p w 计” 因此，码字差错概率上边界的表达式为 匕p ( m ，力) m = t + l ( 2 - 6 ) ( 2 7 ) 假定围绕每一个可能发送的码字放置一个半径为t 的球。每个围绕码字的球内 包含与该码字汉明距离小于或等于t 的所有码字的集合，这样，在半径为t 的球内 的码字数就是 + ( ： + ( 兰 + + ( ：) = 言( ：) ( 2 _ 8 ) 因为有m = 2 个可能发送的码字，也就是有2 个不相重叠的半径为t 的球，所 以包含在2 个球内的错误图案总数不会超过2 “个可能的接收码字。于是，一个纠t 差错的码必然满足不等式 即 ( 2 9 ) ( 2 - 1 0 ) 完备码具有下述特性：围绕m = 2 个可能发送码字、且汉明距离为t 的所有球 都是不相交的，每一个接收码字都落在这些球的某一个中。因此，每个接收码字 离开可能发送码字的距离至多为t ，这时式( 2 1 0 ) 取等号。对于这种码，所有重量 小于或等于t 的差错图案都能用最佳( 最小距离) 译码器纠正。另一方面，任何重量 等于t 或大于t + 1 的差错图案都不能被纠正，所以式( 2 7 ) 给出的差错概率表达式可 以取等号。当错误个数大于t 时，错误码字就会跳到另一个码字，所以当采用完备 码译码时，只会发生译码错误，而不会发生译码失败。 例如如；。= 7 、t ：3 的( 2 3 ，1 2 ) 戈莱码【4 】【1 9 l 【捌是一种完备码，可以通过计算公式 ( 2 1 0 ) 来证明其码字的完备特性。由于满足以下关系 6 第二章纠错码简介 ( 言3 ) + ( 3 ) + ( 主3 ) + ( ；3 = 2 。4 8 = 2 = 2 4 一 c 2 - ， 可见，( 2 3 ，1 2 ) 戈莱码确是一种完备码，即无论接收到发生任何差错的码字都能译成 一个确定的码字，而不会发生译码失败。同理，具有参数刀= 2 ”一l 、= 3 和f = 1 的汉明码也可通过公式( 2 - i o ) j , j e l 日y j 其是完备码。 2 1 3 最大似然译码 在利用( 刀，七) 分组码编码过程中，编码器输入砧表示一个k 比特的信息分组， 编码器输出 ，表示一个疗符号的码字，译码器输入，表示经过量化后一个珂符号的 接收序列，译码器输出五表示一个的k 比特的译码输出。 在接收端，译码器根据接收到的序列，通过一个已知的译码准则，产生一个对 原始信息口的估值五。纠错码的最根本译码准则就是在一个码字集中，为每个的接 收到的序列，找出一个最有可能是原来发送码字参的方法，即尽可能使痧= l ，。所以， 当参= l ，时，五= , 译码正确；而当多 ，时出现译码错误，从而假设定接收到的序 列为，则译码器的条件误码率为 p ( e ir ) = p o ； ，lr)(2-12) 于是，译码器的误码率由公式( 2 1 3 ) 确定 只d = p ( e ir ) p ( r )( 2 - 1 3 ) 其中p ( ，) 为接收序列，的概率，它与所用的纠错码的译码方法无关，因为，是在译 码前受具体信道特性影响产生。纠错码的目的就是使公式( 2 1 3 ) 达到最小，所以最 大似然译码准则要求必须对所有的，使得p ( 五l ，) = p o ； ，l ，) 为最小。又由于要 使p ( 参，i ，) 最小，就等价于使只痧= yi ，) 最大，所以只要在码字集中选择出帚使 得公式( 2 1 4 ) 最大 驯咖等掣 就可以得到最小的误码率。从这一点上也可以看出最大似然译码中“似然 的含 义。 若信源消息是等概发送，那就对等概率的, 8 进行编码，从而得到等概率的输出 7 电子科技大学硕士学位论文 码字l ，即对任何 ，来说p ( v ) 都相同不变，则要使公式( 2 1 4 ) 最大就等价于使 p ( ，l ，) 最大。如果信道选择离散无记忆信道( 实际中也都是这样假设) ，由于信道无 记忆特性，所以每个接收符号，：只与发送符号m 有关，从而可以得到公式( 2 - 1 5 ) p ( r l v ) = 兀p ( l m ) ( 2 1 5 ) j 所以在离散无记忆信道下的最大似然译码准则要求应使公式( 2 1 5 ) 最小，此式也是 最大似然译码推到出的最简式子，但是为了计算方便将公式( 2 1 5 ) 对数化，可以得 到公式( 2 1 6 ) 。 l o g p ( ，i ，) = l o g p ( r fm ) ( 2 - 1 6 ) f 在离散无记忆信道下，采用最大似然译码的译码器选择能使公式( 2 1 6 ) 中的和 为最大的参作为码字。若码字不是等概率的，由于在决定哪个码字能使e ( v l ，) 最 大的时候必须以码字概率e ( v ) 对条件概率p ( r l ，) 进行加权，所以最大似然译码不 一定是最优的。 当信道为二进制对称信道时，是一个二进制序列，由于信道噪声的影响，它 可能在某些位置上不同于发送码字y 。令当, v j 时，p ( ，；l ) = p ；而当，；= u 时， 讹i h ) = 1 - p ，并且d ( ，) 代表，和y 之间的距离。所以对于n 比特长的分组码来 说，公式( 2 1 6 ) 可变形为 l o g p ( rlv ) = d ( r , v ) l o g l + 1 0 9 ( 1 一p )( 2 1 7 ) 1 一p 由于p 0 5 时，l o g ( p ( 1 一p ) ) o ，且对所有 ，n l o g ( 1 一p ) 是一个常数，故b s c 下的最大似然译码就是选择能使得，和，之间的距离d ( r ，p ) 为最小的痧作为码字 y ，即选择与接收序列不同的位置数最小的 ，作为码字。从另一个角度理解就是选 择发生错误比特最少的码字作为输出，而硬判决下的错误比特数和汉明距离对应， 因此b s c 下的最大似然译码有时也叫做最小距离译码。 最简单的最小距离译码就是通过在2 ，| 个差错图案中选择2 ”个错误数最少的 差错图案，将每个差错图案和所有少个码字在二元域上进行加法运算，得到一个 2 量x 2 ”的表，这个表称为标准阵列表。它的每一行的每个二进制序列表示特定差 错图案下所对应的错误码字。将每个接收到的错误码字和表中的错误码字样本对 照，然后样本所在行对应的差错图案就是信道所发生的差错( 虽然实际中可能不 8 第二章纠错码简介 是) ，样本所在列对应的码字就是发送的码字，即译码完毕。 对基于标准阵列表的译码需要做大量的查找运算，故可通过伴随式来化简其 中的操作。具体理论推到和算法如下： 假定分组码的校验矩阵为日，c 是发送码字，p 表示差错图案，则经过信道 后的码字l r 可表示为 y = c + e ( 2 1 8 ) y 的乘积为 l ，日7 = ( c + e ) h = c h + p 日- - e h 7 = s ( 2 - 1 9 ) 其中，( n k ) 维矢量s 就是与差错图案p 所对应的伴随式，所以当信道没有差错发 生时候，s 为零矢量。然而不是所有的丁个错误图案都有不同的伴随式，因为伴 随式的个数为2 ”七，故其中必有同的差错图案对应相同伴随式的情况产生，这也说 明了纠错译码不可能纠正所有的差错。 由公式( 2 1 8 ) 和( 2 1 9 ) 可知，标准阵列表的每一行差错图案对应一个不同的伴 随式，通过计算接收码字的伴随式就可以找到与该伴随式所对应的差错图案吾，也 就能恢复出发送码字 c = y o 占 ( 2 - 2 0 ) 在本文中，对伴随式的计算不是通过矩阵相乘而是通过循环码的多项式运算得到 的，但其最小距离译码思想都是通过查找表来实现。 2 2 循环码 在现今常用并实用的线性分组码体系中，循环码占很大一类，很多码字具有 循环码的结构，如部分的有限几何l d p c 码【1 9 1 。它们都满足一个最基本的特性， 即循环移位： 如果c = ( 巳小巳埘，c i ，c o ) 是一个循环码的码字，n ( c 小q 掣，c i ，c o ) 也是该 循环码的一个码字，且也可以通过对c 中的某个码字循环移位得到。也就是说，c 所有的码字它们的循环移位都还属于该循环码的码字集。由于这种循环的特性， 循环码拥有相当丰富的结构特性，这种特性被大量用在编码和译码操作中。针对 循环码结构上的特点，大量有效的编码算法和硬判决译码算法已经被发现，并且 在实际通信系统中，使得有大量码字的极长分组码的编译码得以实现。 9 电子科技大学硕士学位论文 在实际编码过程中，使用的是码字的系统形式，这样带来的好处就是可以直 接明了地区分出信息位和校验位，同时也方便了编码过程。给定一个( 甩，k ) 循环码 的生成多项式g ( x ) ，假设待编码的消息为m = ( u 0 ，甜i 一，一。) ，则相应的消息多项 式为 口r ) = + ”i x + + “t l x 一1 ( 2 2 1 ) 用x ”乘以u ( x ) ，得到次数不大于以一l 的多项式为 x ”一) = - 1 1 0 x 1 一+ x 4 廿+ + u k l x ”一 ( 2 - 2 2 ) 用生成多项式烈x ) 除以x ”。 ) 得到 x ”u ( x ) = 口( x ) g ( x ) + 6 ( x )( 2 2 3 ) 其中，a ( x ) 和6 ( x ) 分别为商式和余式。由于g ( x ) 的次数为n - k ，贝u b ( x ) 的次数 必不大于力一k 一1 。从而有 6 ) = b o + 6 l x + + 吃一i l x ”以一( 2 - 2 4 ) 重新整理( 2 3 2 ) 式，得到如下次数不大于r l 一1 的多项式 6 ( x ) + x ”u ( x ) = a ( x ) g ( x )( 2 2 5 ) 该多项式为生成多项式g ( x ) 的倍式，由此它也是由多项式g ( x ) 生成的循环码的 码多项式。写出6 ( x ) + x ”) 有 以柳以”阶笼岛冀：l + 冀x n - k - i x x + u t ，。 仁2 6 ， + 材o”矗+ i “一“1 + 一1 r “一1 、。 相应的码字为( b o ，岛，玩- k - iu o ，一。) 。 码字是由k 位不变的信息位和其后的刀一k 个校验位组成。这n k 个校验位正 是生成多项式g ( x ) 除消息多项式x ”) 所得余式的系数。上述方法将得到一个 系统形式的( 以，七) 循环码。在系统形式的循环码中，采用以下约定：前n k 个符号， 即l ，工，x h 1 的系数，取为校验位；而后k 个符号，即x n - kx ”“1 ，x ”1 的系 数则为信息位。最后总结系统码的编码由以下三个步骤组成： 第1 步：用x 乘以消息叫) 得到x ”u ( x ) 。 1 0 第二章纠错码简介 第2 步：用生成多项 g ( x ) 除x ”u ( x ) ，获得余式6 ( x ) ( 校验位) 。 第3 步：编码输出6 ( 朋和x ”h ，即码多项式为b c x ) + x ”u ( x ) 。 其编码电路图如图2 2 所示： 图2 - 2 ( 刀，后) 循环码的系统编码电路 在系统设计中，若不能找到一个具有合适的自然长度的或合适的信息位数目 的码字，有效的解决方案就是缩短一个码，以使它满足需要。给定一个( 万，j | ) 循环 码字c ，考虑c 中信息位的高z 位均为零的码字集合。这样的码字共有2 h 个，它 们构成了c 的线性子码。若从这些码字中删除这个，个零信息位，将得到2 n 个长 度为n 一，的向量。这2 n 个缩短的向量构成0 一，k 一，) 线性码。这种码被称为缩短 循环码，却不是循环码。缩短循环码的纠错能力与原码相同【2 。 缩短循环码的编译码可以采用与普通循环码相同的电路来实现。这是因为删 除前，个零信息位并不影响对奇偶校验位和校正子的计算，但是在整个接收向量全 部进入到校正子寄存器后，对缩短循环码进行译码时，校正子寄存器就必须移位， 次以产生合适的校正子来对第一个接收位山。进行译码。对于很大的，值来说，校 正子寄存器额外的，次移位会带来很大的译码延时；通过调整伴随式寄存器的连接 方式或改进差错检测电路，都可以消除这种译码延时【卯。 2 3 论文用到的编码 2 3 1 戈莱码 戈莱码是由m j e 戈莱( g o l a y ) 在1 9 4 9 年发现的【1 9 】，它的参数为刀= 2 3 ，k = 1 2 ， “- - - 7 。由它的最小距离可知，戈莱码能够纠正2 3 个符号的分组中的3 个错误。 图2 3 【7 4 ) 汉明码獭1 2 ) 媒码的性能仿真 蝴删黼 俐俐 巧啦h 嘴却 一一一 一一 掺潲黼 蹦删 十撇椭 嬲槲 一一一 一一 l 藿姗一 种酾 住 一一一 一一 懈一胛 删脓 一一一一 一一 咖 斓融舭龇娜 一一一一一删一 第二章纠错码简介 生成多项式，所以r s 码的编码电路是通过生成多项式来得到。 令口为g f ( q ) 中的本原元。符号取自g f ( q ) 、纠f 个错误的r s 码，其生成多 项式g ( 加以o t ，口2 ，口2 为其全部的根。由于是g f ( q ) 中的元素，因此其最小多 项式西( x ) 即为x - a 。于是得到 烈柳三篇x幅-an2)-(x哪-an2rt)go ” ( 2 - 2 9 ) = + g l x + 9 2 x 2 + + 9 2 卜1 y 2 卜1 + x 甜 、。 其中毋g f ( q ) ，0 f 2 t 。由于口，口2 口2 是x g 一一l 的根，因此x g 一一l 能够被 g ( x ) 整除。所以，g ( x ) 将生成恰好具有2 f 个奇偶校验符号、长度为刀= g 一1 的g 进制循环码。由b c h 界可知，该码的最小距离至少为2 f + 1 ；同时，生成多项式譬( x ) 是一个码多项式且具有2 t + l 项。因此，勿+ l 中的系数均不能为0 ，否则得到的码 字将具有小于2 f + 1 的重量，这与最小距离的b c h 界矛盾。所以，g ( ) 对应着重 量恰为2 t + l 的码字。这意味着由公式( 2 2 9 ) 的多项式g ( 朋生成的r s 码，其最小 距离恰为2 f + l ，并且该码能够纠正小于等于t 个符号错误。综上所述，符号取自 g f ( q ) 、纠t 个错误的r s 码具有如下参数： 分组长度：拧= g l 奇偶校验符号数：万一k = 2 t 维数：k = q 一1 2 f 最小距离：d 。m = 2 t + l r s 码是特殊的b c h 码，故对r s 码译码，一般采用对b c h 码译码的方法和 步骤。假设所传码字为 c ( x ) = v o + v l z + + v j 1 矿一1 ( 2 3 0 ) 由于信道干扰而产生误码，使得收到的码字r ( x ) 为 ，( z ) = r o + r j x + + ，：，一i z “一1( 2 - 3 1 ) 误差多项式e ( x ) 为c ( 力和，( 工) 之差，使用式( 2 3 0 ) 和式( 2 3 1 ) 得 p ( 工) = ，o ) 一c ( 石) = e o + q z + + 巳一i 石”一。 ( 2 3 2 ) 定义2 f 个部分伴随式墨( 1 js2 f ) 为墨= ，( ) ，由于口1 ，口2 ，口丑均为每个被 传码字c ( x ) 的根( 因为每个码字都是生成多项式g ( 功的倍数) ，因而c ( a ) = 0 和 电子科技大学硕士学位论文 墨- - c ( a 。) + p 似) = g ( ) 。显然，2 t 个部分伴随式鼍只与误差多项式p ( 功有关，与 接收到的特定码字，( 工) 无关【“1 。 假设有七个错误( k f ) ，其位置在一，妒9 * gp 一处，其中 o 工 五 n - 1 。把一处的误差大小记做气，那么p ( x ) 为 e ( x ) - e 。l x j 。+ e j , x j t + + e i m 3 3 ) 定义差错位置数屈= 口 ( f = l ，2 ，七) 。那么由2 t 个部分伴随式的集合，将得 到下列方程式： s i = e j l p 、+ e j l 9 1 + + e j t p k 岛2 气届2 + 气压2 + + 气羼2 ( 2 3 4 ) s n = e j i p ：t + e j l p ：t + 七e j ：p 0 求解上述方程式的算法就是r e e d s o l o m o n 解码算法。误差位置e ，可以由一求 出，而误差的大小可以由屈直接得到。 r e e d s o l o m o n 解码通常分为五步进行： 第1 步是计算部分2 f 个伴随式墨。 第2 步是用b e r l e k a m p m a s s e y 2 4 i 算法计算错误位置多项式盯( 工) 【3 】【2 研。这个多 项式是收到码字，( x ) 的误差位置的函数，但是它不能直接指出所收码字中的哪一 个符号产生错误。 第3 步用c h i e n 搜索算法