有限体の勉強 〜リード・ソロモン符号の誤り訂正の原理〜 [数学]
前回の記事で、リード・ソロモン符号の符号化と誤り訂正のシミュレーションをしてみました。その中で、誤り訂正についてはWikipediaの記事どおりにやってみただけで、その原理についてはまだ理解していませんでした。今回それを若干理解できたつもりになったので紹介します。
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
コメント 0