Help us understand the problem. What is going on with this article?

符号付き2進数の乗算

More than 1 year has passed since last update.

はじめに

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

入力をab、部分積をp、積をPとする。
部分積pp{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

入力をab、部分積をp、積をPとする。
部分積pp{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


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

  2. どうですか?簡単でしょ?と書いてあるが 

ryo_i6
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした