Reed–Solomon 碼原理：錯誤與抹除、有限域，以及 QR Code 和 Voyager 的應用

RS(n, k) 把 k 個資料符號編成一個包含 n 個符號的碼字。採用 GF(256) 時，一個符號是一個位元組（byte），即八個位元（bit）。同一位元組內有幾個位元出錯，仍然只算一個符號錯誤。

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

「有三個符號正確」不等於知道哪三個正確，更不代表可以修正四個位置未知的錯誤。只有錯誤時，上限為⌊(n−k)/2⌋，冗餘數為奇數便須向下取整。超出保證範圍後，解碼可能失敗，亦可能錯誤修正成另一個有效碼字。

先以較容易手算的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(256) 不像 GF(7) 這類素數域，不能把普通整數加法當作域內加法。

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，再減去除以生成多項式 g(x) 所得的餘式，便得到可被 g(x) 整除的 c(x)。此處有限域的特徵為二，減法等同 XOR。校驗符號的計算必須使用有限域運算，不能改用普通數值除法或浮點多項式運算。

這個循環碼構造與前面的求值型例子，是理解 RS 碼的不同方法。未訂明係數慣例、座標對應及縮放方式，就不能假設兩者會把同一份輸入編成相同的位元組序列。縮短碼可在指定資料位置加入虛擬零符號，完成編碼後不傳送這些位置。

設接收多項式為 v(x)，在生成多項式的根上求值：Sⱼ=v(α^(b+j))，j=0,…,r−1。這些值稱為伴隨式（syndrome）。出現非零值，表示接收序列不符合碼字條件；但全部為零，並不能證明它與原本傳送的資料相同。若損壞剛好把一個有效碼字變成另一個有效碼字，檢查仍會通過。

1. 計算伴隨式，並取得已知的抹除位置。
2. 用 Berlekamp–Massey 算法或擴展 Euclid 算法等方法，求出錯誤定位多項式。
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 的CIRC（Cross-Interleaved Reed–Solomon Code）結合 C2=RS(28, 24) 與 C1=RS(32, 28)。編碼由 C2 經交錯排列到 C1，解碼則反過來。單看每個組成碼，都可修正兩個位置未知的符號錯誤；整個系統亦會利用資料重排及抹除資訊。ECMA-130 附錄 C 說明了相關配置。

DVD-ROM 的 ECMA-267 結合垂直方向 RS(208, 192) 與水平方向 RS(182, 172)，不能把 DVD 的配置也叫作 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) 的表格，再核對實際規格的參數，有助分清數學原理與產品能保證的修復範圍。本文例子用來解釋原理，並非符合指定標準的完整編碼器或解碼器。