Kapitel 3 - Binärarithmetik

Dieses Kapitel ist wieder für zwei Wochen gedacht. Eine gute Stelle für den Schnitt ist nach Abschnitt drei, dies kommt zeitlich ganz gut hin, und es fängt außerdem mit der Multiplikation ein neues Thema an. Die Fragestunden und Übungsblätter sind entsprechend organisiert.

Wir lernen in diesem Kapitel, wie man mit Binärzahlen und damit in der Gatterlogik rechnet. Dafür übersetzen wir zunächst die Algorithmen zum schriftlichen Rechnen, die aus der Grundschule bekannt sind, in das Binärsystem. Besondere Finesse ist für die Behandlung negativer Zahlen auf möglichst effiziente Art und Weise nötig. Wir behandeln daher ausführlich das Zweierkomplement als Darstellung für negative Binärzahlen, und setzen damit Algorithmen für Addition, Subtraktion und Multiplikation von Binärzahlen mit beliebigen Vorzeichen um. Die Algorithmen für Addition und Subtraktion werden außerdem in Schaltnetzen implementiert, und in die arithmetisch-logische Einheit (ALU) der Hack-Architektur eingebettet. Dieses Bauelement untersuchen wir ebenfalls ausführlich, da es den Kern des zukünftigen Hack-Prozessors bildet.

Inhalt

Abschnitt 1 - Erinnerung Stellenwertsysteme, mechanische Rechenhilfen

Folien 1-16

Den Inhalt dieses Abschnittes hat wohl jeder schon einmal in der Schule gelernt, daher kann man hier wahrscheinlich gefahrlos auch mit den Folien alleine auskommen. Zur Sicherheit erkläre ich trotzdem alles, für den Fall, daß eine Auffrischung nötig ist.

Wir erinnern uns daran, wie Stellenwertsysteme mit einer allgemeinen Basis, der Anzahl der verfügbaren Ziffern, funktionieren. Insbesondere lernen wir die Verfahren, um zwischen verschiedenen Basen zu konvertieren, vielleicht mit Nachkommastellen nicht mehr ganz so geläufig. Als Vorbereitung für die Übertragung der "Grundschulalgorithmen" für schriftliches Rechnen ins Binärsystem erinnern wir uns noch einmal kurz an die Details dieser Verfahren. Wir schließen die Einführung ab mit ein paar kurzen Verweisen auf mechanische Rechenhilfen, welche Addition im Zehnersystem, insbesondere also den Zehnerübertrag implementieren.


Index

00:00 Einleitung und Überblick
03:20 Erinnerung Zahlendarstellung und Stellenwertsysteme
08:45 Gebräuchliche Stellenwertsysteme im Alltag
13:15 Konvertierung zwischen Stellenwertsystemen
29:25 Allgemeine Formel zur Interpretation einer Ziffernfolge zur Basis $b$
32:25 Schriftliche Addition und Subtraktion, Stellenüberlauf und -unterlauf
34:35 Multiplikation und Division
37:40 Rechenhilfsmittel in der Basis 10: Rechenstäbchen, Rechenuhr von Schickard


Abschnitt 2 - Funktionen und Schaltungen für die Addition positiver Binärzahlen

Folien 17-27

Wir erabeiten grundlegende Ideen, wie man Binärzahlen in Schaltkreisen darstellt und elementare Rechenoperationen durchführen kann. Um mit der Mathematik an einfachen Beispielen vertraut zu werden, zeigen wir Formeln für die Multiplikation mit Zwei und eine Summenformel für die ersten $n+1$ Zweierpotenzen. Anschließend entwickeln wir die Schaltpläne für ein Addierwerk für positive Binärzahlen. Als direkte Übersetzung des Grundschulalgorithmus wird pro Ziffer ein Volladdierer (für zwei Bits und Übertrag) in eine Kette geschaltet. Optimierte Implementierungen verdoppeln einen Teil der Rechenwerke, um auf Kosten zusätzlicher Hardware die Laufzeit zu senken.


Index

