第8回分
プリントの2/2の表でZjの値がすべて0になっていますが，黒板ではZjの値が異なっていました．正しいのは？
あああ、ごめんなさい、板書の方が正しいです。
Webページのほうは、すぐに直しておきます。
ブースのアルゴリズムのX,Yの値の定義がわからない．
最初の-1*XN-1*2N-1がついているのがわからない．
3桁の2進数で最上位を0 ->1に変える理由がわからない
負の数を考慮した書き方(つまり2の補数表現)、になっている、
ということを、3桁の2進数を例にして考えてみたところ、
たしかに、あの式になっている、ということが確認できた、
ということです。
いまいちど確認をしておいてください。
Yjの求め方がわからない
Yj = y2j + y2j-1 - 2y2j+1
という定義に従って、j=0, 1, ...と変えていってみて
もう一度やってみてくださいな。
並列乗算器の回路規模がBC cell * N2となるのは部分積の数だけBC cellが必要ということですか？
そういうことです。
ブースのアルゴリズムでYjがなぜ簡単に求められるのですか？
Yjを、定義どおりに「加算と2倍と減算」で求めなくても、
Yjに出てくるy2j, y2j-1, y2j+1の
値の組み合わせは8通りしかありませんから、
値の組み合わせの対応(真理値表)として書けるので、
単なる組み合わせ論理回路として作ることができる、という意味です。
(詳細は次回)
最初のポイントの所で8通りとは何ですか？
ブースのアルゴリズムのYjところですかね。
上記のとおりです。
計算が3倍速くなることの根拠は？理論的なものか，実験的なものか？
2倍、ですかね。
部分積を加算する回数、つまり演算時間を大きく決める要素が、
並列乗算器(N)→ブースのアルゴリズムを使った乗算器((N-2)/2)ですから、
約半分ですむ、ということです。
乗算器の高速化は段数を減らせばよいのは分かるが，なぜブースのアルゴリズムが効果的なのですか？
上記のとおりです。
これは実際にブースのアルゴリズムを使って乗算回路を
作ってみると、よくわかるかと思いますので、詳しくは次回に・・・
ブースのアルゴリズムで符号ビットを用いないことのデメリットはないのですか？
符号なし2進数でもブースのアルゴリズムは使えませんか？
いや、符号ビットを使わないと、ブースのアルゴリズムが
使えないはず・・・です。
(最後のj=(N-2)/2のときのyN-1の取り扱いが・・・)
ブースのアルゴリズムでXもYと同様に変換するのですか？
Yj=y2j + y2j-1 -2y2j+1がどのように考えられたのか分からないです．
なぜ奇数と偶数で場合分けするのですか？
ブースのアルゴリズムはどのようにあみだされたのでしょうか？
まあ、これはブースさんが頭がよかった(またはそのとき神が降りていた)、
としか言いようがありませんね。
Yj=y2j + y2j-1 -2y2j+1で出てくる+は論理和ですか，それとも算術和ですか？
もちろん算術和です。
Zi= 0 or X2i or -X・22i or X・22i+1 or -X・22i+1で，何故 X -> X・22i，X-> X・22i+1, X->-Xの組み合わせになるのか？
例えば
-X・22iは、
X→-Xの後に、その結果にX→X・22iとすれば
求められますよね。
なので、この3通りを組み合わせればOK、ということです。
Yjにするメリットが良く分からない．
それはブースのアルゴリズムを使って乗算回路をつくったときに
わかりますので、次回にくわしく・・・
最初の2進数の乗算で (例)N=3の時の乗算で，なぜX0〜X3,Y0〜Y3の4桁の乗算になるのですか？
あ、ごめんなさい、N=4 (Nは桁数なので、4桁)、でした。
以前インターネットで「現在はマシンパワーで強引に計算している」と書いてあったが，ブースのアルゴリズムは実際に使われているのですか？
プリント裏に書いてある並列乗算器のYiとXiの入力の時BCではなくてAND回路のみだったりしますか？
Xi・Yi + 0 + 0、ですから、たしかにANDゲートだけですね。
ただしそれでもBCを使って並べた方が、規則的な構造なので
集積回路、としては設計がしやすくなる、というメリットがあります。
教科書にALUは演算結果が正か負かの判定処理が出来ると書いてありますが，どのようにするのでしょうか？
あ、それは講義では触れていませんでしたね。
2の補数表現での2進数では、最上位ビット(MSB)が0のときは正の数、
1のときは負の数ですから、それをみれば、正か負がわかる、ということです。
乗算器のみで独立してつくられるのか？
乗算は結構よく使われるし、かつ加算の繰り返しで行うと
演算時間が長くなりがちなので、
あまり大規模な回路を集積回路に載せることができなかったころは
ともかく、最近は、乗算器を独立で載せているものも多いようです。
BCセルのBCとは何の略ですか？
実はよく知りません。なんの略なんでしょうね・・・
ブースのアルゴリズムでは回路面積も半分程度と考えてよいか？
実際には、Zjを求める部分(ブースデコーダ)が必要ですので、
単純に半分にはなりませんが、半分「近く」はなりますね。
詳しくは次回、全体をつくってみたときに・・・
ブースのアルゴリズムで、Nが奇数の場合は(N-2)/2が分数になりませんか？
Nが偶数のときだけを考えることにしましょう。
実際、Nが奇数の回路(加算器も乗算器もALUも)は
あまり見たことがありません。
ビット数が2のベキ乗ではないから、でしょうね。
ブースのアルゴリズムで、(N-2)/2が「Nの半分くらい」とは？
Nの半分はN/2ですが、例えばN=16ならば、(N-2)/2=7ですから、
まあだいたい半分ぐらいかな、と。
目安です。
ブースのアルゴリズムで、j=0, 1, ...と増やしていくと、該当するyjが1つずつ重なっているのはなぜ？
結果として、そのように重なっていて、Yjを求めると、
ΣYj・22jが、Yと同じになる、ということですね。
ブースのアルゴリズムについて，もう少し詳細なプリントが欲しいです．
ううむ。あれより詳しくまとめることはできないかも・・・
次の講義でもプリントを使うなら結果まで載せておいて欲しかった．
すいません、中途半端でした。
今回の授業は難しかった．
最初に予告しておいたとおりです。
次回も気合を入れていきましょう。
プリントが分かりやすかった．
どうもありがとうございます。
ブースのアルゴリズムでもまだ遅いように思った．
ぜひ、もっと効率のいい乗算器の構成を研究してみてください。
(いまでも研究している人はいます)
回路を工夫する方法は"なぜ思いつくのだろう"と思うものばかりで結構とまどいます．
演算量が半分になるのは凄いと思った．
ブースの考え方は凄いと思った．
思いついたときに、神が降りていたとしか思えませんよねえ・・・
戻る