里德-所羅門錯誤更正

又稱: 里德-所羅門碼, Reed–Solomon 碼, RS 碼, Reed-Solomon

定義

里德-所羅門錯誤更正是讓受損的 QR Code 仍能掃描的數學方法。它在資料中加入檢查碼字,讓讀取器在一定上限內,重建遺失或錯誤的位元組。

起源與更廣的應用

里德-所羅門碼由 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
  • 區塊交錯排列,以分散連續損壞

常見問題

QR Code 裡的里德-所羅門是什麼?

它是在資料中加入額外碼字的錯誤更正方法。掃描器用這些碼字重建受損或無法讀取的碼字。

里德-所羅門碼是誰發明的?

是 Irving S. Reed 與 Gustave Solomon,他們在 1960 年發表。這類編碼現在用於光碟、通訊與大多數二維條碼。

為什麼中間放了標誌的 QR Code 仍然能用?

標誌遮住的模組,可以由里德-所羅門錯誤更正重建。只要被遮住的區域在錯誤更正容量之內,且定位圖案完整,就能運作。

來源與標準

所有名詞