Name:  Datum: 

Lernziele

• Sie kennen die Logikgates und ihre Wahrheitstabellen und können aus einer logischen Schaltung eine Wahrheitstabelle ableiten.
• Sie kennen das XOR-Gate («genau eines von beiden»).
• Sie können eine logische Schaltung für einen Halbaddierer mit den korrekten Symbolen zeichnen und nachvollziehen.
• Sie können erklären, wieso man für die Addition längerer Binärzahlen pro Stelle drei Bits addieren muss («Behalte» bzw. «Carry»).
• Sie können eine logische Schaltung für einen Addierer (Volladdierer) mit den korrekten Symbolen zeichnen und nachvollziehen.
• Sie können erklären, wie man grössere Zahlen mit mehreren Addierern zusammenzählen kann (Multibit-Addierer), und eine Addition damit Schritt für Schritt durchrechnen.

Ihr Computer ist eine Rechenmaschine, die auf purer Logik aufgebaut ist. Es gibt keine Magie, kein "Geist" in der Maschine - alles ist von Grund auf nachvollziehbar.

Um Ihnen das zu zeigen, bauen wir in diesen drei Lektionen einen Addierer, der zwei Zahlen zusammenzählen kann. Dazu brauchen wir sogenannte Logikgates - das sind elektrotechnische Schaltkreise, die eine grundsätzliche Logikfunktion implementieren, sodass Sie zum Beispiel fragen können: "Ist A oder B gleich 1?"

Teil 1 · Logikgates und Halbaddierer

Aufwärmen: Logikgates

Diese Logikgates implementieren jeweils eine Logikfunktion, wie z.B. "und", "nicht", oder "oder". Mit Wahrheitstabellen erfassen wir, was diese Logikgates tun. (Die Symbole und mathematischen Notationen müssen Sie nicht auswendig lernen.)

Ein neues Gate: XOR

XOR steht für «exklusives Oder» (englisch exclusive or). Das XOR-Gate gibt eine 1 aus, wenn genau eines von beiden Inputs 1 ist - also A oder B, aber nicht beide.

Das Symbol sieht aus wie das OR-Gate, hat aber links einen zusätzlichen Bogen (siehe letzte Zeile in der Tabelle oben). Als Notation schreibt man $A \oplus B$.

Füllen Sie die Wahrheitstabelle für XOR aus - ohne nach oben zu schauen:

A	B	A XOR B
0	0
0	1
1	0
1	1

Worin unterscheidet sich XOR vom normalen OR?

Lösung XOR

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Der einzige Unterschied zum OR ist die letzte Zeile: Wenn A und B beide 1 sind, gibt OR eine 1 aus, XOR aber eine 0.

Wahrheitstabelle ganzer Schaltungen

Schaltungen kann man auch aus mehreren Logikgates bauen und dazu dann eine Wahrheitstabelle schreiben. Füllen Sie für die beiden Schaltungen die Wahrheitstabelle aus.

Schaltung 1

A	B	out
0	0
0	1
1	0
1	1

Lösung Schaltung 1

Die Wahrheitstabelle und die Herleitung mit Farben:

A	B	out
0	0	0
0	1	0
1	0	1
1	1	0

Schaltung 2

A	B	out
0	0
0	1
1	0
1	1

Lösung Schaltung 2

Die Wahrheitstabelle und die Herleitung mit Farben:

A	B	out
0	0	0
0	1	1
1	0	0
1	1	0

Intuitive Annäherung

Führen Sie sich folgende binäre Addition von zwei Bits vor Augen. Achtung: Wir sind im Binärsystem!

Ich habe immer zwei Stellen beim Ergebnis hingeschrieben, damit wir uns folgendes überlegen können: Was ist die Logik beider Stellen?

Überlegen Sie sich nun die Logik:

1. Wann gibt es bei den 2ern (blau) eine 1 im Ergebnis?
2. Wann gibt es bei den 1ern (grün) eine 1 im Ergebnis?

Lösung Intuitive Annäherung

