一种适用于DVB系统的低复杂度Reed-Solomon解码器

摘　要:提出了一种适用于DVB(DigitalVideoBroadcasting)系统的低复杂度Reed-Solomon解码器结构.在解码器的设计中充分利用了DVB系统提供的高倍率时钟,提高了核心算法模块的计算速度,优化了解码器的流水线结构,有效减小了芯片面积.解码器用SMIC0.25μm工艺综合后规模为31000门.

关键词:RS解码器;ModifiedEuclidean算法;流水线结构;高倍率时钟　　

Reed-Solomon码作为BCH码的一个重要的子类———q进制BCH码,在数字通信,多媒体系统与数据存储系统中有着广泛的应用.RS码有许多独特的优点:首先,RS码作为一种MDC(MaximumDistanceCode)码,其纠错能力已经发挥到极限;其次,RS码具有成熟的硬判决译码算法,适用于许多需要长码的场合,如DVB2C/T (Digital Vedio Broadcasting-Cableapplication/ Terrestrial application)系统;其三,RS码和数据交织技术相结合后在纠突发错方面也可获得优异的性能,这使得RS码在20世纪80年代起就成为实际应用中线性分组码的主流.DVB2C/T系统采用了规格为(204,188)的Reed-Solomon码为传输的视频信号进行纠错保护.由于数字电视解调器芯片的数据吞吐率一般在几到几十Mbps之间,对速度的要求不高,所以设计时重点考虑减少芯片复杂度,同时兼顾一定的速度.

1 RS解码器算法

RS解码器算法主要分时域和频域两大类,频域解码算法由于需要额外的错误值变换模块,反变换模块和伴随式延迟模块,所以芯片功耗和面积要比时域解码大.时域解码算法中,根据解错误位置多项式的不同方法,主要可分为Berlekamp-Messy和ModifiedEu-clidean两种方法.后者由于基于迭代和寄存器复用等技术可以大大缩小电路的规模,并且有利于高速硬件的实现.

下面以DVB-C/T系统为例,给出基于Modified Euclidean方法的RS时域解码算法.考虑定义在有限域GF(2⁸)上的(204,188)型Reed-Solomon码,其信息位长度为188,码长为204,纠错能力为8,码生成多项式为

解码器的系统框图如图1所示(见第2页).解码步骤如下.

① 由接收码矢ri(0≤i≤n-1)计算伴随式

其中

②用改进的Euclid算法计算错误位置多项式σ(x)和错误估值多项式ω(x).

③由Chien搜索电路计算σ(α_-i),ω(α^-i)和σodd(α^-i)的值,(i=0,1,2,.,n),其中σ(x)的根将指示出错误位置i.

④根据Forney算法对错误位置计算错误值

⑤将错误值和存储在FIFO中的接收码矢相加后得到纠错后的正确码矢,同时进行纠错结果的各项统计,如统计纠错个数,检查是否有不可纠回的错误等.

2 解码器的硬件结构

根据图1所示的RS解码器框图,介绍其中主要模块的硬件实现结构.

2.1 伴随式模块的VLSI实现

由接收码矢计算伴随式主要通过(1)式进行,(1)式可以改写成利于电路实现的迭代形式,

这一迭代计算过程可以由图2所示的简单电路结构实现,耗时204个系统时钟周期.

电路中寄存器为8位并行,加法器满足模二运算法则,乘法器满足域GF(28)的运算规则,本文采用了并行的Mastro-vito乘法器结构.

2.2 Modified Euclidean算法模块的VLSI实现

Modified Euclidean算法模块主要是根据两组多项式的次数、最高次项系数等条件对其进行迭代运算最终求出σ(x),ω(x)以及σ_odd(x).

硬件实现时可用两组8位寄存器R₀～R₁₆,Q₀～Q₁₆和L₀～L₁₆,U₀～U16分别来存放多项式的系数,配合相应的控制电路就可以完成ME算法.

图3(a)是MEA模块的直接实现结构(由于两组寄存器的对称性,只列出了其中一组).初始时,按(2)式为寄存器组置入初值,迭代过程中寄存器的值通过CU模块更新后循环右移,Degree Computation模块计算出每次迭代所需要的li值及Swap,Stop等控制信号.图3(b)列出了控制MEA模块迭代过程的状态机.