00:00 Einleitung, Rechnen mit Binärzahlen und Schaltkreise
03:00 Mathematische Übungen: Multiplikation mit Zwei, Test auf gerade/ungerade
08:30 Summenformel für alle Zweierpotenzen von $2^0$ bis $2^n$
16:40 Optional: Summenformel für Binomialkoeffizienten
20:05 Addition von zwei Bits: Wahrheitswertetafeln und Schaltungen des Halbaddierers
31:10 Addition von zwei Bits und Übertrag: Der Volladdierer
36:40 $n$-bit Übertragskette-Addierer
41:30 Verkürzung der Signallaufzeit durch Parallelität: Übertragsauswahl-Addierer


Abschnitt 3 - Darstellung negativer Zahlen, Addition im Zweierkomplement

Folien 28-35

Wir betrachten drei verschiedene Möglichkeiten, wie man negative Zahlen in Binärdarstellung codieren kann: Betrag und Vorzeichen, Einerkomplement und Zweierkomplement. Diese Darstellungen untersuchen wir im Hinblick auf wünschenswerte Eigenschaften, und es stellt sich heraus, daß das Zweierkomplement für das weitere Vorgehen am günstigsten ist. Grund ist vor allem die Addition, die im Zweierkomplement mit dem gleichen Rechenwerk wie für vorzeichenlose Addition durchgeführt werden kann. Eine kleine Erweiterung erlaubt auch die Subtraktion mit nur wenigen zusätzlichen Gattern.


Index

00:00 Einleitung und Überblick, wünschenswerte Eigenschaften der Darstellung
04:45 Darstellung durch Betrag und Vorzeichen, Einerkomplement und Zweierkomplement
17:30 Stellenerweiterungen in den verschiedenen Darstellungen
22:10 Addition negativer Zahlen im Einerkomplement vs. Zweierkomplement
27:20 Formale mathematische Definition des Zweierkomplements, Wertebereiche, Rechenregeln
35:00 Erweiterung des $n$-Bit Addierers zum $n$-Bit Addierer/Subtrahierer
40:15 Über- oder Unterlauf bei Addition im Zweierkomplement
44:15 Zusammenfassung und Ausblick


Vertiefung: Beweise zur Korrektheit der Addition im Zweierkomplement

Wir beweisen Behauptungen zum Zweierkomplement, die in der Vorlesung aufgestellt wurden. Der Inhalt dieser Vertiefung ist optional, ich denke aber, daß es für das Verständnis der Funktionsweise des Zweierkomplements sehr helfen kann, auch die Beweise im Detail zu studieren.


Index

00:00 Optional: Einleitung, Erinnerung: Definition des Zweierkomplementes
01:40 Optional: Beweis der Korrektheit der Stellenerweiterung
06:30 Optional: Beweis der Negationsregel im Zweierkomplement

16:20 Optional: Beweis der Korrektheit der Addition im Zweierkomplement



Ergänzung

Beim letzten Beweisteil mußte ich etwas zu früh los, um meine Tochter von der Kita abholen, aber ich ergänze hier noch die Umformung, um auf die letzte Behauptung zu kommen. Aber versuchen Sie es doch vorher selber als kleine Übung!

Die Äquivalenz sieht man folgendermaßen:
$$\begin{align}
&(c_0,c_1) = (1,1) \\
\Leftrightarrow \quad
&(1 \; a_{n-1} \; \dots \; a_0 )_2
+ (1 \; b_{n-1}
\; \dots \; b_0 )_2 \geq
( 1\;1 \; 0 \; \dots \; 0 )_2 \\
\Leftrightarrow \quad
&2\cdot 2^n + [ a_n \dots a_0 ]_{2K}
+ 2\cdot 2^n + [ b_n \dots b_0 ]_{2K} \geq 3\cdot 2^n \\
\Leftrightarrow\quad
&A+B \geq 3\cdot 2^n - 4\cdot 2^n = -2^n.
\end{align}$$
Wir haben hier die Identität $( 1\; a_{n-1} \dots a_0)_2 = 2\cdot 2^n + [ 1 \; a_{n-1} \dots a_0 ]_{2K}$ benutzt, die wir ja im Beweis schon mehrfach genutzt haben. In Worten: Wenn ich eine Ziffernfolge mit einer führenden Eins statt im Zweierkomplement in der normalen Binärdarstellung interpretiere, habe ich genau $2\cdot 2^n$ zuviel. Man beachte ausserdem, dass wir im letzten Fall sind, d.h. $a_n = b_n = 1$.


Abschnitt 4 - Multiplikation positiver Binärzahlen

Folien 37-44

