（微电子学与固体电子学专业论文）qam解调芯片中reedsolomon解码模块的设计.pdf

东南大学0 2 级硕士学位论文 摘要 r e e d s 0 1 0 m o n 编码( 简称r s 编码) 是存在于当今数字电子系统中非常重要的一类编码，利用 它的算法特性可以实现适应多种需要的纠错技术。由于其优秀的纠正随机和突发连续误码的性能， r s 码在数据通信、卫星通信及存储器等领域获得了极其j 泛的应用，同时，它也是欧洲电信标准协 会( e t s i ) 关于有线信道部分的传播标准，即d v b c 标准的重要组成部分。 r s 编码器和解码器的实现比较复杂，同时，其算法及运算均基于有限域理论。因此本文从介绍 必需的迦罗华域基础理论开始，论述了r s 编码及解码原理和相关算法，然后针对本文实现目标一 一h d t v 解调芯片中前向纠错部分的r s 解码模块，着重比较几种解码方法，由此确定了解码器设 计方案。在此基础上，本文设计了符合d v b c 标准的r s ( 2 0 4 ，1 8 8 ) 解码器的各模块结构组成，该解 码器采用基于改进的欧几里德( m e ) 算法的时域解码结构，其中在执行核心功能的算法模块中， 通过将其清晰划分为阶数计算和多项式计算两个功能模块，并利用多项式首项系数交叉相乘抵消的 思路，有效地避免了传统核心算法模块中的多项式除法运算，从而减小了模块规模和硬件实现的复 杂度。本文采用v h d l 语言对解码器各部分进行了详细设计，通过了模块仿真和验证，并给出了关 键电路的仿真结果、模块相关参数分析，结果表明，本文所设计的r s 解码器可以对符合d v b c 标 准的比特流进行解码，适合于皿t v 机顶盒等应用场合。 关键词： 纠错码，数字电视，d v b c ，硬件实现，迦罗华域 东南大学0 2 级硕士学位论文 a b s t r a c t r e e d s o l o m o ne r r o rc o l l r e c t i o ni sav e r vi m p o r t a n tt e c h n o l o g yw h i c he x i s t si nt o d a y s d i g i t a lc o m m u n i c a t i o ns y s t e m s b e c a u s eo fi t se x c e l l e n te 1 1 o rc o r r e c t i n g i b i l i t y ， r e e d s o l o m o nc o d e sh a se x t e n s i v ea p p l i c a t i o n si ns t o r a g ed e v i c e s ，c o m m u n i c a t i o na n d b r o a d c a s t i n g ，i np a r t i c u l a rf b r m i n gp a r to ft h es p e c i f i c a t i o nf b rt h ee t s id i g i t a lc a b l e t e l e v i s i o ns t a n d a r d k n o w na sd v b c h a r d w a r ei m p l e m e n t a t i o n so fc o d e r sa j l dd e c o d e r sf o rr e e d s o l o m o ne o rc o r r e c t i o na r e c o m d l i c a t e da n dr e q u i r es o m ek n o w l e d 2 eo ft h et h e o r yo fg a l o i sf i e l d so nw h i c ht h e ya r e b a s e d t h i sp a p e rd e s c r i b e st h eu n d e r l y i n gm a t h e m a t i c sa n dt h ea l g o r i t h m su s e df b rc o d i n g a n dd e c o d i n 2 ，w i t hp a r t i c u l a re m p h a s i so nt h e i rr e a l i z a t i o ni nl o g i cc i r c u i t s b a s e do nt h e a n a l v s i sa n dc o m p a r i s o no fs e v e r a lr e p r e s e n t a t i v ed e c o d i n ga l g o r i t h m s ，w ed e r i v e dav l s i s 0 1 u t i o nf b ro u rd e s i g ng o a lw h i c hp l a y sa ni m p o r t a n tr o l ei nt h ef e cb l o c ko fan e wh d t v d e m o d u l a t ec h i p o nt h eo t h e rh a n d ，w ep r e s e n t e da ut h em o d u l e so ft h i sr s ( 2 0 4 ，18 8 ) d e c o d e rw h i c hi s f u l l yc o m p a t i b l ew i t ht h ed v b cs t a n d a r d ，w i t hp a r t i c u l a re m p h a s i so nt h ek e y e q u a t i o n s o l v e r ( k e s ) b l o c k t h r o u g ht h ew h o l ep r o c e s so fv h d lc o d i n g ，r t l s i m u l a t i o na n d s v n t h e s i s ，t h ep r o p o s e dr sd e c o d e rh a sb e e ni m p l e m e n t e dw i t ht h ec h a r t e r e do 3 5 mc m o s s t a n d a r dc e ut e c h n o l 0 2 v i i lt h ee n do ft h ep a p e r ，r e l a t i v es i m u l a t i o na n dt e s tr e s u l t st o g e t h e r w i t ht h ep a r a m e t e ro ft h ed e c o d e ra r ep r o v i d e d k e yw o r d s ：e r r o r c o r r e c t i n gc o d e s ，d i g i t a l t e l e v i s i o n ，d v b c ，h a r d w a r ei m p l e m e n t a t i o n ， g a l o i sf l e l da r i t h m e t i c 东南大学0 2 级硕士学位论文 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 矽隘躲安、了 日 研究生签名：互)! 日 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生虢墨1 3翩虢陛垭日 期：沁：篁：0 东南大学0 2 级硕士学位论文 1 1 信道编解码概述 第一章绪论 在数字通信系统中，经过信源编码和系统复接后生成的码流，通常需要通过某种传输媒介才能 到达用户接收机。传输媒介可以是广播电视系统( 如地面电视广播系统、卫星电视广+ 播系统或有线 电视广播系统) ，也可以是电信网络系统，或存储媒介( 如磁盘、光盘等) ，这些传输媒介统称为传 输信道。通常情况下，编码码流是不能或不适合直接通过传输信道进行传输的，必须经过某种处理， 使之变成适合在规定信道中传输的形式。在通信原理上，这种处理称为信道编码( c h a n n e lc o d i n g ) ( 与信源编码相对应) ，实现信道编码的系统称为传输系统。 1 2 信道编解码在数字电视芯片领域的应用 在工程应用中，信道处理过程一般被分为两环节：负责传输误码的检测和校正的环节称为信道 编解码，负责信号变换和频带搬移的环节称为调制解调。一个实际的数字传输系统至少要包括上述 两个环节中的一个环节，一般数字电视领域的系统都是由上述两个环节构成的。针对信道特点不同， 世界上两大主流数字电视传输体制美国的g a 系统方案和欧洲的d v b 系列标准分别定义了 相似的信道编解码方案。 数字通信虽然较模拟通信相比有较强的抗干扰的能力，但当干扰较大时仍然可能发生信息失真， 因此必须采取措施进一步提高传输系统的可靠性，纠错编码就是为这一目的提出的。纠错编码是数 字通信特有的，是模拟通信所不具备的。纠错编码利用数字信号可以进行数值计算这一特点，将若 干个数字传输信号作为一组，按照某种运算法则进行数值运算，然后将传输信号和运算结果( 也是 数字信号) 一起传送给接收机。由于一组传输信号和它们的运算结果间保持着一定的关系，如果传 输过程中发生了错误，使得传输信号或运算结果中产生了错误数码，这种关系就会遭到破坏。接收 机按规定的运算法则对接收的一组传输信号及其运算结果进行检查，如符合运算法则，则认为传输 信号中没有误码，然后将运算结果抛弃，将传输信号送给下一级处理系统，如数据解扰器；如不符 合运算法则，就意味着传输中发生了误码，如果误码的数量不超出纠错编码的纠错范围，纠错解码 器就会按照某种算法将误码纠正过来，然后将正确的传输信号送给下一级处理系统，如果误码的数 量超出了纠错编码的纠错范围，纠错解码器无法纠正这些误码，将发出一个出错信号给下一级处理 系统，通知下一级处理系统传输信号中有误码。 纠错码有很多种类，如v i t e r b i 编码、c r c 码、b c h 码等等 2 - 【4 】。但是无论哪种纠错编码的纠 错能力都是有限的，当信道中的干扰较严重，在传输信号中造成的误码超出纠错能力时，纠错编码 将无法纠正错误。针对这种情况，d v b 通信系统中采用了两级纠错的方法以进一步提高纠错能力。 如果把整个通信系统，包括传输信道看成一个传输链路的话，那末处于外层的纠错编，解码一般被称 为外层纠错编码，而处于内层的纠错编解码一般被称为内层纠错编码。内层纠错编码首先对传输误 码进行纠正，对纠正不了的误码，外层纠错编码将进一步进行纠正。两层纠错编码大大提高了纠正 误码的能力，如果内层纠错编码将传输误码纠正到1 0 e 一3 的水平，即平均每一千个传输数码中存在 一个误码的话，经过外层纠错编码后，误码率一般可降至1 0 e 一5 的水平；而如果内层纠错编码将传 输误码纠正到1 0 e 4 的水平的话，经过外层纠错编码后，误码率一般可降至1 0 8 的水平。在目前的 d v b 传输系统中，外层纠错编码采用的是著名的r e e d s o l o m o n 码( r s 码) 5 】，内层纠错编码采用 卷积码。 东南大学0 2 级硕士学位论文 内层的卷积纠错编码虽然具有很强的纠错能力，但一旦发生无法纠正的误码时，这种误码常常 呈现连续发生的形式，也就是说，经卷积解码器纠错后输出的码流中的误码常显连续的形式。此外， 信道中还存在着诸如火花放电等强烈的冲激噪声，也会在卷积解码后的码流中造成连续的误码。这 些连续误码落在一组外层r s 码中，就可能超出r s 码的纠错能力而造成信息失真。为避免这种情况， 在两层纠错编码之问加入了数据交织环节。数据交织改变了信号的传输顺序，将连续发生的误码分 散到多组r s 码中，落在每组r s 码中的误码数量就会大大减少，不会超出r s 码的纠错能力，r s 码能够将其纠正过来。实践证明，数据交织提高了系统的纠错能力，特别是对冲激噪声的纠错能力。 r e e d s 0 1 0 m o n 码是由i s r e e d 和g s 0 1 0 m o n 于1 9 5 8 年1 2 月在m i t 林肯实验室的一篇报告中首 先提出的。在早期阶段，由于没有好的译码算法，对于纠正6 个以上的错误值都是困难的，直到1 9 6 7 年，e b e r l e k a m p 提出了一种有效的译码方法，首次使得纠正多个错误的r s 码有效译码成为可能， 1 9 6 8 年，m a s s e y 提出了一种等效于b e r l e k a m p 算法的b c h 码译码方法，该算法现在通常称为 b e r l e k a m p m a s s e y ( b m ) 算法。到了1 9 7 5 年，e u c l i d e a n 译码算法也被提出，这两种有效的译码算 法使得r s 码被广泛应用在现代通信系统中，在典型应用如深空通讯、移动通讯和高清电视中都可 以发现它的存在 6 】。 作为b c h 码的一种，r s 码包含有用来对信道接收信号进行纠错的奇偶校验位，用来纠正信号 传输过程中发生的误码，尽可能降低误码率。r s 码的一个显著优势在于它具有很强的纠错能力，可 以在容限内对整段字节进行纠错。本文介绍了d v b 数字电视系统中，用于q a m 芯片内的r s 纠错 模块和完整的r s 编解码器的设计及实现。文章从必需掌握的有限域代数学背景开始，在第三章详 细论述了r s 码的编解码算法，在第四章介绍了在数字电视有线信道传输中，r s 解码模块的规范及 最终解码方案选择，第五章给出了符合d v b c 标准的r s ( 2 0 4 ，18 8 ) 解码模块的设计，并且提交了相 关电路的仿真测试结果及模块相关参数与分析评价。 2 东南大学0 2 级硕二i 二学位论文 第二章r e e d s oio m o n 编码背景理论 r s 码所基于的数学原理比较复杂，但是欲设计其硬件细节，有必要对其所涉及的迦罗华域代数 理论及算术规则有清楚的了解。因此本文首先用本章提炼出必需的有关r s 码和迦罗华域算术的关 键背景知识，以利于后续章节关于编解码算法的进一步论述。 2 1 r e e d s o l o m o n 码的分类 在信道编码领域存在很多编码方式，按照信息码元和校验码元之间的约束方式不同，可分为分 组码和卷积码。r e e d s o l o m o n 码属于分组码的一种，这种编码方法的特点是，信息被分为分离的数 据段，同时在每一个数据段根据编码算法加入冗余的保护信息从而形成自包含的码字来用于传输。 如图1 所示，由于保护码元作为独立的段添加至数据段，编码过程并不改变信息码元本身，r s 码也 称为系统码。 d ew o r d ( 打s y m b o i s ) p a t y ( 疗一是= 2 fs w 弧b o i s ) 图2 1r e e d s o l o m o n 码字定义 而且，由于特性诸如叠加两个码字可以形成另外的码字，对任一码字内字节进行循环移位也可 以形成另外的码字，r e e d s o l o m o n 码也可以分别被称为线性码和循环码。总之，它是 b o s e c h a u d h u r i h o c q u e n 曲e m ( b c h ) 码 7 8 】家族中的一员，它的单元由一段具有多比特的自节组成， 即使传输中可能单个字节的每一位都发生了错误，对于码的纠错容量来说，这些位的错误只算作一 个字节，这样的结构使得它尤其适于处理突发性误码。 对于r s 码来说，选择不同的参数可以提供不同的纠错能力，同时也直接影响到硬件实现的复 杂度。它本身可以被描述为( n ，k ) 的形式，n 代表段的长度，即所含字节数，k 则是被保护的信息 字节的数目，同时有： n 2 一1( 2 1 ) 其中m 为每字节包含的比特数，当( 1 ) 中等式不成立时，所形成的码字称为r s 码的缩短形 式。据上所述，显然冗余位为n j i = 字节，假设每段中至多能纠正f 个字节，则有： f = ( ，z 一| i ：) 2当n j i ：为偶数时 f = ( 玎一七一1 ) 2 当n 1 ：为奇数时 li o s l ， b 牡 n b弘” s u 东南大学0 2 级硕士学位论文 需要指出的一点是，在论述纠错码的各种文献中，关于各种符号的定义虽有相似性，但却并不 完全一致，这对于阅读过程无疑会造成相当程度的困扰。因此，了解编解码各种相关参数是如何制 定的显得尤其重要。 2 2 迦罗华域 进一步阐述r s 码的编码和译码，需要一定的被称为迦罗华域( g a l o i sf i e l d ) 的有限域理论知 识【9 】 1 0 】，它因法国数学家g a l o i s 而得名。 2 2 1 迦罗华域元素 对于任何质数p ，存在一个有限域，表示为g f p ) ，其中包含有p 个元素。可以将g f p ) 延伸为 一个含有p 个元素的域，这称为g f p ) 的扩展域，表示为g f ( p ”) ，m 是一个非零正整数。应当注 意的是，g f p ) 是g f ( p “) 的子集。扩展域g f ( 2 “) 中的码元被用于构造r s 码。 二进制域g f ( 2 ) 是扩展域g f ( 2 “) 的一个子域，类似于实数域是复数域的一个子域一样。除了数 字o 和1 ，在扩展域中还有特殊的本征元素，用一个新的符号口表示。g f ( 2 ”) 中任何非0 元素都可 以由口的幂次表示。元素的无限集f ，就是根据元素集 o ，1 ，口) 而形成的，后一个元素通过前一项 乘以口而得 f = o ，口o ，口1 ，口2 ，人，口j ，人) ( 2 2 ) 为了从f 中得到有限元素的集合g f ( 2 ) ，必须对，域施加一个条件，使它只能含有2 “个元素 且对乘法封闭。域元素集对乘法封闭的条件可由下面的不可约多项式表示： 优( 2 ”一1 ) ：1 ：口o ( 2 3 ) 根据这个多项式限制条件，任何幂次等于或超过2 “一1 的域元素都可降价为如下所示的幂次小 于2 ”一1 的元素： 倪( 2 ”+ ”) ：口( 2 ”一1 ) 口肿1 ：口肘1( 2 4 ) 因此，式( 2 3 ) 可用于从无限序列f 中形成有限序列f + ，如下所示： f + = 0 ，1 ，口，口2 ，人，口2 卅_ 2 ，优2 卅_ 1 ，口f ，a ) = o ，口o ，口1 ，口2 ，人口2 m _ 2 ，口o ，口1 ，口2 ，人) 所以，由上式可以看出有限域g f ( 2 ”) 的元素由下式给出： g f ( 2 “) = o ，口o ，口1 ，口2 ，a 口2 l 2 ) 4 ( 2 5 ) ( 2 6 ) 东南大学0 2 级硕士学位论文 例如，g f ( 2 5 6 ) 含有2 5 6 个元素，g f ( 1 6 ) 则含有1 6 个元素，值得指出的是，迦罗华域中每个元 素除了可以用口的指数形式来表示以外，还有一种重要的采用多项式形式的表示方式： 口。一l x “一1 + 以。一2 工”一2 + a + 口l j + 以o ( 2 7 ) 其中，由以。一1 直到以。的m 个系数均取值o 或1 ，这样，对应于二进制m 位数所具有的2 种取 值可能，便可以利用某种特定的规则( 域发生多项式，见2 2 3 节) ，将一个迦罗华域元素形容成二 进制数以。一1 日。一2 人以l 以。的形式，从而形成一一对应的映射。 举例来说，对于含有1 6 个元素的迦罗华域( g f ( 1 6 ) ，m = 4 ) ，元素的多项式表示形式为： 口3 x 3 + 以2 x 2 + 口l 工l + 以o 工o 则口3 以2 以1 日。对应于二进制数0 0 0 0 至1 1 1 1 。同样，方便起见，可以将二进制数的十进制等效形式0 至1 5 对应于分别的迦罗华元素。 有限域内的算术运算同样包括加、减、乘、除，但并不同于通常人们习惯的对整数采取的四则 运算，有限域中的运算一个明显的特点在于对任意域元素进行任何四则混合运算所得仍为该域中元 素。 2 2 2 迦罗华域中加法和减法运算 当对任意两个迦罗华域元素进行加法运算时，相当于对相应得多项式进行相加： ( 口。一l 工”一1 + a + 以l 上1 + 以o x o ) + ( 易，l l z “一1 + a + 易l x l + 工o ) = c m l 工”一+ 人+ c l x l + c o 工。 其中，c i = 日f + 轨， o i ，竹一1 ( 2 8 ) 然而，系数值只能取0 或1 ，所以有： c i 。0 尝旷易i 曼i ( 2 9 ) c f = 1当日f 易i 时j 亦即，任意两个迦罗华域元素相加，即是对相应系数进行以2 为模的加法运算，对它们的二进 制形式来说，得数为对两个二进制数逐位分别进行异或的结果。 例如，在g f ( 1 6 ) 中，将两个域元素工3 + x 2 + 1 和工3 + 1 相加可得工2 + 工+ l 。用二进制形式表 示有： 1 1 0 1 ( 1 3 ) 坦地( 1 0 ) 0 11 1 ( 7 ) 即1 1 0 1 + 1 0 1 0 = 0 1 11 也可用十进制表示成： 同样容易推出，由于定义的逐位异或运算的特性，任何域元素进行与自身的加法运算所得必然 为0 。 5 东南大学0 2 级硕士学位论文 有意思的是，任意两个迦罗华域元素的减法运算完全等同于加法运算。这是因为对两个多项式 做减法所得的系数虽然形式为： c i = 以i 一易i o i ，咒一1 然而c i 的取值仍然受( 2 9 ) 式约束。对于上例，易得： 1 0 1 3 = 7 同样可得，任何域元素自身相减所得为o 。认识到对任一域元素进行加法和减法效果相同这点非常 有用，正因为这一点，在对迦罗华域元素进行算术运算时，减法完全可以用加法来代替。 2 2 3 域发生多项式 有限域的一系列定义中的一个重要的部分是关于域发生多项式的，也有的资料称其为本原多项 式，表示为p ( x ) 。定义域发生多项式为m 次不可约减多项式。对于一个指定大小的迦罗华域，通 常可有不同的域发生多项式供选择，如果编码方和解码方采用不同的域发生多项式则会产生不正确 的结果。对于数字电视系统而言，域发生多项式通常在相关标准里就被固定指定，设计时必须遵守。 例如，对于g f ( 1 6 ) 而言，多项式 p ( j ) = j 4 + 工+ l ( 2 】o ) 是不可约的，因此可以作为域发生多项式。但同样也可以选择其他的4 次多项式作为域发生多项式， 例如： p ( x ) = 工4 + 工3 + 1 2 2 4 构建迦罗华域 在迦罗华域中，所有的非零元素都可以通过函数构建出来。定义本征元素口为域发生多项式 p ( x ) 的根，即： p ( 口) = o 此即所需要的函数关系。举例来说，对于g f ( 1 6 ) ，采用式( 2 1 0 ) 作为域发生多项式，可得方程： 口4 + 口+ 1 = o 亦即 凹4 = 口+ 1( 迦罗华域中加减法等效) 这样，从口。开始，逐级乘以口，并根据上式用口+ 1 代替各级中存在的口4 项，便可完成g f ( 1 6 ) 的构建，如表1 所示。其中，从左往右四栏分别是域元素的指数形式、多项式形式、二进制和十进 制等价形式。 另外，如果从表中口1 4 项开始继续逐级乘以及，可以发现，口1 5 = 口o ，口1 6 = 口1 ，这 6 东南大学0 2 级硕士学位论文 也正反映了g f ( 2 ”) 有且仅有2 “个域元素的原因。 表2 1g f ( 1 6 ) 采用p ( 工) = x 4 + x + 1 时的域元素 i n d e x p o l y n o m i a l b j r i l a 薹vd e c i l i l a l f o f l nf 1 0 r mf - o r mf o r l u 0o0 0 0 0o 0 c o 1o o o l1 0 c l 0 c0 0 1o2 仪2 0 c 20 1 0 04 矿f 1 0 0 08 0 c 4仅i 0 0ll3 一醒+ 伐o l1o6 矿o c 3 + 仪2 1l o o1 2 了 仪7o c + 仪+ 王 1 0 1lll 扩 q 。+ 1 o 1 0 15 遣联+ 仅 1 0lol o 0 c l o 1 伐+ o c _ + l o l1l 7 g c l l一十o c 2 o c1 王1o1 4 2一 。+ o c 一a + l 1lll l5 饯1 30 + 0 c f 2 l 1l o ll3 仪1 4砰+ 1 1 0 0 l9 2 2 5 迦罗华域乘法和除法运算 由于直接将两个m 一1 次多项式相乘会产生2 m 一2 次多项式，而高于m 一1 次的多项式均不是 有效的g f ( 2 “) 的域元素代表形式，所以，在迦罗华域定义中，乘法被定义为两个域元素的积对域 发生多项式p ( x ) 作模余预算所得的结果。也就是说，用p ( 工) 来除乘积，再取其余数，由于p ( z ) 为 m 次，则余数必然小于或等于m 一1 次，从而确保自身是一个有效的迦罗华域元素。 举例来说，在g f ( 1 6 ) 中对1 0 和1 3 进行乘法操作，用多项式形式来表示，就是： ( 工3 + x ) ( x 3 + 工2 + 1 ) = x 6 + 工5 + x 3 + 工4 + 工3 + 工 = x 6 + 工5 + 工4 + 工 ( 2 11 ) 要完成迦罗华域乘法，必须用式( 2 1 1 ) 除以域发生多项式工4 + x + 1 。 多项式除法类似于传统的长除法。其过程包括，先对除数乘以一值以使其阶数与被除数相等， 7 东南大学0 2 级硕士学位论文 再将二者相减( 对迦罗华域元素来说相当于相加) ，然后对余数重复进行上述操作，直至被除数的最 低位参与运算。 为方便起见，可将多项式的每项按次数高低从左至右排开，这样多项式除法运算就可以根据系 数值( o 或1 ) 进行，如下例所示： x 6x 5工4戈3工2x l工o 被除数： 111o010 除数工2 ： 除数x ： 除数1 ： 10011 11 11 1 10011 1100o 1o011 lu ll 据此可知，商为戈2 + 工+ l ，而余数，亦即1 0 乘以1 3 的最终结果，为工3 + x + 1 ，同样可以写 为十进制数1 1 。也就是： l o 13 = 1 1 附录所示为采用式( 2 1 0 ) 作为域发生多项式的g f ( 1 6 ) 域内乘法操作的查找表。 式( 2 11 ) 的多项式形式乘法操作同样可利用前述多项式分栏来完成。首先，将多项式工3 + 工2 + 1 的每项分别乘以工3 + 工，再将所得相加，最后，无需采用多项式除法，可以直接利用表1 对任何指 数溢出项采取代替形式再次分别相加即可得出乘法运算的结果。如下所示： 工6 工5 x 4工3x 2 工lx o z 3 ：l01o 工2 ： 1 ： 1o1o !q!q 111oo1o 工4 ：x + 1 工5 = 工2 + 工 0ol1 ol10 工6 ：工3 + 工211 oo 1o 1l 还有一种迦罗华域乘法技术，同时对除法运算也很方便，是基于指数运算的。其规则为：如果 将两个待乘数用指数形式来表示，那么，积的指数可以通过将待乘数指数相加再对2 “一l 作取余运 算获得。仍用前例，对1 0 和1 3 做乘法运算，通过查找表1 可以发现： 1 0 = 口9 和13 = 口1 3 8 东南大学0 2 级硕士学位论文 因此，1 0 13 = 口9 口1 3 = 口( 9 + j 3 ) 0 d 1 5 = 口2 2 ”0 1 5 = 口7 。 再次查找表1 ，可以发现： 口7 = 1 1 积的结果和多项式方法所得结果一样。 指数法的一个微小缺陷在于，域元素0 不可被表示为指数形式，因此，必须认识到o 值的存在 并强制o 值参与的乘法结果。 指数法同样可以被用于除法运算： 11 1 0 = 口7 口9 = 口( 7 9 ) ”0 1 5 = 口( 一2 ) “0 1 5 = 口1 3 = 1 3 尽管如此，两个迦罗华域元素的除法运算通常通过乘以除数的倒数来完成。任一域元素的倒数 被定义为当乘以其自身时使得所获乘积为1 ( 口o ) 的那个域元素。同样，任一域元素的倒数有且仅 有一个。 例如，1 0 = 口9 ，因此它的倒数为口_ 9 ) “d 1 5 = 口6 = 1 2 ，因此有： 1 1 1 0 = 1 1 12 这样，就可以利用上述三种乘法计算方法的任一种来计算出除法运算结果。 2 3r s 码的构建 r e e d s o l o m o n 码字的信息位和校验位都是特定迦罗华域的域元素，显而易见，对于基于m 位的 r s 码，对应的迦罗华域必须有2 ”个元素。 2 3 1 码元发生多项式 一个( 九，足) r s 码必须通过首先建立码元发生多项式才才能构建，g ( 工) 含有玎一足= 2 f 个因式， 因式的根为连续的迦罗华域元素，这是确保码距最大的必要条件。因此，码元发生多项式具有形式： g ( x ) = ( 工+ 优6 ) ( 工+ 口6 + ) k ( x + 口2 h ) ( 2 1 2 ) 必须重视的是，在各类不同文献中，上式表示略有变化，容易被误解为错误表达。例如，因式 有时被写成( x 一口) ，其意在着重强调当x = 口时g ( 工) = o ，熟悉迦罗华域运算便很容易看出一口 和口是等效的。另外，一些项目选用域元素从口。开始( 易= 0 ) ，但很多却选取从及本征元素开始 ( 易= 1 ) ，虽然这些选取方法都是有效的，但由于码元发生多项式的略微不同，会导致产生的r s 码完全不同，从而需要不同的编码器和解码器操作。如果易值的选择靠近2 “一l ，则一些根可能会 超出口2 一1 ，此种情况下可将它们的指数值对2 “一1 作取余运算来代替之。若要追求硬件实现时 复杂度稍稍减小一点，可以取易= o ，但这并不是一个重要的问题，关键取决于各种工程项目的标 9 东南大学0 2 级硕：仁学位论文 准制定。 2 3 2 基于( 1 5 ，1 1 ) 的r s 码示例 关于r s 码构建的详细例子对于阐述r s 编码与解码过程非常有帮助，然而，d v b c 标准里规 定的r s ( 2 5 5 ，2 3 9 ) 的编码方式并不适于作为示例来论述r s 码的编解码机制。由于其信息位长度长达 几百个字符，因此相关的多项式会长达数百项! 但同样应该看到的是，对于编解码方法而言，不同 的r s 码之间并无差别。观察到这一点，我们可以采用一个相对简单的r s ( 1 5 ，1 1 ) 的版本作为示例贯 穿整个编码解码过程，采用的方法可以很容易移植到其他类型的r s 码上，包括d v b c 里的 r s ( 2 5 5 ，2 3 9 ) 规范。 对于r s ( 1 5 ，1 1 ) ，码元长度为1 5 字符，其中包含1 1 个信息字符和4 个冗余字符，因为f = 2 ， 则每段内最多可纠正2 字符的错误，另外由于： ，z = 2 ”一1 将，z 用1 5 代替，可得m 值为4 ，也就是说，每字符包含一个4 比特字，并且r s ( 1 5 ，1 1 ) 是基于 g f ( 1 6 ) 的。对示例我们采用式( 2 1 0 ) 作为域发生多项式，因此对其所作的的迦罗华域运算基于表1 的基础之上。 欲纠正至多两个错误，域发生多项式需要4 个连续的域元素作为多项式的根，因此可以选择： g ( 工) = ( 工+ 口o ) ( 工+ 口1 ) ( x + 口2 ) ( x + 优3 ) = ( x + 1 ) ( x + 2 ) ( 工+ 4 ) ( 工+ 8 ) 上式两个等效变换分别对域元素采用指数形式和十进制等效形式。显而易见，可以通过将因式 相乘并合并同类项，产生一个关于x 的指数降次排列的多项式。由于乘法运算用指数形式进行处理 来得更为简便，而加法运算用多项式形式更为快捷，因此整个计算过程均可依赖表l 不断进行形式 上的转换，也尤其适用于专门用计算机编程来实现，对于( 1 5 ，1 1 ) 这样的简单码型，可以直接运算如 下： g ( 工) = ( 工+ 1 ) ( 工+ 2 ) ( 上+ 4 ) ( 工+ 8 ) = ( 工2 + 3 x + 2 ) ( 工+ 4 ) ( 工+ 8 ) = ( 上3 + 7 x 2 + 1 4 x + 8 ) ( x + 8 ) ：工4 + 1 5 x 3 + 3 x 2 + x + 1 2( 2 1 3 ) 当然，对系数用指数形式也可以表达为：g ( x ) = 口。工4 + 口1 2 工3 + 口4 工2 + 口。工+ 口6 2 3 3 符合d v b c 标准的r s 码 在d v b c 标准中，r e e d s o l o m o n 码被指定为( 2 0 4 ，l8 8 ，仁8 ) 的形式，它是由r s ( 2 5 5 ，2 3 9 ，f _ 8 ) 经过截短而得到的，这就是说，1 8 8 字节的输入信息加上1 6 字节的校验信息，联合形成了一个含有 2 0 4 个符号的经过编码的打包信息。对于这样的码型，相关的迦罗华域含有2 5 6 个域元素( m = 8 ) ， 同时，域元素的多项式表示形式为： 1 0 东南大学0 2 级硕士学位论文 n 7 工7 + 以6 工6 + 口6 戈5 + 口4 戈4 + 口3 工3 + 以2 戈2 + 以l 工l + 口0 x o 对应的二进制数范围从0 0 0 0 0 0 0 0 到1 1 1 1 1 1 1 1 ，也就是十进制形式0 到2 5 5 。 d v b c 标准规定域发生多项式为： p ( x ) = 工8 + 工4 + 工3 + x 2 + 1 ( 2 1 4 ) 所构建的g f ( 2 5 6 ) 的部分元素列于表2 。与构建表1 采用的方法相同，g f ( 2 5 6 ) 的域元素值可以逐行 计算得出。在每一步，代表多向式形式域元素的二进制值向左移一位( 等同于乘以工) ，如果移位导 致左边的1 溢出，则需要加上0 0 0 1 11 0 1 ，也就是z 8 的二进制代替形式，这是因为： 工8 = 工4 + 工3 + 工2 + 1 很明显，g f ( 2 5 6 ) 可以依次这样构建下去，因所含元素过多，故不一一列出。 表2 2g f ( 2 5 6 ) 部分元素 i n d e x p o l y n o m i a lf - o r m ( 1 e c i l 强al f - o n i l7x 6，x 3 ) x lx ox 0ooo0o0ooo 扩0ooooooll “l oo00oo1o - 2 oo0ooloo4 oooo1ooo8 “4o0olooool6 “5 oolooooo3 2 “6 ol0ooooo6 4 r l0oooooo1 2 8 “8 0ool重lol2 9 0 c 9 oo圭llolo5 8 “2 5 4 1 oo 0 l1 1 0 1 4 2 此外，d v b c 标准还对码元发生多项式作了统一规定： g ( 工) = ( 工+ 斧) ( 工+ 力) ( x + 刀) k ( 工+ 爿5 ) 其中旯= 0 2 删，这意味着标准将迦罗华域的本征元素定为2 ，用符号允而不是通常的口代替之， 同时容易发现，此码元发生多项式对应于式( 2 1 2 ) 中易= o 的情形。 当将因式相乘并展开时，d v b c 中码元发生多项式为： 譬( 工) = 工1 6 + 5 9 x 1 5 + 1 3 x 1 4 + 1 0 4 工1 3 + 1 8 9 x 1 2 + 6 8 x + 2 0 9 工1 0 + 3 0 x 9 + 8 x 8 + 1 6 3 工7 + 6 5 工6 + 4 1 x 5 + 2 2 9 工4 + 9 8 x 3 + 5 0 x 2 + 3 6 x + 5 9 东南大学0 2 级硕士学位论文 第三章 r e e d s oio m o n 编码及解码 3 1r s 码的差错概率 r e e d s 0 1 0 m o n 码对于突发误码的纠正尤其有用，即它对有记忆的信道特别有效，而且，这种编 码可以有效地使用在具有较大输入码元集的信道上。r s 码具有一个有趣的特性：在一个长度为，z 的 r s 码中，可以加入多达2 个信息码元而不减小其最小码距。这种扩展的r s 码的长度为，2 + 2 ，具 有与原始码相同的校验码元数。r s 译码的码元错误概率r ，可用信道码元错误概率p 表示为： r = 击种”斗”。 t ， 其中，f 是码本可纠正的错误码元数，每一码元由m 比特组成。 对于指定的调制方式，比特错误概率的上限可由码元错误概率来表示。例如，对于m = 2 “的 m f s k 调制，b 与名的关系为 吃一2 ”1 r 2 一l ( 3 2 ) 图3 1 是b 随信道误码率p 变化的关系曲线，根据式( 3 1 ) 、式( 3 2 ) 画出了，z = 3 1 、具有不 同纠错能力f 的3 2 进制正交r e e d s o l o m o n 码。对于r s 码错误概率随分组长度n 呈指数下降的函数， 译码复杂度与分组长度的幂次成正比。r s 码有时用于链接系统( c o n c a t e n a t e da r r a n g e m e n t ) 中，在 这样的系统中，内部的卷积译码器通过对解调器输出执行软判决先进行一些差错控制，然后由卷积 译码器将硬判决数据送到外部r s 译码器，进一步降低错误概率。 1 2 东南大学0 2 级硕士学位论文 图3 13 2 进制正交码， n = 3 1 ，r 位纠错的r s 码，b 随p 变化的曲线 3 2r s 码性能分析 3 2 1 突发噪声情况下r s 码性能良好的原因 考虑一个( ，z ，足) = ( 2 5 5 ，2 4 7 ) 的r s 码，这里，每个码元由m = 8 比特组成( 这种码元通常称为 字节) 。由于，z 一良= 8 ，可知这种码可以纠正长度为2 5 5 的分组数据中的4 个错误码元。假设突发 噪声持续2 5 比特并扰乱了发送的一个分组中的数据，对于( 2 5 5 ，2 4 7 ) 码，r s 译码器将纠正任意4 个错误码元而不需要考虑码元所受到的破坏类型。换句话说，当译码器纠正一个字节时，它将不正 确的字节替换为正确的字节，不管这个错误是由于一个比特的错误还是8 个比特的错误引起的。所 以，一个码元发生错误时，任何比特都可能发生错误。这就赋予了r s 码相对于二进制码具有抵抗 突发噪声的优势，尽管二进制编码可以采用交织编码。在该例中，如果2 5 比特噪声干扰以随机方式 发生而不是连续突发出现，很明显将会有多于4 个的码元受到影响( 最多会有2 5 个码元受到干扰) 。 当然，这超过了( 2 5 5 ，2 4 7 ) 码的纠错能力。 1 3 东南大学0 2 级硕士学位论文 3 2 2 作为分组大小、冗余度和编码效率函数的r s 性能 对于一种能够成功抵制噪声影响的编码，噪声的持续时间必须占用相对较小比例的编码字长。 为了确保大部分时间都是如此，接收噪声必须在一个很长的周期上平均，以减少突发和意外干扰的 影响。所以可以认为纠错码随着分组大小的增加而更加有效( 纠错性能提高) ，使得不管多长的编码， r s 码都成为一种极具吸引力的选择。 随着r s 码冗余度的增加( 编码效率降低) ，它的实现变得更加复杂( 尤其对于高效率设备) ， 而且对于任何实时通信，带宽也必须有所扩展。但是，冗余度增大的益处正如增大码元大小的好处 一样，可以提高比特差错性能。 对于假想译码器的传输函数( 输出误比特率随着输入信道误码率变化的曲线) ，因为没有这样一 种系统或信道( 译码器只有一个输入输出) ，所以可以认为纠错性能随着冗余度增加而增加，是一个 单调函数，即使编码效率接近于零，系统性能也会持续提高，但是这不符合实时通信系统的要求。 编码效率在最小值和最大值( 0 到1 ) 之间波动时，可以观察到它的影响。这里，性能曲线刻画的是 不同信道类型的b p s k 调制和r s 码( 31 ，忌) 。对于一个实时通信系统，纠错性能的提高是以增加带 宽为代价的，带宽扩展与编码效率成反比。曲线清楚地描绘出最小毛o 情况下的最佳编码效率。 对于高斯信道，最佳编码效率大约为0 6 到0 7 ，莱斯衰落信道为o 5 ( 直接接收与反射接收信号功 率之比k = 7 d b 条件下) ，瑞利衰减信道为0 3 。为什么对于很大的编码效率( 很小冗余度) 和很小 编码效率( 大冗余度) 会产生毛o 的下降? 很容易解释高编码效率相对于最佳编码效率时 毛o 的下降。任何编码都存在编码增益，所以当编码效率接近于1 ( 没有编码) ，系统将会产生 很恶劣的差错性能。低编码效率下e 。的下降更为明显，是因为在同时采用调制和编码的实时 通信系统中，有两种机制都在起作用，一种是提高差错性能，而另一种则是降低差错性能。提高差 错性能的机制是编码，冗余度越大，纠错性能就越好。降低差错性能的机制是每信道码元能量的降 低( 相比于数据码元) ，它产生于增加的冗余度( 以及实时通信系统中更快的信号处理) 。码元能量 的降低导致译码器产生更多的