リード・ソロモン符号の数学 — 有限体 GF(2⁸) から Voyager・QR・Blu-ray まで

通常のデータ通信では「ビット列をそのまま送る」と考えがちですが、RS 符号の発想はまったく異なります。データを多項式の係数とみなし、その多項式を複数の点で評価 (代入)した値を送信するのです。

たとえばデータが 3 シンボル [a₀, a₁, a₂] なら、多項式 f(x) = a₀ + a₁x + a₂x² を構成し、これを x = α⁰, α¹, α², ..., α⁶ の 7 点で評価して [f(α⁰), f(α¹), ..., f(α⁶)] の 7 シンボルを送信します。受信側は 7 個の値のうち 3 個が正しければ (= 2 個まで誤りがあっても) 元の 3 次未満の多項式を一意に復元できます。

一般化すると: RS(n, k) は k シンボルのデータから n シンボルの符号語を生成し、最大 t = (n - k) / 2 シンボルの誤りを訂正できます。

RS 符号の演算は有限体 (Galois Field) 上で行います。実数や整数ではなく、有限個の元からなる体です。コンピュータで扱う場合の標準は GF(2⁸) = GF(256) で、1 シンボル = 1 バイト (0-255) に対応します。

GF(2⁸) の元は 8 ビットの多項式として表現されます:

例: 0b10000011 = x⁷ + x + 1 = 131 (10進)

加算: XOR (繰り上がりなし)
  0b10000011 ⊕ 0b00000101 = 0b10000110

乗算: 多項式の積 mod 既約多項式
  既約多項式 (QR/CD 標準): p(x) = x⁸ + x⁴ + x³ + x² + 1 = 0x11D

なぜ有限体が必要なのか? 通常の整数では乗算の結果が無限に大きくなり、コンピュータでの表現が難しくなります。有限体では加減乗除のすべてが体の中で閉じる (結果が必ず 0-255 に収まる) ため、固定長のバイト演算だけで完結します。さらに「0 以外のすべての元に逆元が存在する」ため、除算も定義でき、多項式の連立方程式を解くことができます。

α = 0x02 (x) を原始元とすると、α⁰ = 1, α¹ = 2, α² = 4, ..., α⁷ = 128, α⁸ = α⁴ + α³ + α² + 1 = 29, ... と 255 個の非零元をすべて生成できます (α²⁵⁵ = 1 に戻る)。この巡回性が RS 符号の構造の基礎です。

実用上の RS 符号化は「多項式評価」ではなく、等価で効率的な生成多項式 (generator polynomial) による方法を使います。

RS(n, k) の生成多項式 g(x) は:

g(x) = (x - α⁰)(x - α¹)(x - α²)...(x - α^{n-k-1})
     = (x - 1)(x - α)(x - α²)...(x - α^{2t-1})

符号化手順:

1. データ多項式 d(x) = d_{k-1}x^{k-1} + ... + d₁x + d₀
2. d(x) を x^{n-k} 倍して上位に移動: d(x) · x^{n-k}
3. これを g(x) で割った剰余 r(x) を計算
4. 符号語 c(x) = d(x) · x^{n-k} - r(x) (GF(2⁸) では減算 = 加算 = XOR)

こうして得られた c(x) は g(x) で割り切れます。受信側で割り算して余りが 0 でなければ誤りが発生したと判定できます。

RS 符号の復号は、符号化より格段に複雑です。大まかな流れは以下の 4 ステップ:

Step 1: シンドローム計算

受信語 r(x) を α⁰, α¹, ..., α^{2t-1} に代入して 2t 個のシンドローム S₁, S₂, ..., S_{2t} を求めます。すべて 0 なら誤りなし。

Sⱼ = r(αʲ)   (j = 0, 1, ..., 2t-1)
// 誤りなし → c(αʲ) = 0 (g(x)の根だから) → Sⱼ = 0

Step 2: 誤り位置多項式 σ(x) の求解

シンドロームから、誤りの位置を根として持つ多項式 σ(x) を求めます。代表的なアルゴリズムは Berlekamp-Massey 法 (1968-1969) と Euclidean 法。Berlekamp-Massey は計算量 O(t²) で効率的です。

Step 3: 誤り位置の特定 (Chien Search)

σ(x) に α⁰, α¹, ..., α^{n-1} を順に代入し、σ(αⁱ) = 0 となる i を探します。この全探索を Chien Search (1964) と呼びます。

Step 4: 誤り値の計算 (Forney Algorithm)

誤りの位置がわかったら、各位置の誤り値 (正しい値との差) を Forney の公式 (1965) で算出し、受信語を修正します。

QR コードは RS 符号を GF(2⁸) 上で使用します (ISO/IEC 18004)。4 つの誤り訂正レベルはそれぞれ異なる (n, k) パラメータを持ちます:

