はじめに
FPGA上に固定小数点の乗算を実装するとき、基本的には各言語の*演算子を使えば問題ない。
しかし、クロック周波数を高めるために処理をパイプライン化したい場合がある。
パイプライン化するためには、どのような処理を行っているかを理解しておく必要がある。
符号付き2進数の乗算を単純に考えると、
乗算前に入力の絶対値をとり符号無し2進数として乗算した後に
符号を戻せば符号なしと同じように計算できるが
こちらのサイトでは良くない例とされている。1
しかし、その後に続く説明がすぐには理解できなかったので2
4ビット同士の乗算を例に備忘録としてまとめる。
より一般化された式が知りたい場合はこちらのサイトが非常に参考になる。
参考サイトの結果がこちらの記事でまとめた内容と異なるため
同じ結果になる数式を作成し追記(2019/08/19)
符号なし2進数の乗算
符号なし2進数の乗算については、通常の筆算を行っていけば乗算結果が得られる。
a3 a2 a1 a0
*) b3 b2 b1 b0
----------------------------------------------------
p30 p20 p10 p00
p31 p21 p11 p01
p31 p22 p12 p02
+) p33 p23 p13 p03
----------------------------------------------------
P7 P6 P5 P4 P3 P2 P1 P0
入力をa、b、部分積をp、積をPとする。
部分積pはp{i}{j}=a{i}*b{j}として記述する。
符号付き2進数の乗算
符号付き2進数の乗算は最終的に以下の式で表される。
この式の導出方法を説明する。
a3 a2 a1 a0
*) b3 b2 b1 b0
----------------------------------------------------
1 ~p30 p20 p10 p00
~p31 p21 p11 p01
~p31 p22 p12 p02
+) 1 p33 ~p23 p~13 ~p03
----------------------------------------------------
P7 P6 P5 P4 P3 P2 P1 P0
入力をa、b、部分積をp、積をPとする。
部分積pはp{i}{j}=a{i}*b{j}として記述する。
~は反転を表す。
導出
符号無し2進数の場合、値は以下の式で表されるが
A = \sum_{i=0}^{n-1} a_i 2^i
符号付き2進数の場合、値は以下の式で表される。
A = - a_{n-1} 2^{n-1} + \sum_{i=0}^{n-2} a_i 2^i
つまり、符号付き2進数の乗算の式に各ビットの正負を表示すると以下の通りとなる。
-a3 +a2 +a1 +a0
*) -b3 +b2 +b1 +b0
----------------------------------------------------
展開すると
+) -p30 +p20 +p10 +p00
+) -p31 +p21 +p11 +p01
+) -p31 +p22 +p12 +p02
+) +p33 -p23 -p13 -p03
----------------------------------------------------
マイナスの項を分離すると
+) +p20 +p10 +p00
+) +p21 +p11 +p01
+) +p22 +p12 +p02
+) +p33
-) +p31 +p31 +p30 # マイナスの項を分離
-) +p23 +p13 +p03 # マイナスの項を分離
----------------------------------------------------
2の補数の減算を加算に変換して、+の表示を省略すると
+) p20 p10 p00
+) p21 p11 p01
+) p22 p12 p02
+) p33
+) 1 1 ~p31 ~p31 ~p30 1 1 1 # 反転
+) 1 # +1
+) 1 1 ~p23 p~13 ~p03 1 1 1 # 反転
+) 1 # +1
----------------------------------------------------
これを整理すると
+) 1 ~p30 p20 p10 p00
+) ~p31 p21 p11 p01
+) ~p31 p22 p12 p02
+) 1 p33 ~p23 p~13 ~p03
----------------------------------------------------
以上から最初の式が得られていることがわかる。
数式による導出(2019/08/19追記)
数式を使えばより一般的なnビット × mビットの乗算結果を得ることができる。
\begin{eqnarray}
A \cdot B
&=&
\left(
- a_{n-1} 2^{n-1}
+ \sum_{i=0}^{n-2} a_{i} 2^{i}
\right)
\left(
- b_{m-1} 2^{m-1}
+ \sum_{j=0}^{m-2} b_{j} 2^{j}
\right) \\
&=&
a_{n-1} b_{m-1} 2^{n+m-2}
- \sum_{j=0}^{m-2} a_{n-1} b_{j} 2^{n+j-1}
- \sum_{i=0}^{n-2} a_{i} b_{m-1} 2^{i+m-1}
+ \sum_{i=0}^{n-2} a_{i} 2^{i} \sum_{j=0}^{m-2} b_{j} 2^{j}
\end{eqnarray}
ここで2項目の式をn+mビットに拡張表示し、減算を加算に変換すると
\begin{eqnarray}
- \sum_{j=0}^{m-2} a_{n-1} b_{j} 2^{n+j-1}
&=&
- \left(
\sum_{j=0}^{m-2} a_{n-1} b_{j} 2^{n+j-1}
\right) \\
&=&
- \left(
- 0 \cdot 2^{n+m-1}
+ 0 \cdot 2^{n+m-2}
+ \sum_{j=0}^{m-2} a_{n-1} b_{j} 2^{n+j-1}
+ \sum_{k=0}^{n-2} 0 \cdot 2^{k}
\right) \\
&=&
+ \left(
- \overline{0} \cdot 2^{n+m-1}
+ \overline{0} \cdot 2^{n+m-2}
+ \sum_{j=0}^{m-2} \overline{a_{n-1} b_{j}} 2^{n+j-1}
+ \sum_{k=0}^{n-2} \overline{0} \cdot 2^{k}
\right)
+ 1 \\
&=&
- 2^{n+m-2}
+ \sum_{j=0}^{m-2} \overline{a_{n-1} b_{j}} 2^{n+j-1}
+ 2^{n-1}
\end{eqnarray}
3項目も同様にして
\begin{eqnarray}
- \sum_{i=0}^{n-2} a_{i} b_{m-1} 2^{i+m-1}
=
- 2^{m+n-2}
+ \sum_{i=0}^{n-2} \overline{a_{i} b_{m-1}} 2^{i+m-1}
+ 2^{m-1}
\end{eqnarray}
以上から
A \cdot B
=
- 2^{n+m-1}
+ a_{n-1} b_{m-1} 2^{n+m-2}
+ \sum_{j=0}^{m-2} \overline{a_{n-1} b_{j}} 2^{n+j-1}
+ \sum_{i=0}^{n-2} \overline{a_{i} b_{m-1}} 2^{i+m-1}
+ \sum_{i=0}^{n-2} a_{i} 2^{i} \sum_{j=0}^{m-2} b_{j} 2^{j}
+ 2^{n-1}
+ 2^{m-1}
特にn=mときは
A \cdot B
=
- 2^{2n-1}
+ a_{n-1} b_{n-1} 2^{2n-2}
+ \sum_{j=0}^{n-2} \overline{a_{n-1} b_{j}} 2^{n+j-1}
+ \sum_{i=0}^{n-2} \overline{a_{i} b_{n-1}} 2^{n+i-1}
+ \sum_{i=0}^{n-2} a_{i} 2^{i} \sum_{j=0}^{n-2} b_{j} 2^{j}
+ 2^{n}
4ビット同士の乗算の式との対応関係を見ると以下の通りである。
+) 1 ~p30 p20 p10 p00
+) ~p31 p21 p11 p01
+) ~p31 p22 p12 p02
+) 1 p33 ~p23 p~13 ~p03
----------------------------------------------------
+) 1 # 1項目
+) p33 # 2項目
+) ~p31 ~p31 ~p30 # 3項目
+) ~p23 p~13 ~p03 # 4項目
+) p20 p10 p00 # 5項目(j=0)
+) p21 p11 p01 # 5項目(j=1)
+) p22 p12 p02 # 5項目(j=2)
+) 1 # 6項目
----------------------------------------------------
P7 P6 P5 P4 P3 P2 P1 P0
参考
http://www.kumikomi.net/archives/2010/07/ep21suc2.php?page=2
http://zakii.la.coocan.jp/digital/40_2s_complement.htm
http://zakii.la.coocan.jp/digital/42_mult_baugh_wooley.htm
https://wentwayup.tamaliver.jp/e165237.html