ja.wikipedia.org

リード・ソロモン符号 - Wikipedia

出典: フリー百科事典『ウィキペディア（Wikipedia）』

リード・ソロモン符号（リード・ソロモンふごう、Reed-Solomon Coding、RS符号と略記）とは符号理論における誤り訂正符号の一種、訂正能力が高く様々なデジタル機器等で応用されている。

リード・ソロモン符号は1960年にアービング・ストイ・リード（英語版）とギュスタブ・ソロモン（英語版）によって開発された誤り訂正符号である。符号の生成と復号が複雑なので、処理速度が求められる分野ではあまり使用されていないが、その反面誤り訂正能力が高く、地上デジタル放送、衛星通信、ADSLやDVTR、身近なところではCDやDVDやBD、QRコードの誤り訂正に応用されている。

特徴として符号の生成方法にガロア体（有限体）の概念を使用している。これは複数個のビットを一つの固まり（シンボルあるいはワードと呼ぶ）と見なし、符号語をシンボルの集まりで表し各シンボル単位で誤りの検出と訂正を行う。一つのシンボル内のビットがどれだけ誤りを含んでいても全体としては「1シンボルの誤り」と見なされるため特に連続して起こるビット誤り（バースト誤り）に強いという特性がある。なお、リード・ソロモン符号の1シンボルのビット数は通常規定されていないがコンピュータの仕様上、8ビット（1バイト）で実装されるシステムが多い。

ここではリード・ソロモン符号の基本的な理論と実装方法について述べる。なお符号理論の基本概念として以下に登場する加算記号( $\oplus$ )は全て直和ではなく各ビットごとの排他的論理和を表す。

リード・ソロモン符号では r ビットの連続した固まりを一つのシンボルとし、 N個のシンボルすなわち r × N ビットの並びを一つの符号語とする。

このとき K 個のシンボルが実際に送る情報、残りの (N-K)個のシンボルが後述する符号化で生成される冗長シンボルである。ただし r , N, K は以下の条件を満たすとする。

$2^{r}>N>K>0$

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

リード・ソロモンではまず r × N ビットの並びをシンボルを係数とする (N-1)次の多項式の形で表す。図のように各8ビット列が次のようなシンボルに変換されたとする。

このときこのビット列はリード・ソロモン符号では

$\left.Ax^{3}\oplus Bx^{2}\oplus Cx\oplus D\right.$

という多項式の形で表される。

シンボルへの変換は以下のように行う。まず連続する r ビットを一つのシンボルとするのでシンボルは全部で 2 ^r 種類存在することになる。そこで 2 ^r 個の要素で構成される拡大ガロア体を定義する。具体的にはまず r 次の原始多項式から適当な物を一つ選ぶ、例としてここでは r = 8 とし以下のものを使用する。

$x^{8}\oplus x^{4}\oplus x^{3}\oplus x^{2}\oplus 1=0$

このときこの方程式の根を α とおくと

$\alpha ^{8}\oplus \alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1=0$

であるため、

$\alpha ^{8}=\alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1$

と表すことが出来る。そこでこの関係を用いて次のようにαのべき乗を定義して各ビット列に対応させる。

$\alpha ^{0}=1\leftrightarrow 00000001$
$\alpha ^{1}\leftrightarrow 00000010$
$\alpha ^{2}\leftrightarrow 00000100$
$\alpha ^{3}\leftrightarrow 00001000$

・・・

$\alpha ^{254}=\alpha ^{7}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus \alpha ^{1}\leftrightarrow 10001110$

これに

$0\leftrightarrow 00000000$

を加えることで全部で 256 = 2 ⁸の元が出揃い、各ビット列との対応がとれる。

符号化は以下のような手順で行われる。まず送る情報 K × r ビットを前述の方法でシンボル化して K-1次の多項式を生成し、これを情報多項式と呼び I(x) で表す。次に以下の式で表される生成多項式を用意する。

$G(x)=\prod _{i=b}^{2t-1+b}(x-\alpha ^{i})$

上記の式中における b は適当な整数を入れる。例として b=0 で2シンボルの誤りを訂正する符号を生成する。このとき t= 2となり、生成多項式は

$\left.G(x)=(x-1)(x-\alpha )(x-\alpha ^{2})(x-\alpha ^{3})=x^{4}+\alpha ^{75}x^{3}+\alpha ^{249}x^{2}+\alpha ^{78}x+\alpha ^{6}\right.$

となる。このとき情報多項式と生成多項式を用いて以下のような演算を行う。

$C(x)=x^{N-K}\times I(x)+P(x)$

ただし

$P(x)\equiv x^{N-K}\times I(x)\mod G(x)$

である。ここで生成される C(x) に対応するビット列が送信される符号である。

送信されたデータから復号を行う場合の処理は以下の手順で行われる。

