Multiplizierer (Digitaltechnik)

2024-11-27T18:53:31Z

2.207.99.208: /* Festkommamultiplizierer */

Ein '''Multiplizierer''' ist in der [[Digitaltechnik]] eine [[elektrische Schaltung]], die aus zwei oder mehr digitalen Zahlen mit der mathematischen Operation der [[Multiplikation]] das [[Produkt (Mathematik)|Produkt]] ermittelt. Der Multiplizierer ist bei [[Hauptprozessor|Prozessoren]] Teil der [[arithmetisch-logische Einheit|arithmetisch-logischen Einheit]] (ALU) und kommt dort als [[Multiply-Accumulate|Multiplikationsakkumulator]] (MAC) vor, kann aber in programmierbaren digitalen Schaltungen wie [[FPGA]]s auch als eine eigenständige Funktionseinheit realisiert werden.

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

== Arten ==
[[Datei:Multiply.png|mini|hochkant=2|Multiplizierer 16x16=32 bit]]

Multiplizierer werden aufgrund der verarbeiteten Zahlenformate unterschieden:
* [[Festkommazahl|Festkomma-Multiplizierer]] multiplizieren Festkommazahlen.
* [[Gleitkommaarithmetik|Gleitkomma-Multiplizierer]] multiplizieren Gleitkommazahlen.
Der Aufwand ist im Wesentlichen durch die Anzahl der zu multiplizierenden Bits (steigt quadratisch) bestimmt. Gleitkomma-Multiplizierer benötigen noch etwas zusätzliche Logik:
* Einen Addierer für die Exponenten, der parallel arbeiten kann
* Ein XOR-Gatter für das Vorzeichen
* Behandlung des Verlusts des MSB (höchste Bit, most significant bit) nach der Multiplikation: Dekrement und Verschiebung.
* Behandlung für NANs und INFs am Eingang bzw. bei Überlauf- und Unterlauf.
Bei Verwendung von parallelen Multiplizieren in modernen CPUs und Grafikkarten liegt der Hauptaufwand (double: ca. 97 Prozent, float: ca. 92 Prozent) im Multipliziernetzwerk.

=== Festkommamultiplizierer ===
[[Datei:4bit multiplizierer.png|mini|hochkant=2|Paralleler Multiplizierer für 4 Bit. 
<math>s_i</math> = Summanden 
<math>c_i</math> = Carry-Output 
<math>m_0</math> = Input Enable <math>b_i</math>]]
Die [[Dualsystem|binäre]] Multiplikation verläuft analog zum 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 [[Kombinatorische Logik|kombinatorischen Logik]] mit folgender Gleichung gebildet:

:<math>P = X \cdot Y + K</math>

Der Vorgang der Multiplikation gestaltet sich dabei nach folgendem 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 [[Volladdierer]]n 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 dem Komma der beiden Eingangsfaktoren. Im obigen Beispiel ist bei beiden Faktoren die Stellenanzahl hinter dem Komma null, wodurch auch im Produkt der Kommapunkt rechts der letzten Stelle zu liegen kommt.

Bei vorzeichenbehafteten Zahlen, welche in digitalen Schaltungen meistens als [[Zweierkomplement]] dargestellt sind, ist eine entsprechende schaltungstechnische Erweiterung des Multiplizierers nötig. Die vorzeichenrichtige Multiplikation von zwei je vierstelligen binären Zahlen gestaltet sich nach folgendem 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. Ein anderes Verfahren ist der serielle Multiplizierer, bei welchem zu Lasten des Durchsatzes mit geringerem Hardwareaufwand pro Takt ein Bit (eine Stelle) des Ergebnisses berechnet wird. Des Weiteren existieren Verfahren, welche 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 [[Dadda-Tree-Multiplizierer]], der [[Wallace-Tree-Multiplizierer]] und der [[Booth-Algorithmus]].

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

:<math>x = s \cdot m \cdot b^e</math>

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.
Die einzelnen Schritte
* Aufspalten der Faktoren in Vorzeichen, Exponenten und Mantissen. Die führende 1 bei normalisierten Mantissen (Exponent > 1) und die führende Null bei denormalisierter Mantisse (Mantisse = 0) sind hinzuzufügen.
Die folgenden Schritte können parallel ausgeführt werden:
* Multiplikation der Mantissen: M = M1 × M2
* Addition der Exponenten: E = E1 + E2 − Bias
* Xor-Verknüpfung der Vorzeichen: S = S1 + S2
Nun folgt:
* Bestimmung des MSBs, die 0 sind. Im Fall von normalisierten Faktoren kann dies 0 oder 1 sein, im Fall von denormalisierten Faktoren sind größerer Zahlen möglich (double bis 106): L
Fallunterscheidung:
* Falls E − L ≤ −24 bzw. −53, ist das Ergebnis Null. Das Vorzeichen bleibt aber erhalten.
* Falls E − L ≤ 0 ist, ist das Ergebnis eine denormalisierte Zahl.
* Falls 0 < E − L < MaxBias ist, ist das Ergebnis eine normalisierte Zahl.
* Falls MaxBias ≤ E − L ist, ist das Ergebnis unendlich.
Zusätzlich existieren bei Gleitkommamultiplizierern noch Steuerlogiken, welche das korrekte [[Vorzeichen (Zahl)|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. Mit zunehmender Anzahl von Logikbauelementen steigt die gesamte Signallaufzeit des Multiplizierers.

== Literatur ==
* {{Literatur
|Autor = Jean-Michel Muller
|Titel = Elementary functions - Algorithms and Implementation
|Verlag = Birkhäuser |Jahr = 2006 |Auflage = 2 | Ort = Lyon |ISBN = 0-8176-4372-9
}}

== Weblinks ==
* {{Webarchiv | url=http://www.andraka.com/multipli.htm | wayback=20141023233409| text=Multiplication in FPGAs }} Schaltungstechnische Varianten, auf Englisch.

[[Kategorie:Digitale Schaltungstechnik]]
[[Kategorie:Computerarithmetik]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Multiplizierer (Digitaltechnik)