RS编码和纠错算法.docx
《RS编码和纠错算法.docx》由会员分享，可在线阅读，更多相关《RS编码和纠错算法.docx（19页珍藏版）》请在冰点文库上搜索。
RS编码和纠错算法
DataMatrix将有效信息（数字字母等）编码成0~255内的数字表示（编码方式参考：
http:
//en.wikipedia.org/wiki/Data_Matrix）。
为了及时发现数据传输时的错误，使用RS编解码来进行错误检测校验。
RS码可以看成伽罗华域GF（2^m）上的元素，dm码的元素0~255正好对应伽罗华域GF（2^8）上的256个元素。
通过编码时添加冗余信息，可以有效校验数据是否正确传输。
以下为文献概要：
1）介绍如何生成GF（2^m）域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后mod（2^m）。
2）实例分析如何编码及纠错。
（实际上就是求解多项式方程组的过程，在实际工程算法中运用到的钱氏搜索法（ChienSearch），Berlekamp-Massey算法都是为了快速求解方程组，从而纠错）。
3）附录部分为GF（2^8）上的元素列表。
13.2RS编码和纠错算法
13.2.1.GF（2m）域
RS（Reed-Solomon）码在伽罗华域（GaloisField，GF）中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF（2m）=GF（28）中的元素或称符号。
GF（28）表示域中有256个元素，除0，1之外的254个元素由本原多项式P（x）生成。
本原多项式
的特性是
得到的余式等于0。
CD-ROM用来构造GF（28）域的
是
（13－1）
而GF（28）域中的本原元素为
α=（00000010）
下面以一个较简单例子说明域的构造。
[例13.1] 构造GF（23）域的本原多项式
假定为
α定义为
=0的根，即
α3＋α＋1=0
和α3 =α＋1
GF（23）中的元素可计算如下：
0
mod（α3＋α＋1）=0
α0
mod（α3＋α＋1）=α0 =1
α1
mod（α3＋α＋1）=α1
α2
mod（α3＋α＋1）=α2
α3
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
mod（α3＋α＋1）=α1
……
用二进制数表示域元素得到表13-01所示的对照表
表13-01GF（23）域中与二进制代码对照表,
GF（23）域元素
二进制对代码
0
（000）
α0
（001）
α1
（010）
α2
（100）
α3
（011）
α4
（110）
α5
（111）
α6
（101）
这样一来就建立了GF（23）域中的元素与3位二进制数之间的一一对应关系。
用同样的方法可建立GF（28）域中的256个元素与8位二进制数之间的一一对应关系。
在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。
现仍以GF（23）域中运算为例：
加法例：
α0＋α3 =001＋011
=010=α1
减法例：
与加法相同
乘法例：
α5·α4 =α（5＋4） mod7
=α2
除法例：
α5/α3 =α2
α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 =1，由式（13－2）导出的RS校验码生成多项式就为
=
（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 =α6 =101
Q0 =α4 =110
校正子
s0 =0
s1 =0
代入（13－6）式可求得校验符号：
Q1 =α6 =101
Q0 =α4 =110
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。
如果计算得到s0 =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
升级会员 