伽罗华域

Yeemusic

以下为文献概要：
先容如何生成GF(2^m)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后mod(2^m)。
实例分析如何编码及纠错。(实际上就是求解多项式方程组的过程，在实际工程算法中运用到的钱氏搜索法(Chien Search)，Berlekamp-Massey 算法都是为了快速求解方程组，从而纠错)。
附录部分为GF(2^8)上的元素列表。
13.2 RS编码和纠错算法
13.2.1. GF(2m)域
RS(Reed-Solomon)码在伽罗华域(Galois Field，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)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
[例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-01 GF(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.2 RS的编码算法
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.3 RS码的纠错算法
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)就是采用上述方法导出的。