booth 乗算器の話

唐突に Booth アルゴリズムを使った乗算器の話を始めます。
冗長表現の4進数を使って、うまいこと乗算しましょうという話です。
まず2進数と4進数の掛け算を比べてみると、
f0054075_23201334.png

こんな感じです。4進数を使うと2進数と比べて、部分積の数が半分で済みます。当たり前ですが…
でもこれだと、部分積を求めるための×3とか計算が大変ですよね。なので、冗長4進表現に書き換えます。ここでは、-2,-1,0,1,2の5個のシンボルを使う表現にします。大事なのは、2倍は1ビットシフトで済むこと、-1倍はひとまずは論理否定をしておいて、後で+1すれは良いってところです。
結果から先に言うとこんな感じです。部分積が1個増えちゃいましたが…
f0054075_23295465.png
ここで使ったルールは、元のシンボルが2,3の場合は上の桁に+1して(+4になる)自身は-2,-1となります。その結果に下の桁からの桁上げを足したら冗長4進表現になった新しいシンボルが出来ます。
表にすると下のようになります。
f0054075_23375274.png
この表を見るとわかるように-3,3がないので、部分積が簡単に求まります。
4進表現の部分積を2進数に書き換えてあげると下のようになります。
f0054075_23580016.png
符号拡張をさぼる手法の話はまた今度。

[PR]
トラックバックURL : http://tom01h.exblog.jp/tb/28143770
トラックバックする(会員専用) [ヘルプ]
※このブログはトラックバック承認制を適用しています。 ブログの持ち主が承認するまでトラックバックは表示されません。
by tom01h | 2017-09-13 23:46 | 論理設計の話 | Trackback | Comments(0)