リード・ソロモンエラー訂正
リードソロモン誤り訂正は、前方誤り訂正符号の一つです。データから構成される多項式をオーバーサンプリングすることで機能する。多項式はいくつかのポイントで評価され、その値が送信または記録されます。多項式を必要以上にサンプリングすると、多項式が過剰決定されてしまう。多くの」点を正しく受信していれば、「少数の」悪い点があっても、受信機は元の多項式を復元することができる。
リードソロモン符号は、CD、DVD、Blu-ray Disc、DSLやWiMAXなどのデータ伝送技術、DVBやATSCなどの放送システムなど、さまざまな種類の商用アプリケーションで使用されている。
概要
リード・ソロモン符号はブロック符号である。つまり、一定の入力データのブロックが、一定の出力データのブロックに処理される。最も一般的な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点以上の値が送信される。十分な数の値が正しく受信されれば、受信者は元の多項式が何であったかを推測し、元のデータを復号することができる。
リード・ソロモン符号は、曲線を補間して修正するのと同じように、データのブロックにある一連の誤りを埋めて、元の曲線を描いた多項式の係数を復元することができる。
沿革
1960年、当時MITリンカーン研究所に所属していたアーヴィング・S・リードとグスタフ・ソロモンによって考案された暗号である。彼らの代表的な論文は、"Polynomial Codes over Certain Finite Fields "というタイトルだった。この論文が書かれた当時は、まだデジタル技術が発達しておらず、このコンセプトを実現することはできませんでした。1982年、RS符号が初めて量産品に適用されたのは、コンパクトディスクで、2つのインターリーブRS符号が使われた。1969年にElwyn BerlekampとJames Masseyによって大距離RS符号の効率的な復号化アルゴリズムが開発された。現在、RS符号はハードディスクドライブ、DVD、電気通信、デジタル放送のプロトコルに使用されている。
