4 Wie rechnen "Rechner"? (1. Teil)

4.1 Binäre Addition
4.2 Das Problem der negativen Zahlen
4.3 Eine Addier- und Subtrahier-Schaltung
4.4 Das Black-Box-Prinzip

Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel


4.1 Binäre Addition


Beginnen wir unseren Streifzug durch die Rechen-Schaltungen mit der einfachsten Rechenart, nämlich der Addition. Wir beschränken uns dabei zunächst auf natürliche Zahlen, weil wir die in Form von Bytes schon in Registern speichern können.

Der Algorithmus der Addition von Binärzahlen ist durch das Verfahren der schriftlichen Addition gegeben: wir müssen also den Algorithmus der schriftlichen Addition "in Elektronik" übersetzen. Betrachten wir zunächst ein Rechenbeispiel mit zwei 4-stelligen Datenworten (wobei die niederwertigste Stelle (also das "LSB") ganz rechts steht):

  0 1 1 0
+ 0 1 0 1
  1 0 1 1

Welche elementaren Aufgaben müssen hierfür gelöst werden? Folgende Additionen können an der niederwertigsten Stelle auftreten:

0 + 0 =  0
0 + 1 =  1
1 + 0 =  1
1 + 1 = 10

Die ersten 3 Zeilen stellen kein Problem dar: solange das Ergebnis der Elementar-Addition einstellig ist, ist die Welt in Ordnung. Schwieriger wird es in der vierten Zeile: dort liegt ein zweistelliges Ergebnis vor, was einen Übertrag 1 in die nächst-höherwertige Stelle zur Folge hat. Bei den ersten drei Rechnungen hat der Übertrag hingegen stets den Wert 0. Zur Bewältigung der Addition zweier einstelliger Binärzahlen brauchen wir also eine Schaltung mit 2 Eingängen A und B sowie zwei Ausgängen S (für den Stellenwert) und Ü (für den Übertrag). Diese Schaltung muss die folgende Wahrheitswert-Tabelle haben:

A B Ü S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0




Aufgabe:

  1. Elektronische Addition von 2 Bits

    Entwerfen Sie einen Schaltplan für eine logische Schaltung, die diese Wahrheitswert-Tabelle implementiert! Betrachten Sie dazu zunächst nur die ersten 3 Spalten der Tabelle. Diese Wahrheitswert-Tabelle sollte Ihnen sehr bekannt vorkommen! Zeichnen Sie die entsprechende Schaltung auf!
    Betrachten Sie dann die ersten beiden Spalten zusammen mit der 4. Spalte. An welche Wahrheitswert-Tabelle erinnert Sie dies? Falls noch Unterschiede übrigbleiben, ergänzen Sie die Schaltung so, dass diese "ausgebügelt" werden! Dazu gibt es verschiedene Möglichkeiten.
    Lösungsvorschlag





Eine solche Schaltung nennt man einen Halbaddierer und stellt sie durch das folgende Symbol dar:


Das folgende Bild zeigt eine mögliche Implementierung eines Halbaddierers. Es gibt allerdings auch andere Implementierungen, die mit weniger Transistoren auskommen.


Und warum ist dies nur ein "Halb"-Addierer? Die zurückhaltende Bezeichnung ist darauf zurückzuführen, dass die Schaltung zwar den Übertrag auf der Ausgangsseite korrekt produzieren kann, aber keinen Eingang für einen eventuell von einer niederwertigeren Stelle gelieferten Übertrag hat. Studiert man nochmals den Algorithmus der schriftlichen Addition, dann fällt auf, dass für jede Stelle (außer der niederwertigsten) wegen des möglichen Übertrags der vorherigen Stelle die Addition von eigentlich 3(!) einstelligen Binärwerten ermöglicht werden muss.

