一种高效RS编解码器的FPGA实现

一种高效RS编解码器的FPGA实现

文章编号：１００２－８６９２（２００8）12-0032-03

一种高效RS编解码器的FPGA实现

李晓飞，牟崧友

（南京邮电大学通信与信息工程学院，江苏南京210003）

【摘

实用技术··

要】提出了一种实现复杂度低、高效率的RS（204，188）编解码器的FPGA实现电路。整个FPGA设计分为RS编码器、Horner

准则的伴随式计算、改进的BM算法、Chien搜索求根和Forney算法求差错幅值等5个模块，同时，总体电路采用了pipeline结构，有效提高了译码速率。选用Xilinx公司的Spartan3E系列XC3S500E芯片，译码时延242个时钟周期，使用FPGA资源186000门，译码性能与理论值一致，已用于特定无线图像传输系统。

【关键词】Reed-Solomon码；现场可编程门阵列；改进BM算法；Chien搜索；Forney算法【中图分类号】TN762

【文献标识码】A

ImplementationofHighEfficiencyRSCodecBasedonFPGA

LIXiao-fei，MUSong-you

（CollegeofTelecommunicationandInformationEngineering，NanjingUniversityofPostsandTelecommunication，Nanjing210003，China)

【Abstract】AlowcomplexityandhighefficiencyFPGAcircuitofRS（204，188)encoderanddecoderisputforward.Thedesign

ispidedintofivemodules:RSencodermodule，Hornercriteriawithcomputingmodule，animprovedalgorithmoftheBMmodule，Chiensearchrootingmodule,Forneyalgorithmforerroramplitudemodule.Atthesametime，thewholecircuitusesapipelinestructuretoraisetherateofdecodingeffectively.ThedesignisimplementedonXC3S500EchipsofXilinxSpartan3Efamily，with242clockcyclesofdecodingdelay，andusing186000gates.Thedecodingperformanceagreeswiththetheoreticalvalueandithasalreadyusedinaspecialwirelessimagetransmissionsystem.

【Keywords】Reed-Solomoncode;FPGA;improvedBMalgorithm;Chiensearch;Forneyalgorithm

1

引言

RS纠错编码因其突出的纠错能力，已经在太空通

式2t个连续幂次根，在DVB中通常取m0=0，即码生成多项式为

信、数字电视传输以及无线图像系统等许多领域得到广泛应用，其纠错能力达到了分组纠错码的极限，其译码器主要有频域译码器和时域译码器两类。时域译码器结构比较简洁，控制逻辑和运算逻辑比频域译码器少得多，但需要的存储单元比较多。目前主流FPGA都有丰富的存储资源，为了提高译码速度，进一步简化逻辑，本设计中的时域译码器采用了流水线结构，并且在RS译码器的每个模块采用了高效算法，使译码器变得快速简单，已实际用于特定无线图像传输系统中。

g（x）=（x-α0）（x-α1）...（x-at-1）=

an-kxn-k+an-k-1xn-k-1+…+a1x+a0

式（1）中：ai（i=0，1，...，n-k）∈{0，1，α，α2，…，αq-2}。

（1）

RS（204，188）是RS（255，239）的缩短码。在RS（255，239）中，m=8，码长n=28-1=255byte，信息位k=239byte，校验位n-k=16byte，它可纠正t=8byte的随机性或突发性错误。

RS编码电路的主要部分是一组线性反馈移位寄存器，如图1所示。根据码生成多项式P（x）=x8+x4+x3+x2+

2RS编码器原理及实现

RS（n，k）码是q进制BCH码，每个码元取值于q元

1和域生成多项式g（x）=（x-α0）（x-α2）...（x-α15），经计算后得出每一级的反馈系数，其中α0，α1，…，α254到十进制数的映射[1]

符号集{0，α0，α1，…，αq-2}，通常取q=2m，使q元符号集的所有非零元素是基于某个m次域生成多项式（本原多项式）的GF（2m）扩域的元素。RS码具有如下参数：码长为

g（x）=（x-α0）（x-α2）...（x-α15）=

x16+g（15）x15+g（14）x14+…g（1）x+g（0）