直接实现结构的缺点是解码速度比较慢,因为完成寄存器组的移位更新需要较多的时钟周期,分组并行结构可在一定程度上提高解码速度,但把寄存器链分组后会增加控制逻辑的复杂度和芯片面积.本文的解决方案是让直接实现结构工作在4倍系统时钟下,既可提高解码速度又不增加控制逻辑的负担.不同实现方案的比较列于表1,表中bclk代表1倍波特率的时钟,即系统时钟.

表1　不同MEA实现方案对性能的影响

2.3 Chien搜索模块的VLSI实现

Chien搜索电路是在MEA模块得到错误值多项式和错误位置多项式后找出根的位置也就是错误位置,电路如图4所示。

图4的Chien搜索电路,采用了ω(α^-i)和σ(α^-i)分开计算的方案,对于DVB2C/T系统中的(204,188)型RS码,通常情况下搜索一帧数据和统计纠错结果各需要204个系统时钟周期,这样就需要一级额外的流水线和FIFO2缓存,但如果Chien搜索模块也采用4倍系统时钟,完成对一帧数据的搜索和纠错结果统计只要51个系统时钟周期,就能把MEA模块和Chien搜索及纠错结果统计在流水线同一级内完成,不再需要FIFO2,可大大缩小解码器内的存储器面积.

2.4 错误值计算和纠正模块的VLSI实现

该模块主要是根据Chien搜索的结果计算出每个出错位置的错误值,并和经过FIFO1延时的原始数据序列异或后得到正确的结果.对错误位置i计算错误值的公式如(3)式,亦称为Forney算法,求逆电路在实现时采用了基于复合域的并行求逆电路,此处不再赘述.

3 流水线结构的优化

先解释一下流水线中用到的各个操作步骤.S1伴随式计算;S2用MEA算法求解错误位置和错误值多项式;S3Chien搜索求错误位置;S4Forney算法求错误值;S5　FIFO1的延时;S6　纠错结果统计,检查是否纠错失败;S7　FIFO2的延时.

图5为优化前后的解码器流水线结构,每一级中各步骤的延迟列于表2.

可以看出,优化前解码器采用了3级流水线的结构,每级长为204周期.这种结构的缺点如下:①流水线过长导致解码器内的memory太大,面积和功耗也随之上升;②因为(204,188)RS码是(255,239)RS码的截短码,纠错结果统计时为了在204周期处理完一帧数据,需为MEA模块输出的ω(x),σ(x)多项式的每个系数乘一个常数,多使用了32个GF(2⁸)上的常数乘法器,增大了不少面积.

优化后的改进如下:①优化后解码器流水线由3级变成了2级,整个解码过程只需408周期即可完成,缩减了大量存储器面积;②步骤S2,S3,S4,S6等压缩在一级流水线中完成,省去了优化前为MEA模块输出的错误位置和错误值多项式的每个系数所乘的常数需要的32个GF(28)上的常数乘法器;③步骤S5需要的FIFO1采用2倍系统时钟后,其memory内核用单口RAM替换了原来的双口RAM,可节省大约一半面积.

优化前后的实现结果比较见表2.表2列出的面积是基于SMIC0.25μm单元库的布线结果,折合成门数约为31000门.本文采用优化方案后的RS解码器面积折合成门数和其他文献中报道的结果比较见表3.

本文给出了一个完整的基于时域解码算法的RS(204,188)解码器设计方案,在芯片实现时,充分利用了DVB系统提供的多倍率时钟,使MEA算法模块,Chien搜索模块,Forney算法模块,工作在4倍系统时钟下,FI2FO1模块工作在2倍系统时钟下,但是整个芯片的吞吐还是按系统时钟来动作.这样的优化节约了大约40%的芯片面积,同时又保证了一定的解码速率。

本文的RS解码器被整合到DVB2C的解调器芯片中,在AlteraFPGA上通过验证,芯片级验证基于SMIC0.25μm的CMOS工艺,样片在上广电中央研究院,Trident公司,无锡无线电六厂,复旦北区学生宿舍及若干住宅小区通过有线电视现场测试,从芯片内嵌的Ber测试模块的数据来看,集成的RS解码器使视频码流的误码率达到了接收系统的要求。