リード・ソロモン符号講座

Revised : 2006/01/31
Since : 2006/01/26

リード・ソロモン符号(Reed-Solomon code)

　データの誤りを検出・訂正できる順方向誤り訂正符号の1種であり、線形巡回ブロック符号の１種である。
連続して発生する誤り（バースト誤り）を訂正することが可能な数学的な誤り訂正の方法で、高度な訂正能力を持っている。
　リード・ソロモン符号は、QRコード、CDやハードディスク、DVD等の記憶装置や、ADSLや宇宙通信等の通信分野等で用いられている。
ハミング符号などと比べると、誤り訂正能力は高いが、処理に複雑な演算を多用するため、誤りを訂正するために多くの時間がかかる。
　リード・ソロモン符号は、リードソロモン（n , k）符号と定義される。

ブロック長ｎの最大値は？
符号化/復号化時に使用するガロア体（ＧＦ）によって決定する。
例）素数２を拡大したガロア拡大体ＧＦ（２^P）を用いると

n_max＝２^P－１

であり、最大ブロック長は２^P－１のシンボル数である。
また各シンボルはＧＦ（２^P）の要素であり、Ｐ　bitである。

具体的に最大ブロック長を計算すると
P = 4 の場合
n_max = ２⁴－１ = １５ 個のシンボル
１５　*　４bit = ６０bit

P = 8 の場合
n_max = ２⁸－１ = ２５５ 個のシンボル
２５５　*　８bit = ２０４０bit
となる。

リード・ソロモン符号の生成

W(x)はG(x)で割り切れる必要があるから
R(x) = [ｘ^2t V(x)] mod G(x)　（ [ ]内の多項式をG(x)で割った剰余多項式）
ＧＦ（２^P） = { 0 , α⁰ , α¹ , α² , ・・・ , α^m }　(ただし m = 2^P - 2)

では符号を生成してみよう

初めに使用するガロア体と訂正可能数を決める。要するにRS（ｎ，ｋ）を決める。
例として　ＧＦ（２⁸） , ｔ = 2　とし、ＲＳ（255,251）符号を生成してみよう。

符号化する情報を ８bit 毎に区切り、各々ｖ₂₅₀ , ・・・ , v₁ , v₀とし情報ブロックを作る。
これを情報多項式V(x)として表す。

生成多項式は、G(x) = (x - 1）(x - α）(x - α²)(x - α³)　となる。
検査多項式は、R(x) = [ｘ⁴ V(x)] mod G(x)
符号多項式は、W(x) = x⁴ V(x) + R(x)

符号語は、w = v₂₅₀ , ・・・ , v₁ , v₀ , r₃ , r₂ , r₁ , r₀　となり
順番に繋げると 2040bit（１ブロック） の符号語ができる。

以上を情報がある間繰り返す。もし１ブロックを 251個にしない場合は 0 等でパディングし 251個にすれば良い。

リード･ソロモン符号の検査

検査は符号語をブロック毎に、符号多項式W（ｘ）にする。
これを生成多項式G(x)で割り、余りが0であれば t 個以下のエラーはない。

t 個を超えるエラーは検出できない場合がある。また、検出できても訂正できない。
受信語が全零になるという誤りの可能性もあるので、実際には誤りがないとき、
剰余が非零の特定のパターンになるように符号化することが多い。

リード･ソロモン符号の誤り訂正

ブロック毎にシンドロームを求める。
β ∈ GF(q) 、原始元をαとすれば

｛β₀ , β₁ , ・・・ , β_q-1｝ = ｛０ , １ , α , α² , ・・・ , α^q-2｝

と書ける。また一般に受信語 ｙ = ｛ｙ₀ , ｙ₁ , ・・・ , ｙ_q-1｝ ∈ GF(q) に対して

シンドローム Ｓ_j（ｙ） = β₀^j ｙ₀ + β₁^j ｙ₁ + ・・・ + β_q-1^j ｙ_q-1 （0 ≦ ｊ ≦ 2t-1）

と定義する。
符号語 ｗ ∈ RS(n , k) ならば Ｓ_j（ｙ） = ０　（0 ≦ ｊ ≦ 2t-1） が成立する。

今、符号語 ｗ ∈ RS(n , k) が送信され、受信語 ｙ ∈ GF（２^P） として受信されたとすると
ｙ = w + e , e = (e₀ , e₁ , ・・・ ,e_n-1)
と誤りベクトル e を用いて記述すると

Ｓ_j（ｙ） = Ｓ_j（w） + Ｓ_j（e） = Ｓ_j（e）　（0 ≦ ｊ ≦ 2t-1）

が成立する。Ｓ₀（ｙ） , ・・・ , Ｓ_2t-1（ｙ）を受信語 ｙ のシンドロームという。

単一誤り訂正

RS(n,n-2）符号で生成し
シンドロームは S₀（ｙ） = e_j , S₁（ｙ） = e_jα^j である。
よって誤りの値と位置は

S₀（ｙ） = e_j , S₀（ｙ）^-1S₁（ｙ） = α^j　→　j

だから元の符号は w_j = y_j - e_j である。

二重誤り訂正

RS(n,n-4）符号で生成し
シンドロームは S₀（ｙ） , S₁（ｙ） , S₃（ｙ） , S₄（ｙ） が計算できる。

S₀（ｙ） = S₁（ｙ） = S₃（ｙ） =S₄（ｙ） = 0 であれば誤りなしと判断する。

0でないシンドロームがあれば、未知数 u₀ , u₁ , u₂ について連立方程式

S₂(y) u₂ + S₁(y) u₁ + S₀(y) u₀ = 0
S₃(y) u₂ + S₂(y) u₁ + S₁(y) u₀ = 0

をGFにおいて解く。ただし u₂ = 1 または u₂ = 0 , u₁ = 1 とする。

u₂ = 0 , u₁ = 1 として解ければ、誤りは１個と判断し
誤り位置を α^s = -u₀ 誤り値を e_s = S₀(y) と推定する。

u₂ = 1 として解ければ、誤りは２個と判断する。

x² + u₁x + u₀ = x² - (α^s + α^t)x + α^sα^t = (x - α^s)(x - α^t)

と分解して誤り位置 s , t を推定し

α^tS₀(y) - S₁(y) = (α^t - α^s)e_s , α^sS₀(y) - S₁(y) = (α^s - α^t)e_t

として誤り値 e_s , e_t を計算する。
後は単一誤り訂正と同様に元の符号を求める。

２個を超える誤りがある場合、ある条件下では２個以下の訂正を行うことにより
全てのシンドロームが０になる場合がある。（シンドロームは０でも誤りは訂正できない。）

リード･ソロモン符号の応用

情報データを入れ替えた（クロスインターリーブ）後、検査符号を付加する。
インターリーブはエラーを分散させるために行う処理である。

情報データを２次元に配置し、垂直方向・水平方向に演算し、検査符号を付加する。