（2）

n=q-1，信息位为k，纠错能力是t，校验位为n-k=2t，最小距离为dmin=2t+1，码字的符号取值域与g（x）的根所在域相同，均在GF（2m）上。α，α

m0

m0+1

m0+2t-1

3RS译码器原理及实现

RS的时域译码可分为4步[2-3]：1）由接收到的码组计算伴随式；2）求解关键方程；3）计算错误位置和错误样值；4）错误校正及码字输出。RS译码的关键在于求解

，…，α是码生成多项

电视技术

２００8年第32期（总第322期）

一种高效RS编解码器的FPGA实现

BCH/RS关键方程为Ω（x）=Λ（x）S（x）（modx2t），又可推出Λ（x）S（x）=O[mod（1-xn）][5]，从而通过改进的

BM算法求解Λ（x）S（x）=O[mod（1-xn）]，得到错误位置多项式Λ（x）。迭代算法如下：

1）初始化：Λ（0）（x）=1，T（0）（x）=1，L（0）=0，γ（0）=0，k=0。

2）进行以下的循环迭代，直到k=16。

图1

RS（204，188）编码器

L（k）

关键方程，得到错误位置多项式。译码器如图2所示，其Δ（k+1）=ΣΛ（k）jSk-j

（4）j=0

中R（x）为接收码字的多项式，C（x）为发送端码字的多项Λ（k+1）（x）=γ（k）Λ（k）（x）-Δ（k+1）T（k）（x）x（5）

式，E（x）为差错图样，S（x）为伴随式，Λ（x）为错误位置多若Δ（k+1）≠0且2L（k）≤k，T（k）（x）=Λ（k）（x），否则，T（k）（x）=项式，S为S（x）系数矩阵，Λ为Λ（x）系数矩阵。

xT（k）（x）；

错误若Δ（k+1）≠0且2L（k）≤k，L（k+1）（x）伴

位置

随S（x）解Λ（x）=K+1-L，否则，L（k+1）=

CheinR（x）=C（x）+E（x）

关搜索

错

L（k）；

式键误计方

校C（x）若Δ（k+1）≠0且2L（k）≤k，γ（k+1）=Δ（k+1），否则，γ（k+1）=γ（k）；

算

程Λ（x）

错误Forney样值

正

k=k+1。

S（x）

搜索

算法中Δ是Λ与S的卷积求和运算。采用FIR滤波FIFO缓存

器技术实现流水线处理。初始化时，所有的寄存器置0，图2RS（204，188）译码器框图

然后每个时钟周期，依次将S1，S2，…，Si，…，S2t移入移位寄存器。滤波器系数Λi也在每个时钟周期更新一次，如3.1伴随式计算模块

图4所示。

RS码的校验矩阵如下[4]

1α1α2…αn-1 1α2（α2）2…（α2）n-1

H=

…

…

…

…

（3）

…

1α2t（α2t）2…（α2t）n-1

Δ

伴随式为S=[S1，S2，…，Si，…，S2t]=[R0，R1，…，Rn-1]×HT，图4用FIR滤波器计算Δ电路

采用高效算法———Horner准则，即嵌套的乘累加运算来3.3Chien搜索模块

计算伴随式，伴随式可等效为

改进的BM算法中错误位置多项式Λ（x）=kΠ（1-

S（b0+j-1）

（b0+j-1）

（b0+j-1）

j=（（…（Rn-1α+Rn-2）α+Rn-3）α+

αix），其中，k为非零常数，i∈{i:Ei≠0}，Ei为E（x）的系数。…+R+j-1）

+R通过将有限域元素的倒数（即Λ（x）的根）代入错误位置1）α

（b00

式中：b多项式，就可以找到错误所在的位置，这就是Chien搜索0=0，表示初始化时，所有寄存器置0。

图3是等效伴随式的实现电路，经过204个时钟周的原理。具体做法是：将有限域元素α-（n-1），α-（n-2），…，α-1，1期，接收完所有的204 …… 此处隐藏：5397字，全部文档内容请下载后查看。喜欢就下载吧 ……