ウォレス木とは？わかりやすく解説

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

解説

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

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

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

^ “コンピュータアーキテクチャの話(81) Wallace Tree”. TECH+（テックプラス） (2007年6月7日). 2022年10月11日閲覧。
^ Townsend, Whitney J.; Swartzlander, Earl E., Jr.; Abraham, Jacob A. (2003-12-01). A comparison of Dadda and Wallace multiplier delays. 5205. pp. 552–560. doi:10.1117/12.507012.
^ “[http://ifdl.jp/akita/class_old/old/05/lsi/10.html ��10��]”. ifdl.jp. 2022年10月11日閲覧。
^ “Wayback Machine”. web.archive.org (2010年2月15日). 2022年10月11日閲覧。
^ “https://www.ritsumei.ac.jp/ocw/se/2006-55170/lecture_doc/2006-55170-07.pdf”. 立命館大学理工学部電子情報デザイン学科. 2022年10月12日閲覧。