序文 §
LFSRの勉強をしていた際に、Berlekamp-Messeyのアルゴリズムが出てきたのでそれ関連でリードソロモン符号について調べてみたら、結構凄さを感じたアルゴリズムだったので紹介します。
問題設定 §
次のような符号化を考える(最初に考案されたリードソロモン符号)。
メッセージ長をm m m n n n n − m − 1 2 \frac{n - m - 1}2 2 n − m − 1
各バイトやパケットを有限体F p \mathbb F_p F p F p \mathbb F_p F p m − 1 m-1 m − 1 f ( x ) f(x) f ( x )
長さn n n
c i = f ( a i ) c_i = f(a_i) c i = f ( a i ) ここでa i a_i a i i ≠ j i \neq j i = j F p \mathbb F_p F p
この符号C = ( f ( a 1 ) , f ( a 2 ) , … , f ( a n ) ) C = (f(a_1), f(a_2), \dots, f(a_n)) C = ( f ( a 1 ) , f ( a 2 ) , … , f ( a n )) n − m − 1 2 \frac{n-m-1}2 2 n − m − 1 k k k k ≔ n − m − 1 2 k\coloneqq \frac{n-m-1}2 k : = 2 n − m − 1
アルゴリズムの大まかな流れはq ( x ) = e ( x ) f ( x ) q(x) = e(x)f(x) q ( x ) = e ( x ) f ( x ) q ( x ) , e ( x ) q(x), e(x) q ( x ) , e ( x ) q ( x ) e ( x ) \frac{q(x)}{e(x)} e ( x ) q ( x ) f ( x ) f(x) f ( x )
アルゴリズム §
input: 受信した(k k k ( y 1 , y 2 , … , y n ) (y_1, y_2, \dots, y_n) ( y 1 , y 2 , … , y n )
output: f ( x ) f(x) f ( x )
アルゴリズム本体の前に前節の最後で触れたg ( x ) , e ( x ) g(x), e(x) g ( x ) , e ( x ) e ( x ) e(x) e ( x ) y i ≠ f ( a i ) y_i \neq f(a_i) y i = f ( a i ) y i y_i y i
E ≔ { a i ∣ y i ≠ f ( a i ) } e ( x ) ≔ ∏ i ∈ E ( x − a i )
\begin{aligned}
E &\coloneqq \{a_i \mid y_i \neq f(a_i)\} \cr
e(x) &\coloneqq \prod_{i \in E} (x - a_i)
\end{aligned}
E e ( x ) : = { a i ∣ y i = f ( a i )} : = i ∈ E ∏ ( x − a i )
このe ( x ) e(x) e ( x ) i i i
e ( a i ) f ( a i ) = e ( a i ) y i
e(a_i)f(a_i) = e(a_i)y_i
e ( a i ) f ( a i ) = e ( a i ) y i
誤りがない、つまりy i = f ( a i ) y_i = f(a_i) y i = f ( a i ) e ( a i ) = 0 e(a_i) = 0 e ( a i ) = 0 q ( x ) ≔ e ( x ) f ( x ) q(x) \coloneqq e(x)f(x) q ( x ) : = e ( x ) f ( x ) q ( a i ) − e ( a i ) y i = 0 q(a_i) - e(a_i)y_i = 0 q ( a i ) − e ( a i ) y i = 0 i i i
ここで、q ( x ) q(x) q ( x ) e ( x ) e(x) e ( x ) e ( x ) e(x) e ( x ) k k k k k k q ( x ) q(x) q ( x ) k + m k+m k + m k + m + 1 k+m+1 k + m + 1 2 k + m + 1 2k+m+1 2 k + m + 1 a i a_i a i n ≥ 2 k + m + 1 n \geq 2k+m+1 n ≥ 2 k + m + 1
e ( x ) , q ( x ) e(x), q(x) e ( x ) , q ( x )
e ( x ) ≔ ∑ j = 0 k e j x j q ( x ) ≔ ∑ j = 0 k + m q j x j
\begin{aligned}
e(x) \coloneqq \sum_{j=0}^k e_jx^j\cr
q(x) \coloneqq \sum_{j=0}^{k+m} q_jx^j
\end{aligned}
e ( x ) : = j = 0 ∑ k e j x j q ( x ) : = j = 0 ∑ k + m q j x j
これを用いると任意のi i i
q 0 + q 1 a i + q 2 a i 2 + ⋯ + q k + m a i k + m − y i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e k − 1 a i k − 1 + a i k ) = 0
q_0 + q_1a_i + q_2a_i^2 + \dots + q_{k+m}a_i^{k+m} - y_i(e_0 + e_1a_i + e_2a_i^2 + \dots + e_{k-1}a_i^{k-1} + a_i^k) = 0
q 0 + q 1 a i + q 2 a i 2 + ⋯ + q k + m a i k + m − y i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e k − 1 a i k − 1 + a i k ) = 0
e e e k k k − y i a i k -y_ia_i^k − y i a i k
q 0 + q 1 a i + q 2 a i 2 + ⋯ + q k + m a i k + m − y i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e k − 1 a i k − 1 ) = y i a i k
q_0 + q_1a_i + q_2a_i^2 + \dots + q_{k+m}a_i^{k+m} - y_i(e_0 + e_1a_i + e_2a_i^2 + \dots + e_{k-1}a_i^{k-1}) = y_ia_i^k
q 0 + q 1 a i + q 2 a i 2 + ⋯ + q k + m a i k + m − y i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e k − 1 a i k − 1 ) = y i a i k
未知数であるe j , q j e_j, q_j e j , q j i i i
( 1 a 1 a 1 2 … a 1 k + m − y 1 − y 1 a 1 − y 1 a 1 2 … y 1 a 1 k − 1 1 a 2 a 2 2 … a 2 k + m − y 2 − y 2 a 2 − y 2 a 2 2 … y 2 a 2 k − 1 ⋮ 1 a n a n 2 … a n k + m − y n − y n a n − y n a n 2 … y n a n k − 1 ) ( q 0 q 1 q 2 ⋮ q k + m e 0 e 1 e 2 ⋮ e k − 1 ) = ( y 1 a 1 k y 2 a 2 k ⋮ y n a n k )
\begin{pmatrix}
1 & a_1 & a_1^2 &\dots& a_1^{k+m} & -y_1 & -y_1a_1 & -y_1a_1^2 & \dots & y_1a_1^{k-1} \cr
1 & a_2 & a_2^2 &\dots& a_2^{k+m} & -y_2 & -y_2a_2 & -y_2a_2^2 & \dots & y_2a_2^{k-1} \cr
&&&&&\vdots \cr
1 & a_n & a_n^2 &\dots& a_n^{k+m} & -y_n & -y_na_n & -y_na_n^2 & \dots & y_na_n^{k-1} \cr
\end{pmatrix} \begin{pmatrix}
q_0 \cr q_1 \cr q_2 \cr \vdots \cr q_{k+m} \cr
e_0 \cr e_1 \cr e_2 \cr \vdots \cr e_{k-1}
\end{pmatrix} = \begin{pmatrix}
y_1a_1^k \cr y_2 a_2^k \cr \vdots \cr y_na_n^k
\end{pmatrix}
⎝ ⎛ 1 1 1 a 1 a 2 a n a 1 2 a 2 2 a n 2 … … … a 1 k + m a 2 k + m a n k + m − y 1 − y 2 ⋮ − y n − y 1 a 1 − y 2 a 2 − y n a n − y 1 a 1 2 − y 2 a 2 2 − y n a n 2 … … … y 1 a 1 k − 1 y 2 a 2 k − 1 y n a n k − 1 ⎠ ⎞ ⎝ ⎛ q 0 q 1 q 2 ⋮ q k + m e 0 e 1 e 2 ⋮ e k − 1 ⎠ ⎞ = ⎝ ⎛ y 1 a 1 k y 2 a 2 k ⋮ y n a n k ⎠ ⎞
これが解ければ、e ( x ) e(x) e ( x ) q ( x ) q(x) q ( x ) q ( x ) q(x) q ( x ) e ( x ) e(x) e ( x ) f ( x ) f(x) f ( x )
実装(SageMath) §
K = GF ( 521 )
PR .<x> = PolynomialRing (K)
m = 5
coeffs = [K. random_element () for _ in range (m)]
f = PR (coeffs)
k = 3
n = 2 *k+m+ 1
A = [i+ 1 for i in range (n)]
code = [ f (a) for a in A]
for _ in range (k):
i = randint ( 0 , 11 )
code[i] = K. random_element ()
M = []
v = []
for i in range (n):
row_left = [ K (A[i])^e for e in range (k+m+ 1 )]
row_right = [-code[i] * K (A[i])^e for e in range (k)]
row = row_left + row_right
v. append (code[i]* K (A[i])^k)
M. append (row)
M = matrix (K, M)
v = vector (K, v)
polys = M. solve_right (v)
q = PR ( list (polys[:k+m+ 1 ]))
e = PR ( list (polys[k+m+ 1 :]) + [ 1 ])
assert q / e == f
References §