Wie Rechner rechnen – Teil 2

Das letzte Mal haben wir geklärt, wie logische Operationen auf einzelnen Bits durch einfache Bauteile umgesetzt werden können. Diesmal soll es darum gehen, wie man mit Hilfe dieser Bauelemente nun ganz konkret rechnen kann.

Zum Einstieg und zur Erinnerung noch einmal die Wertetabelle für die logischen Operationen AND (UND), OR (ODER) und XOR (EXKLUSIV-ODER) mit den zugehörigen Schaltbildern; die Wertetabellen sind diesmal in einer leicht anderen Form festgehalten (der Grund dafür erschließt sich beim Weiterlesen):

Die einfachste Art des binären Rechnens ist die Addition zweier einzelner Bits. Erinnern wir uns, wie das Rechnen im Binären war (auf den Index “₂” verzichte ich im Folgenden aus Gründen der Übersichtlichkeit):

Dass Ergebnis der Rechnungen habe ich mit Absicht jeweils aus zwei Ziffern bestehend geschrieben. Der Grund ist, dass auf diese Art das Ergebnis optisch gut ersichtlich in zwei Teile zerlegt werden kann: den Übertrag C (von englisch carry) in der vorderen Ziffer und die Summe S in der hinteren Ziffer. Das kennt man ja noch von der schriftlichen Addition von Dezimalzahlen; die Gleichung 8+6 zum Beispiel hat das Ergebnis 14, wobei die 1 der Übertrag und die 4 die Summe ist.

Die Addition zweier Bits lässt sich somit wiederum als Wertetabelle aufschreiben (X und Y sind die jeweiligen Eingaben):

Aufmerksame Leser werden an der Tabelle sicher schon erkennen, wohin das führen wird. Die beiden Spalten für C und S lassen sich nämlich wunderbar mit den logischen Operationen erklären, wie ein Vergleich mit der ersten Abbildung zeigt – AND für C und XOR für S. Kombiniert man also ein AND-Gatter mit einem XOR-Gatter in ein Bauelement, so erhält man einen sogenannten Halbaddierer – ein Bauelement, welches 2 Bits als Eingänge besitzt, diese miteinander addiert und die Summe sowie den Übertrag der Rechnung an den Ausgängen wieder ausgibt.

Das Schaltbild dazu folgt hier. Diejenigen unter den Lesern, die Flash aktiviert haben (und – unter Umständen – diesen Artikel nicht im Feed-Reader, sondern direkt auf Scienceblogs lesen), sollten statt eines langweiligen Bildes einen interaktiven Schaltplan sehen, in welchem sie die Funktionsweise des Halbaddierers selber ausprobieren können (was ich sehr empfehle – es macht Spaß). Alle anderen müssen mit einem langweiligen Bild vorlieb nehmen*:

Damit sind wir schon auf dem halben Weg zum richtigen Addieren – was jetzt noch fehlt, ist die Möglichkeit, auch längere Binärzahlen miteinander addieren zu können. Wir erinnern uns: die schriftliche Addition findet immer stellenweise statt, wobei lediglich der Übertrag von einer Stelle an die nächste (also von rechts nach links) durchgereicht wird. Um den Halbaddierer also voll-additionsfähig (das Wortspiel muss sein) zu machen, also um einen Volladdierer zu erhalten, muss neben den Eingängen für die beiden zu addierenden Bits zusätzlich ein Eingang für den Übertrag der vorherigen Rechnung her. Es findet dann im Grunde eine Addition von 3 Bits statt. Damit ergibt sich die folgende Wertetabelle für einen Volladdierer:

Diese Berechnung kann durchgeführt werden, indem zwei Halbaddierer mit einem OR-Gatter verbunden werden, wie der folgende (wieder interaktive) Schaltplan zeigt (HA steht für Halbaddierer):

Damit haben wir jetzt alle Zutaten zusammen, um unser erstes Addierwerk zu bauen. Ein Addierwerk ist ein Bauelement, in welches zwei Binärzahlen mit jeweils der Länge n eingegeben werden und welches daraus die Summe der beiden Zahlen bildet. Addierwerke können auf verschiedene Art aufgebaut werden; grob sind dabei Paralleladdierer und Serienaddierer unterscheidbar, wobei es in jeder Gruppe weitere Unterteilungen gibt.

Die einfachste Form ist ein Paralleladdierer, welcher so arbeitet, wie wir es von der schriftlichen Addition kennen, sprich, welcher stellenweise die Summe zweier Ziffern berechnet und den eventuell entstehenden Übertrag an die nächste Ziffernaddition weitergibt. Der “parallele” Aspekt bezieht sich hier lediglich auf die Ziffern der beiden Eingabewerte, nicht auf den Übertrag. Ein solches Addierwerk nennt man passenderweise Ripple-Carry-Addierer und baut es einfach durch die Hintereinanderschaltung mehrerer Volladdierer auf. Jeder Volladdierer erhält als Eingabe die Bit-Ziffer der beiden Eingabezahlen entsprechend seiner Position und den Übertrag des vorgeschalteten Addierers (demzufolge kann der erste Volladdierer durch einen Halbaddierer ersetzt werden, da hier noch kein Übertrag berücksichtigt werden muss). Auch hierzu gibt es einen (interaktiven) Schaltplan, und zwar für einen 4-Bit-Addierer, also einen Addierer, der Bitketten der Länge 4 miteinander addieren kann:

Einfache Ripple-Carry-Addierer haben den Vorteil, dass sie ziemlich einfach aufgebaut werden können, aber auch den Nachteil, dass eine Berechnung relativ lange dauert, da ja der Übertrag von Position zu Position weitergereicht werden muss. Im Laufe der Zeit entstanden daher verschiedene verbesserte Paralleladdierer, welche dieses Problem umgehen. Für das Verständnis der Funktionsweise von Computern sind sie nicht weiter wichtig, daher werde ich sie auch nicht erklären – außer, es besteht der explizite Wunsch, dann schiebe ich noch einen Artikel nach.