《计算机组成与体系结构（原书第4版）》 —2.7.3　里德-所罗门纠错码

2.7.3　里德-所罗门纠错码

汉明码在期望错误很少的情况下工作得很好。固定磁盘驱动器的错误等级为亿分之一位。我们刚刚研究的3位汉明码很容易纠正这种类型的错误。然而，在有多个相邻位被损坏的情况下，汉明码是无用的。这种类型的错误称为突发错误。由于接触不当和环境压力，在可移动介质（如磁带和光盘上）突发错误是常见的。

如果我们预料错误发生在块中，那么就应该使用一个在块级别上工作的纠错代码，而不是在位级别上工作的汉明码。可以认为里德-所罗门(RS)纠错码是一种CRC，它对整个字符进行操作而不是只对几个位进行操作。RS码像CRC一样，具有系统性，即奇偶校验字节附加到一个信息字节块上。使用以下参数定义RS（n，k）码：

●s为字符（或“符号”）中的位数

●k为s位字符包含的数据块数

●n为码字中的位数

RS(n，k)能够纠正k个信息字节中的(n-k)/2个错误。

因此，流行的RS（255，223）码使用223个8位信息字节和32个特征字节以形成有255字节的码字。它会纠正信息块中的16个错误字节。

RS码的生成多项式是由一个定义在伽罗华域的抽象数学结构上的多项式给出。（对伽罗华的具体讨论超出了本书的范围。见本章结尾处的参考资料。）RS生成多项式为：

其中t=n-k；x是整个字节（或符号）；g（x）工作在域GF（2s）上。（注意：这个多项式是在伽罗华域上展开的，这与普通代数使用的整数域有很大不同）

使用以下公式计算n字节RS码字：

其中i（x）是信息块。

尽管它们背后有令人生畏的代数运算，但RS纠错算法很适合在计算机硬件中实现。它们用在大型计算机的高性能磁盘驱动器以及存储音乐和数据的光盘上。这些实现将是在第7章中描述。