4. Halb- und Volladdierer
Nun ist also klar, wie ein Computer sich eine "0" oder eine "1" merkt. Aber ein Computer, der nur speichert, ist wie ein Notizblock, der nie benutzt wird. Damit aus einem digitalen Gedächtnis ein echtes Rechenwerk (ALU – Arithmetic Logic Unit) wird, wird die Fähigkeit benötigt logische Zustände mathematisch zu verknüpfen.
Die Addition stellt dabei die elementarste Operation innerhalb eines Prozessors dar. Während Flipflops Zustände über die Zeit stabil halten, müssen Addierschaltungen Eingangssignale in Echtzeit kombinieren. Dabei ist insbesondere die Behandlung des Übertrags (Carry) eine zentrale Herausforderung.
Im Binärsystem werden Zahlen ausschließlich mit den Ziffern 0 und 1 dargestellt.
Bei der Addition einstelliger Binärzahlen gelten einfache Regeln, die sich aus den möglichen Kombinationen der beiden Ziffern ergeben.
Das Ergebnis 10 zeigt eine Besonderheit des Binärsystems:
Die Summe besteht aus zwei Stellen. Die rechte Stelle gibt die Summe an, die linke Stelle den Übertrag in die nächste höhere Stelle.
Bei der Addition zweier Binärziffern entstehen somit zwei Ausgaben: die Summe (S) und der Übertrag (Ü). Weitere Informationen zum Rechnen im Binärsystem sind hier zu finden.
Diese Beobachtung führt direkt zur Frage, wie eine solche Addition technisch mit logischen Schaltungen umgesetzt werden kann.
4.1 Halbaddierer
Eine Schaltung, die genau diese Aufgabe übernimmt – also zwei Binäreingänge addiert und dabei Summe und Übertrag erzeugt –, wird als Halbaddierer bezeichnet.
Betrachtet man die vier Grundregeln erneut, lassen sich diese direkt mit logischen Gattern beschreiben:
Die Summe (S) ist immer dann 1, wenn entweder A oder B eine 1 ist, aber nicht beide gleichzeitig. Dies entspricht exakt der Logik eines XOR-Gatters (Exklusiv-Oder).
Der Übertrag ist nur dann 1, wenn sowohl A als auch B eine 1 sind. Dies entspricht exakt der Logik eines AND-Gatters (Und).
Damit ist die theoretische Basis für den Halbaddierer gelegt: Er ist die physische Umsetzung dieser beiden Gatter, um die einstellige Addition zu automatisieren.
Schaltung:
Ein Halbaddierer (HA) ist eine kombinatorische Schaltung, die zwei einstellige Binärzahlen addiert und dabei eine Summe und einen Übertrag erzeugt.
Dabei wird die Summe mit Hilfe eines XOR-Gatters und der Übertrag mit Hilfe eines AND-Gatters dargestellt.
Der Halbaddierer verarbeitet lediglich zwei Eingänge. In einer Rechenkette, die über die Einerstelle hinausgeht, muss jedoch ein Übertrag aus der vorherigen Stelle mit einberechnet werden können.
Diese Einschränkung führt zur Notwendigkeit des Volladdierers, der im nächsten Schritt betrachtet wird.
4.2 Volladdierer
Der Volladdierer ist die notwendige Erweiterung des Halbaddierers, um mehrstellige Binärzahlen addieren zu können. Er ist in der Lage, neben den zwei Operanden A und B auch einen Übertrag aus einer vorherigen Stelle (Cin) zu verarbeiten.
Er lässt sich effizient durch die Kombination von zwei Halbaddierern und einem OR-Gatter realisieren. Die Logik teilt sich dabei wie folgt auf:
- Erster Halbaddierer: Addiert die Eingänge A und B und liefert eine Teilsumme sowie einen Teilübertrag.
- Zweiter Halbaddierer: Addiert die Teilsumme des ersten Schritts mit dem eingehenden Übertrag Cin. Dies ergibt das endgültige Summenbit S.
- OR-Gatter: Verknüpft die Überträge beider Halbaddierer. Wenn mindestens einer der beiden Schritte einen Übertrag erzeugt, ist der endgültige Übertrag Cout aktiv.
Schaltung:
Ein Volladdierer (FA) ist eine kombinatorische Schaltung, die zwei einstellige Binärzahlen sowie den Übertrag der vorherigen Stelle addiert und dabei eine Summe und einen Übertrag erzeugt.
Dabei werden zwei Halbaddierer und ein OR-Gatter verwendet.
Mit der Analyse des Volladdierers ist die Grundlage für das Verständnis moderner Rechenarchitekturen gelegt. Während ein einzelner Volladdierer lediglich die kleinste Einheit einer Rechnung darstellt, bildet die Kaskadierung dieser Bausteine das Herzstück jedes Prozessors. Durch das Hintereinanderschalten lassen sich beliebig große Binärzahlen addieren, was die Basis für alle komplexeren mathematischen Operationen und logischen Entscheidungen eines Computers bildet.
Aufgabe 1: 2-Bit-Zahlen
In einem digitalen Rechenwerk sollen zwei 2-Bit-Zahlen (z.B. 10 und 11) addiert werden.
- Warum ist es technisch ausreichend, für die niederwertigste Stelle (Bit 0) einen Halbaddierer zu verwenden, während für die höherwertige Stelle (Bit 1) zwingend ein Volladdierer benötigt wird?
- Zeichne die Schaltung.
- Überlege, wie sich die Schaltung für Bit 1 ändern müsste, wenn man auch dort nur einen Halbaddierer zur Verfügung hätte. Wäre eine korrekte Addition der Gesamtzahl dann noch möglich?
Lösung
-
Bit 0 (LSB – Last Significant Bit): Bei der Addition der niedrigsten Stelle gibt es per Definition keinen Übertrag aus einer vorherigen Spalte. Da lediglich zwei Summanden (A0 und B0) addiert werden müssen, ist die Funktionalität eines Halbaddierers (2 Eingänge) vollständig ausreichend.
Bit 1: Diese Stelle muss nicht nur die eigenen Bits (A1 und B1) verarbeiten, sondern auch den potenziellen Übertrag (C) aus der Rechnung von Bit 0 aufnehmen. Da somit drei Eingangssignale gleichzeitig verarbeitet werden müssen, ist der Einsatz eines Volladdierers zwingend erforderlich. -
-
Technische Änderung: Ein Halbaddierer besitzt nur zwei Eingänge. Der Übertrag aus der Stelle Bit 0 könnte somit nicht angeschlossen werden. Er würde "ins Leere laufen" oder müsste ignoriert werden.
Auswirkung auf die Korrektheit: Eine korrekte Addition der Gesamtzahl wäre nicht mehr möglich, sobald bei der Addition von Bit 0 ein Übertrag entsteht (also bei 1+1).
Beispiel: 01+01
→ Bit 0 ergibt 1+1=0 (Übertrag 1).
→ Bit 1 würde (da es den Übertrag ignoriert) lediglich 0+0=0 rechnen.
→ Das falsche Ergebnis wäre 00, obwohl 10 korrekt wäre.
Fazit: Der Halbaddierer an Bit 1 würde die Informationen der vorherigen Stelle vernichten, wodurch die mathematische Integrität des Rechenwerks verloren ginge.
Aufgabe 2: Eingang unbekannt
Ein Volladdierer liefert das Ergebnis S=0 und Cout=1.
- Welche verschiedenen Eingangskombinationen (A, B, Cin) führen zu genau diesem Ergebnis?
- Warum ist das Ergebnis S=0 und Cout=1 mathematisch gleichbedeutend mit der Dezimalzahl 2?
Lösung
-
Damit die Summe S=0 und der Übertrag Cout=1 ausgegeben werden, muss die Summe der Eingänge exakt 2 ergeben. Dies ist bei genau drei Kombinationen der Fall, bei denen jeweils zwei Eingänge auf "1" und einer auf "0" gesetzt sind:
Eingang A Eingang B Eingang Cin Summe (S) Übertrag (Cout) 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 -
Das Summenbit (S): Es repräsentiert die niederwertigste Stelle (20) des Ergebnisses.
Das Übertragsbit (Cout): Es repräsentiert die nächsthöhere Stelle (21), da dieser Wert in einer Kaskadierung an die nächste Spalte weitergereicht wird.
Das Bitpaar 10 in binärer Schreibweise entspricht somit exakt der 2 im Dezimalsystem.
Aufgabe 3: Erzeuge das Ergebnis
Aufgabe 4: Der kaskadierte Übertrag (Ripple-Carry)
Ein 4-Bit-Addierwerk besteht aus vier hintereinandergeschalteten Volladdierern.
- Zeichne die Schaltung.
- Angenommen, an den Eingängen liegen die Zahlen 1111 und 0001 an.
Wie viele Volladdierer müssen nacheinander einen Übertrag (Cout) berechnen, bevor das korrekte Endergebnis feststeht? - Warum ist diese Schaltung für extrem große Bitbreiten (z. B. 64-Bit) problematisch im Hinblick auf die Rechengeschwindigkeit?
Lösung
-
Es müssen alle vier Volladdierer nacheinander einen Übertrag berechnen. Das korrekte Endergebnis 10000 steht erst fest, nachdem der Übertrag durch die gesamte Kette „gerippelt“ ist.Stufe (VA) Eingang A Eingang B Eingang Cin (Übertrag) Rechnung Summe (S) Cout (neuer Übertrag) Bit 0 (VA₀) 1 1 0 1 + 1 + 0 0 1 ➔ Bit 1 (VA₁) 1 0 1 1 + 0 + 1 0 1 ➔ Bit 2 (VA₂) 1 0 1 1 + 0 + 1 0 1 ➔ Bit 3 (VA₃) 1 0 1 1 + 0 + 1 0 1 (Überlauf) -
Das Problem dieser Schaltung ist die Signallaufzeit (Propagation Delay).
Abhängigkeit: Da jeder Volladdierer auf das Ergebnis des vorherigen warten muss, summiert sich die Zeit, die die Gatter für die Berechnung benötigen.
Geschwindigkeit: Bei einem 64-Bit-Addierer müsste das Signal im schlimmsten Fall durch 64 hintereinandergeschaltete Einheiten wandern. Während moderne Gatter extrem schnell schalten (im Bereich von Nanosekunden), führt diese sequentielle Abhängigkeit bei hohen Taktfrequenzen zu einer massiven Bremsung des gesamten Prozessors.
In modernen Hochleistungs-CPUs verwendet man deshalb keine einfachen Ripple-Carry-Adder, sondern sogenannte Carry-Look-Ahead-Addierer, die Überträge über mehrere Stellen hinweg parallel vorausberechnen können.