誤り訂正符号エンコーダの回路
情報多項式$${a(x)}$$、生成多項式$${g(x)}$$とすると、次のように符号を生成できる。
a(x)x^{n-k}をg(x)で割って余りr(x)を得る。
w(x) = a(x)x^{n-k} + r(x)を符号とする
多項式の除算を使うが、回路は比較的シンプルになる。
まず多項式除算について手続きの例を示す。$${GF(8)}$$の原始元$${\alpha}$$の最小多項式を$${x^3+x+1}$$とし、生成多項式は$${g(x) = x^4 + 3x^3 + x^2 + 2x + 3}$$とする(7, 3)RS符号を扱う。(1,3,4)を符号語に変換する。
(1,3,4)は情報多項式$${a(x) = 1x^2+3x+4}$$であるから$${a(x)x^4 = x^6+3x^5+4x^4 }$$を$${g(x)}$$で割る。
$$
\begin{array}{}
& x^{6} & x^5 & x^4 & x^3 & x^2 & x^1 & x^0\\
& 1 & 3 & 4 & \\
\times x^{4} & 1 & 3 & 1 & 2 & 3 \\
\hline
& & & 5 & 2 & 3 \\
\times 5x^{2} & & &5 & 4 & 5 & 1 & 4 \\
\hline
& & & & 6 & 6 & 1 & 4 \\
\end{array}
$$
したがって$${r(x) = 6x^4+6x^3 + x + 4}$$を得る。符号はこれを(1,3,4)の後ろに付け加えれば良い。回路的には$${x^{n-k}}$$をかけることはただの桁移動に相当するので、$${a(x)}$$と$${r(x)}$$はそのまま使われる。すなわち符号語は(1,3,4,6,6,1,4)となる。
また、基本的に誤り訂正符号が使われる用途は、誤りを含む通信路を通る場合であったり、メモリへの書き込み時であることから、情報は一度にはエンコーダには入ってこず、1サイクルに数シンボル送られてくる形が一般的である。1サイクルに1シンボルが送られてくるようなパイプライン方式の時の動作例を示す。
$$
\begin{array}{}
& x^{6} & x^5 & x^4 & x^3 & x^2 & x^1 & x^0\\
& 0 & 0 & 0 & \\
& 1 & & & \\
g(x)\times & 1\rightarrow & 3 & 1 & 2 & 3 \\
\hline
& & 3 & 1 & 2 & 3 \\
& & 3 & \\
g(x)\times & &0\rightarrow \\
\hline
& & & 1 & 2 & 3 \\
& & & 4 \\
g(x)\times & & &5 \rightarrow & 4 & 5 & 1 & 4 \\
\hline
& & & & 6 & 6 & 1 & 4\\
\end{array}
$$
計算手順としては、入力された情報シンボルと前回の最上位桁の係数とを足して、その結果で$${g(x)}$$の最大次数以外の各係数をかけ、前回の結果に足し合わせる。これを入力シンボルがなくなるまで繰り返せばよい。
このパイプライン方式のエンコーダを図に示す
controlは、inputが入力シンボルを供給するフェーズと、供給後に余りをたんに押し出すフェーズで回路動作を制御するために使用する。
さて、残る問題はガロア体の乗算器および加算器である。回路内ではベクトル表現的に、各桁を1つのFFで持ってガロア体シンボルを扱うとすると、加算器は単純で、各桁についてXORを取ればよいだけになる。一方で乗算器は、べき表現において加算をすれば良いと説明していた。それを回路で行うとなると、べき表現への変換回路を通って、2進数の加算器を通って、またベクトル表現への変換回路を通ることになり、やや大がかりである。実は回路上はもっと直接的に乗算器を作ることができる。しかし力尽きたので次回に続く。