Von Logikgattern zu Addierern
Computer "rechnen" nicht — sie bauen nur Bausteine Schicht für Schicht mit Logikgattern auf. In dieser Lektion bauen wir eine Schaltung, die Zahlen von Hand mit XOR-, AND- und OR-Gattern addieren kann, vom Halbaddierer über den Volladdierer bis zum 4-Bit-Addierer, Schritt für Schritt aufbauend.
Addition im Alltag – inspiriert von der schriftlichen Addition
Erinnere dich an den Prozess der Addition auf Papier. Berechne37 + 58：
Berechne zuerst die Einerstelle:7 + 8 = 15, schreibe5，, erhöhe um 1。
Berechne dann die Zehnerstelle:3 + 5 + Übertrag 1 = 9, schreibe9, das Ergebnis ist95。
Dieser Prozess zeigt drei Kernpunkte:
1. Bitweise Berechnung: Jedes Bit kümmert sich nur um seine beiden Summanden und den Übertrag vom niederwertigeren Bit.
2. Übertragsfortpflanzung: Nachdem das niederwertigere Bit berechnet wurde, kann ein Übertrag entstehen, und dieser Übertrag muss an das höherwertige Bit weitergegeben werden.
3. Besonderheit des niedrigstwertigen Bits: Das niedrigste Bit hat keinen Übertrag von einem niederwertigeren Bit; es muss nur die beiden Summanden verarbeiten.
Computer führen Additionen nach demselben Prinzip durch: ein großes Problem (Multi-Bit-Addition) in viele kleine Probleme (1-Bit-Addition) zerlegen und sie dann nacheinander lösen.
Halbaddierer — 1-Bit-Addition für das niedrigste Bit
Das niedrigste Bit hat keinen Übertragseingang; es muss nur zwei 1-Bit-Binärzahlen addieren. Eine Schaltung, die diese Situation bewältigen kann, wird alsHalbaddierer bezeichnet。
Ein Halbaddierer hat zwei Eingänge A und B und zwei Ausgänge:SummenbitundÜbertrag。
Wahrheitstabelle des Halbaddierers:
| A | B | Summe (sum) | Übertrag |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Bei Betrachtung der Wahrheitstabelle fällt eine überraschende Übereinstimmung auf:
Sum = A XOR B. Wenn A und B verschieden sind, ist Sum=1; wenn sie gleich sind, ist Sum=0 — das ist genau die Wahrheitstabelle eines XOR-Gatters.
Carry = A AND B. Ein Übertrag wird nur erzeugt, wenn beide Eingänge 1 sind — das ist genau die Wahrheitstabelle eines AND-Gatters.
Ein Halbaddierer benötigt nur1 XOR-Gatter + 1 AND-GatterDas lässt sich implementieren. George Boole hätte sich wohl nie vorgestellt, dass das von ihm erfundene algebraische System eines Tages zur mathematischen Grundlage von Addierern werden würde.
Volladdierer—Vollständige Addition mit Übertragsbehandlung
Der Halbaddierer hat einen fatalen Fehler:Er kann keinen Übertrag vom niederwertigeren Bit empfangen.. Außer beim niedrigsten Bit muss jedes Bit drei Zahlen verarbeiten: A, B und den Übertragseingang Cin vom niederwertigeren Bit.
Eine Schaltung, die gleichzeitig zwei Summanden und einen Übertragseingang verarbeiten kann, wird alsVolladdierer bezeichnet。
Wahrheitstabelle des Volladdierers:
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Ein cleveres Design:Man kann einen Volladdierer mit zwei Halbaddierern bauen。
Schritt 1: Halbaddierer 1 verarbeitet A und B und erzeugt die Zwischensumme S1 und den Übertrag C1.
Schritt 2: Halbaddierer 2 verarbeitet S1 und Cin und erzeugt die Endsumme Sum und den Übertrag C2.
Schritt 3: EndübertragCout = C1 OR C2(Wenn einer der beiden Halbaddierer einen Übertrag erzeugt, ist die endgültige Ausgabe ein Übertrag.)
Die Schaltungsstruktur eines Volladdierers:2 Halbaddierer + 1 OR-Gatter. Übereinander geschichtet, ist jeder Halbaddierer intern XOR + AND. Diese hierarchische Konstruktionsidee zieht sich durch die gesamte Computerarchitektur.
Kaskadierung von Volladdierern — 4-Bit-Ripple-Carry-Addierer
Mit Volladdierern wird die Mehrbit-Addition einfach:Verbinde mehrere Volladdierer in Reihe, wobei der Übertragsausgang des niedrigeren Bits mit dem Übertragseingang des höheren Bits verbunden wird。
Die Kaskadenstruktur eines 4-Bit-Addierers:
Bit 0 (niedrigstwertiges Bit): Volladdierer verarbeitet A0, B0, carry-in = 0, erzeugt Summe S0 und Übertrag C0.
Bit 1: Volladdierer verarbeitet A1, B1, carry-in = C0, erzeugt Summe S1 und Übertrag C1.
Bit 2: Volladdierer verarbeitet A2, B2, carry-in = C1, erzeugt Summe S2 und Übertrag C2.
Bit 3 (höchstwertiges Bit): Volladdierer verarbeitet A3, B3, carry-in = C2, erzeugt Summe S3 und Übertrag C3 (Endübertrag).
Der Übertrag breitet sich wie Wasserwellen vom niedrigen Bit zum hohen Bit Ebene für Ebene aus, daher wird diese StrukturRipple-Carry-Addierer (Ripple Carry Adder) genannt。
Der Ripple-Carry-Addierer ist einfach und intuitiv, hat aber einen Leistungsengpass: Im schlimmsten Fall muss sich der Übertrag von Bit 0 bis zum höchsten Bit ausbreiten und dabei N Stufen von Volladdierer-Verzögerungen durchlaufen. Moderne CPUs verwenden Techniken wie Carry-Lookahead zur Optimierung, aber das Verständnis des Ripple-Carry ist eine Voraussetzung für das Verständnis aller Addierer-Optimierungen.
Python-Code-Demo
Beispiel
# Vorlesung 8: Von Logikgattern zu Addierern - Python-Demo
# Beispiel-Tutorial-Serie
# ============================================
def half_adder(a, b):
"""
Halbaddierer: addiert zwei 1-Bit-Binärzahlen und ignoriert den Übertragseingang.
Parameter:
a, b: jeweils 0 oder 1
Rückgabe:
(sum_bit, carry_out): Summenbit und Übertragsausgang
Schaltungsimplementierung:
sum_bit = a XOR b (XOR-Gatter)
carry_out = a AND b (AND-Gatter)
"""
sum_bit = a ^ b # XOR: gleich ist 0, verschieden ist 1
carry_out = a & b # AND: Übertrag nur, wenn beide 1 sind
return sum_bit, carry_out
def full_adder(a, b, carry_in):
"""
Volladdierer: Addiere zwei 1-Bit-Binärzahlen unter Berücksichtigung des Übertragseingangs.
Parameter:
a, b, carry_in: jeweils 0 oder 1
Rückgabe:
(sum_bit, carry_out): Summenbit und Übertragsausgang
Implementierungstipp—zwei Halbaddierer kaskadieren:
Schritt 1: half_adder(a, b) → (s1, c1)
Schritt 2: half_adder(s1, carry_in) → (sum_bit, c2)
Endgültiger Übertrag: carry_out = c1 OR c2
"""
s1, c1 = half_adder(a, b)
sum_bit, c2 = half_adder(s1, carry_in)
carry_out = c1 | c2 # OR-Gatter: Wenn einer von beiden einen Übertrag hat, wird der endgültige Übertrag gesetzt
return sum_bit, carry_out
def adder_4bit(a_bits, b_bits):
"""
4-Bit-Ripple-Carry-Addierer: 4 kaskadierte Volladdierer.
Parameter:
a_bits: 4-Bit-Binärliste, a_bits[0] ist das niederwertigste Bit (LSB)
b_bits: 4-Bit-Binärliste, b_bits[0] ist das niederwertigste Bit (LSB)
Rückgabe:
(sum_bits, final_carry): 4-Bit-Summe (niederwertigstes Bit zuerst) und finaler Übertrag
Gib den vollständigen Ablauf der Carry-Weitergabe aus, der veranschaulicht, wie Ripple-Carry funktioniert.
"""
carry_in = 0
sum_bits = []
print("=" * 55)
print(4-Bit-Ripple-Carry-Addierer — Carry-Propagationsprozess)
print("=" * 55)
# Höherwertige Bits zuerst anzeigen, zur einfacheren Lesbarkeit
print(f" Summand A: {list(reversed(a_bits))} (höherwertige Bits zuerst)")
print(f" Summand B: {list(reversed(b_bits))} (höherwertige Bits zuerst)")
print()
for i in range(4):
s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
sum_bits.append(s)
print(f" [Bit {i}] (das niedrigstwertige Bit ist Bit 0)")
print(f" Eingabe: A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, Übertragseingang={carry_in}")
print(fAusgabe: Summenbit={s}, Übertragsausgang={carry_out})
if carry_out:
print(f>> Übertrag erzeugt! Übertrag={carry_out} wird an Bit {i+1} weitergegeben)
carry_in = carry_out # Der aktuelle Übertrag wird zum Übertragseingang des nächsten Bits
print()
print(fBerechnungsergebnis: {list(reversed(sum_bits))} (höherwertige Bits zuerst))
print(fEndübertrag: {carry_in})
print("=" * 55)
return sum_bits, carry_in
def decimal_to_4bit(n):
"""Konvertiere Dezimalzahlen 0-15 in 4-Bit-Binärlisten (niedrigstwertiges Bit zuerst)"""
return [(n >> i) & 1 for i in range(4)]
def bits_to_decimal(bits):
"""Konvertiert eine Liste binärer Bits (niedrigstwertiges Bit zuerst) in eine ganze Dezimalzahl"""
return sum(bit * (2 ** i) for i, bit in enumerate(bits))
# ============================================
# Testfall
# ============================================
print(>>> Beispiel-Test für Halbaddierer <<<)
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f" half_adder({a}, {b}) => Summe={s}, Übertrag={c}")
print()
print(>>> Beispiel-Test für Volladdierer <<<)
test_cases = [
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
s, c = full_adder(a, b, cin)
print(f" full_adder({a}, {b}, carry_in={cin}) => Summe={s}, Übertrag={c}")
print()
print(>>> Beispiel-Test für 4-Bit-Addierer: 7 + 5 <<<)
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(fErwartet: {a_dec} + {b_dec} = {a_dec + b_dec})
print(fErgebnis: {result_dec} (Übertrag={final_carry}))
print(f" Beispielüberprüfung: {'Bestanden!' if result_dec == a_dec + b_dec else 'Fehlgeschlagen!'}")
print()
print(>>> Beispiel-Zusatztest: 10 + 6 (möglicher Überlauf) <<<)
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" Erwartet: 10 + 6 = 16")
print(f" 4-Bit-Ergebnis: {result_dec2}, Übertragsbits: {carry2}, Vollständiger 5-Bit-Wert: {full_result}")
print(fBeispielüberprüfung: {'Bestanden!' if full_result == 16 else 'Fehlgeschlagen!'})
Führen Sie den Code aus und beobachten Sie, wie sich der Übertrag zwischen den einzelnen Bits fortpflanzt – das niedrigstwertige Bit wird zuerst berechnet, und nachdem ein Übertrag erzeugt wurde, wird er an das nächste Bit weitergegeben; das nächste Bit wird dann berechnet, und wenn ein Übertrag erzeugt wird, wird er weitergegeben. Daher stammt der Name „Ripple-Carry“.
Interaktive Demo: 4-Bit-Addierer-Kaskadenanimation (Beispiel-Demo zur Übertragsausbreitung)
Unten wird ein 4-Bit-Ripple-Carry-Addierer mit reinem div+SVG simuliert.Klicken Sie auf die Schaltfläche, um schrittweise durchzugehen, wie sich der Übertrag von Bit 0 (niedrigstwertiges Bit) zu Bit 3 (höchstwertiges Bit) fortpflanzt., oder Sie können „Auto-Demo“ verwenden, um den gesamten Prozess anzusehen.