Lange hat es gedauert, hier nun aber endlich der fünfte Teil der “Wie Rechner rechnen”-Serie. Bald haben wir alles Wissen zusammen, um die Funktionsweise eines (einfachen) Prozessors verstehen zu können, aber einiges fehlt uns noch. Da wäre zum Beispiel noch die Durchführung auch anderer Rechenarten als der Addition sowie eine Möglichkeit, die durchzuführende Rechenoperation irgendwie bestimmen zu können. Konkret wäre der Aufbau eines Rechenwerkes zu klären. Und genau darum soll es heute gehen.
[Ein Hinweis vorab: zumindest in meinem RSS-Reader sieht dieser Beitrag nicht sonderlich gut aus – das Lesen direkt auf Scienceblogs scheint daher diesmal angeraten.]
Vorher schiebe ich aber noch schnell, wie im letzten und einem vorherigen Artikel versprochen, die Erklärung einer alternativen Umsetzung eines Addierers, nämlich des Serienaddierers, ein. Zum Verständnis von Rechenwerken ist er zwar nicht unbedingt erforderlich, aber er gibt einen ersten Hinweis darauf, auf wie viele unterschiedliche Arten ein Problem gelöst werden kann. Hinter einem Serienaddierer steckt auch keine große Magie: er kann mit Hilfe von zwei Schieberegistern, einem Volladdierer und einem zusätzlichen D-Flipflop aufgebaut werden. Die folgende Abbildung zeigt den einfachsten Aufbau; auf Grund der Größe der Schaltung musste ich die interaktive Anwendung leider auslagern – bitte hier oder auf das Bild klicken (Erklärung zur Benutzung: mit 4 Klicks auf den C-Eingang werden die beiden zu addierenden Zahlen geladen und mit 4 weiteren Klicks wird das Ergebnis berechnet):
Relativ einfach also. Die zu addierenden Zahlen werden einfach in die Eingangs-Schieberegister eingegeben und dann Bit für Bit an den Volladdierer verfüttert. Der schiebt das berechnete Ergebnis ebenfalls Bit für Bit in das Ausgabe-Schieberegister und speichert zusätzlich noch den berechneten Übertrag für den nächsten Takt im D-Flipflop. Eine Variation des Serienadddierers besitzt übrigens kein separates Ausgabe-Register, sondern schiebt seine Ergebnisse einfach in das erste Eingabe-Register hinein – dieses bezeichnet man dann als sogenannten Akkumulator, da es die Ergebnisse mehrerer aufeinanderfolgender Rechnungen akkumuliert, also sammelt. Der Serienaddierer hat aber einen klar erkennbaren Nachteil: er braucht für die Berechnung immer so viele Takte, wie Bits vorhanden sind. Das macht ihn ziemlich langsam, was zur Entwicklung verbesserter Versionen, wie etwa dem Von-Neumann-Addierwerk geführt hat (wer sich dafür interessiert, möge sich bitte selber informieren – die Behandlung würde hier zu weit führen).
So viel zum Thema addieren – kommen wir zum Subtrahieren. Bevor wir hier allerdings das eigentliche Rechnen anschauen können, muss noch etwas anderes erklärt werden.
Die Subtraktion im klassisch mathematischen Sinne bringt es mit sich, dass auch negative Zahlen als Ergebnis entstehen können (wenn man nämlich eine größere Zahl von einer kleineren abzieht). Es wird also eine Möglichkeit benötigt, im Computer auch negative Zahlen darstellen zu können. In der Mathematik ist das kein Problem, da hier einer Binärzahl einfach ein Minus vorangestellt werden kann, also zum Beispiel -1012 für -510. Im Computer funktioniert das natürlich nicht, da hier ja überhaupt nur zwei Symbole – eben die 0 und die 1 – zur Verfügung stehen. Abhilfe schafft hier die sogenannte Zweierkomplement-Operation.
Für die Nutzung des Zweierkomplements wird eine bekannte maximale Länge der Bitkette – die sogenannte Bitbreite – benötigt. Übliche Werte sind hier Längen wie 8 Bit, 16 Bit, 32 Bit und neuerdings auch 64 Bit. Da Computer ohnehin in der Regel mit fester Bitbreite rechnen, ergibt sich hier also kein Nachteil. Die Darstellung einer negativen Zahl ergibt sich, indem das Zweierkomplement der positiven Entsprechung dieser Zahl gebildet wird; dazu wird die Bitkette der positiven Zahl invertiert (sprich, jede 0 mit einer 1 ausgewechselt und umgekehrt; man spricht auch von Negation und stellt sie mit einem durchgezogenen Strich über der Zahl dar) und anschließend noch eine binäre 1 draufaddiert.
Klingt kompliziert? Hier ein kleines Beispiel zur Erklärung. Bleiben wir bei der Darstellung der 4 im 4-Bit-System:
Die Invertierung dieser Bitkette sieht so aus:
Noch eins draufaddiert ergibt dann das folgende Ergebnis (der kleine Strich über der 2 bei der Stellensystemanzeige soll nur verdeutlichen, dass wir es hier mit einem Zweierkomplement zu tun haben):
Die -4 wird also bei einer Bitbreite von 4 durch die Bitkette 1100 repräsentiert. Das erste Bit wird hier also als Vorzeichenbit betrachtet; ist es 0, handelt es sich um eine positive Zahl; ist es 1, repräsentiert die Bitkette eine negative Zahl. Der große Vorteil der Zweierkomplement-Darstellung ist – neben dem Umstand, dass sie allein über 0en und 1en umsetzbar ist – die Möglichkeit, eine Subtraktion ohne zusätzliche Logik durchführen zu können, da sie einfach auf die Addition zurückgeführt wird. Statt “6 – 4” wird also “6 + (-4)” berechnet. Wieder am Beispiel gezeigt sieht das dann so aus (die 1 in Klammern in der Rechnung ist der Übertrag der Addition, welcher in einem 4-Bit-System verfällt):
| 610 – 410 | = 610 + (-4)10 |
| = 01102 + 11002 | |
| = (1) 00102 | |
| = 210 |
Um also ein Addierwerk in ein Subtrahierwerk umzuwandeln, reicht es, das Zweierkomplement des zweiten Summanden zu bilden; ein einfaches Inverter-Gatter (wir erinnern uns) für jedes Eingabebit schafft hier Abhilfe; wird zusätzlich dem Werk ein Carry-in (wer sich nicht erinnert, muss noch einmal bei der Erklärung des Volladdierers nachschauen) von 1 mitgegeben, ist das Zweierkomplement perfekt. Jetzt wäre es natürlich Platzverschwendung, für Addition und Subtraktion zwei getrennte Schaltungen anzulegen, also kombiniert man beides in eine einzige, wobei über einen Steuereingang geregelt wird, ob denn nun addiert oder subtrahiert werden soll. Das folgende Schaltbild zeigt ein einfaches 4-Bit-Addier-/Subtrahierwerk; statt der Inverter für den zweiten Summanden zur Bildung des Zweierkomplements werden hier Exklusiv-Oder-Gatter (die Gatter mit dem “=1” drin) verwendet, um das Komplement nur abhängig vom Steuereingang zu berechnen:
Wer etwas mit dem Rechenwerk herumspielt, wird schnell merken, dass die Ergebnisse scheinbar manchmal nicht mehr stimmen, wenn die höchstwertigen Bits (also A0 und B0) involviert sind. Das Rechenwerk macht aber alles korrekt (hoffe ich zumindest); die höchstwertigen Bits sind auf Grund der Zweierkomplement-Darstellung ja für das Vorzeichen reserviert. Wir haben also keine Möglichkeit mehr, zum Beispiel eine 15 mit 4 Bit darzustellen. Schlechter stehen wir aber nicht da, da wir ja nun die Möglichkeit haben, dafür zum Beispiel die -8 auszudrücken; der Wertebereich verschiebt sich also lediglich von [0,15] auf [-8,7].
Damit haben wir unser erstes, einfachstes Rechenwerk fertig (genau genommen eine sogenannte arithmetisch-logische Einheit oder ALU)! Um daraus ein produktionsreifes Rechenwerk zu machen, müsste man noch weitere Rechenarten und Operationen hinzufügen – ich verzichte an dieser Stelle allerdings darauf, da es im Prinzip genau so wie bei der Addition und Subtraktion funktioniert und nur etwas komplexer in der Darstellung und Erklärung ist. Wer Interesse an der Thematik hat, findet dazu im Internet einiges an Literatur; hier geht es in erster Linie darum, die Magie eines Prozessors etwas zu beleuchten und das lässt sich auch mit Addition und Subtraktion bewerkstelligen (wirklich – viel komplizierter wird es nicht mehr). Ein komplettes Rechenwerk besitzt ein paar Eingänge für die Daten (Summanden, Faktoren usw.) sowie Eingänge für das Steuersignal, das aus einer Bitkette besteht und angibt, welche Operation auf den Eingabedaten durchgeführt werden soll.
Eigentlich ganz einfach, oder? Jetzt stellt sich jedoch noch eine Frage: woher kommt das Steuersignal? Aber das werden wir beim nächsten mal sehen (was diesmal hoffentlich nicht so lange dauert).
Kommentare (4)