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):

i-e99b371b58e72953ab8ec7250e8813b8-SerialAdder.png

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:

410 = 01002

Die Invertierung dieser Bitkette sieht so aus:

01002 = 10112

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):

10112 + 12 = 11002 = -410

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)

  1. #1 Engywuck
    August 15, 2011

    Zweierkomplement habe ich damals erst kapiert, als mir klar wurde, was bei “0000” – “0001” passiert.

    Beim klassischen “Zehnersystem” wird ja (schreibts mal auf! :D) bei z.B. “100 – 24” von rechts nach links subtrahiert. Also “0 minus 4” – hmmm, geht nicht, aber wenn ich “10 minus 4” rechne gehts, muss nur nachher vom nächsthöheren eins zusätzlich abziehen, also rechte Ziffer ist ne “6”. Zweite Ziffer: “0 minus 2”, aber da war ja vorher noch die 1, also “0 minus 3”, Mist, selbes Problem, also “10 minus 3” und beim nächsten eins zusätzlich abziehen, bisher also “76”. Bei der dritten Stelle “1 minus 0 minus 1 von vorhin”, bleibt 0.

    Was passiert nun bei binär “0000 – 0001”? Klar, rechte Stelle: “0 – 1” geht nicht, aber “10 – 1 = 1” geht, also rechte Stelle eine “1”. Zweite Stelle: “0 – 0 – 1” (letzte -1 von vorhin), selbes Problem, also nun Ergebnis “11”. Mit der dritten Stelle dasselbe, ebenso bei der vierten, also nun “1111” – und ein zusätzliches Abziehen von der fünften Stelle. oh, die haben wir gar nicht? toll, also lassen wir das untern Tisch fallen.

    Dass ein Rechner natürlich einfacher “-2 ist 0010 invertiert + 0001, also 1110” rechnet ist klar 😀

    Übrigens hast du “unterschlagen”, warum man nicht einfach das am weitesten links stehende Bit zum Vorzeichen ernannt hat (in heutigen Rechnern): damit hätte man positive wie negative Null (1000 = -0, 0000 = +0)… auch nicht unbedingt besser, zudem würde das Rechenwerk komplexer (naive Addition geht dann nicht: 1001 (-1) + 0001 (+1) = 1010 (-2). oops.). Das mit dem Zweierkomplement verwandte Einerkomplement (nur invertieren) hätte dasselbe Problem mit der negativen Null (und das Rechenwerk wird minimal komplexer als beim Zweierkomplement). Zudem gewinnt man durch das Zweierkomplement einen Wert im Wertebereich – 4-Bit-Zweierkomplement geht von “1000” (-8) bis “0100” (+7), “höchstes Bit als Vorzeichen” (wie Einerkomplement) dagegen von “1111” (-7) bis 0111 (+7). Bei 64 Bit macht das zwar nicht mehr soooo viel aus, aber bei den früher verwendeten niedrigen Bitzahlen….

    Interessanterweise verwenden Gleitkommazahlen üblicherweise dann doch wieder ein Vorzeichenbit. Scheint da dann einfacher zu implementieren zu sein als die entsprechende Komplementdarstellung.

  2. #2 Marcus Frenkel
    August 15, 2011

    @Engywuck
    Schöne Erklärung mit dem Dezimalsystem. Die kannte ich noch gar nicht. 😉

    Warum die Gleitkommazahlen das ordinäre Vorzeichenbit und nicht das Zweierkomplement benutzen, liegt meiner Meinung nach genau an dem Vorteil des Zweierkomplements, dass sich die Subtraktion ohne zusätzliche Logik auf die Addition abbilden lässt – und die Addition lässt sich ziemlich schnell durchführen (die nicht doppelte 0 halte ich gar nicht einmal für den größten Vorteil – aber das ist nur eine Vermutung). Da Berechnungen mit Gleitkommazahlen ja nicht ganz so einfach funktionieren, bringt hier vermutlich das Zweierkomplement gar nichts – immerhin möchte man ja nicht, dass ein Bit durch die Addition von 1 am Ende von der Mantisse in den Exponenten rutscht. Das wäre kontraproduktiv. 😉

  3. #3 CHP
    August 15, 2011

    Passend zu diese Artikelserie möchte ich auf die Software Logisim: https://ozark.hendrix.edu/~burch/logisim/ (GPL) aufmerksam machen.

    Damit kann man einfache und komplexe logische Schaltungen simulieren, ohne sich mit den elektrotechnischen Grundlagen herumschlagen zu müssen. Das ist genau das richtige Werkzeug bzw. Spielzeug um diese Artikel nachzuvollziehen.

  4. #4 Engywuck
    August 18, 2011

    Dezimalsystem. Die kannte ich noch gar nicht.

    Typisch Informatiker. kennen nur dual 😉

    @CHP: leider etwas high-level, z.B. kennt es nur p-type Transistoren und darüber dann schon komplexe Gatter… Trotzdem ganz nett.