Analog zum obigen Vorgehen könnte man nun die Wahrheitswert-Tabelle eines Volladdierers mit 3 Eingängen aufstellen und versuchen, eine entsprechende Schaltung zu entwerfen. Dies ist eine lohnende Hausaufgabe für ambitionierte Schüler. Allerdings ist sowohl die erfolgreiche Bearbeitung der Aufgabe als auch eine eventuelle Überprüfung und Korrektur der erarbeiteten Lösungen recht mühsam.

Der Ansatz, aus der Wahrheitswerttabelle die Schaltung zu entwickeln, gehört in die Kategorie der "Brute-Force-Methoden". Geschickter ist hier die Anwendung eines "Divide-and-Conquer"-Ansatzes: man zerlege das Problem in kleinere Einzelprobleme, löse diese und versuche dann, die Lösung des ursprünglichen Problems aus den Einzellösungen zusammenzusetzen. Zumindest die Zerlegung geht im vorliegenden Fall sehr einfach: statt eine Addition dreier Bits "in einem Rutsch" zu betrachten, nehmen wir zuerst mal zwei der Bits und addieren diese. Dann addieren wir zum Zwischenergebnis das dritte Eingangsbit. Eigentlich müssen wir also nur zwei Halbaddierer hinter einander schalten:


Der Ausgang S enthält offensichtlich den Stellenwert des Ergebnisses. Aber welcher der beiden Überträge Ü1 und Ü2 ist der richtige? Nun, da ein Übertrag bei der ersten oder auch bei der zweiten Addition auftreten könnte, müssen irgendwie beide Überträge berücksichtigt werden.




Aufgabe:

  1. Vom Halbaddierer zum Volladdierer

    Überlegen Sie sich, wie in dem vorstehenden Schaltungsfragment der Übertrag Ü aus den beiden internen Überträgen Ü1 und Ü2 gebildet werden muss. Ergänzen Sie die Schaltung entsprechend!
    Lösungsvorschlag




Die komplette Volladdierer-Schaltung wird mit dem folgenden Symbol abgekürzt:


Um nun auch mehrstellige Binärzahlen addieren zu können, müssen wir für jede belegte Binärstelle einen Volladdierer einsetzen. Lediglich für die niederwertigste Stelle genügt ein Halbaddierer. Eine 4-Bit-Addier-Schaltung, die z.B. unser einführendes Rechenbeispiel bewältigt, müsste also die beiden binären Zahlen "A3A2A1A0" und "B3B2B1B0" addieren und die Summe in "ÜS3S2S1S0" ausgeben. Die folgende Abbildung zeigt links das Gatterschaltbild eines solchen 4-Bit-Addierers und rechts eine entsprechende Simulation eines solchen Rechenwerks:

     

Achtung: die Addition zweier 4-Bit-Zahlen kann eine 5-Bit-Zahl ergeben! Für das Abspeichern der vollständigen Summe ist also eine größere Wortbreite nötig als für die einzelnen Summanden. Dieses Problem taucht bei sämtlichen numerischen Datentypen auf und muss entsprechend in allen Berechnungsalgorithmen berücksichtigt werden!


Aufgabe:

  1. Der 4-Bit-Addierer

    a) Spielen Sie im obigen Simulationsfenster die Rechnung "6+5=11" durch. Übersetzen Sie dazu die dezimale Aufgabenstellung in binäre Kodierung, und geben Sie diese Eingangsdaten in die obige Schaltung ein. Wandeln Sie dann das binäre Ergebnis wieder in eine Dezimalzahl. Stimmt's?

    b) Versuchen Sie, ein möglichst scharfes Kriterium für den Rechenbereich zu finden, in dem die obige Addier-Schaltung korrekte Ergebnisse mit höchstens 4 Binärstellen liefert.
    Lösungsvorschlag








4.2 Das Problem der negativen Zahlen


Bisher haben wir die verwendeten 4-Bit-Worte bei der Interpretation als Zahlen stets als natürliche Zahlen angesehen. Gemäß der folgenden Tabelle lässt sich also mit einem solchen 4-Bit-Wort ein Zahlenbereich von 0..15 beschreiben:

