誤り訂正の計算例(example.pdf, 7/20) - Kobe

情報数学特論: Reed-Solomon 符号の誤り訂正例
担当：桔梗宏孝
q 元体 Fq の原始元 α をとり，RS(q, 2) を考える。すなわち，
Cy + D ≡ (Ay 2 + By + 1)S(y) (mod y 4 )
誤り訂正能力 2 の場合を考える。
A, B, C, D ∈ F8 ，Cy + D と Ay 2 + By + 1 は互いに素
f ∈ RS(q, 2) ⇐⇒ f (α) = f (α2 ) = f (α3 ) = f (α4 ) = 0
が成り立つとき，
E(y) = ea y a + eb y b (誤り箇所は 2 つ)，
である。
Ay 2 + By + 1 = (1 − αa y)(1 − αb y),
Reed-Solomon 符号 f に対し誤り E が加わって，f1 になった
Cy + D = ea αa (1 − αb y) + eb αb (1 − αa y).
とする。
と書ける。
シンドローム多項式 S(y) は次の通りである。
S(y) = f1 (α4 )y 3 + f1 (α3 )y 2 + f1 (α2 )y + f1 (α)
4
3
3
2
例 1．Fq = F8 = F2 [x]/(1011) = {0, 1, 10, 11, 100, 101, 110, 111}
2
= E(α )y + E(α )y + E(α )y + E(α).
で考える。1011 は x3 + x + 1 のこと (係数ベクトル) である。
誤り位置が 2 箇所以内の誤り訂正には，次の鍵方程式の解
F8 の要素は係数ベクトルで表現された 2 次以下の F2 係数
Ω(y)，Λ(y) を求めればよい。
多項式である。和 + は F2 係数多項式としての和 (桁ごとの
4
Ω(y) ≡ Λ(y)S(y) (mod y )
mod 2 の和) で，積 · は F2 係数多項式としてかけた後に 1011
deg Ω(y) < deg Λ(y) ≤ 2
で割った余りをとる演算とする。α = 10 とすると，α のべきは
Ω(y) と Λ(y) は互いに素
次の表で表される。下の段が上の式の値である。
α2
α3
α4
α5
α6
α7
10 100
11
110 111
101
1
α
誤り箇所が誤り訂正能力以下の場合は，この鍵方程式の解は定
数倍を除いて一意的である。
さて，RS(8, 2) の Reed-Solomon 符号を受信したところ，
さて，E(y) の y a の係数が ea = 0 だったとする。
f1 = (α, α, α6 , α, 0, 0, α5 )
Sa (y) = ea αa (1 + αa y + α2a y 2 + α3a y 3 )
とおいて両辺を αa y 倍すると
αa ySa (y) = ea αa (αa y + α2a y 2 + α3a y 3 + α4a y 4 )
であったとする。シンドローム多項式の係数を計算すると
f1 (α) = α · α6 + α · α5 + α6 · α4 + α · α3 + α5
= 1 + α6 + α3 + α4 + α 5
両辺をそれぞれ引くと
(1 − αa y)Sa (y) = ea αa (1 − α4a y 4 )
= 1 + 101 + 11 + 110 + 111
となるので
= α4 ,
ea αa ≡ (1 − αa y)Sa (y) (mod y 4 ).
f1 (α2 ) = α2 ,
(i) 誤り箇所が 1 つの場合，E(y) = ea y a ，S(y) = Sa (y) と書
f1 (α3 ) = 1,
けるので，鍵方程式の解は定数倍を除いて
f1 (α4 ) = α5
ea αa ≡ (1 − αa y)S(y) (mod y 4 )
となる。ユークリッドの互除法により，鍵方程式の解を求める。
だけである。
(1) y 4 ≡ 0 · S(y) (mod y 4 )
事実 1．
(2) α5 y 3 + y 2 + α2 y + α4 ≡ 1 · S(y) (mod y 4 )
誤り箇所が 2 つ以内で，
(3) α ≡ (α2 y + α4 ) · S(y) (mod y 4 )
C ≡ (1 − Ay)S(y) (mod y 4 ) (A, C ∈ Fq )
(3) は (1) − (2) × 多項式で得られる。
が成り立つとき，
(α4 )−1 を (3) の両辺にかけると
E(y) = ea y a (誤り箇所は 1 つ)，
α4 ≡ (α5 y + 1)S(y) (mod y 4 )
C = ea αa ，A = αa と書ける。
事実 1 より，誤り多項式は E(y) = ea y a と書け，a = 5 である。
(ii) 誤り箇所が 2 つの場合，E(y) = ea y a + eb y b ，
また，事実 1 より，α4 = ea αa なので，ea = α6 である。した
S(y) = Sa (y) + Sb (y) と書ける。
がって，もとの符号 f は
ea αa ≡ (1 − αa y)Sa (y) (mod y 4 ),
f = (α, α5 , α6 , α, 0, 0, α5 )
eb αb ≡ (1 − αb y)Sb (y) (mod y 4 )
と推測される。
より，
ea αa (1 − αb y) + eb αb (1 − αa y)
≡ (1 − αa y)(1 − αb y)S(y) (mod y 4 )
鍵方程式の解は定数倍を除いてこれだけである。
事実 2．
誤り箇所が 2 つ以内で，
1
よって，誤り位置は，y 3 (3 次) の係数。
再び Reed-Solomon 符号を受信したところ，
f1 = (α, 1, α6 , 0, 0, 0, α5 )
4 = e3 · 33 .
であった。シンドローム多項式の係数を計算すると
33 = 6 = −1 より，e3 = 4 · (−1)−1 = −4 = 3.
f1 (α) = α，f1 (α2 ) = 0，f1 (α3 ) = α2 ，f1 (α4 ) = α4 である。
よって，元の符号は f1 (y) − 3y 3 で
(2, 4, 0, 1, 6, 3).
ユークリッドの互除法により，鍵方程式の解を求める。
y 4 ≡ 0 · S(y) (mod y 4 )
(1)
4 3
と推測される。
2 2
4
(2)
α y + α y + α ≡ 1 · S(y) (mod y )
(3)
α3 y 2 + α4 y + α2 ≡ (α3 y + α) · S(y) (mod y 4 )
再び Reed-Solomon 符号を受信したところ，
f1 = (2, 5, 0, 0, 6, 3)
であった。シンドローム多項式の係数を計算すると
((3) は (1) − (2) × 多項式による)
f1 (3) = 2，f1 (32 ) = 5，f1 (33 ) = 0，f1 (34 ) = 2 である。
α6 y + α4 ≡ (α4 y 2 + α5 y + α3 ) · S(y) (mod y 4 )
(4)
ユークリッドの互除法により，鍵方程式の解を求める。
(1) y 4 ≡ 0 · S(y) (mod y 4 )
((4) は (2) − (3) × 多項式による)
α
3 −1
を (4) の両辺にかけると
3
2
(2) 2y 3 + 5y + 2 ≡ 1 · S(y) (mod y 4 )
2
4
α y + α ≡ (αy + α y + 1)S(y) (mod y )
2
2
(3) y 2 + 6y ≡ −4y · S(y) (mod y 4 )
2
を得る。y = α とすると，αy + α y + 1 = 0 である。
((3) は (1) − (2) × 多項式による)
よって，
(4) 2 ≡ (y 2 + y + 1) · S(y) (mod y 4 )
αy 2 + α2 y + 1 = (α5 y + 1)(α3 y + 1)
((4) は (2) − (3) × 多項式による)
y = 2 とすると、mod 7 で、22 + 2 + 1 = 0. 2−1 = 4 なので、
事実 2 より，E(y) = ea y a + eb y b ，a = 5，b = 3，
(a = 3, b = 5 でもよい)
1 − 4y(= 1 + 3y) を因数にもつ。よって，
α3 y + α = ea αa (αb y + 1) + eb y b (αa y + 1)
y 2 + y + 1 = (1 − 4y)(1 − 2y) = (1 − 34 y)(1 − 32 y)
と書ける。よって，
事実 2 より，誤り多項式は E(y) = ea y 4 + eb y 2 で，
E(y) = α4 y 5 + αy 3
2 = e4 · 34 (1 − 32 y) + e2 y 2 (1 − 34 y)
であり，もとの符号は
と書ける。よって，y = 4, y = 2 と代入してみることにより，
f = (α, α5 , α6 , α, 0, 0, α5 )
E(y) = y 4 + 6y 2 = y 4 − y 2
と推測される。
であり，もとの符号は f1 (y) − E(y) で，
例 2．Fq = F7 = Z/(7) = {0, 1, 2, 3, 4, 5, 6}
(2, 4, 0, 1, 6, 3)
で考える。3 が 1 つの原始元である。標数が 2 でないので，符
と推測される。
号に注意が必要。
3 32
33
34
35
36
3
6
4
5
1
2
さて，RS(7, 2) の Reed-Solomon 符号を受信したところ，
f1 = (2, 4, 3, 1, 6, 3)
であったとする。シンドローム多項式の係数を計算 (mod 7 の
計算) すると
f1 (3) = 2 · 35 + 4 · 34 + 3 · 33 + 32 + 6 · 3 + 3 = 4
f1 (32 ) = 3， f1 (33 ) = 4，f1 (34 ) = 3．
ユークリッドの互除法により，鍵方程式の解を求める。
(1)
y 4 ≡ 0 · S(y) (mod y 4 )
(2) 3y 3 + 4y 2 + 3y + 4 ≡ 1 · S(y) (mod y 4 )
(3) 1 ≡ −(5y + 5) · S(y) (mod y 4 )
≡ (2y + 2) · S(y) (mod y 4 )
(3) は (1) − (2) × 多項式で得られる。
2−1 = 4 (in F7 ) を (3) の両辺にかけると
4 ≡ (y + 1)S(y) (mod y 4 )
係数は F7 なので，1 + y = 1 − 6y = 1 − 33 y ．
2

Download Report