Chapter 11
リード・ソロモン符号 — QR コード・CD・宇宙通信の主役
最も広く使われている誤り訂正符号. CD の傷、QR コードの汚れ、ボイジャー探査機からの信号、DVD、地上デジタル放送、 RAID-6、分散ストレージ——すべてリード・ソロモン (RS) 符号が守っている。
1960 年、MIT リンカーン研究所の Irving Reed と Gustave Solomon がわずか 5 ページの論文で発表した。 当時は復号アルゴリズムが無く実用にならなかったが、 1968 年にバーレカンプ・マッシー法が現れて一気に実用化した。
強さの理由は 2 つ:
- MDS 符号である（06 章のシングルトン限界で等号）——冗長を 1 ビットも無駄にしていない
- バイト単位で扱うので、バースト誤りに極めて強い
1. 構成
パラメータ
\(\mathrm{GF}(q)\)（通常\(q = 2^8 = 256\)、つまり 1 シンボル = 1 バイト）上で:
シングルトン限界\(d \le n-k+1\)で等号 → MDS 符号 ✓
訂正能力:
- 誤り（位置が未知）: \(t = (n-k)/2\) シンボルまで
- 消失（位置が既知）: \(n-k\) シンボルまで（2 倍）
- 混在: \(2\times(\text{誤り数}) + (\text{消失数}) \le n-k\)
生成多項式
\(\alpha\)を\(\mathrm{GF}(q)\)の原始元として:
BCH（10 章）と同じ「連続する\(2t\)個の根」だが、係数が\(\mathrm{GF}(q)\)なので最小多項式を取る必要がない （\(\alpha^j\)自身が\(\mathrm{GF}(q)\)の元なので\(x-\alpha^j\)がそのまま使える）。 だから\(\deg g\)がちょうど\(2t\)になり、無駄が出ない——これが MDS になる理由である。
符号化
CRC と同じ組織符号形式:
データの後ろに\(2t\)個の検査シンボル（パリティバイト）を付ける。
2. なぜバースト誤りに強いのか
これが RS 最大の実用的価値である.
RS はシンボル（1 バイト）単位で誤りを数える。 1 バイトの中で 1 ビット壊れようが 8 ビット全部壊れようが、どちらも「1 シンボル誤り」である。
たとえば RS(255,223)（\(t=16\)）は 16 シンボル訂正できる。これは:
- 最悪の場合でも連続 16 バイト = 128 ビットの破壊を完全に修復
- CD の場合、約 2.5 mm の傷に相当する範囲を復元できる
ビット単位の符号（ハミングや BCH）で 128 ビット連続の誤りを訂正しようとすると、 桁違いに大きな冗長が必要になる。 「誤りが固まって起きる」という現実の性質を、シンボル化によって味方につけているわけである。
インターリーブとの組み合わせ
さらに強くするために、複数の符号語をばらして交互に並べる（インターリーブ）。
長いバーストが来ても、各符号語から見れば「ぽつぽつと数シンボル」に散らばるので、 それぞれの訂正能力内に収まる。
CD の CIRC (Cross-Interleaved Reed-Solomon Code) はこれを 2 段構えで行い、 最大 4000 ビット（約 2.4 mm）の連続傷を訂正できる。
3. 復号アルゴリズム（この章の本体）
受信語\(r(x) = T(x) + e(x)\)から誤りを特定して除去する。
ステップ 1: シンドローム計算
- \(X_l = \alpha^{i_l}\): 誤り位置（\(i_l\)が壊れたバイトの番号）
- \(Y_l\): 誤り値（そのバイトに XOR された値）
- \(\nu\): 実際の誤り個数（未知）
全部 0 なら誤り無しとして終了。
ステップ 2: 誤り位置多項式 Λ(x) を求める
キーとなる関係式（ニュートンの恒等式）の導出:
\(\Lambda(X_l^{-1}) = 0\)（定義より）。両辺に\(Y_l X_l^{j+\nu}\)を掛けて\(l\)について和を取る:
各項を展開すると\(\sum_l Y_lX_l^{j+\nu-i} = S_{j+\nu-i}\)なので:
これは\(\Lambda\)の係数に関する連立一次方程式である（\(j=1,\dots,\nu\)）。 未知数\(\nu\)個、式\(\nu\)本。有限体上の連立方程式なので、03 章の掃き出し法で解ける。
03 章で「有限体の上では実数と同じ手順で連立方程式が解ける」と強調した理由がここで回収される. 誤り訂正の核心は、結局のところ有限体上の線形代数である。
バーレカンプ・マッシー法
上の連立方程式を直接解く（ガウス消去、\(O(t^3)\)）よりも効率的な方法がある。 上の式は「線形帰還シフトレジスタ (LFSR) が\(S_1,S_2,\dots\)を生成する」という形をしている。 その最短の LFSR を求める問題に読み替えると、\(O(t^2)\)で解ける。
アルゴリズムの骨子:
- \(\Lambda(x)=1\)、\(L=0\)（現在の次数）から開始
- 各シンドローム\(S_j\)について、現在の\(\Lambda\)が予測する値とのズレ（discrepancy）\(\Delta\)を計算
- \(\Delta \neq 0\)なら、過去の\(\Lambda\)を使って補正
- 必要なら\(L\)を増やす
13 章の LFSR と同じ数学がここに出てくる. 暗号（乱数生成）と誤り訂正（復号）という無関係に見える 2 つが、 「線形帰還シフトレジスタ」という同一の対象を、片や作る側、片や推定する側から扱っている。 ちなみに「短い LFSR で生成できてしまう」ことは、暗号にとっては弱点である（13 章）。
ステップ 3: チェン探索（誤り位置の特定）
\(\Lambda(x)=0\)の根を、\(x = \alpha^{-i}\)（\(i=0,1,\dots,n-1\)）と総当たりで探す。 \(\Lambda(\alpha^{-i})=0\)なら位置\(i\)が誤り。
（総当たりだが、有限体の要素は\(n\)個しかないので\(O(nt)\)で終わる。 ハードウェアでは全位置を並列評価できる。）
ステップ 4: フォニー・アルゴリズム（誤り値の計算）
誤り評価多項式\(\Omega(x)\)を
と定義すると、誤り値は
（\(\Lambda'\)は形式的微分。標数 2 では偶数次の項が消えるので計算が簡単。）
導出のあらすじ: \(\Omega\)と\(\Lambda\)の定義から \(\Omega(x) = \sum_l Y_l X_l \prod_{p\neq l}(1-X_px)\)と書ける。 \(x = X_l^{-1}\)を代入すると\(l\)以外の項が消え、 分母の\(\Lambda'(X_l^{-1}) = -X_l\prod_{p\neq l}(1-X_pX_l^{-1})\)と組み合わせると上式が出る ∎
ステップ 5: 訂正
（\(\mathrm{GF}(2^m)\)なので引き算は XOR。）
4. 実例: QR コードの RS 符号
QR コードは\(\mathrm{GF}(2^8)\)、既約多項式\(x^8+x^4+x^3+x^2+1\)（0x11D）、原始元\(\alpha=2\)を使う。
| 誤り訂正レベル | 冗長率 | 復元可能な汚れ |
|---|---|---|
| L | 7% | 約 7% |
| M | 15% | 約 15% |
| Q | 25% | 約 25% |
| H | 30% | 約 30% |
QR コードの真ん中にロゴを載せられるのはこのため. レベル H なら約 30% が欠けても復元できるので、中央にロゴを置いても読み取れる。 「壊れることを前提に、あらかじめ冗長を持たせておく」という設計思想の勝利である。
5. RS 符号の応用一覧
| 分野 | 符号 | 備考 |
|---|---|---|
| CD | CIRC (RS(32,28) + RS(28,24)) | 2 段インターリーブ |
| DVD | RS-PC (208,192)+(182,172) | 積符号 |
| QR コード | RS over GF(256) | 4 段階のレベル |
| ボイジャー探査機 | RS(255,223) + 畳み込み符号 | 連接符号 |
| 地上デジタル放送 | RS(204,188) | 外符号 |
| RAID-6 | RS（2 パリティ） | 消失訂正 |
| 分散ストレージ | RS(k+m, k) | Erasure Coding |
6. まとめ
| 項目 | 内容 |
|---|---|
| 構成 | \(g(x)=\prod_{j=1}^{2t}(x-\alpha^j)\)、\(\mathrm{GF}(2^8)\)上 |
| 最適性 | MDS（\(d=n-k+1\)、冗長に無駄なし） |
| 訂正能力 | 誤り\(t\)個 / 消失\(2t\)個 |
| 強み | シンボル単位なのでバースト誤りに極めて強い |
| 復号 | シンドローム → BM 法 → チェン探索 → フォニー |
| 数学的基盤 | GF(2^8)（05 章）+ 有限体上の線形代数（03 章） |
これで第 II 部（誤り検出・訂正）は完了である。次章から暗号に入る。 第 I 部で作った代数——特に\(\mathrm{GF}(2^8)\)と合同算術——が、再び主役として登場する。