（电力电子与电力传动专业论文）基于dvd应用的rs码译码算法优化及其vlsi设计.pdf

a b s t r a c t a b s t r a c t r s r e e d s o l o m o n c o d eh a sb e e nw i d e l ye m p l o y e di nd a t at r a n s m i s s i o na n d s t o r a g es y s t e m so w i n gt oi t se x c e l l e n tc a p a b i l i t yf o rc o r r e c t i n gb u r s te r r o r sa n dr a n d o m e r r o r s b a s e do nt h er e s e a r c ho fr sc o d et h e o r y a n a l y s i so fd v ds p e c i f i c a t i o n a n d o p t i m i z a t i o ni m p r o v e df r o ma l g o r i t h m t h i sp a p e rp r e s e n t saf u l l p r o c e s sp i p e l i n e d e r r o r s a n d e r a s u r e sc o r r e c t i n gr e e d s o l o m o np r o d u c t c o d e r s p c d e c o d e r sc h i pf o r d v da p p l i c a t i o n i tf e a t u r e s f u l l p r o c e s sp i p e l i n e d h i 曲 s p e e dd e c o d i n g h i g h p e r f o r m a n c ec o r r e c t i n g s i m p l e n e s s o fc o n t r o l t i m i n g s u c c i n c t n e s so fc i r c u i t i m p l e m e n t a t i o n a r e ae f f i c i e n t a n dw i t l l g o o de x t e n dc a p a c i t y i tc a nc o r r e c t e r r o r s a n d e r a s u r e si n t r o d u c e di nt h ep r o c e s so fs t o r a g ea n dr e c o v e r yo fd v dd a t aa n d a l s oc a l lb eu s e da sa ni pc o r ei n t h ed e s i g no fd v ds e r v oc h i p t h em a i nm o d u l eo ft h er s p cd e c o d e re l i i pa r et w op i p e l i n e de r r o r s a n d e r a s u r e s c o r r e c t i n gr sd e c o d e r sa n dab l o c kb u f f e rm a n a g e r t h er sd e c o d e rf e a t u r e sa l l a r e a e f f i c i e n tk e ye q u a t i o ns o l v e ru s i n gam o d i f i e de u c l i da l g o r i t h m w h i c hr e d u c e dt h e c o m p l e x i t yo ft h ed e s i g n b a s e do nt h em e t h o d so fm o d u l e sr e u s e t h ep r o p o s e dr s d e c o d e ra r ev e r yr e g u l a ra n da r e ae f f i c i e n t u s i n gt h r e es t a g ep i p e l i n e s t h er sd e c o d e r c a l lo p e r a t ea tar a t eo f1b y t e e l k b a s e do nam e t h o do f2d i m e n s i o nd a t ar e a r r a n g e a h i g hs p e e da n dh i 曲e f f i c i e n c yi m p l e m e n t a t i o no fd r a ma c c e s si sp r o p o s e di nt h e d e s i g no fb l o c kb u f f e rm a n a g e gu s i n gt h eb l o c kb u f f e rm a n a g e rw i t ho f f c h i pd r a m a 18 2 17 2 r o wr sd e c o d e ra n da 2 0 8 18 2 c o l u m nr sd e c o d e rc a nb ep i p e l i n e d w h i c h d o u b l et h es p e e do fr s p cd e c o d e ra n dg e tar a t eo f1b y t e e l k b a s e do nt h ed v ds p e c i f i c a t i o n s t h er s p cd e c o d e rc h i pd e s i g ni sd e f i n e d t h e m a t l a bm o d e lo fr s p ce n c o d e r sa n dd e c o d e ri sp r e s e n t e df o r t h ev e r i f i c a t i o no ft h e a l g o r i t h m t h eh a r d w a r eo fr s p cd e c o d e rc h i pi sd e s c r i b e di nt h ev e r i l o gh d l f u n c t i o ns i m u l a t i o na n dt i m i n gv e r i f i c a t i o na r ep r o c e s s e d a n dt h e ni si m p l e m e n t e di na a l t e r af p g a t h r o u g ht h ef u n c t i o ns i m u l a t i o na n dt i m i n gv e r i f i c a t i o n t h ep r o p o s e d r s p cd e c o d e rm e e tt h ee x p e c t e dp e r f o r m a n c er e q u i r e m e n t w h i c hg e t st h er a t e so fo n e b y t ep e rc l o c k g e t st h em a xr o we r r o rc o r r e c t i n go f5e r r o r so f10e r a s u r e sa n dt h em a x c o l u m ne r r o rc o r r e c t i n go f8e r r o r so r16e r a s u r e s g e t sad a t ar a t e4 0 m b y t e s si n t e r f a c e d w i m10 0 m h zs d rd r a m w h i c hm e e tt h e12 d v dp e r f o r m a n c er e q u i r e m e n t k e y w o r d s r e e d s o l o m o nc o d e m o d i f i e de u c l i da l g o r i t h md e c o d e rv l s l d e s i g n m a t l a b 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果 尽我所知 除了文中特别加以标注和致谢中所罗列的内容以外 论文中不 包含其他人已经发表或撰写过的研究成果 也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意 申请学位论文与资料若有不实之处 本人承担一切相关责任 本人签名 狂菇i 凌 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定 即 研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学 本人保证毕业 离校后 发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学 学 校有权保留送交论文的复印件 允许查阅和借阅论文 学校可以公布论文的全部 或部分内容 可以允许采用影印 缩印或其它复制手段保存论文 保密的论文在 解密后遵守此规定 本学位论文属于保密 在一年解密后适用本授权书 本人签名 导师签名 日期 谚 f 冶 日期 堕 之 第一章绪论 第一章绪论 本章介绍了课题的研究背景 包括课题的来源 纠错码理论及其发展趋势 信 道编解码简介 国内外研究进展 d v d 系统简介以及本课题实现的目标和研究的 意义 最后 给出本论文内容的结构和安排 1 1 课题来源 本课题来源于大连东软股份有限公司 以下简称东软 与日本松下 p a n a s o n i c 株式会社合作的一项d v d v c d c d 外包项目 其中东软公司负责该项目中的伺服 芯片前端代码的设计与验证 本论文的研究即为该伺服芯片研发的一部分 主要 是在研究r s r e e d s o l o m o n 码理论和分析d v d 标准的基础上 给出了一种全 程流水线的纠错纠删r s p c 译码器芯片的设计 该芯片能实现对d v d 存储和读 取中发生的随机和突发错误进行校正 可作为一个p 核用于d v d v c d c d 伺服 控制芯片的设计和实现 1 2 纠错码理论及其发展趋势 在信息的传输和存储中 广泛用到纠错编码和译码技术 这项技术大大提高了 存储设备的性能 使其能广泛地推广和使用 0 1 1 9 4 8 年c e s h a n n o n 在 通信的数学原理 一文中提出了著名的信道编码定 理 开创了纠错码的研究方向 标志着编码理论的开端 纠错码的任务是通过增 加消息冗余度的办法消除在噪声信道下传输消息时所带来的干扰 从而使接收端 能纠正错误 正确译码 自从s h a n n o n 的标志性论文发表以来 纠错码就开始了迅速的发展 在分组码 的理论研究中 r s 码扮演着重要的角色 0 1 r s 码是有限域f q 上的极大距离可 分 m d s m a x i m u md i s t a n c es e p a r a b l e 码 达到s i n g l e t o n 限 从这个意义上讲 r s 码是最佳的 r s 码的一个码字可以看作是某个多项式在一个特定的点集上的 值 r s 码在数据存储 无线通信 卫星通信 宽带调制和数字电视等领域都得到 了广泛的应用 1 3 信道编解码简介 s h 锄o n 信道编码定理告诉我们 1 1 每一类信道都存在着一定的容量c 它代 表信道的极限传输能力 只要实际传输速率r 小于c 就可以在信道中无差错的传 输 但是数字信号在传输过程中 由于信道传输特性的不理想和加性噪声的影响 所接收到的数字信号不可避免的会发生错误 通常 在实际数字通信系统中 为 了在已知信噪比的情况下达到一定的误码比特率 就要使加性干扰尽可能小 以 保证码元误码率在允许的范围内 若不能达到这一要求 就需要采用纠错码 又 称信道编码 的方式来实现通信 信道编码是提高信息传输可靠性 增强抗干扰 能力和降低误码率的一种有效方法 随着纠错编码理论的不断完善和超大规模集成电路 v l s i 的迅猛发展 信 道编码已成功地应用于各种通信系统中 而且在计算机 磁记录和数据存储等方 面得到了日益广泛的应用 信道编码的基本思想是 通过对发送端信息序列做某种变换 使原来彼此独立 相关性极小的信息码元产生某种相关性 在接收端利用这种相关性来检查并纠正 信息码元在信道传输中所发生的差错 信道编码的实现方法是 信息位 校验位 纠错编码 由于校验位本身并不携带 信息 它们的加入必然要降低信息的传输速率 可见 信道编码原则上是以降低 信息传输速率为代价来换取传输可靠性的提高 在差错控制系统中使用的信道编码可以有很多种 按照纠错编码的不同功能 可将其分为检错码 纠错码和纠删码 按照信息码元和附加监督码元的关系可以 分为线性码和非线性码 按照信息码元在编码后是否保持原来的形式不变 可以 分为系统码和非系统码 按照纠正错误的类型不同 可以分为纠正随机错误的编 码和纠正突发错误的编码 按照信息码元和监督码元之间的约束方式不同可划分 为分组码和卷积码 本文所要研究和设计的r e e d s o l o m o n 码是差错控制领域中一类非常重要的线 性码 由于它具有很强的纠正突发错误和随机错误的能力 因而被广泛应用于各 种差错控制系统中 分组码中常见的码包括 汉明码 h a m m i n gc o d e 循环码 c y c l i cc o d e b c h 码 b c hc o d e 格雷码 g o l a yc o d e 等 1 4 国内外研究进展 r e e d s o l o m o n 码 以下简称r s 码 是由i s r e e d 和g s o l o m o n 提出的 在发明r s 码的早期由于没有好的解码算法 对于纠正6 个字节以上的数据传输错 误都显得非常困难 直到1 9 6 7 年 e b e r l e k a m p 提出了一种可以有效实现b c h 和 r s 码的解码算法 它首次使得可以纠正多个字节错误的r s 码的解码成为可能 1 9 6 8 年 m a s s e y 提出了一种等效于线性反馈移位寄存器综合方法的b c h 解码算 法 该方法与b e r l e k a m p 的方法类似 因此该算法现在被称为b e r l e k a m p m a s s e y 第一章绪论 3 b m 算法 b m 算法使得解码复杂度大大降低 1 9 7 5 年 s u g i y a n m a 提出了一 种解关键方程的e u c l i d 算法 该算法有效的解决了b c h r s 和格雷码的解码p 1 随着微电子技术的不断发展 r s 解码算法也在不断改进 使得r s 解码算法 的硬件实现成为现实 从而推动了r s 解码器结构的研究与发展 8 0 年代后期 对r s 编码 解码器的研究达到了高潮 并出现了一些用v l s i 实现的r s 解码器成 功的例子 1 9 8 4 年 l i u 将r s 解码器分成5 个部分 采用流水线的处理结构 使 得r s 2 5 5 2 2 3 解码器地解码速率达到了4 m b i t s 1 9 8 6 年 m a k i 采用了 a s i c 设计 实现了一个r s 2 5 5 2 2 3 解码器 该系统采用了4 片v l s i 来分 别实现解码器各个模块 另加了三块r o m 和一块做缓存的r a m 解码速率高达 8 0 m b i t s l l 1 9 9 4 年c o i l s 利用e d a 综合技术设计出码速为8 0 m b i t s 的r s 2 5 5 2 2 3 译码器 大大提高了设计效率 设计门数为1 0 0 0 0 0 门 工作量为2 人 年 法国m a t r am a r c o n i 公司于上世纪9 0 年代初 研制成功了完全能符合c c s d s 标准的r s 2 5 5 2 2 3 译码器 译码吞吐率为8 0 m b i t s 至1 9 9 7 年 r s 2 5 5 2 2 3 最大的译码吞吐率为略大于8 0 m b i t s u l 2 0 0 1 年 s a r w a t e 等提出了一种改进的b m 译码结构 大大提高了译码速度 并降低了资源消耗 2 0 0 3 年 h a n h o 设计了一 种用于光纤通信的r s 译码器 采用4 个译码模块并联结构 使译码速度达到了 2 6 6 g b s 1 3 1 更高效的解码算法以及大规模集成电路技术的发展使得r s 码在深空通信 移 动通信 军用通信 光纤通信 磁盘阵列以及激光存储等方面得到了广泛的应用 比如r s 2 5 5 2 2 3 已经成为美国航天局和欧洲空间站的深空通信系统中的标准 信道编码 而r s 3 1 1 5 是军用通信中的首选编码 r s 1 8 2 1 7 2 r s 2 0 8 1 9 2 则成为数字视频光盘 d v d 系统的纠错标准 正因为r s 码的应用范围如此的广泛 对于r s 码的编码和解码一直是国内外 通信领域的一个研究热点 本论文所研究讨论的为用于数字视频光盘 d v d 中 的r s 1 8 2 1 7 2 和r s 2 0 8 1 9 2 解码器的v l s i 设计 1 5 1 光存储技术概述 1 5d v d 系统简介 光存储的发展步伐很快 自其问世以来一直保持着强劲的增长趋势 从2 0 世 纪6 0 年代光存储的提出 1 9 7 8 年出现商品化光盘 1 9 9 7 年出现商品化的d v d 播 放器 现在已经发展到了d v d r w 和蓝光光盘的阶段 1 4 1 引 光盘作为一种重要的 存储介质 不仅渗透到各个信息部门 也渗透到人们的生活当中 光存储有两大核心技术 伺服技术和解码技术 由此而产生的两个芯片部分 伺服芯片和解码芯片 伺服芯片负责光盘盘片的转动 使之放置在最合适的位置 通过激光头完成信号读取 并进行相应的解调 纠错和检错处理 解码芯片负责 将读取的信号进行解码处理 将d v d 碟片上的信号重新解压复原 当前伴随着集 成电路向着s o c 方向发展 d v d 关键芯片的功能也逐渐被合并 伺服控制和解码芯 片合并在一起组成了单芯片系统 即由在单个芯片上提供伺服和解码的一体化方 案 掌握相关的知识产权对我国光存储产业的发展具有重大的意义 在光存储领 域 知识产权主要掌握在以6 c 日立 松下 j v c 三菱 东芝 时代华纳 i b m 3 c 飞利浦 索尼 先锋 l c 汤姆逊 杜比 d t s 等的手中 他们以专利许可 的方式向d v d 产业链的生产厂家收取专利费 光存储在诸多方面有着广泛的应用 前景 作为光存储设备的生产和消费大国 掌握自有知识产权的核心技术是我们 发展的目标 积极参与相关标准的制定和研究 对于我们的产业发展意义重大 掌握知识产权是为后续发展铺平道路 1 5 2c d 家族的成长历史 追根溯源 光盘存储技术源自音频领域 随着数字音频技术的发展 相继出现 了很多新型媒介 其中的代表就是数字光盘 c d 光盘家族遍及了多媒体诸多领域 c d 在音乐领域是c d d a 数字激光唱盘 在图像领域是p h o t o c d 相片光盘 和v c d 视频光盘 在计算机领域中是c d r o m 计算机存储光盘 如果依照时间顺序的话 最先于1 9 8 2 年制定了数字音响用的c d d a 规格 其 后 于1 9 8 4 年制定了能利用c d d a 的辅助数据 子码 来重放出简单的静止图 像的c d g 规格 1 9 8 5 年又制定了存储各种数字数据 主要为计算机用 用的 c d r o m 规格 然后又从这个c d r o m 进一步派生出许多新的数字数据光盘规格 1 5 3d v d 应运而生 1 9 9 5 年初 以s o n y p h i l i p s 为代表的m m c d 阵营和以t o s h i b a t i m e s w a r n e r 为代表的s d 阵营分别公布了自己的技术方案 形成了完全不兼容的两种光盘规 格 1 9 9 5 年9 月1 5 日 两大阵营十大公司正式达成d v d 统一的规格协议 同年 1 2 月中旬 国际d v d 联盟在东京正式成立 并公布了统一的标准 针对不同的需 求对d v d 产品制定了5 种不同的标准 1 d v d r o m 只读型d v d 一 只读型d v d 光盘属于计算机数据存储只读 光盘 用途类似c d r o m 相应得硬件为d v d r o m 驱动器或d v d v p c 装置 第一章绪论 5 d v d v i d e o 影音d v d 一影音d v d 光盘属于视频存储光盘 简称d v d 视盘或者d v d 影碟 用途类似l d 或者v c d 相应的硬件称作d v d v 播 放器或d v d 影碟机 d v d a u d i o 音乐d v d 音乐d v d 光盘属于音频存储光盘 用途类 似音乐c d 相应的硬件是d v d a 播放机或d v d 放音机 d v d r 一次可写型d v d 一d v d r 属于限写一次的光盘 用途类似 于c d r 相应的硬件是d v d r 驱动器或者刻录机 d v d r a m 可重复读写型d v d d v d r a m 光盘属于可多次读写的 光盘 d v d 和c d 相比较 最大的优点就是容量大 清晰度高 1 5 4d v d 解码伺服芯片简介 d v d 系统中的主要芯片是伺服芯片和m p e g 解码芯片 伺服芯片主要负责光 盘盘片的转动 使之放置在最合适的位置 通过激光头完成信号读取 并进行相 应的解调 纠错 检错处理 解码芯片负责将读取的信号进行解码处理 将d v d 碟片上的信号重新解压复原 本设计所涉及到的r s 码的解码器主要包含在信道解 码部分 图1 1 是信道解码部分的系统框图 图1 1 信道解码系统框图 虚线以上的部分为写通道 用于刻录机 直线以下部分为读通道 用于d v d 播放器 d v d r o m 等 可见在读通道中 c d 主要包括以下几个部分 2 3 4 5 1 s u m v g a l p f 以及r fa d c 和d p l l 主要完成模拟信号到数字信号的 转化和数字信号的预处理 2 对于c d 来说 接下来的是e f m 解调 d v d 是e f m 解调 e f m 是e i g h t t of o u r t e e nm o d u l a t i o n 的简称 3 c 1 c 2 解调 4 l a y e r e c c 解调 5 通过b u f f e rm a n a g e r 送往h o s t 端 d v d 主要包括以下几个部分 1 s u m v g a l p f 以及r fa d c 和d p l l 主要完成模拟信号到数字信号的 转化和数字信号的预处理 2 e f m 解调 3 e c c 解调 4 通过b u f f e rm a n a g e r 送往h o s t 端 1 6 论文的研究内容及其安排 第一章为引言部分 介绍了课题的研究背景 包括课题的来源 纠错码理论及 其发展趋势 信道编解码简介 国内外研究进展 d v d 系统简介以及本课题实现 的目标和研究的意义 最后 给出本论文内容的结构和安排 第二章是纠错码基本理论 简要介绍了r s 译码所需的相关数学知识 其中主 要是有限域的基本数学知识及基本的编解码理论 第三章是r s 码在d v d 纠错控制中的应用 在对d v d 标准 d v ds p e c i f i c a t i o n 分析的基础上 对d v d 数据纠错码和r s p c 的编译码的原理进行进一步的研究 最后给出本文实现r s p c 译码的实现方案 包括采用的译码算法 v l s i 结构 流 水线的实现和时序控制等 第四章是r s 码及其编译码算法的硬件设计 主要介绍了r s 译码器各个组成模 块的硬件实现电路 其中包括本文对核心算法硬件结构提出的改进方案 为后续 的v l s i 实现奠定基础 第五章是r s p c 编译码器的m a t l a b 模型 在第二三四章给出r s 编译码和r s p c 编译码算法的基础上 给出应用于d v d 数据纠错的r s p c 编译码器m a t l a b 模型的设 计和实现 为后面的r s p c 译码器芯片的v l s i 设计与验证准备了参照条件和测试 数据 第六章是r s p c 译码器芯片的v l s i 设计 介绍采用t o p d o w n 的设计流 程 设计了全程流水线结构的纠错纠删r s p c 译码器芯片的设计 该设计分成纠错 纠删行r s 1 8 2 1 7 2 译码器 纠错纠删y t j r s 2 0 8 1 9 2 译码器和块缓冲管理器的设计 第一章绪论 7 然后在此基础之上的整体 t o p 的设计 第七章是总结 主要对全文进行总结和进一步研究的展望 第二章纠错码基本理论 本章简要介绍了r s 译码所需的相关数学知识 其中主要是有限域和编解码理 论的基本数学知识 为后续电路设计做准备 2 1 有限域 g a l o i a s 域 基本概念及重要结论 有限域 g a l o i a s 就是域中元素的个数是有限的 元素的个数称为域的阶 g 阶 有限域用g f q 表示 如果g 为一个素数 则集合 o 1 2 q 一1 在模q 加法和乘法 下 构成一个q 阶有限域g f q 有限域在编码理论中具有重要的地位 下面给出 g a l o i a s 域的几个基本概念和重要结论 i 定义1 在域g f q 中 满足n e 0 的最小正整数n 称为域的特征 e 为域的单 位元 定义2 以g 为特征的域是g f q 扰 1 2 称g f q 是g f q 的基域 g f q m 为g f q 的扩域 域中一切非零元素的特征都等于域的特征 且域的特征一定为素数 非零元素 构成的乘法群的阶定义为域中该元素的级 若口为域g f q 中的n 级元素 则称口 为n 次单位原根 若某一元素口的级为g 一1 则称a 为本原域元素 域的特征表明 了域中加法运算的循环性 而域的级则表明了域中乘法运算的循环性 下面给出几个有限域的重要结论 定理l 有限域g f q 中的g 一1 个非零元素构成一个循环群 它其中至少有一 个本原元 它的其它元素分别由这个本原元的 次幂构成 j o 1 g 一2 定理2 在g f q 中 每一个非零元素均满足x p l 1 0 定理3 在特征为g 的域中 恒有 一a q x q a q 式中 a 是域中的任一元 素 推论3 1 在g 特征域中 任一元素的级均不是g 的倍数 特别的 在g f q 中 本原域元素的级是g 一1 而其它所有元素的级必为g 一1 的因子 推论3 2 对g f q 上的任何元素0 3 恒有国矿 该推论就是著名的费尔马 f e r m a t 定理 定理4q 特征域中 元素为域整数的充要条件是 该元素是方程护一x 0 的 根 第二章纠错码基本理论 9 2 2 有限域上的多项式 有限域g f q 上的n 次多项式定义为 f x f n x 以q x 1 f x f o z g f q f o l 2 以 2 1 定理5 给定任一两个多项式厂 石 g x 为g f q 上的多项式 一定存在有唯一 的多项式q x 和 x 使得 f x q x g x r 工 0 a or x a g x 或r x 0 2 2 定义3 设f x 是次数大于零的多项式 如果除了常数和常数本省的乘积以外 再不能被域g f q 上的其它多项式除尽 则称f x 为域g f q 上的既约多项式 定理6 每一个首一多项式f x 必可分解为首一既约多项式之积 并且当不考 虑因式的顺序时 这种分解是唯一的 即 f x p 1 工 mp 2 工 4 2 p f x 2 3 式中 p x 为首一既约多项式 a 是某一正整数 f 1 2 j 定义4 若 厂 x g 工 七 z 是同时除尽多项式厂 x g x k x 的次数最高 的首一多项式 则称 厂 x g x 尼 x 是厂 x g x k x 的最大公因式 用 厂 z g x 后 x 表示之 定理7 多项式的欧几里德算法 厂 x g x 彳 x 厂 x 召 x g 功 2 4 式中 0 c o o 彳 功 c o g x 一ao 厂 功 g x 0 a o t k x a o f x 一ao x g x 定义5 若g f q 上的多项式口 x b x 被同一多项式f x 除时 有相同的余 式 a x q l z 厂 x r x b x q 2 x 厂 x x 0 a r x 0 次首一多项式f x 在域g f q 上既约 则由模f x 所组成的 多项式剩余类环是一个有g 个元素的有限域a f q 定理9 设f x 为g f q 上的多项式 若g 特征域的元素国是方程f x 0 的 根 则对于一切自然数n c o q 也必是f x 的根 定义6 满足q 兰1 m o d 刀 的最小正整数聊 称为g 对模以的方次数 定义7 若 g f q 且为g f q 上多项式f x 的根 则由推论3 2 知 国 c o 故 o p o p 2 z l p 1 必为f x 的m 个互不相同的根 这m 个互不相同 的根称为厂 工 的共轭根系 定义8 系数取自g f q 上 且以国 g f q 为根的所有首一多项式中 必有 一个次数最低的 称它为c o 的最小多项式 定理1 0 在口特征有限域中的每一个元素c o 皆存在有唯一的最小多项式 记 为r e x 则它具有如下性质 1 r e x 在g f q 域上既约 2 若f x 也是缈 国p 国p 缈p 1 上的多项式 且f c o 0 则m x if x 定理1 1 设国为g 特征有限域国 g f q 中的n 级元素 而m 是g 关于模n 的 方次数 则c o 的最小多项式肌 x 是m 次多项式 且 m i m x 几 x o 2 7 面 推论1 1 1 共轭根系内的每个元素国 国p 国 c o p 1 的最小多项式均相同 定义9 元素国的最小多项式的次数为国的元素的次数 称c o 为m 次域元素 定义1 0 系数取自g f q 上的以g f q 中本原域元素为根的最小多项式 称 为本原多项式 定理1 2 若彩是g 特征有限域f 上的m 次域元素 则g f q 上的次数小于m 的 国的多项式的全体构成域f 上的q 阶子域 由于有限域的阶必是其特征的幂 而有限域的特征必是素数g 的幂g 因此 若有以素数g 则一定可以从g f q 的多项式中选出一个m 次的既约多项式p x 以它构造出一个g 阶有限域g f q 并且该域包含了g f q 上所有m 次的既约多 项式的全部根 如果把p x 的一个根称为a 则由定理1 2 可把g 阶有限域中的 每一个元素 表示成系数在g f q 上且次数低于m 的口多项式 而g f q 上次数小 于m 的多项式与g f q 的m 重同构 因此 m 重 多项式剩余类环以及a 多项式 之间均同构 都可以用来表示g 阶有限域 2 3 g f q 有限域的基 定义1 1g f q 中的q 1 个非零元素 均可用本原多项式的根口多项式表 示 此时 1 口 口 一1 就是域的一组自然基底或本原基底 也称多项式基 定义1 2 口为g f q m 中的本原域元素 定义k 口p 口p 2 口p m i 为卯 g 域 第二章纠错码基本理论 的正规基底 正规基底其实就是以口为根的本原多项式f x 的共轭根系 值得注意的是并 不是每个本原多项式的共轭根系都能作为正规基 这是由于作为一组基底元素 它们之间必须是线性无关的 下面给出一个本原多项式的共轭根系不是正规基的 例子 设口是g f 2 3 中的本原元 它是本原多项式厂 z x 3 z 1 的根 则它的 共轭根系是缸 a 2 a 4 但它们不能作为g f 2 3 的正规基 因为 口 口2 口4 口 口2 a a 2 0 即这3 个元素线性相关 可喜的是 已经证明 了除了少数次数之外都存在有任意次数的g f q 上的本原多项式 它们的共轭根系 是一组正规基 在域的运算和研究中 迹是非常有用的分析工具 下面给出迹的概念和性质 定义1 3a g f q 则它在g f q 上的迹定义为 口 口 口9 口9 2 口矿 1 2 8 其中g 为素数或素数幂 对于所有口 g f q 迹具有如下性质 z g f q r a z 口 z z a a z r r 兄 g f q z 9 z 迹把g f q 中元素映射到g f q 中 定理1 3 当且仅当有一个元素 g f q 使得口 一 9 则z 0 定义1 4 与g f q 的基底b p o 屈 凡一 相对应 若 抛 传篡坶 协9 成立 则称g f q 的基底b i y l 一 y 州 是b 的对偶基 如果b b 则 称b 为自对偶基 2 4 循环码 循环码是一类最重要的线性码 它具有严格的代数结构 其性能易于分析 目 前已发现的大部分线性分组码均与循环码有密切联系 它们之中的大部分都可归 结于循环码的范畴 并且循环码具有循环特性 其编译码电路 特别是编码电路 易于实现 基于这些特征 循环码特别引人注目 对它的研究也比较深入和系统 循环码的定义 设有一个n 重的k 维子空间圪 圪 若对其中任意一个 v a n l 口脚 a o 圪 恒有h a n 2 口 3 a o a 1 圪 t 则称圪 为循环子 空间或循环码 域g f q 上的多项式和它上的 z 重之间是一一对应的 在 刀 k 循环码中 码字 a n i 口帕 a o 的多项式表示为a x a n i x 1 口神x 2 口1 x a o a g f q 它的循环移位一次后所得的码字多项式 a l x a n 2 x 2 口 3 工棚 x a 川 相当于乘以x 后 用x 4 一l 取模 x a x a n 1 x 4 a n 2 x 一1 a l x 2 口o z a n 2 x 一1 口o x a 一1 r o o dx 1 2 1 0 即循环码可以用模x 一1 的多项式表示 域g f q q 为素数或素数的幂 上的 刀 k 循环码中 存在有唯一的以一尼次 首一多项式g x x 柑 g n k i x g l x g o 每一码多项式都是g x 的倍式 且每一个次数小于等于 n k 的g x 的倍式一定是码多项式 g x 称为码的生成 多项式 它是 k 循环码中唯一的以一k 次多项式 g x 一定是x 1 的因式 要 找一个k 维循环码 就是找一个能除尽x 一1 的n k 次首一多项式g x 可由此多 项式生成该循环码 因为每一个码多项式都是g x 的倍式 因此g x 的根必是所有码字多项式的 根 基于这点 循环码可以用生成多项式的根来定义 通常情况下 g x 有重根 时 生成的循环码比无重根时生成的要差 这里讨论无重根的情况 由于g x 10 一1 故如果x 一1 无重根 则可保证g x 无重根 下面给出一 个x 一1 无重根的充要条件 定理1 4 在g f q 上 多项式x 一1 无重根的充要条件是n 与g 的最大公约数为 1 若g x 无重根 则必可以在g f q 的扩域g f q 小 上完全分解 g x x 9 1 x 一口2 x 一口 a f 口 f j 1 2 2 1 1 其中 a c f q n k 因此每一个码多项式c x 也必以a 1 口2 a 为 根 设码字多项式为 c z c n 1 x 1 c 一2 x 一2 c l x c o 2 1 2 则 c a f c n 1 a i 一1 c 一2 口f 一2 c 1 口j c o 0 i 1 2 2 1 3 可表示成矩阵形式 第二章纠错码基本理论 1 3 a p a 1 口 1 a 1 1 口2 1 1 口 1 c n 1 c n 一2 q c 0 2 5b c h 码 0 2 1 4 自1 9 5 0 年汉明发表了纠正单个错误的码以来 几乎过了1 0 年的时间 才于 1 9 5 9 年由霍昆格姆 h o e q u e n g h 锄 1 9 6 0 年由博斯 b o s e 和雷 查得胡里 f r a y c h a u d h u r i 分别提出了纠正多个随机错误的循环码 b c h 码的构造方法 b c h 码是目前所发现的一类很好的线性纠错码类 它的纠错能力很强 特别是在 短和中等码长下 其性能接近理论值 并且构造方便 编码简单 特别是它具有 严格的代数结构 因此它在编码理论只能够起着重要的作用 b c h 码是迄今为止 研究的最为详尽 分析的最为透彻 取得成果也最多的码类之一 1 9 6 0 年彼得逊 p e t e r s o n 从理论上解决了二迸制b c h 码的译码算法 奠定了 b c h 码译码的理论基础 稍后 格林斯士日 g o r e n s t e n 和齐勒尔 z i e r l e r 把它推广到 多进制 从实际上解决了b c h 码的译码问题 i b c h 码的定义 给定任一有限域g f q 及其扩域g f q 其中g 为素数或素 数的幂 m 为某一正整数 若码元取自g f q 上的一循环码 它的生成多项式g x 的根集合尺中含有以下万一1 个连续根 r 2 仁j 1 0 口 l a m o 柑之 2 1 5 时 则由g x 生成的循环码称为g 进制b c h 码 其中 a g f q 是域中的n 级 元素 a m o g f q 0 f 万一2 m 是任意正整数 如果生成多项式g x 的 根中 有一个g f q 域中的本原域元素 则n q 一l 称这种码长n q 1 的 b c h 码为本原b c h 码 否则 称为非本原b c h 码 g f q 中元素的级一定是 g 卅一1 的因子 2 6r s 码 r s 码是一类有很强纠错能力的码 是二进制b c h 码的多进制推广 也是一种 典型的代数几何码 它首先由里得 r e e d 和所罗蒙 s o l o m o n 应用m s 多项式 于1 9 6 0 年构造出来的 所以称为r e e d s o l o m o n 码 简称r s 码 r s 码通常在信 道编码中作为外码与其它编码方式一起构成整个信道编码 从而获得所需的编码 增益 以满足通信系统信息传输所需的误码率 内码可以采用t c m g 习格编码调 制 卷积码或t u r b o 码等编码方式 r s 码定义 g f q q 2 上 码长n q 1 的本原b c h 码称为r s 码 r s 码 是符号域和根域相一致的b c h 码 长为n q 一1 设计距离为万的r s 码 生成多项式 g x x a a r a o 1 x a 卅0 2 2 1 6 其中m 是任意正整数 口为g f q 上的本原域元素 由此生成了一个g 进制的 k 一1 q 一8 g s 码 有最小距离万 r s 码最小距离等于校验元的个数加1 所以也 称r s 码为极大最小距离可分码 简称m d s 码 任何一个g f q 上的 l k r s 码 对任何k 个符号位置 将只有一个与这个位置内g 中符号组合之一相对应的码字 2 一 r s 码可以表示为r s n k 每个符号是s 比特 这就表明r s 编码器每次取k 个 符号 然后产生校验符号 最后生成n 个符号的码字 码字中每个符号是s 比特 图2 1 是一个典型的r s 码 图2 1 典型r s 码 给定的符号长度s 最大的码字长度n 是n 2 5 1 r s 码可以被缩短 方法是 在发送端把一些为0 的码字去掉 不发送 而在 接收端再把为0 的码字插入到接收到的码字中 第三章r s 码在d v d 纠错控制中的应用 1 5 第三章r s 码在d v d 纠错控制中的应用 在东芝 日立等公司于1 9 9 6 年制定的d v d 标准 d v ds p e c i f i c a t i o n 中 推荐 采用里得 所罗门乘积码 r s p c r e e d s o l o m o np r o d u c t c o d e 作为d v d 数据纠错 的纠错码 因此实现d v d v c d c d 伺服芯片的设计就必须了解和分析标准提出的 纠错算法 选取合适的电路结构和算法实现纠错控制 本章在分析d v d 标准的基础上 叙述了d v d 数据纠错控制码r s p c 的编 译码原理并在此基础上给出本文实现r s p c 译码器芯片的实现方案 其中包括采 用的译码算法 v l s i 结构 流水线的实现和时序控制等 3 1d v d 标准及其纠错码 在1 9 9 6 年由东芝 日立等公司制定并不断改进和推出更新版本的d v d 标准 可分为物理规范 文件规范 视频 音频规范等 在d v d 标准的物理规范 p h y s i c a l s p e c i f i c a t i o n s 中 规定采用里得一所罗门乘积码 r s p c r e e d s o l o m o n p r o d u c t c o d e 作为d v d 数据的纠错控制码 图3 1 是d v d r 的标准架构 p a r t1 翻粥i c a ls 王吧c 刁 c a l o n sv 旺 1 0 4 掺 谚 v e t i 0 彰铌睁繇 酝i p a r t2 f 罡s y s l 卫ms p e c i f l c a 西 a k sv e f 1 0 4m i o 薹豢i 绻i 臻篆黪 一 p a r t3 v e os p e c 蕊c a o n sv e r 1 1 3 t r e f e r e n c ei n f o r m a t i o n j a c k e tp i c t u r ef o r m a t 酾落 嚣 v e r 1 1 1 o 蠹酝黪潺檄 1 0 l 滋麟 v e r 1 o r e f e r e n c ei n f o r m a t i o n i e c 9 5 8t o c o n v e y i 1 0 1 1 p c me a c o d e da u d i ob i t s t r e