計算機算術
高速な乗算器で使われるウォレスツリーの特徴として正しいものはどれか。
- A桁上げ保存加算器の木で部分積を並列に減らし、段数は対数程度
- B部分積を1つずつ順番に足していくので、回路は最も小さいが遅い
- C掛け算の結果を表から引くだけなので、加算器をまったく使わない
答えと解説を見る
正解：A. 桁上げ保存加算器の木で部分積を並列に減らし、段数は対数程度
nビットの掛け算ではn個の部分積ができます。ウォレスツリーは、桁上げ保存加算器で3つを2つにまとめる処理を各段で並列に行い、部分積の数をおよそ3分の2ずつ減らしていきます。そのため、2つになるまでの段数はビット数の対数に比例する程度で済み、順番に足す方式より大幅に速くなります。最後に残った2つの数を高速な加算器で足して完成です。順番に足すのは小さいが遅い配列型の方式で、表を引く方式は大きなビット数では使えません。
- A. 正しい。部分積を並列に減らし、段数は対数程度で済みます。
- B. 順番に足すのは、小さいが遅い別の方式です。
- C. 表を引く方式は大きなビット数では現実的でありません。