1、1信息论与编码课程设计RS 编解码的 MATLAB 实现与分析2中文摘要RS 码全称为 Reed-Solomon 码，是由 Irving Reed 和 Gus Solomon 在 1960年发明的。RS 码是差错控制领域中一类重要的线性分组码，具有较强的纠正突发错误和随机错误的能力。特别是在短码和中等长度码的情况下，其性能接近于理论值。由于 RS 码采用了 q 进制（ q=2m） ，所以它是多进制调制时的自然和方便的编码手段。因为 RS 码能够纠正小于或等于 t 个的随机差错，或者纠正单个长度为（t-1 ）m+1 的突发错误，所以适合于在衰落信道中使用，以克服突发性差错。而且该码具有各种成熟，
2、可用，有效的译码算法。因此 RS 码在工程中被广泛应用，包括各种通信和计算机存储系统中。特别是 RS 码和卷积码构成的级联码，已经被定义为深空通信的下行链路中的标准 1。另外，欧洲数字视频广播DVB（ -S/T/C）统一采用（ 204，188）RS 码。本文将对 RS 码的编解码原理进行阐述，并运用 MATLAB 对 RS 码进行仿真和分析。关键词：RS 码 纠错 MATLAB3AbstractRS codes as Reed-Solomon code, found by Irving Reed and Gus Solomon in 1960. RS code is an important
3、class of linear block codes in the field of error control code, with a strong capacity of correcting burst errors and random errors. Especially in the case of short and medium length code, the performance is close to the theoretical value.Using a base-Q, RS codes are the natural and convenient means
4、 in a multi-ary modulation. RS code can correct a less than or equal to t random errors, or to correct a single length (t-1) m+1 burst error, so it is suitable for the use in the fading channel in order to overcome the unexpected errors. And that the codes have a variety of mature, available, effici
5、ent decoding algorithms. Therefore, RS codes are widely used in engineering, including various communications and computer storage systems. especially in concatenated codes which consists of RS code and convolutional code, has been defined as deep-space communications standards in the downlink1. In
6、addition, the European Digital Video Broadcasting DVB (-S/T/C) uniform application of (204,188) RS codes. This RS code and decoding will be explained the principle and the use of MATLAB code for simulation and analysis of RS is also includes in this principleKey words: RS code,Correction,MATLAB41. R
7、S 码的发展和现状 2根据香农提出的信道编码定理，任意离散输入无记忆平稳信道存在信道容量 C，它标志着信道传输能力的上限，只要信息传输速率 R=3 ，m 是任意整数)有限域上，且 RS 码是 MDS 码，具有极大最小距离特性，它具有卓越的纠错能力，无论是纠突发错误还是纠随机错误的能力，以及它的快速译码速度，均是其它码类无法比拟的。用 MS 多项式产生的是非系统码，而用 BCH 构造方法能产生系统码。我们用的是后一种。RS 码的定义：GF(q)上的 (q2，q=2 m)，码长 n=q-1 的本原 BCH 码成为 RS6码 2。可知 RS 码最主要的特点之一是码元取自 GF(2m)上，而它的生成多
8、项式也在 GF(q)上，所以 RS 码是码元的符号域与根域一致的 BCH 码。因为 ， （其中 ）的最小多项式 。iqxx1iqGFiix所以，码长为 N=q-l，校验位 n-k=2t，设计距离为 的 RS 码，最小距离 dmin=n-k+1。由 BCH 码的定义可知，它的生成多项式为 txxg22从 RS 码的 n、k 值立即可断定其纠错能力为t=int(dmin-1)/2=int(n-k)/2由此生成一个 q 进制的q-1，q- RS 码，有最小距离 。由于线性码的最大可能的最小距离是校验元的个数加 l，而 RS 码恰好做到了这一点。因此，称RS 码为极大最小距离可分码，简称 MDS 码。
9、显然 RS 码的设计距离 与实际距离 D 是一致的。如果我们要设计一个 =9 的 RS 码，显然 RS 码的冗余位为-1=8=2t 它的生成多项式为：82xxg将信息段看成信息码多项式 m(x)，即 knnnccm21用信息码多项式 m(x)除以生成多项式 g(x)，所得余式 r(x)为监督码多项式，即 xgxrknod将监督码多项式 r(x)置于信息码多项式之后，形成 RS 码。4.2 RS 译码RS解码可分为时域解码和频域解码。时域解码直接根据接收到的数据确定错误位置，不需要转换计算，相对较容易实现。反之，频域解码首先要确定错误位置的傅氏变换，然后通过傅氏反变换找到错误位置，因此一般采用时
10、域解码 9。本文 RS 码译码算法采用 Berlekamp 算法 10-11，该算法是从计算接收码字得到的伴随式入手，以下我们用 c(x)表示码字，e(x)表示有 个错误得错t误图样，r(x)表示接受字，r(x)=c(x)+e(x)， 其中 xi 是xyxye21第 i 个差错得错误位置，定义 ，yi 是它的错误值。iix（1）根据接收到的码多项式计算伴随式 S7而计算伴随式之值Sp(p=1,2,，2t-1,2t),就是将码得规定根代入多项式 r(x) ，则得， 110 npppp rrrs 若 S=0，认为接收无误。若 ，则由 S 找出错误图样。0S因为 ，而 （p=1,2,，2t）pppe
11、cpc110 npees 即从本质上说，译码器就是求解伽逻华域GF（2 m）上得这组伴随式非线性联立方程，由伴随式S 找出错误图样时，先确定错误位置。由于 RS 码是由伽逻华域 GF（2 m）上某个元素的 2t 个连续幂次为根的生成多项式所定义的，用这些根取估算一个码字多项式时，可写出 xi 再求错误值 yi。一般避免直接求解错误位置 xi，而代之以间接法。 （2）从伴随式S 到差错位置多项式 的迭代算法x错误位置多项式为：显然，差错位置多项式 的 v 个根式差错位置数的倒数 。x 112,v各次项的系数 和 一样是未知数。将式展开可得：x,10 v,218再将式代入式可得牛顿恒等式：令第 次
12、迭代后所得 是 次多项式为xl这时， 表示第 次迭代后所得得 i 次项系数。 得系数li,21 x一定满足式得前 个牛顿恒等式，但不一定满足第 +1 个牛顿恒等式。为了求 ，先求第 次迭代的差值 如下：x d差值 实际上就是将第 次迭代的结果代入最后一个牛顿恒等式所得的结果。d如果 =0，说明 的系数也满足第 +1 个牛顿恒等式，校验通过。x这时可令 ，如果 ，说明 的系数不满足第 +1 个x1 0dx牛顿恒等式，差距是 ，这时要求 做修正并求修正后的 。修正dxx1后的取法是：I从本次的迭代回退，寻找前面某一次，比如第 次迭代（）的差错多项式 ，要求该次（即第 次）迭代差值 且 最大。 是第
13、x 0dll9 次迭代时多项式 最高项的次数，即xxldegII取修正项为 ，即令：d1x1式中， ， ， 的最高次为：l1eglxegx1 lllx,maxd11（3）利用错误位置多项式求出差错位置数 v,21将得到的错误位置多项式的系数代入式，可算得 v,21（4）利用伴随式和 的系数求出差错幅值x由式和式，可得：比较它们得同次项系数，再代入式，即可得：根据式即可求得差错幅值。5.模块组合本文采用 RS（7，3）码进行仿真，各模块组合及其仿真流程图如图 1 所示：10图 1其中，RS 编码与解码已经在基础理论中做了介绍，下面着重对其他组合模块的功能和产生进行简单的介绍。5.1 多进制信源用 MATLAB 自带函数 rand 产生随机数，乘以 M（所要产生的进制数） ，再经过向下取整即可。5.2 将多进制信息进行分帧由于多进制信源产生的是一连串的多进制符号，为了进行编码，需将这些符号进行分组，本次设计采用 MATLAB 自带函数 reshape, 将信息串（本次设计采用 12000）变换成一个矩阵，该矩阵的行数为帧数（本次设计取值为 4000） ，列数为信息位数（本次设计取值为 3）