Bits 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Zahl 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Addiert man zu 1111B = 15 nun nochmals eine 1, dann erhält man 10000B = 16, was aber 5 Bits zur Speicherung braucht und daher nicht mehr in ein 4-Bit-Wort passt. Schreibt man dieses Ergebnis dann eben "soweit es geht" stellengerecht in einen 4-Bit-Speicher, dann erhält man als Resultat dieser Addition das Bitmuster "0000". Mithin erscheint der Zahlenraum zyklisch geschlossen:


In einer solchen zyklischen Anordnung ist die Interpretation der Bitmuster als rein positive ganze Zahlen nicht mehr zwingend. Man könnte auch eine Hälfte der Zahlen als positive und die andere Hälfte als negative Zahlen ansehen. Da in der Menge der ganzen Zahlen die 0 den Vorgänger -1 hat, müsste dieser Zahl das Bitmuster "1111" entsprechen, der -2 das Muster "1110". Üblicherweise wird das höchstwertige Bit als Vorzeichen-Indikator genommen: alle Bitmuster der Form "1xxx" werden als negativ interpretiert, alle der Form "0xxx" als positiv. Die sich damit ergebende Zuordnung ist im folgenden Diagramm durch den zusätzlichen inneren Zahlenkreis dargestellt:


So lässt sich der Zahlenraum von -8 bis +7 mit 4-Bit-Worten darstellen. Man nennt die hier gewählte Darstellung der negativen Zahlen die Zweier-Komplement-Darstellung.

Was uns noch fehlt, ist ein Algorithmus, mit dem wir aus dem Bitmuster für eine Zahl a > 0 das Bitmuster der Zahl (-a) erhalten können. Schauen wir uns dazu mal ein Beispiel an:

Die Zahl 3 hat das Bitmuster "0011". Wenn wir nun dieses Muster bitweise invertieren (also jede 0 durch eine 1 ersetzen und jede 1 durch eine 0), dann erhalten wir das Muster "1100". Ein Blick in die obige Tabelle zeigt, dass wir dicht neben dem richtigen Ergebnis landen, nämlich bei (-4). Wenn wir nun zu dieser Zahl noch eine 1 addieren, dann erhalten wir das korrekte Bitmuster "1101" für (-3). Allgemein gilt der folgende Algorithmus zur Bildung des Zweierkomplements einer Zahl a:

Man invertiere das Bitmuster von a und addiere zum Ergebnis eine 1.
Wenn wir das bitweise Inverse einer Zahl a mit abi bezeichnen und das Zweier-Komplement von a mit a*, dann lässt sich die obige Regel als Formel schreiben:

a* = abi + 1
Um den Nutzen der Zweierkomplement-Darstellung für negative Zahlen einzusehen, klären wir zunächst, wie man die Bildung des Zweierkomplements einer Zahl a mathematisch beschreiben kann. Liegt a in einer Darstellung mit N Bits vor, dann kann man das bitweise Inverse von a, also abi, erhalten, indem man a von einer Binärzahl abzieht, die aus genau N Einsen besteht. Im obigen konkreten Beispiel wäre also zu rechnen: "1111" - "0011" = "1100", wobei die Differenz in Zahlen geschrieben bedeutet: (24 1) 3. Die Zweierkomplement-Darstellung erhält man nun, indem man zu diesem Term noch eine 1 addiert: (24 1) 3 + 1 = 24 3. Allgemein ergibt sich für das Zweier-Komplement a* einer positiven Zahl a in N-stelliger Binärdarstellung der Term

a* = 2N a.


