RS码编码算法.docx
《RS码编码算法.docx》由会员分享，可在线阅读，更多相关《RS码编码算法.docx（11页珍藏版）》请在冰点文库上搜索。
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=2tT二n-k1符号或m（n-kT）比特;
最小距离为d的本原RS码的生成多项式为
g（x）=（x-：
）（x-：
2）（x-：
3）（x-：
d-2）
式中的m是一个任意整数。
令信息元多项式为：
2k—1
m（x）=m0m1m2x亠亠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）=r2t_1x2^1r2t-2x2t_2r2x2jxr0
则编程的码多项式为
c（x）二xn-ka（x）r（x）
除法电路构成的RS编码辭
（2）根据校验码多项式h（x）构造的除法编码器
设校验多项式为：
h（x）=hkxkhk^x1^1亠亠h1xh0
系统码的多项式为:
C（X）二Cn_iXn「5_2乂"25—kx"5_—必—1Cq
它的前k位系数：
Cn_1,Cn_2「，Cn_k是已知的信息位，而后n-k位系数:
Cn_k_1,Cn^_2，…,C1,C0是需求的校验位。
码多项式必是生成多项式g（x）的背式，所以
C（x）=q（x）g（x）C（x）乞n_1,：
：
g（x）=n_k,rq（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）xn的最低位次数至少为n次，而在h（x）C（x）的乘积中
xnT,x门一2,…,xk的次数为0。
X—1的系数：
xn_2的系数：
Cn_2血Cn_2_lhiCn_2_khk
而
k
工Cn—jhj=0i=0,1,2,…，n-k
ro
由于h（x）为首一多项式，hk=1，故上式可写为
k-1
Cn_k_i八'Cn—i—jhji=1,2,,n-k
j=0
上式展开为：
Cn-k^=-（Cn-1hoCn_2hiCn-khk-1）
Cn_k_2=—（Cn_2hoCn-3h1Cn-k-1hk-1）
-
Cn-k-（n-k）-Co八（Ckho“柑⑴qhk_1）
由上式看出码字C的第一个码元Cn—kJ可由k个信息元Cn_1,Cn_2,…，cn_k与
h（x）的系数相乘得到，而由Cn_2,Cn<,…，Cn_k,Cn_kJ可得到第二个校验元
Cn_k_2，再由Cn_3,,Cn_k信息元和第一、第二校验元5_k_1,Cn_k—2可得到
第三校验元Cn_k_3。
按这样的线性关系递推，一直可求得所有的n-k个校验
'“■■B
兀Cn-k-1，Cn-k-2，，C1,Co0
瓦循坏码k级編码器
（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）=（xa）（xa2）（xa3）（xa4）（xa5）（xa6
=x6-a10x5a14x4-a4x3a6x2a9xa6
由分圆多项式多项式：
g（x）=（x2x1）（x4x1）
aGF（16）是本原域元素，它是多项式x4x1的根，则
a4a1=0
或a4=a1
以x4x1为模的GF（24）的元素如下表：
a0=1
0001
82斗
a=a+1
0101
a
0010
93
a=a+a
1010
2a
0100
a=a+a+1
0111
3a
1000
113丄2
a=a+a+a
1110
a4=a+1
0011
a=a+a+a+1
1111
a5=a2+a
0110
a=a+a+1
1101
63+2
a=a+a
1100
a=a+1
1001
a=a+a+1
1011
15.
a=1
0001
GF（24）中每个元素都可表示成它的自然基地1,a,a2,a3（在域GF
（2）上）的线性组合，如下形式：
32
asaa?
aa〔aa°
因此在GF（24）上的24进制RS码，它的编码电路可用k或n-k级24进制寄存器实现。
本例是用n-k=6级乘法器电路实现，如下图。
图中的移位积存器必
须是由能积存16进制的元件组成，这可用4级触发器组成的移存器完成。
a10,a14,a4,a6,a9常乘器可用模2加法器构成。
在域GF（24）上的系数a10,a14,a4,a6,a9可用自然基地表示为如下形式:
103213121110
a（83aa?
aa〔aa°）-83aa?
aa〔aa°a
=a3（a3a21）a2（a3a2a1）a1（a3a2a）a0（a2a1）
=@3a2aja3（a?
a?
a「a°）a2（a?
a「a°）a（a?
a。
）
14/32、17161514
a（a3aa2aa1aa0）=a3aa2aa1aa
32
=a°aa3aa?
a（a「a。
）
4320765-.4
a（a3aa2aa1aa0a）=a3aa2aa1aa0a
=a3（a3a1）a2（a3a2）a1（a2a）a0（a1）
=@3a?
）a3（a?
aja2（a?
a「a°）a@a。
）
63—2.9—876
a（a3aa2aa1aa0）=a3aa2aa1aa0a
二a3（a3a）a2（a21）a1（a3a1）a0（a3a2）
32
=@3a1ao）a（a?
a°）a@3a〔a°）a（a?
aj
a9（a3a3a2a2a1aa0）=a3a12a2a11a1a10a0a9
aia°）a@a〔）
=a3（a3a2a1）a2（a3a2a）a1（a2a1）a0（a3a）=@3a2a°）a3Q3a?
aja2Q3a?
a10（a3a3+a2a2+a[a+a0）
=@3+a?
+a〔）a3+（a3+a?
+印+a°）a2+（a?
式中：
a3'=a3+a2十a〔
a2〕=83+a?
+a〔
a*=a2+a〔+a0
a0|=a2+a0
□j'
a：
'
GF（24）中乘a10的转换电路如下表示:
aia°）a（a?
a。
）
a
HJLII
H」lHK
a。
GF（214）中乘a10电路
GF（24）中乘a14的转换电路如下表示:
a?
'=a?
ai
GF（214）中乘a14电路
a31=a3a?
GF（24）中乘a4的转换电路如下表示:
a31二a。
二a3
a*=a2
a。
'=a3
GF（214）中乘a14电路
GF（24）中乘a6的转换电路如下表示:
GF（214）中乘a6电路
GF（24）中乘a9的转换电路如下表示:
a3Ja3a2a0
a?
i=a3a?
ai
ai、a3a2a「a。
ao'a?
ai
GF（214）中乘a9电路
[15,9,7]RS编码器具体实现电路如下图所示:
符界输入
[⑸9f?
]RS编码瞬
工作过程如下：
（1）门打开，开关拨到符号输入端，所有移存器清0。
然后将6个16进制信息符号，一边送入移存器，一边送入信道。
注意每一节拍移动一个16进制符号。
（2）6个16进制符号送入移存器后，完成除法运算，移存器中的就是余式。
此时，门关闭，开关拨到下面。
再经过6个节拍的移动，得到所有6个校验元,并且跟随信息元送入信道，完成一个码字的编码过程。
（3）清洗积存器，打开门，开始第二组信息元的编码。
升级会员 