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

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


Home  誤り訂正 ∥ 符号生成 | 符号検査 | 誤り訂正 | 単一訂正 | 二重訂正 | 応用

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

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

n 各ブロックの総シンボル数 ブロック長
k 各ブロックの情報シンボル数 情報ブロック長
n-k = 2t 各ブロックに加えるパリティ・シンボル数 パリティ長
t = (n-k) / 2 各ブロックにおける訂正可能な最大シンボル数 誤り訂正可能最大数

ブロック長nの最大値は?
符号化/復号化時に使用するガロア体(GF)によって決定する。
例)素数2を拡大したガロア拡大体GF(2P)を用いると

nmax=2P-1

であり、最大ブロック長は2P-1のシンボル数である。
また各シンボルはGF(2P)の要素であり、P bitである。

具体的に最大ブロック長を計算すると
P = 4 の場合
nmax = 24-1 = 15 個のシンボル
15 * 4bit = 60bit

P = 8 の場合
nmax = 28-1 = 255 個のシンボル
255 * 8bit = 2040bit
となる。

ページの上部へ

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

情報シンボル vk-1 , ・・・ , v1 , v0
情報多項式 V(x) = vk-1 xk-1 + ・・・ + v1 x + v0
生成多項式 G(x) = (x - α0)(x - α1)・・・(x - α2t-1)
符号多項式 W(x) = x2t V(x) + R(x)
検査多項式 R(x) = r2t-1 x2t-1 + ・・・ + r1 x + r0
符号語 w = vk-1 , ・・・ , v1 , v0 , r2t-1 , ・・・ , r1 , r0

W(x)はG(x)で割り切れる必要があるから
R(x) = [x2t V(x)] mod G(x) ( [ ]内の多項式をG(x)で割った剰余多項式)
GF(2P) = { 0 , α0 , α1 , α2 , ・・・ , αm } (ただし m = 2P - 2)

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

初めに使用するガロア体と訂正可能数を決める。要するにRS(n,k)を決める。
例として GF(28) , t = 2 とし、RS(255,251)符号を生成してみよう。

符号化する情報を 8bit 毎に区切り、各々v250 , ・・・ , v1 , v0とし情報ブロックを作る。
これを情報多項式V(x)として表す。

生成多項式は、G(x) = (x - 1)(x - α)(x - α2)(x - α3) となる。
検査多項式は、R(x) = [x4 V(x)] mod G(x)
符号多項式は、W(x) = x4 V(x) + R(x)

符号語は、w = v250 , ・・・ , v1 , v0 , r3 , r2 , r1 , r0 となり
順番に繋げると 2040bit(1ブロック) の符号語ができる。

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

ページの上部へ

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

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

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

ページの上部へ

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

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

{β0 , β1 , ・・・ , βq-1} = {0 , 1 , α , α2 , ・・・ , αq-2

と書ける。また一般に受信語 y = {y0 , y1 , ・・・ , yq-1} ∈ GF(q) に対して

シンドローム j(y) = β0j0 + β1j1 + ・・・ + βq-1jq-1 (0 ≦ j ≦ 2t-1)

と定義する。
符号語 w ∈ RS(n , k) ならば j(y) = 0 (0 ≦ j ≦ 2t-1) が成立する。

今、符号語 w ∈ RS(n , k) が送信され、受信語 y ∈ GF(2P) として受信されたとすると
y = w + e , e = (e0 , e1 , ・・・ ,en-1)
と誤りベクトル e を用いて記述すると

j(y) = Sj(w) + Sj(e) = Sj(e) (0 ≦ j ≦ 2t-1)

が成立する。S0(y) , ・・・ , S2t-1(y)を受信語 y のシンドロームという。

ページの上部へ

単一誤り訂正

RS(n,n-2)符号で生成し
シンドロームは S0(y) = ej , S1(y) = ejαj である。
よって誤りの値と位置は

S0(y) = ej , S0(y)-1S1(y) = αj → j

だから元の符号は wj = yj - ej である。

ページの上部へ

二重誤り訂正

RS(n,n-4)符号で生成し
シンドロームは S0(y) , S1(y) , S3(y) , S4(y) が計算できる。

S0(y) = S1(y) = S3(y) =S4(y) = 0 であれば誤りなしと判断する。

0でないシンドロームがあれば、未知数 u0 , u1 , u2 について連立方程式

S2(y) u2 + S1(y) u1 + S0(y) u0 = 0
S3(y) u2 + S2(y) u1 + S1(y) u0 = 0

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

u2 = 0 , u1 = 1 として解ければ、誤りは1個と判断し
誤り位置を αs = -u0 誤り値を es = S0(y) と推定する。

u2 = 1 として解ければ、誤りは2個と判断する。

x2 + u1x + u0 = x2 - (αs + αt)x + αsαt = (x - αs)(x - αt)

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

αtS0(y) - S1(y) = (αt - αs)es , αsS0(y) - S1(y) = (αs - αt)et

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

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

ページの上部へ

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

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

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

情報データ

外符号
ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア