RS编解码的基本方法

2024年2月15日发(作者：团干部培训心得体会)

RS编解码的基本方法

作者：刘延海 张亮

来源：《科技资讯》 2011年第32期

刘延海 张亮

(陕西凌云电器集团有限公司 陕西宝鸡 721006)

摘 要:总体介绍了RS码的基本理论,讲述了RS编解码的基本方法。实践证明,RS编解码适用于大多数无线通讯信道的纠错码。

关键词:伽罗华域 生成多项式 伴随多项式 错误多项式

中图分类号:TP393.33 文献标识码:A 文章编号:1672-3791(2011)11(b)-0003-02

BCH码是迄今为止所发现的一类很好的线性纠错码。它的纠错能力很强,可以纠正多个随机错误,特别是它在短和中等码长下,其性能很接近于理论值,并且构造方便,编码简单。特别是它具有严谨的代数结构,因此在编码理论中起着重要的作用。BCH码是迄今为止研究得最为详尽,分析最为透彻,取得的成果也是最多的码类之一。

在实际应用中,所选择码字主要看其编译码是否简单,速度是否足够快,是否易于工程实现,是否能取得较好的性能。BCH码有很多译码算法,其中Berlekamp或Euclid迭代译码算法,大大加快了译码速度。且易于软硬件实现,从实际上解决了BCH码的译码问题。正是由于这些优点,使得它在实际中受到工程技术人员的欢迎,是目前应用最为广泛的码类之一。

RS码是一类有很强纠错能力的多进制BCH码,也是一类典型的代数几何码。它的编译码技术比较成熟且性能优良,因此在数字通信和数字存储系统中得到广泛应用。这些应用包括无线通信,移动通信,卫星通信,数字电视,DVB,及象ADSL,或xDSL这样的高速调制解调器中。在这些系统中,RS码已经被选为用于FEC的码类,作为规范的一部分。

1 RS码的性能

在实际的通信中,由于各种噪声及其它不可预知的因素,不可避免的造成传输的信息错误。这种错误的特性和信道及系统特性有关。一般来说,所发生的错误可以分为以下两类。

(1)一类是随机错误。即单个比特错误,而且各个错误彼此独立,不相关,它一般是由于热噪声引起的。纠此类错误,可以用RS码和卷积码。由于RS码是块码,如果在一个信息块中,错误较少,则错误可以被RS码全部纠正。

(2)第二类是突发错误。即错误比特连续出现,但不是很长。纠正此类错误,RS码非常有效。

RS码是最大距离可分码,其最小距离dmin=n-k+1,最多可纠正(n-k)/2个错误,如RS(16,7)可纠正4个错误,RS(31,15)可纠正8个错误。

RS码的纠错能力是以所能纠正的符号数来表示的。对RS码来说,一个符号内错一个比特与错所有比特是相同的,这使得RS码特别适用于纠突发错误,如RS(16,7)可纠正连续20比特的错误,RS(31,15)可纠正连续40比特的错误。相对而言,RS码就对随机错误比较敏感。

综上所述,RS码是一类非常好的码字,性能优良。

2 有限域的基本知识

2.1 (定义)域是一种代数结构,它由一个集合F构成,并在该集合上定义了加法运算(+)和乘法运算(×),且对集合F中的任意元素满足以下性质

3 RS编码原理

RS编码方式为系统码,码字多项式的第n-1次至n-k次系数是信息位,其余为校验位,这相当于C(x)=m(x)xn-k+r(x),式中m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0是信息多项式,(mk-1,m1,m0)是信息位,而r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+…+r1x+r0是校验多项式,相应的系数是码元的校验位。编码过程即是根据k个信息码元及[n,k]RS码的特性获得n-k个校验码元的过程。[n,k]RS循环码的校验码元可根据校验多项式h(x)=hkxk+hk-1xk-1+…+h1x+h0获得。设系统码多项式为C(x)=cn-1xn-1+cn-2xn-2+…+cn-kxn-k+cn-k-1xn-k-1+…+c1x+c0,它的前k位系数。cn-1,cn-2,cn-k是已知的信息位,后n-k位系数。cn-k-1,cn-k-2,…,c1,c0是需要求的校验位。因为码多项式必是生成多项式g(x)的倍式,故有C(x)=q(x)g(x),而h(x)C(x)=q(x)g(x)h(x)=q(x)(xn-1)=q(x)xn-q(x),q(x)xn的最低次数至少为n次,因此h(x)C(x)的乘积中,xn-1,xn-2,…,xk次的系数应为0,而xn-1的系数由cn-1-0h0+cn-1-1h1+…+cn-1-khk组成,xn-2的系数由cn-2-0h0+cn-2-1h1+…+cn-2-khk组成。这表明码字C的第一个校验元cn-k-1可由k个信息元cn-1,cn-2,,cn-k与h(x)的系数相乘得到,而由cn-2,cn-3,…,cn-k,cn-k-1可得到第二个校验元cn-k-2,再由cn-3,…,cn-k信息元和第一、第二校验元cn-k-1,cn-k-2可得到第三校验元cn-k-3。依此类推,可求得所有的n-k个校验元cn-k-1,cn-k-2,…,c1,c0。

根据以上的过程分析,可知RS编码的软件实现过程如下。

(1)首先求出域GF(2m)中的所有元素并存储备用。

(2)在[n,k,d]RS码中,其生成多项式是唯一的,由xn-1=g(x)h(x),可知校验多项式h(x)也是唯一确定的,且g(x)=(x-)(x-2)…(x-n-k),根据伽罗华域上的运算规则可求出h(x)=(xn-1)/g(x)的各项系数。

(3)据上面的分析,依次求出所需的校验元cn-k-1,cn-k-2,…,c1,c0。

4 RS解码

解码比编码困难得多,解码过程描述如下。

(1) 求伴随式。

(2)检查伴随式,若全为0,则接收码字为有效码字,转到9)。

(3)初始化。

其中和分别是和的最高次项系数,m是和的度数之差;执行这个迭代过程直到。

(5)分别对和归一化,使常数项为1,求得和。

(6)求的根,得到错误位置;如果根的数目小于的度数(说明有重根,或在扩域上有根),译码失败,转到10)。

(7)由Forney算法,求错误值,如果分母为0,则译码失败,转到10)。

(8)接收码字对应位置减去错误值,纠错。

(9)输出正确码字中的信息位。

(10)输出接收码字中的信息位,置译码失败标志。

5 结语

RS编解码过程涉及域、线性分组码、生成矩阵、校验矩阵、伴随式等概念,文中将编解码方法做了总结。

参考文献

[1]王新梅,肖国镇.纠错码原理与方法[M].西安:西安电子科技大学出版社,2001.

[2]JyhHorng Jeng,TrieuKien ding of Both Errors and Erasures of

aReed-Solomon CodeUsing an Inver-FreeBerlekamp-Masy Algorithm[J].IEEE

Transactions on Communications,1999,47(10):1488～1494.