1. Bei den 2ern gibt es eine 1, wenn A und B 1 sind.
2. Bei den 1ern gibt es eine 1, wenn nur A oder nur B 1 sind.

Der Halbaddierer

Wir wollen nun eine Schaltung bauen, die zwei Bits "A" und "B" zusammenzählt, wie oben bei der Rechnung. "Low" ist die tiefere Stelle (die 1er), "high" die höhere Stelle (die 2er).

Aufgabe 1: Füllen Sie die Wahrheitstabelle aus.

A	B	high	low
0	0
0	1
1	0
1	1

Aufgabe 2: Vergleichen Sie die Spalten "high" und "low" mit den Wahrheitstabellen der Logikgates. Welches Gate passt zu "high", welches zu "low"? Zeichnen Sie die Schaltung mit den korrekten Symbolen: Die Inputs A und B gehen in beide Gates.

Lösung Halbaddierer

A	B	high	low
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Die Spalte "high" ist genau die Wahrheitstabelle von AND, die Spalte "low" genau die von XOR. Diese Schaltung nennt man Halbaddierer: Sie zählt zwei Bits "A" und "B" zusammen.

Teil 2 · Volladdierer

Rückblick: der Halbaddierer

Letzte Lektion haben wir einen sogenannten Halbaddierer gebaut, der zwei Bits "A" und "B" zusammenzählt. "Low" ist die tiefere Stelle, "high" die höhere Stelle.

Wieso der Halbaddierer nicht reicht

Damit können wir nur eine einzelne Stelle einer binären Zahl addieren. Für eine Addition von längeren Zahlen müssten wir nicht zwei sondern drei Bits addieren können. Wieso?

Schauen Sie sich dazu folgende schriftliche Addition zweier Binärzahlen an:

Man könnte denken, dass man die 1er, 2er, 4er und 8er nacheinander mit dem Halbaddierer addieren kann - es sind ja jeweils zwei Bits.

Stelle	Rechnung	Ergebnis
Bei den 1ern geht das:	1+0	= 1
Bei den 2ern auch:	0+1	= 1
Aber die 4er machen Probleme!	1+1	= 10

Sie würden das als Mensch mit einem "Behalte" auf die nächste Stelle lösen. Auf Englisch wird das "Carry" genannt, deswegen schreiben wir im Folgenden "C". Überlegen wir uns also die Rechnung:

• Bei den 4ern würden Sie also 0 ins Ergebnis schreiben, aber ein Behalte 1 in die nächste Stelle - die 8er (blaue Pfeile).
• Bei den 8ern hätten Sie dann entsprechend drei Bits, die Sie addieren müssen (in diesem Fall drei Einsen).

Sie sehen: Um zwei Binärzahlen mit mehreren Stellen addieren zu können, müssen wir pro Stelle nicht zwei sondern drei Bits addieren können: wegen dem "Behalte" (oder auf Englisch: "Carry"). Und genau das macht der "Voll"-Addierer (oder auch einfach Addierer genannt).

Kontrollfrage: Was ist das Ergebnis der Addition $1101_2 + 1110_2$ oben? Rechnen Sie es auch dezimal nach.

Lösung Kontrollfrage

$1101_2 + 1110_2 = 11011_2$. Dezimal: $13 + 14 = 27 = 16 + 8 + 2 + 1$.

Mit Abstraktion zum Addierer

Um die Schaltung für den (Voll-)Addierer zu verstehen, schlage ich vor, dass Sie auf dem Halbaddierer aufbauen und seine Funktionsweise total ausblenden. Überlegen Sie sich den Halbaddierer als eine Box, die zwei Inputs zusammenzählt:

• Wenn beide Inputs 1 sind, kommt beim "high" 1 raus.
• Wenn nur einer der Inputs 1 ist, kommt beim "low" 1 raus.
• Wenn keiner der Inputs 1 ist, kommt nirgends eine 1 raus.

Jetzt wollen wir dazu einfach noch einen weiteren Input C zum Ergebnis dazuaddieren. Überlegen wir uns die Stellen wieder einzeln:

