リード・ソロモン符号
ここではリード・ソロモン符号の基本的な理論と実装方法について述べる。なお符号理論の基本概念として以下に登場する加算記号( ⊕ {\displaystyle \oplus } )は全て直和ではなく各ビットごとの排他的論理和を表す。
リード・ソロモン符号では r ビットの連続した固まりを一つのシンボルとし、 N個のシンボルすなわち r × N ビットの並びを一つの符号語とする。
このとき K 個のシンボルが実際に送る情報、残りの (N-K)個のシンボルが後述する符号化で生成される冗長シンボルである。ただし r , N, K は以下の条件を満たすとする。
2 r > N > K > 0 {\displaystyle 2^{r}>N>K>0}
ここで (N-K)/2 を t とした場合、リード・ソロモン符号は t 個までのシンボルの誤りを訂正することができる。
リード・ソロモンではまず r × N ビットの並びをシンボルを係数とする (N-1)次の多項式の形で表す。 図のように各8ビット列が次のようなシンボルに変換されたとする。
このときこのビット列はリード・ソロモン符号では
A x 3 ⊕ B x 2 ⊕ C x ⊕ D {\displaystyle \left.Ax^{3}\oplus Bx^{2}\oplus Cx\oplus D\right.
送信されたデータから復号を行う場合の処理は以下の手順で行われる。
誤りの検出、シンドロームの算出
誤りを含むシンボルの数を検出
誤りを含むシンボルの位置を検出
誤りの値を検出
誤りの訂正
リード・ソロモン符号の復号方法はいくつか種類があり、代表的なところではピーターソン法やユークリッド法などが知られている。ここではピーターソン法について述べる、 この方法は処理が単純である反面、訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある。
まず誤りの検出を行う、この方法は受信したデータから生成された多項式を Y(x) で表すとする。このとき Y(x) は以下の式で表される。
Y ( x ) = C ( x ) + E ( x ) {\displaystyle Y(x)=C(x)+E(x)}
ここで E(x) は通信中に紛れ込んだ誤りである。 最初にシンドロームの算出を行う、シンドロームとは
S i = Y ( α i − 1 + b ) , ( i = 1 , ... , 2 t ) {\displaystyle S_{i}=Y(\alpha ^{i-1+b}),(i=1,\dots ,2t)}
で表される、2t 個の数値である。
前述の C(x) と G(x) の関係から C(x) が G(x) で割り切れるのは明らかである。よって誤りがあるかどうかは G(x) の各根、α, α, ...