 |
Digitaltechnikvon Prof. Jürgen Plate |
|
Digitaltechnikvon Prof. Jürgen Plate |
Mit wachsender Anzahl der zu zählenden Elemente wird das Ganze bald unübersichtlich. Um dies zu vermeiden, könnte man für jede denkbare Anzahl ein Symbol definieren. Mit größer werdender Anzahl der Elemente ist irgendwann der Symbolvorrat verbraucht. Die Vielfalt der Symbole führt darüber hinaus zu Mißverständnissen und Fehlern. Im Laufe der Entwicklungsgeschichte sind wohl die ersten Schritte hin zu Zahlensystemen entstanden. Dabei wurde der Symbolvorrat auf relativ wenige Symbole beschränkt. Um aber große Mengen zu erfassen, müssen die wenigen festgelegten Symbole mehrfach verwendet werden. Je nach Kombination der Symbole ergeben sich verschiedene Zahlenwerte. Das römische Zahlensystem verwendet beispielsweise für die Zahlen eins bis zehn verschiedene Kombinationen der Zeichen I, V und X (I, II, III, IV, V, VI, VII, VIII, IX, X usw.). Später wurde irgendwann das von uns verwendete dezimale Zahlensystem geschaffen, das mit zehn verschiedenen Symbolen (0 .. 9) und einen Stellewertsystem auskommt.
Anmerkung: Wir sind an das Dezimalsystem so gewöhnt, dass uns Zahlensysteme wie das im Folgenden behandelte Dualsystem zunächst exotisch anmuten. Die Axiome und Lehrsätze der Mathematik bleiben aber weiterhin gültig und daher ändert sich diesbezüglich nichts.
Der allgemeine Umgang mit dem Dezimalsystem und dessen Bildungsgesetz lässt uns vergessen, daß verschiedenen Bildungsgesetze existieren können, z. B.:
Für DV-Systeme eignet sich nur das Stellenwertsystem.
| Z = |
n
Σ i=-m | ai * Bi |
wobei für die Ziffern ai gilt: 0 ≤ an < B
Als Basis bezeichnet man die kleinste, nicht mehr durch eine Ziffer darstellbare Zahl. Am geläufigsten ist uns das Dezimalsystem mit der Basis 10 Die Festlegung ist rein willkürlich und vermutlich auf die Zahl der Finger beider menschlicher Hände zurückzuführen. → Zahlzeichen der Azteken (Basis 20, Ziffernwertsystem), Zahlzeichen der Inkas (Basis 10, Stellenwertsystem).
Die verkürzte Schreibweise durch Aneinanderreihung von Ziffern ist eine abkürzende Schreibweise der Summenformel. Damit kann jede positive und negative reelle Zahl dargestellt werden, indem jede Stelle der Ziffernfolge mit einer Zehnerpotenz gewichtet wird.
allgemein:
an an-1 ... a0 a-1 ... a-m = an·10n + an-1·10n-1 + ... + a0·100 + a-1·10-1 + ... + a-m·10-m
0,328 = 0 + 3·10-1 + 2·10-2 + 8·10-3
allgemein:
0,a-1 ... a-m = a-1·10-1 + ... + a-m·10-m
Radixschreibweise:
Z = an an-1 ... a0 a-1 ... a-m
Potenzschreibweise:
Z = an·10n + an-1·10n-1 + ... + a0·100 + a-1·10-1 + ... + a-m·10-m
Potenz-Summen-Schreibweise:
| Z = |
n
Σ i=-m | ai * 10i |
Prinzipiell kann jede ganze Zahl größer 1 Basis B eines Stellenwertsystems sein. In der Praxis finden aber nur wenige Werte Verwendung.
Für das Dualsystem ist die Basis B = 2 und a aus {0,1}, z. B. Z = 1010.1dual = 10.5dez. Dieses Zahlensystem ist speziell für die Digitaltechnik von Bedeutung, da nur zwei Zustände eine physikalischen Größe benötigt werden (Spannung, Strom, Frequenz, Magnetisierungsrichtung).
Nachteil ist die unübersichtliche, monotone Ziffernfolge bei der Darstellung langer Dualzahlen. Daher werden beim Umgang mit EDV-Anlagen zwei andere Zahlensysteme verwendet:
Zusammenfassung von 3 Dualstellen zu einer Oktalstelle (bessere
Lesbarkeit, kürzer zu schreiben, leicht umzurechnen)
→ Oktalsystem: Basis B = 8 und a ist aus
{0,1,2,3,4,5,6,7}, z. B. 101001dual = 51oktal.
Bei der Eingabe von Oktalzahlen müssen diese - zur
Unterscheidung von Dezimalzahlen - gekennzeichnet werden. Dies
geschieht durch Hinzustellen der Basis, z. B.: 1257(8)
Häufig (besonders bei Programmiersprachen) geschieht dies
auch durch Voranstellen von '@' oder Anfügen von 'O', 'Q', 'C' z. B.:
@154 154O 154Q 154C (bei C-Compilern auch durch führende Null).
Weitere, manchmal verwendete Zahlensysteme, sind das Ternärsystem (B = 3) und das Quinärsystem (B = 5). Es stellt sich nun die Frage, wie man Zahlen von einem Zahlensystem in ein anderes umrechnen kann.
210 Bit = 1.024 Bit = 1 kiBit 220 Bit = 1.048.576 Bit = 1 MiBit 230 Bit = 1.073.741.824 Bit = 1 GiBit 240 Bit = 1.099.511.627.776 Bit = 1 TiBit("ki" steht hierbei für "kilo binär", "Mi" für "Mega binär" usw.)
103 Bit = 1.000 Bit = 1 kBit 106 Bit = 1.000.000 Bit = 1 MBit 109 Bit = 1.000.000.000 Bit = 1 GBit 1012 Bit = 1.000.000.000.000 Bit = 1 TBitEs gilt also:
256 kiByte = 28*210*23 Bit =221 Bit = 2.097.152 Bit 256 kByte = 28*103*23 Bit = 1000 * 211 Bit = 2.048.000 Bit
|
|
|
Z = an·Bn + an-1·Bn-1 + ... + a0·B0 + a-1·B-1 + ... + a-m·B-m
Es soll die Dualzahl zur Dezimalzahl 71 ermittelt werden. Man zieht die Potenzen auf der Basis 2 heran und untersucht, welche höchste Potenz von 2 noch in die Zahl 71 "hineinpaßt". Hier ist es 26 = 64. Somit ist die Dualstelle 26 gleich 1 ist. Weiter rechnet man 71 - 64 = 7. Die nächste Zweierpotent 25 = 32 ist größer als 7 → 0 notieren. Das Gleiche geschieht bei 24 = 16 und 23 = 8. Die nächst kleinere Potenz zur Basis 2 paßt wieder in den Rest: 22 = 4. Somit ergibt sich für die Dualstelle 22 eine 1. Als Rest ergibt sich 7 - 4 = 3. Dieser Rest läßt sich in 21 = 2 und 20 = 1 aufteilen. Man erhält so die Dualzahl 1000111 als Ergebnis.
Eine andere Form der Darstellung ist das Hornerschema (hier nur für den ganzzahligen Teil):
Bei der Umwandlung ganzer Zahlen gibt es nur positive Potenzen des Basis B. Bei fortgesetzter Division durch die Basis B' des gesuchten Zahlensystems fallen die gesuchten Koeffizienten als Reste der ganzzahligen Division an. Die Division wird fortgesetzt, bis das Divisionsergebnis 0 geworden ist. Die Divisionsreste sind die Ziffern des Zielsystems in aufsteigender Reihenfolge (1. Rest = niederwertigste Ziffer, letzter Rest = höchstwertige Ziffer).
Vereinfacht gesagt, wird die Dezimalzahl wiederholt durch 2 geteilt. Jede Division gibt eine Dualziffer, die gleich dem Rest der Operation ist. Der Rest kann 0 oder 1 sein. Dazu ein Beispiel:
Division Rest 71 : 2 = 35 1 35 : 2 = 17 1 17 : 2 = 8 1 8 : 2 = 4 0 4 : 2 = 2 0 2 : 2 = 1 0 1 : 2 = 0 1Das Ergebnis ergibt sich, wenn man die Rest-Ziffern von unten nach oben liest: 10001111
Hornerschema für den gebrochenen Teil:
Bei der Umwandlung von echten Brüchen wird nach dem gleichen Schema verfahren, nur wird hier fortgesetzt mit der Basis des Zielsystems multipliziert. Die ganzzahligen Anteile der einzelnen Multiplikationsschritte ergeben die Koeffizienten des Zielsystems. Die Rechnung ist zuende, wenn der gebrochene Anteil des Multiplikationsergebnisses 0 wird. Die ganzzahligen Anteile der Multiplikationen werden dann in absteigender Reihenfolge aufgeschrieben (1. Anteil = höchste Stelle).
Beispiele:
0,90625 * 2 = 1,81250 → 1 * 2-1 0,81250 * 2 = 1,62500 → 1 * 2-2 0,62500 * 2 = 1,25000 → 1 * 2-3 0,25000 * 2 = 0,50000 → 0 * 2-4 0,50000 * 2 = 1,00000 → 1 * 2-5Es ergibt sich 0,11101 (diesmal wird von oben nach unten gelesen).
0,4375 * 2 = 0,8750 → 0 * 2-1 0,8750 * 2 = 1,7500 → 1 * 2-2 0,7500 * 2 = 1,5000 → 1 * 2-3 0,5000 * 2 = 1,0000 → 1 * 2-4Es ergibt sich 0,0111.
Vorsicht: Ein endlicher Bruch in einem Stellenwertsystem ist nicht immer auch ein endlicher Bruch in einem anderen. Versuchen Sie mal die Umwandlung von 0,210!
Für beliebige Dezimalzahlen mit ganzzahligem und gebrochenem Anteil ergibt sich die folgende Rechenvorschrift:
Z = an·Bn + an-1·Bn-1 + ... + a0·B0 + a-1·B-1 + ... + a-m·B-m
Die Umwandlung erfolgt durch Auswertung der Summe, wobei die Koeffizienten und die Potenzen der Basis B im Dezimalsystem dargestellt werden.
Beispiel: Umwandlung aus dem Dualsystem
Z = 101,11(2) = ??(10)
Z = 1·22 + 0·21 + 1·20 + 1·2-1 + 1·2-2
Z = 4 + 0 + 1 + 1/2 + 1/4 = 5,75
Eine andere Möglichkeit ist wieder die Anwendung des
Hornerschemas. Das oben dargestellte Verfahren der
Dezimal-Dual-Umwandlung wird einfach umgekehrt. Beginnend bei der
höchstwertigen Ziffer wird bei ganzen Zahlen mit der Basis des
Ausgangssystems (dargestellt im Zielsystem) multipliziert und zur
nachfolgenden Stelle addiert. Dies wird bis zur niederwertigsten
Ziffer fortgesetzt. Das letzte Ergebnis ist die Zahl im Zielsystem.
Die Faktoren bi werden schrittweise berechnet; es gilt:
| dn...d0 = |
n
Σ i=0 |
di * bi | = | dn * bn + dn-1 * bn-1 + ... + d1 * b1 + d0 * b0 |
| = | (...(dn * b + dn-1) * b + ... + d1) * b + d0 |
Beispiel:
1011110002
= (((((((1 * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 0) * 2 + 0) * 2 + 0 = 376
Die Zwischenergebnisse sind: 1, 2, 5, 11, 23, 47, 94, 188, 376
Es ergibt sich dann folgender Algorithmus:
Beispiel: 110111012 = ??10
1 1 0 1 1 1 0 1
2 * 1 + 1 = 3
2 * 3 + 0 = 6
2 * 6 + 1 = 13
2 * 13 + 1 = 27
2 * 27 + 1 = 55
2 * 55 + 0 = 110
2 * 110 + 1 = 221
Das funktioniert auch mit Sedezimal- oder Oktalzahlen.
7 C 2
16 * 7 + 12 = 124
16 * 124 + 2 = 1986
Beispiel: 0,10112 = ??10
0, 1 0 1 1
1/2 = 0,5
(1 + 0,5)/2 = 0,75
(0 + 0,75)/2 = 0,375
(1 + 0,375)/2 = 0,6875
Alternativ können auch die Dezimalaquivalente jeder einzelnen Dualstelle
aus einer vorgefertigten Tabelle gelesen und fortlaufend im Dezimalsystem
addiert werden. In diesem Fall ist keine Unterscheidung zwischen vor bzw.
nach Radixpunkt notwendig. Beispiel:
10111.1012 = ??10
Stellenwert Dezimalsumme
1 * 2-3 0,125 0,125
0 * 2-2 0,25 0,125
1 * 2-1 0,5 0,625
1 * 20 1 1,625
1 * 21 2 3,625
1 * 22 4 7,625
0 * 23 8 7,625
1 * 24 16 23,625
Die behandelten Umwandlungsroutinen können hier genauso verwendet werden. Da die Rechenoperationen immer im Zielsystem durchgeführt werden, ist dies für uns zumindest ungewohnt. Es gibt aber ein einfacheres Verfahren, das über das Dualsystem führt. Alle Basen sind Zweierpotenzen:
oktal 2 3 7 . 5 4 dual 010 011 111 . 101 100 → 1001 1111 . 1011 0000 sedezimal 9 F . B 0Natürlich ist auch eine direkte Umwandlung nach dem weiter oben beschreibenen Schema möglich.
0,4375 * 8 = 3,5000 → 3 * 8-1 3,5000 * 8 = 4,0000 → 4 * 8-2Es ergibt sich 0,348.
Beispiel: 0,6110 = ??16
0,61 * 16 = 9,76 → 9 * 16-1 0,76 * 16 = 12,16 → C * 16-2 0,16 * 16 = 2,56 → 2 * 16-3 0,56 * 16 = 8,96 → 8 * 16-4 0,96 * 16 = 15,36 → F * 16-5 0,36 * 16 = 5,76 → 5 * 16-6 ...Es ergibt sich 0,9C28F5...16 mit Periode C28F5.
Die einzelnen Ziffern der Dualzahl werden entsprechend ihrer Position im Stellensystem mit Gewichten multipliziert, die Potenzen von 2 sind.
Gebrochene Zahlen (sogenannte Festpunktzahlen und Gleitpunktzahlen) werden in späteren Kapiteln behandelt.
| a | b | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Bei der letzten Operation entsteht ein Übertrag auf die folgende Stelle (Carry). Das Ergebnis ist nicht mehr einstellig darstellbar. Die Addition mehrstelliger Dualzahlen wird wie im Dezimalsystem stellenweise durchgeführt (Übertrag berücksichtigen).
Beispiel:
23 0 1 0 1 1 0 3,75 0 0 1 1 . 1 1
+13 0 0 1 1 0 1 +5,25 0 1 0 1 . 0 1
1 1 1 0 0 0 Carry 1 1 1 1 1 Carry
35 1 0 0 0 1 1 9,00 1 0 0 1 . 0 0
Für die Subtraktion einstelliger Dualzahlen D = a - b gilt:
| a | b | D | B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | -1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
Bei der Operation 0 - 1 ist von der nächsthöheren Stelle zu "borgen" (Borrow). Die Subtraktion mehrstelliger Zahlen erfolgt wieder stellenweise.
9,25 1 0 0 1 . 0 1
-4,75 0 1 0 0 . 1 1
1 0 0 1 0 0 Borrow
4,50 0 1 0 0 , 1 0
In realen digitalen Rechensystemen wird jedoch nicht subtrahiert, sondern lediglich
addiert, weshalb an dieser Stelle näher auf die Addition natürlicher Zahlen
eingegangen wird. Die Realisierung der Subtraktion wird im folgenden Kapitel
besprochen. Als Realisierungsmöglichkeiten für die Addition bieten sich an:
Wegen der festen Wortlänge können auch nur endlich viele verschiedene Zahlen dargestellt werden. Der Wertebereich hängt einerseits davon ab, ob natürliche Zahlen, ganze Zahlen oder rationale Zahlen dargestell werden sollen und andererseits von der Wortlänge. Verwendet man die Menge der natürlichen Zahlen mit 0, so ergibt sich bei der Wortlänge von einem Byte der darstellbare Zahlenbereich von 0 bis 255, wobei bei der Dezimalzahl 0 kein einziges Bit und bei 255 alle Bits gesetzt sind.
Die Addition einstelliger Dualzahlen wurde bereits gezeigt ("Halbaddierer" im Bild unten auf der linken Seite). Will man jedoch mehrstellige Dualzahlen addieren, ist (bis auf das LSB) der Übertrag von der vorhergehenden Stelle zu berüchsichtigen - es sind als drei Dualziffern zu addieren: ai, bi und ci. Das leistet ein Volladdierer, der als Erbnis seinerseits zwei Werte liefert: si und ci+1.
Später werden Sie sehen, wie so ein Volladdierer als Digitalschaltung realisiert werden kann. Verwendet man für jede Stelle einen Volladierer und verbindet man jeweis den Ausgang ci+1 einer Stelle mit dem Eingang ci der nächsthöheren Stelle, erhält man einen Addierer für die gewünschte Wortbreite. Das folgende Bild zeigt das Schema eines 4-Bit-Addierers.
Beispiel: Addition zweier 8-Bit-Zahlen
2510 0 0 0 1 1 0 0 1
+1110 0 0 0 0 1 0 1 1
1 1 1 1 Carry
0 0 1 0 0 1 0 0
Ganz allgemein kann ein Addierer für n Stellen durch die folgende "Blockschaltung"
repräsentiert werden:
Zur Erinnerung: Eine n-stellige Zahl Z im Stellenwertsystem mit der Basis B wird beschrieben durch:
| Z = |
n
Σ i = 0 | zi * Bi |
Darstellung des Komplements von Z:
| Allgemein | Dezimal | Dual | |
|---|---|---|---|
| B-Komplement K(z) | Bn - z | 10n - z | 2n - z |
| (B-1)-Komplement K1(z) | (Bn - 1) - z | (10n - 1) - z | (2n - 1) - z |
Bnn hat in jedem Zahlensystem stets die Form 10.....00, eine Eins und n Nullen und
(Bn - 1) die Form (HH.......HHHH) n mal die jeweils höchstwertige Ziffer H.
Beispiele für (Bn-1) mit n = 8:
Dual: (Bn-1) = 1111 1111 Octal: (Bn-1) = 7777 7777 Dezimal: (Bn-1) = 9999 9999 Hex: (Bn-1) = FFFF FFFFDas Komplement kommt hauptsächlich zum Einsatz bei Subtraktion.
a - b
= a + K(b)
= a + (Bn - b)
= Bn + (a - b)
↑
Übertragsbit
Das Übertragsbit Bn kann dann bei der Ergebnisermittlung
einfach weggelassen werden. Das Komplement ist im Prinzip beliebig
wählbar, jedoch sollte eine Zahl in Komplementdarstellung von einer
natürlichen Zahl unterscheidbar sein. Es gelten daher
zwei wichtige Vereinbarungen:
In den folgenden Beispielen wird im Dezimalsystem gerechnet (mit B = 10n+1). Wir vereinbaren:
835 0835
- 276 + 9733
568 10568
↑↑
↑ Vorzeichenstelle = 0 → Erg. positiv
Übertrag/Überlauf weglassen
- 535 9465
- 267 + 9733
- 802 19198
↑↑
↑ Vorzeichenstelle = 0 → Erg. positiv
Übertrag/Überlauf weglassen
Das Komplement von 9198 ergibt als Betrag 0802.
Mit der o. a. Methode ist also auch ein negatives Ergebnis erkennbar und der Betrag (bzw. das Endergebnis) kann durch nochmaliges Komplementieren ermittelt werden. Im Dezimalsystem wird mit der Addition des Komplements nichts gewonnen, weil hier nur die "Arbeit" vom Subtrahieren auf die Komplementbildung verlagert wird. Interessant wird diese Methode erst im Dualsystem.
| (B-1)-Komplement | (1-Komplement, Einerkomplement) | stellenweise invertieren (0→1, 1→0) |
|---|---|---|
| B-Komplement | (2-Komplement, Zweierkomplement) | stellenweise invertieren, dann 1 dazu addieren |
X sei eine n-stellige positive Zahl im Zahlensystem zur Basis 2, dann ist:
Die Bildung des Einerkomplements geschieht durch Invertieren jeder einzelnen Stellen (sehr einfach). Es ergeben sich jedoch zwei "Nullen", beispielsweise für n = 4: 0000 = +0, 1111 = -0. Die -0 muss dann auf +0 normiert werden.
Vor allem bei EDV-Systemen wird deshalb ausschließlich das Zweierkomplement verwendet. Die Bildung kann auf zwei Wegen erfolgen:
0110 1100 X
1001 0011 1-Komplement
+ 1 1 addieren
= 1001 0100 2-Komplement
0110 1100 X
1001 0100 übernehmen/komplementieren
= 1001 0100 2-Komplement
Frage: Warum nicht -2n bis +2n?
Antwort: Der Wert +2n würde eine weitere Stelle benötigen;
die Darstellung passt dann nicht mehr in n Stellen mit Vorzeichen.
Beispiele für die Komplement-Bildung (Basis = 2, Stellenzahl n = 4 → 3 Ziffern und VZ)
Dez. Dual 1-kompl. 2-kompl. 0 0000 1111 0000 1 0001 1110 1111 2 0010 1101 1110 3 0011 1100 1101 4 0100 1011 1100 5 0101 1010 1011 6 0110 1001 1010 7 0111 1000 1001 8 1000 - 1000Die Gesamtheit der so dargestellten Zahlen nennt man konegative Zahlen (gesprochen "ko-negativ", kommt von "komplement-negativ"). Der Vorteil der Komplementdarstellung von negativen Zahlen liegt in der Ausführbarkeit der Subtraktion als Addition des Komplements. Da die Komplementbildung im Dualsystem gegenüber anderen Zahlensystemen sehr einfach ist, ist das Verfahren auch sinnvoll anwendbar.
Schon Blaise Pascal hat im 18 Jahrhundert bei seiner mechanischen Rechenmaschine die Komplementaddition realisiert, um mechanische Bauteile (Zahnräder etc.) einzusparen. Bei der Entwicklung von elektronischen Rechenanlagen im 20. Jahrhundert (zuerst mit Relais, dann mit Elektronenröhren und Transistoren) hat man aus den selben Gründen wieder auf die Komplementaddition zurückgegriffen.
Bei der Subtraktion wird das Komplement addiert und (bei pos. Ergebnis) der Übertrag in die n+1-te Stelle weggelassen. Bei negativem Ergebnis: Komplementdarstellung. Das Carry-Bit (Übertrag) wird gesetzt, wenn in der höchstwertigen Stelle ein Übertrag auftritt.
Wemm man bei einem dreistelligen System (2 Stellen und VZ; Wertebereich -4 ... +3) 2 + 3 addiert, ergibt sich folgende Rechnung:
010
011
101
Das Ergebnis 101 ist eindeutig negativ, nämlich -3. Das korrekte Ergebnis
5 = 0101 liegt nicht im darstellbaren Zahlenbereich! EIm Blick auf den folgenden
Zahlenkreis läßt einen das Problem sofort erfassen. Schreitet man ausgehend von
der Zahl 2 im Uhrzeigersinn 3 Schritte weiter, landet man bei -3. Dabei wird
die rot gezeichnete "Demarkationslinie" überschrittewn → das Ergebnis
der Rechnung ist falsch.
Untersucht man die verschiedenen Möglichkeiten und fasst man die Erkenntnisse zusammen, ergibt sich folgende Tabelle:
| Vorzeichen Operanden |
Vorzeichen Ergebnis |
Bereichs- überschr. |
|---|---|---|
| beide positiv |
positiv negativ |
nein ja |
| positiv negativ |
positiv negativ |
nein nein |
| beide negativ |
positiv negativ |
ja nein |
| In einem Byte sind darstellbar: | ||
| kleinste Zahl: | 1111 1111 | -12710, -(27 - 1) |
| Null: | 0000 0000, 1000 0000 | (2 Darstellungen) |
| größte Zahl: | 0111 1111 | +12710, +(27 - 1) |
| In einem Byte sind darstellbar: | ||
| kleinste Zahl: | 1000 0000 | -12710, -(27 - 1) |
| Null: | 0000 0000, 1111 1111 | (2 Darstellungen) |
| größte Zahl: | 0111 1111 | + 12710, +(27 - 1) |
| In einem Byte sind darstellbar: | ||
| kleinste Zahl: | 1000 0000 | -12810, -(27) |
| Null: | 0000 0000 | (1 Darstellung) |
| größte Zahl: | 0111 1111 | +12710, +(27 - 1) |
|
16-Bit-Wort |
Bedeutung |
|
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
0 |
|
. . .
|
. . . |
|
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
(215 –1) |
|
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
- 0 |
|
. . .
|
. . . |
|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
- (215 –1) |
|
16-Bit-Wort |
Bedeutung |
|
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
0 |
|
. . .
|
. . . |
|
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
(215 –1) |
|
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
- (215 –1) |
|
. . .
|
. . . |
|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
- 0 |
|
16-Bit-Wort |
Bedeutung |
|
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
0 |
|
. . .
|
. . . |
|
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
(215 –1) |
|
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
- 215 |
|
. . .
|
. . . |
|
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
- 1 |
Die bisher gesammelten Erkenntnisse führen dann zur Rechenvorschrift für die Subtraktion durch Komplementaddition im (Zweierkomplement):
Die technische Realisierung erfolgt, indem der schon verwendete Addierer um eine Komponente zur Komplementbildung erweitert wird. Diese muss lediglich die Bit "umdrehen" (Einerkomplement), da die Addition von 1 durch das passende Ansteuern des Carry-Eingangs c0 erfolgen kann (für Addition: 0, für Subtraktin: 1).
Beispiele:
Zahlen Komplenmente Dezimal
a: 00101101 ak: 11010011 (a = 4510)
b: 00011101 bk: 11100011 (b = 2910)
a - b:
0 0 1 0 1 1 0 1 a
1 1 1 0 0 0 1 1 bk
1 1 1 1 1 1 1 Carry
0 0 0 1 0 0 0 0 Ergebnis: 1610
b - a:
0 0 0 1 1 1 0 1 b
1 1 0 1 0 0 1 1 ak
1 1 1 1 1 1 Carry
1 1 1 1 0 0 0 0 Ergebnis: -1610
VZ = 1 → Ergebnis negativ, dargestellt im Zweierkomplement
Für die Subtraktion durch Addition des Einerkomplements (B-1) gilt:
a - b → a + bk1
→ a + ((2n-1) - b)
→ 2n + a - b - 1
Tritt bei der Subtraktion des Einerkomplements ein Übertrag beim MSB auf, darf man diesen nicht ignorieren, sondern er muss zum LSB des Ergebnisses addiert werden. Zum Beispiel:
s = a - b mit a = 1310 = 01101, b = 610 = 00110, bk1 = 11001
0 1 1 0 1 a
1 1 0 0 1 bk1
1 1 1 Carry
1 0 0 1 1 0 Zwischenergebnis
→ → → → → 1 Korrektur
0 0 1 1 1 Ergebnis = 710
Aus diesem Grund und auch wegen der doppelten Null wird das Einerkomplement
fast nie verwendet.
Beispiele:
Addition, Basis = 2, Stellenzahl = 4, 2-Komplement
(+5) 0101 (+5) 0101 (-5) 1011 (-2) 0010 (-7) 0111 (-2) 1110 (+7) 0011 (-2) 1110 (-7) 1001 (-5) 1011 (+2) 0010 (+7) 0111 (-7) 1001 (+5) 0101 (+5) 0101 (+4) 0100 † (+7) 0111 (-4) 1100 †Die mit † gekennzeichneten Ergebnisse sind falsch → Zahlenbereichsüberschreitung.
Der dualen Multiplikation liegt die folgende Multiplikationstabelle zu Grunde (das "Kleine Einmaleins" des Dualsystems):
Beispiel: 23 * 12 = 276
10111 * 01100
00000
10111
10111
00000
00000
100010100
Bei diesem Verfahren kann natürlich in gleicher Form von rechts nach links vorgegangen werden. Ein Nachteil beim oben gezeigten Verfahren ist, dass unter Umständen mehrere 1-Bits in einer Spalte addiert werden müssen und so das Übertragsbit gleich um mehrere Stellen "springt". Es ist somit eine zusätzliche Buchführung der Carry-Bits notwendig. Das läßt sich vermeiden, wenn jedes Teilergebnis addiert wird. Das Verfahren kann noch weiter optimiert werden:
Die Multiplikation von Dualzahlen kann durch Addition und Bitverschiebung vereinfacht werden. Die Verschieben um eine Bitposition entspricht Multiplikation mit 2 (links) oder Division durch 2 (rechts). Alle Rechenanlagen besitzen Bit-Verschiebe-Befehle. Angefangen bei niederwertigsten Bit des Multiplikators wird fortlaufend der Multiplikand zum Ergebnis-Speicher (der zu Beginn auf Null gesetzt wurde) addiert, wenn das entsprechende Bit des Multiplikators den Wert 1 besitzt und dann um eine Position nach links verschoben. Die stellenrichtige Addition wird also nur in Teilschritte zerlegt.
Beispiel: 9 * 13 = 117
1001 * 1101
0000 Ergebnis nullsetzen
+1001
1001 Zwischenergebnis
+0000
01001 Zwischenergebnis
+1001
101101 Zwischenergebnis
+1001
1110101 Endergebnis
Anstatt den Multiplikanten jedesmal nach links zu verschieben (entspricht einer Multiplikation mit 2) und zu addieren, kann man genausogut den Multiplikanten in seiner Position belassen und den Ergebnisspeicher nach rechts verschieben. In diesem Fall wird mit dem LSB der Multiplikators begonnen. Noch etwas modifiziert ergibt sich folgendes Verfahren:
1101 * 0110
0000 Ergebnis Nullsetzen
0000 Addiere 0 (LSB des Multiplikators)
0000 Zwischenergebnis
0000 0 nach rechts schieben
1101 Addition
1101 0 Zwischenergebnis
0110 10 nach rechts schieben
1101 Addition
1 0011 10 Zwischenergebnis (Carry!)
1001 110 nach rechts schieben (mit Carry!)
0000 Addition
1001 110 Zwischenergebnis
0100 1110 nach rechts schieben
Endergebnis: 0100 1110
Da das Multiplikationsergebnis eine höhere Stellenzahl benötigt, müsste der Ergebnisspeicher eigentlich die doppelte Breite gegenüber der Addition bzw. Subtraktion haben. Durch geschicktes Kombinieren vom Operandenspeicher für Y mit dem Ergebnisspeicher kann das vermieden werden. Mit jedem Bit, das nach rechts aus dem Operanden geschoben wird, gelangt von der anderen Seite ein Bit des Ergebnisses hinein. Das Endergebnis steht dann im Ergebnisspeicher (höherwertiger Teil) und im Operandenspeicher (niederwertiger Teil).
Der Block "Multiplikation" entspricht für jedes einzelne Bit der obigen Multiplikationstabelle; ist das LSB der Multiplikators 0, ist der Ausgang des Multiplikationsblocks ebenfalls 0. Im anderen Fall wird der Multiplikand "durchgereicht".
Bei konegativen Operanden werden, wie schon erwähnt, meistens die Beträge multipliziert und danach die Vorzeichen berücksichtigt: ist ein Operand negativ und der andere positiv, erfolgt eine Komplementierung des Ergebnisses.
Die Vorzeichenrechnung kann umgangen werden, wenn Multiplikand und Multiplikator in der Komplementdarstellung verwendet werden. Bei der Multiplikation dieser Zahlen treten additive Korrekturglieder auf, die ohne eine eigentliche Subtraktion eliminiert werden müssen. Die erforderlichen Korrekturen sind im sogenannten Booth-Algorithmus, der die Multiplikation zweier ganzer Zahlen in Zweierkomplementdarstellung ermöglicht, bereits enthalten.
3 6 Dividend
- 7 1. Subtraktion für 1. Quotientenstelle
- 4 kleiner 0, daher wird 1. Quotientenstelle Q = 0
3 6 Korrekturaddition bzw. Restoring
- 7 1. Subtraktion für 2. Quotientenstelle
2 9 größer 0, daher wird Q = 01
- 7 2. Subtraktion für 2. Quotientenstelle
2 2 größer 0, daher wird Q = 02
- 7 3. Subtraktion
1 5 größer 0, daher wird Q = 03
- 7 4. Subtraktion
0 8 größer 0, daher wird Q = 04
- 7 5. Subtraktion
0 1 größer 0, daher wird Q = 05
- 7 6. Subtraktion
- 6 kleiner 0, daher bleibt Q = 05
0 1 Korrekturaddition bzw. Restoring
Es bleibt der Rest R = 1, der Quotient ist Q = 5, also gilt: 36 : 7 = 5 Rest 1
Im Folgenden ist ein Beispiel fur den Algorithmus im Dualsystem
mit n = 4 Stellen angegeben. H und L sind zwei bei der Rechnung benutzte Speicher.
Dividend = 3610 = 0010 0100
Divisor = 710 = 0111; Zweierkomplement = 1001
(H) (L) Erläuterung
0010 0100 Dividend in H und L
0100 1000 1. Linksshift Dividend
1001 1. Add. des Divisor-Komplements
1101 1000 kleiner 0, daher LSB = 0
0100 1000 1. Restoring
1001 0000 2. Linksshift Dividend
1001 2. Add. des Divisor-Komplements
0010 0001 groesser Null, daher LSB = 1
0100 0010 3. Linksshift Dividend
1001 3. Add. des Divisor-Komplements
1101 0010 kleiner 0, daher LSB = 0
0100 0010 2. Restoring
1000 0100 4. Linksshift Dividend
1001 4. Add. des Divisor-Komplements
0001 0101 groesser Null, daher LSB = 1
Das Ergebnis lautet also: Quotient (in L) = 5; Rest (in H) = 1
Vorzeichenbehaftete Operanden stellt man bei der Division durch Betrag und Vorzeichen dar. Deshalb ist eine gesonderte Vorzeichenrechnung nötig.
Eine alternative Möglichkeit der Division X/Y beruht ebenfalls auf der Stellenverschiebung von Dividend und Divisor. Zunächst wird der Divisor Y in einem Hilfsspeicher W abgelegt und W dann solange nach links verschoben (also verdoppelt), bis W > dem Dividenden X ist. Der Divisionsrest R wird mit dem Dividenden X vorbelegt. Der Algorithmus verwendet die Invarianz in der Gleichung
X = Quotient * W + Rest
wobei fortlaufend W durch 2 dividiert und der Quotient mit 2 multipliziert wird, bis W == X ist. Der Ausdruck (Quotient * W) bleibt dabe invariant. Wenn in einem Durchgang W kleiner als der Rest wird, wird W vom Rest abgezogen und der Quotient erhöht.
Vorbereitung:
Wiederholungsschleife:
Beispiel: 14/3 = 4 Rest 2
Dividend X = 1410 = 1110;
Divisor Y = 310 = 0011, Komplement: 1101
Vorbereitung:
Q(otient) = 0000
R(est) = X =1110
W = Divisor Y = 0011
W linksschieben, bis W > X: W = 11000
Ablauf der Schleife:
Q W R
0000 11000 1110 Anfangswerte
0000 1100 1110 Q linksschieben, W rechtsschieben
0001 1100 0010 W <= R → W von R subtrahieren
W != Y → weitermachen
0010 0110 0010 Q linksschieben, W rechtsschieben
W > R → keine Subtraktion
W != Y → weitermachen
0100 0011 0010 Q linksschieben, W rechtsschieben
W > R → keine Subtraktion
W == Y → fertig
Ergebnis: Q(otient): 0100, R(est): 0010
Die Zahl wird mit führenden Nullen dargestellt und gegebenenfalls gerundet. Der Nachteil liegt im begrenzten Zahlenbereich → bei sehr kleinen Zahlen gehen durch die Rundung Stellen verloren, sehr große Zahlen sind nicht mehr darstellbar.
Beispiele:
Dualzahl, 8 Stellen, 3 Stellen nach dem Radixpunkt: 00101011
mit Radixpunkt: 00101.011 → dezimal: 4 + 1 + 0.25 + 0.125 = 5.375
Dezimalzahl: 8.875 = 8 + 0.5 + 0.25 + 0.125
ergibt dual: 01000.111 → 01000111
Um eine Zahl korrekt umzuwandeln, muss also immer das Format (Gesamtstellen, Nachkommastellen) bekannt sein.
Da die Basis bekannt ist, kann die Zahl durch die Mantisse M und den Exponenten e dargestellt werden. → halblogarithmische Darstellung → normalisierte Darstellung. Die Anpassung der GP-Zahl an die angegebene Darstellungsform wird als "Normalisieren" bezeichnet.
Beispiel (dezimal):
Z = 42.5456 → 0.425456 * 102
→ M = 425456, e = 2
Man bezeichnet e als Exponent (bzw. Charakteristik) → Größenordnung der Zahl und M als Mantisse → Angabe der gültigen Zifferndarstellungen.
Die Art der Darstellung von Mantisse und Exponent ist recht unterschiedlich. Für Mantisse und Exponent wird jeweils eine feste Stellenzahl vorgegeben, in der auch das Vorzeichen von Mantisse und Exponent untergebracht werden muss. Am üblichsten ist Betrags-Vorzeichen-Darstellung der Mantisse und Exponentendarstellung mit verschobenem Wertebereich (Charakteristik) so, dass der Wert der Charakteristik immer > 0 ist (so wird ein zusätzliches Bit für das Vorzeichen des Exponenten eingespart). Sie stellt also eine einfache Verschiebung des Wertebereichs dar und hat keinen Einfluss auf die Berechnung.
Beispiel:
Wertebereich Exponent e: -128 ... 127
Charakteristik (C = e + V): 0 ... 255 (V = 128)
27.75 dez. = 11011.11 dual → M = 0.1101111, E = 0101
→ M = 0.1101111, C = 1101
2. Methode:
27.75 dez. → M = 0.8671875, E = 5
→ M = 0.1101111, E = 0101
→ M = 0.1101111, C = 1101
Beispiel (dezimal): 123.45 + 3.6
123.45 3.6
Normalisiert 0.12345 * 103 0.36000 * 101
Exponent anpassen 0.12345 * 103 0.00360 * 103
Mantissen addieren 0.12705 * 103
Multiplikation und Division zweier Gleitpunktzahlen Z1 = M1 * Be1 und Z2 = M2 * Be2 werden realisiert durch
Z1 * Z2 = M1 * M2 * Be1+e2
und
Z1 / Z2 = M1 / M2 * Be1-e2
Nach Auflösung der Operation muß normalisiert werden.
Beispiel: 123.45 * 3.6
123.45 3.6 Ergebnis
Normalisiert 0.12345 * 103 0.36000 * 101
Mantissen multiplizieren 0.04444
Exponenten addieren 4
Produkt 0.04444 * 104
Normalisiert 0.44440 * 103
a + (b + c) ≠ (a + b) + c
a * (b * c) ≠ (a * b) * c
(a + b) * c ≠ (a * c) + (b * c)
Einfaches Beispiel: 10.11 + 11101
Vz Expo. Mantisse
Z1 0 0001 101100 0.101100 * 21
Z2 0 1100 111010 0.111010 * 25
Expo. angleichen
Z1 0 0101 000101 0.000101 * 25
Z2 0 0101 111010 0.111010 * 25
Addieren
S 0 0101 111111 0.111111 * 25
Beim Angleichen des Exponenten geht die letzte Stelle
des ersten Summanden verloren.
Assoziativität und Distributivität gelten nicht mehr! Durch die begrenzte Stellenzahl entstehen u. U. Rundungsfehler beim Angleichen der Operanden (Rundungsfehler).
a + (b + c) ≠ (a + b) + c
a * (b * c) ≠ (a * b) * c
(a + b) * c ≠ (a * c) + (b * c)
Beispiel: Assoziativität: a + ( b + c ) ≠ ( a + b ) + c
a = 0.23*103 b = 0.23*102 c = 0.23*102 0.23*102 + 0.23*102 = 0.46*102 0.46*102 + 0.23*103 = 0.05*103 + 0.23*103 = 0.28*103 0.23*102 + 0.23*103 = 0.02*103 + 0.23*103 = 0.25*103 0.25*103 + 0.02*103 = 0.27*103Tatsächlich äußert sich die Beschränkung der Stellenzahl in der Realität nicht so krass wie in diesem Beispiel, jedoch sind vielfach spezielle numerische Verfahren notwendig, um nicht vollkommen falsche Ergebnisse zu erhalten.
Beispiel: DIN IEC 47B für Mikroprozessoren
Beispiel: IEEE-754-Floating-Point-Standard, Single precision
Einfache Genauigkeit, 32 Bit:
Beispiel: IEEE-754-Floating-Point-Standard, Double precision
Doppelte Genauigkeit, 64 Bit:
Beispiele:
1100 0011 1000 1111 0100 0000 0000 0000
Vorzeichen: 1
Charakteristik: 1000 0111 → 128 + 7 = 135
Exponent: 135 - 127 = 8
Mantisse: 1.0001 1110 1000 0000 0000 000
→ Zahlenwert: -1 0001 1110,1000 0000 0000 000
= -(256 + 16 + 8 + 4 + 2 + 0,5)
= -286,5
+0,375
Dualzahl: 0,011
Normierte Mantisse: (1),1 * 2-2
Exponent: -2
Charakteristik: Exponent + 127 = 125 = 0111 1101
→ Floatzahl: 0011 1110 1100 0000 0000 0000 0000 0000
||________||__________________________|
Vz Char. Mantisse
Zur Kodierung von Zahlen mit mehr als einer Dezimalziffer werden die BCD-Darstellungen der einzelnen Ziffern hintereinander gesetzt (z. B. wird die Zahl 1754 als 0001 0111 0101 0100 dargestellt).
Für einige Anwendungen ist es sinnvoll und/oder notwendig mit Dezimalzahlen zu arbeiten (z.B. kaufmännische Anwendungen, exakte Rechnung mit vorgegebener Stellenzahl). Die Dezimalzahlen werden dann als BCD-Zahlen dargestellt. Es gibt zwei Möglichkeiten der Darstellung:
5 0101 5 0101
+3 0011 +6 0110
8 1000 richtig! (11) 1011 Pseudo-Tetrade!
+6 0110 Korrekturaddition
1 0001 Ergebnis und Übertrag
Statt bei der Korrektur von Pseudotetraden 10 zu subtrahieren
wird 6 addiert. Da der Zahlenbereich vier Dualstellen umfasst
(Werte 0 .. 15), hat die Addition von 6 den gleichen Effekt wie
die Subtraktion von 10. Jedoch wird bei der Addition von 6 auch
gleich ein "paasendes" Übertragsbit erzeugt.
Einige Rechner kennen Befehle zur BCD-Arithmetik (automatische Korrekturaddition).
Die Ausdrücke big endian und little endian beziehen sich auf die Reihenfolge verschiedener Elemente einer hierarchisch strukturierten Einheit, wie es auch eine ganze Zahl ist. Steht das hierarchisch höchststehende Element, also das "dicke Ende" vorne, spricht man von einem "big endian"-System. Steht dagegen das hierarchisch niedrigste Element (das "kleine Ende") am weitesten vorn, spricht man von einem "little endian"-System. Meist bezeichnet man diesen Ausdrücken die Stellenabfolge der Bytes eines Datenwortes und dementsprechend zwei unterschiedliche Regeln, nach denen ein aus mehreren Bytes zusammengesetztes Datenwort auf den Speicher verteilt wird.
Ist beispielsweise das Datenwort vier Bytes (also 32 Bit) lang, werden diese Bytes (b0, b1, b2, b3) in einem "big endian" System im Speicher so angeordnet, wie man die Stellen einer Dezimalzahl auf Papier schreiben würde, also zuerst das höchstwertige Byte und zuletzt das Byte mit dem geringsten Stellenwert → (b3, b2, b1, b0).
In "little endian"-Systemen hingegen steht das Byte mit dem niedrigsten Stellenwert am weitesten links und das Byte mit dem höchsten Stellenwert am weitesten rechts → (b0, b1, b2, b3).
Beispiel:
Der Hexadezimal-Wert 0xABCD soll gespeichert werden. In einem "little endian"-System
erfolgt die Ablage in folgender Reihenfolge im Speicher:
0xD 0xC 0xB 0xAIn einem "big Endian"-System wird dieser Wert in folgender Reihenfolge gespeichert:
0xA 0xB 0xC 0xD
Der 32-Bit-Hexadezimalwert 0x12345678 würde entsprechend folgendermaßen im Speicher abgelegt:
| Adresse | 00 | 01 | 02 | 03 |
| big endian | 12 | 34 | 56 | 78 |
| little endian | 78 | 56 | 34 | 12 |
Viele Mainframes (Großrechner) sind "big endian"-Systeme. Auch die Motorola-Prozessoren (die im Apple Macintosh und im Atari eingesetzt wurden), verwenden die "big endian"-Byte-Anordnung. Die im PC eingesetzten Intel-Prozessoren arbeiten hngegen mit der "little endian"-Byte-Anordnung.
"Big endian" und "little endian" bezieht sich nicht nur auf die Anordnung von Bytes, sondern auch auf die anderer Einheiten, etwa die von Bits innerhalb eines Bytes. Es gibt Computer-Systeme, die die Bits "big endian", die Bytes jedoch "little endian" anordnen oder umgekehrt. In der Regel jedoch ist die Bit-Abfolge sowohl in "big endian"- als auch in "little endian"-Systemen "big-endian", also so, dass das Bit mit dem höchsten Stellenwert am weitesten links steht. Ein Byte mit dem Hexadezimal-Wert 47 wird also in aller Regel als 01000111 wiedergegeben, unabhängig davon, an welcher Position im Datenwort das Byte mit dem Hexadezimalwert 47 steht.
Auch auf Datumsformate lassen sich die Bezeichnungen "big endian" und "little endian" anwenden. In Europa ist für Datumsangaben die "little endian"-Reihenfolge Tag, Monat, Jahr üblich, in Japan wird meist die "big endian"-Reihenfolge Jahr, Monat, Tag verwendet.
Der Ausdruck "big-endian" und "little endian" stammt übrigens aus dem Roman "Gullivers Reisen" von Jonathan Swift. Dort sind die Bewohner des Landes Lilliput in zwei verfeindete Lager gespalten. Es geht um die Frage, ob man gekochter Eier am dicken Ende ("big endian") öffnen sollte oder an der Spitze ("little endian").
2710 3510
(B-1)-Komplement: 11100100 11011100
B-Komplement: 11100101 11011101
3510 - 2710: 00100011 11100101 00001000
a) 0000 11002 1210 b) 1111 01002 -1210 c) 0001 10002 2410
 Zum vorhergehenden Abschnitt |
 Zum Inhaltsverzeichnis |
 Zum nächsten Abschnitt |