2024年2月15日发(作者:餐饮员工培训)
- -
RS码编码算法
一.RS编码
对于能够纠正t个错误的RS(n,k,d)码,具有如下特征:
1) 码长:n2m1符号或m(2m1)比特
2) 信息码元数:kn2t或mk比特;
3) 监督码元数:nk2t符号或m(nk)比特;
4) 最小距离:d2t1nk1符号或m(nk1)比特;
最小距离为d的本原RS码的生成多项式为
g(x)(x)(x2)(x3)(xd2)
式中的m是一个任意整数。
令信息元多项式为:
m(x)m0m1m2x2mk1xk1
二.RS编码器的类型
1.基于乘法形式的RS编码器
公式:c(x)m(x)g(x)
结构图如下:
由上面结构的乘法编码器输出的码字是非系统码。
2.基于除法形式的RS编码器
(1) 根据生成多项式g(x)构造的除法编码器。
令
xnka(x)r(xg(x)b(x))g(x)
剩余多项式r(x)至少比g(x)低一次。
r(x)r2t1x2t1r2t2x2t2r2x2r1xr0
-
总结
- -
则编程的码多项式为
c(x)xnka(x)r(x)cn1x具体实现如下图:
n1cn2xn2c2xc1xc02
(2) 根据校验码多项式h(x)构造的除法编码器
设校验多项式为:
h(x)hkxhk1x系统码的多项式为:
kk1h1xh0
C(x)cn1xn1cn2xn2cnkxnkcnk1xnk1c1xc0它的前k位系数:cn1,cn2,,cnk是已知的信息位,而后nk位系数:cnk1,cnk2,,c1,c0是需求的校验位。码多项式必是生成多项式g(x)的背式,所以
C(x)q(x)g(x)
C(x)n1,g(x)nk,q(x)k1
而
h(x)C(x)q(x)g(x)h(x)q(x)(xn1)q(x)xnq(x)
由于
C(x)n1,g(x)nk,g(x)nk,q(x)k1
所以q(x)x的最低位次数至少为n次,而在h(x)C(x)的乘积中nxn1,xn2,,xk的次数为0。
xn1的系数:
-
总结
- -
cn10h0cn11h1cn1khk
xn2的系数:
cn20h0cn21h1cn2khk
而
cnijhj0j0ki0,1,2,,nk
由于h(x)为首一多项式,hk1,故上式可写为
cnkicnijhjj0k1i1,2,,nk
上式展开为:
cnk1(cn1h0cn2h1cnkhk1)cnk2(cn2h0cn3h1cnk1hk1)cnk(nk)c0(ckh0ck1h1c1hk1)由上式看出码字C的第一个码元cnk1可由k个信息元cn1,cn2,,cnk与
h(x)的系数相乘得到,而由cn2,cn3,,cnk,cnk1可得到第二个校验元cnk2,再由cn3,,cnk信息元和第一、第二校验元cnk1,cnk2可得到第三校验元cnk3。按这样的线性关系递推,一直可求得所有的nk个校验元cnk1,cnk2,,c1,c0。
具体实现如下图:
(3) RS的时域编码实际例子
-
总结
- -
RS码是非二进制码,它是在GF(q)上的,这里q2。这里我们选用GF(16)域来进行,域中16个元素可用4bits符号表示。
例 构造一个能纠正3个错误符号,码长为15,m=4的RS码。求生成多项式和编码电路。
解:当t3时,最小码距Dmin7,信息元长度k9。该码为(15,9)RS码,其生成多项式为:
g(x)(xa)(xa2)(xa3)(xa4)(xa5)(xa6xaxaxaxaxaxa2461
由分圆多项式多项式:
g(x)(xx1)(xx1)
aGF(16)是本原域元素,它是多项式x4x1的根,则
a4a10
或
aa1
4以xx1为模的GF(2)的元素如下表:
44
a01
0001
a8a21
0010
a9a3a
0100
a10a2a1
1000
a11a3a2a
0101
1010
0111
1110
a
a2
a3
a4a1
0011
a12a3a2a1
1111
0110
a13a3a21
1100
a14a31
1101
1001
0001
a5a2a
a6a3a2
a7a3a1
1011
a151
GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3(在域GF(2)上)的线性组合,如下形式:
-
总结
- -
a3aa2aa1aa0
因此在GF(2)上的2进制RS码,它的编码电路可用k或nk级2进制寄存器实现。本例是用nk6级乘法器电路实现,如下图。图中的移位积存器必须是由能积存16进制的元件组成,这可用4级触发器组成的移存器完成。44432a10,a14,a4,a6,a9常乘器可用模2加法器构成。
在域GF(2)上的系数a,a,a,a,a可用自然基地表示为如下形式:
41014469a10(a3a3a2a2a1aa0)a3a13a2a12a1a11a0a10a3(a3a21)a2(a3a2a1)a1(a3a2a)a0(a2a1)
(a3a2a1)a3(a3a2a1a0)a2(a2a1a0)a(a2a0)
a14(a3a3a2a2a1aa0)a3a17a2a16a1a15a14a0aa3aa2a(a1a0)
32
a4(a3a3a2a2a1aa0a0)a3a7a2a6a1a5a0a4a3(a3a1)a2(a3a2)a1(a2a)a0(a1)(a3a2)a3(a2a1)a2(a3a1a0)a(a3a0)
a6(a3a3a2a2a1aa0)a3a9a2a8a1a7a0a6a3(a3a)a2(a21)a1(a3a1)a0(a3a2)(a3a1a0)a3(a2a0)a2(a3a1a0)a(a2a1)
-
总结
- -
a9(a3a3a2a2a1aa0)a3a12a2a11a1a10a0a9a3(a3a2a1)a2(a3a2a)a1(a2a1)a0(a3a)(a3a2a0)a3(a3a2a1)a2(a3a2a1a0)a(a3a1)
GF(24)中乘a10的转换电路如下表示:
a10(a3a3a2a2a1aa0)(a3a2a1)a(a3a2a1a0)a(a2a1a0)a(a2a0)式中:a3'a3a2a1
a2'a3a2a1a0
32
a1'a2a1a0
a0'a2a0
GF(214)中乘a10电路
GF(24)中乘a14的转换电路如下表示:
a3'a3a2
a2'a2a1
a1'a3a1a0
a0'a1a0
GF(214)中乘a14电路
-
总结
- -
GF(24)中乘a4的转换电路如下表示:
a3'a0
a2'a3
a1'a2
a0'a3a0
GF(214)中乘a14电路
GF(24)中乘a6的转换电路如下表示:
a3'a3a1a0
a2'a2a0
a1'a3a1a0
a0'a2a1
GF(214)中乘a6电路
GF(24)中乘a9的转换电路如下表示:
a3'a3a2a0
a2'a3a2a1
a1'a3a2a1a0
a0'a3a1
-
总结
- -
GF(214)中乘a9电路
[15,9,7]RS编码器具体实现电路如下图所示:
工作过程如下:
(1) 门打开,开关拨到符号输入端,所有移存器清0。然后将6个16进制信息符号,一边送入移存器,一边送入信道。注意每一节拍移动一个16进制符号。
(2) 6个16进制符号送入移存器后,完成除法运算,移存器中的就是余式。此时,门关闭,开关拨到下面。再经过6个节拍的移动,得到所有6个校验元,并且跟随信息元送入信道,完成一个码字的编码过程。
(3) 清洗积存器,打开门,开始第二组信息元的编码。
-
总结
本文发布于:2024-02-15 18:16:54,感谢您对本站的认可!
本文链接:https://www.wtabcd.cn/zhishi/a/1707992214266935.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文word下载地址:RS码编码算法.doc
本文 PDF 下载地址:RS码编码算法.pdf
留言与评论(共有 0 条评论) |