乗算器その1 - kivantium活動日記

この記事はkivantium Advent Calendarの7日目です。

昨日は乗算器の準備のために順序回路の構成要素であるラッチとフリップフロップについて簡単に触れ、シフトレジスタを導入しました。今日は掛け算を行う回路を作っていこうと思います。

単純な符号なし乗算器その1

掛け算の基本的考え方は筆算です。簡単のためにしばらく符号なし整数を考えます。
4bitで11x14=154を二進数の筆算でやると

    1011
  x)1110
  ------
    0000
   1011
  1011
 1011
 -------
10011010

のようになります。

この筆算を素直に回路に直すと以下のようになります。

MUXはマルチプレクサの意味で、横からの制御入力が0（B[0]とか）なら左側の入力(つまり0)を出力し、1なら右側の入力（A[n-1:0]とか）を出力します。各bitごとに

A	B	Select	Out
0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	1

という真理値表を持つゲートをbit数だけ並べればマルチプレクサは作れるのでこれもNANDゲートだけでできます。入力を増やしたマルチプレクサもよく使います。
また、最初の加算器に入る左側のマルチプレクサの入力{A[n-1:0], 0}はVerilog HDLの記法でA[n-1:0]の右側に0を追加したものを表します。

この回路でも確かに掛け算は実現できるのですが、割とゲートを必要とする加算器をbit数の分だけ直列に並べるこの回路はトランジスタ使用数の点からも速度の点からも使いにくいので改善していく必要があります。

単純な符号なし乗算器その2

昨日作ったシフトレジスタを使って加算器の数を減らした乗算器は次のようになります。

これはクロック入力のたびにマルチプレクサの入力を変更し、シフトレジスタをずらしていくことでbit数ぶんのクロックで掛け算を計算する回路です。

これは加算器を1つしか使わないので資源は節約できますが、クロックの分だけ待つことになりこれまた遅いです。

符号付き乗算器

今までは符号なし整数同士の掛け算を考えてきましたが、この方法を符号あり整数に拡張するには工夫が必要になります。
筆算で上に来る数が負の場合は足し算の際に符号拡張（値が負の数となるように答えのbit数の長さになるよう1で埋める必要がある）が必要になり、下に来る数が負の数の場合は一番上の符号bitの扱いを変える必要があるなど、さっきの方法を拡張するのは少し面倒です。

符号付き整数の掛け算を行う方法としてBaugh-Wooleyアルゴリズムを紹介します。
$n$bitの符号付き整数$A$は第$i$bitの数を$a_i$とすると
$$A = -2^{n-1}\cdot a_{n-1} + \sum_{i=0}^{n-2}2^i \cdot a_i$$
と書けます。このとき、Aと$m$bitの符号付き整数$B$との積は、
${\displaystyle \begin{align} A \times B &= (-2^{n-1}\cdot a_{n-1} + \sum_{i=0}^{n-2}2^i \cdot a_i) (-2^{m-1}\cdot b_{m-1} + \sum_{j=0}^{m-2}2^i \cdot b_j) \\ &= 2^{n+m-2}\cdot a_{n-1}b_{m-1}+(-2^{n-1}\cdot a_{n-1})\sum_{j=0}^{m-2}2^i \cdot b_j \\ & \quad + (-2^{m-1}\cdot b_{m-1})\sum_{i=0}^{n-2}2^i \cdot a_i + \sum_{i=0}^{n-2}2^i \cdot a_i \sum_{j=0}^{m-2}2^i \cdot b_j \\ &= 2^{n+m-2}\cdot a_{n-1}b_{m-1}+(2^{n-1})(-\sum_{j=0}^{m-2}2^i \cdot a_{n-1}b_j) \\ & \quad + (2^{m-1})(-\sum_{i=0}^{n-2}2^i \cdot a_ib_{m-1}) + \sum_{i=0}^{n-2}\sum_{j=0}^{m-2}2^{i+j} \cdot a_ib_j \\ \end{align} }$

ここで、「bit反転+1」という操作がnビット符号なし整数$X$を$2^n-X$に変更する操作であることに注意すると、
${\displaystyle \begin{align} &= 2^{n+m-2}\cdot a_{n-1}b_{m-1}+(2^{n-1})(-2^{m-1}+1+\sum_{j=0}^{m-2}2^i \cdot \overline{a_{n-1}b_j}) \\ & \quad + (2^{m-1})(-2^{n-1}+1+\sum_{i=0}^{n-2}2^i \cdot \overline{a_ib_{m-1}})+ \sum_{i=0}^{n-2}\sum_{j=0}^{m-2}2^{i+j} \cdot a_ib_j \\ &= 2^{n+m-2}\cdot a_{n-1}b_{m-1}+\sum_{j=0}^{m-2}2^{n+i-1} \cdot \overline{a_{n-1}b_j} \\ & \quad + \sum_{i=0}^{n-2}2^{m+i-1} \cdot \overline{a_ib_{m-1}}+ \sum_{i=0}^{n-2}\sum_{j=0}^{m-2}2^{i+j} \cdot a_ib_j +(2^{n-1}+2^{m-1}-2^{n+m-1})\\ &= 2^{n+m-2}\cdot a_{n-1}b_{m-1}+\sum_{j=0}^{m-2}2^{n+i-1} \cdot \overline{a_{n-1}b_j} \\ & \quad + \sum_{i=0}^{n-2}2^{m+i-1} \cdot \overline{a_ib_{m-1}}+ \sum_{i=0}^{n-2}\sum_{j=0}^{m-2}2^{i+j} \cdot a_ib_j +(2^{n-1}+2^{m-1}+2^{n+m-1})-2^{n+m}\\ \end{align} }$
従って、
${\displaystyle \begin{align} &2^{n+m-2}\cdot a_{n-1}b_{m-1}+\sum_{j=0}^{m-2}2^{n+i-1} \cdot \overline{a_{n-1}b_j} \\ & \quad + \sum_{i=0}^{n-2}2^{m+i-1} \cdot \overline{a_ib_{m-1}}+ \sum_{i=0}^{n-2}\sum_{j=0}^{m-2}2^{i+j} \cdot a_ib_j +(2^{n-1}+2^{m-1}+2^{n+m-1}) \end{align} }$
は求める積より$2^{n+m}$大きい値になりますが、結果を(n+m)bitの変数に格納する場合$2^{n+m}$は溢れるので反映されません。
よって最後の式を計算すれば符号付き整数同士の積が求まります。
$n=m=4$の場合にこの式を筆算で表すと

${\displaystyle \begin{array}{ccccccc} &&&&a_3 & a_2 & a_1 & a_0 \\ &&&\times&b_3 & b_2 & b_1 & b_0 \\ \hline &&&1&\overline{a_3b_0} & a_2b_0 & a_1b_0 & a_0b_0 \\ &&& \overline{a_3b_1} & a_2b_1 & a_1b_1 & a_0b_1 & \\ &&\overline{a_3b_2} & a_2b_2 & a_1b_2 & a_0b_2 & & \\ 1&a_3b_3 & \overline{a_2b_3} & \overline{a_1b_3} & \overline{a_0b_3} &&& \\ \hline \end{array} }$
となります。