読者です 読者をやめる 読者になる 読者になる

kivantium活動日記

プログラムを使っていろいろやります

乗算器 その3

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

昨日はWallaceツリーを用いた乗算器の構成を紹介しました。
昨日までの方法ではbit数と同じ数の部分積の和を取る必要がありましたが、今日は部分積を減らすことで高速化を目指す方法を紹介します。

Radix-4 Booth Encoding

Radix-4 Booth Encodingでは筆算で下に来る方の数を3bitずつ見て部分積を構成します。

片方の数を3bitからなるブロックに分解し

ブロック N倍
000 +0
001 +1
010 +1
011 +2
100 -2
101 -1
110 -1
111 -0

というテーブルに従って部分積を作って足し合わせると通常の方法のおよそ半分の部分積を足すだけで積が求まるという方法です。

実例を見た方が分かりやすいので、4bit符号付き整数での(-7)x6を計算してみます。

符号ありの場合はまず、筆算で下に来る方に対して右に0を付け足します。
011001100
これを右から順に2bitずつずらしながら3bitのブロックを作ります。
01100では順に100, 011となります。
これらは`-2`, `+2`に相当するので筆算は

1001
0110
---------
00001110
110010
---------
11010110

ここで各部分積は符号拡張(最上位の符号bitを必要なbit数だけ増やす)を行っています。

これは (-7)\times6 = 7\times ((+2)\times 2^2+(-2)\times 2^0)に相当する計算を行っていることになります。

逆に6x(-7)はブロックは010 (+1), 100 (-2)なので

0110
1001
-----
00000110
110100
--------
11010110

となって同じ結果を得ます。

この方法は
乗算器 その1の2つめで紹介した繰り返し乗算を行うときに特に効果を発揮します。

片方の数を3bitずつエンコードし、マルチプレクサに入れた0倍, 1倍, 2倍の数字からどれを加減算器に入れるかを選びます。
正なら加算、負なら減算するようにすればBooth Encodingによる遅延はほとんど起こりません(MUXが3入力になった分と減算器のNOTくらい)。
足した結果を格納するシフトレジスタは算術シフト(シフトして出来る空きには最上位のbitを入れる。こうすると符号が保たれる)をするようにします。
このような回路にすることで通常の繰り返し加算による掛け算を行った時の半分の回数の足し算で積を求めることができます。

符号付きの場合を説明してきましたが、符号なしの場合は最上位bitに0を追加してn+1bitの符号付き整数とみれば同じことができるはずですが、特にそう解説している文は見当たらなかったので不明です。

Booth EncodingとWallaceツリーを組み合わせることもできますが、デコード回路や2の補数を作る回路のせいで効果的ではないと言われています。