RS码编码算法

更新时间:2024-02-15 18:16:54 阅读: 评论:0

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

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)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) 清洗积存器,打开门,开始第二组信息元的编码。

-

总结

RS码编码算法

本文发布于:2024-02-15 18:16:54,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/zhishi/a/1707992214266935.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:RS码编码算法.doc

本文 PDF 下载地址:RS码编码算法.pdf

标签:符号   电路   编码器   编码
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 实用文体写作网旗下知识大全大全栏目是一个全百科类宝库! 优秀范文|法律文书|专利查询|