Zhengzhou Oriole Xinda Electronic Information Co.,Ltd.
1
RS 纠错编码原理
―及其实现方法
陈文礼
January 08 于郑州
If you have any suggestion or criticism . please email to
ciciendi@163.com
QQ:83902112
Zhengzhou Oriole Xinda Electronic Information Co.,Ltd.
2
前言
随着越来越多的系统采用数字技术来实现,纠错编码技术也得到了越来越广
泛的应用。RS 码既可以纠正随机错误,又可以纠正突发错误,具有很强的纠错
能力,在通信系统中应用广泛。近些年来,随着软件无线电技术的发展,RS 编
码、译码一般都在通用的硬件平台上实现。通常采用基于 FPGA 的 VHDL 编码
硬件实现,或者在 DSP、单片机上用 C 和汇编编程软件实现。
RS 纠错编码涉及的领域很广,特别是设计到很多数学知识。这对那些对数
学不太感冒的工程技术人员来书是个不小的挑战。尽管讲 RS 编码的书籍很多,
但是那些书都是采用循序渐进,逐步引入的方式,从汉明码到循环码,从循环码
到 BCH 码,BCH 码再引入 RS 码。对于工程技术人员他们需要的是简明扼要的讲
解,和详细的实现方法。
本人写这篇文章的宗旨就是尽量最简单的语言,最简短的篇幅,来讲 RS 纠
错编码原理,把重点来放在实现方法上。
为了便于读者仿真,本文采样 MATLAB 程序实现,程序尽量符合硬件 C 语言
写法,读者经过简单修改即可应用到工程中去。
本文读者对象
本文是为那些初识 RS 编码的学生、工程技术人员而写,并不适合做理论研
究,如果你是纠错编码方面的学者、专家,那么本文并不适合你。
由于作者水平有限,错误在所难免,恳请读者批评指正。
陈文礼
2008-01 于郑州
Zhengzhou Oriole Xinda Electronic Information Co.,Ltd.
3
一、必备的一些代数知识
1、在纠错编码代数中,把以二进制数字表示的一个数据系列看成一个多项式。例如二进制
数字序列 10101111,可以表示成:
=
式中的
i
x
表示代码的位置,或某个二进制数位的位置,
i
x
前面的系数
i
a
表示码的
值。若
i
a
是一位二进制代码,则取值是 0 或 1。 ()
M
x 称为信息代码多项式。
多项式次数:
称系数不为 0 的
x
的最高次数为多项式 ()
f
x 的次数,记为 ()
f
x
∂
。
2、域
域在 RS 编码理论中起着至关重要的作用。
简单点说域 (2 )
m
GF 有 2
m
(设 2
m
=q )个符号
01 2
0, ,
q
αα α
−
且具有以下性质:
域中的每个元素都可以用
012 1
,,
m
a
α
αα
−
的和来表示。
1
1
q
α
−
=
α
为本原多项式 ()
p
x 的根。
运算规则有:
在纠错编码运算过程中,加、减、乘和除的运算是在伽罗华域中进行。现以
GF(2
4
)域中运算为例:
加法例:
10 8
0010 0111 0101
α
αα
+= + = =
(模 2 加法相当于0010 与0111异或)
减法运算与加法相同
乘法例:
810 (810)mod15 3
α
αα α
+
•= =
除法例:
8 10 2 2 15 13
/
α
ααα α
−−+
== =
不理解没关系,下面的例子也许对你有帮助。
例: m=4,
4
() 1
p
xxx=++ 求 (2 )
m
GF 的所有元素
: 因为
α
为 ()
p
x 的根 得到
4
10
αα
+
+= 或
4
1
αα
=
+ (根据运算规则)
Zhengzhou Oriole Xinda Electronic Information Co.,Ltd.
4
由此可以得到域的所有元素
元素 二进制对应
码
十进制对应
值
0 0 0000 0
0
α
1 0001 1
1
α
1
α
0010 2
2
α
2
α
0100 4
3
α
3
α
1000 8
4
α
1
α
+
0011 3
5
α
2
(1)
α
ααα
+
=+(mod ( ))p
α
0110 6
6
α
232
()
α
αααα
+=+(mod ( ))p
α
1100 12
7
α
32 3
() 1
αα α α α
+=++(mod ( ))p
α
1011 11
8
α
32
(1)1
αα α α
++= +(mod ( ))p
α
0101 5
9
α
23
(1)
α
ααα
+= +(mod ( ))p
α
1010 10
10
α
32
() 1
αα α α α
+=++(mod ( ))p
α
0111 7
11
α
232
(1)
α
αα ααα
++= + + (mod ( ))p
α
1110 14
12
α
32 32
() 1
αα α α α α α
++=+++(mod ( ))p
α
1111 15
13
α
32 32
(1)1
αα α α α α
+++=++(mod ( ))p
α
1101 13
14
α
32 3
(1)1
αα α α
++=+(mod ( ))p
α
1001 9
15
α
3
(1)1
αα
+=(mod ( ))p
α
0001 1
由此可以看出本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问
我们如何得到 ()
p
x 呢? 本原多项式 ()
p
x 的特性是
21
1
()
m
x
p
x
−
+
得到的余式等于 0。
由于作者也是工程技术人员,具体怎么得到
()
p
x ,也没有深究过。
Zhengzhou Oriole Xinda Electronic Information Co.,Ltd.
5
作者在设计 RS 编码时候都是根据 MATLAB 指令 rsgenpoly 来得到 ()
p
x 。
其格式为 rsgenpoly(n,k)
参数 n 为码长一般
21
m
n =−,k 为信息码元个数。
例如 m=4, 码长 n=15,信息码元长度为 9
GF(2
4
)的本原多项式可以根据指令
>>rsgenpoly(15,9)
得到:
ans = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
二、线性分组码的一些基本概念
1、线性分组码一般用 (,)nk 或 (,, )nkd 表示 n 为码长,k 为信息码元的数目,nk− 为监督
码元的数目。 d 表示码元距离。
定义:两个码组上对应位置上数字不同的个数称为码组的距离。
发送的码字
123 )
( , , ,...
n
ccccc=
接收的矢量
123 )
( , , ,...
n
rrrrr=
信道错误图样:
ecr=+
例如
c
=(1,1,0,0,0) r =(1,0,0,0,1)
e
=(1+1,1+0,0+0,0+0,0+1)=(0,1,0,0,1)
从而可以看出从左端起第 2 位和第 5 位是错误的。
2、校验矩阵概念
码长为 n,信息数为 k,监督数为 r。
这样的一组码形式为:
12 12
, ,... , , ,...
kr
cmm mpp p=
i
m 表示第i 个信息码,
j
p
表示第
j
个校验码
各个校验码可从下列线性方程组求得。
11 1 12 2 1 1 2
21 1 22 2 2 1 2
11 2 2 1 2
... 1 0 ... 0 0
... 0 1 ... 0 0
...
... 0 0 ... 1 0
kk r
kk r
rr rkk r
hm hm hm p p p
hm hm hm p p p
hm hm hm p p p
+++++++=
+++++++=
+++++++=
(1-1)
式中
ij
h
是常数
校验方程组可写成校验矩阵
评论0