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

摘要 摘要 数字电视在我国的广泛应用，对数字电视信号的传输质量有了更高的要求，信道传输质量显得 尤为重要，这也就对高效的信道编解码技术提出了更高的要求。r e e d s o l o m o n 码是现行d v b c 标 准中使用的信道编解码方式，其算法特性和独特的有限域内运算编码的方式使得它在处理连续突发 性数据错误上有着十分出色的表现，因而成为欧洲电信标准协会( e t s i ) 的数字有线传播标准，即 d v b c 标准的重要组成部分。 文章介绍了r s 码依据的迦罗华域基础理论，论述了r s 编码及解码原理和相关算法，然后针对 h d t v 解调芯片中前向纠错部分的r s 解码模块，从核心算法的选择出发着重比较四种解码方法， 并最终确定了时域内采用b e r l e k a m p 算法作为核心算法的解码器设计方案。在设计中采用逻辑简化、 分时复用的方法缩小了电路规模，优化了电路结构。 整个电路采用v e r i l o g - h d l 语言进行描述，各模块及整体电路经m o d e l s i m 软件仿真，用 s y n o p s y s 工具进行逻辑综合，逻辑仿真和f p g a 验证表明，r s 解码模块在6 8 7 5 m ( b y t e 秒) 的 符号率情况下，能实现对r s ( 2 0 4 ，1 8 8 ) 码的解码纠错，符合d v b c 标准，满足q a m 解调芯片 的要求，并经过了c h a r t e r e do 2 5 t m c m o s 工艺流片实现。 此外，文章最后还提出了对电路进行进一步研究的方向，留待继续研究。 关键词：纠错解码，d v b c ，硬件实现，迦罗华域 东南大学硕士学位论文 a b s t r a c t r e e d s o l o m o ne r r o rc o r r e c t i o ni sa v e r yi 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 f i t se x c e l l e n te r r o rc o r r e c t i n ga 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 o r m i n gp a r to f t h es p e c i f i c a t i o nf o 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 f e n c o d e r sa n dd e c o d e r sf o rr e e d s o l o m o ne r r o rc o r r e c t i o n r e q u i r es o m ek n o w l e d g eo f t 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 eb a s e d t h i sp a t ) e r d 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 o re n c o d i n ga n dd e c o d i n g ， w i t hp a r t i c u l a re m p h a s i so nt h ec h o o s i n go fa l g o r i t h m sf o rk e y e q u a t i o ns o l v e r ( k e s ) b l o c k a n dt 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 a t i e rt h ea n a l y s i sa n dc o m p a r i s o no fs e v e r a l r 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 ec h o o s eav l s is o l u t i o nf o ro u rd e s i g ng o a lw h i c h p l a y sa ni m p o r t a n tr o l ei nt h ef e c b l o c ko fan e wh d t vd e m o d u l a t e c h i p 耵】e n w ep r e s e n t e da l lt 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 sf u l l yc o m p a t i b l e 谢t ht h ed v b - cs t a n d a r d ，a n du s i n gt i m e d i v i s i o n - m u l t i p l e x ( t d m lw h i c hi st h em a i ni d e ao f s e v e r a lm e t h o d st oo p t i m i z et h ea r c h i t e c t u r ea n dm i n i s hc i r c l es c a l e a t i e ro p t i m i z a t i o nt h ec i r c u i tn o to n l y m e e t st h ep e r f o l i n a n c er e q u i r e m e n to ft h eh d t vr e c e i v e rc h i pb u ta l s oh a v es m a l l e rc i r c u i ts c a l e ， c o m p l e x i t ya n dl o w e rc o s t t h r o u g ht h ew h o l ep r o c e s so fv e r i l o g - h d lc o d i n g ，r t ls i m u l a t i o n a n ds y 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 d0 2 5 b m c m o ss t a n d a r de e l lt e c h n o l o g y t h er e s u l ts h o w st h a tt h ed e s i g nc a r lb eu s e df o rr s ( 2 0 4 18 8 ) a tt h es p e e do f6 8 7 5 m h z a tt 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 s t o g e t h e rw i t ht h ep a r a m e t e ro ft 1 1 ed e c o d e ra r ep r o v i d e d w o r k e de x a m p l e sa r ep r o v i d e dt o i i l u s t r a t et h ep r o c e s s e si n v o l v e d k e yw o r d s ：e r r o rc o r r e c t o r ，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 i e l d i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：孑生如 日期：皇竺堑：生笸 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：难导师签名：啦 d 赐：；蔓= i 印，6 第一章绪论 第一章绪论 1 1 信道纠错编解码原理 在数字通信系统中，经过信源编码和系统复接后生成的码流，需要通过某种传输媒介到达用户 接收机，传输媒介的形式多样，广播电视系统( 如地面电视广播系统、卫星电视广播系统或有线电 视广播系统) ，电信网络系统或存储媒介( 如磁盘、光盘等) 均可成为传输媒介，传输信道即是这些 传输媒介的统称。通常情况下，编码后码流必须经过某种处理使之变成适合在规定信道中传输的形 式，之后才可以通过传输信道进行传输。在通信原理上，这种处理称为信道编码( c h a n n e lc o d i n g ) ( 与信源编码相对应) ，实现信道编码的系统称为传输系统。m 同样，在接收端也需要将从信道中得到的信息再做一次处理以还原编码前信息，这种处理被称 为信道解码，在发送端为适应信道传输而做的处理和接收端所做的还原处理统称为信道编解码。 由于在信道中存在各种干扰，收到的信息往往存在错误，使用一种信道编码方式使得在接收端 可以对这样的错误进行恢复是十分必要的。在发送端按照某种算法在原始信息的上添加冗余信息就 生成了纠错码，在接收端利用相应的纠错算法对出错的原始数据进行恢复。本文采用的r s 码即是这 样一种行之有效的纠错码。 1 2 信道纠错编解码在数字电视芯片领域的应用 如上节所述，数字通信系统中需要信道编解码和调制解调两个部分，世界上两大主流数字电视 传输体制美国的g a 系统方案和欧洲的d v b 系列标准就由各自的特点分别定义了相似的信道编 解码方案。 纠错编码可以还原信道干扰产生的误码，但是任何纠错编码的纠错能力都是有限的，当信道中 的干扰较严重，使得传输信号中造成的误码超出纠错能力时，纠错编码将无法纠正错误。为此只有 改善信道质量并提高纠错码的纠错能力，d v b 通信系统为进一步提高纠错能力采用了两级纠错的方 法。 d v b 系统中将整个通信系统，包括传输信道看成一个传输链路处于外层的纠错编解码被称为外 层纠错编码，而处于内层的纠错编解码被称为内层纠错编码。内层纠错编码首先对传输误码进行纠 正，对纠正不了的误码，外层纠错编码将进一步进行纠正。如内层纠错编码将传输误码纠正到1 0 e 3 的水平，经过外层纠错编码后，误码率一般可降至1 0 e 一5 ；内层纠错编码将传输误码纠正到1 0 e - 4 的 水平，经过外层纠错编码后，误码率则可降至1 0 e - 8 ，两层纠错编码大大提高了纠正误码的能力1 3 1 1 4 1 。 在现行d v b 通信系统中，外层纠错编码采用的是r e e d s o l o m o n 码( r s 码) 3 1 ，内层纠错编码采用 卷积码。 内层的卷积纠错编码虽然具有很强的纠错能力，但一旦发生无法纠正的误码时，这种误码常常 呈现连续发生的形式；此外，信道中还存在着诸如火花放电等强烈的冲激噪声，也会在卷积解码后 的码流中造成连续的误码。这些连续误码落在一组外层r s 码中，就可能超出r s 码的纠错能力而造 东南大学硕士学位论文 成信息失真。为避免这种情况，在两层纠错编码之间加入了数据交织环节。数据交织改变了信号的 传输顺序，将连续发生的误码分散到多组r s 码中，落在每组r s 码中的误码数量就会大大减少，不 会超出r s 码的纠错能力，r s 码能够将其纠正过来。实践证明，数据交织提高了系统的纠错能力， 特别是对冲激噪声的纠错能力。 1 3r s 码简介 1 3 1r 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 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 码被广泛应用在现代通信系统中，在典型应用如深空通讯、移动通讯和高清电视中都可 以发现它的存在1 6 1 。 作为b c h 码的一种，r s 码包含有用来对信道接收信号进行纠错的校验位，用来纠正信号传输 过程中发生的误码，尽可能降低误码率。r s 码的一个显著优势在于它具有很强的纠错能力，可以在 容限内以字节为单位进行纠错。 1 3 2r s 码的差错概率 r s 码对于记忆信道十分有效，而且可以有效地使用在大输入码元集的信道上。r s 码具有一个 有趣的特性：在一个长度为丑的r s 码中，可以加入多达2 个信息码元而不减小其最小码距。这种扩 展的r s 码的长度为n + 2 ，具有与原始码相同的纠错容限。若r s 码的码元错误概率b ，则可用信 道码元错误概率p 表示为： 最* 码1 刍2 - - i 。1 ( 2 了1 卜- p ) 2 q 。 “， 其中，f 是码本可纠正的错误码元数，码元长度是脚比特。 对于指定的调制方式，比特错误概率的上限可由码元错误概率来表示。以m = 2 。的m f s k 调 制为例，b 与b 的关系为 墨：! i _ b2 ”- 1 ( 1 2 ) 图1 1 是随信道误码率p 变化的关系曲线，根据式( 1 1 ) 、式( 1 2 ) 画出了丑= 3 1 、具有不 同纠错能力t 的3 2 进制正交r e e d s o l o m o n 码。对于r s 码错误概率随分组长度妇呈指数下降的函数， 译码复杂度与分组长度的幂次成正比。r s 码在链接系统中应用时，内部的卷积译码器会先对解调器 2 第一章绪论 输出进行软判决再由卷积译码器将硬判决数据送到外部i t s 译码器，以进一步降低错误概率。 1 3 3r s 码对突发错误的良好性能 以一个r s ( 2 5 5 2 3 9 ) 码为例，码元长度8 比特( 这种码元通常称为字节) ，由于丑一土= 1 6 ，可 知该码可以纠正一个2 5 5 字节的码段段中最多8 个字节的错误。这8 个字节的错误的发生位置可以 是随即的，即是说，当译码器纠正一个字节时，将该字节看成一个整体，无论错误是由该字节内的 哪个比特产生的。实际情况中，一个码元发生错误时，任何比特都可能发生错误，r s 码忽略错误位 置和以字节为单位的纠错特性对随机的错误也就有了先天的抵抗优势1 7 l s 。 1 3 4r s 码性能受分组大小和冗余度的影响 噪声的持续时间必须占用相对较小比例的编码字长，编码才可以抵制噪声的影响。为此接收噪 声必须在一个很长的周期上平均，减少突发和意外干扰的影响。所以可以认为纠错码性能和分组大 小成正比，这也就是前文提到r s 码在长码段的编码方式中得到广泛应用的原因。 图1 13 2 进制正交码， 丑= 3 1 ，f 位纠错的r s 码，r 随p 变化的曲线 随着r s 码冗余度的增加( 编码效率降低) ，可以增加编码的纠错性能，但是它的实现变得更加 复杂( 尤其对于高效率设备) ，应用于实时通信中带宽也必须有所扩展。为此在冗余度和编码效率之 间需要找到一个平衡点以取得最经济的效果。纠错性能随着冗余度增加而增加，是一个单调函数， 即使编码效率接近于零，系统性能也会持续提高，但是这不符合实时通信系统的要求。纠错性能的 提高是以增加带宽为代价的，带宽扩展与编码效率成反比。对于高斯信道，最佳编码效率大约为0 6 到0 7 ，莱斯衰落信道为0 5 ( 直接接收与反射接收信号功率之比k = 7 d b 条件下) ，瑞利衰减信道 3 东南大学硕士学位论文 为0 3 。为什么对于很大的编码效率( 很小冗余度) 和很小编码效率( 大冗余度) 会产生e 0 的 下降，这是由于任何编码都存在编码增益，所以当编码效率接近于l ( 没有编码) ，系统将会产生很 恶劣的差错性能。低编码效率下e n j 的下降更为明显，是因为在同时采用调制和编码的实时通信 系统中，提高和降低差错性能的两种机制都在起作用，提高差错性能的机制是编码，冗余度越大， 纠错性能就越好；降低差错性能的机制是由于冗余的增加造成平均码元能量的下降这直接导致译码 器产生更多的错误。最终第二种机制占了上风，因而在很低的编码效率下系统差错性能也会下降。 所以要根据实际的信道情况和带宽需求选取适当的编码效率。 1 4 本课题背景 当今社会，随着技术的提高，通信系统正迅速地走向“数字耐代”，在这个大趋势下，广播电视 从模拟向数字的过渡也已全面展开。我国高清晰度数字电视( ) t v ) 已经取得了不少成果，但在 数字电视接收核心芯片领域还有不小的空白。 东南大学国家专用集成电路工程研究中心为研制出自主的h d t v 信道解调解码芯片于2 0 0 3 年 成立了“数字电视正交幅度调制( q u a d r a t u r ea m p l i t u d em o d u l a t i o n ，q a m ) 解调接收专用芯片 s f j 6 6 0 8 研发项目，本课题的选题即来自芯片中的一个重要的模块f e c ( f o r w a r de r r o r c o r r e c t i o n ) 模块，是为了实现其中的r s ( 2 0 4 ，1 8 8 ) 解码而定。 s f _ j 6 6 0 8 芯片针对数字电视有线传输信道的接收端系统应用而研制，接收端系统框图如图3 1 所 示，芯片采用c m o s 工艺，工作于3 3 伏电压下，对d v b - c 或者i t uj 8 3 a c 比特流进行解调解码。 集成了模数转换器，运用q a m 全数字解调方式，并且支持1 6 ，3 2 ，6 4 ，1 2 8 ，2 5 6 点星座。本课题 的目的就在于为适用该系统而设计并实现一种高效的r s 解码器。 天线，电缆，传r f 图1 2 有线传输信道接收端系统框图 4 出 出 第二章r e e d s o l o m o n 编解码理论 第二章 r o o d - s oio m o l l 编解码理论 设计r s 码的硬件细节，必须对其运算规则所涉及的迦罗华域( o a l o i sf i e l d ) 及其算术规则有清 楚的了解。本章将对迦罗华域( g a l o i sf i e l d ) 相关的背景知识作出一些介绍，以利于后续章节的理 解。 2 1 迦罗华域 迦罗华域( g a l o i sf i e l d ) 是一种有限种类元可自由进行四则混合运算的集合，它因法国数学家 g a l o i s 而得1 9 1 1 “，简写为g f 域。 2 1 1 迦罗华域元素 对于任何质数p ，存在一个有限域，表示为g f 0 , ) ，其中包含有p 个元素。可以将g f ( p ) 延伸为 一个含有广个元素的域，定义该域为g f 的扩展域，表示为g f ( ，m 是一个非零正整数。g f ( p ) 是g f 的子集，例如二进制域g f ( 2 ) 是扩展域g f ( 删) 的一个子域。用于构造r s 码的的元素即是 扩展域g f ( 2 ”) 中的码元。 类似于实数域是复数域的一个子域。除了数字0 和l ，在扩展域中还有特殊的本征元素( p r i m i t i v e e l e m e n t ) ，用一个新的符号a 表示。6 f ( 2 “5 中任何非0 元素都可以由a 的幂表示。元素的无限集f ， 就是根据元素集 o ，1 ，a ) 而形成的 ，= 以a ：o2 ，口3 ，口二0 ( 2 1 ) 为了从f 中得到有限元素的集合g f ( 2 m ) ，必须对f 域施加一个条件，使它只能含有2 皿个元素 且对乘法封闭。域元素集对乘法封闭的条件可由如下多项式表示： o t ( 2 j - i ) ：1 ：a o( 2 2 ) 根据这个多项式限制条件，任何幂次数大于等于2 ”一l 的域元素都可降阶为如下所示元素 a ( 2 4 + 砷= 口( 2 。一1 ) a 舯l = a 舯l 所以， 从无限序列f 中形成有限序列后g f ( 2 “) 的元素由下式给出 ( 2 3 ) g f ( 2 脚) = 0 ，a o ，a 1 ，a2 ，a 2 m - 2 ， ( 2 4 ) 迦罗华域中元素除了可以用a 的指数形式来表示还有一种重要的多项式形式表示法： a 册d x 俨1 + a n p 2 x - 2 + + a l x + a o ( 2 5 ) 其中，由a 珊- i 直到矗0 的m 个系数分别取值0 或1 ，对应于二进制m 位数即有2 ”种取值可能。 2 1 2 加减法运算 g f 域的四则混合运算，不同于通常习惯的运算规则，其特点在于对任意域元素进行任何四则 混合运算所得结果仍为该域中元素。 5 东南大学硕士学位论文 当对任意两个迦罗华域元素进行加法运算时，即将相应的多项式相加： ( a 咖l x 廿1 + + a l 一+ a o p ) + ( 6 l 卜l x - 1 + + 6 l 一+ b o x o ) = i x 十1 + + c l | + c o p ( 2 6 ) 其中，c l = a ，+ 6 l ，0 i 1 1 1 - 1 然而，系数值只能取0 或l ，所以规定： 铲?2 唑 ( 2 ，) q = l当a ，乜时j 可以看出任意两个迦罗华域元素相加，即是对相应系数进行以2 为模的加法运算，对它们的二 进制形式来说，得数为两个二进制数按位异或的结果。 推论可知，任何域元素进行与自身的加法运算所得必然为0 ，且实际上减法和加法所做的操作 是完全一致的，结果也相同。 2 1 3 乘除法运算 进行乘除法运算首先要明白在构建迦罗华域时的一个重要概念域发生多项式( 某些资料称 其为本原多项式) ，表示为p ( x ) 。域发生多项式为1 1 次不可约降次多项式，对于一个指定大小的迦 罗华域，域发生多项式可以不同，但编码方和解码方必须采用相同的域发生多项式。 以g f ( 1 6 ) 为例，设定域发生多项式为 p ( 曲= 一+ x + l ( 2 8 ) 在迦罗华域中，所有的非零元素都可以通过函数构建出来。定义本征元素岱为域发生多项式 p ( 曲的根，即：p ( a ) = 0 ，此即所需要的函数关系。举例来说，对于g f ( 1 6 ) ，采用式( 2 8 ) 作 为域发生多项式，可得方程： 口4 + a + 1 = o ，亦即：a4 = c t + 1( 迦罗华域中加减法等效) 从a o 开始，逐级乘以a ，并根据上式以口+ l 替代各级中存在的a 4 项，便完成了g f ( 1 6 ) 的构 建。如表1 所示，从左往右四栏分别是域元素的指数形式、多项式形式、二进制和十进制等价形式。 从表1 中可以看到从a 1 4 项开始继续逐级乘以口，口”= 口o ，a ”= a 1 ，说明了迦罗华域 对乘法封闭且有固定个元素的特性。 在迦罗华域定义中，乘法被定义为两个域元素的积与域发生多项式觥模余运算所得的结果， 即取黼两数乘积后的余数作为真正的积。这样的操作出于符合有限域运算在自身域内封闭的原 则，由于p 为m 次，则余数必然小于或等于m 一1 次，从而确保乘积是一个有效的迦罗华域元素。 在实际的实现中乘法会使用专用的乘法器来实现，且在设计方法上也采用的是直接按位取得逻 辑表达式后组合逻辑电路实现的方法，后文将针对不同乘法器的实现详细分类介绍实现的结构和电 路的优化方法。 6 第二章r e e d s o l o m o n 编解码理论 表1 g f ( 1 6 ) 采用p ( 曲= 一+ x + i 时的域元素 i n d e xf o r m p o l y n o m i a lf o r mb i n a r yf o r m d e c i m a lf o r i l l 000 0 0 00 a o 1 0 0 0 1 l a l a 0 0 l o2 口2a 2 0 1 0 04 a 3 a 3 1 0 0 08 a 4 a + 10 0 1 13 a 5 a + 口0 1 l o6 a 6 a3 + 口21 1 0 0 1 2 a 7 a3 + a1 0 1 11 1 a 8 a 2 0 1 0 l5 a 9 口3 + 口1 0 1 01 0 a 1 0 a + a + 10 1 1 17 a i 1 a3 + a2 + a1 1 1 0 1 4 a 1 2 a3 + a2 + a + 1 1 1 l l 1 5 a 1 3 口3 + a2 + 1i i o 】1 3 口1 4a3 + l1 0 0 l9 举例说明，在g f ( 1 6 ) 中对1 0 和1 3 进行乘法操作，用多项式形式来表示为： ( p + 曲( p + f + 1 ) = + 一+ 矿+ x ( 2 9 ) 要完成迦罗华域乘法，必须用式( 2 1 1 ) 除以域发生多项式一+ x + 1 。 多项式除法类似于传统的长除法。首先对除数乘以一值以便其阶数与被除数相等，再将二者相 减( 对迦罗华域元素来说相当于相加) ，然后对余数重复进行上述操作，直至被除数的最低位参与运 算。 为方便起见，可将多项式的每项按次数高低从左至右排开，这样多项式除法运算就可以根据系 数值( o 或1 ) 进行，如下例所示： 叠tt 圣亡亡窖 被除数： 1110010 除数f ： lqqll 除数x 五： 除数l 11lll 1o0l1 l1000 1 qq! l011 据此可知，商为f + x + i ，而余数，亦即1 0 乘以1 3 的最终结果，为，+ x + l ，同样可以写 7 东南大学硕士学位论文 为十进制数1 1 。也就是：1 0 1 3 = 1 1 式( 2 9 ) 的多项式形式乘法操作同样可利用前述多项式分栏来完成。首先，将多项式，4 - f + 1 的每项分别乘以，4 - x ，再将所得相加，最后，无需采用多项式除法，可以直接利用表l 对任何指 数溢出项采取代替形式再次分别相加即可得出乘法运算的结果。如下所示： 圣tt 圣亡素圣 f ：lolo f ：lo10 l ： !qlq l11ool0 一= x + 1oo1l 亡：f + x 叠= t + 亡 0l1o l1oo 迦罗华域还有一种基于指数运算的乘除法技术，其规则为：积的指数通过将乘数指数相加再对 2 8 1 取余获得。仍用1 0 乘以1 3 为例，通过查找表l 可以发现：1 0 = a9 和1 3 = a ” 因此，1 0 x 1 3 = a 9 a ”= a ( 9 + 1 3 ) 埘耐1 5 = a2 2 肿4 ”= a 7 。 再次查找表l ，可以发现：a7 = 1 1 ，积的结果和多项式方法所得结果一样 指数法中没有域元素0 的表示形式，因此，必须强制0 值参与乘法结果。 指数法同样可以被用于除法运算： i i 1 0 = a7 a 9 = a ( 7 9 ) m 哪”= a ( - 2 ) m o d ”= a 1 3 = 1 3 2 2r s 编码 2 2 1r s 码字结构 r e e d - s o l o m o n 码是分组码的一种，这种编码方法的特点是，信息被分为分离的数据段，同时在 每一个数据段根据编码算法加入冗余的保护信息从而形成自包含的码字来用于传输，将各个码段发 生的错误和其余码段隔离开来，提高了系统的稳定性。 如图2 1 所示，保护码元作为独立的段添加至数据段尾部，原始数据部分完全保持了原形，编 码过程并不改变信息码元本身，所添加的信息都是只和本码元相关的，不会受到相邻码元错误的干 扰。 8 第二章r e e d s o l o m o n 编解码理论 煸码后码字( ns y m b o l s ) 一 一 ： i ： 一 原始信息( k s y m b o l s )冗余( 2 ts y m b o l s ) 图2 1r e e d s o l o m o n 码字定义 r s 码的单元由一段具有多比特的字节组成，即使传输中可能单个字节的每一位都发生了错误， 对于码的纠错操作而言，同一字节内的所有错误只算一个字节错误，这样的结构使得它尤其适于处 理连续的误码。 一个r s 码字被描述为( n ，k ) 的形式，n 代表段的长度，即所含字节数，k 是实际的信息字节 数，不同参数的r s 码纠错能力不同，硬件实现的复杂度也有不同，同时： n 2 ”一l( 2 1 0 ) 其中n l 为每字节包含的比特数，式( 2 1 0 ) 中等号不成立时，所形成的码字称为r s 码的缩短 形式。据上所述，冗余信息为n - k 字节，设每个码字至多能纠正f 个字节，则有： t = ( 丑一曲2当n - k 为偶数时 t = 佃一七一1 ) 2 当n 岳为奇数时 r s 码字的信息位和校验位都是特定迦罗华域的域元素，显而易见，对于基于1 1 位的r s 码，对 应的迦罗华域必须有2 0 个元素。 2 2 2 码元发生多项式 构2 - 个r s ( 马d 码必须首先建立码元发生多项式颤砷，颤习含有n - k = 2 t 个因式，因 式的根为连续的迦罗华域元素，这是确保码距最大的必要条件。因此，码元发生多项式具有形式： 反两= ( x + o t6 ) ( _ ) 【+ 口b + 1 ) ( x + a 2 卜1 ) ( 2 1 1 ) 需要说明的是在各类不同文献中，上式表示略有变化，容易被误解。例如，一些文章选用域元 1 9 , a o 开始( b = 0 ) ，但其余却选取从a 本征元素开始( b = 1 ) 。这些选取方法都是有效的，但 由于发生多项式的些微差异会造成r s 码的截然不同，从而需要不同的编码器和解码器。一般为了 硬件实现时复杂度稍稍减小一些，可以取b = 0 ，这是因为b 值的选择靠近2 。一l ，一些根可能会 超出口”一l 。这通常根据各个标准的不同来设置，并不是主要的问题。 9 f篙l 娜洄 东南大学硕士学位论文 2 2 - 3 编码过程 在r s ( n ，l c ，0 中，初始信息的k 个符号作为一段被编码，表示为一个k l 阶的多项式： m ( 两= o i x * - 1 + + m l x + m o 其中，每个系数m b i ， f l ，m o 都是一个埘比特的信息符号( 符号长度由选择的r s 码形式 决定) ，这些符号同时也是( 谤( 2 ”) 的域元素之一，m 在最高位。 首先将信息多项式m ( x ) 乘以x “( 即左移n 一七位，低位补零) ，结果作为被除数。将码元发 生多项式作为除数，进行多项式除法运算，得到商q ( 习和余数“曲。计算可表达如下： 丛坚兰：q ( 曲+ 塑 ( 2 1 2 ) g ( x )占( x ) 将余数“两加在m ( 曲r 4 上即得到实际传输用的码字玎神： h 曲= m ( 砷r - 上+ f ( 曲 = m 一1 ，1 + + m 0 广j + o 卜l 矿h + + 而 这也正体现了r s 码是系统码的形式。 通过对式( 2 1 2 ) 两边乘以艄到： 城x ) 妒= q g ( 妒f t x ) 移项可得： m ( x ) x x 以广= q x g ( x ) ( 2 1 3 ) 容易注意到，式( 2 1 3 ) 的左边即是传输用码字7 i 矽，可以推断出，在正确传输的情况下，接 收端收到的传输码字应可以被码元发生多项式整除换而言之，一旦余数不为零，则t 中必然含 有一个或多个误码，这点同如c r c 码等只需要探测错误的编码方式是相同的。 2 2 4 编码示例 举r s ( 1 5 ，1 1 ) 为例，任取一段1 1 个符号的信息，每字符长4 比特，如：1 ，2 ，3 。4 ，5 ，6 ，7 ， 8 ，9 ，1 0 ，1 1 ，可以得到信息多项式 雹柚： t o + 2 叠+ 3 叠+ 4 t + 5 萱+ 6 叠+ 7 叠+ 8 + 9 0 + 1 0 ；+ l ll 2 1 4 ) 对式( 2 1 4 ) 乘以x 4 ，可得： 又4 + 2 t 3 + 3 t 2 + 4 t l + 5 t o + 6 t + 7 叠+ 8 叠+ 9 叠+ l o f + l l 叠( 2 1 5 ) 岩及以下项均先补零，然后将上式除以码元发生多项式得到余数多项式删。最后将删填在式 ( 2 1 5 ) 补零的位置上即得到传输信息多项式7 和啪以下是具体的计算过程： 1 0 第二章r e e d - s o l o m o n 编解码理论 在多项式除法的每一步中，码元发生多项式都乘以一因子，列于左手栏中，以使得最高项与前 一级余项的最高项相同。两者相减( 相加) 消除最高项。形成新的余项，如此往复，过程如下： 一：1 1 一o ? ，px 4rf r l2345 6 789 l o 1 l0000 一o l耋三l1 2 1 30596 1 3 ， 1 32生! 兰3 71457 7 ， 211222 1 0 1 3 2 58 x i o x 7 l q1 21 31 q ! l1 51 599 1 x 6l1 53l1 2 01 2 8 5l o 0 矿 q qqq q 1 285 l o1 l x 1 2 x 4 1 2 z1 21 02640 o，00000 26400 2 f 21 3 211 1 122l l0 1 1 x l !三l 垒! ! 三 l1 201 30 1 i ! 三 l 1 2 331 2 1 2 因此，经过长除法可得余数： ，( 曲= 3 矿+ 3 矿+ 1 2 x + 1 2 商无用可以舍弃。 最终，传输码字“曲可以表达为： 一4 + 2 3 + 3 2 + 4 1 + 5 x i o 十6 矿+ 7 x + 8 x 7 + 9 x 6 + 1 0 f + 1 1x 4 + 3 f + 3 f + 1 2 一+ 1 2 ( 2 1 6 ) 或者简写为：l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，3 ，3 ，1 2 ，1 2 。 由于多项式除法的硬件实现是有较大难度，所以在编码器的硬件实现上通常采用流水线 ( p i p e l i n e ) 操作： 一4 3 一：，一o ，一，f ，ff p 00 00 东南大学硕士学位论文 烈神 1 烈曲 觑曲 烈砷 烈神 6 l l 01 2 烈神0 qqqq l l01 20 甙帕 1 2 821 21 5 8 1 1 1 21 5 一曲0 qq q q 1 l1 21 50 g ( 砷 2 1 3 21 i l 9 21 l g ( x ) x 1 1 3 1 41 1 1 3 1 01 201 3 甙神 l ! 311 2 331 21 2 p i p e l i n e 方法对多项式运算进行小小的变化，对每个字符当运算进行到它时才提取进行操作，可 以描述为，第一个信息字符1 ，在运算中被加到初始值为零的最高位栏中，得出1 。然后乘以码元发 生多项式的其余系数1 5 ，3 ，l ，1 2 ，得数分别加入初始值均为零的其它栏中，接下来第二个信息字 符2 再被加上最高位栏中的新系数1 5 ，得出1 3 ，再与码元发生多项式的其余系数相乘，如此往复， 得出余数。 2 2 5 编码器硬件结构 2 2 4 节中所述的流水线式编码操作很容易用如下图所示的硬件电路实现： o u t o u t k e y 专磊 专乘菇 图2 2r s 编码的硬件实现电路结构 图2 2 中，所有的数据宽度都是4 比特，在初始输入时，与门使能数据在送入乘法器运算的同 时从选择器输出端直接输出，在前文p i p i l i n e 方法所述的1 1 个计算步骤完成之后( 即需要1 1 个连续 的时钟周期) ，余数各项存放于四个d 触发器中。接下来关闭与门，终止送数据到乘法器。最后，4 1 2 第二章r e e d s o l o m o n 编解码理论 个寄存器中的余数依次顺序移位输出到选择器的输出端，完成编码过程。 2 2 6 编码截短 对于r s 0 5 ，1 1 ) 的编码截短版本，例如r s 0 2 ，8 ) ，是将编码前信息字段前三项系数置零编码后 抛弃而得到的。这一改变对2 2 4 节的流水线型硬件结构的影响在于所有的寄存器置零，直至第一个 非零的一1 项输入到达。因此，只要控制信号在数据输入时间内保持为高电平，图2 2 所示的电路结 构依然可以用于截短的r s 编码。 2 2 7 符合d v b c 标准的r s 码 在d v b - c 标准中采用的是经由r s ( 2 5 5 ，2 3 9 ，卢8 ) 经过截短而得到的r s ( 2 0 4 ，1 8 8 ，# 8 ) 码。标准 规定编码时在信息字节前添加5 1 字节的零值，再传递到r s ( 2 5 5 ，2 3 9 ) 的输入端，在编码结束后再丢 弃这5 1 字节，1 8 8 字节的输入信息加上1 6 字节的冗余校验信息，构成了一个2 0 4 个符号长度的码 字。 r s ( 2 0 4 ，1 8 8 ) 基于g f ( 2 5 6 ) ，域元素的多项式表示形式为： a l i + a 6 叠+ a 6 叠+ a i 叠+ 虬叠+ a t f + a t t + 8 0 叠 对应的二进制数范围从0 0 0 0 0 0 0 0 到1 1 1 1 1 1 1 1 ，也就是十进制形式0 到2 5 5 。 d v b - c 标准规定的g f ( 2 5 6 ) 域发生多项式为： p ( x ) = x s + x 4 + f + f + l 移p = 一十矿+ f + 1 ( 2 1 7 ) 所构建的g f ( 2 5 6 ) 的部分元素列于表2 。与构建表2 采用的方法相同，g f ( 2 5 6 ) 的域元素值可以逐行 计算得出。在每一步，代表多项式形式域元素的二进制值向左移一位( 等同于乘以 ) ，如果移位导 致左边溢出，则加上0 0 0 1 1 1 0 1 ，根据式( 2 8 ) 可以推出这是p 的二进制代替形式 很明显，o f ( 2 5 6 ) 可以依次这样构建下去，因所含元素过多，故不一一列出。 此外，d v b - c 标准还对码元发生多项式作了统一规定： g ( x ) = ( x + 卯) ( x + ) ( x + 矛) ( x + a t 5 ) 其中a = 0 2 日，这意味着标准将迦罗华域的本征元素定为2 。 当将因式相乘并展开时，d v b - c 中码元发生多项式为： 烈而= 一6 + 5 9 1 5 + 1 3 x 1 4 + 1 0 4 x t 3 + 1 8 9 x a 2 + 6 8 1 + 2 0 9 x j o + 3 0 x 9 七8 x s 七1 6 3 x 7 七6 5 圣+ 4 1 t + 2 2 9 亡七9 8 t + 5 0 亡七3 6 x + 5 9 2 3r s 码解码 2 3 1 引入误码 在接收端得到的码字要经过解码还原成信息码字，其中可能会有误码信息，我们将误码以误码 东南大学硕士学位论文 多项式目矽的形式来表达，这样，在接收端接收到的多项式尉砂可以表示为： j 郇砂= 冠妒目萄 ( 2 1 8 ) 式中e ( x ) n - - f 以表示为： e t 玲= e 。誓i + + e ，x + e o 其中每一个系数值正o 局都是一个m 位的错误值，错误值也属于相应的g 】诳。域。错误值在码字 中的位置由j 的阶数来确定，若码字中有多于( n - k ) 2 的点值是非零的，那么将超出r s 码的纠错 容限，误码将无法得到纠正。 表2 g f ( 2 5 6 ) 部分元素 i n d e xf o r m p o l y n o m i a lf o r m d e c i m a lf o r m 父一 碧r碧 岩又碧 o000oo0000 a 0 00o0 00 0 l1 a l 0000 00102 a 2 000ool0o4 a 3 oo o0 lo0o8