（微电子学与固体电子学专业论文）里德所罗门解码器的研究.pdf

摘要 摘要 r s 码纠错能力极强，已广泛应用于通信、计算机、存储介质、网络和数字电 视领域，以提高数据可靠性。r s ( 2 0 4 , 1 8 8 ) 码是数字音频，多媒体广播( d a b , ：d m b ) 系统中采用的标准码。 本论文首先从宏观上介绍了与r s 码有关的基本常识和国内外发展现状。然后 从基本代数算法入手，介绍了有限域的基本概念及其算术运算，并提出了每种运 算的适合心国m b 系统的硬件实现结构。其次，介绍了编解码的基本流程，在此 基础上，分析了不同求解关键多项式的算法，比较各自优缺点，确定本文采用m e 解码算法，并提出了改进的m e 硬件实现架构；推导 t f o m e y 算法，使硬件实现电 路进一步简化。最后，提出了r s 解码器的具体设计方案并编写了相应的r 1 1 代码， 验证了功能的正确性，绘出电路仿真综合结果。此优化的r s ( 2 0 4 。t 8 8 ) 解码器规模 为3 j 万门，最高工作频率约为1 3 4 m h z 关键词z 里德一所罗门i t s 解码器r s f 2 0 4 j $ $ ) a b s t r a c t a b s t r a c t r e e d - s o l o m o n ) c o d eh a st h em o s tp o w e r f u lc l f f o r - c o r r e c tc a p a b i l i t y ，w h i c hi s w i d e l y u s e di n c o m m u n i c a t i o n , c o m p u t e r , s t o r a g em e d i a , n e t w o r k sa n dd i 【g i t a l t e l e v i s i o nt oe n h a n o gd a t ar e l i a b i l i t y r s ( 2 0 4 ，1 s 8 ) c o d ei st h es t a n d a r dc o d ei nt h e c o n c a t e n a t e dc o d es y s t e mo f t h ed i g i t a la u d i o m e d i ab r o a d c a s t i n g ( d a b d m b ) f i r s t l y ，s o m eb a s i ci n f o r m a t i o na n dt h eg l o b a ld e v e l o p m e n to fr sc o d e a r c ： i n t r o d u c e di nm a c r o s c o p i c a lv i e w t h ec o n c e p to ft h ef i n i t ef i e l da n dt h ea r i t h m e t i c o p e r a t i o na r ei n t r o d u c e db a s e do l la l g e b r aa l g o r i t h m ，a n dt h eh a r d w a r es t r u c t m e ：f o r d a b d m bs y s t e ma p p l i c a t i o na c c o r d i n gt oe a c ha r i t h m e t i co p e r a t i o ni s p r o p o s e d s e c o n d l y , t h i st h e s i si n t r o d u c e s t h ef l o wo fe n c o d ea n dd e c o d e ，a n da n a l y s e st h e a d v a n t a g e sa n dd i s a d v a n t a g e so fs o m es o r t so ft h ek c ye q u a t i o ns o | v c ia l g o r i t h m s , a n d f i n d st h em e ( m o d i f i e de u c l i d ) a l g o r i t h ma st h em o s ts u i t a b l ea l g o r i t h ma n dc o m e su p w i t ha na d v a n c e dh a r d w a r es t r u c t u r eo fm em o d u l e t h ef o r n e ya l g o d t h mi sd e v e l o p e d i nt h i st h e s i s , w h i c hh a sam u c hs i m p l e rs t y l e a d d i t i o n a l l y , t h eb l u ep r i n to ft h er s d e c o d e ri s p f o p o s e da n dt h ev e r i l o gh d lc o d ei sc o m p l e t e da c c o r d i n gt o i t f u r t h e r m o r e , t h ec i r c u i tf u n c t i o ni sv e r i f i e da n dt h er e s u l to fs i m u l a t i o na n ds y n t h e s i s a r eg i v e na tt h ee n do ft h e s i s t h eo p t i m i z a t i o nr sd e c o d e ro c c u p i e s3 5 kg a t e sa n dt h e h i g h c s tw o r k i n gf r e q u e n c y i sa b o u t1 3 4m h z 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论 本人签名： 不实之处，本人承担一切的法律责任。 日期芝! ! ：堑 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印，缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学 ( 保密的论文在解密后遵守此规定) 本人签名： 导师签名： 日期! l ! ：堑 日期垒盟! ! ! 堑 第一章绪论 第一章绪论 1 1 引言 近年来，由于数字与通信技术的迅速发展，人类对高科技通信产品的使用度 与依赖度与日俱增，使得我们处在一个数字化的时代，从计算机局域网到世界范 围的国际互联网( i n t e r n e t ) ，从普通电话到无线通信，从模拟电视到高清晰数字电视 ( i 玎丌v ) 的发展，无不印有数字化的痕迹。而通信的内容也不再只限于声音或者电 报码，它有可能是计算机资料，有可能是卫星数据，也有可能是高容量的视频信 号，随着信息内容的不同，以及接收端设备的多样化，进而衍生出多种不同的通 信方式。数字通信和网络技术是数字化时代两大主要支撑技术。一个典型的数字 通信系统如图1 1 所示。无论是网络还是一般的数字通信系统的数据传输，数据都 要经过信源与信宿之间的信道。信道将信源数据和信宿端的数据用户连接起来， 信道可以是微波链路，同轴电缆，电话线路，甚至磁带等数据在经过信道时， 由于诸如雷电、高频信道衰落、电源开关切换、通信设备中器件的缺陷和内部噪 声，以及由于信道过度开发面使得拥挤的数据信号之闻的相互干扰等的影响面使 数据失真。从而使信道的输入与输出不同，如果不采取任何措旌，在信宿端的用 户可能得不到正确的数据。 t o o 廿w l l e 蜘n a t i o n 图1 1基本数字通讯系统方块图 由图1 1 可知道，由信源输出的数据首先要经过信源编码，在传输之前要进行 信道编码【信源编码首先是把信源信号转换成二进制信息序列，然后为了使要传 2 里德所罗门解码器的研究 输的信源信息在传输率一定的条件下更快、更多地传输，需要把数据进行压缩， 进行数据压缩的编码方法有很多，如哈夫曼编码( h u f m a n ) ，j p e g ，m p e g ，h 2 6 4 等标准中的编码算法。信道编码是在信源编码器输出的信息序列中增加一定数量 的冗余码元，使信宿用户端能利用一定的方法( f 言道解码浏断接收的码字是否发生 错误，以及码字能否恢复，使码字具有一定的抗干扰能力，以保证信息传输的可 靠性，提高传输质量。 s h a n n o n 信道编码定理告诉我们：每一类信道都存在着一定的容量c ，它表示信 道的极限传输能力，只要实际传输速- 率r 而) 一段的码段。但是该码段的靠涡个校验元不仅与本组的 信息元有关，而且也与其前小段的信息元有关，称脚为编码存贮，因此卷积码用 伪口，b ，朋) 表示。 ( 2 ) 根据校验元与信息元之间的关系可分为线性码与非线性码。若校验元与信 息元之间的关系是线性关系( 满足线性迭加原理) ，则称为线性码；否则，称为非线 性码 ( 3 ) 按照纠正错误的类型可分为纠正随机( 独立) 错误的码、纠正突发错误的码和 纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码 ( 4 ) 按照每个码元取值来分，可分为二进制代码与口进制码【g i 矿，p 为素数， 埘为正整数1 1 3 1r s 码的发展 1 3r s 码的发展与应用 1 9 4 8 年，当时供职于a t & t 的克劳德香农( c l a u d es h a n n o n ) 发表了他的著名论 文( a m a t h e m a t i c a l t h e o r y o fc j o m m u n i c a t i o n s ) 3 1 ，这一论文成为了现代信息论的奠基 性文件。其中关于信道容量，信息传输率及信噪比的公式可以在任何一本信息论 教材中找到： f o rt h ec 搬o f d i g i t a ls i g n a l sp l u sw h i t eg u a s s i o nn o i s e , t h e r ee x i s t sac h a n n e l c a p a c i t yc i nb i t s s e c o n ds u c ht h a ti ft h er a t eo fi n f o r m a t i o nr ( b i t s s e c o n d ) i sl e s st h a n c t h ep r o b a b i l i t yt h a tt h er e c e i v e ds i g n a li si ne r r o rw o u l da p p r o a c hz e r o c 幽g 水+ s 这一公式意味着，理论上只要信息速率低于信道容量，那么一定可以在合适的条 件下实现无错传输实际应用中，为了取得理想的误码率( 或误比特率) ，设计者需 要选择合适的基带信号和调制解调方式，并采用频域均衡，增加收发端的信噪比 6 里德所罗门解码器的研究 等手段。而最有效的方法，就是对所要传送的信息进行纠错控制编码，也就是所 说的信道编码。纠错编码是以牺牲通信系统的其他性能指标如信号信噪比，信息 传输速率为代价的。它的实际意义在于，通过在收发端增加较少的信号功率而显 著地降低误比特率或者提供数据传输率。香农在他的上述论文中同时指出，在采 用极大似然译码法则的条件下，通过增加分组码的码组长度可以取得任意小的误 比特率。他同时指出，对于加性高斯白噪声信道，若要取得任意小的误码率，则 信噪比至少需要1 6 d b ，这一数值称为香农极限。 从1 9 4 9 年到6 0 年代初，这是差错控制码的提出、发展到奠定线性分组码的理 论基础阶段。这期问m m m i n g 于1 9 5 0 年发现了一类纠单个差错的分组码，b o s e ， r a y c h a u d h u r i ( 1 9 6 0 ) 和h o c q u e l i h e m ( 1 9 5 0 ) 找到一大类纠多个差错的纠错码( 即b c h 码1 。 1 9 5 9 年，h v i r e e d 和o u s m v es o l o m o n 发表了他们的论文( p o l y n o m i a lc o d e s o v e rc e r t a i nf i n i t ef i e l d ) ，这篇论文给出了r e e d s o l o m o n 码的雏形并直接促使了它 的诞生。这项发现最好起源于二十世纪5 眸代中期i r c e d 为雷达系统设计自动数字 处理器的工作。当时他们设计出一台完全由固体晶体管制造的计算机c g - 2 4 ，这台 计算机本身也具有许多开创性的工作，例如它是第一台完全用瑚r l 级语言设计的计 算机，并且具备初级中断功能。但此时i r e e d 开始关注伽罗华域的应用他试图用 非二进制有限域元素来设计以字节为单位的基本运算，以代替传统的比特级的设 计风格。这一想法在得到m 1 1 r 代数数学家g u s t a v es o l o m o n 的帮助和参与后，最终 导致了r e e d - s o l o m o n 码的诞生。 尽管r s 码的纠错能力相当令人满意，但在其诞生的早期并没有得到广泛的应 用，原因是由于没有好的解码算法，对于纠正6 个字节以上的数据传输错误都显得 异常困难。w w p e t e r s o n 首先将r s 码归结为一类特殊的b c h 码，并给出了一个基于 伴随式和基本对称函数的代数解码方法1 4 1 1 5 1 。这一方法通过求解矩阵方程来确定错 误位置。这项工作虽然较少被人提及，但实际上对r s 吗解码算法的发展及其重要 直到1 9 6 7 年，e r b e r l e k a m p 提出了一种可以有效地实现b c h 和r s 码解码的方法， b c d e k 锄p 将p e t e 嘲n 的算法改造成迭代形式【4 】嘲，使得可对高纠错能力的r s 码进行 解码，它首次使得可以纠正多个字节错误的r s 码的解码成为可能。1 9 6 8 年，j m a s s e y 则发t 现b e r l e k a m p 算法等价于寻找到一个能生成给定序列的最短线性移位寄存器。 所以，m a s s e y 黜了一种等效于线性反馈移位寄存器( l f s r ) 综合方法的b c h 译码 方法1 7 1 ，该方法与b c r l e k a m p 的方法是类似的，因而该算法现在常称为 b e r l e k a m p - m a s s e y ( b m ) 算法。b m 算法使得解码复杂度从。协3 ) 降到勺。1 9 7 5 年， s u g i y a m a e ta 1 提出了一种解关键方程的e u c f i d e a n 算法，该算法的复杂度也是d 0 2 ) ， 可以有效地对r s 码、b ( = h 码和g 叩p a 码解码嗍 上面提到这两种方法都需要大量的有限域乘法运算和求逆运算直到1 9 9 9 年 第一章绪论 7 h s i e c h i nq 岫尉b m 算法进行了改进，提出了一种只需要3 个有限域乘法器的串 行b m 算法，大大减少了b m 算法实现的复杂度和所占用的资源。 随后，又有人提出了一种改进的欧氏算法，因为b m 算法总要迭代很多次，并 且其改进算法只适用于串行处理方式，所以b r e n t e 和k u n gh ，z 又提出了修正的 欧几里德算法( m o d i 锄e d u c f i da l g o r i t h m ) ，这种算法也是只需要3 个有限域乘法器 实现。 虽然r s 的算法在不断的改进，但是由于微电子技术发展进程的限制，其相应 算法的硬件实现一直发展缓慢。直到了2 1 世纪初期，随着微电子技术、通信以 及音频视频技术领域的飞速发展，使锝r s 解码算法的高速硬件实现成为现实，从 而也推动了r s 解码器结构的研究和发展。并且，随着e d a _ t 具的发展，对r s 码的 研究重点也转移到了如何高速有效的硬件实现上 1 3 2r s 码的应用 在b c h 码中有一个重要的非二元码子类胁d s o l o m o n ( r s _ 码嗍。这种码的码元 符号和码的生成多项式s 伍) 的根取自相同的域，其码距满足s i n g l e t o n 界的上限，是 最大距离可分码，与相同校验位的其它分组码相比，r s 码的纠错能力更强。 r s 码除了能纠随机错误外，还具有很强的纠突发错误的能力，因而得到广泛 的应用。如r s ( 3 1 ，1 5 ) 码为战术军用通信中的首选码字，r s ( 1 5 ，9 ) 码为光存储介质的 标准码，而r s c 2 5 5 2 2 3 码则为美国航空航天局( n s ) 和欧洲空间站( e s a ) 在深空 卫星通信系统的级联码方案中所采用的标准外码。如今i n t e r n e t 的数据传输不再仅 依据于光缆( 电缆) ，著名的“铱星计划”就是用卫星的某些频道来传输i n t e m e t 数据 ( 虽然“铱星计划”后因为资金原因流产，但其通信思想对未来通信方式产生了深远 影响) 。欧洲数字视频广播标准采用t r s ( 2 0 4 ，1 8 8 ) 码作为差错控制级联系统的外 码，该级连系统可用于机顶盒( t o p - 辩t ) ，数字电视的接收部分。数字电视最终将替 代模拟电视，它具有广阔的市场前景。此外，r s 码还广泛地应用于密码学，以增 强数据传输的安全性 更高效的解码算法以及大规模集成电路技术的发展，使得r s 码在深空通信、 移动通信、军用通信、光纤通信、磁盘阵列及光存储方面等方面得到了广泛的应 用，正因为r s 编码的应用范围是如此广泛，对于r s 解码技术的研究也一直是国内 外的一个研究热点r s ( 2 0 4 , 1 8 8 ) 解码器是目前具有实际应用意义的分组码译码器 中结构最复杂，纠错能力最强的解码器，因此研究r s ( 2 0 4 , 1 8 8 ) 解码器的设计对其 它长度的r s 解码器的设计有指导意义，并且有很大的应用前景本课题就是在这 种背景下提出的 8 里德所罗门解码器的研究 1 4 本文的内容及章节安排 本文主要研究了r d s o l o m o n 码的解码算法及其实现结构。本文的章节及主 要内容安排如下。第一章介绍了r s 码的发展及应用，指出了研究意义第二章介 绍了r s 码的数学基础，即有限域代数理论，并且提出了加减乘除运算的硬件实现 方法。第三章研究了r s 编解码的流程及其对应算法，详细介绍了求解关键方程的 各种方法，并对比其优缺点，确定了求解关键方程最快、最节省资源的一种算法。 第四章设计了一个适合高速应用的比特并行r s 解码器，采用了基于修正的欧几里 德算法的解码方案，并对该方案进行了电路结构上的改进。第五章给出芯片设计， f p g a 仿真及测试结果。第六章为结论。 第二章有限域代数运算及硬件实现 9 第二章有限域代数运算及硬件实现 本章介绍r s 码的基本知识及其代数学基础。核心内容为有限域算术运算的基 本法则及其硬件实现结构，为下章r s 码的运算奠定基础，p , s 码的所有运算均 在有限域上 2 1 代数学基础 有限域代数( f i n i t ef i e l da r i t h m e t i c ) 【2 l 【1 0 1 是法国数学家伽罗华( g a l o i s ) 创始的一 门代数理论，由于有限域运算具有无进位、无四舍五入和固定字长等优点，因而 在差错控制编码，密码学、数字信号处理以及开关理论等信息学领域得到了广泛 的应用，在现代编码理论中占有重要的地位。有限域的生成、循环码的构造都离 不开抽象代数这一工具，抽象代数还是研究代数码的结构，查找新码的最佳工具。 为了弓l 入有限域，先来介绍“群“、。环”和“域”的概念 2 1 1 群的基本概念 设g 是非空元素集合，并在g 内定义了一种代数运算。”，若满足下述公理： 1 ) 有封闭性；对于任意珥6 - g ，恒有a b e g ： 2 ) 结合律成立；对于任意a , b , ce g ，有佃啊c = 口p - c ) ； 3 ) g 中有一恒等元c 存在；对于任意4 e g ，有c e g ，使口叩= p 叼= 口， 4 ) 对任意口e g ，存在有4 的逆元4 - j ，使得口恤一= e ； 那么称代数系统g 构成一个群( g u p ) 。 上述定义中，g 的运算符号“一可以是加法或者乘法如果为加法，则恒等元 记为0 ；如果是乘法，则称恒等元为单位元；群g 中的“单位元”是唯一的，群g 中的任意一个元素的“逆元”也是唯一的。 如果集合g 为有限集，则称g 是有限群，并把该有限群内的元素的个数席称 为有限群g 的阶数反之，如果集合g 内元素个数无限，则称g 是无限群。 如果群g 满足交换率，即a b = 6 4 ，则称为阿贝尔群( a b c l i a ng r o u p ) 或者交 换群。 此外，群的其他概念和定理以及格的概念由于本论文当中并不涉及，故在此 不作详细讨论，详细概念可参见参考文献【2 】 里德所罗门解码器的研究 2 1 2 环与域的基本概念 2 1 2 1 环的基本概念 非空元素集合r 中若定义了两种在其上的二元代数运算符加法和乘法，且满 足：下述定理： 1 ) 集合r 在加法运算下构成阿贝尔群； 2 ) 乘法具有封闭性，a , be g ，a b g ； 3 ) 乘法结合律成立，且和于乘之间有分配律，即对任何a , b , c g ，有： n 伪+ 0 = a b + a c 和( b + c ) a = b a + c m 则称集合r 是一个环。 由上述定义可知，环是在集合中定义了两种运算的代数系统。必须注意的是， 在环r 中乘法无恒等元，即无单位元，当然更无逆元存在。若环有单位元存在， 则称它为有单位元环。 若环r 对乘法满足交换律，即对任何元素a , be g ，有a b = b a ，则称此环为可 换环或者交换环。 2 1 2 2 域的基本概念 域是信道编码理论中一个重要的概念，它是具有两种运算的代数系统。 对于非空元素集合，若在，中定义了在其上的二元代数运算加和乘，若满 足下述公理： 1 ) ，关于加法构成阿贝尔群，其加法的恒等元记为0 ( 又叫零元) ； 2 ) f 非o 元素的全体在乘法运算下构成阿贝尔群，其恒等元( 单位元) 记为1 ； 3 ) 加法运算和乘法运算之间满足如下分配率： 口p + c ) = a b + a c 和( b + c ) a = b a + c a 则称f 为一个域( f i e l d ) 。 由此可见域是一个可换的、有单位元的、非等元素有逆元的环，且域中一定 无零因子若在f 中有0 因子，则由a , b e f ，4 d ，6 d ，得出a b = o ，因此 o = a 。o = a o q 6 ) = ( 4 a ) b = b ，这与原理假设的6 知有矛盾，因此4 6 d 。 由域的定义知，一个域至少含有两个元素，即零元( 加法恒等元) 和单位元( 乘 法恒等元) ，少一个都不能称为域一个仅具有零元和单位元的域，这其实正是常 用的最简单二元域，记为a f ( 2 ) 包含有限个元素的“域”被称为“有限域”或叫作“伽罗华( g a l o i s ) 域”，记为 a f ( q ) 域中的元素个数称为域的“阶”元素个数为厅的有限域记为g m ) 可以证 第二章有限域代数运算及硬件实现 “ 明，有限域g _ 鼬) 的阶数捧必为质数或某一质数的幂。 2 1 3 基于多项式的有限域 在有限域g 霸r 霉) 上的多项式可定义为； ，o ) - ，i _ t x 。44 - - - + 缸+ ，o ( 2 1 ) 其中系数正为o f ( q ) 中的元素，工为一未知元。 特别的。我们比较关心域g 固r 2 ) = 0 1 及其扩展域g j 缈) 。这是因为g j 吧! 域 上的任何一个元素，均可以表示为多项式的形式，多项式的系数在g ! 致萄= o 1 ) 上， 假设p ( z ) 一，4 - p 。，。1 + 4 - p l x 4 - p o 为g f ( 2 ) 上阶数为所的既约多项式，其 中用e g f ( 2 ) 如果可以被删除尽的形如，+ 1 多项式的最小次数为七= 2 剃则币哳) 为a 谁域的本原多项式。记本原多项式的根为口，即有： 口_ 一p - i 口。4 - 4 - p 1 a + p o ( 2 2 ) 由本原多项式的定义可知，集合i f , 口，口弓a 洳。玮 好不重复的构成整个a 妒 域。所以，a 称为g j 电_ ) 域的生成元素，面p 缸) 称为g j 犯勺域的生成多项式。当i m 1 时，a 总可以通过式( 2 2 ) 交换成五a ，口弓a m - o 的组合，因而 卫口，口乏口“) 构成g h 2 矾) 域的一组基，称为标准基( s t a n d a r db a s i s ) 。如果将口记为茹，则g f ( 2 d 域上的任何一个元素，重都可以唯一的表示为如下的多项式形式： a 一口w _ l x 。1 + a 0 2 z 4 - l t i i x + c bq 蔓改；圆一扣舛( 2 - 3 ) 因此，a 砸域的标准基也称为多项式基( p o l y n o m i a lb a s i s ) ，或者称为正交基。 提到了正交基，不能不提到对偶基，下面就给出对偶基的定义及其表示： 设 ，d ，6 户卅 是掣) 在g 2 ) 上的一个基，若存在另一个基 物弛一 m 使得打m p 力= 西时，称 声d 卢扣，尹“ 是标准基， 硒船一m 为其对偶 - l 基，其中办是迹函数：n 伍) 一亨 例 还可以用一般的线性函数代替迹来建立对偶基的概念，称为广义对偶基： 设 卢凸，扣，户。j 和 抽j 是g h r ) 的两个不同的基底，设陡线性 函数，是，的集合； ，- ( f f f ：g f ( p 。) 一g f ( p ) 设1 6 回v 一) ，t 口则当且仅当满足条件 ，【l y ，声，) 一如时，两个基底被称为是关于，和t 对偶的。其中 芦。声，芦。j ) 为标准基， 弛一j 为其对偶基 域元素z 可以用这两个基底表示为 1 2 里德所罗门解码器的研究 z 。荟钆反。荟厂何t 溉 2 2 有限域的算术运算及硬件实现 不难看出，在元素的多项式基表示形式下，g f ( 2 ，1 ) 域上两元素4 0 ) 和口o 。的加 法相当于将多项式相同次数项系数相加，而由于其均为模2 运算，所以其电路实现 形式上相当于异或运算。而乘法运算则需要将，l 和口0 ) 做多项式乘法后对域生成 多项式取模。这在后面会有详细讨论。 元素个数为尼的有限域记为g f ( , 0 可以证明，有限域g f ( n ) 的阶数 必为质数 或某一质数的幂。特别的，我们比较关心域矾2 ) = o ，1 及其扩展域a f ( 2 d 。这是 因为伪1 2 i 霄) 域上的加法运算和乘法运算可以通过逻辑与舢q d 和异或逻辑x o r 实 现。具体原因下面将给出证明。 2 2 1 有限域的加，减法 有限域的加减法是最简单的一种运算。下面将分为2 节，第一节说明算法以 及加法和减法的运算一致性。第二节给出实现形式。 2 2 1 1 加法和减法算法 在前面已经提到过，有限域上的加法器用异或逻辑即可实现，其具体推导过程 如下： 假设：在g j 啦内有2 个数a 和口做加法运算，则可以表示为a + b = c 用 2 。1 ，3 节中介绍的方法，将a ，暑与c 分别用多项式表示为： 4 _ 1 工。1 + 4 _ 2 ，- 2 + + 4 一+ 4 0 6 _ 声_ 1 + k 2 善_ 2 + + 6 p + b o 气一l ，1 + c _ 一2 ，- 2 + + c t x + c o 则a + b = c 可表示为： 0 k 一+ q 2 ，卜2 + 。+ d f + 旬+ 肥i 卜萱， + 屯。+ 水+ 的一c ；一+ c ；i ，也+ + c l z + c o o l - 4 + 电一) x 一+ 口0 2 + 岛卜2 ) 誓们+ + 瓴+ 岛弦+ + b o ) - c 1 寸誓“+ q 2 + + c + c 0 比较同次幂的系数，可以得到也吲一，；其蚧监：2 所以，实际上就是q q 岛，所以就印证了在前面曾经提蓟的加法器可以用异 第= 章有限域代数运算及硬件实现 或逻辑实现的说法。 当进行减法运算的时候，即为a - - b = c ，可以表示为： k “+ q r 2 + + 肇+ 砧一g o 也，2 + “f + 酗- 卜| + 5 矗p + 岬+ 龟 纯- l 也i 为+ 吃2 ) 广。+ 斗瓴吨弦+ - g ) - o + 弓d 严+ + c r r + q 比较同次幂的系数，可以得到c l - 4 l 一岛，。f m 一- 1 ；其中q 三：毫 当q 一岛时，从纯数学角度讲其值应该是土l ，但是由于q 是在g f ( 2 ) 域上的，所以 运算之后符号位将丢失，也就是说，q 仍然是q 一严a & t ，_ a b 珐i ； 这就说明，在g f 域上的加法运算和减法运算是一致的。这也就大大简化了运 算中符号的处理，在g f 域上就可以用“，替代“，而不会影响最后的结果。根据推 导结果，减法操作可以用加法代替，所以，只要实现加法器就可以了，并且，g f 域加法实际上就是按位异或。 2 2 1 2 加法器的硬件实现 讨论了加法器的算法之后可以知道，g f 域加法就是按位异或由于本论文是 基于a 域上的r s 实现，所以加法器的硬件实现就是8 b i t 的。按照前面的算法， 用v e r i o g 语言编写，具体代码如下； m o d u l eg l a a d ( h 1 ，i n 2 , d a t ao u t ) ； i n p u t 【7 ：o 】i n l ； i n p u tf 7 ：o li n 2 ； o u t p u tf 7 - 0 1d a t ao u t ； a s s i g nd a t ao u t = n l “i n 2 ： e n d m o d u l e 图2 18 位伽罗华域加法嚣 由上述代码综合而生成的电路如图2 1 所示，实际上是一个8 b t 的异或门 2 2 2 有限域的乘法 要理解乘法，先要了鳞一个概念：本原多项式。这个概念在2 1 3 节中已经提 1 4 里德所罗门解码器的研究 到，这里再次强调一下：本原多项式雌) 是一个最高次幂为m 次的不可约多项式， 也就是说再没有公因项葺p 协) 用来定义域中元素的关系。也就是说，雌) 定义了 最终计算结果在伽罗华域的映射关系，p 0 ) 不一样，也就是映射关系不一样，那么 同样是进行乘法运算，得到的结果就不一样。 例如，有2 个整数，3 和4 ，进行g f 域上的乘法运算，3 锄觏f ( 缸) ) = ，当p 0 ) = 5 时，3 * 4 r o o d ( 5 ) = 2 ，当p 0 ) = 8 时，3 * 4 r o o d ( 8 ) = 4 。从该例子就可以看出，如果本原多 项式p 0 ) 发生变化，那么相应的伽罗华域的运算关系也就发生了变化，自然，结 果就发生了变化。 2 2 2 1 有限域乘法器种类 在有限域运算操作中，乘法是最复杂最耗时的操作近年来已有一些g f ( 2 m ) 上的乘法器被开发出来，概括起来有限域乘法器实现方法主要有如下几种： 1 查表法：这种方法将有限域中的元素( 零除外) 用本原元的指数表示，并在 r o m 中存储每个元素的对数及反对数，有限域中任意两个元素的乘积可通过查表 获得。这种乘法器随着位数增加面积迅速增大。 2 线性反馈移位寄存器法【1 2 1 ：有限域中的任意两个元素的乘积可由线性反馈移 位寄存器电路获得。这种方法实现的乘法器电路简单，面积小，但需要埘个时钟周 期铆为乘法器的位数) 才能完成运算。 3 对偶基法【捌1 1 4 1 ：b e r l e k a m p 的串行乘法器首先采用了该方法。这种乘法器乘 数用对偶基表示，被乘数用标准基表示，乘积项用对偶基表示，乘法器只需移位 和异或运算。这种乘法器在目前所有己实现的乘法器中，如果不包括基转换电路， 其面积最小，但需要肼个时钟周期才能完成计算，且需要基与基之间的转换基与 基之间的转换电路的复杂性强烈依赖于生成域的本原多项式 4 正交基法i 甥：m v s s c y o m u r a 采用有限域中的正交基表示乘数和被乘数，乘积 项的每一个分量可用同一个函数表示a 啦域上的任一元素，可用一组正交基 j ，口，口之口剃l 唯一地表示，即 ，- b o a + b l a2 + b 2 a + + b _ l e g 2 。- 1 其中，町，幻，6 k i 为g f ( 2 ) 域中的数，加法在a 妒) 域上 为： 卢2 - b o a + b l a2 + b 2 a4 + + k 2 口2 卜1 + b m _ 1 f 7 2 。 ( 2 5 ) 声平方可表示 ( 2 6 ) - b m _ l a + b o a2 + b l a4 + b 2 a8 + b _ 2 a 2 “ 因此，如果将声看作g j ；中的元素用正交基表示的向量，并记为 ，- b o ，6 1 ，屯。 ，那么卢2 - 瓴- 1 6 0 ，6 l ，虬。 在正交基表示下，卢2 是卢的循 第二章有限域代数运算及硬件实现 环移位。再令y - c 。，c l ，c _ 。 为a 妒) 域上的另一个用正交基表示的元素，那么， 6 一声r - d o ，d 1 ，d 1 ，而最后一个分量羁可用一个包含芦和1 | 分量的二元函 数表示，印d 。厂仇，6 1 ，屯。，c 。，c l ，c _ 。) 。将秤方可得 6 2 一2 r 2 - 。，玩，“- 2 p 。1 ，c o ，c i ，气2 ( 2 - 7 ) 由此可得到 d 二_ l - ，( 6 坩- l ，b o ，b l ，6 _ - 2 ，c 一- i ，c o ，c l ，) ( 2 8 ) 重复地对硪生行平方运算可以得到其余乘积项的，函数表示形式 m e s s e y - o m u r a 乘法器对有限域元素的平方运算及指数运算非常有效。它可以 用两种方式实现：流水线方式和并行方式。流水线方式实现的乘法器面积较小，但 需要m 个时钟周期完成运算，并行方式实现的乘法器面积较大，速度快。此外这种 乘法器需要将有限域中的元素用正交基表示，乘积项表示函数需要用计算机搜索 才能获得，且与有限域中的本原多项式选择有关 5 。标准基法【1 6 l1 1 7 】【1 8 l 【1 9 1 基于标准基的乘法器将有限域元素用标准基表示，这 种乘法器应用广，可适用于任何有艰域中的乘法运算。s c o t - t r a v a r e s p e p p a r d 给出 了一个基于标准基的流水线结构乘法器，该乘法器为位串输入、位串输出工作方 式，完成乘法运算要肼个时钟周期，? t l 为乘法器的位数。 k a r a t s u b a o f m a n 算法是有限域多项式乘法运算的商效算法。算法描述如下：设 彳例和口似为阶数小于坍的多项式，其系数取自有限j 或f 中，那么其乘积 e ( x ) - a ( x ) b ( x ) 的阶数d c 酗o ”2 m 一2 ，下面讨论m = 7 ，沩自然数的情况，将 例和8 m 分别为高阶和低阶部分即： 竺! _ i 竺i 1 4 。工2 扣。2 4 - 4 - a ，) 4 - h 工2 4 - + 4 0 ) 工2 4 + 4 ij i 竺 !一!-l 曼 召红) - 工2 ( 6 二- l 工24 - + 虬) 4 - ( b 。工2 + + ) 一j2 最( 】) + 马( 】0 j i - l 再定义辅助多项式雅，： z ) o o ) 一a t 0 ) s l o ) d i - g ) + 4 0 ) 】【b i 4 - b k 0 ) 】 d ：( 砷- 4 p ) 风仁) 那么乘积多项式船) - 商白归扛 可由下式获得： 苎 芒g ) - d o o ) + 工2 【d 1 g ) 一d 。o ) 一d 2 0 ) 】+ 工。d 2 0 ) ( 二9 ) ( 2 - 9 ) 式与两个多项式直接进行相乘的结果比较，系数乘法次数减少为3 4 m 2 ，继续 对爿肛) ，a h ，a z ) 4 - a 和雄) 的相应部分按上述方法往下细分。系数乘法次数 将进一步减小，一直进行塑j t = l o g z m 步算法结柬c p a a r 将此算法用于g j 砥力上 1 6 里德所罗门解码器的研究 有限域乘法器的设计，这种乘法器复杂度为0 3 ) ( 其d p k = n m ) ，比一般有限域乘 法器复杂度o ( k 2 ) 的略小。这种乘法器面积较小，但设计方法复杂，且要将g f ( p y 靠) 中的元素的分量用a 妒) 中的元素表示而不是通常的用g f ( 2 ) 6 p 的元素表示 m a s t r o v i t o 乘法器也基于标准基的乘法器。对于掣) 上的两个阶数不大于m 1 次任意多项式4 g ) 和b g ) ，对本原多项c a ( x ) 求模的乘法运算可表示为： c g ) ；4 g 归0 ) m o dp ( x ) ( 2 1 0 ) 其中， a ( x ) - a m _ i x _ 1 + 4 _ 2 工_ 一2 + + a l x + 口o b ( z ) - b - 1 工m - 1 + _ 2 x 。_ 2 + + 6 p + c ( x ) - c _ t x 一- l + c _ 一2 + + c 一+ c o p ( z ) i 工_ + p _ 1 工- 1 + p _ - 2 j _ - 2 + + p l x + l 旦嘶，阢，句，ae g f ( 2 ) ，i = 0 1 朋- 1 ，引入矩阵z 鼍朋0 x 雌”，那么求模乘法可 以用矩阵表示为： c c o c 1 ： c _ - 1 - z 口_ ，0 。 厂l o 1 l h 4 ，l - i ，_ “1 ( 2 1 1 ) 兵中 f 4 l ；，- o ，1 ，j 啊一1 i - o j , ，臃一1 ，。- j ) 4 + 薹弓制一一；j 1 0 ，辨- 1 “咄，m - 1 p 场 而h ( p ) 一 ：，p o , i 弓，一】 ，所一，z o ，筇一，( 2 - s ) - k + 只鬟；篙：= 二7 m - 0 一， q m 弱信0 v 洳乘法器的空问复杂度为。电，6 ，设计简单，易于实现，面积稍大。基 于标准基的乘法器不需要进行基的转换，它可以与任意输入、输出系统匹配，而 且由于该乘法器的规则很简单，因此非常容易扩展到商阶有艰域。这种乘法器要 比基于对偶基或正交基的乘法器易于实现。 2 2 2 2g f ( 2 8 ) 域乘法器设计 本小节将介绍一个a 梢上基于标准基的乘法器的设计，与上节介绍的 m 弱咖叭t o 算法的区别是，本小节直接采用多项式乘法运算和多项式长除法运算获 “执； v八 第二章有限域代数运算及硬件实现 1 7 得乘积项的表达式，这种方法更易于用硬件描述语言如v e r i l o g ：拓 i 述，简化设计过 程，节省设计时间 伪伪上的任意两个元素，哇、b 及其乘积c 可分别用多项式表示为： 假设，有2 个上的元素，4 和曰，进行g f 域上的乘法运算，它们的乘 积为c ，假设本原多项式为p ( x 1 - 善8 + ，+ z 3 + f + l ，则可以表示为 c - - a * b m o d ( p ( x ) ) ，a 和口分别可以表示为a t x l + 4 6 + + 4 一+ 4 0 和 晰7 + 船+ + 6 一+ b o ，则用多项式乘法，将两式相乘所得结果如表2 1 所得的 结果表示为： c - e 毒“七e # 3 e 毒幢e 茹d e 亡挚e i i t 毒+ a a i 矗i 勾亡+ d 矗壬氐 然后再进行运算。删玑p o 盼，实际上是一个多项式的长除法，结果取余式而不是商。 运算如下： 垡型型坐! 丛堡苎熊堂苎苎塑 ，o o o 柚矿妒1 一f 耐彬彬忡