起源与更广泛的应用
里德-所罗门码由欧文·里德(Irving S. Reed)和古斯塔夫·所罗门(Gustave Solomon)于 1960 年提出。它以整个符号(通常是字节)而不是单个比特为单位工作,因此擅长应对划痕或污渍这类成片的突发损坏。
同一类编码保护着 CD、DVD 和蓝光光盘上的数据,用于一些数字电视和卫星链路,也用在包括 Data Matrix ECC 200、Aztec 码和 PDF417 在内的其他二维条码中。
二维码如何使用它
二维码把每个 8 位码字看作有限域 GF(256) 中的一个元素,该域由本原多项式 x^8 + x^4 + x^3 + x^2 + 1(十六进制 0x11D)构造。数据码字被生成多项式除,余数就成为附加在其后的纠错码字。
较大的二维码把数据分成若干块,每块都有自己的纠错码字。这些块在码字放入网格时会被交错排列,这样一处损坏就会分散到许多块上,而不会压垮某一块。
它能纠正多少
一块中有 n 个纠错码字时,解码器可以纠正最多 n/2 个位置未知的码字,或最多 n 个位置已知的码字(称为擦除)。混合情形遵循这样的规则:每个错误算两个,每个擦除算一个。
这就是为什么被 Logo 盖住一块干净平整区域的二维码仍能扫描:聪明的读取器可以把被遮住的区域当作擦除处理,而随机损坏更难修复,因为解码器首先得找到它们。
- 未知位置的错误:最多为纠错码字数的一半
- 擦除(已知位置):最多等于纠错码字数
- 有限域:GF(256),多项式 0x11D
- 各块交错排列,以分散突发损坏