リード・ソロモン符号（-ふごう Reed-Solomon Coding RS符号と略記）とは符号理論における誤り訂正符号の一種、訂正能力が高く様々なデジタル機器等で応用されている。 リード・ソロモン符号は1960年にアービング・リード
目次
1 概要
2 基本理論
2.1 符号化
2.2 復号
3 関連項目
4 参考文献
概要
特徴として符号の生成方法にガロア体（有限体）の概念を使用している。これは複数個のビットを一つの固まり（シンボルあるいはワードと呼ぶ）と見なし、符号語をシンボルの集まりで表し各シンボル単位で誤りの検出と訂正を行う。一つのシンボル内のビットがどれだけ誤りを含んでいても全体としては「1シンボルの誤り」と見なされるため特に連続して起こるビット誤り（バースト誤り）に強いという特性がある。なお、リード・ソロモン符号の1シンボルのビット数は通常規定されていないがコンピュータの仕様上、8ビット（1バイト）で実装されるシステムが多い。 ここではリード・ソロモン符号の基本的な理論と実装方法について述べる。なお符号理論の基本概念として以下に登場する加算記号( ⊕ {\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.} という多項式の形で表される。 シンボルへの変換は以下のように行う。まず連続する r ビットを一つのシンボルとするのでシンボルは全部で 2 r 種類存在することになる。そこで 2 r 個の要素で構成される拡大ガロア体を定義する。具体的にはまず r 次の原始多項式から適当な物を一つ選ぶ、例としてここでは r = 8 とし以下のものを使用する。 x 8 ⊕ x 4 ⊕ x 3 ⊕ x 2 ⊕ 1 = 0 {\displaystyle x^{8}\oplus x^{4}\oplus x^{3}\oplus x^{2}\oplus 1=0} このときこの方程式の根を α とおくと α 8 ⊕ α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 = 0 {\displaystyle \alpha ^{8}\oplus \alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1=0} であるため、 α 8 = α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 {\displaystyle \alpha ^{8}=\alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1} と表すことが出来る。そこでこの関係を用いて次のようにαのべき乗を定義して各ビット列に対応させる。 α 0 = 1 ↔ 00000001 {\displaystyle \alpha ^{0}=1\leftrightarrow 00000001} ・・・ α 7 ↔ 10000000 {\displaystyle \alpha ^{7}\leftrightarrow 10000000} α 8 = α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 ↔ 00011101 {\displaystyle \alpha ^{8}=\alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1\leftrightarrow 00011101} α 9 = α 8 × α = α 5 ⊕ α 4 ⊕ α 3 ⊕ α 1 ↔ 00111010 {\displaystyle \alpha ^{9}=\alpha ^{8}\times \alpha =\alpha ^{5}\oplus \alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{1}\leftrightarrow 00111010} α 10 = α 9 × α = α 6 ⊕ α 5 ⊕ α 4 ⊕ α 2 ↔ 01110100 {\displaystyle \alpha ^{10}=\alpha ^{9}\times \alpha =\alpha ^{6}\oplus \alpha ^{5}\oplus \alpha ^{4}\oplus \alpha ^{2}\leftrightarrow 01110100} ・・・ α 254 = α 7 ⊕ α 3 ⊕ α 2 ⊕ α 1 ↔ 10001110 {\displaystyle \alpha ^{254}=\alpha ^{7}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus \alpha ^{1}\leftrightarrow 10001110} これに 0 ↔ 00000000 {\displaystyle 0\leftrightarrow 00000000} を加えることで全部で 256 = 2 8の元が出揃い、各ビット列との対応がとれる。 符号化は以下のような手順で行われる。まず送る情報 K × r ビットを前述の方法でシンボル化して K次の方程式を生成し、これを情報多項式と呼び I(x) で表す。次に以下の式で表される生成多項式を用意する。 G ( x ) = ∏ i = b 2 t − 1 + b ( x − α i ) {\displaystyle G(x)=\prod _{i=b}^{2t-1+b}(x-\alpha ^{i})} 上記の式中における b は適当な整数を入れる。例として b=0 で2シンボルの誤りを訂正する符号を生成する。このとき t= 2となり、生成多項式は G ( x ) = ( x − 1 ) ( x − α ) ( x − α 2 ) ( x − α 3 ) = x 4 + α 75 x 3 + α 249 x 2 + α 78 x + α 6 {\displaystyle \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 × I ( x ) + P ( x ) {\displaystyle C(x)=x^{N-K}\times I(x)+P(x)} ただし P ( x ) = x N − K × I ( x ) mod G ( x ) {\displaystyle P(x)=x^{N-K}\times I(x)\mod G(x)} である。ここで生成される C(x) に対応するビット列が送信される符号である。 送信されたデータから復号を行う場合の処理は以下の手順で行われる。 リード・ソロモン符号の復号方法はいくつか種類があり、代表的なところではピーターソン法 まず誤りの検出を行う、この方法は受信したデータから生成された方程式を Y(x) で表すとする。このとき Y(x) は以下の式で表される。
基本理論
α 1 ↔ 00000010 {\displaystyle \alpha ^{1}\leftrightarrow 00000010}
α 2 ↔ 00000100 {\displaystyle \alpha ^{2}\leftrightarrow 00000100}
α 3 ↔ 00001000 {\displaystyle \alpha ^{3}\leftrightarrow 00001000}
符号化
復号
誤りの検出、シンドロームの算出
誤りを含むシンボルの数を検出
誤りを含むシンボルの位置を検出
誤りの値を検出
誤りの訂正
