リードソロモン符号（Reed–Solomon）の仕組みと実装：理論から実用まで徹底解説
エバープレイ編集部はじめに — リードソロモン符号とは何か
リードソロモン符号（Reed–Solomon, RS）は、誤り訂正符号の中でも極めて重要かつ広く用いられている線形ブロック符号です。1960年に Irving S. Reed と Gustave Solomon により提案されて以来、デジタル放送、光ディスク、バーコード、ストレージ、衛星・深宇宙通信など、多くの分野で実用化されています。特徴は有限体（Galois Field）上の多項式を用いて設計され、最大距離分解能（MDS: Maximum Distance Separable）を達成するため、与えられた冗長度で最大の訂正能力を得られる点にあります。
基礎数学：有限体と多項式表現
RS符号は主に GF(2^m) のような有限体上で定義されます。符号長 n は一般に最大で 2^m - 1 を取り、情報長を k とすると、パリティ長は n-k となり、訂正可能な誤り数 t は (n-k)/2 です。符号語は有限体上の多項式 p(x) の値（評価）として扱う評価符号（evaluation code）の一種です。
具体的には、情報データを係数とする多項式 m(x)（次数 < k）を取り、有限体の n 個の異なる評価点 α_0, α_1, ..., α_{n-1} に対して c_i = m(α_i) を計算して符号語 c = (c_0, ..., c_{n-1}) を得ます。この評価方式により、RS符号が MDS 性質（任意の k シンボルから元のメッセージを再構成可能）を持つことが分かります。
パラメータと性質
符号長 n：通常 2^m - 1（非短縮）だが、任意の n ≤ 2^m で短縮して使える。
情報長 k：メッセージシンボル数。
最小距離 d：d = n - k + 1（MDS 性）であり、これにより t = ⌊(d-1)/2⌋ = ⌊(n-k)/2⌋ の誤り訂正能力をもつ。
シンボル単位の符号：各シンボルは GF(2^m) の要素であり、バイト単位（m=8）で使う実装が一般的。
符号化の仕組み（系統符号化）
実装上は系統符号（systematic code）での符号化がよく用いられます。情報係数をそのまま符号語の最初の k シンボルに置き、残りの n-k シンボルをパリティとして付加する方法です。多項式的に言えば、情報多項式 m(x) を x^{n-k} で乗じてから生成多項式 g(x) で割った剰余 r(x) を求め、符号語を x^{n-k} m(x) - r(x) として得ることでパリティが生成されます。生成多項式 g(x) は連続する 2t 個の根（一般に α, α^2, ..., α^{2t}）を持つよう設計されます。
復号の基本手順
RS 復号は以下の主要なステップで構成されます。
シンドローム計算：受信語 r(x) に対してシンドローム S_j = r(α^j)（j=1..2t）を計算します。全シンドロームがゼロなら誤りなしと判断できます。
誤り位置多項式（エラーロケータ）の求解：Berlekamp–Massey アルゴリズムや拡張ユークリッド法（Euclidean algorithm）によって誤り位置多項式 σ(x) を求めます。σ(x) の根 α^{-i} が誤り位置を示します。
誤り評価多項式（エラーエバリュエータ）：誤りの大きさ（シンボル単位の誤差値）を求めるための多項式 ω(x) を計算します。
フォーニーの公式（Forney）：誤り位置から各誤り値 e_i を計算し、受信語から差し引くことで訂正を行います。
代表的な復号アルゴリズムの詳細
Berlekamp–Massey アルゴリズムはシンドローム列から最小帰還多項式（つまり誤り位置多項式）を効率よく求める手法です。計算量はおおむね O(t^2) で、ハードウェア実装にも適しています。別のアプローチとして拡張ユークリッド法を用いる方法は、シンドローム多項式と x^{2t} の最大公約多項式を求めることで σ(x) と ω(x) を同時に得ます。
誤り位置の根の探索（Chien search）は多項式 σ(x) の各有限体要素を代入して零かどうかを調べるアルゴリズムで、並列化に適しています。シンボル単位の誤り値は Forney の公式によって効率よく算出できます。
消失・擦れ誤り（erasures）と組合せ訂正
RS は誤り訂正（errors）だけでなく消失（erasures）にも強い特性があります。消失位置が既知であれば、消失 t_e と誤り t_f に対して 2 t_f + t_e ≤ n - k を満たす限り復元できます。消失処理はシンドロームの構成や復号手順を簡略化することが可能で、ストレージやパケット通信で実用的に用いられます。
短縮符号化と拡張
RS 符号は短縮（shortening）によって任意の長さに合わせられます。例えば GF(256) 上の最大長 255 の RS を用いて、必要な n に合わせて先頭に固定値（通常ゼロ）を付加・削除することで効率的に実装できます。さらに多重符号化や交差符号化（interleaving）と組み合わせることでバースト誤りに対する耐性を高める設計が一般的です。
実用上の注意点と最適化
有限体演算の効率化：GF(2^m) の乗算や逆数計算はルックアップテーブル（対数表と指数表）や多項式乗算の最適化で高速化できます。ハードウェア実装ではシリアル・パラレル回路設計、ソフトウェアではSIMDやGPUを用いた並列化が効果的です。
複合符号化：畳み込み符号やターボ符号、LDPC などと連結して使うことで、RS の誤り訂正と他符号の誤り訂正の長所を生かせます（例：深宇宙通信での連結符号）。
数値安定性と実装上の落とし穴：有限体は実数ではないため「丸め誤差」は起きませんが、テーブルサイズ、端からの短縮、複数バイトの扱いなど実装ミスで解読不能になることがあるため、テストベクターや既知のベンチマークで検証することが重要です。
応用例
QRコードやバーコード：誤りや汚損のある領域からの復元に使用。
光ディスク（CD/DVD/Blu-ray）：読み取りエラーやスクラッチに対する訂正。
デジタル放送（DVB）や衛星通信：パケット損失や伝送誤りに対する保護。
分散ストレージ・RAID：データ片の欠損・損傷に対する再構築（例：オブジェクトストレージでのエラー耐性用のパリティ分散）。
拡張と代替技術
近年の符号理論では、LDPC やターボ符号、Polar 符号などが高いチャネル容量近傍での性能を示しますが、RS の「シンボル誤りに対する高い確実性」「MDS 性」「実装の確立された手法」は依然として重要です。加えて、列（シンボル）単位の消失訂正が必要なアプリケーションでは RS の利点が際立ちます。
実装例と擬似コード（概念レベル）
基本的な復号の流れ（概念）：
受信 r を受け取る → シンドローム S を計算
S が全てゼロなら完了
Berlekamp–Massey で σ(x) を求める
Chien search で誤り位置を見つける
Forney で各誤り値を計算 → 受信語を訂正
実際のコードは有限体演算ライブラリ（例：GF(2^8) の乗算・逆元テーブル）を前提に実装されます。多くのオープンソース実装やハードウェアIPが存在するため、用途に応じて選択するのが実務的です。
まとめ
リードソロモン符号は、その堅牢性・柔軟性・MDS 性により、今日でも多くのシステムで採用されています。有限体と多項式評価に基づく理論は一見難解ですが、Berlekamp–Massey、Chien search、Forney の各手法を組み合わせることで効率的な復号が可能です。用途に応じて短縮、交差符号化、並列化などの工夫を施すことで、ソフトウェア・ハードウェアの双方で高性能に実装できます。
参考文献
Reed–Solomon coding (practical overview and implementation notes)
I.S. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields", 1960
投稿者プロフィール
