読む編集履歴表示

ウォレス木

ウィキペディアから、無料の百科事典

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2022年10月）

翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。
万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
翻訳後、{{翻訳告知|en|Wallace tree|…}}をノートに追加することもできます。
Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

ウォレス木（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.
↑ “��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日閲覧。