里德-所罗门纠错

又称: 里德-所罗门码, Reed–Solomon 码, RS 码

定义

里德-所罗门纠错是让受损二维码仍能扫描的数学方法。它在数据里加入校验码字,让读取器能在一定限度内重建缺失或出错的字节。

起源与更广泛的应用

里德-所罗门码由欧文·里德(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
  • 各块交错排列,以分散突发损坏

常见问题

二维码里的里德-所罗门是什么?

它是一种纠错方法,在数据后面加入额外的码字。扫描器利用它们重建损坏或无法读取的码字。

里德-所罗门码是谁发明的?

欧文·里德和古斯塔夫·所罗门,他们在 1960 年发表了这种码。如今它用于光盘、通信和大多数二维条码。

为什么中间放了 Logo 的二维码还能用?

Logo 遮住的模块,里德-所罗门纠错可以重建。只要被遮住的面积在纠错能力范围之内,并且定位图案完好,它就能工作。

来源与标准

全部术语