第 6 章 リード・ソロモン符号 49
6.2 リード・ソロモン符号の復号
6.2.2 RS 符号の誤り訂正
RS符号のt重誤り訂正は以下のような手順で行われる.
1.誤り位置検出 0∼n−1のシンボル中,どこに誤りがあるのか調べる. 2.誤り訂正 誤りのあったシンボルの正しい値を求める.
これらはそれぞれt個の変数を調べる必要があるため,t重訂正を行うためには合わせて2t個の変数を調べ る必要がある. まずシンドロームを使って,誤り位置を検出する.
s=HR=H(c+e) =He これを多項式表示すると
(α0)0eo+· · ·(α0)n−1en−1=s0
...
(αr−1)0eo+· · ·(αr−1)n−1en−1=sn−1
(6.2)
これらはr個の方程式であり,またr=2tなので,2t個の方程式であると言える. この式の中で,e0,· · ·, en−1
は未知であり,s0,· · ·, sn−1は既知である. また,e0,· · · , en−1はt個の誤りの場所と誤り内容を孕んでいる. よってこの未知な情報から, 2t個の変数を用意する. 誤り位置をi,誤り内容をeiとすると, 2t個の変数が取 りうる値は
ei1 ∈{0, α0,· · · , α2s−2} ...
eit ∈{0, α0,· · ·, α2s−2} i1∈{0,· · · , n−1}
...
it∈{0,· · · , n−1}
(6.3)
となる.
52 第6章 リード・ソロモン符号
t≥3では,式(6.2)を解くのが非常に困難なため*3,ここからはtが1か2の場合について考えていく.
t=2のとき,r=4なので,HRは
HR=
(α0)0 · · · (α0)n−1 ... . .. ... (α3)0 · · · (α3)n−1
R0
... Rr−1
=
s0
s1
s2
s3
これによって,s0∼s3が与えられる. また,HR=Heより
HR=
(α0)0 · · · (α0)n−1 ... . .. ... (α3)0 · · · (α3)n−1
e0
... er−1
=
s0 s1 s2 s3
と変形できるのでこれを展開し,
(α0)0eo+· · ·(α0)n−1en−1=s0
...
(α3)0eo+· · ·(α3)n−1en−1=s3
(6.4)
これから,e0,· · ·, en−1を求める*4.
6.2.3 1 重誤りの訂正
誤りシンボルをei(ei6=0, ej=0(j6=i), 0≤i≤n−1)とする. また,ei∈{0, α,· · ·, α2s−2}である. 訂正 に必要な情報は
• iの値はいくつか(誤り位置)
• eiの値はいくつか(誤りの値)
であるので,順を追って求めていく. ei以外は0であるから,式(6.4)は
(α0)iei=s0 (α1)iei=s1
(α2)iei=s2 (α3)iei=s3
(6.5)
となる. ここで,
s1
s0 = (α(α10))iieei
i =ai
s2
s1 = (α(α21))iieei
i =ai
s3
s2 = (α(α32))iieeii =ai
(6.6)
より,
s1 s0
= s2 s1
= s3 s2
が成り立つ. これが,t=2のときの1重誤りの条件である.
*3デジタルTVでは,内部にt=8の方程式を解く回路が埋め込まれているらしい
*4くどいようだが,この式はt=1,2の時しか使えないので注意
6.2 リード・ソロモン符号の復号 53 Def: 1重誤りの条件
¶ ³
シンドロームsを求め,各要素間が以下の関係を満たすとき,その受信系列は1重誤りである. s1
s0 = s2
s1 = s3
s2
これを満たさない場合は, 2重か,それ以上の誤りがあるとみてよい.
µ ´
シンドロームは既知であるから,これで誤り位置iが求められる. 更にiがわかればeiが計算可能となるの で,s0を使って
ei= s0
(α0)i =s0
このs0が誤り内容となる. 正しい符号多項式c(x)は
c(x) =R(x) +e(x) =R(x) +ei
によって訂正できる.
6.2.4 2 重誤りの訂正
1重誤りのとき同様,誤りシンボルをei, ej(i 6= j, ei, ej 6=0, ek = 0(k 6= i, j), 0≤ i, j≤n−1)とする. ei, ej以外は0であるから,式(6.4)は
(α0)iei+ (α0)jej=s0
(α1)iei+ (α1)jej=s1 (α2)iei+ (α2)jej=s2
(α3)iei+ (α3)jej=s3
(6.7)
となる. これらをまとめて,以下の式で扱う.
ei(αh)i+ej(αh)j=sh (h=0, 1, 2, 3) ··· 6.8° 方程式4つに対し未知数も4つ(i, j, ei, ej)であるから,解は必ず求められる. この連立方程式を解くために, 以下のような誤り位置方程式σ(x)を考える.
σ(x) = (x−αi)(x−αj) =x2+ (αi+αj)x+αiαj=0
この解となるxを求めることで,誤り位置を検出することができる. ここで,σ1= (αi+αj), σ2=αiαjとお くと,
σ(x) =x2+σ1x+σ2=0 ··· 6.9° となるので,まずはσ1σ2を求める. σ2について解くと,
σ2=αiαj= (σ1+αj)αj=σ1αj+α2j 同様に,
σ2=σ1αi+α2i よって,
α2i+σ1αi+σ2=0 α2j+σ1αj+σ2=0
54 第6章 リード・ソロモン符号
この2つの式と式(6.8)の積を取ると
ei(αh)i(α2i+σ1αi+σ2) +ej(αh)j(α2j+σ1αj+σ2) =0 eiαi(h+2)+ejαj(h+2)+σ1(eiαi(h+1)+ejαj(h+1)) +σ2(eiαi+ejαj) =0 よって,
sh+2+σ1sh+1+σ2sh=0(h=0, 1) ··· 6.10° sの値は既知であるから,この式からσを求めることができる. ここまでをまとめて整理する.
Def: RS符号の2重誤り訂正
¶ ³
まず,
sh+2+σ1sh+1+σ2sh=0(h=0, 1) の2本の式によってσ1, σ2を求める.
次に,
σ(x) =x2+σ1x+σ2=0 によって根xを2つ求める.
x=ai, aj であるから,iとj(誤り位置)が求められることになる. 最後に,
ei(αh)i+ej(αh)j=sh (h=0, 1, 2, 3) により,eiとejを求める. 正しい符号多項式c(x)は1重誤り同様
c(x) =R(x) +e(x) =R(x) +ei+ej
により求められる.
µ ´
¨
§
¥
例¦GF(24)上で考える. GF(2)上の原始多項式f(x)をf(x) =x4+x+1とし, f(α) =0, t=2とする. い ま,受信系列R(x)が以下の多項式であったとして,誤り検出,訂正を行う.
R(x) =x14+α6x8+α3x7+α2x6+α12x5+α13x4+α8x3+α4x2+α10x まず,シンドロームsを求める.
HR=
(α0)0 · · · (α0)14 (α1)0 · · · (α1)14 (α2)0 · · · (α2)14 (α3)0 · · · (α3)14
0 α10
α4 α8 α13
... 1
=
α α11 α12 α2
=
s0
s1
s2
s3
=s6=0
よって, Rが符号語でないのが確認できる. ここで注意して欲しいのが,Rの順番である. これを間違えると 全て台無しなので注意!!
1重誤りのチェックをする.
s1 s0
= s2 s1
= s3 s2
6.2 リード・ソロモン符号の復号 55
を満たさないのは明らかなので, Rは2重誤りである. 式(6.10)より
±
s3+s2σ1+s1σ2=0 s2+s1σ1+s0σ2=0 これを解くと,
σ1=α8, σ2=α5 式(6.9)より
σ(x) =x2+α8x+α5=0
これを因数分解して根を求めなくてはならないが,x∈0, 1, α,· · · , α14であることを利用し,全てを代入して 根を求めても良い.
σ(0) =α56=0
σ(1) =α8+α5+16=0 (6.11)
... (6.12)
結果は,
x=α6,=α14
よって,誤り位置i, jは14, 6となるので,e14, e6を求める. 式(6.8)のh=0, 1を用いて α=e6+e14
α11=e6α6+e14α14 解くと,
e6=α4, e14=1 よって正しい符号多項式c(x)は
c(x) =e(x) +R(x)
=x14+α4x6+x14+α6x8+· · ·+α10x
=α6x8+α3x7+α10x6+α12x5+α13x4+α8x3+α4x2+α10x
56 第6章 リード・ソロモン符号