Dadda-Tree-Multiplizierer

(Weitergeleitet von Dadda-Multiplizierer)

Ein Dadda-Tree-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 Multiplizierer 1965 vorstellte.[1]

Funktionsweise

Bearbeiten

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

 .

Hierbei sind   und  ,   die Binärdarstellungen der zwei zu multiplizierenden Zahlen.

Der Dadda-Tree-Multiplizierer geht in drei Schritten vor:

  1. Berechne für jedes Paar   mit   und   das Partialprodukt  .
  2. Addiere die Resultate dieser Berechnung innerhalb der für den Dadda-Tree-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-Tree-Multiplizierers

Bearbeiten

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   mit   stehen.

Dann betrachtet man die Folge  . Das Symbol   steht für die Gauß-Klammer. Man errechnet die Glieder der Folge bis zu dem  , sodass   größer ist als die Anzahl der Elemente in der größten Spalte,   aber noch nicht. Anschließend verwendet man Halb- und Volladdierer, um die Partialprodukte so zu addieren, dass am Ende keine Spalten mehr als   Elemente enthalten. Die Überträge werden jeweils an die Spalte des nächsthöheren   weitergereicht. Für diesen Vorgang verwendet man so wenig 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  , dann für   und so weiter bis einschließlich  .

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

Beispiel 8-Bit

Bearbeiten

Hier sieht man die obige Vorgehensweise für einen 8-Bit-Dadda-Tree-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.

 
4-schichtige Dadda-Reduktion einer 8x8-Teilproduktmatrix unter Verwendung von 7 Halbaddierern (zwei Punkte) und 35 Volladdierern (drei Punkte). Die Punkte in jeder Spalte sind Bits mit gleichem Gewicht. Bits mit geringerem Gewicht sind ganz rechts.

Laufzeit

Bearbeiten

Mit den Rechenregeln für die Abrundungsfunktion und der geometrischen Reihe kann man folgende Abschätzung für   herleiten:

 
 

Sei nun   die Länge der zwei eingegebenen Binärzahlen   und  , und seien  ,   die Partialprodukte. Ordnet man nun alle Partialprodukte in Spalten an, sodass in der k-ten Spalte alle Partialprodukte   mit   stehen, so hat die größte Spalte genau   Einträge.

Zur Erstellung des Dadda-Tree-Multiplizierers wählen wir ja, wie oben beschrieben, das   so, dass

 ,

wobei   nach der Funktionsweise des Algorithmus die Anzahl der Addierer ist, die ein elektronisches Signal vom Eingang zum Ausgang maximal durchlaufen muss. Nimmt man nun die obige Abschätzung für   hinzu, erhält man:

 .

Wenn man nun den Logarithmus auf beide Seiten anwendet, erhält man

 ,

wobei   das Landau-Symbol für die asymptotische obere Schranke darstellt.

Da die Laufzeit eines Addierwerks auch in   liegt, hat der Dadda-Tree-Multiplizierer dieselbe asymptotische Laufzeit wie ein Addierwerk und ist damit schneller als ein vorzeichenloser paralleler Multiplizierer, der eine asymptotische Laufzeit von   aufweist.

Der Dadda-Tree-Multiplizierer ist ferner absolut gesehen schneller als der Wallace-Tree-Multiplizierer, obwohl beide Multiplizierer dieselbe asymptotische Laufzeit von   besitzen.

Einzelnachweise

Bearbeiten
  1. Luigi Dadda: Some schemes for parallel multipliers. In: Alta Frequenza. Vol. 34. Dipartimento di Elettronica Politecnico di Milano, Italy, Mailand 1965, S. 349–365 (englisch, berkeley.edu [PDF; 663 kB]).