RS码编码算法

2024年2月15日发(作者：餐饮员工培训)

- -

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)m0m1m2x2mk1xk1

二．RS编码器的类型

1．基于乘法形式的RS编码器

公式：c(x)m(x)g(x)

结构图如下：

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

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

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

令

xnka(x)r(xg(x)b(x))g(x)

剩余多项式r(x)至少比g(x)低一次。

r(x)r2t1x2t1r2t2x2t2r2x2r1xr0

-

总结

- -

则编程的码多项式为

c(x)xnka(x)r(x)cn1x具体实现如下图：

n1cn2xn2c2xc1xc02

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

设校验多项式为：

h(x)hkxhk1x系统码的多项式为：

kk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)

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)的乘积中nxn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

而

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a2)(xa3)(xa4)(xa5)(xa6xaxaxaxaxaxa2461

由分圆多项式多项式：

g(x)(xx1)(xx1)

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

a4a10

或

aa1

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

44

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

a2

a3

a4a1

0011

a12a3a2a1

1111

0110

a13a3a21

1100

a14a31

1101

1001

0001

a5a2a

a6a3a2

a7a3a1

1011

a151

GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3（在域GF(2)上）的线性组合，如下形式：

-

总结

- -

a3aa2aa1aa0

因此在GF(2)上的2进制RS码，它的编码电路可用k或nk级2进制寄存器实现。本例是用nk6级乘法器电路实现，如下图。图中的移位积存器必须是由能积存16进制的元件组成，这可用4级触发器组成的移存器完成。44432a10,a14,a4,a6,a9常乘器可用模2加法器构成。

在域GF(2)上的系数a,a,a,a,a可用自然基地表示为如下形式：

41014469a10(a3a3a2a2a1aa0)a3a13a2a12a1a11a0a10a3(a3a21)a2(a3a2a1)a1(a3a2a)a0(a2a1)

(a3a2a1)a3(a3a2a1a0)a2(a2a1a0)a(a2a0)

a14(a3a3a2a2a1aa0)a3a17a2a16a1a15a14a0aa3aa2a(a1a0)

32

a4(a3a3a2a2a1aa0a0)a3a7a2a6a1a5a0a4a3(a3a1)a2(a3a2)a1(a2a)a0(a1)(a3a2)a3(a2a1)a2(a3a1a0)a(a3a0)

a6(a3a3a2a2a1aa0)a3a9a2a8a1a7a0a6a3(a3a)a2(a21)a1(a3a1)a0(a3a2)(a3a1a0)a3(a2a0)a2(a3a1a0)a(a2a1)

-

总结

- -

a9(a3a3a2a2a1aa0)a3a12a2a11a1a10a0a9a3(a3a2a1)a2(a3a2a)a1(a2a1)a0(a3a)(a3a2a0)a3(a3a2a1)a2(a3a2a1a0)a(a3a1)

GF(24)中乘a10的转换电路如下表示：

a10(a3a3a2a2a1aa0)(a3a2a1)a(a3a2a1a0)a(a2a1a0)a(a2a0)式中：a3'a3a2a1

a2'a3a2a1a0

32

a1'a2a1a0

a0'a2a0

GF(214)中乘a10电路

GF(24)中乘a14的转换电路如下表示：

a3'a3a2

a2'a2a1

a1'a3a1a0

a0'a1a0

GF(214)中乘a14电路

-

总结

- -

GF(24)中乘a4的转换电路如下表示：

a3'a0

a2'a3

a1'a2

a0'a3a0

GF(214)中乘a14电路

GF(24)中乘a6的转换电路如下表示：

a3'a3a1a0

a2'a2a0

a1'a3a1a0

a0'a2a1

GF(214)中乘a6电路

GF(24)中乘a9的转换电路如下表示：

a3'a3a2a0

a2'a3a2a1

a1'a3a2a1a0

a0'a3a1

-

总结

- -

GF(214)中乘a9电路

[15,9,7]RS编码器具体实现电路如下图所示：

工作过程如下：

（1） 门打开，开关拨到符号输入端，所有移存器清0。然后将6个16进制信息符号，一边送入移存器，一边送入信道。注意每一节拍移动一个16进制符号。

（2） 6个16进制符号送入移存器后，完成除法运算，移存器中的就是余式。此时，门关闭，开关拨到下面。再经过6个节拍的移动，得到所有6个校验元，并且跟随信息元送入信道，完成一个码字的编码过程。

（3） 清洗积存器，打开门，开始第二组信息元的编码。

-

总结