• Wenn das "h" des ersten Halbaddierers 1 ist, sind die Inputs A und B beide 1. Wir können uns also sicher sein, dass das Signal irgendwie zum "HIGH" der gesamten Schaltung muss - weil wir haben bereits den Zahlenwert zwei.
• Wenn beim "l" des ersten Halbaddierers 1 rauskommt, war entweder A oder B 1 und wir können das als normalen Input betrachten! Wir können "l" mit einem zweiten Halbaddierer mit C zusammenrechnen.

Überlegen wir uns die Outputs des zweiten Halbaddierers:

• Wenn das "h" beim zweiten Halbaddierer 1 ist, kam von entweder A oder B 1 und von C eine zusätzliche 1. Das Signal muss weiter zum "HIGH" der gesamten Schaltung - weil wir haben den Zahlenwert zwei.
• Wenn das "l" des zweiten Halbaddierers eins ist, heisst das, er hat nur eine 1 empfangen. Das muss also zum "LOW" der Schaltung.

Eine Schwierigkeit ist noch, dass entweder vom ersten oder vom zweiten Halbaddierer ein Signal kommen kann und beide müssen zum "HIGH" der gesamten Schaltung. Wie hängen wir das zusammen? Nun, die Logik ist bereits im Satz: mit einem OR-Gate.

Wenn Sie das nun ohne unsere abstrakten Boxen zusammenstecken wollen, müssen Sie sich überlegen, was denn nochmal in den Halbaddierern steckt. Voilà, Sie haben einen Volladdierer gebaut!

Aufgaben zum Volladdierer

Aufgabe 1: Füllen Sie die Wahrheitstabelle des Volladdierers aus. Tipp: Zählen Sie einfach, wie viele Einsen bei A, B und C stehen, und schreiben Sie diese Anzahl als zweistellige Binärzahl (high, low).

A	B	C	high	low
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Lösung Aufgabe 1 (Volladdierer)

A	B	C	high	low
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Bei keiner 1 ist das Ergebnis $00_2$, bei einer 1 ist es $01_2$, bei zwei Einsen $10_2$ und bei drei Einsen $11_2$.

Aufgabe 2: Verfolgen Sie in der Schaltung des Volladdierers (letztes Bild oben) die Signale für A = 1, B = 1, C = 1. Schreiben Sie an jede Leitung, ob eine 0 oder eine 1 anliegt. Stimmt das Ergebnis mit Ihrer Tabelle überein?

Lösung Aufgabe 2 (Volladdierer)

Erster Halbaddierer (A = 1, B = 1): h = 1, l = 0. Zweiter Halbaddierer (l = 0, C = 1): h = 0, l = 1. Das OR-Gate bekommt 1 und 0, also HIGH = 1. LOW = 1. Ergebnis $11_2 = 3$ - stimmt mit der letzten Zeile der Tabelle überein.

Aufgabe 3: Zeichnen Sie den Volladdierer aus dem Gedächtnis - zuerst mit zwei Halbaddierer-Boxen und einem OR-Gate, dann ganz mit Logikgates (AND, XOR, OR).

Lösung Aufgabe 3 (Volladdierer)

Mit Boxen:

Ganz mit Logikgates:

Teil 3 · Multibit-Addierer

Mehrere Addierer zusammenhängen

Wir haben nun einen Addierer gebaut, der drei Inputs zusammenrechnen kann. Das heisst: Wir können nun die schriftliche Addition von Binärzahlen automatisieren!

Hier ein Beispiel, wie Sie vier Addierer zu einem Multibit-Addierer zusammenhängen würden, um 13+5 zu rechnen.

So lesen Sie die Zeichnung:

• Jede Box "add" ist ein Volladdierer und ist für eine Stelle zuständig (ganz rechts die 1er, dann 2er, 4er, 8er).
• Oben kommen die Bits von A (rot) und B (grün) dieser Stelle hinein, dazu das "Behalte" C (blau) von der Stelle rechts davon. Der 1er-Addierer ganz rechts hat kein Behalte - dort ist C einfach 0.
• Das "l" (low) ist das Ergebnis dieser Stelle. Das "h" (high) ist das Behalte und wird zum Addierer der nächsten Stelle links weitergeleitet.
• Das "h" des letzten Addierers ganz links wird zur 16er-Stelle des Ergebnisses.

