リードソロモン符号とは？誤り訂正の定義・仕組みと応用例

リードソロモン符号の基本原理と誤り訂正の仕組み、実用例（CD/DVD、Blu‑ray、放送、通信）を図解でわかりやすく解説

著者: Leandro Alegsa

07-12-2025 22:04

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

基本概念とパラメータ

有限体（ガロア体）: リードソロモン符号は主に 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 の選択が可能）、バースト誤りに対して強い（インターリーブと併用）。
注意点：有限体上の演算（特に乗除算）を必要とするため、ハードウェア/ソフトウェア実装のコストや遅延に配慮が必要。長さや符号率の選択により必要な計算量が変わる。

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

概要

リード・ソロモン符号はブロック符号である。つまり、一定の入力データのブロックが、一定の出力データのブロックに処理される。最も一般的なR-S符号（255, 223）の場合、223個のリード-ソロモン入力シンボル（各8ビット長）が255個の出力シンボルに符号化されます。

R-S ECC方式の多くはシステマティック方式である。これは、出力されるコードワードの一部が入力データをそのまま含んでいることを意味します。
リードソロモンのシンボルサイズを8ビットとしたのは、これより大きなシンボルサイズのデコーダを現在の技術で実装することが困難なためである。この設計により、最長のコードワードは255シンボルとなる。
標準的な（255, 223）リードソロモン符号は、各コードワードで最大16個のリードソロモン記号の誤りを訂正することができます。各シンボルは実際には8ビットなので、このコードは内部の畳み込み復号器による16個の短いバーストエラーを訂正できることを意味します。

リードソロモン符号は、畳み込み符号と同様、透明な符号である。つまり、チャネルシンボルがどこかで反転していたとしても、デコーダは動作します。結果は、元のデータの補数となる。しかし、リードソロモン符号は、仮想ゼロフィルを使用すると透明性が失われる。このため、リードソロモン復号の前にデータの意味（真か補数か）を解決しておくことが必須となる。

Voyagerプログラムの場合、R-S符号を(7, 1/2) 畳み込み（ビタビ）内部符号と連結することで、ほぼ最適な性能となる。各エラーを訂正するために2つのチェックシンボルが必要なので、コードワードあたり合計32個のチェックシンボルと223個の情報シンボルが必要となります。

また、コンボリューション符号化する前に、リード・ソロモン符号語をシンボル単位でインターリーブすることができる。これにより、コードワード内のシンボルが分離されるため、ビタビ復号器からのバーストが1つのコードワード内の複数のリードソロモンシンボルを妨害する可能性が低くなる。

基本的な考え方

リード・ソロモン符号の重要な考え方は、符号化されたデータをまず多項式として可視化することである。この符号は、任意のk個の異なる点が最大でk-1の次数の多項式を一意に決定するという代数学の定理に依存している。

送信者は、k個の{displaystyle k} データ点を表す有限体上の次数k - 1 {displaystyle k-1} $k-1$ 多項式を決定する。この多項式は、様々な点での評価によって「符号化」され、これらの値が実際に送信される。送信中に、これらの値の一部が破損することがある。そのため、実際にはk点以上の値が送信される。十分な数の値が正しく受信されれば、受信者は元の多項式が何であったかを推測し、元のデータを復号することができる。

リード・ソロモン符号は、曲線を補間して修正するのと同じように、データのブロックにある一連の誤りを埋めて、元の曲線を描いた多項式の係数を復元することができる。

沿革

1960年、当時MITリンカーン研究所に所属していたアーヴィング・S・リードとグスタフ・ソロモンによって考案された暗号である。彼らの代表的な論文は、"Polynomial Codes over Certain Finite Fields "というタイトルだった。この論文が書かれた当時は、まだデジタル技術が発達しておらず、このコンセプトを実現することはできませんでした。1982年、RS符号が初めて量産品に適用されたのは、コンパクトディスクで、2つのインターリーブRS符号が使われた。1969年にElwyn BerlekampとJames Masseyによって大距離RS符号の効率的な復号化アルゴリズムが開発された。現在、RS符号はハードディスクドライブ、DVD、電気通信、デジタル放送のプロトコルに使用されている。

百科事典を検索する