カテゴリ:論理設計の話( 3 )

Boothで求めた部分積を足しこむ際に符号拡張をばぼる話です。
ここにあげた例ではデータ長が短すぎて有難さがわからないのですが、符号拡張をさぼる手法があります。名前は知りません。
まずは、今までの例ではありがたみどころか説明さえできないので、前回の符号あり乗算の例を無駄に符号拡張します。
赤字が符号拡張です。実際の乗算器では、もっとたくさん符号拡張が必要になります。
f0054075_15224965.png
これをさぼるには…
最下位の部分積とそれ以外ではルールが違うのですが、Sを部分積の符号とすると
最下位は "~S,S,S" を上位ビットに拡張
それ以外は "1,~S" を上位ビットに拡張
上の例だと
f0054075_15233438.png
では、最下位の部分積とそれ以外の部分積の場合で、本来の符号拡張との差を見てみます。
f0054075_15244723.png
ここで、n-1個目の部分積までの差分の総和が{1,1,…,1,0,0}と仮定したときの n個目の部分積までの差分の総和を求めてみます。
部分積は 2bit ずれるのに注意です。
f0054075_15253740.png
n個目の部分積までの差分の総和も{1,1,…,1,0,0}になり、最下位も同様なので、帰納法で証明されたことに… なるんだよね?
つまり、桁あふれ分だけに差が出てくるので、まぁ良いかってことです。
Verilog にするとあまり差が出ないのですが、Github を更新しました。

[PR]
by tom01h | 2017-09-18 18:20 | 論理設計の話 | Trackback | Comments(0)

符号付き乗算器の話

前回は符号なしの話でしたが、Boothの良いところは、そのままで符号付きの乗算ができるところです。
たぶん、2,3を-2,-1にするのが、4の補数(?で良いの?)と相性が良いのかな?
まずは、入力の2進数を4進数と、冗長表現に変換するところまで。符号付きと符号なしだとこんな感じ。4の補数の4進数は3で符号拡張するので良いんだよね?
f0054075_10151286.png
このBoothを使って乗算します。Boothと2進が混ざってカオスですが…
f0054075_13233924.png
つまり、符号拡張さえちゃんとやれば、Boothの乗算は符号について難しい事を考えずに済みます。
これまでの話を Verilog で記述しました。Verilatorで検証することを前提に、テストベンチはC++で記述しています。32bitの符号あり、符号なしの乗算に対応しています。テストベンチは符号ありにしか対応していませんが…
Verilatorが使える環境前提ですが、
mul/ の下で make を実行すると sim/Vmul_0 が出来ます。
sim/Vmul_0 を引数なしで実行すると、ランダムで生成した入力を使った乗算を 1000 回実行します。
好きな回数で実行する場合は、引数を1個与えます。
好きな値をかけるには、引数を2個与えます。
引数は10進数ですが、結果の表示は16進数なので、バグの再現実行が面倒くさいです。
今度こそ符号拡張をさぼる手法の話をしたいと思います。

[PR]
by tom01h | 2017-09-16 22:06 | 論理設計の話 | Trackback | Comments(0)

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]
by tom01h | 2017-09-13 23:46 | 論理設計の話 | Trackback | Comments(0)