Hierzu habe ich Schablonen vorbereitet:

• Multibit-Addierer mit Beispielrechnung als PDF
• Multibit-Addierer mit Platzhaltern als PDF

Aufgabe: Selbst rechnen mit dem Multibit-Addierer

Rechnen Sie die folgenden Additionen mit der leeren Schablone (Multibit-Addierer mit Platzhaltern) durch. Gehen Sie jeweils so vor:

1. Wandeln Sie beide Zahlen in 4-stellige Binärzahlen um.
2. Tragen Sie die Bits von A und B oben bei den passenden Addierern ein.
3. Rechnen Sie von rechts nach links: Bestimmen Sie für jeden Addierer "h" und "l" und leiten Sie "h" als C zum nächsten Addierer weiter.
4. Lesen Sie das Ergebnis unten ab und kontrollieren Sie es dezimal.

Falls Sie keine Schablone haben, zeichnen Sie die vier Addierer-Boxen selbst ins Feld.

a) $6 + 7$

b) $9 + 11$

c) $3 + 5$

Lösung a) 6 + 7

$6 = 0110_2$, $7 = 0111_2$. Von rechts nach links:

Stelle	A	B	C (Behalte)	h	l
1er	0	1	0	0	1
2er	1	1	0	1	0
4er	1	1	1	1	1
8er	0	0	1	0	1

Ergebnis: $01101_2 = 8 + 4 + 1 = 13$ ✓

Lösung b) 9 + 11

$9 = 1001_2$, $11 = 1011_2$. Von rechts nach links:

Stelle	A	B	C (Behalte)	h	l
1er	1	1	0	1	0
2er	0	1	1	1	0
4er	0	0	1	0	1
8er	1	1	0	1	0

Das "h" des 8er-Addierers wird zur 16er-Stelle. Ergebnis: $10100_2 = 16 + 4 = 20$ ✓

Lösung c) 3 + 5

$3 = 0011_2$, $5 = 0101_2$. Von rechts nach links:

Stelle	A	B	C (Behalte)	h	l
1er	1	1	0	1	0
2er	1	0	1	1	0
4er	0	1	1	1	0
8er	0	0	1	0	1

Ergebnis: $01000_2 = 8$ ✓ - hier wird das Behalte dreimal hintereinander weitergereicht.

Repetition

Beantworten Sie die Fragen in eigenen Worten.

1. Wann gibt ein XOR-Gate eine 1 aus? Worin unterscheidet es sich vom OR-Gate?

2. Aus welchen zwei Gates besteht ein Halbaddierer? Welches Gate liefert "high", welches "low"?

3. Wieso reicht ein Halbaddierer nicht, um längere Binärzahlen zu addieren?

4. Aus welchen Bausteinen besteht ein Volladdierer?

5. Wie viele Volladdierer braucht man, um zwei 8-Bit-Zahlen (zwei Bytes) zu addieren? Wie viele Bits kann das Ergebnis haben?

Lösung Repetition

1. XOR gibt eine 1 aus, wenn genau einer der beiden Inputs 1 ist. Im Unterschied zum OR gibt XOR bei 1 und 1 eine 0 aus.
2. Aus einem AND ("high") und einem XOR ("low").
3. Bei der schriftlichen Addition entsteht ein "Behalte" (Carry), das zur nächsten Stelle dazukommt. Pro Stelle muss man deshalb drei Bits addieren können: A, B und C. Der Halbaddierer kann nur zwei.
4. Aus zwei Halbaddierern und einem OR-Gate - also ganz mit Logikgates aus zwei AND, zwei XOR und einem OR.
5. Acht Volladdierer, einen pro Stelle. Das Ergebnis kann 9 Bits haben, weil das "h" des letzten Addierers eine neue Stelle ergibt (z.B. $255 + 255 = 510$).