符号付き2進数の乗算

# はじめに

FPGA上に固定小数点の乗算を実装するとき、基本的には各言語の`*`演算子を使えば問題ない。
しかし、クロック周波数を高めるために処理をパイプライン化したい場合がある。
パイプライン化するためには、どのような処理を行っているかを理解しておく必要がある。

符号付き2進数の乗算を単純に考えると、
乗算前に入力の絶対値をとり符号無し2進数として乗算した後に
符号を戻せば符号なしと同じように計算できるが
[こちらのサイト](http://www.kumikomi.net/archives/2010/07/ep21suc2.php?page=2)では良くない例とされている。[^1]

[^1]: 悲しいことにVHDLのnumeric_stdではそのように実装されているように見えるが、論理合成時に最適化されるので問題ないとの判断だろう。

しかし、その後に続く説明がすぐには理解できなかったので[^2]
4ビット同士の乗算を例に備忘録としてまとめる。

[^2]: どうですか？簡単でしょ？と書いてあるが

より一般化された式が知りたい場合は[こちらのサイト](http://zakii.la.coocan.jp/digital/42_mult_baugh_wooley.htm)が非常に参考になる。

参考サイトの結果がこちらの記事でまとめた内容と異なるため
同じ結果になる数式を作成し追記(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進数の場合、値は以下の式で表されるが

```math
A = \sum_{i=0}^{n-1} a_i 2^i
```
符号付き2進数の場合、値は以下の式で表される。

```math
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ビットの乗算結果を得ることができる。

```math
\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ビットに拡張表示し、減算を加算に変換すると

```math
\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項目も同様にして

```math
\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}
```

以上から

```math
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ときは

```math
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