誤り訂正符号エンコーダの回路 乗算器

前回のnote↑で乗算器について言及した。乗算器は片側定数で、$${GF(2^3)}$$ならば$${\times1, \times2, \times3}$$の3つ用意すればよい。

$${\times1}$$：$${1=\alpha^0}$$は乗算において単位元なので、何もしなくてよい。

$${\times2}$$：

$${x\times2=x\times\alpha^1}$$について、xをべき表現で表すと$${x=x_2\alpha^2 + x_1 \alpha + x_0 }$$のようになる。ただし$${x_i \in GF(2)}$$。ガロア体でも分配法則が成立するので

$$
\begin{array}{l}
x \times \alpha = (x_2\alpha^2 + x_1 \alpha + x_0) \times \alpha \\
= (x_2\alpha^3 + x_1 \alpha^2 + x_0 \alpha) \\
= (x_2(\alpha + 1) + x_1 \alpha^2 + x_0 \alpha) \\
= (x_1 \alpha^2 + (x_2 + x_0) \alpha + x_2) \\
\end{array}
$$

したがって実は各桁ごとに論理演算で書けば、

$$
\begin{array}{l}
0桁目：x_2 \\
1桁目：x_2 \oplus x_0 \\
2桁目：x_1 \\
\end{array}
$$

となる。回路では、

x2の回路

であって1つのXORゲートしか必要としない。

$${\times3}$$：

$${x\times3}$$：を同様に計算すると、

$$
\begin{array}{l}
x \times (\alpha+1) = (x_2\alpha^2 + x_1 \alpha + x_0) \times (\alpha+1) \\
= (x_1 \alpha^2 + (x_2 + x_0) \alpha + x_2) \\
+ (x_2\alpha^2 + x_1 \alpha + x_0)\\
= ((x_1 + x_2) \alpha^2 + (x_2 + x_1 + x_0) \alpha + (x_2 + x_0)) \\
\end{array}
$$

回路では

x3の回路

となる。