Multiplizierer (Digitaltechnik)

Ein Multiplizierer ist in der Digitaltechnik eine elektrische Schaltung, welche aus zwei oder mehr digitalen Zahlen mit der mathematischen Operation der Multiplikation das Produkt ermittelt. Der Multiplizierer ist bei Prozessoren Teil der arithmetisch-logische Einheit (ALU) und kommt dort als Multiplikationsakkumulator (MAC) vor, kann aber in programmierbaren digitalen Schaltungen wie FPGAs auch als eine eigenständige Funktionseinheit realisiert werden.

Neben der Addition, welche in digitalen Schaltungen mit geringerem schaltungstechnischen Aufwand in Form von Addierwerken realisiert ist, ist eine schnelle, hardwarebasierende Multiplikation insbesondere im Bereich der digitalen Signalverarbeitung wesentlich. Anwendungsgebiete des Multiplizierers liegen daher bei der Signalverarbeitung wie der Bildverarbeitung oder im Bereich digitaler Filter. Er findet aber auch Anwendung in der digitalen Regelungstechnik. Einer der ersten Einsatzbereiche waren digitale Signalprozessoren (DSP).

Arten

Multiplizierer werden aufgrund der unterschiedlichen Zahlenformate, welche sie verarbeiten können, unterschieden. Die auf Festkommaarithmetik basierenden Multiplizierer zeichnen sich durch geringeren Schaltungsaufwand aus, sind aber nicht so flexibel wie die aufwändigeren, auf Gleitkommaarithmetik basierenden Multipliziererschaltungen.

Festkommamultiplizierer

Paralleler Multiplizierer für 4 Bit.

Die binäre Multiplikation verläuft analog wie im dezimalen System, und kann in digitalen Schaltungen als eine Abfolge von Additionen und Schieboperationen realisiert werden. In nebenstehender Schaltung ist ein vorzeichenloser, paralleler Multiplizierer (MAC) für zwei, je vier Bit breite Zahlen X und Y und dem Summanden K mit Volladdierern dargestellt. Die acht Ausgabebits P werden in der kombinatorischen Logik mit folgender Gleichung gebildet:

$P = X \cdot Y + K$

Der Vorgang der Multiplikation gestaltet sich dabei nach folgenden Schema, die vier Eingangsbits K sind der Einfachheit wegen auf 0 gesetzt:

      1011   (X, entspricht dezimal der Zahl 11)
    · 1110   (Y, entspricht dezimal der Zahl 14)
    ======
 +    0000   (1011 · 0)
 +   1011    (1011 · 1, um eine Stelle nach links verschoben)
 +  1011     (1011 · 1, um zwei Stellen nach links verschoben)
 + 1011      (1011 · 1, um drei Stellen nach links verschoben)
 =========
  10011010   (P, entspricht dezimal 154)

Dieser einfache Multiplizierer lässt sich aus einzelnen Volladdierern, und die Schiebeoperation durch direkte Verschaltung, realisieren. Die binären Stellen des Produktes P sind gleich der Summe der Stellen der beiden Faktoren X und Y. Ein in der Position fixer Kommapunkt wird generell nicht schaltungstechnisch abgebildet, sondern die Position des Kommapunktes im Produkt ergibt sich aus der Summe der Stellen nach den Komma der beiden Eingangsfaktoren. In obigen Beispiel ist bei beiden Faktoren die Stellenanzahl hinter dem Komma null, wodurch auch im Produkt der Kommapunkt rechts der letzten Stelle zum liegen kommt.

