ユークリッド復号法

ユークリッド復号法(Euclidean decoding algorithm)は、拡張ユークリッドアルゴリズムを利用して復号を行う方法である。

$${GF(2^m)}$$の原始元$${\alpha}$$。$${(n=2^m-1,k,d_{min})}$$原始BCH符号において、生成多項式$${g(x)}$$の連続根を$${\alpha, \alpha^2, \cdots, \alpha^{2t} \in GF(2^m)}$$とする。また、
符号多項式$${w(x)}$$
受信多項式$${v(x)}$$
誤り多項式$${e(x)}$$

とする。

　いま、誤りは$${s}$$個($${s \leq t}$$)あるとし、その誤り位置の集合を$${I = \lbrace i_1, i_2, \cdots,i_s \rbrace}$$とする。すなわち誤り多項式は

$$
e(x) = x^{i_1} + x^{i_2} + \cdots + x^{i_s} = \sum_{k=1}^s x^{i_k}
$$

と表される。

このとき、シンドロームは

$$
S_j = v(\alpha^j) = e(\alpha^j) = \sum_{k=1}^s (\alpha^j)^{i_k}, (j=1,2,\cdots,2t)
$$

となる。誤り位置多項式は

$$
\sigma(z) = \prod_{k=1}^s (1 - \alpha^{i_k}z)
$$

$${\sigma(z)}$$の根は$${\alpha^{-i_k}, (k = 1,2,\cdots,s)}$$より誤りロケータは$${\alpha^{i_k}, (k = 1,2,\cdots,s)}$$となる。

シンドローム$${S_j}$$を係数とする多項式をシンドローム多項式といい、

$$
S(z) = S_1 + S_2z + \cdots + S_{2t}z^{2t-1} \\
= \sum_{j=1}^{2t}S_jz^{j-1}
= \sum_{k=1}^{s}\sum_{j=1}^{2t}(\alpha^{i_k})^jz^{j-1}
$$

となる。ところで形式的に、

$$
\dfrac{\alpha^{i_k}}{1 - \alpha^{i_k}z} = \sum_{j=1}^{\infty}\alpha^{i_k}(\alpha^{i_k}z)^{j-1}
= \sum_{j=1}^{\infty}(\alpha^{i_k})^jz^{j-1}
$$

と展開できる。この式を用いると、

$$
\sum_{j=1}^{2t}(\alpha^{i_k})^jz^{j-1}
\equiv 
\dfrac{\alpha^{i_k}}{1 - \alpha^{i_k}z}, (mod z^{2t})
$$

という関係が得られる。したがって、

$$
S(z) \equiv \sum_{k=1}^{s}\dfrac{\alpha^{i_k}}{1 - \alpha^{i_k}z}, (mod z^{2t})
$$

となる。この式の両辺に誤り位置多項式$${\sigma(z)}$$をかけると、

$$
式(6.74) \\
\sigma(z)S(z)
\equiv 
\prod_{k=1}^s (1 - \alpha^{i_k}z)
\sum_{k=1}^{s}\dfrac{\alpha^{i_k}}{1 - \alpha^{i_k}z}, (mod z^{2t}) \\
\equiv 
(1 - \alpha^{i_2}z)(1 - \alpha^{i_3}z) \cdots (1 - \alpha^{i_s}z)\alpha^{i_1} \\
(1 - \alpha^{i_1}z)(1 - \alpha^{i_3}z) \cdots (1 - \alpha^{i_s}z)\alpha^{i_2} \\
(1 - \alpha^{i_1}z)(1 - \alpha^{i_2}z) \cdots (1 - \alpha^{i_s}z)\alpha^{i_3} // i_3の項なし\\
\cdots \\
 (1 - \alpha^{i_1}z)(1 - \alpha^{i_2}z) \cdots (1 - \alpha^{i_{s-1}}z)\alpha^{i_s} , (mod z^{2t}) \\
$$

となる。ここで、右辺を誤り評価多項式といい$${\eta(z)}$$と表す。

明らかに$${deg \lbrace \eta(z)\rbrace =s-1 \leq t-1, deg \lbrace \sigma(z)\rbrace \leq t }$$である。$${式(6.74)}$$より、両辺の差は$${ z^{2t}}$$で割り切れる。そこで、商を$${\phi(z)}$$とすれば、

$$
\eta(z) - \sigma(z)S(z) = \phi(z)z^{2t}, (deg\lbrace \eta(z) \rbrace = s-1 \leq t -1 , deg \lbrace \sigma(z) \rbrace=t) \\
\eta(z) = \phi(z)z^{2t} + \sigma(z)S(z), (deg\lbrace \eta(z) \rbrace = s-1 \leq t -1 , deg \lbrace \sigma(z) \rbrace=t) (式(6.76))
$$

と表すことができる。この中で$${z^{2t}}$$と$${S(z)}$$が既知なので、これらに拡張ユークリッドアルゴリズムを適用することで$${\sigma(z)}$$と$${\eta(z)}$$を求めることができる。

まず$${a_0(z)=z^{2t}, a_1(z) = S(z)}$$とおく、

$$
a_0(z) = q_1(z)a_1(z) + a_2(z), (deg \lbrace a_2(z) \rbrace \leq  deg\lbrace a_1(z) \rbrace) \\
a_1(z) = q_2(z)a_2(z) + a_3(z), (deg \lbrace a_3(z) \rbrace \leq  deg\lbrace a_2(z) \rbrace) \\
\vdots
a_{n-2}(z) = q_{n-1}(z)a_{n-1}(z) + a_n(z), (deg \lbrace a_{n}(z) \rbrace \leq  deg\lbrace a_{n-1}(z) \rbrace) \\
$$

ここで、この計算は割り切れるまでは続けずに、$${deg \lbrace a_{n}(z) \rbrace \leq t-1}$$となった時点で終了する。
拡張ユークリッドアルゴリズムと同様に行列で表せば

$$
\begin{pmatrix}
a_{n-1}(z) \\
a_{n}(z) \\
\end{pmatrix}
=
\begin{pmatrix}
q_{n-1}(z) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
q_{n-2}(z) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1} \\
\cdots 
\begin{pmatrix}
q_2(z) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
q_1(z) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
a_0(z) \\
a_1(z) \\
\end{pmatrix} \\
= 
\begin{pmatrix}
0 & 1 \\
1 & -q_{n-1}(z) \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -q_{n-2}(z) \\
\end{pmatrix} \\
\cdots
\begin{pmatrix}
0 & 1 \\
1 & -q_2(z) \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -q_1(z) \\
\end{pmatrix}
\begin{pmatrix}
a_0(z) \\
a_1(z) \\
\end{pmatrix} \\
$$

となり、$${a_n(z) = u_0(z)a_0(z) + u_1(z)a_1(z)}$$と表される。すなわち
$${a_n(z) = u_0(z)z^{2t} + u_1(z)S(z)}$$と表される。式(6.76)と比較することで、

$$
\eta(z) = \gamma a_n(z) , \sigma(z) = \gamma u_1(z)
$$

が求められる。$${\gamma}$$は$${\sigma(z)}$$の定数項が1となるように定める。