リードソロモン誤り訂正は、前方誤り訂正符号の一つで、デジタルデータの欠損や誤りを検出・訂正するために広く使われています。符号化は、まずデータから多項式を構成し、その多項式を複数の点で評価して得られる値列（シンボル列）を送信または記録する、という仕組みで動作します。元のデータを超えて多くの点で評価（オーバーサンプリング）しておくことで冗長性を持たせ、受信側は多数の正しい点に基づいて元の多項式を復元できるため、受信中に生じた一部の「悪い」点（誤りや消失）があってもデータを復元できます。

基本概念とパラメータ

  • 有限体（ガロア体）: リードソロモン符号は主に GF(2^m) 上のシンボル（バイト単位なら m=8）で動作します。
  • 符号長 n と情報長 k: 一般に原始的なリードソロモン符号は n = 2^m − 1 を最大長とし、情報シンボル数を k、符号語全体の長さを n と表します。冗長性は n − k です（短縮符号もよく使われます）。
  • 訂正能力: t = floor((n − k) / 2) は訂正可能な符号誤り（位置不明な誤り）の最大個数です。既知の位置（消失＝erasures）の場合は最大 n − k 個まで訂正できます。一般には 2e + s ≤ n − k（e は誤り数、s は消失数）という条件で訂正可能性が決まります。

符号化の流れ（概念的）

  • メッセージシンボル列を係数とみなして多項式 m(x) を作る。
  • 選んだ n 個の評価点 a1, a2, …, an に対して m(ai) を計算する（これが符号語のシンボル）。
  • 得られた n 個のシンボルを送信または媒体に記録する。これにより情報の冗長コピーが作られる。
  • 実装上は「系統符号化（systematic encoding）」を行い、元の情報シンボルをそのまま符号語の一部に保持し、残りを冗長シンボルとして付加することが多いです。

復号の概要

  • 受信した符号語からまずシンドローム（syndromes）を計算し、誤りの有無とその性質の手がかりとする。
  • シンドロームに基づいて誤り位置多項式（error locator polynomial）を求める（代表的手法：Berlekamp–Massey アルゴリズム、あるいは拡張ユークリッドアルゴリズム）。
  • 誤り位置が分かれば Forney のアルゴリズムなどで誤り幅（エラー値）を計算し、該当位置を修正する。
  • 上記の処理で訂正が成功すれば元の多項式（＝元のデータ）を復元できる。

実装上の工夫と派生技術

  • 短縮符号: 実際のアプリケーションでは n を小さく調整した「短縮」リードソロモン符号が多用されます（例えば GF(256) 上で n≤255）。
  • インターリーブ: 連続するビットやバイトの塊に生じるバースト誤りに対しては、インターリーブ（符号語を時間や位置で分散させる）を併用してバースト誤りをランダムな単位誤りに変換します。
  • 組み合わせ復号: 誤り（errors）と消失（erasures）が混在する状況に対しては、混合条件 2e + s ≤ n − k を用いて復号を行います。

代表的な例と応用

リードソロモン符号は多くの商用システムで重要な役割を果たしています。たとえば、CD、DVD、Blu-ray Disc などの光ディスクメディアでは、読み取りノイズや傷に対する耐性を与えるために用いられています。通信分野でも DSL や WiMAX などのデータ伝送技術、衛星／放送（DVB、ATSC）などで利用されます。また、QRコードやバーコード、RAID-6 のような複数ディスク障害に対する分散符号にもリードソロモンが使われています。

数値例

よく使われる例として GF(256) 上の RS(255,223) があります。ここでは n − k = 32 なので t = 16、すなわち最大 16 バイトの位置不明誤りを訂正できます。実際には必要に応じて短縮して使うことが多いです。

利点と注意点

  • 利点：高い訂正能力、柔軟な設計（n, k, m の選択が可能）、バースト誤りに対して強い（インターリーブと併用）。
  • 注意点：有限体上の演算（特に乗除算）を必要とするため、ハードウェア/ソフトウェア実装のコストや遅延に配慮が必要。長さや符号率の選択により必要な計算量が変わる。

まとめると、リードソロモン符号は「多項式の過剰評価」による冗長化を通じて、受信側で元のデータを復元できる強力な誤り訂正方式です。その理論的な単純さと実用上の柔軟性から、ストレージや放送、通信など広範な分野で採用されています。