ダダ乗数

ダッダ乗算器は、 1965年にコンピュータ科学者のルイジ・ダッダによって発明されたハードウェア2進乗算器の設計です。 ^[1]選択された全加算器と半加算器を使用して、2つの数値が残るまで段階的に部分積を加算します（ダッダツリーまたはダッダ削減）。設計はウォレス乗算器に似ていますが、異なる削減ツリーにより、必要なゲート数が削減され（最小のオペランドサイズを除くすべての場合）、わずかに高速化されます（すべてのオペランドサイズの場合）。^[2]

Dadda 乗算器と Wallace 乗算器は、それぞれ長さがとである2つのビット文字列に対して同じ 3 つのステップを実行します。 ${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle \ell_{1}}$${\displaystyle \ell_{2}}$

1. の各ビットをの各ビットで乗算 (論理積) し、結果を重み別に列にグループ化して生成します。${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle \ell_{1}\cdot \ell_{2}}$
2. 各重みが最大 2 ビットになるまで、全加算器と半加算器の段階によって部分積の数を減らします。
3. 最終結果を従来の加算器で加算します。

ウォレス乗算器と同様に、最初のステップの乗算積は、乗算の元のビット値の大きさを反映して異なる重みを持ちます。たとえば、ビットの積の重みは です。 ${\displaystyle a_{n}b_{m}}$${\displaystyle n+m}$

各レイヤーで可能な限り削減する Wallace 乗算器とは異なり、Dadda 乗算器は、使用されるゲートの数と入出力遅延を最小限に抑えようとします。このため、Dadda 乗算器の削減フェーズは低コストですが、最終的な数値が数ビット長くなる可能性があるため、若干大きな加算器が必要になります。

より最適な最終製品を実現するために、削減プロセスの構造は、ウォレス乗数よりもわずかに複雑なルールによって制御されます。

削減の進行は、次のように定義される最大高さのシーケンスによって制御されます。 ${\displaystyle d_{j}}$

${\displaystyle d_{1}=2}$、 そして${\displaystyle d_{j+1}=\operatorname {floor} (1.5d_{j}).}$

次のようなシーケンスが生成されます。

${\displaystyle d_{1}=2,d_{2}=3,d_{3}=4,d_{4}=6,d_{5}=9,d_{6}=13,\ldots }$

の初期値は、 となる最大値として選択されます。ここで、と は、入力の被乗数と乗数のビット数です。2 つのビット長のうち小さい方が、乗算の最初の段階の後の重みの各列の最大の高さになります。削減の各段階で、アルゴリズムの目標は、各列の高さを の値以下になるように削減することです。 ${\displaystyle j}$${\displaystyle d_{j}<\min {(n_{1},n_{2})}}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle j}$${\displaystyle d_{j}}$

からの各ステージでは、次の規則に従って、 重みが最も低い列から始めて各列を削減します。${\displaystyle ,\ldots ,1}$${\displaystyle c_{0}}$

1. 列の縮小が必要ない場合は、列に移動します${\displaystyle \operatorname {height} (c_{i})\leqslant d_{j}}$${\displaystyle c_{i+1}}$
2. 半加算器で上位2つの要素を加算し、結果を列の一番下に置き、繰り上がりを列の一番下に置いて、列に移動する。${\displaystyle \operatorname {height} (c_{i})=d_{j}+1}$${\displaystyle c_{i+1}}$${\displaystyle c_{i+1}}$
3. それ以外の場合は、上位3つの要素を全加算器で加算し、結果を列の一番下に、繰り上がりを列の一番下に配置し、ステップ1から再開します。${\displaystyle c_{i+1}}$${\displaystyle c_{i}}$

隣の画像の例は、ここで説明されている 8 × 8 乗算器の削減を示しています。

初期状態は として選択され、最大値は 8 未満になります。 ${\displaystyle j=4}$${\displaystyle d_{4}=6}$

ステージ、${\displaystyle j=4}$${\displaystyle d_{4}=6}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{5})}$高さはすべて6ビット以下なので変更は行われません
• ${\displaystyle \operatorname {height} (c_{6})=d_{4}+1=7}$なので、半加算器を適用して6ビットに減らし、そのキャリービットを${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{7})=9}$からの桁上げビットを含むので、全加算器と半加算器を適用して6ビットに減らす。${\displaystyle c_{6}}$
• ${\displaystyle \operatorname {height} (c_{8})=9}$からの2つのキャリービットを含むので、再び全加算器と半加算器を適用して6ビットに減らす。${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{9})=8}$2つのキャリービットを含むので、1つの全加算器を適用して6ビットに減らす。${\displaystyle c_{8}}$
• ${\displaystyle \operatorname {height} (c_{10}\cdots c_{14})}$キャリービットを含めて高さが6ビット以下なので、変更は行われません。

ステージ、${\displaystyle j=3}$${\displaystyle d_{3}=4}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{3})}$高さはすべて4ビット以下なので変更は行われません
• ${\displaystyle \operatorname {height} (c_{4})=d_{3}+1=5}$なので、半加算器を適用して4ビットに減らし、そのキャリービットを${\displaystyle c_{5}}$
• ${\displaystyle \operatorname {height} (c_{5})=7}$からのキャリービットを含むので、全加算器と半加算器を適用して4ビットに減らす。${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{6}\cdots c_{10})=8}$前のキャリービットも含め、2つの全加算器を適用して4ビットに減らす。
• ${\displaystyle \operatorname {height} (c_{11})=6}$前のキャリービットも含めると、全加算器を適用して4ビットに減らす。
• ${\displaystyle \operatorname {height} (c_{12}\cdots c_{14})}$キャリービットを含めて高さが4ビット以下なので、変更は行われません。

ステージ、${\displaystyle j=2}$${\displaystyle d_{2}=3}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{2})}$高さはすべて3ビット以下なので変更は行われません
• ${\displaystyle \operatorname {height} (c_{3})=d_{2}+1=4}$半加算器を適用して3ビットに減らし、そのキャリービットを加算します。${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{4}\cdots c_{12})=5}$前のキャリービットも含むので、1つの全加算器を適用して3ビットに減らす
• ${\displaystyle \operatorname {height} (c_{13}\cdots c_{14})}$キャリービットを含めて高さが3ビット以下なので変更はありません。

ステージ、${\displaystyle j=1}$${\displaystyle d_{1}=2}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{1})}$高さはすべて2ビット以下なので変更は行われません
• ${\displaystyle \operatorname {height} (c_{2})=d_{1}+1=3}$なので、半加算器を適用して2ビットに減らし、そのキャリービットを${\displaystyle c_{3}}$
• ${\displaystyle \operatorname {height} (c_{3}\cdots c_{13})=4}$前のキャリービットも含むので、1つの全加算器を適用して2ビットに減らす
• ${\displaystyle \operatorname {height} (c_{14})=2}$からのキャリービットを含むため、変更は行われません。${\displaystyle c_{13}}$

追加

最後のステージの出力には、高さ 2 以下の 15 列が残り、標準加算器に渡すことができます。

• ブースの乗算アルゴリズム
• 融合乗算と加算
• ウォレスツリー
• 複素対数と指数のためのBKM アルゴリズム
• モジュラー乗算のためのコハンスキー乗算

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