Reed–Solomon 錯誤更正碼：從有限體、錯誤與抹除到 QR Code 和 Voyager

RS(n, k) 將 k 個資料符號編成含 n 個符號的碼字。使用 GF(256) 時，每個符號是一個位元組；同一個位元組內即使有多個位元損壞，仍只算一個符號錯誤。

錯誤（error）是數值不正確，而且解碼器不知道其位置；抹除（erasure）則是數值未知，但位置已知。對最小距離 d=n−k+1 的 RS 碼，一般唯一解碼的保證條件為2e+s≤n−k，其中 s 是抹除數，e 是抹除位置以外的錯誤數。

只知道「有 3 個符號正確」，不代表知道是哪 3 個，也不保證能修正 4 個位置未知的錯誤。只有錯誤時，上限為⌊(n−k)/2⌋；冗餘數是奇數時要無條件捨去小數部分。超過保證範圍，可能解碼失敗，也可能誤更正成另一個碼字。

為了方便追蹤計算，先使用GF(7)，而不是 GF(256)。GF(7) 的元素是 0 到 6，運算取除以 7 的餘數。把資料 [1, 2, 3] 寫成 f(x)=1+2x+3x²，再代入七個相異的點 x=0,1,…,6。

傳送的數列是 [1, 6, 3, 6, 1, 2, 2]。這個構造不會把原始係數直接保留在開頭。只要知道三組正確的位置與數值，就能以內插法還原次數不超過二的多項式。

將兩個相異、次數不超過二的多項式相減，會得到非零且次數不超過二的多項式，因此最多只有兩個根。兩組七點求值結果至少有五個位置不同，這解釋了最小距離為五，以及能唯一修正兩個錯誤的原因。一般而言，把次數小於 k 的多項式代入 n 個相異點，最小距離為 n−k+1。達到這個 Singleton 界限的碼稱為最大距離可分碼（MDS）。

求值型構造需要有限體中有 n 個相異元素。GF(256) 中只使用非零元素的一般循環碼構造，以長度 255 為起點。不能因此把包含零元素的求值型構造或延伸碼，一律限制為最多 255 個符號。

在 GF(2⁸)=GF(256) 中，八個位元代表一個次數不超過七、係數為 0 或 1 的多項式。例如位元組數值 131（0x83）對應 x⁷+x+1。加法與減法都是 XOR；乘法則先求多項式的乘積，再取除以八次不可約多項式的餘式。這不是整數對 256 取餘數的運算。

0x83 XOR 0x05 = 0x86
p(x) = x⁸ + x⁴ + x³ + x² + 1 = 0x11D
0x80 × 0x02 = 0x1D   （採用此 p(x) 的有限體乘法）
α = 0x02
α⁰ = 1, α¹ = 2, …, α⁷ = 128, α⁸ = 29, α²⁵⁵ = 1

在採用 0x11D 的這種表示法中，0x02 是本原元素，其冪次會遍歷全部 255 個非零元素。每個非零元素都有乘法反元素；除了除以零未定義之外，運算結果都留在有限體內。與 GF(7) 這類質數體不同，GF(256) 的加法不能用一般整數加法代替。

QR Code 與 CD 使用 0x11D 表示法，但不是所有 RS 規格都採用相同參數。不可約多項式、本原元素、基底與符號順序都必須一致。只有 RS(255, 223) 這個名稱，不足以製作彼此相容的編碼器。

保留原始資料並附加同位檢查符號的方式，稱為系統式編碼（systematic encoding）。以下以 GF(256) 的循環碼構造為例，使用本原元素 α，以及 r=n−k 個連續冪次的根。起始指數 b 也是規格指定的參數。

g(x) = ∏ (x − α^(b+j))   j = 0, …, r−1
R(x) = d(x) x^r mod g(x)
c(x) = d(x) x^r − R(x)

將資料多項式 d(x) 乘上 x^r，再減去除以生成多項式的餘式，所得 c(x) 就能被 g(x) 整除。這裡的有限體具有特徵二，因此減法就是 XOR。計算同位檢查符號時，應使用有限體運算，不能套用一般除法或浮點數多項式計算。

這個循環碼表示法與前面的求值型範例，是理解 RS 碼的不同構造。若沒有指定係數慣例、座標對應與縮放方式，不能認定相同輸入會得到相同的位元組序列。縮短碼可以在指定的資料位置補入虛擬零符號後編碼，再省略這些位置、不予傳送。

令接收到的多項式為 v(x)，在生成多項式的根上計算Sⱼ=v(α^(b+j))，j=0,…,r−1，所得就是症候值（syndrome）。只要有非零症候值，就表示接收到的序列不符合碼字條件。然而，症候值全部為零，不能證明資料與傳送時完全相同：損壞可能把一個有效碼字變成另一個有效碼字，因而通過檢查。

1. 計算症候值，取得已知的抹除位置。
2. 使用 Berlekamp–Massey 法或擴展歐幾里得演算法等方法，求出錯誤定位多項式。
3. 用 Chien 搜尋找出根，再映射到符號位置。
4. 利用 Forney 公式等方法計算錯誤值並更正，重新檢查更正數量、位置與症候值是否一致。

例如，若係數順序定為 c(x)=Σcᵢxⁱ，位置 i 的定位值定為 Xᵢ=αⁱ，且 Λ(z)=∏(1−Xᵢz)，則根是z=Xᵢ⁻¹=α⁻ⁱ。根的指數不一定直接等於陣列索引；若陣列從最高次項開始儲存，還需要再轉換。

