RS编码和纠错算法Word下载.docx
《RS编码和纠错算法Word下载.docx》由会员分享，可在线阅读，更多相关《RS编码和纠错算法Word下载.docx（16页珍藏版）》请在冰点文库上搜索。
mod（α3＋α＋1）=α＋1
α4
mod（α3＋α＋1）=α2＋α
α5
mod（α3＋α＋1）=α2＋α1＋1
α6
mod（α3＋α＋1）=α2＋1
α7
mod（α3＋α＋1）=α0
α8
……
用二进制数表示域元素得到表13-01所示的对照表
表13-01GF（23）域中与二进制代码对照表,
GF（23）域元素
二进制对代码
（000）
（001）
（010）
（100）
（011）
（110）
（111）
（101）
这样一来就建立了GF（23）域中的元素与3位二进制数之间的一一对应关系。
用同样的方法可建立GF（28）域中的256个元素与8位二进制数之间的一一对应关系。
在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。
现仍以GF（23）域中运算为例：
加法例：
α0＋α3
=001＋011
=010=α1
减法例：
与加法相同
乘法例：
α5·
α4
=α（5＋4）
mod7
=α2
除法例：
α5/α3
α3/α5
=α－2
=α（－2＋7）
=α5
取对数：
log（α5）=5
这些运算的结果仍然在GF（23）域中。
13.2.2RS的编码算法
RS的编码就是计算信息码符多项式
除以校验码生成多项式
之后的余数。
在介绍之前需要说明一些符号。
在GF（2m）域中，符号（n，k）RS的含义如下：
m
表示符号的大小，如m=8表示符号由8位二进制数组成
n
表示码块长度，
k
表示码块中的信息长度
K=n－k
=2t
表示校验码的符号数
t
表示能够纠正的错误数目
例如，（28，24）RS码表示码块长度共28个符号，其息代码的长度为24，检验码有4个检验符号。
在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式
，RS校验码生成多项式的一般形式为
（13－2）
式中，m0是偏移量，通常取K0
=0或K0
=1，而（n-k）≥2t
（t为要校正的错误符号数）。
下面用两个例子来说明RS码的编码原理。
[例13.2]
设在GF（23）域中的元素对应表如表13-01所示。
假设（6，4）RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式
为
（13－3）
并假设RS校验码的2个符号为Q1和Q0，
的剩余多项式
这个多项式的阶次比
的阶次少一阶。
如果K0
=1，t
=1，由式（13－2）导出的RS校验码生成多项式就为
=
（13－4）
根据多项式的运算，由式（13－3）和式（13－4）可以得到
m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0
=（x－α）（x－α2）Q（x）
当用x
=α和x
=α2代入上式时，得到下面的方程组，
经过整理可以得到用矩阵表示的（6，4）RS码的校验方程：
求解方程组就可得到校验符号：
在读出时的校正子可按下式计算：
[例13.3]
在例13.2中，如果K0
=0，t
=
（13－5）
根据多项式的运算，由（13－3）和（13－5）可以得到下面的方程组：
方程中的αi也可看成符号的位置，此处i
=0，1，…，5。
求解方程组可以得到RS校验码的2个符号为Q1和Q0，
（13－6）
假定mi为下列值：
信息符号
m3
=α0
=001
m2
=α6
=101
m1
=α3
=011
m0
=α2
=100
校验符号
Q1
Q0
=α4
=110
校正子
s0
=0
s1
代入（13－6）式可求得校验符号：
13.2.3RS码的纠错算法
RS码的错误纠正过程分三步：
（1）计算校正子（syndrome），
（2）计算错误位置，（3）计算错误值。
现以例13.3为例介绍RS码的纠错算法。
校正子使用下面的方程组来计算：
为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。
如果计算得到的s0和s1不全为0，则说明有差错，但不知道有多少个错，也不知道错在什么位置和错误值。
如果只有一个错误，则问题比较简单。
假设错误的位置为αx，错误值为mx，那么可通过求解下面的方程组：
得知错误的位置和错误值。
如果计算得到s0
=α2和s1
=α5，可求得αx
=α3和mx
=α2，说明m1出了错，它的错误值是α2。
校正后的m1
=m1′＋mx
，本例中m1=0。
=0，而s1≠0，那基本可断定至少有两个错误，当然出现两个以上的错误不一定都是s0
=0和s1≠0。
如果出现两个错误，而又能设法找到出错的位置，那么这两个错误也可以纠正。
如已知两个错误
和
的位置
，那么求解方程组：
就可知道这两个错误值。
CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码（Reed
Solomon
Product－likeCode，RSPC）就是采用上述方法导出的。
CopyRight©
Octopus2000
附录1
GF（8）元素如下GF（2^8）1+x^2+x^3+x^4+x^8
Fieldelement（polynomialnotation）
4-tuplerepresentation
0
0000_0000（0
）
1
0000_0001（1
a^1
0000_0010（2
a^2
0000_0100（4
a^3
0000_1000（8
a^4
0001_0000（16）
a^5
0010_0000（32）
a^6
0100_0000（64）
a^7
1000_0000（128）
a^8
0001_1101（29）
a^9
0011_1010（58）
a^10
0111_0100（116）
a^11
1110_1000（232）
a^12
1100_1101（205）
a^13
1000_0111（135）
a^14
0001_0011（19）
a^15
0010_0110（38）
a^16
0100_1100（76）
a^17
1001_1000（152）
a^18
0010_1101（45）
a^19
0101_1010（90）
a^20
1011_0100（180）
a^21
0111_0101（117）
a^22
1110_1010（234）
a^23
1100_1001（201）
a^24
1000_1111（143）
a^25
0000_0011（3
a^26
0000_0110（6
a^27
0000_1100（12）
a^28
0001_1000（24）
a^29
0011_0000（48）
a^30
0110_0000（96）
a^31
1100_0000（192）
a^32
1001_1101（157）
a^33
0010_0111（39）
a^34
0100_1110（78）
a^35
1001_1100（156）
a^36
0010_0101（37）
a^37
0100_1010（74）
a^38
1001_0100（148）
a^39
0011_0101（53）
a^40
0110_1010（106）
a^41
1101_0100（212）
a^42
1011_0101（181）
a^43
0111_0111（119）
a^44
1110_1110（238）
a^45
1100_0001（193）
a^46
1001_1111（159）
a^47
0010_0011（35）
a^48
0100_0110（70）
a^49
1000_1100（140）
a^50
0000_0101（5
a^51
0000_1010（10）
a^52
0001_0100（20）
a^53
0010_1000（40）
a^54
0101_0000（80）
a^55
1010_0000（160）
a^56
0101_1101（93）
a^57
1011_1010（186）
a^58
0110_1001（105）
a^59
1101_0010（210）
a^60
1011_1001（185）
a^61
0110_1111（111）
a^62
1101_1110（222）
a^63
1010_0001（161）
a^64
0101_1111（95）
a^65
1011_1110（190）
a^66
0110_0001（97）
a^67
1100_0010（194）
a^68
1001_1001（153）
a^69
0010_1111（47）
a^70
0101_1110（94）
a^71
1011_1100（188）
a^72
0110_0101（101）
a^73
1100_1010（202）
a^74
1000_1001（137）
a^75
0000_1111（15）
a^76
0001_1110（30）
a^77
0011_1100（60）
a^78
0111_1000（120）
a^79
1111_0000（240）
a^80
1111_1101（253）
a^81
1110_0111（231）
a^82
1101_0011（211）
a^83
1011_1011（187）
a^84
0110_1011（107）
a^85
1101_0110（214）
a^86
1011_0001（177）
a^87
0111_1111（127）
a^88
1111_1110（254）
a^89
1110_0001（225）
a^90
1101_1111（223）
a^91
1010_0011（163）
a^92
0101_1011（91）
a^93
1011_0110（182）
a^94
0111_0001（113）
a^95
1110_0010（226）
a^96
1101_1001（217）
a^97
1010_1111（175）
a^98
0100_0011（67）
a^99
1000_0110（134）
a^100
0001_0001（17）
a^101
0010_0010（34）
a^102
0100_0100（68）
a^103
1000_1000（136）
a^104
0000_1101（13）
a^105
0001_1010（26）
a^106
0011_0100（52）
a^107
0110_1000（104）
a^108
1101_0000（208）
a^109
1011_1101（189）
a^110
0110_0111（103）
a^111
1100_1110（206）
a^112
1000_0001（129）
a^113
0001_1111（31）
a^114
升级会员 