Aufgabe:

  1. Zwischendurch mal etwas Mathematik...

    Machen Sie sich klar, dass die Zweier-Komplement-Bildung involutorisch ist, dass also das Zweierkomplement vom Zweierkomplement von a stets wieder a liefert!
    Sie haben in der Unter- und Mittelstufe schon einige geometrischen Abbildungen kennengelernt. Welche davon würden Sie als "involutorisch" bezeichnen?
    Lösungsvorschlag




Damit lässt sich eine Subtraktion zweier positiver Zahlen stets folgendermaßen realisieren:
b a = b a + 2N 2N = b + 2N a 2N = b + (2N a) 2N = b + a* 2N
Zur Ausführung der Subtraktion b - a kann also ein normales Addierwerk verwendet werden, wenn man an dessen Eingänge den Minuenden b und die Zweierkomplement-Darstellung a* des Subtrahenden anlegt und vom Ergebnis schließlich noch 2N abzieht. Die Subtraktion von 2N schließlich können wir einfach realisieren, indem wir ein eventuell gesetztes Übertrags-Bit in der höchstwertigen Stelle des Ergebnisses ignorieren: da dieses zusätzliche Bit ohnehin beim Abspeichern in einem N-Bit-Datenwort keinen Platz hat, lässt man es einfach unberücksichtigt.

Das Problem der Subtraktion wird also vollständig durch die Zweier-Komplement-Kodierung der negativen ganzen Zahlen gelöst, und zwar gemäß der Umformung:
b a = b + (-a)
die wir ja aus der Mathematik kennen. Für uns sieht diese Gleichung nun (bei Beschränkung auf N Binärstellen!) so aus:
b a = b + a*.
Wie aber erhält man aus dem Bitmuster einer Zahl a das Bitmuster der zugehörigen Zweier-Komplements a*? Dieses Problem haben wir bisher noch nicht wirklich gelöst: oben wird a* als Differenz dargestellt wird, nämlich a* = 2N - a. Also brauchen wir zur Berechnung von a* eine Subtrahier-Maschine, was schwierig wird, weil unser Addierer nur dann als Subtrahierer einsetzbar ist, wenn wir a* schon berechnen können!

Als Alternative bietet sich der oben schon angegebene Algorithmus für die Transformation von a in a* an, nämlich: "Man invertiere alle Bits von a und addiere zum Ergebnis eine 1!" Aber wie invertiert man die einzelnen Bits von a? Hier hilft uns das XOR-Gatter weiter:

E1 E2  XOR 
 0  0  0
 0  1  1
 1  0  1
 1  1  0

Für E1 = 0 leitet das XOR-Gatter das Signal von E2 ungeändert zum Ausgang weiter. Für E1 = 1 inveriert es das an E2 anliegende Datum. Wenn wir also einen Bitwert an E2 mit einer "1" XOR-verknüpfen, dann erhalten wir den invertierten Bitwert. Die folgende Schaltung erledigt diese Arbeit für eine 4-Bit-Zahl b und führt darüberhinaus auch gleich noch die anstehende Addition von 1 zum vollständigen Zweier-Komplement b* aus:

Die Implementierung ist sehr sparsam: für die Addition der 1 genügt eine 4er-Serie von Halbaddierern. Der unterste Input-Schalter wählt die Betriebsart: steht er auf "0", dann wird die links eingestellte Zahl b unverändert in die Ausgänge auf der rechten Seite weitergeleitet; steht er jedoch auf "1", dann erscheint rechts das Zweier-Komplement b* der links eingestellten Zahl b.




4.3 Eine Addier- und Subtrahier-Schaltung


Die obige Schaltung kann man leicht zu einer universellen Addier- und Subtrahier-Schaltung erweitern. Dazu muss man nur noch jeden Halbaddierer durch einen Volladdierer ersetzen und die zusätzlichen Eingänge zur Eingabe einer zweiten Zahl a benutzen. Dann erhält man eine Schaltung, die je nach Stellung des Betriebsarten-Schalters sowohl die Summe a + b als auch die Differenz a - b berechnen kann:




