読み方：リードソロモンふごう

リードソロモン符号【Reed–Solomon coding】

概要

リードソロモン符号とは、データ伝送や記録の際に生じる誤りを検出・訂正するための誤り訂正符号の一つ。連続して発生する「バースト誤り」（burst error）に強い特徴があり、CDやDVD、QRコード、衛星通信、無線通信など幅広い分野で利用されている。

データを記録したり送受信する際には、媒体表面の傷、ノイズ、電気的な干渉などによってビットの誤りが生じることがある。誤り訂正符号はこうした誤りを自動的に検出して元のデータに復元するための冗長情報を付加する技術である。

リードソロモン符号は、一定の個数の記号からなる元のデータに、訂正のための冗長な記号を付け加えて符号語を作る。ビット単位ではなく、通常は8ビットなどをひとまとまりにした「シンボル」という記号単位で扱うため、複数ビットにまたがる誤りにも対応しやすい。受信側や読み出し側では、追加された冗長情報を用いて、どこに誤りがあるかを推定し、一定範囲内であれば元のデータを復元できる。

1960年にアービング・リード（Irving S. Reed）とギュスターブ・ソロモン（Gustave Solomon）が考案した。「有限体」（ガロア体）と呼ばれる数学的な構造を利用した代数的符号であり、符号化と復号の処理はこの有限体上の多項式演算を行う。n個のシンボルからなる符号語のうちk個のシンボルが元データであるとき、残りの（n-k）シンボルが冗長データとなり、最大で（n-k）/2シンボルまでの誤りを訂正できる。

実際の利用では、インタリーブと呼ばれる並べ替え技術と組み合わせることで、連続した誤りを分散させ、より効果的に訂正できるようにすることが多い。一方、冗長データを付加する分だけ記憶容量や通信量が増え、訂正能力を高めるほど効率が下がるトレードオフが存在する。また、訂正できる誤りの量には限界があり、それを超えると正しく復元できない。