（通信与信息系统专业论文）基于edcme算法的rs译码器ip核设计.pdf

摘要 摘要 r s 码作为一类最大距离可分码，由于它具有很强的纠正突发错误和随机错误 的能力，因而被广泛应用于各种通信系统以及数据存储系统之中。 r s 译码的重点就是求解关键方程，本文主要研究m e 算法的最新改进算法 e d c m e 算法来求解关键方程。传统的m e 算法的实现需要多项式的次数计算及比 较电路，而e d c m e 算法不需要多项式的次数计算以及比较电路，可以在很大程 度上降低关键方程求解电路的复杂性。e d c m e 算法求解关键方程只需要2 f 一1 个 时钟周期，远小于m e 算法的3 t + 3 7 个时钟周期，这样就可以减少译码延时，提高 译码速度。 e d c m e 算法中所用的关键方程求解电路使用了3 f 个基本单元电路，通过并行 处理多项式的系数达到了较小的译码时延。由于整个r s 译码器主要是通过三级流 水线来工作的，第一级和第三级的处理时间都是n ，只有第二级关键方程的求解 电路的处理时间为2 f 一1 远小于n ，在连续译码的时候，关键方程的求解电路大多 数时候都是空闲的，资源得不到充分利用。为了节省资源同时不影响译码器的吞 吐率，本文提出了使关键方程求解电路资源最小化的设计方法。 在实际应用中，很多时候要用到缩短和打孔的r s 码，缩短的r s 码的译码和 一般的r s 码的关键方程求解算法是一样的，本文对e d c m e 算法进行了修改使得 它也适用于打孔的r s 码的译码。 最后，本文用v h d l 语言在f p g a 上实现了三种模式的r s 译码器：常规的 r s 码译码器、缩短的r s 码译码器和打孔的r s 码译码器，并对它们进行了软硬件 测试及性能分析。在测试的时候，发现e d c m e 算法初始化时没有考虑伴随式最 高次项系数为0 的情况，本文对此进行了补充。 关键词：f p g a ，e d c m e ，流水线，打孔 a b s l r a c t a b s t r a c t a sam a x i m u md i s t a n c es e p a r a t ec o d e , r sc o d ec a ne f f i c i e n t l yc o r r e c tb u r s te r r o r s a sw e l la sr a n d o me r r o r s r sc o d eh a sb e e nw i d e l yu s e di nv a r i o u sc o m m u n i c a t i o na n d d i 百t a ls t o r a g es y s t e m s t h em o s ti m p o r t a n tp a r ti nt h er sd e c o d e ri st h ek e ye q u a t i o ns o l v e r i nt h i sp a p e r , w em a k er e s e a r c ho nt h ee d c m ea l g o r i t h m i nt h em ea l g o r i t h m ，t h e r ea l ed e g r e e c o m p u t a t i o na n dd e g r e ec o m p a r a t i o nc i r c u i t s t h e r ea r en od e g r e ec o m p u t a t i o na n d d e g r e ec o m p a r a t i o nc i r c u i t si nt h ee d c m ea l g o r i t h m ，s ow ec a nr e d u c et h ec o m p l e x i t y o ft h ek e ye q u a t i o ns o l v e rt oag r e a te x t e n t t h ee d c m ea l g o r i t h mn e e d s2 t - 1c l o c k c y c l e st os l o v et h ek e ye q u a t i o n t h i st i m ei sf a rl e s st h a n3 t + 3 7o f t h em ea l g o r i t h m ，s o t h ed e l a yo ft h ed e c o d e ri ss h o r t e ra n dt h ed e c o d i n gs p e e di sf a s t e r a m o n gt h et h r e es t a g e so fp i p e l i n ei nt h er sd e c o d e r , t h ep r o c e s s i n gd e l a yo ft h e f i r s ta n dt h et h i r dp i p e l i n ei snc l o c kc y c l e s t h ep r o c e s s i n gd e l a yo ft h es e c o n d p i p e l i n e i s2 t - 1 ，w h i c hi sf a rl e s st h a nn w h e nd e c o d i n gc o n t i n u o u s l y , t h es e c o n d p i p e l i n ei si d l em o s to ft h et i m e ，t h u st h ec i r c u i t sc a nn o tb ef u l l yu s e d i nt h i sp a p e r , w e p r o p o s e dan e wm e t h o dt om i n i m i z et h ec i r c u i t st os o l v et h ek e ye q u a t i o n t h i sm e t h o d c a nr e d u c er e s o u r c e s ，a n dw i l ln o tr e d u c et h et h r o u g h p u to ft h ed e c o d e r i np r a c t i c e ，w en e e ds h o r t e n e da n dp u n c t u r e dr sc o d e s t h ea l g o r i t h mt od e c o d et h e s h o r t e n e dr sc o d ei st h es a m ea st h ec o m m o n l yu s e dr sd e c o d e r i nt h i sp a p e r , w e m o d i f i e dt h ee d c m ea l g o r i t h m ，i tc a na l s ob eu s e dt od e c o d et h ep u n c t u r e dr s c o d e f i n a l l y , w er e a l i z e dt h r e et y p e so fr sd e c o d e ro nt h ef p g a ，t h ec o m m o n l yu s e d r sd e c o d e r , r sd e c o d e rf o rt h es h o r t e n e dr sc o d ea n dr sd e c o d e rf o rt h ep u n c t u r e d r sc o d e w et e s t e dt h e mi ns o f t w a r ee n v i r o n m e n ta n dh a r d w a r ee n v i r o n m e n t i nt h ee n d ， w ea n a l y s e dt h ep e r f o r m a n c eo ft h er sd e c o d e r s i nt e s t i n g , w ef o u n dt h a tt h ee d c m e a l g o r i t h md o e sn o tc o n s i d e rt h es i t u a t i o nw h e nt h el e a d i n gc o e f f i c i e n to ft h es y n d r o m e p o l y n o m i a li sz e r o ，s ow em o d i f i e di t k e y w o r d s ：f p g a ，e d c m e ，p i p e l i n e , p u n c t u r e d i i 图目录 图目录 图1 i 一般的通信系统框图1 图1 - 2r s 码译码流程图1 图2 1e u c l i d 算法时域译码9 图2 2d c m e 算法的流程图1 2 图2 3e d c m e 算法流程图1 4 图2 4 基于e u c l i d 算法的r s 纠删纠错译码。1 8 图3 1 译码器的接口图2 1 图3 - 2s t a ni i l 时序图2 2 图3 3r e a d y 时序图。2 2 图3 - 4s t a r to u t 时序图2 3 图3 5b l ke n d 时序图2 3 图3 - 6e r rn u m 和f a i l 时序图2 3 图3 7 有限域元素乘以口2 5 图3 8 有限域时序乘法器2 5 图3 - 9l c b p 乘法器中的循环移位2 6 图3 1 0b t x 的电路结构2 7 图3 1 1l c b p 乘法器2 7 图3 1 2r s 译码器电路结构。2 8 图3 1 3 伴随式分量计算电路2 9 图3 1 4 伴随式计算电路2 9 图3 1 5m e 算法关键方程求解电路的并行结构3 0 图3 1 6m e 算法多项式计算电路3 1 图3 17m e 算法控制电路31 图3 1 8e d c m e 算法并行电路实现结构3 2 图3 1 9e d c m e 算法并行电路实现的基本单元结构3 3 图3 2 0e d c m e 算法并行电路实现顶部单元2 f 结构3 3 图3 2 1 改进后的基本单元结构3 4 图3 - 2 2 改进后的顶部单元2 f 结构3 4 v 图目录 图3 2 3e d c m e 算法实现的状态转移图3 5 图3 2 4 钱搜索计算c r ( a ) 和仃位) 的电路结构3 7 图3 2 5 钱搜索计算c o ( a i ) 的电路结构3 8 图3 2 6 错误值计算电路及错误纠正电路3 9 图3 2 7 流水结构划分3 9 图3 2 8 流水译码示意图4 0 图3 2 9e d c m e 算法实现的串行电路结构4 0 图3 3 0e d c m e 算法串行电路的基本单元结构4 2 图3 3 1r s 纠删译码的结构图4 2 图3 3 2 删除位置多项式计算电路4 3 图3 3 3 带错误检测的r s 译码器结构图4 3 图3 3 4 错误检测电路的结构图4 4 图4 1r s ( 1 5 ，9 ，3 ) 码译码器的仿真图4 7 图4 2 测试模型图4 8 图4 3p n 序列发生器。4 9 图4 - 4r s 码系统码编码电路4 9 图4 - 5r s 编码后d s p 内存中的数据。5 0 图4 - 6 加干扰后的r s 码5 0 图4 _ 7r s 译码后d s p 中收到的译码数据5 l 图4 - 8r s 译码器误比特率曲线5 2 图4 9r s 译码器误符号率曲线5 3 图4 1 0r s 译码器误组率曲线5 3 v i 表目录 表目录 表3 1 译码器接口信号定义2 1 表3 2m e 算法、d c m e 算法和e d c m e 算法对比3 6 表3 3 常规码r s ( 2 5 5 ，2 3 9 ，8 ) 与口核的对比。4 4 表3 4 缩短码g s ( e 0 4 ，1 8 8 ，8 ) 与i p 核的对比4 4 表3 5 打孔码g s ( 2 51 ，2 3 9 ，6 ) 与p 核的对比。4 5 表4 1 有限域g f ( 2 4 ) 的元素4 6 表4 2r s 码最大纠错能力t 的测试结果5 1 v i i 缩略词表 英文缩写 r s m d s b m f f t m e e d c m e f p g a i p d s p l c b p l u t 缩略词表 英文全称 r e e d s o l o m o n m a x i m u md i s t a n c es e p a r a b l e b e r l e k a m p - m a s s e y f a s tf o u r i e rt r a n s f o r m m o d i f i e de u c l i d e n h a n c e d d e g r e ec o m p u t a t i o n l e s s m o d i f i e de u c l i d f i e l dp r o g r a m m a b l eg a t ea r r a y i n t e l l i g e n c ep r o p e r t y d i 百t a ls i g n a lp r o c e s s o r l o wc o m p l e x i t yb i tp a r a l l e l l o o k u p t a b l e v i l l 中文释义 里德索洛门 最大距离可分的 伯利坎普梅西 快速傅立叶变换 修改的欧几里德算法 增强的无需次数计算的 欧几里德算法 现场可编程门阵列 知识产权 数字信号处理器 低复杂度的比特并行 查找表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 卅年皇月彩日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：型盛导师签名：篮互趔l 日期：卅年上月弼日 第一章引言 1 1 信道编码及r s 码 第一章引言 在数字通信系统中，需要采用编码技术来达到一定的通信性能指标。在一般 的通信系统中，如图1 1 所示，编码部分可以分为信源编码和信道编码。信源编码 的目的是为了压缩冗余信息，以增强通信的有效性。信道编码则通过引入冗余信 息以增加通信的可靠性。信道编码技术是提高信息传输可靠性的一种重要手段， 广泛应用于各种通信系统中。 图1 - 1 一般的通信系统框图 r s 码是一种纠错能力很强的线性分组循环码，它属于信道编码部分。因为它 具有非常强的纠正突发以及随机错误的能力，因而被广泛应用于通信领域中。 1 2r s 码的译码 关键方程、计算错误位置、计算错误值和错误纠正。而译码的关键在于第二步求 电子科技大学硕+ 学位论文 解r s 码的关键方程，关键方程的求解有较多的算法来实现。比较适合用f p g a 来 实现的算法有b m 算澍1 】和e u c l i d 算法【2 1 ，以及它们的各种改进算法。 r i b m ( r e f o r m u l a t e di n v e r s i o n l e s sb e r l e k a m p - m a s s e y ) 是b m 算法的一种改进算 法，它去掉了b m 算法中不必要的些元件，因此硬件复杂度比b m 算法低。到 现在为止，也有不少学者对e u c l i d 算法进行了改进，出现了m e ( m o d i f i e de u c l i d ) 算法【3 】【4 】【5 】以及它的改进算法d c m e ( d e g r e ec o m p u t a t i o n l e s sm o d i f i e de u c l i d ) 算法 【6 1 ，还有最新的改进算法e d c m e ( e n h a n c e dd e g r e ec o m p u t a t i o n l e s sm o d i f i e de u c l i d ) 算法【7 l 【8 】【9 】。这些改进算法的主要特点就是通过算法求解错误位置多项式以及错误 数值多项式所需要的时钟周期数不断减少，硬件实现的复杂度也不断降低。 1 3 设计目标和论文组织 本论文的主要工作是在f p g a 上实现参数可变的通用的r s 译码器i p 核，即 三种模式的r s 译码器一常规的r s 译码器、缩短的r s 码译码器和打孔的r s 码译 码器。设计完成后首先用m a t l a b 和m o d e l s i m 软件在软件环境中对三种模式的r s 译码器进行验证，然后在实验室某项目用的p c b 板上利用x i l i n x 公司的v i r t e x 4 系列的f p g a 芯片- - x c 4 v s x 3 5 以及a d i 公司的t i g e r s h a r c 系列的d s p t s 2 0 1 芯片完成硬件测试工作。 本论文的内容是这样安排的： 第一章是引言部分； 第二章首先简要地介绍了与r s 码译码相关的基本的理论知识，然后讨论了实 现r s 译码的m e 算法及其改进算法d c m e 算法以及e d c m e 算法，并详细介绍 了本设计中所用的e d c m e 算法以及对算法的补充，接着介绍了纠删译码算法， 最后对e d c m e 算法的初始化条件进行了修改使得修改后的e d c m e 算法能够用 于打孔后的r s 码的译码； 第三章详细介绍了基于e d c m e 算法的r s 译码器的f p g a 实现，然后讨论了 如何对设计进行改进和优化，并用资源最小化的设计方法完成了三种模式的r s 译 码器的电路设计，接着简单介绍了r s 译码器中的错误检测电路，最后把设计完成 的三种模式的译码器分别与x i l i n x 公司的i p 核进行了对比； 第四章介绍了对所设计的三种模式的r s 译码器进行的软硬件验证方法以及 验证结果； 第五章对本课题进行了全面的总结，包括本文的贡献以及还需要改进的地方。 2 第二章r s 码译码理论 2 1 有限域 第二章r s 码译码理论 r s 码是在有限域中定义的，所以我们研究r s 码首先要搞清楚有限域的相关 理论。只含有限个元素的域称为有限域，又称为伽罗华域，我们通常把含g 个元素 的有限域记为e 或者g f ( q ) 。 我们可以如下来定义有限域g f ( q ) 上的n 次多项式： ( z ) = f n x “+ z l 工“叫+ + z x + 石( 2 1 ) 其中，z g f ( q ) i = 0 ，1 ，2 ，n 。 定义1 ：不存在非零次多项式为其因式的多项式厂( 功称为既约多项式，又称 不可约多项式。 定理l ：有限域f 上的多项式全体对模f ( x ) 多项式加与模f ( x ) 多项式乘运算 构成一个环，称为模f ( x ) 多项式剩余类环。 定理2 ：若有限域g f ( q ) 上的次数为m 的首一多项式 p ( 工) - i f ”+ 矾- l 工”- 1 + + 乃z + 岛( 2 2 ) 既约，则以模p ( x ) 加和模p ( x ) 乘为运算的环是有限域g f ( q ”) 。p ( x ) 称为有限域 g f ( q ”) 的域多项式。 定义2 ：有限域g f ( q ”) 上的具有最大阶的域元素称为本原元，通常用口表示。 定义3 ：如果0 9 g f ( q ”) ，是有限域g f ( q ) 上的多项式厂( 功的根，那么 0 9 ，f o p ，f o p 29 矿h 一定是f ( x ) 的m 个互不相同的根，这些根称为厂( z ) 的共轭根系。 定义4 ：以0 9 g f ( q ”) 为根的有限域g f ( q ) 上的次数最低的首一的多项式， 我们称之为c o 的最小多项式。 定理3 ：如果c o g f ( q “) 的共轭根系为0 9 ，f o p ，国p _ ，0 9 ，那么缈的最小多项 式为有限域g f ( q ) 上的m 次多项式，最小多项式表示为： m - i r e ( x ) = 兀( 工一f o p i ) ( 2 3 ) # o 。 定义5 ：有限域g f ( q ”) 中的本原多项式是本原元口的最小多项式m r ( x ) ，常 记为p ( x ) = p 。( x ) = m 。( x ) 。 电子科技大学硕士学位论文 2 2b c h 码 定义6 ：g f ( q ) 上广义g 元b c h 码是以g f ( q ”) 中的非零的8 - 1 个元素 五，“1 ，“扣2 ) 为根的循环码，其中整数兄 0 ，整数万 1 ，我们称g f ( q ) 为码 元域，g f ( q “) 为根域。 根集合 ，肌1 ，蝴。2 ) 中各元素的最小多项式为 m 五( x ) ，m 川( 功，+ 8 - 2 ( 工) ，则有b c h 码的生成多项式： g 雪搿( x ) = l c m m i ) m 纠( x ) 珑五+ 5 2 ( 力 ( 2 - 4 ) 其中l c m ) 表示取最小公倍式，由此生成多项式生成的循环码称为g 进制 b c h 码。口等于2 时为二进制b c h 码。 b c h 码按其参数五是否为1 和根集合是否包含本原元分为狭义和广义b c h 码 以及本原和非本原b c h 码。 如果b c h 码的生成多项式g 占倒0 ) 的根中，有一个g f ( q ”) 域中的本原元，那 么码长r l = q ”一l ，我们称这种b c h 码为本原b c h 码；否则，称为非本原b c h 码。 定理4 ：b c h 码的最小码距矗i 。万，并称参数占为b c h 码的设计距离。 2 3r s 码 r s 码是一类有很强的纠错能力的线性分组循环码，它是二进制b c h 码的多 进制推广。在有限域g f ( q ”) ( q 朋2 ) 上，码长以= q 埘一1 的本原b c h 码称为r s 码。 r s 码的码元和它的生成多项式的根均在g f ( q ”) 上( g ”2 ) 。 长为n = q ”一1 ，设计距离为万的r s 码，生成多项式： g ( x ) = ( x 一口2 ) ( x - - t z “) ( x 一口五+ 占一2 )( 2 - 5 ) 其中旯是任意正整数，口为g f ( q “) 上的本原元。由此生成了一个g ”进制的 ( g ”一l ，q ”- 8 ) 的r s 码。 ( n ，k ，o r s 码的纠错能力为t = ( t l - - k ) 2 ，最小码距为d = 2 t + 1 。在后面章节 中我们将纠错能力为t 的( n ，k ) r s 码表示为( n ，k ，o r s 码。 2 4r s 码的伴随式译码 r s 编码后的码字多项式c ( x ) 在带有噪声的信道中传输，噪声e ( x ) 叠加到 4 第二章r s 码译码理论 c ( x ) 上并传送到接收端，接收端接收到的码字多项式r ( x ) = c ( x ) + e ( 工) 。其中： c ( 力= c ：一l z ”_ 1 + c ；工+ c o ( 2 - 6 ) e ( x ) = e l x ”叫+ + e z + 毛 ( 2 7 ) r ( x ) = 见一i x ”- 1 + + 置x + 民 ( 2 8 ) r s 译码的基本思想就是：从接收多项式r ( x ) 中找出错误的位置和错误值，即 错误图样e ( x ) 的系数e ( f = o ，1 ，万一1 ) ，然后从r ( x ) 中减去e ( x ) 就得到译码后的 正确码字c ( x ) ： c 7 ( z ) = r ( x ) - e ( x )( 2 - 9 ) 其中： c 7 ( 砷= q 一。x ”1 + c 仁+ q( 2 - 1 0 ) r s 译码的第一步是由接收多项式r ( x ) 计算伴随式，对1 f 2 t ，伴随式多项 式s ( x ) 可以表示为： s ( x ) = s 2 ，x 2 卜1 + + 叉x + 墨 “一i ( 2 1 1 1 ) = 墨一 卜7 伴随式的第i 个分量是： 墨= r ( t z ) = 民一i 口肛v + - - + r t a + r o = r o f 扩 ( 2 - 1 2 ) j - - o 因为口，o f 2 c o f 2 是每个码字多项式的根，故对l5f 2 t ，c ( a ) = o ，所以伴随 式分量和错误图样有以下关系： n - i 墨= e ( 口) = 易口妒 ( 2 - 1 3 ) ，= o 由式( 2 一1 3 ) 可知，伴随式分量仅取决于错误图样e ( x ) ，而与传输的码字无关。 由式子( 2 1 2 ) 和( 2 - 1 3 ) 可以得到以下方程组： 墨= 尺( 口) = e j , o f + e ja 厶+ + 曩口凡 是：r ( 口2 ) 2 气位 ) 2 + 气似办) 2 + + 曩( 口 ) 2 ( 2 1 4 ) ： 足，= 尺( 口2 ) = 毛( 口 ) 2 + ( 口止) 2 + + 气( 口 ) 2 电子科技大学硕士学位论文 式中口 ，口止，口上都是未知的。求解这些非线性方程的任何方法就是r s 码的译码 算法。一旦找到了口 ，口止，口 ，则幂次工，j 2 ， 就告诉我们式( 2 - 7 ) 中的错误位 置。然后就可以求得错误值e 一一般而言，方程组( 2 1 4 ) n - - i 能有很多解，每一种解 得到不同的错误图样。若在实际错误图样e ( x ) 中的错误数目是t 或更小( 即1 ，t ) ， 则能产生有最小错误数目错误图样的解就是正确的解。这就是说，相应于这个解 的错误图样就是由信道噪声引起的最可能的错误图样。若t 很大，则用直接方法求 解方程组( 2 1 4 ) 既困难又费事，一般我们都采用间接的方法来解方程组。 为了方便，对l ，我们定义z = 口 为错误位置数，因为它们告诉我们错 误的位置。用错误位置置来表示方程组( 2 1 4 ) 可以表示为： s i = r ( a 1 = j i xl + e j 攀1 七+ e j v x ， 是= r ( 口2 ) 2 毛五2 + 置2 + + 色。，置2 ( 2 1 5 ) s n = r ( o t _ 、= e j j x ：t + e h x 2 乞+ + e j v x j t 1 9 6 0 年p e t e r s o n 提出不必计算上面的非线性方程组，而是将其转换为一组线 性方程式，用错误位置多项式对其求解。为此定义错误位置多项式为： 盯( x ) = ( 1 一五x ) ( 1 一五力( 1 一墨x ) ( 2 - 1 6 ) = a o + o 一+ + o f t 是实际发生错误的符号个数，仃( 工) 的根盯1 = 口一 = 口- h 是错误位置的倒数。也 就是说，如果把代入盯( x ) 后得到0 ，那么口就表示错误位置，错误图样瓦一不 为0 ，接收数据尺就是错误数据。 2 5 关键方程及其求解算法 由错误位置多项式盯( x ) 可得： 盯( x ) = ( 1 一x l x ) ( 1 一j ，2 x ) ( 1 一x , x ) = l 一( 五+ 五+ + 置) x + ( 五五+ x 。墨+ ( 2 - 1 7 ) + 五一。五) x 2 + ( 一1 ) 五五置， 对比式( 2 1 7 ) 和式( 2 1 6 ) 有： 6 第二章r s 码译码理论 那么式( 2 1 7 ) n - i 表示成： 吒= l q = 一( 五+ x 2 + + 五) 吒= ( x 。x 2 + 五置+ + z 一。置) ： t r , = ( 一1 ) 五置置 盯( x ) = 1 + 呒石+ + g 若以为错误位置，m = l ，2 ，t - 1 ，t ，那么： 仃( 叉乙一) = l + q 义二_ + + o r t 叉- 一= o 式( 2 2 0 ) 两边同时乘以以可得： x ：+ o | x ：+ + o r = q 式( 2 2 1 ) 两边同时乘以以”，刀= 1 ，2 ，f 一1 ，t ： e j 。x ：t + a ，e j x ：p + + o t e j 。x ：= o 对m 求和可得： 弼州+ q 气g 卜1 + - + q 气e = o 月 = lm = lm f f i l 由方程组( 2 1 5 ) 可知： e j i x ：1 - = - s n 。 m = l 所以式( 2 2 3 ) n - 以写成如下形式： q 邑卅l + + q 鼠= 一瓯+ ， 由于墨，f = 1 ，2 ，t 在前面式( 2 1 2 ) 已经求出，因此可以得到以下方程组： q 墨+ 呸墨一i + + g s = 一s + l q 墨+ l + 吒置+ + q = 一s t + 2 ； q 是h + 吒& ，- 2 + + q 墨= 一是， 7 ( 2 - 1 8 ) ( 2 - 1 9 ) ( 2 - 2 0 ) ( 2 - 2 1 ) ( 2 - 2 2 ) ( 2 - 2 3 ) ( 2 - 2 4 ) ( 2 - 2 5 ) ( 2 - 2 6 ) 、， x 誓 一 ，i ，n = 电子科技大学硕士学位论文 写成矩阵的形式如下： s is 2s s 2s js i s 3s 4s s s | s t 。ls t n q o r , 一i q 一2 ： q 一墨+ 。 一墨+ ： 一置+ 3 ： 一是， ( 2 2 7 ) 决定r s 码译码器复杂度的主要因数在于求解上面的方程组，得到错误位置多 项式仃( x ) 。 用s ( x ) 乘以仃( x ) 可以得到： s ( x ) c r ( x ) = s i + ( s 2 + s q ) x + + ( + 墨一l q + + s i q i ) ，q + ( 墨+ l + q + + s i q ) ，+ ( 墨+ 2 + s t + l o r , + + 孓q ) 一+ 1 + + ( 最，+ 是卜l o l + + q ) z 2 卜1 ( 2 - 2 8 ) + ( 足，q + + 墨一i q ) ，+ + s 2 ，t r , x 撕- 1 2 + c o l x + + q i ，一1 + c o t x t + + c 0 3 卜l 工3 卜1 令c o ( x ) = c o o + c o a x + + q l 一+ c o t x + + c 0 3 f - i x 射，由方程组( 2 2 6 ) n - d - 得： 吼墨+ 吼墨一i + + q 墨+ 墨+ i = 0 ，s + t + 吒置+ “+ q 最+ 墨+ 2 ( 2 - 2 9 ) q 是卜l + 吒是卜2 + + q + 足，= 0 所以式( 2 2 8 ) 中次数大t l 而小于2 f 的项的系数都为o ，所以式( 2 2 8 ) n - - 以写成： s ( x ) c r ( x ) 兰c o ( 神m o d ，( 2 3 0 ) 式( 2 3 0 ) 就是我们通常所说r s 译码的关键方程，多项式c o ( x ) 称为错误数值多 项式。求解关键方程是r s 码译码的关键，e u c l i d 算法和b m 算法以及它们的改进 算法是应用较多的关键方程的求解算法。 2 5 1e u c l i d 算法 利用附录中所示的e u c l i d 算法得到错误位置多项式盯( x ) 以及错误数值多项式 功( 功以后，我们就可以确定错误图样e ( x ) ，然后确定纠错后的码字 c ( x ) = 尺( x ) - e ( x ) 。 基于e u c l i d 算法的r s 码的时域译码算法可以用以下的伪代码描述【1 0 1 ： 2 qs叉双； 第二章r s 码译码理论 如r ( _ ，= l t 0 2 t ) 墨= ：r ； s ( 工) = s + 曼x + + 最，x 2 卜1 ； i f ( 双x ) = = 0 ) 没有错误： e l s e e u c l i d ( x “, s ( x ) ，厶t 一1 ) ； 盯( 工) = 1 ，( x ) 1 ，( 0 ) ； 缈( z ) = ，- ( z ) v ( o ) ； f o r ( f = 0 t o 刀一1 ) f ( a ( a 叫) = = 0 ) 互= 一缈( 口叫) 盯7 ( 口叫) ； e l s e 互= o ； ) f o r “= 0 t o 刀一1 ) q = 足一互； ) 图2 - 1e u c l i d 算法时域译码 如果错误数目不超过t ，上面的算法会正常运行。但是如果出现了f 个以上的 错误，就可能产生某些问题。例如，程序e u c l i d & , s ( 曲，f ，t 1 ) 可能返回一个多项 式v ( x ) 具有v ( o ) = 0 ，因此导致在计算仃( 曲= v ( x ) v ( o ) 时除数为0 。另外，译码器 的输出： c = ( q ，q ，q 一。)( 2 3 1 ) 可能不是一个码字。因此在这个译码算法的任何实际应用中，必须检测这些非正 常情况。 对基于欧几里德算法的r s 译码总结如下，算法初始化为【1 1 1 ： t i ( x ) = x 缸，t o ( z ) = s ( z ) ( 2 3 2 ) n l ( x ) = 0 ，v o ( 曲= 1 、 7 对第i 次迭代，由下面式子计算出，；( 功和- ( 力： 9 电子科技大学硕士学位论文 ，；( 功= ，；一2 ( z ) 一，；一l ( x ) g ，一l ( 功 一( 工) = v f 一2 ( x ) 一v l ( x ) g 卜l ( z ) 直到i ( z ) 的次数小于t 。 算法通常在t 步以内就完成了，最终我们得到： 仃( j c ) = v ( x ) v ( o ) c o ( x ) = ，( x ) v ( 0 ) 2 5 2m e 算法 ( 2 - 3 3 ) ( 2 - 3 4 ) 在e u c l i d 算法中，由于需要用到除法，因此每次迭代中都需要求有限域元素 的逆。在硬件实现中，连续地求元素的逆将耗费大量资源。可以通过m e 算法来 消除求逆运算。 m e 算法描述如下，首先初始化条件为【1 2 1 ： 删，q ( 工) = s ( x ) 2 委墨( 2 - 3 5 ) 凡( x ) = 0 ，u o ( x ) = 1 第i + 1 次迭代计算如下： 其中， 暑+ 。( x ) = q 6 f 墨( x ) + q 口，q ( x ) 卜妒i o i a ，q ( x ) + q 岛置( 功】 丑+ 。( 功= 【q 包以( 曲+ q 口，肛( x ) 卜一| 【g 口f 肛( 石) + q 包五( x ) 】 q + 。( x ) = qq ：f ( x ) + i 砖( x ) 鸬+ 。( 工) = q 鸬( x ) + 现( x ) = d e g ( r ( 工”一d e g ( q i ( x ) ) 吼= 搿茗 ( 2 3 6 ) ( 2 3 7 ) ( 2 3 8 ) ( 2 3 9 ) ( 2 - 4 0 ) ( 2 - 4 1 ) a i 和岛分别是置( x ) 和q f ( 工) 的最高次项系数。当d e g r ；+ 。( 工) d e g s ( x ) ，那么没有错误产生。这时不需要求解关键 方程，直接得到错误位置多项式盯( 曲= a ( x ) 和错误数值多项式讲功= s ( z ) 。如果 d e g a ( x ) d e g r i ( x ) 时，迭代完毕。得到删除及 错误位置多项式盯( 功= 丑( 功和删除及错误数值多项式缈( x ) = g ( x ) 。 第五步：把( i = l ，2 n 1 ，n ) 代入错误位置多项式盯( 功找出它的根。如果口 是盯( x ) 的根，那么口是错误位置，接收多项式分量，。是错误数据。 第二章r s 码译码理论 第六步：计算错误值： 互一筹( 2 - 6 5 ) 仃l 口l 从而得到错误值多项式e ( x ) 。 第七步：从接收码字中减去错误得到译码后的码字c ( 工) = 尺( 功一e ( x ) 2 9 3d c m e 以及e d c m e 纠删纠错译码算法 前面的d c m e 算法和e d c m e 算法都是用于只纠正错误的情况，需要对它们 进行修改才能适用纠正删除的情况。我们只需要修改算法的初始化条件就行了， 其他地方都不用改动。 虽然d c m e 纠删译码算法在文献【6 】中没有提出来，但是我们可以根据文献 1 7 】 中已有的m e 纠删译码算法推导出d c m e 纠删译码的初始化条件。用d c m e 算法 来求解r s 纠删纠错译码的关键方程的初始化条件需要修改为： 民( x ) = 工。，q 0 ( x ) = 砖( x ) ( 2 - 6 6 ) 气( 功= o ，心( z ) = a ( x ) e d c m e 纠删译码算法在文献【7 】和【8 】中也没有提及，我们也可以根据m e 纠 删译码算法推导出e d c m e 纠删译码的初始化条件。当伴随式的最高次项系数不 为0 时，用e d c m e 算法来求解r s 纠删纠错译码的关键方程的初始化条件变为： r o ( x ) = j r 2 ) ，q o ( x ) = 格( x ) ( 2 6 7 ) 凡( 曲= x a ( x ) ， 心( x ) = 人( x ) 、 。 当伴随式的最高次项系数为0 时，初始化为： r ( 砷= x 卜，q o ( x ) = x 2 s ( 功( 2 - 6 8 ) 厶( 功= o ，p o ( x ) = z 人( 工) 2 10 缩短r s 码的译码 对于6 f ( 2 ”) 上参数为( 以，k ，t ) 的r s 码，它的最小码距d = n - - k + l 。实际中如 果信息符号个数k 7 k ，这时码长以 刀，我们称这种码为缩短的r s 码。可以将缩 短的r s 码表示为仍一s ，k s ，o