Aufgabe:

  1. Praxistest für unsere 4-Bit-Strichrechnung

    Überzeugen Sie sich davon, dass die folgenden Subtraktionsaufgaben von dem obigen 4-Bit-Addier/Subtrahier-Werk korrekt ausgeführt werden, wenn man alle negativen Zahlen in Zweier-Komplement-Darstellung eingibt:
    a) 5 - 2    b) 2 - 5    c) (-5)-(-4)    d) (-5)-(-7)

  2. ....bis an die Grenzen!

    Versuchen Sie, die Aufgaben (-5)-3  und  (-5)-4  mit dem 4-Bit-Addier/Subtrahier-Werk zu berechnen. Welche Schwierigkeiten ergeben sich dabei?
    Lösungsvorschlag




Wie die Beispiele aus der letzten Aufgabe zeigen, sind damit noch nicht alle Probleme der binären Addition bzw. Subtraktion gelöst. Das berechnete Ergebnis EB stimmt nämlich nur dann mit dem korrekten Ergebnis E überein, wenn letzteres(!) innerhalb des zulässigen Zahlbereichs (hier: [-8;+7]) liegt. Das berechnete Ergebnis EB liegt immer in diesem Zahlbereich, was ja schon durch die Hardware des Addierers gesichert ist! Für unsere 4-Bit-Zahlen ist z.B. schon die Addition 6 + 3 eine unüberwindliche Hürde, denn sie liefert Ü = 0 und das Bitmuster S = 1001, und damit EB = (-7)! Solch ein "Überlauf" sollte durch geeignete Maßnahmen erkannt werden, so dass dann die Software zumindest melden kann, dass die Berechnung fehlgeschlagen ist. Allerdings ist die Erkennung nicht einfach zu implementieren. Das hier angegebene Beispiel lehrt schon, dass die Überwachung des Ü-Ausgangs der Rechenschaltung keinesfalls genügt, und dass "Übertrag" und "Überlauf" zwei total verschiedene Dinge sind!

Das Überlaufproblem ist ein grundsätzliches Problem der Computerarithmetik, weil alle numerischen Datentypen fester Größe eben stets nur endlich viele verschiedene Werte annehmen können. Mithin gibt es stets eine größte und eine kleinste darstellbare Zahl. Überschreiten die korrekten Ergebnisse einer Aufgabe die dadurch gesetzten Grenzen, dann liefern die Berechnungsalgorithmen sinnlose Werte. Um dies zu vermeiden, kann man sich numerischer Datentypen bedienen, die nicht mit einer festen Stellenzahl arbeiten. So gibt es z.B. in JAVA zur Darstellung großer Zahlen die dynamischen Datentypen BigInteger und BigDezimal, welche das Rechnen mit beliebig vielen Stellen erlauben. Der Umgang damit ist aber nicht ganz einfach, und die Performance solcher Programme kann problematisch sein. So wird man sich in den meisten Fällen doch der endlichen Standard-Datentypen bedienen.

Viele Compiler verwenden aus Performance-Gründen zumindest bei der Integer-Arithmetik keinerlei Überlauferkennung (z.B. die Pascal-Compiler der Delphi-Serie). So bleibt es dem Programmierer der Software anheimgestellt, seine Programme selbst gegen Überläufe zu sichern. Lässt man dabei nicht die gebotene Sorgfalt walten, kann das durchaus schlimme Folgen haben. Ein Überlauf war z.B. 1996 der Grund dafür, dass die Ariane5-Rakete auf ihrem Jungfernflug abstürzte. Im Navigationssystem der Rakete wurde vor dem Start eine 64-Bit-Float-Zahl gerundet und der gerundete Wert in eine 16-Bit-Integer-Zahl geschrieben. Leider ergab sich beim Runden ein Wert, der mehr als 16 Bits groß war, weshalb einige der höherwertigen Bits beim Speichern verloren gingen. Der falsche gespeicherte Wert führte dann bei weiteren Berechnungen zum Absturz des Navigationssystems der Rakete. Der damit orientierungslos gewordene Hauptcomputer der Rakete änderte die Flugbahn danach eigenmächtig so stark ab, dass die Bodenstation die Selbstzerstörung der Rakete einleiten musste!





