リード・ソロモン符号

リード・ソロモン符号とは

リード・ソロモン符号（Reed-Solomon Coding、RS符号）は、1960年にアービング・ストイ・リードとギュスタブ・ソロモンによって開発された誤り訂正符号です。データ伝送や記憶の際に発生する誤りを訂正する能力に優れており、様々なデジタル機器で幅広く応用されています。

概要

リード・ソロモン符号は、符号の生成と復号に複雑な計算処理を必要とするため、高速処理が求められる分野での利用は限られています。しかし、その高い誤り訂正能力から、地上デジタル放送、衛星通信、ADSL、DVTR、CD、DVD、BD、QRコードなど、身近な様々なデジタル機器や技術で活用されています。

特徴

リード・ソロモン符号の最大の特徴は、符号の生成にガロア体（有限体）の概念を用いている点です。複数のビットをまとめてシンボル（またはワード）として扱い、シンボル単位で誤りの検出と訂正を行います。これにより、バースト誤り（連続したビットの誤り）に強いという特徴があります。通常、1シンボルは8ビット（1バイト）で構成されることが多いです。

基本理論

リード・ソロモン符号では、rビットのまとまりを1つのシンボルとし、N個のシンボル（r × Nビット）を1つの符号語とします。このうち、K個のシンボルが実際に送信する情報であり、残りの(N-K)個のシンボルが符号化によって生成される冗長シンボルです。これらのパラメータは以下の条件を満たします。

N: 符号語のシンボル数
K: 情報シンボルの数
r: 各シンボルのビット数

(N-K)/2をtとすると、リード・ソロモン符号は最大でt個のシンボルの誤りを訂正できます。

リード・ソロモン符号では、まずr × Nビットの並びを、シンボルを係数とする(N-1)次の多項式で表現します。例えば、以下のように8ビット列がシンボルに変換されたとします。


[0x45, 0x67, 0x23, 0xAB, 0xCD]


このビット列は、リード・ソロモン符号では以下の多項式で表されます。


45x^4 + 67x^3 + 23x^2 + ABx + CD


シンボルへの変換は、2^r個の要素を持つ拡大ガロア体を定義することで行います。具体的には、r次の原始多項式を選択し、その根をαとすることで、αのべき乗で各ビット列を表現します。例えば、r=8の場合、以下の原始多項式を使用します。


x^8 + x^4 + x^3 + x^2 + 1


このとき、αを根とすると、


α^8 = α^4 + α^3 + α^2 + 1


となり、各ビット列とαのべき乗を対応付けることで、256個の元を生成できます。

符号化

符号化は以下の手順で行われます。

1. 送信する情報(K × rビット)をシンボル化し、K-1次の情報多項式I(x)を生成します。
2. 以下の式で表される生成多項式G(x)を用意します。


G(x) = (x - α^b)(x - α^(b+1))...(x - α^(b+2t-1))


ここで、bは整数、tは訂正可能なシンボル数です。

3. 情報多項式I(x)と生成多項式G(x)を用いて、以下の演算を行います。


C(x) = I(x) G(x) = Q(x) + R(x)


ここで、C(x)が符号語多項式、Q(x)は商、R(x)は剰余です。送信される符号はC(x)に対応するビット列です。

復号

復号は以下の手順で行われます。

1. 受信したデータから多項式Y(x)を生成します。
2. シンドロームSを算出します。シンドロームは、受信した多項式Y(x)に生成多項式G(x)の各根を代入したものです。もし、シンドロームがすべて0ならば、誤りはありません。
3. 誤りが存在する場合、誤りシンボルの数を検出します。
4. 誤りシンボルの位置を検出します。
5. 誤りシンボルの値を検出します。
6. 誤りを訂正します。

リード・ソロモン符号の復号方法には、ピーターソン法やユークリッド法などがあります。ピーターソン法は処理が単純ですが、訂正するシンボル数が多いと計算量が増大します。

シンドロームの算出

シンドロームは、以下の式で表される2t個の数値です。


S_i = Y(α^(b+i))


ここで、iは0から2t-1までの整数です。受信したデータに誤りがなければ、すべてのシンドロームは0になります。

誤り数の検出

誤り数を仮定し、シンドロームから行列式を生成します。行列式が0にならなければ、仮定した誤り数が実際の誤り数となります。

誤り位置の検出

誤り位置多項式σ(x)を生成し、その根を求めることで誤り位置を検出します。σ(x)の根の逆元が誤りのある位置です。

誤り値の検出

シンドロームと誤り位置から連立一次方程式を解き、誤り値を算出します。

誤り訂正

誤り位置と誤り値を用いて、受信したデータを訂正します。

参考文献

江藤良純、金子敏信、『誤り訂正符号とその応用』、オーム社、1996年、ISBN 4-274-03486-0

関連項目

符号理論
巡回符号
ハミング符号
BCH符号
ターボ符号

もう一度検索