根据香农提出的信道编码定理,任意离散输入无记忆平稳信道存在信道容量C,它标志着信道传输能力的上限,只要信息传输速率R<c,就存在一种编码方式,当平均码长足够大时,译码错误概率可以做到任意小;反之,则无论采用何种编码方式也不可能保证错误概率任意小。该定理虽然没有明确指出如何对数据信息进行纠错编码,也没有给出这种具有纠错能力通信系统的具体实现方法.但它奠定了信道编码的理论基础,从理论上指出了信道编码的努力方向。[ color][="" align]正由于目前其成熟的理论和技术,rs码在现代数字通信、数据存储系统中得到了广泛的应用,具体应用[6]见表1.1。[="" 0)]表1.1[="" align] | |
| |
| |
| RS(208,192)码,RS(182,172)码乘积码 |
| 内码为卷积码,外码为RS(204,188)码的级联码 |
| 内码为卷积码,外码为RS(207,187)码的级联码 |
| 内码为卷积码,外码为RS(255,223)码的级联码 |
| |
3.研究RS码的意义与目的[7]在实际的通讯信道中,信号的传输会受到噪声的干扰,从而在接收端不可避免地会发生错误。要使信号能可靠的传输,即要降低信号传输中的误码率。人们采用了一系列相关技术来改善噪声信道的接收性能,使接收信息的误码率尽可能降低。这些技术中,信道的纠错编码及其译码方法处于非常重要的地位。自从1948年香农发表了关于信道容量理论极限的重要论文之后,短短几十年时间里,人们在信道编码研究领域相继取得了众多理论成果和突破。
信道编码按照对信息元的处理方式不同,可分为线性分组码和卷积码,线性分组码可以完全用代数方法来严格地表达,它的出现较早而且其译码方法也较为简单,因此容易被人们所认识,现在有关线性分组码的理论已经相当成熟。卷积码虽然也早已出现,但由于其编码结构不能较好的用代数方法表示,因此给卷积码的理论研究带来了一定的困难。但是,单独的线性分组码或卷积码在性能上离香农理论极限还相差较远。为了进一步提高编码的纠错性能,人们采用了不同的措施,其中将两个编码进行串行级联是一种有效的方法。级联码一般采用Rs码作为外码,卷积码作为内码,因此可以同时纠正随机和突发的混合错误。但是这种形式的级联码,对改善单个码元的误码率仍没有太大帮助。如何对现有的编码方法进行改进,从而更加逼近香农理论极限,已经成为国际通信学界的重大课题。
RS码具有很强的抗突发误码的能力,因此被广泛应用于各种通信领域。正因为RS编码的应用范围非常广泛,对于RS编/解码技术的研究一直是国内外通信系统研究的一个热点,特别是RS编/解码的硬件设计更是其中之重点和难点。
4.基础理论4.1 RS编码RS编码是一种线性的块编码[8],其表示形式为RS(n,k)。当编码器接收到一个数据信息序列,该数据信息序列被分割成若干长度为k的信息块,并通过运算将每个数据信息块编码成长度为k的编码数据块。在RS码中的码元符号不是二进制而是多进制符号,其中2m进制使用更为广泛。RS码是建立在GF(2m)上(m>=3,m是任意整数)有限域上,且RS码是MDS码,具有极大最小距离特性,它具有卓越的纠错能力,无论是纠突发错误还是纠随机错误的能力,以及它的快速译码速度,均是其它码类无法比拟的。用MS多项式产生的是非系统码,而用BCH构造方法能产生系统码。我们用的是后一种。
RS码的定义:GF(q)上的(q≠2,q=2m),码长n=q-1的本原BCH码成为RS码[2]。可知RS码最主要的特点之一是码元取自GF(2m)上,而它的生成多项式也在GF(q)上,所以RS码是码元的符号域与根域一致的BCH码。
因为
,(其中
)的最小多项式
。所以,码长为N=q-l,校验位n-k=2t,设计距离为
的RS码,最小距离dmin=n-k+1。由BCH码的定义可知,它的生成多项式为
从RS码的n、k值立即可断定其纠错能力为
t=int[(dmin-1)/2]=int[(n-k)/2]
由此生成一个q进制的[q-1,q-]RS码,有最小距离。由于线性码的最大可能的最小距离是校验元的个数加l,而RS码恰好做到了这一点。因此,称RS码为极大最小距离可分码,简称MDS码。显然RS码的设计距离与实际距离D是一致的。如果我们要设计一个=9的RS码,显然RS码的冗余位为-1=8=2t它的生成多项式为:
将信息段看成信息码多项式m(x),即
用信息码多项式m(x)除以生成多项式g(x),所得余式r(x)为监督码多项式,即
将监督码多项式r(x)置于信息码多项式之后,形成RS码。
4.2 RS译码RS解码可分为时域解码和频域解码。时域解码直接根据接收到的数据确定错误位置,不需要转换计算,相对较容易实现。反之,频域解码首先要确定错误位置的傅氏变换,然后通过傅氏反变换找到错误位置,因此一般采用时域解码[9]。
本文RS码译码算法采用Berlekamp算法[10-11],该算法是从计算接收码字得到的伴随式入手,以下我们用c(x)表示码字,e(x)表示有
个错误得错误图样,r(x)表示接受字,r(x)=c(x)+e(x),
其中xi是第i个差错得错误位置,定义
,yi是它的错误值。
(1)根据接收到的码多项式计算伴随式S
而计算伴随式之值{Sp}(p=1,2,…,2t-1,2t),就是将码得规定根代入多项式r(x) ,则得,
若S=0,认为接收无误。若
,则由S找出错误图样。
因为
,而
(p=1,2,…,2t)
即
从本质上说,译码器就是求解伽逻华域GF(2m)上得这组伴随式非线性联立方程,由伴随式S找出错误图样时,先确定错误位置。
由于RS码是由伽逻华域GF(2m)上某个元素的2t个连续幂次为根的生成多项式所定义的,用这些根取估算一个码字多项式时,可写出xi再求错误值yi。一般避免直接求解错误位置xi,而代之以间接法。
(2)从伴随式S到差错位置多项式
的迭代算法
错误位置多项式为:
显然,差错位置多项式的v个根式差错位置数的倒数
。各次项的系数
和
一样是未知数。将②式展开可得:
再将③式代入①式可得牛顿恒等式:
令第μ次迭代后所得
是
次多项式为
这时,
表示第μ次迭代后所得得i次项系数。得系数一定满足式③得前μ个牛顿恒等式,但不一定满足第μ+1个牛顿恒等式。为了求
,先求第μ次迭代的差值
如下:
差值实际上就是将第μ次迭代的结果代入最后一个牛顿恒等式所得的结果。
如果=0,说明的系数也满足第μ+1个牛顿恒等式,校验通过。这时可令
,如果
,说明的系数不满足第μ+1个牛顿恒等式,差距是,这时要求做修正并求修正后的。修正后的取法是:
I.从本次的迭代回退,寻找前面某一次,比如第ρ次迭代(ρ<μ)的差错多项式
,要求该次(即第ρ次)迭代差值且
最大。
是第ρ次迭代时多项式
最高项的次数,即
II.取修正项为
,即令:
式中,
,
,的最高次为:
(3)利用错误位置多项式求出差错位置数
将得到的错误位置多项式的系数代入式①,可算得
(4)利用伴随式和
的系数求出差错幅值
由式④和式⑤,可得:
比较它们得同次项系数,再代入①式,即可得:
根据⑥式即可求得差错幅值。
5.模块组合本文采用RS(7,3)码进行仿真,各模块组合及其仿真流程图如图1所示:
图1
其中,RS编码与解码已经在基础理论中做了介绍,下面着重对其他组合模块的功能和产生进行简单的介绍。
5.1 多进制信源用MATLAB自带函数rand产生随机数,乘以M(所要产生的进制数),再经过向下取整即可。
5.2 将多进制信息进行分帧由于多进制信源产生的是一连串的多进制符号,为了进行编码,需将这些符号进行分组,本次设计采用MATLAB自带函数reshape, 将信息串(本次设计采用12000)变换成一个矩阵,该矩阵的行数为帧数(本次设计取值为4000),列数为信息位数(本次设计取值为3)
5.3 PSK传输系统
图2
(1)8PSK调制器
I.首先将RS编码器的输出,映射到数域。然后把每个八进制符号都映射成三个二进制符号,映射规则如表2所示:
表2
II.再将每三个二进制符号按图三进行映射。
(2)高斯随机数发生器
同时产生高斯随机数的同相分量和正交分量。
(3)为了验证RS码在突发差错情况下仍然保持良好性能,故在PSK传输系统中引入突发差错,与未加突发差错的情况形成对比。
(4)判决器
计算接受信号在发送向量的投影,判断哪个投影最大,就判哪个向量输出。
图3
5.4 将信息帧合并一串信息由于从RS译码器输出的消息是分组的,应将这些消息进行合并,以便与信源产生的消息进行比较,计算误码率。
5.5 误码率计算只要将上述输出与信源比较,计算有多少不同的符号,然后再除于信源产生的符号数,即得误码率。
6.结果分析根据以上仿真过程,采用信源产生N=
(为节约程序运行时间,故N取值较小)个符号,固定信号功率S=1,得出以下图表。
经RS编码后,信道采用pskmoto.m文件,信息流通过未加随机差错的曲线如下图所示:
图4
经RS编码后,信道采用pskmoto2.m文件,信息流通过加上随机差错的曲线如下图所示:
图5
对比两图可见,未加突发差错和加上突发差错的信噪比与误码率曲线图相差不多,故得出结论,RS编码对突发差错具有良好的抵抗能力。
7.总结通过本次课程设计的学习让我了解了RS编码的历史、原理和编码的步骤还有它的实际应用和不足之处、也使我对RS编码有了重新的认识。通过本课程的学习,我也认识了自己还有很多不足,需要进一步学习的地方,在接下来的学习中我会花更多时间,我要不断的努力,多联系,多思考,来认真加深知识理解与运用,我相信我能有所进步的。
参考文献[1] 苏艳琴等.基于RS码和LDPC码的纠错性能分析.海军航空工程学院电子信息工程系.
[2] 陈曦.基于RS编码的光通信系统的设计与实现:[硕士学位论文].成都:电子科技大学,2009
[3] Xu Youzhi.Implementation of Berlekamp-Massey algorithm without inversion.1EE E
Proceedings-I,1991,138(2):138-140
[4] Hsie-Chia Chang,C.Bernard Shung.New Serial Architecture for the Berlekamp-Massey
Algorithm.IEEE Transactions on communications,1999,47(4):48 1-483
[5] DiHp V Sarwate,Narcsh R Shanbhag.High-Speed Architectures for Reed-Solomon Decoders.
IEEE Transactions Very Large Scaleintegration(VLSD Systems,2001,9(5):641-655
[6]陈飞,周德新.高速光网络系统中FEC编码器的设计与实现.光通信技术,2004,4(5):35.37
[7] 曹立朋.数字视频广播传输系统中的的信道编码技术:[硕士学位论文].西安:西安电子科技大学,2006
[8] 曹雪虹,张宗橙.信息论与编码.清华大学出版社.2004.
[9] 尧勇仕.DVB系统的RS编解码的设计及ASIC实现:[硕士学位论文].江苏:江南大学,2008
[10] Marconetti, R. Guenard, D. Savage, P. Crowe, I. Epelde, L. Bradley, F. Cali.A fully programmable Reed Solomon 8-bit codec based on a re-shapedBerlekamp Massey algorithm. Proceedings of the IEEE InternationalSymposium on Circuits and Systems (ISCAS ’02), 2002, 5: 553-556.
[11] 朱起悦.RS码编码和译码算法.中国期刊网.1999.4.