RS码编码算法

RS码编码算法

一．RS编码

对于能够纠正t个错误的RS（n,k,d）码，具有如下特征：

1）码长：n?2m?1符号或m(2m?1)比特 2）信息码元数：k?n?2t或mk比特；

3）监督码元数：n?k?2t符号或m(n?k)比特；

4）最小距离：d?2t?1?n?k?1符号或m(n?k?1)比特； 最小距离为d的本原RS码的生成多项式为

g(x)?(x??)(x??2)(x??3)?(x??d?2)

式中的m是一个任意整数。 令信息元多项式为：

m(x)?m2k?10?m1?m2x???mk?1x

二．RS编码器的类型

1．基于乘法形式的RS编码器 公式：c(x)?m(x)g(x) 结构图如下：

由上面结构的乘法编码器输出的码字是非系统码。

2．基于除法形式的RS编码器

（1） 根据生成多项式g(x)构造的除法编码器。 令

xn?ka(x)g(x)?b(x)?r(x)g(x)

剩余多项式r(x)至少比g(x)低一次。 r(x)?r?12t?22t?1x2t?r2t?2x???r2x2?r1x?r0

则编程的码多项式为

c(x)?xn?ka(x)?r(x)n?1?cn?1x?cn?2xn?2???c2x2

?c1x?c0具体实现如下图：

（2） 根据校验码多项式h(x)构造的除法编码器 设校验多项式为：

h(x)?hkx系统码的多项式为：

C(x)?cn?1xn?1n?2k?hk?1xk?1???h1x?h0

n?k?1?cn?2x???cn?kxn?k?cn?k?1x???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) ??C(x)?n?1,??g(x)?n?k,??q(x)?k?1

而

h(x)C(x)?q(x)g(x)h(x)?q(x)(xn?1)?q(x)xn?q(x)

由于

??C(x)?n?1,??g(x)?n?k,??g(x)?n?k,??q(x)?k?1

所以q(x)x的最低位次数至少为n次，而在h(x)C(x)的乘积中

xxn?1n,xn?2,?,x的次数为0。

kn?1的系数：

cn?1?0h0?cn?1?1h1???cn?1?khk

xn?2的系数：

cn?2?0h0?cn?2?1h1???cn?2?khk

而

?cn?i?jhj?0j?0ki?0,1,2,?,n?k

由于h(x)为首一多项式，hk?1，故上式可写为 cn?k?i???cn?i?jhjj?0k?1i?1,2,?,n?k

上式展开为：

cn?k?1??(cn?1h0?cn?2h1???cn?khk?1)cn?k?2??(cn?2h0?cn?3h1???cn?k?1hk?1)?cn?k?(n?k)?c0??(ckh0?ck?1h1???c1hk?1)

由上式看出码字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。 具体实现如下图：

（3） RS的时域编码实际例子

RS码是非二进制码，它是在GF(q)上的，这里q?2。这里我们选用GF(16)域来进行，域中16个元素可用4bits符号表示。

例 构造一个能纠正3个错误符号，码长为15，m=4的RS码。求生成多项式和编码电路。

解：当t?3时，最小码距Dmin?7，信息元长度k?9。该码为（15，9）RS码，其生成多项式为：

g(x)?(x?a)(x?a)(x?a)(x?a)(x?a)(x?a?x623456?a10x?a514x4?ax?ax4362?ax?a96

由分圆多项式多项式：

g(x)?(x2?x?1)(x4?x?1)

a?GF(16)是本原域元素，它是多项式xa44?x?1的根，则

?a?1?0

或 a44?a?1

4以x?x?1为模的GF(2)的元素如下表：

a0?1 0001 a8?a2?1 0010 a9?a3?a 0100 a10?a2?a?1 1000 a11?a3?a2?a 0101 1010 0111 1110 a a a aa432?a?1 ?a20011 a12?a3?a2?a?1 1111 0110 a13?a3?a2?1 1100 a14?a3?1 1101 1001 0001 5?a aa6?a?a3?a 27315?a?1 1011 a?1

GF(2)中每个元素都可表示成它的自然基地1,a,a,a（在域GF(2)上）的线

423性组合，如下形式：