Bei vorzeichenbehafteten Zahlen, welche in digitalen Schaltungen meisten als Zweierkomplement dargestellt sind, ist eine entsprechende schaltungstechnische Erweiterung des Multiplizierers nötig. Die vorzeichenrichtige Multiplikation von zwei, je vier stelligen, binären Zahlen gestaltet sich nach folgenden Schema, wobei zu beachten ist, dass die letzte Zeile aufgrund des negativen Faktors subtrahiert werden muss:

       1001   (entspricht dezimal der Zahl -7)
     · 1101   (entspricht dezimal der Zahl -3)
     ======
 + 11111001   (1001 · 1, mit Vorzeichenerweiterung)
 + 0000000    (1001 · 0, um eine Stelle nach links verschoben und mit Vorzeichenerweiterung)
 + 111001     (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 - 11001      (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 ==========
   00010101   (entspricht dezimal +21)

Schaltungstechnisch kann die Subtraktion in der letzten Zeile durch erweiterte Volladdierer realisiert werden, welche neben der Addition auch die Subtraktion beherrschen.

Der Parallelmultiplizierer, bei dem die Rechengeschwindigkeit nur von der maximalen Gatterlaufzeit abhängt, ist allerdings für größere Bitbreiten aufwendig zu realisieren. Andere Verfahren sind der serielle Multiplizierer, bei welchen zu Lasten des Durchsatzes mit geringeren Hardwareaufwand pro Takt ein Bit (eine Stelle) des Ergebnisses berechnet wird. Des Weiteren existieren Verfahren welchen auf Tabellen mit bereits vorab berechneten Werten (engl. Look-Up-Tables) basieren. Es existieren auch effiziente Algorithmen mit denen sich schnelle Multiplizierer mit moderatem schaltungstechnischen Aufwand realisieren lassen. Beispiele hierfür sind der Wallace-Tree-Multiplizierer oder der Booth-Algorithmus.

Gleitkommamultiplizierer

Eine beliebige Gleitkommazahl x wird aus dem Vorzeichenbit s (±1), der Mantisse m und einem Exponenten e, mit einer willkürlich gewählten und fixen Basis b, gebildet:

$x = s \cdot m \cdot b^e$

Bei der in der Computertechnik üblichen Norm IEEE 754 zur Darstellung von Gleitkommazahlen wird mit einer Basis b = 2 und je nach benötigter Auflösung verschieden breiten Mantissen und Exponenten gearbeitet.

Die Multiplikation zweier Gleitkommazahlen lässt sich immer auf eine Multiplikation der beiden Mantissen und eine Addition der beiden Exponenten mit Festkommaarithmetik zurückführen. Die Addition und Multiplikation kann aus Geschwindigkeitsgründen parallel mit getrennten Schaltungsteilen erfolgen. Um bei Über- bzw. Unterläufen des Festkommamultiplizierers korrekte Ergebnisse zu erhalten, ist am Ausgang eine weitere Logik vorhanden, welche durch zusätzliche Addition von ±1 im Exponenten und Verschiebung um ± eine Stelle der Mantisse ein korrektes Ergebnis gewährleistet. Zusätzlich existieren bei Gleitkommamultiplizieren noch Steuerlogiken welche das korrekte Vorzeichen des Ergebnisses bilden und bestimmte Sonderfälle des IEEE-754-Gleitkommaformates, wie „Keine Zahl“ (NaN, engl. für Not-A-Number), behandeln.

Hardwarerealisierung und zeitliches Verhalten

Alle Logikbauelemente besitzen eine Signallaufzeit. Mit zunehmender Bitbreite des Multiplizierers nimmt die Anzahl der Logikbauelemente, die parallel und / oder in Reihe geschaltet sind, zu. Idealerweise wird der komplette Rechenschritt innerhalb eines einzelnen Systemtakts ausgeführt. Mit zunehmender Anzahl von Logikbauelementen steigt die gesamte Signallaufzeit des Multiplizierers. Sie darf jedoch die Länge eines Taktzyklus nicht übersteigen.

Dieses Problem kann man auf zwei unterschiedliche Arten lösen. Im ersten Fall verlängert man den Systemtakt (= Reduzierung der Taktfrequenz). Genau das ist aber nicht erwünscht, denn ein Rechner mit einer größeren Bitbreite wird dadurch zwangsweise langsamer.

Im zweiten Fall kompensiert man die verlängerte Signallaufzeit durch Verteilen des Rechenvorgangs auf beispielsweise zwei Systemtakte. Dazu muss man Hardwareschaltung in zwei Einzelschaltungen aufteilen. Im ersten Systemtakt wird der erste Teil des Rechenvorgangs ausgeführt und die Ergebnisse werden in einem Zwischenspeicher (z. B. Register, Flip-Flop) abgespeichert. Im zweiten Systemtakt werden dann die zwischengespeicherten Werte auf den zweiten Schaltungsteil gegeben, der die Weiterverarbeitung der Zwischenergebnisse zum Gesamtergebnis vornimmt. Bei dieser Lösung kann ein nachfolgender Multiplikationsvorgang bereits wieder im ersten Teil der Schaltung bearbeitet werden, während der gerade laufende Rechenvorgang im zweiten Teil der Schaltung abgeschlossen wird. Eine Aufteilung der Multiplikation auf mehr als zwei Takte ist auch möglich. Diese Technik nennt man pipelining.

Literatur

• Jean-Michel Muller: Elementary functions - Algorithms and Implementation. 2 Auflage. Birkhäuser, Lyon 2006, ISBN 0-8176-4372-9.

Weblinks

• Multiplication in FPGAs Schaltungstechnische Varianten, in englisch.