ウォレスツリー

8x8部分積行列の4層ウォレス縮約。15個の半加算器（ドット2個）と38個の全加算器（ドット3個）を使用。各列のドットは等しい重みのビットを表す。

ウォレス乗算器は、2つの整数を乗算するデジタル回路である2進乗算器のハードウェア実装です。ウォレス乗算器は、全加算器と半加算器（ウォレスツリーまたはウォレス縮約）を組み合わせて、2つの数が残るまで段階的に部分積を加算します。ウォレス乗算器は各層で可能な限り縮約を行いますが、ダッダ乗算器は縮約を上位層に延期することで、必要なゲート数を最小限に抑えようとします。^{[ 1 ]}

ウォレス乗数は1964年にオーストラリアのコンピュータ科学者クリス・ウォレスによって考案されました。 ^{[ 2 ]}

ウォレスツリーには 3 つのステップがあります。

1. 一方の引数の各ビットをもう一方の引数の各ビットで乗算します。
2. 全加算器と半加算器の層によって部分積の数を 2 に減らします。
3. 電線を2つの数字にグループ化し、従来の加算器で加算します。^{[ 3 ]}

通常の加算器を用いて単純に部分積を加算するのと比較して、ウォレス木の利点は高速性です。ウォレス木には縮約層がありますが、各層には伝播遅延しかありません。単純な部分積の加算には時間がかかります。部分積の作成は で、最終的な加算は なので、全体の乗算は となり、加算とそれほど変わりません。計算量理論の観点から見ると、ウォレス木アルゴリズムは乗算をNC ^{1 の}クラスに分類します。ウォレス木の欠点は、単純な部分積の加算と比較すると、ゲート数が大幅に多いことです。 ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log^{2}n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

これらの計算ではゲート遅延のみが考慮され、非常に大きくなる可能性がある配線遅延は考慮されません。

ウォレス ツリーは、3/2 または 4/2 加算器のツリーで表すこともできます。

ブース符号化と組み合わせられることもある。^{[ 4 ] [ 5 ]}

詳細な説明

ウォレス木は長整数乗算の一種です。最初のステップは、一方の因数の各桁（各ビット）をもう一方の因数の各桁で乗算することです。これらの部分積の重みはそれぞれ、その因数の積に等しくなります。最終的な積は、これらの部分積の重み付き和によって計算されます。

最初のステップは、前述のように、一方の数値の各ビットをもう一方の数値の各ビットで乗算することであり、これは単純なANDゲートで実現され、ビットが生成されます。ビットとビットの部分積は重みを持ちます。${\displaystyle n^{2}}$ ${\displaystyle a_{m}}$ ${\displaystyle b_{n}}$ ${\displaystyle 2^{(m+n)}}$

2 番目のステップでは、結果のビットが 2 つの数値に削減されます。これは次のように実行されます。同じ重みのワイヤが 3 本以上ある場合は、次のレイヤーを追加します。

• 同じ重みを持つ任意の3本のワイヤを全加算器に入力します。結果は、同じ重みの出力ワイヤと、入力ワイヤ3本ごとに重みが増した出力ワイヤになります。
• 同じ重さのワイヤが 2 本残っている場合は、それを半加算器に入力します。
• ワイヤーが 1 本だけ残っている場合は、それを次の層に接続します。

3 番目で最後のステップでは、結果として得られた 2 つの数値が加算器に入力され、最終的な積が得られます。

例

${\displaystyle n=4}$ を掛けて： ${\displaystyle a_{3}a_{2}a_{1}a_{0}}$ ${\displaystyle b_{3}b_{2}b_{1}b_{0}}$

