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