html> 第5回

第5回分

ブースのアルゴリズム

ブースのアルゴリズムが並列乗算回路の加算回数の1/2ということは、無駄な演算を省いているものと考えられるが、どこが省かれたのか？ブースのアルゴリズムを用いることで加算回数が減る理由が分からない。

結果としてそうなっている、ということですかね・・・

X = -1・xN-12N-1 + ∑n=0N-2 xn・2n という式は紹介だけで使っていなかったようだが、何か意味はあるのか？

Yと同じように表記できる、という程度の意味です。

ブースのデコーダを用いた回路は実際に使われているのか？もっと効率の良い方法はあるのか？並列乗算回路と比べ、どの程度速いのか？

ほとんどの実用的な乗算器は、ブースのアルゴリズムを使っているようです。 速度は、単純には部分積の段数分だけ速くなりますね。

乗算数Yだけでなく、非乗算数Xも計算回数に影響しないのか？

Xを加工しながら加算していくことで積を求めるわけですから、 Xの値そのものは影響はありません。

ブースのデコーダでのオーバヘッドは演算にどの程度影響を与えるのか？

単純な組み合わせ論理回路ですので、ほとんど無視できるといえるでしょう。

ブースのアルゴリズムのXとYはどうしてあのように表現されるのか？

ブースのアルゴリズムに限った話ではなく、符号を含めた2進数の一般的な表記、ということです。

ブースのアルゴリズムにおいて、Nが奇数のとき、Σ演算は、j=0,1,…,[(N-2)/2](ガウスの記号？)となるのか？

ブースのアルゴリズムのYjはどのようにして求めたのか？

思いつき、でしょうかねえ・・・

ブースのアルゴリズムのアルゴリズムで本当に演算速度が速くなるのか、いまいち理解できない。

部分積の段数が減っている分は、確実に演算速度が速くなります。

その他

資料のワレスツリーはどういうときに使うのか？

ワレスツリーの解説も時間があればお願いします。

次回触れます。

乗算回路は加算回路の組み合わせで実現できないのか？できるとしたら、限界はどこまでか？

ぜひやってみてください。けっこうえらいことになります。

並列乗算回路は何ビット程度までなら遅延が問題にならずに使えるか？

用途次第、ですね。 ただ、部分積の段数は回路規模にもほぼ比例しますので、 回路規模の制限からも、ブースのアルゴリズムは有用といえます。

第5、6階配付資料の図4.5の全加算器と半加算器の差がないのだが。HAの図にCiはいらないのでは？

ご指摘の通りです。

最後の方の説明の数学的だった部分がよく分からなかった。

ブースのアルゴリズムから話が複雑になり、過程が分かりづらかった。

乗算器は計算がめんどくさい。ブースのアルゴリズムの式変形が途中でよく分からなくなった。

まあ乗算器の高速化の理論的裏付け、ということで、 あとで一通り読んで納得していただければ、と思います。

桁数が小さいものしか必要ないため並列乗算回路を使われる、ということはあるのか？

設計の手間しだい、というところでしょうか。

乗算器の設計は電流伝達速度も視野に入れているのか？

電流伝達速度、とは、信号伝搬速度、のことでしょうか。 もしそうであれば、信号伝搬に最も時間のかかる経路（クリティカルパス）が 部分積の加算のところ、といえますので、ブースのアルゴリズムは クリティカルパスを短くする、ということもできます。

X・22jでなぜ2jビット左シフトになるのですか？

シフト演算とは、そういうものですね。

並列乗算回路について、板書と資料の図が異なっていましたが、どちらが正しいのか？

おや、失礼しました。資料の方が正しいです。

感想

乗算器について理解が深まった。

講義資料がすごくありがたかった。

それはよかったです。

ブースのアルゴリズムは、2の補数の性質をうまく利用していると思う。回路の段数は並列乗算器に比べてかなり減りそうだと思う。

ブースのアルゴリズムの式変形が、狐につままれたような気分だった。ブースがどのようにしてこの変形を見つけることができたのか気になった。

回路を小さくするためのブースのアルゴリズムは画期的だと思った。

そうですね、頭の良い方法ですよね。

乗数YをYjに置き換えてXとYjでなんらかの操作を加えることで、Zjの加算を半分にするから高速化される、ということは分かった(ブースのアルゴリズムの結果だけは分かった)。

それだけで十分だと思います。

ブースのプログラムについてもっと詳しく知りたい。

具体的には次回も。

ブースのデコーダの仕組みを考案した人について知ってみたい。

Wikipediaによれば、 ブースさんが考案したもののようですね。

ブースのアルゴリズムのX=…、Y=… が成り立つのは認めることにする、ということだが、やはり少し気になる。

認めることにする、というか、確かにそういう表記で正しいですね、と確認をして 使ったのでした。
戻る