1. まず、すべてのビットをすべてのビットで乗算します。
   • 重量1 –${\displaystyle a_{0}b_{0}}$
   • 重量 2 – 、${\displaystyle a_{0}b_{1}}$ ${\displaystyle a_{1}b_{0}}$
   • 重量 4 – 、、${\displaystyle a_{0}b_{2}}$ ${\displaystyle a_{1}b_{1}}$ ${\displaystyle a_{2}b_{0}}$
   • 重量8 – 、、、${\displaystyle a_{0}b_{3}}$ ${\displaystyle a_{1}b_{2}}$ ${\displaystyle a_{2}b_{1}}$ ${\displaystyle a_{3}b_{0}}$
   • 体重 16 – 、、${\displaystyle a_{1}b_{3}}$ ${\displaystyle a_{2}b_{2}}$ ${\displaystyle a_{3}b_{1}}$
   • 体重 32 – 、${\displaystyle a_{2}b_{3}}$ ${\displaystyle a_{3}b_{2}}$
   • 体重 64 –${\displaystyle a_{3}b_{3}}$
2. 削減層1:
   • 重み1のワイヤーのみを通過させ、出力：重み1のワイヤー1本
   • 重み2の半加算器を追加し、出力：重み2のワイヤ1つ、重み4のワイヤ1つ
   • 重み4の全加算器を追加し、出力: 重み4のワイヤ1つ、重み8のワイヤ1つ
   • 重み8の全加算器を追加し、残りのワイヤを通過させると、出力は重み8のワイヤ2本、重み16のワイヤ1本となる。
   • 重み16の全加算器を追加し、出力: 重み16のワイヤ1本、重み32のワイヤ1本
   • 重み32の半加算器を追加し、出力: 重み32のワイヤ1本、重み64のワイヤ1本
   • ウェイト64ワイヤーのみを通過させると、出力：ウェイト64ワイヤー1本
3. 削減層1の出力の配線:
   • 重量 1 – 1
   • 重量 2 – 1
   • 重量 4 – 2
   • 体重 8 – 3
   • 体重16～2
   • 体重 32 – 2
   • 体重 64 – 2
4. 削減層2:
   • 重み8には全加算器を追加し、重み4、16、32、64には半加算器を追加します。
5. 出力:
   • 重量 1 – 1
   • 重量 2 – 1
   • 重量 4 – 1
   • 体重 8 – 2
   • 体重16～2
   • 体重 32 – 2
   • 体重 64 – 2
   • 体重 128 – 1
6. ワイヤーを整数のペアとそれを加算する加算器にグループ化します。

参照

• ダダの木

参考文献

1. Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). 「DaddaとWallaceの乗算器遅延の比較」 . Luk, Franklin T. (編). Advanced Signal Processing Algorithms, Architectures, and Implementations XIII . Proceedings of the SPIE. Vol. 5205. pp.  552– 560. Bibcode : 2003SPIE.5205..552T . doi : 10.1117/12.507012 . ISSN  0277-786X . S2CID  121437680 .
2. Wallace, Christopher Stewart (1964年2月). 「高速乗算器に関する提案」. IEEE Transactions on Electronic Computers . EC-13 (1): 14– 17. doi : 10.1109/PGEC.1964.263830 . S2CID 34688264 . 
3. Bohsali, Mounir; Doan, Michael (2010). 「Rectangular Styled Wallace Tree Multipliers」(PDF) . 2010年2月15日時点のオリジナル(PDF)からアーカイブ。
4. 「Introduction」 . 8x8 Booth Encoded Wallace-tree multiplier . タフツ大学. 2007年. 2010年6月17日時点のオリジナルよりアーカイブ。
5. Weems Jr., Charles C. (2001) [1995]. 「CmpSci 535 ディスカッション7：数値表現」 . アマースト：マサチューセッツ大学. 2011年2月6日時点のオリジナルよりアーカイブ。

さらに読む

• Savard, John JG (2018) [2006]. 「高度な算術技術」 . quadibloc . 2018年7月3日時点のオリジナルよりアーカイブ。 2018年7月16日閲覧。

外部リンク

• Wallace Tree Multiplier の汎用 VHDL 実装。