起源與更廣的應用
里德-所羅門碼由 Irving S. Reed 與 Gustave Solomon 於 1960 年提出。它以整個符號(通常是位元組)而不是單一位元為單位運作,因此擅長處理刮痕或污漬這類集中的連續損壞。
同一類編碼保護著 CD、DVD 與藍光光碟上的資料,也用於部分數位電視與衛星鏈路,以及其他二維條碼,包括 Data Matrix ECC 200、Aztec Code 與 PDF417。
QR Code 如何使用
QR Code 把每個 8 位元的碼字視為有限體 GF(256) 的元素,該體由本原多項式 x^8 + x^4 + x^3 + x^2 + 1(十六進位 0x11D)建構。資料碼字除以一個生成多項式,所得的餘式就成為附加在後的錯誤更正碼字。
較大的 QR Code 會把資料分成多個區塊,每個區塊有自己的錯誤更正碼字。碼字放入格線時,各區塊會交錯排列,讓單一片損壞分散到許多區塊,而不是壓垮其中一個。
能修復多少
一個區塊有 n 個錯誤更正碼字時,解碼器最多能修正 n/2 個位置未知的碼字,或最多 n 個位置已知的碼字(稱為抹除)。混合情況則遵循每個錯誤算兩個、每個抹除算一個的規則。
這也是為什麼有一塊乾淨、平整區域被標誌蓋住的 QR Code 仍然能掃描:聰明的讀取器可能把被遮住的區域視為抹除,而隨機損壞則比較難修,因為解碼器要先找出損壞在哪裡。
- 位置未知的錯誤:最多為錯誤更正碼字數的一半
- 抹除(位置已知):最多與錯誤更正碼字數相同
- 體:GF(256),多項式 0x11D
- 區塊交錯排列,以分散連續損壞