Fandom

[ENCYCLOPÆDIA]

Dadda-Multiplizierer

5.395Seiten in
diesem Wiki
Seite hinzufügen
Diskussion0 Teilen

Ein Dadda-Multiplizierer ist ein Multiplizierer, der sich durch eine vergleichsweise geringe Laufzeit und eine geringe Anzahl von logischen Gattern auszeichnet. Er ist nach seinem Erfinder Luigi Dadda benannt, welcher diesen Algorithmus 1965 vorstellte.[1]

Laufzeit

Der Dadda-Multiplizierer hat eine Laufzeit in \mathcal{O}(\log n) und ist damit asymptotisch gleich schnell wie der Wallace-Tree-Multiplizierer und schneller als ein vorzeichenloser paralleler Multiplizierer, der eine asymptotische Laufzeit von \mathcal{O}(\log^2 n) aufweist. [2] Ferner ist der Dadda-Multiplizierer etwas schneller als der Wallace-Tree-Multiplizierer und kommt mit weniger logischen Gattern aus.

Funktionsweise

Ein n-Bit Dadda-Multiplizierer basiert wie der Wallace-Tree-Multiplizierer auf der Formel

\left(\sum_{k=0}^n a_k 2^k\right) \cdot \left(\sum_{k=0}^n b_k 2^k\right) = \sum_{k=0}^n \sum_{i+j=k} a_i b_j 2^k.

Hierbei sind \sum_{k=0}^n a_k 2^k und \sum_{k=0}^n b_k 2^k, a_k, b_k \in \{0, 1\} die Binärdarstellungen der zwei zu multiplizierenden Zahlen.

Der Dadda-Multiplizierer geht in drei Schritten vor:

  1. Berechne für jedes Paar (i, j) mit 1 \le i \le n und  1 \le j \le n das Partialprodukt a_i \cdot b_j \cdot 2^{i+j}.
  2. Addiere die Resultate dieser Berechnung innerhalb der für den Dadda-Multiplizierer spezifischen Baumstruktur stufenweise mithilfe von Voll- und Halbaddierern, bis nur noch zwei Zahlen übrig sind, die addiert werden müssen.
  3. Addiere diese beiden Zahlen mit einem normalen Addierwerk.

Baumstruktur des Dadda-Multiplizierers

In Schritt 2 der obigen Schritte werden die Partialprodukte in einer Baumstruktur addiert.

Dabei werden zunächst die Partialprodukte in Spalten angeordnet, sodass in einer Spalte jeweils alle Partialprodukte a_i \cdot b_j mit i+j=k stehen.

Dann betrachtet man die Folge d_1 = 2, d_{j+1} = \left\lfloor \frac{3 \cdot d_j}{2} \right\rfloor. Das Symbol \left\lfloor \cdot \right\rfloor steht für die Gauß-Klammer. Man errechnet die Glieder der Folge bis zu dem j, sodass d_{j+1} größer ist als die Anzahl der Elemente in der größten Spalte, d_j aber noch nicht. Anschließend verwendet man Halb- und Volladdierer, um die Partialprodukte so zu addieren, dass am Ende keine Spalten mehr als d_j Elemente enthalten. Die Überträge werden jeweils an die Spalte des nächsthöheren k weitergereicht. Für diesen Vorgang verwendet man sowenig Voll- und Halbaddierer wie möglich. Kann man sich, um die Spalte hinreichend zu verkleinern, zwischen Voll- und Halbaddierer entscheiden, wählt man den Halbaddierer, da dieser ein kleineres Bauteil ist. Anschließend wiederholt man den Vorgang für j-1, dann für j-2 und so weiter bis einschließlich j=1.

Wenn man den Vorgang für j=1 vollendet hat, enthalten alle Spalten nur noch 2 Elemente. Daher kann man die beiden verbleibenden Zeilen durch ein Addierwerk addieren.

Beispiel 8-Bit

Hier sieht man die obige Vorgehensweise für einen 8-Bit-Dadda-Multiplizierer. Die Punkte stehen dabei für die Partialprodukte bzw. für die Ausgänge der vormalig verwendeten Voll- und Halbaddierer, welche durch die dünnen Linien gekennzeichnet sind.

Quelle

Einzelnachweise

Referenzfehler: Das in <references> definierte <ref>-Tag hat das Gruppenattribut „“, das nicht im vorausgehenden Text vorkommt.

Störung durch Adblocker erkannt!


Wikia ist eine gebührenfreie Seite, die sich durch Werbung finanziert. Benutzer, die Adblocker einsetzen, haben eine modifizierte Ansicht der Seite.

Wikia ist nicht verfügbar, wenn du weitere Modifikationen in dem Adblocker-Programm gemacht hast. Wenn du sie entfernst, dann wird die Seite ohne Probleme geladen.

Auch bei Fandom

Zufälliges Wiki