2024年4月23日发(作者：板钰)
.
Data Matrix将有效信息(数字字母等)编码成0~255内的数字表示 （编码方式参考：
/wiki/Data_Matrix）。为了及时发现数据传输时的错误，使用RS编解码
来进行错误检测校验。RS码可以看成伽罗华域GF(2^m)上的元素，dm码的元素0~255正好
对应伽罗华域GF(2^8)上的256个元素。通过编码时添加冗余信息，可以有效校验数据是否
正确传输。
以下为文献概要：
1) 介绍如何生成GF(2^m)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后
mod(2^m)。
2) 实例分析如何编码及纠错。(实际上就是求解多项式方程组的过程，在实际工程算法中
运用到的钱氏搜索法(Chien Search)，Berlekamp-Massey 算法都是为了快速求解方程
组，从而纠错)。
3) 附录部分为GF(2^8)上的元素列表。
13.2 RS编码和纠错算法
13.2.1. GF(2)域
RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简
要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2) = GF(2)中的元素或称符号。
8
GF(2)表示域中有256个元素，除0，1之外的254个元素由本原多项式
P
(
x
)生成。本原多
m
8
m
项式的特性是得到的余式等于0。CD-ROM用来构造GF(2)域的
8
是
(13－1)
而GF(2)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
8
[例13.1] 构造GF(2)域的本原多项式
3
假定为
α定义为
3
= 0的根，即
α＋α＋1 = 0
.
.
和 α = α＋1
GF(2)中的元素可计算如下：
0
α
α
α
α
α
α
α
α
α
……
8
7
6
5
4
3
2
1
0
3
3
mod(α＋α＋1) = 0
mod(α＋α＋1) = α = 1
mod(α＋α＋1) = α
mod(α＋α＋1) = α
mod(α＋α＋1) = α＋1
mod(α＋α＋1) = α＋α
mod(α＋α＋1) = α＋α＋1
mod(α＋α＋1) = α＋1
mod(α＋α＋1) = α
mod(α＋α＋1) = α
31
30
32
321
32
3
32
31
30
3
用二进制数表示域元素得到表13-01所示的对照表
表13-01 GF(2)域中与二进制代码对照表,
GF(2)域元素
0
α
α
α
α
α
α
α
3
6
5
4
3
2
1
0
3
3
二进制对代码
(000)
(001)
(010)
(100)
(011)
(110)
(111)
(101)
这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方法
8
可建立GF(2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过
3
程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例：
加法例：α＋α = 001＋011
= 010 = α
减法例：与加法相同
1
03
.
2024年4月23日发(作者：板钰)
.
Data Matrix将有效信息(数字字母等)编码成0~255内的数字表示 （编码方式参考：
/wiki/Data_Matrix）。为了及时发现数据传输时的错误，使用RS编解码
来进行错误检测校验。RS码可以看成伽罗华域GF(2^m)上的元素，dm码的元素0~255正好
对应伽罗华域GF(2^8)上的256个元素。通过编码时添加冗余信息，可以有效校验数据是否
正确传输。
以下为文献概要：
1) 介绍如何生成GF(2^m)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后
mod(2^m)。
2) 实例分析如何编码及纠错。(实际上就是求解多项式方程组的过程，在实际工程算法中
运用到的钱氏搜索法(Chien Search)，Berlekamp-Massey 算法都是为了快速求解方程
组，从而纠错)。
3) 附录部分为GF(2^8)上的元素列表。
13.2 RS编码和纠错算法
13.2.1. GF(2)域
RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先简
要介绍一下伽罗华域。
CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2) = GF(2)中的元素或称符号。
8
GF(2)表示域中有256个元素，除0，1之外的254个元素由本原多项式
P
(
x
)生成。本原多
m
8
m
项式的特性是得到的余式等于0。CD-ROM用来构造GF(2)域的
8
是
(13－1)
而GF(2)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
8
[例13.1] 构造GF(2)域的本原多项式
3
假定为
α定义为
3
= 0的根，即
α＋α＋1 = 0
.
.
和 α = α＋1
GF(2)中的元素可计算如下：
0
α
α
α
α
α
α
α
α
α
……
8
7
6
5
4
3
2
1
0
3
3
mod(α＋α＋1) = 0
mod(α＋α＋1) = α = 1
mod(α＋α＋1) = α
mod(α＋α＋1) = α
mod(α＋α＋1) = α＋1
mod(α＋α＋1) = α＋α
mod(α＋α＋1) = α＋α＋1
mod(α＋α＋1) = α＋1
mod(α＋α＋1) = α
mod(α＋α＋1) = α
31
30
32
321
32
3
32
31
30
3
用二进制数表示域元素得到表13-01所示的对照表
表13-01 GF(2)域中与二进制代码对照表,
GF(2)域元素
0
α
α
α
α
α
α
α
3
6
5
4
3
2
1
0
3
3
二进制对代码
(000)
(001)
(010)
(100)
(011)
(110)
(111)
(101)
这样一来就建立了GF(2)域中的元素与3位二进制数之间的一一对应关系。用同样的方法
8
可建立GF(2)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过
3
程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(2)域中运算为例：
加法例：α＋α = 001＋011
= 010 = α
减法例：与加法相同
1
03
.