第6回分

シフト演算においてANDやORはどれくらい削ることができますか?

シフト演算は実際どのようにするのか。また、動作はそれほど重くないのか。

シフト演算は、隣のビットから配線をつないでくるだけ、ですから シフト演算自体は、回路は必要ありません。 ただし、シフトするか否かを選択する必要がある場合は、 セレクタ回路が必要になりますね。

Zの計算で、2ビットずつ左にずらすのかよくわからなかった。なぜ正しい値になるのか?1ビットずつならわかる気がするが、なぜ2ビットずつ?

それがブースのアルゴリズムのポイント、です。 式を丹念に追ってみてください。

X・Yj=-1・ANj+ΣANj・2^i+Cjで、Cjの意味がわかりませんでした。

とりあえずつけておき、ふだんはCj=0としておくのですが、 符号を反転させるために2の補数をとるとき、「ビット反転+1」の +1、のところに使います。

X・Yj=-Xのとき、Aij=/xi、Cj=1とありましたが、予めxiの各ビットに何が入っているかによってAijの値はxi、/xiのどちらも取り得るのではないでしょうか。

いえ、2の補数をとる過程で、Xの各ビットの値xiを反転、つまり 0を1に、1を0に入れ替えますから、Aij=/xi、になります。

なぜ/ANjの値が負の符号ビットになっているのでしょうか。計算の仕方がわかりません。

最上位ビットは符号を表すのでした。 (前回のブースのアルゴリズムに入る前の準備のところの話)

ブースのアルゴリズムを使った乗算器は演算速度が速くなるが、いくつもデコーダがあり、配線も複雑で理解しにくくて規模が大きくなるような気がする。実際に使われているのか?

足し算の段数を変えての高速化は、特別なことのように感じましたが、実際はよく用いられているのですか?

図が複雑なのですが、半分にできるとはいえ、また時間がかかるのではないですか?

デコーダを使う分の回路・配線の複雑化よりも、 部分積の段数を半分にできることによる回路規模削減と速度向上のメリットは かなり大きいため、実用的な乗算回路ではよく使われているようです。

ブースのアルゴリズムを使った回路はFAだけ使った回路と比べてどのくらい速くなるんですか?

Webの講義資料(第6回)には、他文献からの例を載せてありますので、 参考にしてください。

ブースのアルゴリズムを使った乗算器よりもっと速くなる乗算器はあるのか?

ブースのアルゴリズムは、部分積の段数を減らすための方法です。 そのほかに、部分積の加算自体を高速化するワレスの木や、 さらには加算器自体の高速化など、いろいろな方法を独立に併用できそうです。

ブースのアルゴリズムにデメリットはありますか?

とっつきにくいこと、ぐらいでしょうか。

段数を減らすワレスの木はよく用いられるのですか?

実用的な乗算器では、比較的よく使われているようです。

段数がN/2になるかが、いまいち理解できなかった。

ぜひ式を丹念に追ってみてください。

今まで、いろいろな加算器・乗算器を見てきて、どれが高速でよいなどと学んできたが、回路にした場合の消費電力の面でみると、良し悪しはまた違ってくるのか。

そうですね、消費電力という観点は、いろいろな要因が関係するので 一般論で論じることは非常に難しいのですが、いろいろ変わってくると思います。 例えば回路規模が大きくても動作速度が遅ければ消費電力は少ないですし、 同じ動作速度ならば回路規模が小さいほど消費電力が小さいわけですが、 回路の動作速度や、回路の構成要素の動作(値が変化する)の確率は、 設計した回路に対して個別に検証するしかなさそうです。

4進数表現には4つ以上のシンボルが必要ですが、ブールのアルゴリズムは負の数に着目することにより、うまくそのシンボルを全て2のべきにしていると思います。ガウス整数などの整数に比べてさらに単数の多い環を使って、効率化をはかる方法はありますか?

なかなか面白い観点ですね。 ブースのアルゴリズムも、実は講義で紹介したのは「2次のブースのアルゴリズム」 と呼ばれるもので、もっと次数の高いブースのアルゴリズムもありますので、 それに関連がありそうです。

教室がかなり寒かったのですが、温度調節を授業中にお願いしてもよいですか?

さすがにそこまで調節できないので、講義中に、皆さんでお願いします。
戻る