本noteではユークリッド復号法のハードウェア実装の説明の準備として、ユークリッド復号法を別表現で解いておく。

符号は

と同じ(15, 11)RS符号とし、受信語は(1,2,3,4,5,11,7,8,9,10,11,3,1,12,12)すなわち、受信多項式は$${R(x) = x^{14} + 2x^{13} + 3x^{12} + 4x^{11} + 5x^{10} +11x^9 + 7x^8 + 8x^7+9x^6+10x^5 + 11x^4 + 3x^3+x^2+12x+12 }$$とする。

シンドローム計算

ホーナー法で示した方法で解ける。$${S_0 = 15, S_1=3, S_2=4,S_3=12}$$

多項式ユークリッド互除法

シンドローム多項式は

$$
S(x)=S_3x^3 + S_2x^2+S_1x + S_0 \\
= 12x^3 + 4x^2 + 3x + 15
$$

$${a_0(x) = x^{2t} = x^4, a_1(x) = S(x)}$$として除算を行う。

$$
\begin{array}{}
       　　　　&  x^{4} & x^3 & x^2 & x^1 & x^0\\ 
       　　　　& 1 & 0 & 0 & 0 &  0  \\
\times 10x     & 1 & 14 & 13 & 12 & \\
\hline
                     &    & 14 & 13 & 12 & 0 \\
\times 6        &    &  14 &11 & 10 & 4 & \\
\hline
                     &    &    & 6 & 6 & 4  \\
\end{array}
$$

余り$${a_2(x)= 6x^2 + 6x^1 + 4}$$は次数が$${t = 2}$$以上なので継続。

回路実装を想定した計算手順

回路実装を想定すると、この時行列計算も並列に行いレイテンシを短くする。行列要素をレジスタに格納するとし、i行j列の要素を$${m_{ij}}$$とすると

1サイクルの終わり：

$$
m_{11} = 0 \\
m_{12} = 1 \\
m_{21} = 1 \\
m_{22} = a_2(x) \\
$$

次サイクル以降は：

$$
m_{11} = m_{21} \\
m_{12} = m_{22} \\
m_{21} = m_{11} + a_3(x)m_{21} \\
m_{22} = m_{12} + a_3(x)m_{22} \\
$$

と計算していけば、最終的に$${\eta(x) = m_{21}, \sigma(x)=m_{22}}$$(正確には、さらに定数倍して$${\sigma(x)}$$の定数項が1になるようにしたものが答え)が得られる。

a_2(x)を得たときの値と辻褄が合うように初期値を決めると：

$$
m_{11} = 1 \\
m_{12} = 0 \\
m_{21} = 0 \\
m_{22} = 1 \\
$$

すなわち単位行列にしておけばよい。a_2(x)をかける操作は、上記の割り算の部分商をかける操作として、毎サイクル進めることができる。すなわち、除算で得た部分商から$${m_{22}}$$を求める操作も除算の横に示すと：

$$
\begin{array}{}
       　　　　&  x^{4} & x^3 & x^2 & x^1 & x^0 &&& x^1 & x^0\\ 
       　　　　& 1 & 0 & 0 & 0 &  0  &&& 0& 0 & (m_{12}の現在値)\\ 
\times 10x     & 1 & 14 & 13 & 12 & &&& 10 & 0& (m_{22}の現在値にかける)\\
\hline
                     &    & 14 & 13 & 12 & 0 &&& 10 & 0\\
\times 6        &    &  14 &11 & 10 & 4 &&& 0 & 6\\
\hline
                     &    &    & 6 & 6 & 4  &&& 10 & 6 \\ 
\end{array}
$$

さて、次の繰り返しでは$${a_1(x)}$$を$${a_2(x)}$$で割って

$$
\begin{array}{}
       　　　　&  x^{3} & x^2 & x^1 & x^0 &&& x^2&x^1 & x^0\\
       　　　　& 12 & 4 & 3 & 15    &&& 0 & 0 & 1\\
\times 2x      & 12 & 12 & 8 & &&& 7 & 12& 0\\
\hline
                     &    & 8 & 11 & 15 &&& 7 & 12 & 1\\
\times 13     &    & 8 & 8 & 1 &&& 0 & 11 & 8\\
\hline
                     &    &    & 3 & 14   &&& 7 & 7 & 9\\
\end{array}
$$

余り$${a_3(x)= 3x^1 + 14}$$は次数が$${t = 2}$$より小さいので終了。この$${7x^2+7x+9}$$について、定数項が1になるように$${9}$$で割れば$${\sigma(x)}$$を得ることができる。したがって$${\sigma(x) = 14x^2+14x+1}$$。また、$${\eta(x) = m_{21}/9 = a_3(x)/9 = 6x+15}$$も得ることができる。