In diesem Abschnitt führen wir den Standardalgorithmus für die Multiplikation von Binärzahlen ein, der dem bekannten "Grundschulalgorithmus" für die Multiplikation nachempfunden ist. Wir betrachten dafür zunächst als Erinnerung Multiplikation und Division mit Potenzen der Basis, und zeigen eine effiziente Hardwareimplementation für diese Verschiebeoperation.


Index

00:00 Einleitung, Multiplikation mit Potenzen der Basis
02:30 Division durch Potenzen der Basis, Division mit Rest (Modulo)
10:30 Hardwarerealisierung des Bit-Schiebens, logischer vs. arithmetischer Shift
17:45 Multiplikation durch Addieren von Stellenprodukten, die durch Bit-Schieben berechnet werden
25:00 Effiziente Implementation des Multiplikationsalgorithmus in Registern am Beispiel
33:30 Formales Ablaufdiagramm des Multiplikationsalgorithmus
38:10 Implementation des Multiplikationsalgorithmus in C / Java


Abschnitt 5 - Multiplikation von Binärzahlen im Zweierkomplement

Folien 44-59

Ziel dieses Abschnittes ist die Einführung des Algorithmus von Booth, mit dem man auf elegante Weise Zahlen im Zweierkomplement korrekt multiplizieren kann. Zur Motivation schauen wir uns zuerst an, auf welche Weise der Standardalgorithmus dort versagt. Sodann skizzieren wir die Idee: der erste Faktor wird nicht Bit für Bit für die Stellenprodukte durchlaufen. Stattdessen wird jede Einserkette im Faktor als Differenz von Zweierpotenzen dargestellt, so daß ein negatives Stellenprodukt für den Start, ein positives Stellenprodukt für das Ende einer Einserkette dazukommt. Wir erläutern die Funktionsweise an zahlreichen Beispielen, und fassen den Algorithmus in einem Flußdiagramm zusammen.


Index

00:00 Einleitung, funktioniert der Standardalgorithmus im Zweierkomplement?
02:45 Rettung durch korrekte Stellenerweiterung, falls nur zweiter Faktor negativ
08:30 Idee von Booths Algorithmus
12:50 Darstellung von Einserketten als Differenzen von Zweierpotenzen
17:00 Bemerkung: Allgemeinere Formel für andere Basen
19:00 Umsetzung der Idee, Booths Algorithmus an einem einfachen Beispiel
25:30 Komplitzierteres Beispiel: erster Faktor negativ, "unendliche Einserkette" am Anfang
32:05 Bit-Verschiebeoperationen für Booths Algorithmus
35:55 Flußdiagramm für Booths Algorithmus, am Beispiel erklärt
43:00 Abschließende Bemerkungen, Ausblick


Abschnitt 6 - Die arithmetisch-logische Einheit (ALU) der Hack-Architektur

Folien 60-73

Wir betrachten, wie die Arithmetisch-logische Einheit (ALU) der Hack-Architektur aufgebaut ist, und wie sie in den Hack-Prozessor eingebettet ist. Durch Steuerbits werden verschiedene nützliche Funktionen realisiert, und wir zeigen, wie diese Funktionen durch das Setzen verschiedener Kombinationen der Steuerbits realisiert werden. Schließlich sehen wir, wie in Kombination mit einem Flag für das Auslesen des Speichers alle Rechenoperationen der Hack-Maschinensprache durch die ALU realisiert werden.


Index

00:00 Einleitung, Aufgabe sowie Ein- und Ausgaben der ALU
06:02 Interpretation der Steuerbits als Selektor für eine Funktion
08:40 Hardware-Implementation der Steuerbits
13:15 Schaltplan der gesamten ALU der Hack-Architektur
19:00 Welche sinnvollen Funktionen können durch die Steuerbits realisiert werden?
25:30 Korrektheitsbeweis für die konstanten Ausgaben $0,1,-1$
32:44 Korrektheitsbeweis für die Ausgaben $x$, $\sim x$, $y$ und $\sim y$
36:25 Korrektheitsbeweis für die Ausgaben $-x$ und $-y$
41:05 Einbettung der ALU im Hack-Prozessor
45:00 Ausblick auf Maschinensprachebefehle, Memory-Flag
48:43 Bemerkung: Festkomma- und Gleitkommazahlen
54:30 Zusammenfassung und Ausblick