誤りの検出、シンドロームの算出
誤りを含むシンボルの数を検出
誤りを含むシンボルの位置を検出
誤りの値を検出
誤りの訂正

リード・ソロモン符号の復号方法はいくつか種類があり、代表的なところではピーターソン法やユークリッド法などが知られている。ここではピーターソン法について述べる、この方法は処理が単純である反面、訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある。

まず誤りの検出を行う、この方法は受信したデータから生成された多項式を Y(x) で表すとする。このとき Y(x) は以下の式で表される。

$Y(x)=C(x)+E(x)$

ここで E(x) は通信中に紛れ込んだ誤りである。最初にシンドロームの算出を行う、シンドロームとは

$S_{i}=Y(\alpha ^{i-1+b}),(i=1,\dots ,2t)$

で表される、2t 個の数値である。

前述の C(x) と G(x) の関係から C(x) が G(x) で割り切れるのは明らかである。よって誤りがあるかどうかは G(x) の各根、α^b, α^b+1, ... , α^b+2t-1を代入することで検出することが出来る、すなわち

$\exists S_{i}\neq 0,(i=1,\dots ,2t)$

となるならY(x) ≠ C(x) であり、Y(x) には誤りが存在することになる。

誤りが存在した場合、次に誤りを含むシンボルの数を検出する。検出にはまず誤りの数を仮定し、上記シンドロームから行列式を生成する。たとえば仮定した誤りの数が k 個の場合は次のような関係式が成り立つ、

${\begin{vmatrix}S_{k}&S_{k-1}&\cdots &S_{1}\\S_{k+1}&S_{k}&\cdots &S_{2}\\\vdots &\ddots &\vdots &\vdots \\S_{2k-1}&S_{2k-2}&\cdots &S_{k}\\\end{vmatrix}}\neq 0$

誤りの数が kで無い場合は上記の式は必ず 0 になる。これによりまず最初に誤り数を t と仮定し、上記の行列式が 0 になるなら次は誤り数を t-1 と仮定し…という処理を繰り返し、行列式が 0 以外の値を出したときに仮定した誤り数が実際の誤りの数であることがわかる。

誤りの数を検出した後は誤りの位置を検出する。これは誤りの数が k だった場合、以下のような誤り位置多項式を生成することで求められる。

$\sigma (x)=1+\sigma _{1}x+\sigma _{2}x^{2}+\cdots +\sigma _{k}x^{k}$

ただし σ₁, σ₂, …, σ_k は以下の式を満たす変数である。

${\begin{bmatrix}S_{k}&S_{k-1}&\cdots &S_{1}\\S_{k+1}&S_{k}&\cdots &S_{2}\\\vdots &\ddots &\vdots &\vdots \\S_{2k-1}&S_{2k-2}&\cdots &S_{k}\\\end{bmatrix}}{\begin{bmatrix}\sigma _{1}\\\sigma _{2}\\\vdots \\\sigma _{k}\\\end{bmatrix}}={\begin{bmatrix}S_{k+1}\\S_{k+2}\\\vdots \\S_{2k}\end{bmatrix}}$

このときσ(x) に α⁰～α^N-2を順次代入すると、必ず k 箇所でσ(x) = 0 となる場所が存在する。このときその根の逆元が誤りのある位置である。σ(α^m）= 0 となった場合は Y(x) の x^255-mの係数が誤りを含んでいることになる。

位置が検出が出来ると最後に誤りの値を検出し復号を行う、Y(x) = C(x) + E(x) であるので、前述のシンドロームは

$S_{i}=C(\alpha ^{i-1+b})+E(\alpha ^{i-1+b})(i=1,\dots ,2t)$

であるといえる。そこでこの式より連立一次方程式を用いて誤りの値を算出する。例として誤りの位置検出の結果 m₁, ... , m_k の次数に誤りがあったとする、このとき以下の方程式を生成する。

${\begin{cases}\alpha ^{m_{1}\times b}e_{1}+\alpha ^{m_{2}\times b}e_{2}+\cdots +\alpha ^{m_{k}\times b}e_{k}=S_{1}\\\alpha ^{m_{1}\times (b+1)}e_{1}+\alpha ^{m_{2}\times (b+1)}e_{2}+\cdots +\alpha ^{m_{k}\times (b+1)}e_{k}=S_{2}\\\vdots \\\alpha ^{m_{1}\times (b+k-1)}e_{1}+\alpha ^{m_{2}\times (b+k-1)}e_{2}+\cdots +\alpha ^{m_{k}\times (b+k-1)}e_{k}=S_{k}\\\end{cases}}$

この式より e₁, ... , e_k を求め、

$C(x)=Y(x)+x^{m_{1}}e_{1}+x^{m_{2}}e_{2}+\cdots x^{m_{k}}e_{k}$

により誤りを復元できる。

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