重新檢查也無法完全排除誤更正，必要時應搭配其他錯誤偵測機制。若要防範刻意竄改，則需要訊息鑑別碼（MAC）或數位簽章等機制；RS 碼不能取代訊息鑑別。

QR Code 使用 GF(256) 的 RS 碼。在 QR 的術語中，一個碼字（codeword）是八個位元，也就是一個位元組，相當於前面 RS 說明中的一個符號，並非整個含 n 個符號的 RS 碼字。DENSO WAVE 提供的 L/M/Q/H 比例，是以全部 QR 碼字數為分母的概略復原能力：

這些比例不是容許損壞的影像面積，也不是安全的 Logo 覆蓋比例。版本與更正等級會決定區塊配置、資料數與同位檢查符號數，因此把各等級寫成固定的「冗餘比例」也不精確。更正能力必須逐一計算每個 RS 區塊，不能任意挪用其他區塊的同位檢查符號。

定位圖樣或格式資訊損壞，以及拍攝條件不佳，都可能導致讀取失敗。現行規格為 ISO/IEC 18004:2024。本文比例依據 DENSO WAVE 的公開說明，並非重製規格全文。更多細節可參考QR Code 錯誤更正等級說明。

CD 的交錯式 Reed–Solomon 碼（CIRC）使用 C2=RS(28, 24) 與 C1=RS(32, 28)。編碼順序是從 C2 經過交錯配置，再到 C1；解碼方向相反。單獨看每個組成碼，都能更正兩個位置未知的符號錯誤，完整系統還會運用資料重排與抹除資訊。ECMA-130 附錄 C 說明了這個結構。

DVD-ROM 的 ECMA-267 則結合垂直方向的 RS(208, 192) 與水平方向的 RS(182, 172)，不能也稱為 CIRC。2004 年的 BD-RE 白皮書說明，Blu-ray 結合保護主要資料的長距離碼（LDC，Long Distance Code），以及協助指出叢發錯誤位置的BIS（Burst Indicator Subcode）。

交錯配置會把連續損壞分散到多個碼字。RS 碼本身也能把同一位元組內的多個位元錯誤視為一個符號錯誤，因此適合處理叢發錯誤；不是每一種叢發錯誤都必須依賴交錯配置才能修正。實際刮痕耐受度取決於方向、形狀、讀取設備、資料配置與解碼策略，不能只憑刮痕長度保證完整還原。

NASA/JPL 的技術資料指出，Voyager 為了天王星與海王星階段的更遠通訊距離，已搭載實驗性的 RS 資料編碼器。後續的操作與軟體更新，不應被描述成完全靠軟體新增一個原本不存在的編碼器。結合 RS 碼與迴旋碼的串接編碼，是改善遠距離資料傳輸的一環；資料壓縮與地面接收設備改善則是另外的工作。

太空通訊規格 CCSDS 131.0-B-5（2023 年）第 4 章規定八位元符號，以及 t=8 或 16 的 RS 更正能力。RS(255, 223) 有 32 個同位檢查符號，一般保證可更正最多 16 個位置未知的符號錯誤。CCSDS 也指定有限體表示法與生成多項式的根，不能直接套用前面的 QR 參數。

截至 2026 年 10 月 21 日，JAXA 文件清單已列出131.0-B-6（2026 年 4 月）。本文公式參照 B-5，並未將它視為最新版。實作時應查閱適用的現行規格與任務規範，也不應推論特定火星探測任務一定將同一種 RS 碼與 Turbo 或 LDPC 碼併用。

DVB-T 的 ETSI EN 300 744 V1.6.2 採用縮短 RS(204, 188) 作為外碼：在 188 個位元組後加入 16 個同位檢查位元組，可更正最多八個位置未知的位元組錯誤。系統也使用交錯配置與內層迴旋碼。這是 DVB-T 的配置，不能推廣到每一代數位廣播規格。

MDS 表示在給定 n 與 k 下達到最大的最小距離，不代表考量雜訊統計與軟判決資訊後，就一定最接近夏農容量極限。當通道適合使用長區塊、軟資訊與迭代解碼時，Turbo 或 LDPC 碼也是選項。

解碼計算量必須分階段討論。令 r=n−k 為同位檢查符號數，並把一次有限體運算視為固定成本。直接計算症候值需要 O(nr)，一般 Berlekamp–Massey 定位多項式計算需要 O(r²)。若沒有抹除、最多處理 t=⌊r/2⌋ 個錯誤，針對 n 個候選位置進行 Chien 搜尋的成本為 O(nt)。更一般地，若搜尋用的定位多項式次數為 ℓ，成本就是 O(nℓ)；將錯誤與抹除位置合併的定位多項式，其次數為 ℓ=e+s。這些是各階段的運算次數，並非特定實作或硬體的實測執行時間。

• 確認符號大小、n 與 k，並區分位置未知的錯誤與位置已知的抹除。
• 一般唯一更正的保證條件是 2e+s≤n−k；超出範圍可能失敗，也可能誤更正。
• 對齊有限體多項式、基底、本原元素、起始根、陣列順序與縮短方式。
• 症候值全為零，不等於資料完全未變，也不能證明沒有遭到竄改。
• 不要把 QR 的復原比例或光碟的更正能力，換算成影像面積或刮痕長度的保證。

先手算 GF(7) 的表格，再查閱實際規格的參數，有助於分清楚數學原理與產品的復原保證。本文範例用於說明原理，不是符合特定標準的完整編碼器或解碼器實作。