（通信与信息系统专业论文）rs分组turbo码译码算法研究与实现方案设计.pdf

东南大学硕士学位论文 摘要 t u r b o 编码是迄今为止发现的一种具有较高性能的信道编码技术，它由两个基本思想组成：一是 级联编码，二是采用软输入软输出( s o f t - i n s o f t - o u t 。s i s o ) 的迭代译码方案。这种思想被推广到乘 积码中并产生了分组t u r b o 码( b l o c kt u r b oc o d e ，b t c ) ，它基于两个或多个线性分组系统码的串 行级联。近年来，b t c 又扩展到了以r c e c t - s o l o m o n ( 1 峪) 码作为分量码的乘积码中。利用r s 码的 高码率特性和对抗突发错误的能力，r s b t c 获得了比较好的性能。 本文主要研究以r s 码为分量码的分组t u r b o 码的译码算法。首先研究了一般的b t c 编译码算 法，包括基于最小码字错误概率准则的最大似然译码，以及基于c h a s e 算法的渐近s i s o 迭代译码。 然后分析了r s - b t c 的编译码算法与般b t c 编译码的相同与不同之处，给出了性能仿真和比较结 果。 本文并针对s i s o 译码中的c h a s e 算法，提出了一种改进的试探序列生成方案，该方案是h a c k e t t e 针对二进制线性分组码提出的优化方案在r s - b t c 中的推广。我们再现了h a c k c t t e 方法在二进制线 性分组码上的应用效果，进而将其应用于r s - b t c ，给出了仿真结果。结果表明，该方法可在几乎 不增加运算复杂度的情况下获得较为明显的性能提升。 我们对r s b t c 译码器中与s i s o 迭代译码相关的一些关键运算结构进行了研究，给出了部分的 硬件结构设计方案。最后，针对r s - b t c 译码器的硬件实现问题，对译码算法进行了定点化仿真。 关键词：分组t u r b o 码，s i s o 译码，迭代译码，r e e d s o l o m o n 码，c h a s e 算法，h a c k e t t e 算法 东南大学硕士学位论文 a b s t r a c t t u r b oc o d i n gh a sb e c o m eo n eo ft h em o s tc r u c i a lt e c h n o l o g i e sf o re r r o rc o r r e c t i o n ，w h i c hi sc o m p o s e d o ft w ob a s i cc o n c e p t s ：c o n c a t e n a t e dc o d i n ga n ds o f t - i n s o f t - o u t ( s i s o ) i t e r a t i v ed e c o d i n g t h e s eo r i g i n a l c o n c e p t sh a v eb e e ne x t e n d e dt op r o d u c tc o d e s ，a n dr e s u l ti nt h ei n n o v a t i o no fb l o c kt u r b oc o d e s ( b t c ) ， w h i c hi sc o n s t r u c t e do ft w oo rm o r ec o n c a t e n a t e ds y s t e m a t i cl i n e a rb l o c kc o d e s b t ch a sb e e nl a t e l y e x t e n d e dt op r o d u c tc o d e sw i t hr e e d - s o l o m o n ( r s ) a sc o m p o n e n tc o d e s t a k i n ga d v a n t a g e so fi t sa b i l i t i e s o fc o r r e c t i n gb u r s te r r o r si nh i g h - d a t a - r a t et r a n s m i t t i n g ，r s - b t cp r o v i d e sas a t i s f y i n gp e r f o r m a n c e i nt h i st h e s i s ，w em a i n l yw o r ko nt h ed e c o d i n ga l g o r i t h m so fr e e d s o l o m o nb l o c kt u r b oc o d e s f i r s t l y w es t u d yo nt h ec o d i n ga n dd e c o d i n ga l g o r i t h mo fg e n e r a lb t c s ，i n c l u d i n gm ld e c o d i n go nt h ep r i n c i p l e o fm i n i m i z i n gc o d ee r r o rp r o b a b i l i t i e s ，a n ds i s oi t e r a t i v ed e c o d i n gu s i n gc h a s ea l g o r i t h m t h e na c o m p a r i s o nb e t w e e nr s - b t ca n db i n a r yb t ch a sb e e ng i v e n w eh a v ei m p l e m e n t e dt h e s ef l g o r i t h m sa n d a n a l y z e dt h es i m u l a t i o nr e s u l t s w ea l s og i v ea na d v a n c e dm e t h o df o rg e n e r a t i n gt e s tp a a e r n si nc h a s ea l g o r i t h m ，w h i c hi sa na p p l i c a t i o n o fh a c k e a e sa l g o r i t h mo r i g i n a l l yf o rb i n a r yb t c st ot h ed e c o d i n go fr s - b t c t h ea l g o r i t h mh a sb e e n i m p l e m e n t e da n ds i m u l a t e df o rb o t hb i n a r yb t c sa n dr s - b t c s s i m u l a t i o nr e s u l t ss h o wt h a tt h i sm e t h o d c a np r o v i d eam e a n i n g f u li m p r o v e m e n to fp e r f o r m a n c ew i t hs l i g h ti n c r e a s eo f c o r n p l e x i t y h a r d w a r ed e s i g no fs o m ek e yp a r t so fr s - b t cd e c o d e ri sd i s c u s s e dl a t e ri nt h et h e s i s f i n a l l y , f i x e d - p o i n td e c o d i n ga l g o r i t h mi ss i m u l a t e d k e y w o r d s ：b l o c kt u r b oc o d e s ，s i s od e c o d i n g ，i t e r a t i v ed e c o d i n g ，r e e d s o l o m o nc o d e s ，c h a s ea l g o r i t h m ， h a c k e t t ea l g o r i t h m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：盟 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：塑导师签名日期：2 i 一纠一f 午 第一章 1 1 纠错编码的发展 第一章绪论 通信系统的主要问题，是提高通信的有效性和可靠性，即在尽量节省资源( 带宽、功率等) 的 前提下。降低通信过程中发生差错的概率。实现该目标的重要手段之一是采用信道纠错编码技术。 1 9 4 8 年，香农在他具有里程碑意义的论文“通信的数学理论”中证明【i 】，只要信息传输速率低于信 道容量，通过对信息进行适当编码，可以在不牺牲信息传输速率的情况下实现任意低差错概率的信 息传输。自该著作发表以来，人们在寻找高效的编码方案上做了大量的努力。 目前为止所发现的纠错编码大致分为两类【2 】：一是基于代数理论的线性分组码，如汉明码、循 环码、b c h 码、g o l a y 码等等，译码主要采用大数逻辑译码和捕错译码。这类算法的复杂度随着码 长的增加呈指数级增长，对长码来说译码的实现十分困难。二是卷积码，卷积码在编码过程中引入 了寄存器，增加了码元之间的相关性，在相同复杂度的条件下可以获得比线性分组码更高的编码增 益，但是这种相关性同时也增加了分析和设计的复杂性。随着人们对卷积码研究的深入，在卷积码 的译码算法方面出现了序列译码和v i t e r b i 译码算法。基于寻找最大似然路径的v i t e r b i 算法的出现， 使得卷积码逐渐成为研究和应用的热点。后来又出现了t c m 网格编码调制技术，进一步确定了卷 积码在纠错编码应用中的地位。以上这些编码方法相对未编码系统能提供一定的编码增益，但是和 理论上的香农限相差甚远。 上面所述的两种码各有优缺点。此外，随着码长的增加，译码器的复杂度和计算量也相应地增 加以致难以实现，因此人们希望使用较短的码来获得长码的优秀性能，于是乘积码和级联码的概念 被相继提出。2 0 世纪9 0 年代，法国的c b e 仃0 u 1 3 】【4 】等人，在卷积码和级联码的基础上，提出了t u r b o 码，这种编码能够在码长较长时逼近香农的理论极限，同时其译码复杂度也是可以接受的。t u r b o 码 在子编码器中采用了反馈型的系统卷积码，且引入交织器减少了子编码器间信息的相关性，模仿了 随机编码的形式，同时在译码中采用了软输入软输出的递推迭代译码形式。正是这些特点为达到 s h a n n o n 信道容量开辟了一条新的途径。t u r b o 码被视为1 9 8 2 年t c m 技术问世以来，在编码的 理论和应用中所取得的最伟大的技术成就，具有里程碑的意义。 东南大学硕士学位论文 1 2r e e d s o lo m o n ( r s ) 码概述 霍昆格姆( h o c q u e n g h e m ) t s l 、博斯( b o s e ) 和查德胡里( c h a u d h u r i ) 【6 1 在1 9 5 9 年至1 9 6 0 年 间分别独立地发现t - - 进制b c h 码。b c h 码是对汉明码的重要推广，具有强有力的纠正随机错误 能力。戈伦斯坦( g o r e n s t e i n ) 和齐而勒( z i e r l e r ) 7 1 在1 9 6 1 年将二进制b c h 码推广到具有矿个符 号的码( 其中p 是素数) 。在非二进制b c h 码中，最重要的子类是里德一索罗门( r e e d s o l o m o n ) 码。 独立于h o c q u e n g h e m 、b o s e 和c h a u d h u r i 的工作，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 so v e rc e r t a i nf i n i t ef i e l d s ”【8 1 中谨慎地提i t 5 了构造一类新型纠错编码的方法， 之后这种码便被称为r e e d s o l o m o n ( r s ) 码。r s 码具有严密的代数结构以及极大最小距离可分 ( m a x i m u md i s t a n c es e p a r a b l e ，m d s ) 性质，在纠正随机符号错误和随机突发错误方面非常有效， 因此在随后的四十年里，r s 码在高密度数据存储、数字广播、无线通信以及深空通信等多个应用领 域大放异彩。 r s 码的译码方法研究经历了数个不同阶段。1 9 6 7 年b e d e k a m p p l 构造了一种有效的译码算法， 使得高效的r s 码硬判决译码成为可能；1 9 6 9 年m a s s e y l l0 1 证明了b e d e k a m p 算法等价于一种基于 快速的线性反馈移位寄存器的算法：1 9 7 5 年s u g i y a r n a ，k a s a h a r a ，h i r a s a w a 和n 锄e k a w a 川证明 e u c l i d 算法能有效地对b c h 码和r s 码译码：1 9 9 9 年g u r u s w a m i 和s u d a n ( g s ) 1 2 】提出了一种能够 超越r s 码硬译码半径的代数列表译码，r s 码的软译码隐现曙光。 2 0 0 4 年k o e t t e r 和v a r d y ( k v ) t 1 3 1 在g u m s w a m i s u d a n ( g s ) 算法的基础上提出了一种多项式复 杂度的代数软判决译码( a s d ) 算法，该算法与硬判决算法( h d ) 有着明显的增益，宣告了r s 码 软判决译码时期的到来。从此，g a u s s 算法【l4 1 ，c h e m o 算法d s ，w a t e r f i l l i n g 1 i k e 算法【1 6 1 ，a b p 算 法1 1 7 1 ，分解译码1 1 3 1 1 1 9 1 以及各种级联型算法1 2 0 1 接踵而至。虽然r s 软判决译码算法取得了比较好的性 能，但复杂度也相对较高，对其优化实现的研究也是当今信道编码领域的热点。 1 3bio c kt u r b oc o d e ( b t c ) 概述 由于在实际应用中，短码的性能有限，只有长码才能得到优越的性能，但长码译码的复杂度很 大，于是人们设想是否能够在短码的基础上构造长码。1 9 5 4 年。e l i a s 提出了乘积码( p r o d u c t c o d e ) 2 。 由于当时软判决和迭代译码的技术还没有得到充分发展，乘积码采用的是硬判决译码方法，其性能 没有明显的优势，未能引起人们的重视。1 9 6 6 年，f o m e y 在此基础上提出了级联码的概念【2 2 】，内码 和外码之间用交织器相连，希望通过对外码的译码纠正内码未能纠正的错误。内码一般采用最大似 然译码的卷积码，外码采用多进制的r s 码。通过将多个外码与多个内码相连，也可以构造多级级 2 第一章 联。多级级联可以通过多阶段译码获得较好的误码性能并减小译码复杂度。在多阶段译码中，每个 阶段译出一个分量码。个阶段的译码信息被传递给下一阶段，用于对下一个分量码进行译码。由 于分量码比较简单短小，可以对其进行软判决译码以获得较好性能。合理设计的多阶段译码可以在 显著复杂度的条件下。获得次优或近似最优的误码性能。 2 0 世纪9 0 年代，b e r r o u 等学者提出了t u r b o 码。t u r b o 码采用递归卷积码并行级联，中间采用 随机交织器，可以看作一种类随机码，同时又具有足够的结构信息，使得它可以使用比较高效的迭 代译码方法，在可接受的复杂度下能够达到渐近最大似然译码的效果。t u r b o 码由两个或更多的简 单分量码组成，对每个分量码采用简单的软输入软输出( s i s o ，s o f t i n s o f t - o u t ) 译码器，其中一个 译码器的软输出结果直接作为另一个译码器的软输入，反之亦然，直到得到最终的译码估计。 总的说来，t u r b o 编码技术由两个基本思想组成：一是能够产生具有类随机特性码的码设计方 案，二是采用软输出值和迭代译码的译码器设计方案。1 9 9 4 年，p y n d i a h 等人将s i s o 迭代译码思想 推广到了对乘积码的译码中【2 3 1 ，由此创造了分组t u r b o 码( b l o c kt u r b oc o d e ，b 1 ) 。该码的分量 码译码采用针对线性分组码的s i s o 译码方案，利用到了码字中每个码元分量的可信度信息。这些 算法包括以码字错误概率最低为准则和以码元错误概率最低为准则两大类常用的有广义最小距离 g m d ( g e n e r a l i z e dm i n i m u md i s t a n c e ) 2 4 】、c h 镐e 【2 s 】、最大后验概率m a p 译码、逐位译码、重量删 除译码、o s d ( o r d e r e ds t a t i s t i c sd e c o d i n g ) 2 6 1 等等。其中c h a s e 算法相对而言比较简单，易于硬件 实现。它首先寻找码字中可信度最小的码元组，通过在这些位置上加入一系列扰动来扩大搜寻码字 的半径，从而在可以承受的复杂度下找到尽可能多的最接近接收序列的码字再根据该码字集合， 重新估算每个码元位的可信度作为软输出。用s i s o 译码算法得到的软信息输出在行分量码译码器 和列分量码译码器之间反复迭代，最终可以实现渐近最优译码的效果，这一点与采用递归卷积码的 t u r b o 码相似，所以将这种编译码方案称作分组t u r b o 码。b t c 译码算法相对其它软判决译码算法 来说比较简单，利于硬件实现。当码率较高时，其性能和同等码长的t u r b o 码使用m a x l o g m a p 、 s o v a 等次优算法进行译码时相近。b t c 译码的误码率在较大的范围内可以随着信噪比的增加任意 减小，无错误平台效应或错误平台出现得较迟，这一点与t u r b o 码不同。i e e e 8 0 2 1 6 标准中也将b t c 作为可选方案以提高系统性能。 p y n d i a h 提出的b t c 是基于以b c h 为分量码的乘积码。他也同时提出了采用r s 码作为分量码 的分组t u r b o 码，并指出在高数据传输速率应用中，r s 分组t u r b o 码的译码器在存储器使用和复杂 度上较之相近码率的b c h 分组t u r b o 码有显著的优势。e r w a np i r i o u 2 7 1 等人率先硬件实现了r s 分 组t u r b o 码的译码器。b t c 译码器的硬件实现中，对分量码多采用基于c h a s e 算法的s i s o 译码， 因为它在实现上比较简单。然而，c h a s e 是一种列表译码方法，需要进行多个试探序列的译码，运 3 东南大学硕士学位论文 算量仍然较高。如何进一步降低c h a s e 译码中的运算量是b t c 译码算法中有待研究的课题。 1 4 本文的主要内容 本文重点讨论r s b t c 的译码算法，给出性能仿真结果，并分析了译码器主要模块的硬件结构 实现。 全文分五章，本章为绪论，简单概括信道编码技术的历史以及r s 码和b t c 码的发展。 第二章首先讲述近世代数初步，它是b c h 码和r s 码等基于代数方法构造的编码的理论基础。 然后介绍了线性分组码的概念和基本知识，以及b c h 码和r s 码的构造、编码及译码方法，并对其 进行了再现和性能仿真。 第三章至第五章是本文重点。第三章介绍分组t u r b o 码的编码方案、译码流程，详细地论述了 基于c h a s e 2 算法的近似s i s o 译码和b t c 的迭代译码过程。 第四章首先阐述r s b t c 的编码方式和s i s o 迭代译码方案，继而介绍对译码算法的一些优化 措施，主要是借鉴哈盖特( h a c k e t t e ) 2 8 1 针对g o l a y 码提出的偶重量试探序列生成方案，在性能只 有微小降低的基础上可减少一半的试探序列译码运算，或在相同试探序列数量的情况下改善误码率 性能。 第五章分析了r s b t c 译码器的硬件实现结构框架，并给出了一些关键模块的详细实现结构。 最后给出了r s b t c 译码算法的定点化性能仿真结果。 4 第二章 2 1 群、环、域 2 1 1 群 第二章线性分组码基础、b c h 码及r s 码 令g 为一组元素的集合。g 上一个二元运算定义为这样一种规则四】：对g 中的每对元素a 和 b ，由该规则可在g 中唯一确定第三个元素c = a * b 。若在g 上定义了这样一种二元运算，则称g 在下是封闭的。 如果g 上的二元运算对g 上任意a , b , c 满足 a p 砂= 向例七 则称二元运算满足结合律。 定义2 1 1 称代数系统 为群，如果 1 ) 满足结合律： 2 ) 中有单位元e ，即对g 中任意元素a ，有口= p 屹= 口； 3 ) g ，吟中每一元素都有逆元。即：对g 中任意元素a ，在g 中存在一个元素a ，满足 a a = a a = e 口 群中元素的个数，称为群的阶。若+ 也满足交换律，则称群g 是交换群或阿贝尔( a b e l ) 群。 我们不加证明地给出群的相关定理。 定理2 1 1 群中单位元是唯一的，群中每个元素的逆元也是唯一的。 2 1 2 环 定义2 1 2 称定义了两种运算+ 和。的代数系统 为环，如果 1 ) 是阿贝尔群； 2 ) 满足封闭性： 3 ) 运算对+ 运算满足分配律，即对任意元素口，b ，c r ，有 5 东南大学硕士学位论文 2 1 3 域 a ( b - i - c ) = a b + a c ，( b + c ) a = b a + c a 定义2 1 3 称代数系统 为域，如果 1 ) 是阿贝尔群。关于加法运算+ 的单位元称为f 的零元，记为o ： 2 ) f 中的非零元素在乘法运算下构成阿贝尔群。关于乘法运算的单位元称为f 的么元或乘法 单位元，记为l ： 3 ) 乘法对加法满足分配律，即对任意三个元素口，b ，c r ，有 a ( b + c ) = a b + a c ，( 6 - i - c ) a = b a + c a 域中元素的个数称为域的阶。元素个数有限的域称为有限域，用g 哟) 或日表示g 阶有限域。 有限域也称为g a l o i s 域。我们不加证明地给出域的相关性质。 性质2 1 1 域中任意元素口满足a 0 = 0 a = 0 性质2 1 2 域中任意两非零元素口和b 满足a b 0 。 性质2 1 3 若a b = 0 且a 0 ，则b = 0 。 性质2 1 4 域中任意两非零元素a 和b 满足一( 口6 ) = ( 一a ) b = a ( 一6 ) 。 性质2 1 5 若a 0 ，a b = a c ，则b = c 。 下面给出有限域中本原元素的定义。 定义2 1 4 称口是有限域g f ( g ) 的本原元素如果q - 1 是最小的正整数使得 口口一= 1 。 2 2g a10is 域扩域的构造 在纠错码理论中应用最广泛的域是二元域瞅2 ) 及它的扩域g f ( 2 ”) 。 首先定义系数在二元域中的一元多项式f ( x ) ： f ( x ) = f o + z x + 厶x 2 + + a x ” ( 2 2 1 ) 其中，= 0 或1 。多项式的次数是非零系数对应的最高幂次。 g 即) 上的多项式可以进行加减乘除运算。设9 0 ) 为另一个一元多项式 6 第二章 g ( z ) = g o + g l x + 9 2 x 2 + + g 朋z m 。 ，( x ) 与g ( x ) 的加( 减) 法等于两者相同次幂的系数相加( 减) ( 此处假定m n ) ， ( 2 2 2 ) 厂( 工) + g ( 工) = ( 厶+ g o ) + ( z + g l h + + ( 厶+ g 。批”+ + l x “， ( 2 2 3 ) 其中( z + 岛) 进行的是模2 加( 减) 运算- f ( x ) 与g o ) 的乘法等于多项式展开： 其中 厂( x ) 。g ( 工) = c 。+ c t x + c 2 工2 + + c n + m 工“+ 用。 f 圭乃 q ： 卢o 。l 窆l g , ， l j = ，一_ i = 0 ，1 ，2 ，m ，露m i = m + l , m + 2 ，以+ n ( 2 2 4 ) 可以证明g f ( 2 ) 的多项式满足交换律、结合律和分配律。事实上，这些多项式的集合构成了一个环， 通常称为多项式环。 我们假定g ( x ) 为非零次多项式，当f ( x ) 除以g ( x ) ，我们得到了唯一确定的商式g o ) 和余式 厂( 工) ： f ( x ) = q ( x ) g ( 工) + ，( j ) ，a o ，( 工) a o g ( 工) 该表达式通常被称为e u c l i d 除法。 ( 2 2 5 ) 定义2 2 1 设厂( 工) 是非零次多项式若厂( 工) 不能被次数低于自身且不为零的任何多项式除尽， 那么我们称它为既约多项式。 定理2 2 1 ：鲫( 2 ) 中次数为m 的不可约多项式能被x 2 - 一1 + 1 除尽。 定义2 2 2 p ( x ) 是不可约多项式，若满足r + 1 能被p ( 工) 整除的最小正整数n 为n = 2 ”一1 ， 则称p ( 曲为本原多项式。 接下来，定义一个新符号t t t ，以及种乘运算“”： 0 0 = 0 ， 0 - 1 = 0 1 1 = 1 0 口= 口0 = 0 ， 1 t t g = 口1 = o t ， 口2 - - - - e 1 口 7 东南大学硕士学位论文 根据以上定义可以推出： 口。= 口口口 ( t i m e s ) 0 口= 口，0 = 0 ， 1 口j = 口- i = 口j ， 口，口，= 口j 口j = 口+ 这样，我们就得到了一个定义于下列元素集合上的乘法运算： f = o ，1 ，口，口2 ，口，) 元素1 通常用口。表示。 接下来，假定口是本原多项式的根，即p ( 口) = o 。因为p ( 工) 能被x r - 1 除尽，所以 将口代入上式，得到 又因为p ( a ) = 0 故 两边同时加1 ，得 工2 一1 + 1 = g ( x ) p ( z ) 口2 。一+ 1 = g ( 口) p ( 口) 口2 。一1 + 1 = q c a ) 0 口r 一：1 因此，集合，变为有限集合，包含以下元素 f = o ，1 ，口，口2 ，口2 。一1 ) 不难得出，f 关于乘法运算封闭，满足交换律结合律，且l ，口，口2 ，口2 _ 。为不同的元素。因 此，非零元素构成了一个阶数为2 ”1 的交换环。 得： 我们再为集合f 定义加法运算+ ，并使得f 构成加法+ 上的交换群。用p ( x ) 除以工，o f 2 ”， x = 吼( z ) p ( z ) + q ( 工) ( 2 2 6 ) 其中，吼( x ) 为商式，a i o ) 为余式。余式n ，( z ) 的次数不大于m 一1 ，可以写成以下形式： a i ( x ) = 口f o + 口f 1 x + a ，2 工2 + + a t r n - z x 历一 8 ( 2 2 7 ) 第二章 又因为x 和p ( 工) 是互质的( 除常数外没有任何公因子) 。一不能被p ( 工) 除尽。因此，对于任意i 0 ， 口i ( x ) 0 。若0 f ，j 2 ”，且，匈。则能用反证法证明 a t ( x ) a j ( 工) 因此，对于不同的i = o ，1 ，2 ，2 ”- 2 ，我们得到次数不大于m 一1 的2 m 1 个不同非零多项式q ( x ) ， 再将口代入式2 2 7 ，并利用条件口。0 = 0 ，得到o f 7 的多项式表示： 口- a l ( 口) = 口f o + 口f 1 口+ q ，2 口2 + + q 。一l 口1 1 ( 2 2 8 ) 此外，f 中的0 元素用零多项式表示。最终，我们用2 ”个不同的多项式表示了，中2 ”个不同的 元素。 现在，可以定义，上的加法运算为： o + 0 = 0 。 0 + o f = 口。+ 0 = o f ， 其中0 i _ 2 1 1 ，a 。 + 口j j 是g f ( 2 ) 上的模2 加运算，0 七 埘。由式2 2 9 可得 口+ 口= 0( 2 2 1 0 ) + 口一定是次数低于2 ”1 的多项式，因此集合f 对于加法运算+ 封闭。因为模2 加满足交换律和 结合律，所以加法运算+ 也满足交换律和结合律。而且式2 2 1 0 说明集合，中所有元素的加法逆元 为它自身。加法和乘法在集合f 上同样满足结合律。因此： 定理2 2 2 是元素个数为2 “的有限域。 通过以上步骤，我们构造了g f ( 2 ) 的有限扩域g f ( 2 “) ，并给出了扩域元素的两种表达形式：幂 形式和多项式形式。幂形式用来进行乘法运算非常方便，而多项式形式用来表示加法运算比较方便。 因此，在实现有限域运算时，通常是利用幂形式进行乘法运算，利用多项式形式进行加法运算，在 必要时利用查表完成幂形式与多项式形式之间的相互转换。 最后。我们不加证明地给出有限域的一些基本性质详细推导请参阅相关文献。 定理2 2 3 设f ( x ) 是g 只2 ) 上的多项式，卢是g f ( 2 ) 扩域的元素。如果卢是f ( x ) 的根，那么 夕掣，f o 也是- 厂( x ) 的根。 9 2 衙 口口+口口 口p + 冉 辑托 + d h ， 朋矿地 口 + 叶抛 + 町 邸即 + + 心 口 口 + + 口 口 = = 口+口 东南大学硕士学位论文 定理2 2 4 洲2 ”) 上的2 ”1 个非零元素构成了x ，+ l 的所有的根。 定理2 2 5 域中元素的最小多项式妒( x ) 是既约多项式。 定理2 2 6 元素为洲2 ”) 中的元素，p 为满足r = 最小的非负整数，则 。一l 厂( 工) = 兀( 工叩一) 为呶2 ) 上的既约多项式，也是的最小多项式，且次数为e ，且p 朋。 定理2 2 7 元素为洲2 ”) 中的本原元，则2 ，2 ，也是本原元。 定理2 2 8 元素为6 以2 “) 中的疗阶元素，则2 ，2 ，的阶也为刀。 1 0 第二章 2 3 线性分组码的基本概念 线性分组码( l i n e a rb l o c kc o d e ) 是分组码中最重要的一类码，也是应用最为广泛的纠错编码它 将信源输出的信息序列，以k 个码元为一段，通过线性编码，由这k 个信息元求出( n - k ) 个校验元， 最终得到长度为n 的一组码元。分组码每个码字的校验元仅与本组信息元有关，而与其它组无关， 这就是“分组”的含义。 用数学语言，线性分组码定义如下： 定义2 3 1 n ，幻线性分组码是a f ( 口) 上n 维线性空间圪的一个七维子空间 一个分组码是线性的当且仅当任意两个码字之和c l + c 2 胁，明仍然是一个码字。【行，明的 线性分组码c 是n 维向量空间的一个七维的子空间，因此可以找到七个线性无关的码字g o 粤l ，舢l ， 使得c 中的任意码字都可由它们线性表示： v = i i o g o 十g i + + u t _ l 一l ， v ，【一，k 】 将这七个线性无关码字排列成下列k n 的矩阵： g = g o 。o g l , q g k 1 0 g o ，i 9 1 i g k 一1 1 若= ( “。，u lg ，u ) 是待编码的信息序列，那么相应的码字可通过将其与矩阵g 相乘得到： v = “g = ( 4 0 , l 一，蚝一1 ) g o g l ： 一j = ( ”o g o ，“1 9 i ，” 。1 9 一1 ) 因此，矩阵g 通常被称为线性码c 的生成矩阵。为了使用方便，线性码通常设计为系统码结构，即 码字可分为校验位部分和信息位部分，此时的g 矩阵为如下形式： lg o g ：ig - 1 g 二 扩 ： 切 岛& 趾 0 o ；l 0 l ；0 1 o ；o 0 ， q p 0 氏0 ：趾凡口：陬 = i t 东南大学硕士学位论文 生成矩阵g 含有k 个线性无关的行，因此在向量空间中必存在( 甩七) 个线性无关的行与g 的 任意行正交，这( n - k ) 行组成的矩阵日被称为校验矩阵。向量v 是c 中的码字当且仅当，日= 0 。 因此，线性码c 也可以由校验矩阵来表示。系统码的校验矩阵如下： 日= k 。 ( 2 3 2 ) 下面介绍一个编码理论中的重要概念：分组码的最小距离( m i n i m u md i s t a n c e ) 。假定 v = ( v o ，h ，匕一。) 和“= ( ”。，”剃) 为n 维向量，它们的汉明重量以，) 和w ( u ) 分别为各自非零元 的个数，它们之间的汉明距离d ( ，“) 定义为两者对应位上不同元素的个数。一个分组码的最小距离 d i - i i n 定义为任意两码字间的最小汉明距离： d m 皇m i n d ( v ，u ) l ，“c ，”) ( 2 3 3 ) 如果c 为线性码，根据线性码的定义，任意两码字之和仍是一个码字。因此，线性码的最小距离等 于最小码重量： d m i n = m i n w ( v + “) iv ，“c ，y “ = m i n w ( x ) l 工c ，z 0 ) ( 2 3 4 ) a 2 h 最后，我们不加证明地给出线性分组码的纠错能力的定理，详细证明请参阅相关文献： 定理2 3 1 当错误个数1 ，和删除个数f 满足以下关系时，纠错码可以纠正该误码： d 。 l l 2 v + e + 1 ( 2 3 5 ) 定理2 3 2 以，k ，厶f 】线性分组码的最大可能的最小距离等于( 刀七+ 1 ) ，即d 刀一k + l 。若码 的最小距离等于( n - k + 1 ) ，则称此码为极大最小距离可分( m d s ) 码。 最后，介绍一下线性分组码的扩展和截短。 对二进制【n ，q 线性分组码，可以给每个码字添加一位奇偶校验位而构成二进制的【九+ 1 ，七】线性 码，这个添加的校验位用来对整个码字作校验，使得最终整个码字中l ，的个数为偶数。称这种胁+ l ， 明线性分组码为m ，础线性分组码的扩展码。 把信息元的前，位固定地置为0 ，并按【以，h 系统码的编码方法进行编码，最后把得到的码字中 信息元部分的前，位去掉，得到长为( ，l - 1 ) 的码字，则称由此得到的( ，z 一，k 一，) 线性分组码为m ， 明线性分组码的截短码。 1 2 第二章 2 4 循环码 2 4 i 循环码的定义 循环码是线性分组码的一个重要子类。它通常有一定的代数结构，编码和译码都能使用简单的 移位寄存器实现，因此应用十分广泛。 定义2 4 1 如果加，明线性码c 中的任意码字循环移位后仍是c 中的码字，则该码是循环码。 循环码除了可以用矩阵的形式表示，还可以使用多项式来表示。定义码字，= ( ，v 1 ，以一。) 的 多项式形式为v o ) = v o + v , x + v 2 x 2 + 匕一l 工剃。 定理2 4 1 对于研，明循环码c ，只存在一个码字多项式的次数为n - k ， g ( x ) = l + g t 工+ + g - 七一i 工“- 七- 1 + 石1 以 所有的码字多项式都是荆的倍数而且鼬) 所有次数低于刀一1 的倍式都是码字多项式。 定理2 4 , 2c n ，七 循环码的生成多项式是r + 1 的因子。即：，+ l = g ( 工) h ( x ) ，其中h ( 曲 被称为校验多项式。 2 4 2 循环码的编码 由循环码的生成多项式可以得到其生成矩阵和校验矩阵。对以g ( x ) 为生成多项式的循环码， g ( x ) 、x g ( x ) 、1 9 ( x ) 这七个多项式必然是线性无关的，而且根据定理2 4 1 ，必然是该循环 码的码字，因此可以构成循环码的生成矩阵g ，如下所示： i g 。一g 。一 一l 9 1g o 00 l g ：l ? g ? tg - g - g o? ? i ( 2 4 1 ) l ： ： ： i l 00 g 。一tg 。一女1 g lg oj 校验矩阵h 司以表示如下： i 饥一。 | 7 l i00 日：l ?冬k t |：l冬? ? l ： ： ： ： l 00 以一。 7 1 1 其中i i l i 卢o ，1 ，曲为校验多项式 的系数。 ( 2 4 2 ) 由此可以得到循环码的编码方法。设信息多项式为m ( x ) ，其次数不超过“1 ，则进行编码时直 1 3 东南大学硕士学位论文 接将其与生成多项式g ( x ) 相乘即得到码字多项式。 然而，从生成矩阵g 可见，这样得到的码字不是系统形式的。对于系统码，要求码字多项式的 第( 刀1 ) 次到第( n - k ) 次的系数对应于信息位，而其余为校验位，即 c ( x ) = m ( x ) x ”+ r ( x ) - - - 0( r o o dg ( 石) ) 其中厂o ) = r o + r t x + r 2 x 2 + 一h 工”卜1 为校验多项式，相应的系数是校验元。由上式可得 ( 2 4 3 ) 一，( 工) = c ( 工) + m ( x ) x ”一三肌( 工) x “一( r o o dg ( 工) ) ( 2 4 4 ) 所以，从生成多项式g ( x ) 得到系统码的过程，由以下三个步骤组成： 1 ) 用x ”乘以信息多项式m ( _ x ) ： 2 ) 用生成多项式g ( 工) 除r _ m ( x ) ，得到余式，0 ) ，此即系统码的校验位多项式； 3 ) 晟终得到的码字多项式为：x n - k m ( x ) + r ( x ) 。 所有这三步可以由除法电路来实现，该除法电路是一个( 刀的级移位寄存器，其反馈连接基于生成多 项式g ( x ) = 1 + g l x + + 邑一 一l x “一一1 + 工“一，如图2 4 1 所示： 校验位 图2 4 1 基于生成多项式的循环码编码电路 码字 ) + 编码操作过程如下： 1 ) 初始时，开关与上方触点相连。门开启，k 个信息位m o ，m l ，聊b i 串行移位进入电路中， 同时送入通信信道发送。从前端将信息向量移位输入等价于将信息多项式m ( x ) 预先乘以x ”。一旦 所有的信息位全部进入电路，则寄存器中的( 九七) 位就构成了余式多项式，即校验位数据； 2 ) 门关闭以断开反馈连接； 3 ) 开关改为与下方触点相连。移位寄存器继续移位，将( ，l 啪位校验位发送到通信信道中，则这 些校验位就与先前发送的k 个信息位共同构成了一个完整的系统循环码码字。 1 4 第二章 根据生成多项式g ( 工) ，可以得到循环码的系统生成矩阵。设k 组信息元对应的信息多项式如下： m 。( 工) = ，一，朋：( 工) = 工卜2 ，m 。( 工) = 1 。与这些信息多项式相应的校验多项式分别为： 吒( x ) 富x k - t x 4 一( m o dg ( x ) ) 吒( 工) 兰x i - 2 x ”( m o dg ( j ) ) ( x ) = - - x ”( r o o dg ( 工) ) 一般地写成： ，：( 力暑z ”叫( r o o dg ( z ) ) ，i - - 1 ，2 ，k ( 2 4 5 ) 与之相应的码字多项式为： c ：( 工) = x ”叫一，：( x ) ，i = 1 ，2 ，k 这七个码字多项式的系数就构成了系统生成矩阵g 的行，i l p g = l0 ol ： o o 一亏( 工) 一五( x ) 一五( z ) =