4.4 Das Black-Box-Prinzip


Obwohl unsere Addier- und Subtrahier-Schaltung noch einige Schwächen hat und wir uns noch nicht blind auf die gelieferten Ergebnisse verlassen sollten, wollen wir den bisher erreichten Stand der Entwicklung in einem eigenen "Addier- und Subtrahier-Baustein" zusammenfassen. Damit wird die weitere Verwendung unserer Ergebnisse in komplizierteren Schaltungen deutlich vereinfacht. Wir nutzen diese Gelegenheit aber auch gleich noch dazu, den Zahlbereich unserer "Add-Sub-Maschine" zu vergrößern: statt einer Reihe von 4 nebeneinander arbeitenden Volladdierer könnten wir auch 8 Volladdierer verwenden und damit den gesamten Rechenbereich eines Bytes abdecken: interpretieren wird das höchstwertige Bit als Vorzeichenbit, dann ergibt sich so ein Bereich für die möglichen Summanden von [-128..127].

Entsprechend brauchen wir dann 2 Daten-Eingänge a und b, und einen Daten-Ausgang c, wobei a, b und c aber nun jeweils "8 Bit breit sind", d.h.: aus je 8 Datenleitungen bestehen. Zusätzlich zu den 2 * 8 Daten-Eingängen brauchen wir auch noch einen "Modus"-Eingang "M", um zwischen Addition und Subtraktion umzuschalten:
Es ist üblich, solche Funktions-Einheiten als flache Rechtecke darzustellen, wobei die Eingänge oben und die Ausgänge unten sind. Werden nun mehrere solche Bausteine miteinander kombiniert, dann erhält man auf natürlichem Wege einen Signalfluss von oben nach unten - wie wenn man eine Textseite in einem Buch lesen würde. Die abgekürzte (bzw. "integrierte") Darstellung unserer Addier- und Subtrahier-Schaltung wird also in Zukunft so aussehen:



Wir haben inzwischen schon so viele "Integrations-Stufen" hinter uns gebracht, dass wir das "Einpacken einer Schaltung in eine Black Box" als ein allgemeines Prinzip erkennen können:

Diese "Black-Box-Methode" ist das Erfolgsrezept der Elektronik: wenn man eine Funktionalität in einer Schaltung implementiert hat, dann beschreibe man nur noch die Schnittstellen dieser Schaltung (also: ihr Input-Output-Verhalten) - danach schließe man die Black Box zu! Braucht ein Anwender die in dieser Box implementierte Funktionalität, dann verwendet er die Black Box einfach, ohne sich um ihren Inhalt (d.h.: die Details der Implementierung!) zu kümmern - er muss sich nur noch an der Input-Output-Beschreibung orientieren!

Die großen Halbleiterfirmen haben in den letzten Jahrzehnten Millionen "integrierter Schaltungen" entwickelt und die Spezifikationen dieser "ICs" ("I"ntegrated "C"ircuits) in entsprechenden Datenblättern veröffentlicht. Wenn ein Anwender die Datenblätter (mit den Input-Output-Beschreibungen!) lesen kann, dann kann er auch die zugehörigen ICs für seine eigenen Zwecke einsetzen - obwohl er in den meisten Fällen kaum fähig wäre, die Innenschaltung dieser ICs selbst herzustellen!

Unabdingbare Voraussetzung für das Funktionieren dieses Verfahrens ist es aber, dass die Dokumentation der Schnittstellen der verwendeten Black Boxes fehlerfrei und verständlich ist, damit der Anwender ihr auch alle benötigten Informationen entnehmen kann!






Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel