ウォレス木

ウォレス木（Wallace tree）は2進数において乗算をする際に乗数の各桁に対応する部分積を作り、それら全ての合計を求めるアルゴリズムである^[1]。

解説

情報工学では、2つの整数を乗算するデジタル回路であるバイナリ乗算器をハードウェアで実装したもの^[2]と説明される。全加算器と半加算器を選択しながら2つの数値が残るまで部分積を段階的に加算するため、通常の加算器で純粋に部分積を加算するのに比べて高速であることが利点である。並列乗算回路ではブースのアルゴリズムを使った場合も含め、 部分積の和をビット毎に求めることになるが、ウォレス木の手法を用いればビット毎に全加算器を用いることなく、いくつかのビットをまとめて全加算器を用いることができる^[3]。

実装

ウォレス木は以下の3つの手順を踏む^[4]。

1. 一方の引数の各ビットに他方の引数の各ビットを乗算する。
2. 全加算器と半加算器を重ねることで部分積の数を2個に減らす。
3. 2つの数字でワイヤーをグループ化し、従来の加算器で加算する。

したがって中間結果の個数が1段でおよそ3分の2に減ることになる^[5]。