Zahlensysteme
Die allgemeine Darstellung für den Wert einer Zahl in einem beliebigen
Zahlensystem mit der Basis , den Ziffern und den Stellenwerten
kann durch folgende Gleichung ausgedrückt werden:
(1) |
11111000101 | im Dualsystem |
3705 | im Oktalsystem |
1989 | im Dezimalsystem |
7C5 | im Hexadezimalsystem |
Dualsystem
Ein Digitalrechner kann nur mit den Ziffern 0
und 1 rechnen. Dieses wird dadurch realisiert, daß eine elektrische
Größe wie Spannung oder Magnetfeld entweder an oder aus ist. Dieses
führt zwar zu einer ungeheuren Verschwendung von Schaltelementen, ergibt
aber andererseits eine außerordentliche hohe Rechengenauigkeit. An oder aus
heißt hierbei einfach, daß die elektrische Größe oberhalb oder unterhalb
einer bestimmten Schwelle liegen muß. Wie weit sie oberhalb oder unterhalb
liegt, ist belanglos. Systeme, die nur zwei stabile Betriebszustände
einnehmen können, werden als Binärsysteme (zweiwertige Systeme)
bezeichnet. Ein Wechsel des Signals von 0 auf 1 stellt in seinem
Informations- oder Nachrichteninhalt eine Elementarentscheidung zwischen
zwei entgegengesetzten Werten (vorhanden - nicht vorhanden, falsch -
richtig, ja - nein) dar. Es ist klar, daß es belanglos ist, welche
der Informationen man mit 0 oder 1 bezeichnet. Diese Informationsmenge
bezeichnet man als Nachrichteneinheit oder, als Abkürzung für den
englischen Ausdruck binary-digit, als bit. Aus der 4. Grundaufgabe
der Kombinatorik können wir sofort herleiten, daß man mit bits
Binärkombinationen realisieren kann, also auch Zahlen
(oder allgemeiner Zeichen) darstellen kann. Umgekehrt können wir auch
fragen, wieviele Binärstellen werden benötigt, um eine bestimmte
Informationsmenge durch Binärkombinationen darzustellen. Hierzu
definieren wir zunächst den binären Logarithmus als Umkehrfunktion
der Potenz zur Basis 2.
(2) |
Rechnen mit Dualzahlen
Die Rechenregeln der arithmetischen Algebra sind unabhängig vom Zahlensystem.
Die Operationen der allgemeinen Algebra, wie Addition, Subtraktion, Division
und Multiplikation, die wir vom Dezimalsystem her gewohnt sind, lassen sich
daher auch auf Dualzahlen anwenden. Die Grundregeln für die Addition
mit den binären Zahlen 0 und 1 sind die folgenden:
Die folgenden Rechenbeispiele werden jeweils parallel mit dezimalen und dualen Zahlen durchgeführt.
dezimal | dual | |
10 | Übertrag | 110000 |
25 | Summand | 11001 |
+28 | Addend | + 11100 |
53 | Summe | 110101 |
Die entsprechenden Rechenregeln für die Subtraktion sind:
dezimal | dual | |
25 | Minuend | 11001 |
-18 | Subtrahend | -10010 |
-10 | Entlehnung | - 1100 |
07 | Differenz | 00111 |
Für Dualzahlen läßt sich das gleiche Verfahren anwenden. Allerdings
müssen wir jetzt vom Subtrahenden das Komplement auf 1 bilden. Dieses
1-er Komplement ist rechentechnisch besonders einfach, man muß lediglich
jede Bitstelle einzeln negieren. Das obige Beispiel der Dezimalzahlen 25 - 18
möge dieses verdeutlichen:
1. Schritt | 2. Schritt | 3. Schritt | 4. Schritt |
1-er Komplement | + Minuend | +1 | Streiche höchste Stelle |
11111 | 01101 | 100110 | |
-10010 | +11001 | +000001 | |
01101 | 100110 | 100111 | 00111 |
Wir müssen noch den Fall diskutieren, wenn der Subtrahend größer ist als der Minuend. Bekanntlich erhält man in diesem Fall ein negatives Ergebnis. Dieses läßt sich mit folgender Regel behandeln: Ist der Minuend kleiner als der Subtrahend, so wird zum Minuenden das 9-er (1-er) Komplement des Subtrahenden hinzuaddiert, und das so erhaltene Ergebnis zurückkomplementiert. Ein Dekadenübertrag in der werthöchsten Stelle tritt nicht auf. Ein Beispiel möge diese Regel belegen. Gesucht ist die Differenz 48 - 89 im Dezimal- bzw 11101 - 10110111 im Dual- System.
dezimal | dual | |
89 | 10110111 | |
10 | 01001000 | |
+48 | +00011101 | |
58 | 01100101 | |
-41 | -10011010 |
Die Multiplikation von Dualzahlen wird exakt wie bei Dezimalzahlen
durchgeführt. Das ,,kleine Ein-mal-Eins'' (daher der Name) ist
dezimal |
25 18 |
200 |
250 |
450 |
dual |
11001 10010 |
110010 |
110010000 |
111000010 |
Bei der Division wird geprüft, wie oft der Divisor im Dividenden enthalten ist. Das Ergebnis erhält man durch wiederholte Subtraktion des Divisors. Folglich können alle Rechenoperationen im Dualsystem in einfacher Weise auf die Addition zurückgeführt werden.
Elektronische Addierwerke
Die Rechenregeln der Addition können in der folgenden Funktionstabelle
zusammengefaßt werden (U = Übertrag, S = Summe):
A | B | U | S |
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
Abbildung 1: Schaltung eines Halbaddierers aus NAND- Verknüpfungen.
Diesen Addierer nennt man auch einen Halbaddierer. Halbaddierer deshalb, weil er keinen Übertrag aus einer wertniedrigeren Stelle verarbeiten kann. Im folgenden Applet können Sie mit diesem Halbaddierer spielen. Das Applet selbst haben wir in einer früheren Lektion bereits diskutiert. Einen 1-bit Volladdierer erhält man durch Zusammenschalten zweier Halbaddierer. Eine Schaltung zeigt Abb.2 und eine Realisierung aus NAND und NOT Elementen ist im folgenden Applet angegeben.
Abbildung 2:Schaltung eines 1-bit Volladdierers aus 2 Halbaddierern.
Die Funktionsgleichungen und die Funktionstabelle (siehe Tabelle 1) dieses Volladdierers
sind wie folgt:
Mit diesem 1-bit Volladdierer kann jetzt ein Dual- Addierwerk beliebiger Stellenzahl (n-bit Addierer) aufgebaut werden. Hierbei wird jeweils der Übertrag aus der wertniedrigeren Stelle auf den Eingang der werthöheren Stelle geführt (siehe Abb.3).
Abbildung 3: Schaltung eines n-bit Addierers aus n-1 1-bit Volladdieren und einem 1-bit Halbaddierer.
Die wertniedrigste Stelle braucht natürlich nur als Halbaddierer
ausgeführt zu sein, da kein Übertrag aus einer noch niedrigeren Stelle
als Eingangsgröße vorhanden ist. Mit Hilfe eines ähnlichen
Verfahrens kann man auch Subtrahierwerke entwickeln. Wir werden darauf
jedoch nicht weiter eingehen, da in digitalen Rechenanlagen immer eine
Subtraktion auf eine Addition zurückgeführt wird. Das Verfahren
wurde bereits ausführlich diskutiert. Wir formulieren noch einmal
die allgemeine Subtraktionsregel:
Eine Subtraktion wird als Addition durchgeführt, indem der komplementierte
Subtrahend zum Minuenden addiert wird. Ensteht dabei in der werthöchsten
Stelle der Übertrag 1, so ist das Ergebnis eine positive Zahl, sie muß
aber noch um 1 vergrößert werden (Korrekturaddition). Entsteht in der
werthöchsten Stelle hingegen der Übertrag 0, dann ist das Ergebnis eine
negative Zahl, sie muß dann noch zurückkomplementiert werden.
Rechnerarithmetik
Digitalrechner arbeiten im allgemeinen mit n=16 oder n=32 bit Zahlendarstellung.
Negative Zahlen werden hierbei immer bereits als komplementierte Zahlen
gespeichert, d.h. negative Zahlen erkennt man an einer 1 in der
werthöchsten Stelle. Für die eigentliche Zahlendarstellung verbleiben
lediglich 15 oder 31 bits. Hiermit kann man die positiven Zahlen von
0 bis = 32767 bzw. bis = 2147483647 darstellen.
In vielen modernen Rechenanlagen wird allerdings nicht das Komplement
selbst gespeichert, sondern das Komplement plus der Korrekturaddition.
Dieses nennt man auch das 2-er Komplement. Diese beiden
Darstellungen negativer Zahlen werden in der folgenden Tabelle
verglichen, am Beispiel eines 16 bit Rechners.
Oktalzahl | Dualzahl | Dezimalzahl | Dezimalzahl |
(1-er Kompl.) | (2-er Kompl.) | ||
077777 | 0 111 111 111 111 111 | 32767 | 32767 |
077776 | 0 111 111 111 111 110 | 32766 | 32766 |
077775 | 0 111 111 111 111 101 | 32765 | 32765 |
..... | |||
000010 | 0 000 000 000 001 000 | 8 | 8 |
000007 | 0 000 000 000 000 111 | 7 | 7 |
...... | |||
000001 | 0 000 000 000 000 001 | 1 | 1 |
000000 | 0 000 000 000 000 000 | 0 | 0 |
177777 | 1 111 111 111 111 111 | -0 | -1 |
177776 | 1 111 111 111 111 110 | -1 | -2 |
..... | |||
177771 | 1 111 111 111 111 001 | -6 | -7 |
177770 | 1 111 111 111 111 000 | -7 | -8 |
177767 | 1 111 111 111 110 111 | -8 | -9 |
..... | |||
100001 | 1 000 000 000 000 001 | -32766 | -32767 |
100000 | 1 000 000 000 000 000 | -32767 | -32768 |
Wir haben in diesem Beispiel auch die Oktalzahlen angeschrieben, da sie wesentlich kürzer sind als die Dualzahlen, und man aus ihnen das Bitmuster ebenfalls sofort ablesen kann. Die Anzahl der darstellbaren Zahlen ist im 2-er Komplement um eins größer als im 1-er Komplement. Dafür gibt es im 1-er Komplement 2 Nullen, eine positive und eine negative. Der Vorteil der Zahlendarstellung im 2-er Komplement ist, daß einmal die Doppeldeutigkeit der Null nicht auftritt, und zum zweiten, daß die Korrekturaddition bei der Subtraktion nicht mehr durchgeführt werden muß.
Im mathematischen Sinne existiert die Summe und das Produkt
zweier positiver ganzer Zahlen und immer.
Wie sehen nun diese Summe und das Produkt in der Rechnerarithmetik aus?
Solange das mathematische Ergebnis eine Zahl innerhalb der Zahlendarstellung
des Rechners ergibt, sind natürlich beide, das mathematische
Resulat und das Rechnerresultat, identisch gleich. Wenn nun aber das
mathematische Ergebnis außerhalb des Zahlenbereiches des Rechners liegt,
ergeben sich Unterschiede. Im allgemeinen gehen die bits, die eine
höhere Wertigkeit als die höchstwertige Stelle des Rechners besitzen,
einfach verloren. Manche Rechner geben in diesem Fall eine Fehlermeldung
aus. Wir studieren diese sogenannte Überlauf- Arithmetik für den
einfachen Fall eines Modellrechners mit 4 bit Zahlendarstellung.
Wir haben dann die folgende Zahlendarstellung.
Bilden wir z.B. die Summe der Dezimalzahlen 5 und 6, so erhalten wir bei
der Addition der entsprechenden Dualzahlen die Summe 1011. Dieses entspricht
aber laut obiger Tabelle der Dezimalzahl -4 bei der 1-er Komplement
Dartstellung und -5 bei der 2-er Komplement Darstellung. Entsprechend
ergibt das Produkt aus 5 und 6 die Dualzahl 11110. Die höchste Stelle
geht verloren, da, wie wir oben angenommen haben, unser Rechner nur 4 bits
hat. Es verbleibt also die Zahl 1110. Dieses entspricht der Dezimalzahl
-1 oder -2 im 1-er oder 2-er Komplement. Bilden wir dagegen das Produkt
der Dezimalzahlen 5 und 7, so gibt der Rechner das Resultat 0011 aus,
was gleichbedeutend mit der Dezimalzahl 3 ist. Für unsere weiteren
Diskussionen müssen wir zunächst eine Größe definieren, die uns
im folgenden häufig begegnen wird:
Satz: Sind und zwei ganze Zahlen und ist , so gibt es stets
zwei andere Zahlen und , so daß die Gleichung
(3) |
(4) |
(5) |
Seien nun und zwei ganze positive Zahlen (wir beschränken im
folgenden auf positive Zahlen). Sei ferner die Summe oder das Produkt
von und im mathematischen Sinne und die mit einem Rechner
berechnete Summe oder das Produkt. Der Rechner habe eine n-bit
Arithmetik. Dann gilt für die Relation
(6) |
(7) | |||
(8) |
Gleitkomma- Darstellung
Viele Rechner unterscheiden bei der Zahlendarstellung zwischen
Festkomma- und Gleitkomma- Darstellung.
Die ganzen Zahlen werden, wie bereits oben erläutert, im Dualcode mit m=0
in Formel (1)
dargestellt, während reelle Zahlen entweder in Festkomma- Darstellung
mit oder in der Gleitkomma- Form
(9) |
Dezimalcodes
Moderne Rechner verwenden Dezimalcodes für die Ein- und Ausgabe von Daten,
schon deshalb, weil der Mensch
an das Dezimalzahlensystem gewöhnt ist, und der Computer für den
Menschen da ist und nicht umgekehrt. Ein Dezimalzahlencode, bei dem
jeder Stelle einer Zahl zehn verschiedene elektrische Zustände
zugeordnet sind, ist für die technische Realisierung durch digitale
Schaltungen ungeeignet. Wir werden uns daher mit der binären
Darstellung von Dezimalzahlen befassen müssen, und hierbei insbesondere
mit den BCD- Codes (englisch: binary coded decimal code). Diese Codes
sind dadurch gekennzeichnet, daß jede einzelne Dezimalziffer unabhängig
von der anderen codiert ist. Im dualen BCD- Code ergibt sich damit
für die Ziffer 184 die Codierung
0001 | 1000 | 0100 |
1 | 8 | 4 |
Es gibt eine enorm große Anzahl (
) von
Möglichkeiten, 4 bit Codes zu konstruieren.
In der Praxis werden hiervon jedoch nur wenige Möglichkeiten
ausgenutzt. In der folgenden Tabelle wird gezeigt, wie sich einige
dieser Codes durch Einschieben von Pseudotetraden aus dem Dualcode
entwickeln lassen.
Dualcode | BCD | Codes | |||||||
8421 | Aitken | 3 Excess | 5421 | 5311 | |||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
0 | 0 | 1 | 0 | 2 | 2 | 2 | 2 | ||
0 | 0 | 1 | 1 | 3 | 3 | 3 | 0 | 3 | 2 |
0 | 1 | 0 | 0 | 4 | 4 | 4 | 1 | 4 | 3 |
0 | 1 | 0 | 1 | 5 | 5 | 2 | 4 | ||
0 | 1 | 1 | 0 | 6 | 6 | 3 | |||
0 | 1 | 1 | 1 | 7 | 7 | 4 | |||
1 | 0 | 0 | 0 | 8 | 8 | 5 | 5 | 5 | |
1 | 0 | 0 | 1 | 9 | 9 | 6 | 6 | 6 | |
1 | 0 | 1 | 0 | 10 | 7 | 7 | |||
1 | 0 | 1 | 1 | 11 | 5 | 8 | 8 | 7 | |
1 | 1 | 0 | 0 | 12 | 6 | 9 | 9 | 8 | |
1 | 1 | 0 | 1 | 13 | 7 | 9 | |||
1 | 1 | 1 | 0 | 14 | 8 | ||||
1 | 1 | 1 | 1 | 15 | 9 |
Übungen
Aufgabe 1:
Für einen 32-bit Rechner mit Zahlendarstellung im 2-er Komplement
berechne man die folgenden dezimalen Ausdrücke:
a) 37956 * 69069;
b) 1729358476 + 2010004738;
c) 1729358476 - 2010004738.
Schreiben Sie die Ausdrücke a) bis c) und deren Lösungen auch im
Hexadezimalsystem.
Aufgabe 2: Schreiben Sie Programm- Routinen für die doppelt genaue (64 bit) Addition, Subtraktion, Multiplikation und Division zweier 32-bit Zahlen in 2-er Komplement Darstellung.
Aufgabe 3: Im folgenden Applet finden Sie eine Schaltung für einen 2-bit Volladdierer. Erweitern Sie die Schaltung zu einem 3-bit Volladdierer.
Aufgabe 4: Entwerfen Sie mit Hilfe des Applets von Aufgabe 3 einen Schaltplan aus NAND- und NOT- Verknüpfungen für einen 1-bit Vollsubtrahierer.