ウォレスツリー

ウォレス乗算器は、2つの整数を乗算するデジタル回路であるバイナリ乗算器のハードウェア実装です。フルアダーとハーフアダー（ウォレスツリーまたはウォレスリダクション）を選択して、2つの数値が残るまで段階的に部分積を加算します。ウォレス乗算器は各層で可能な限り削減しますが、ダッダ乗算器は削減を上位層に延期することで必要なゲート数を最小限に抑えようとします。^[1]

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

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

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

通常の加算器で単純に部分積を加算するのに比べ、ウォレス ツリーの利点は速度が速いことです。ウォレス ツリーには縮約層がありますが、各層には伝播遅延しかありません。単純な部分積の加算には時間がかかります。部分積の作成は で、最終的な加算は なので、全体の乗算は であり、加算よりもそれほど遅くはありません。計算量理論の観点から、ウォレス ツリー アルゴリズムでは乗算はNC ¹クラスに分類されます。ウォレス ツリーの欠点は、単純な部分積の加算と比較すると、ゲート数が非常に多いことです。 ${\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]}

ウォレス ツリーは、長乗算の変形です。最初のステップでは、1 つの因数の各桁 (各ビット) を他の因数の各桁で乗算します。これらの各部分積の重みは、その因数の積に等しくなります。最終的な積は、これらすべての部分積の重み付けされた合計によって計算されます。

最初のステップは、上で述べたように、ある数値の各ビットを他の数値の各ビットで乗算することです。これは単純な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ワイヤーを通過させると、出力：1ウェイト64ワイヤー
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. ワイヤを整数のペアとそれを加算する加算器にグループ化します。

• ダダの木

• Savard, John JG (2018) [2006]. 「Advanced Arithmetic Techniques」. quadibloc . 2018-07-03 にオリジナルからアーカイブ。2018-07-16に取得。

• Wallace Tree Multiplier の汎用 VHDL 実装。