QR コードの中央にロゴを重ねるデザインが可能なのは、H レベルの RS 符号が 30% の欠損を訂正できるためです。ただし「30%」はシンボル単位の上限であり、欠損がファインダーパターンやフォーマット情報に集中すると読み取り不能になる場合があります。

音楽 CD (Red Book, IEC 60908) は CIRC (Cross-Interleaved Reed-Solomon Code) と呼ばれる二重 RS 構造を使います:

• C1 符号: RS(32, 28) — 最大 2 シンボル訂正 (バースト誤り対策の第 1 段)
• インターリーブ: C1 の出力を 28 フレーム分散させる
• C2 符号: RS(28, 24) — 最大 2 シンボル訂正 (第 2 段)

この二重構造 + インターリーブにより、ディスク表面の約 2.5mm の傷 (= 約 4,000 ビットのバースト誤り) まで完全に訂正できます。CD が多少の傷で音飛びしないのはこの技術のおかげです。

DVD は RS(208, 192) + RS(182, 172) の二重構造、Blu-ray はさらに強力なピッカリング符号 (Picket Code)を採用しています。光ディスクの世代が進むにつれてトラックピッチが狭くなり、同じ傷でもより多くのビットに影響するため、RS 符号のパラメータも強化されてきました。

1977 年に打ち上げられた Voyager 2 は、当初 Golay 符号 (畳み込み符号) のみを搭載していました。しかし 1986 年の天王星接近時、地球からの距離が 30 億 km に達し、信号強度が木星時の 1/400 に低下。そこで NASA/JPL は地上からソフトウェアアップデートで RS 符号を追加しました。

採用されたのは CCSDS (255, 223) — GF(2⁸) 上の RS 符号で、255 シンボル中 32 シンボルが冗長 (最大 16 シンボル訂正)。これを既存の畳み込み符号と連接 (concatenated code) して使うことで、天王星・海王星の鮮明な画像撮影が可能になりました。

CCSDS (Consultative Committee for Space Data Systems) はこの RS(255, 223) を宇宙通信の国際標準として規格化しています (CCSDS 131.0-B)。現在の火星探査機 (Mars Reconnaissance Orbiter 等) も同じ RS パラメータを基本とし、さらに Turbo 符号や LDPC 符号と組み合わせています。

欧州の地上デジタル放送規格 DVB-T (ETSI EN 300 744) では、トランスポートストリーム (MPEG-2 TS, 188 バイト/パケット) に 16 バイトの RS パリティを付加した RS(204, 188) を外符号 (outer code) として使います。内符号には畳み込み符号 + Viterbi 復号を配置する連接符号構成です。

日本の ISDB-T (ARIB STD-B31) も同じ RS(204, 188) を外符号に採用しています。テレビ受信時にブロックノイズが出る前に RS 符号が誤りを訂正しており、一般視聴者が誤り訂正の存在を意識することはほぼありません。

RS 符号は 60 年以上の実績がありますが、万能ではありません:

• 復号計算量: O(n·t) 〜 O(t²) — シンボル数が大きくなると重い
• シャノン限界からの距離: RS 符号は MDS (Maximum Distance Separable) 符号であり、最小距離は理論最大ですが、符号化率が低い場合にシャノン限界に近づくには長い符号長が必要
• バースト誤り専用ではない: ランダム誤りにも対応するが、バースト誤りにはインターリーブとの組み合わせが必須

2000 年代以降、通信分野では Turbo 符号 (1993, Berrou et al.) や LDPC 符号 (1960 Gallager, 1996 再発見) がシャノン限界に迫る性能で主役になりつつあります。5G NR では LDPC (データチャネル) + Polar 符号 (制御チャネル) が標準です。

しかし RS 符号はストレージ (QR, 光ディスク, RAID 6) や短ブロック・低遅延が求められる場面で依然として現役であり、LDPC/Turbo と連接して外符号として使われることも多い。「枯れた技術」こそが信頼性の証です。

• Reed-Solomon 符号 = データを多項式の係数とみなし、有限体上で評価した値を冗長として付加する代数的符号
• GF(2⁸) 上で演算: 加算 = XOR、乗算 = 多項式積 mod 既約多項式、1 シンボル = 1 バイト
• RS(n, k) は最大 t = (n-k)/2 シンボルの誤りを訂正 (MDS 符号 — 最小距離が理論最大)
• 復号: シンドローム → Berlekamp-Massey → Chien Search → Forney Algorithm
• QR コード (ISO/IEC 18004): L/M/Q/H の 4 レベルで RS パラメータを切替
• CD/DVD: CIRC (二重 RS + インターリーブ) で約 2.5mm の傷を訂正
• 深宇宙通信: CCSDS RS(255, 223) — Voyager 2 は天王星接近時にソフトウェア更新で追加
• 地デジ: DVB-T / ISDB-T の RS(204, 188) が外符号として稼働
• 現代は LDPC / Turbo / Polar が主流だが、RS は短ブロック・ストレージで現役