《本科毕业设计 - Reed-Solomon》由会员分享，可在线阅读，更多相关《本科毕业设计 - Reed-Solomon（30页珍藏版）》请在金锄头文库上搜索。
1、Reed-Solomon码的 研究与实现指导老师：周学海教授0311PB03206070张雨璞中国科学技术大学 计算机科学与技术系2003级本科毕业设计1本科毕业设计 - RS码的研究与实现主 要 内 容n简 介n基本原理nRS(255, 239)编码器的实现nRS(255, 239)译码器的实现n模拟仿真 n小 结2本科毕业设计 - RS码的研究与实现简 介n里得-所罗门码（Reed-Solomon Code, RS）差错控制领域中一类很重要的纠错码 纠错能力强，能纠正随机错误、突发错误以及二者的 结合nRS码的应用超远距离通信 卫星通信系统，海底通信系统大容量存储 Solid State
2、Mass Memory数字视屏广播 HDTV3本科毕业设计 - RS码的研究与实现基 本 原 理 nRS码的码元取自 GF(2m)GF，伽罗华域n指按域的构成规则构成的有限个元素的集合q=2m个元素为：0, 1, , 2, , q-2，其中q-1=1 GF(2m)中的元素有四种表示方法n这四种表示方法是等价的，而且可以互相转换幂表示矢量表示 多项式表示对数表示 21 0 0z2230 1 1z + 134本科毕业设计 - RS码的研究与实现基 本 原 理 nRS码的参数描述：定义在GF(2m)中的RS(n,k)码，纠错能力为t m 码元取自GF(2m)，每个码元为 m bit n 码长为n个码
3、元k 前k个码元为信息码，后n-k个码元为校验码t t=(n-k)/2即能纠正的t个码元错误即最多可以纠正t*m个bit错误5本科毕业设计 - RS码的研究与实现基 本 原 理 n编码步骤编码公式这样，编码后的码字为 (dk-1,d1,d0,p2t-1,p1,p0)信息码 校检码编码的主要目的就是求出2t位校检码6本科毕业设计 - RS码的研究与实现基 本 原 理 n译码步骤 (1) 伴随式计算判断码元是否有错误(2) 关键方程求解求出(z)和(z) 为下一步计算做准备7本科毕业设计 - RS码的研究与实现基 本 原 理 n译码步骤 (3) 错误位置和错误值计算使用钱氏搜索找到错误位置 用Fo
4、rney公式求每个错误位置的错误值(5) 纠正错误将原码元和错误值相加，得到正确的码元8本科毕业设计 - RS码的研究与实现RS(255,239)编码器的实现 RS编码器是一个由移位寄存器构成的多项式除法电路完成求校检多项式的除法使用Verilog HDL实现9本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n基本情况RS(255,239)译码器是RS(31,19)译码器的扩展nRS(31,19)译码器的源码来自OPENCORE.ORGn使用Verilog HDL实现，已经流水化为什么要扩展？n在与计算机有关的数据传输和存储中，都是以8 bit为单位 nRS(31,19
5、)的码元是5 bit，需要频繁进行5 bit - 8 bit的转换n扩展后适用面更广，效率更高n通过研究扩展的具体方法，可以以此为基础实现任意参数的 RS码编码译码器10本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n总体结构除了controller，每个模块与译码步骤里相对应11本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n扩展实现参数选择n生成多项式n取239, 240, , 254为根，Forney公式 就能简化为n错误位置和错误值计算模块能直接计算出分子和分母部分， 能够快速地算出错误值 12本科毕业设计 - RS码的研究与实现RS
6、(255,239)译码器的实现 n模块修改公共乘法模块 n需要将原来的GF(25)乘法器 扩展成GF(28)乘法器n设两个乘数用多项式表示为n求出P(z) = P1(z) P2(z) mod F(z)，P(z)的系数就是要求的乘 积n同时，P(z)的系数都是P1(z)、P2(z)的系数相乘再相加构成的 ，因此，可以用组合逻辑实现这个乘法器。13本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n模块修改FIFO缓冲模块nRS(255, 239)每个码字有255 bytes，因此，FIFO中的寄存器 需要增加到255个14本科毕业设计 - RS码的研究与实现RS(255,2
7、39)译码器的实现 n模块修改伴随式计算模块 n每个计算单元就是一个变量与一个常数相乘n具体流程q 转换成多项式表示P1(z)设另一个乘数为P2(z)求出P(z) = P1(z) P2(z) mod F(z)n每一步都是多项式相乘和求余运算量非常大n使用Mathematica辅助运算，预先求出P(z)和P1(z)、P2(z)的系数关系，用组合逻辑实现15本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n模块修改关键方程求解模块 n结构图nPE模块内部不用改变n计算模块24个 PE0-PE15为PE模块，初始值是syndval PE16-PE23为PE_16模块，初始值是
8、8b00000000 PE24 为PE_24模块，初始值是8b00000001 16本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n模块修改错误位置和错误值计算模块 n总体结构17本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n模块修改错误位置和错误值计算模块 n关键子模块：inverscomb 求逆元计算量非常大，即使用Mathematica直接调用乘法模块将导致很大的延迟n解决方法：利用GF中运算的封闭性预先将元素及其逆元的对应关系找出计算时只要“查表”就可以了18本科毕业设计 - RS码的研究与实现模 拟 仿 真 n环境 操作系统：Wi
9、ndows XP SP2仿真软件：ModelSim SE 6.0an目的RS(255,239)编码器n编码正确性RS(255,239)译码器n译码的正确性n流水化的正确性19本科毕业设计 - RS码的研究与实现模 拟 仿 真 nRS(255,239)编码器 编码器进行的是GF(28)中的多项式求余运算问题 n计算量非常大，不能手工验证n没有相应的C程序能够验证，Mathematica也不行方法：利用RS码的编码性质进行验证n在求出效验码后，并不立刻停止编码，而是将效验码作为输 入，继续求余n这相当于把求得的余数加在原来的除数上继续作除法n如果结果是0，则表示求余正确(译码正确)，否则表示译码错
10、 误20本科毕业设计 - RS码的研究与实现模 拟 仿 真 nRS(255,239)译码器 译码的正确性n无错n有错，错误数不超过纠错能力 n有错，错误数超过纠错能力 testbench设计n译码器是串行输出的，得到的译码结果无法保留n设计了一个移位寄存器组，接在译码器输出，保存译码结果21本科毕业设计 - RS码的研究与实现模 拟 仿 真 nRS(255,239)译码器 流水化的正确性n读入的码字共3种情况n连续读入两组码字共3*3=9种情况n只要验证连续两次译码的这9种情况就可以了 testbench设计n每次要保存两组码字，增加一个移位寄存器组22本科毕业设计 - RS码的研究与实现小
11、结 n经过长时间的修改和调试，程序最终通过了验证n结合代码分析，按照上面的扩展方法，可以实现 任意参数的RS码的编码器和译码器n很可惜，由于时间的关系，没有能够在开发板上 验证23本科毕业设计 - RS码的研究与实现谢谢！24本科毕业设计 - RS码的研究与实现基 本 原 理 n编码原理把原始数据转换成GF中的元素(信息码元)每k个作为一组信息码(dk-1,d1,d0)，有信息多项式：根据编码需要，得到生成多项式：n在GF(28)中选择连续的2t个元素作为生成多项式的根根据下面公式，求得校检多项式系数就是校检码25本科毕业设计 - RS码的研究与实现基 本 原 理 n译码原理根据收到或读出的码
12、字，得到多项式：伴随式为伴随多项式26本科毕业设计 - RS码的研究与实现基 本 原 理 n译码原理错误位置多项式错误值多项式 (Yi是错误值, Xj = 称为错误位置)关键方程27本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n译码流程读入的码字，从高次开始，依次通过INPUT读入一路传给SC，另一路传给FIFOSC完成计算后，将伴随式的值送往KES28本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n译码流程KES使用改进的Berlekamp Massey算法求解出所有 的值以及部分w(h)的值(用于改进的Forney公式)，送 到CSEE 29本科毕业设计 - RS码的研究与实现RS(255,239)译码器的实现 n译码流程从高次开始，CSEE依次确定该位置是否错误位置， 并求出相应的错误值同时，FIFO也同步输出读入的码字，经过EC的处理( 将原码字和错误值相加)，得到正确的码字30本科毕业设计 - RS码的研究与实现
