Digitaltechnik


von Prof. Jürgen Plate

3 Zahlendarstellung

Für die meisten von uns erscheint das beim Zählen normalerweise angewandte dezimale Zahlensystem von Natur aus vorgegeben zu sein. Beschäftigt man sich etwas genauer mit Zahlen und Zählen, stößt man auf unterschiedliche Zahlensysteme, die genauso natürlich sind wie unser Dezimalsystem. Schon im prähistorischen Zeiten mußten Symbole erfunden (und mit anderen Menschen vereinbart) werden, die jeweils die Anzahl der Tauschobjekte oder deren Wert repräsentieren. Ein geeignetes und einfaches Verfahren dafür ist eine Strichliste, die durchaus auch heute noch Anwendung findet.

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.

3.1 Grundlagen der Zahlensysteme

Definitionen

3.2 Stellenwertsysteme

Für den Wert einer Zahl Z = an an-1 ... a0 a-1 ... a-m in einem Stellenwertsystem zur Basis B gilt:

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.

Ganze Zahlen:

2018 = 2·103 + 0·102 + 1·101 + 8·100

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

Echter Dezimalbruch:

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

Dezimalzahlen:

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.

Dualzahlen

In der Digitaltechnik wird in der Regel das duale Zahlensystem verwendet. Anders als im dezimalen Zahlensystem werden im dualen System nur zwei verschiedene Ziffern unterschieden: 0 und 1. Mit Hilfe dieser beiden Ziffern sind alle Zahlenwerte genauso darstellbar, wie mit den zehn verschiedenen Ziffern des Dezimalsystems. Grundsätzlich wird im Dualsystem nach genau denselben Regeln gerechnet, wie im Dezimalsystem. Lediglich durch das ungewohnte Zahlensystem erscheint und die Rechner schwieriger zu sein.

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:

Oktalzahlen

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

Sedezimalzahlen (= Hexadezimalzahlen)

Zusammenfassung von 4 Dualstellen ergibt eine Sedezimalstelle → Sedezimalsystem: Basis B = 16 und a aus {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}, z. B. 101001dual = 29sedezimal. Übliche Darstellung der eigentlich binären Information in einem Rechner (Kurzschreibweise binärer Info). Kennzeichnung bei der Programmierung durch Voranstellen von '$', '0x' oder Anfügen von 'H' (für "hexadezimal") z. B.: $FFC2 FFC2H 0xFFC2. Gelegentlich wird eine führende Null verwendet, wenn die Zahl mit einem Buchstaben beginnt.

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.

Vielfache von Bit/Byte

Üblicherweise werden die Zweierpotenzen 210, 220, 230 ... und nicht die Zehnerpotenzen 103, 106, 109 ... verwendet:
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 TBit
Es 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

Einheiten Bit
KBit 1000 Bit
MBit 1000 kBit
GBit 1000 MBit
TBit 1000 GBit
PBit 1000 TBit
Einheiten Byte (dezimal)
Kilobyte (kB) 1000 Byte
Megabyte (MB) 1.000.000 Byte
Gigabyte (GB) 1.000.000.000 Byte
Terabyte (TB) 1.000.000.000.000 Byte
Peta (PB) 1.000.000.000.000.000 Byte
Einheiten Byte (binär)
Kibibyte (KiB) 1024 Byte
Mebibyte (MiB) 1.048.576 Byte
Gibibyte (GiB) 1.073.741.824 Byte
Tebibyte (TiB) 1.099.511.627.776 Byte
Pebibyte (PiB) 1.125.899.906.842.624 Byte

3.3 Umrechnung zwischen den Stellenwertsystemen

Umwandlung Dezimalsystem → anderes Stellenwertsystem

Die Darstellung als Potenzreihe kann als Polynom zur Basis B aufgefasst werden.

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    1
Das Ergebnis ergibt sich, wenn man die Rest-Ziffern von unten nach oben liest: 10001111

Dezimal-Dual-Wandlung echtgebrochener Zahlen (Basis B = 2)

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-5
Es 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-4
Es 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:

  1. Aufteilen der Dezimalzahl in einen ganzzahligen und einen gebrochenen Anteil
  2. Berechnung des ganzzahligen Anteils der Dualzahl durch fortwährende Division durch 2
  3. Berechnung des gebrochenen Anteils der Dualzahl durch fortwährende Multiplikation mit 2
  4. Zusammensetzen der Dualzahl aus dem ganzzahligen und dem gebrochenen Anteil

Umwandlung anderes Stellenwertsystem → Dezimalsystem

Der offensichtliche Weg ergibt sich aus der Definition einer Zahl im Stellenwertsystem:

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:

Dual-Dezimal-Umwandlung, ganzzahlig

  1. Setze die Dezimalzahl auf 0. Beginne bei der höchstwertigen Stelle n der Dualzahl. Wir führen einen Wert I ein, der die gerade bearbeitete Stelle der erzeugten Dualzahl enthält. I wird auf n gesetzt.
  2. Multipliziere die Dezimalzahl mit 2 und addiere die I-te Stelle der Dualzahl zur Dezimalzahl.
  3. Wiederhole Schritt 2 solange, bis alle Stellen der Dualzahl verarbeitet sind.

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.
Beispiel: 7C216 = ??10
       7     C    2

16 *   7  + 12       =  124
16 * 124        + 2  = 1986 

Dual-Dezimal-Umwandlung, echter Bruch

Bei echten Brüchen wird fortgesetzt durch die Basis des Ausgangssystems (dargestellt im Zielsystem) dividiert (im Dualsystem die 2). Die Ziffern werden von der niederwertigsten Stelle aus abgearbeitet (rechts nach links) → Abbau zum Komma hin.

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 

Umwandlung Dual - Oktal - Hexadezimal

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:

Die Umwandlung erfolgt in zwei Schritten:
  1. Umwandlung in das Dualsystem. Jede Stelle wird in 3 (oktal) oder 4 (hexadezimal) Dualstellen umgewandelt.
  2. 3 bzw. 4 Dualstellen werden zusammengefasst und in eine Oktal- bzw. Hexadezimalstelle gewandelt. Die Dualzahl ist gegebenenfalls vorher auf volle 3er- oder 4er-Gruppen zu ergänzen (0!). Die Umwandlung erfolgt immer vom Komma weg (ganzzahliger Anteil nach links, gebrochener Anteil nach rechts).
Beispiel: 237.548 = ??16
oktal     2    3    7  .  5    4
dual     010  011  111 . 101  100 → 1001  1111 . 1011  0000
sedezimal                             9     F  .   B     0
Natürlich ist auch eine direkte Umwandlung nach dem weiter oben beschreibenen Schema möglich.
Beispiel: 0,437510 = ??8:
0,4375 * 8 = 3,5000 → 3 * 8-1
3,5000 * 8 = 4,0000 → 4 * 8-2
Es 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.

3.4. Arithmetik im Dualsystem

Wie schon erwähnt, wird im Dualsystem nach genau denselben Regeln gerechnet, wie im Dezimalsystem. Lediglich durch das ungewohnte Zahlensystem erscheint und die Rechner schwieriger zu sein. Die Zahlendarstellung für ganze Zahlen wurde weiter oben schon behandelt. Es gilt:

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.

Arithmetische Grundoperationen

Für die Addition zweier einstelliger Dualzahlen S = a + b gilt:

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:

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: Die letztgenannte Methode, Addition durch Verknüpfung, ist das übliche Verfahren in der Digitaltechnik. Zahlen werden digitaltechnischen Systemen (z. B. Computern) mit einer festen Wortlänge dargestellt. Eine Speicherzelle oder ein Ergebnisspeicher des Prozessors besteht aus einer festen Anzahl von Bits. Diese Größe nennt man Wortlänge. Sie ist von Computertyp zu Computertyp und von Computergeneration zu Computergeneration unterschiedlich. Großrechner der 60ger Jahre verwendeten u. a. Wortlängen von 56 oder 60 Bit, Mikroprozessoren der 80er Jahre begannen mit 4 bzw. 8 Bit. Heute verwenden die meisten Rechner 32 oder 64 Bit Wortlänge.

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:

Darstellung negativer Zahlen

Verläßt man den Bereich der natürlichen Zahlen und will ganze Zahlen darstellen, verändert sich natürlich der Wertebereich, weil jetzt für eine gegebene Wortlänge möglichst symmetrisch ein positiver und negativer Bereich reserviert wird. Ein sehr einfacher Ansatz wäre es, ein Bit als Vorzeichen definieren und den Betrag des Zahlenwerts in den restlichen Bits des Wortes darstellen → Betrags-Vorzeichen-Form. Bei der technischen Realisierung gibt es jedoch einige Nachteile. In der Datenverarbeitung ist das Subtraktionsverfahren mit einem "Borrow"-Signal von der nächsthöheren Stelle nicht gut durchführbar. Daher führt man die Subtraktion auf die Addition einer negativen Zahl zurück. Die Darstellung negativer Zahlen könnte in Form von Betrag und Vorzeichen oder durch die sogenannte Komplementdarstellung erfolgen.

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:

 AllgemeinDezimalDual
B-Komplement K(z)Bn - z10n - z2n - 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 FFFF
Das Komplement kommt hauptsächlich zum Einsatz bei Subtraktion.

Rückführung der Subtraktion auf die Addition:

a - b = a + K(b), wobei K(b) das Komplement von b ist. Die Subtraktion a - b wird also mittels Komplementaddition realisiert:
     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:
  1. Für alle Rechnungen wird eine maximale Stellenzahl n festgelegt.
  2. Für die Komplementbildung wird Bn, sondern Bn+1 gewählt. Dann kann man nämlich eine Vorzeichenstelle verwenden.
Die Vorzeichenstelle dient zwar als Indikator für das Vorzeichen, ist jedoch Bestandteil der Zahl!

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.

Komplementbildung im Dualsystem

Zunächst eine allgemeine Definition. Es sind zwei Arten von Komplementen gebräuchlich.

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

Auch hier gilt: Werden alle n Stellen für den Zahlenwert benutzt, dann ist nicht unterscheidbar, ob eine pos. Zahl oder das Komplement dargestellt wird → (n+1)-te Stelle hat VZ-Funktion.

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:

  1. Einerkomplement bilden und dann 1 addieren:
          0110 1100    X
    
          1001 0011    1-Komplement
        +         1    1 addieren
    
        = 1001 0100    2-Komplement
    
  2. Direkt: Übernahme aller Stellen von rechts bis zur ersten 1 einschließlich, alle weiteren Stellen invertieren:

          0110 1100    X
          1001 0100    übernehmen/komplementieren
    
        = 1001 0100    2-Komplement
    
Wertebereich bei n+1 Stellen (n Ziffern und VZ): -2n bis +2n-1

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     -        1000
Die 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

Merksatz: Wenn beide Operanden das gleiche Vorzeichen haben und das Ergebnis ein
davon abweichendes Vorzeichen, gab es eine Bereichsüberschreitung (Overflow).

Zusammenfassung: Darstellung negativer Zahlen

Am Beispiel der Darstellung von -7310 als 8-Bit-Zahl (n = 8):
Betrag: 7310 → 0100 10012

Übersicht am Beispiel von 16 bit Zahlen

Vorzeichen, Betrag

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)

Einerkomplement, B-1 - Komplement

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

Zweierkomplement, B–Komplement

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

Subtraktion dualer Zahlen

Die Subtraktion kann prinzipiell durch Zählen, Einsatz einer Subtraktionstafel oder als Subtraktion durch Verknüpfung realisiert werden. Die letztgenannte Lösung kann ihererseits durch ein eigenes Subtrahierwerk oder durch Komplementaddition umgesetzt werden, wobei die Komplementaddition die häufigste Methode darstellt.

Die bisher gesammelten Erkenntnisse führen dann zur Rechenvorschrift für die Subtraktion durch Komplementaddition im (Zweierkomplement):

  1. Stellenzahl von X und Y angleichen
  2. B-Komplement Xk des Subtrahenden X bilden
  3. Y und Xk addieren
  4. Eventuellen Übertrag streichen
  5. Ist VZ-Stelle von Y = VZ-Stelle von X und unterscheidet sie sich von der VZ-Stelle des Ergebnisses, dann ist ein Zahlenbereichsüberlauf aufgetreten→ Fehlermeldung.
  6. Ist die VZ-Stelle des Ergebnisses = 0, dann ist das Ergebnis positiv, sonst ist das Ergebnis negativ (in B-Komplement-Darstellung). Will man in diesem Fall den Betrag des Ergebnisses feststellen, muss man das Ergebnis komplementieren.

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
Betragsbildung durch Komplementieren: 00001111 → 00010000 => 1610.

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.

Multiplikation

Bei Multiplikation und Division werden selten konegative Zahlen verwendet. Es werden vielmehr die Beträge multipliziert und dann das Vorzeichen betrachtet. Die duale Multiplikation erfolgt prinzipiell nach den selben Regeln, wie wir sie in der Schule für das Dezimalsystem gelernt haben: Der Multiplikand wird stellenweise mit dem Multiplikator malgenommen und die so erhaltenen Teilergebnisse stellenrichtig aufaddiert. Für Dualzahlen ist die Bestimmung eines Teilergebnisses besonders einfach. Da an der Multiplikatorstelle nur die Werte 0 oder 1 stehen können, ist bei einer 0 das Teilergebnis auch 0, im Fall der 1 ist das Teilergebnis identisch mit dem Multiplikanden. Das Ergebnis zweier n-stelliger Dualzahlen hat nahezu die doppelte Stellenzahl, nämlich 2n - 1.

Der dualen Multiplikation liegt die folgende Multiplikationstabelle zu Grunde (das "Kleine Einmaleins" des Dualsystems):

b
a
a*b
0
0
0
0
1
0
1
0
0
1
1
1

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:

Algorithmus für X * Y:

Setze den Ergebnisspeicher auf 0 und bei einer Wortbreite von n, wiederhole folgende Schritte n-mal.
  1. wenn die letzte Stelle von Y = 1 ist, addiere X zum Ergebnisspeicher.
  2. Verschiebe Y um eine Stelle nach rechts (die in Schritt 1. behandelte Stelle wird "hinausgeschoben", sie verschwindet also).
  3. Verschiebe den Ergebnisspeicher um eine Stelle nach rechts.
      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.

Division

Auch bei der Division X/Y wird nur Addition, Subtraktion (= Komplementaddition) und das Multiplizieren/Dividieren mit 2 benötigt. Auch hier wird nur die Division positiver ganzzahliger Operanden betrachtet. Bei dem geschilderten Verfahren wird der Divisor fortlaufend solange vom Dividenden subtrahiert (durch Addition des Komplements), bis das Ergebnis negativ wird. In diesem Fall ist bereits einmal zuviel subtrahiert worden, was durch durch eine Korrekturaddition des Divisors rückgängig gemacht wird. Die Anzahl der Subtraktionsschritte bei positivem Rest-Dividenden liefert den Quotienten. Eine stellenbewertete Subtraktion reduziert dabei die Schrittzahl. Im Gegensatz zur Multiplikation müssen vor Ausfuhrung der Division noch Kontrollen stattfinden:
  1. Ist der Divisor = 0, erfolgt eine Fehlermeldung.
  2. Der Dividend hat normalererweise die doppelte Stellenzahl (2n) wie Divisor (n) oder Quotient (n). Daher muss weiterhin geprüft werden, ob das Ergebnis in den n-stelligen Quotientenspeicher hineinpasst. Das ist der Fall, wenn der Divisor größer ist als die höchstwertigen n Stellen des Dividenden. Andernfalls erfolgt eine Fehlermeldung.
Der Algorithmus werde zunachst an einem Beispiel im Dezimalsystem demonstriert. Man rechne Dividend : Divisor = Quotient + Rest mit den Zahlen 3610 : 710 = Q + R:
       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:

  1. Setze Quotient auf 0. Setze Rest = X. Setze Zwischenspeicher W = Y.
  2. Verdopple W solange, bis W > Rest ("wie oft geht Y in X")

Wiederholungsschleife:

  1. Wenn W == Y ist, dann ist die Division zuende.
  2. Verdopple den Quotientenwert (Q linksschieben). Halbiere W (rechtsschieben).
  3. Wenn W <= Rest ist, subtrahiere W vom Rest und erhöhe den Quotienten um 1.
  4. Fahre fort bei Schritt 1.

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

3.5 Festpunkt- und Gleitpunktdarstellung

Festpunktzahlen

Bei Festpunktzahlen (Festkommazahlen, fixed point numbers) handelt es sich um gebrochene Zahlen, die eine feste Anzahl von Nachkommastellen haben. Der Dezimalpunkt steht immer an der gleichen (gedachten) Stelle. Der Vorteil liegt darin, dass es sich rechnerintern um ganze Zahlen handelt, deren arithmetische Verarbeitung sehr viel einfacher ist. Wie weit die erste von Null verschiedenen Ziffer vom Punkt entfernt steht, hängt von der Größe der Zahl ab, z. B. Darstellung mit Vorzeichen, 8 Stellen vor dem Komma und 3 Stellen dahinter (dezimal).

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.

Gleitpunktzahlen

Gebrochene Zahlen (reelle Zahlen) werden i. a. in Gleitpunktdarstellung (Gleitkomma-Darstellung) bearbeitet → Gleitpunktzahlen, floating point numbers. Wegen der endlichen Stellenzahl können reelle Zahlen nur unvollkommen dargestellt werden, sie repräsentieren nur einzelne Punkte auf der reellen Zahlengerade → Rundungsfehler beim Rechnen. Bei der Gleitpunktdarstellung wird die Zahl so gespeichert, daß der Radixpunkt immer zur ersten von Null verschiedenen Ziffer gleitet. Dies erreicht man durch Abspalten einer entsprechenden Potenz der Basis:

Z = M * Be, e ganzzahlig
M = 0.xxxxxxx..., 1/B <= M < 1

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)

Umwandlung einer Dezimalzahl in eine Gleitpunkt-Dualzahl:

1. Methode: Beispiel: (8 Stellen Mantisse, 4 Stellen Exponent, V = 8)
27.75 dez. = 11011.11 dual → M = 0.1101111, E = 0101
                           → M = 0.1101111, C = 1101
2. Methode: Beispiel: (8 Stellen Mantisse, 4 Stellen Exponent, V = 8)
27.75 dez. → M = 0.8671875, E = 5
           → M = 0.1101111, E = 0101
           → M = 0.1101111, C = 1101

Eigenschaften von Gleitpunktzahlen:

Gleitpunkt-Arithmetik

Auch hier gilt wieder, dass die Rechenverfahren verwendet werden, die wir in der Schule gelernt haben - eben nur angewendet auf Dualzahlen.

Addition und Subtraktion:

  1. Angleichen der Exponenten der beiden Operanden (Verschieben der Mantisse des Operanden mit kleineren Exponenten)
  2. Addition/Subtraktion der Mantissen
  3. Normalisieren des Ergebnisses

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:

  1. Multiplikation/ Division der Mantissen
  2. Addition/ Subtraktion der Exponenten
  3. Normalisieren des Ergebnisses

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

Assoziativität und Distributivität gilt nicht mehr

Durch die begrenzte Stellenzahl entstehen u. U. Rundungsfehler beim Angleichen der Operanden (Rundungsfehler). Das Assoziativgesetz und das Distributivgesetz gelten nicht mehr.
           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*103
Tatsä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 für Gleitpunkt-Formate

Bei EDV-Anlagen mit großer Maschinenwortlänge werden Mantisse und Exponent meist in einem Maschinenwort untergebracht. Die GK-Arithmetik wird meist von der Hardware unterstützt. Bei Mikrocomputern ist die GK-Arithmetik meist durch Software realisiert (Ausnahme: spezielle GK-Koprozessoren). Häufig wird neben einen Format für einfache Genauigkeit ein weiteres Format für erweiterte Genauigkeit angeboten.

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

3.6 BCD-Zahlen

Zur Erinnerung: "BCD" steht für "Binary coded decimal". Bei der BCD-Darstellung werden die dezimalen Ziffern einer dezimalen Zahl durch vier Bit breite, binäre Zahlen dargestellt. Negative Zahlen werden mit Hilfe eines eigenen Vorzeichen-Bits dargestellt. Wegen der Dezimaldarstellung werden nur die dualen Werte 0000 bis 1001 verwendet. Die verbleibenden mit vier Bit darstellbaren sechs Werte (1010 bis 1111), stellen keine gültigen BCD-Zahlen dar und werden daher auch als "Pseudotetraden" bezeichnet.

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:

Während BCD-Zahlen genauso einfach wie Binärzahlen verglichen und sortiert werden können, sind die Rechenoperationen (Addition, Subtraktion, Multiplikation, Division) aufwendiger. Intern wird jedoch immer dual gerechnet. Tritt bei der BCD-Addition von einer Dezimalstelle zur nächsten ein Übertrag auf oder ist die Summe der Ziffern größer als 9, so muss bei der entsprechenden Stelle 10 subtrahiert und bei der folgenden Stelle 1 addiert werden. Es kann zum Ausgleich alternativ 6 addiert werden. Zum Beispiel:
      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).

BCD-Gleitpunktdarstellung:

3.7 Bit-Reihenfolge

Bei unterschiedlichen Computerarchitekturen werden ganze Zahlen, die länger als ein Byte sind, bei der Speicherung unterschiedlich im Arbeitsspeicher abgelegt. Datenworte, die aus mehreren Bytes bestehen, können nicht vollständig in einer Speicherzelle des Computer-Prozessors gespeichert werden; sie müssen auf mehrere Zellen verteilt werden.

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 0xA
In 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:

Adresse00010203
big endian12345678
little endian78563412

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").

3.8 Übungen

  1. Stellen Sie die Zahlen 11.25 sowie 33.5 im Dual-, Oktal- und Sedezimalsystem dar.
  2. Führen Sie folgende Zahlenumwandlungen durch:
    3067.758 in das Sedezimalsystem
    4A3.D416 in das Oktalsystem
  3. Geben Sie zu folgenden Zahlen die Gleitpunktdarstellung im jeweils angeführten Zahlensystem an. Für die Stellenzahlen gilt: VZ + Mantisse 6 Stellen + Characteristik 3 Stellen:
    a) 456.1310 b) 0.07158 c) -111.0012
  4. Bestimmen Sie das B- wie auch das (B-1)-Komplement der Zahlen 2710 und 3510 im Dualsystem mit 8 Stellen (inkl. Vorzeichen).
  5. Führen Sie die Subtraktion 3510 - 10 durch Komplementaddition im B-Komplement des Dualsystems mit 8 Stellen (inkl. Vorzeichen durch.
  6. Führen Sie die Subtraktion s = a - b mit 8 Bit im B-Komplement für folgende Werte von a und b durch:
    a) a = 1910, b = 710
    b) a = 710, b = 1910
    c) a = 710, b = 1110 11112
  7. Führen Sie die Multiplikation 1310 * 1210 im Dualsystem durch.
  8. Dividieren Sie 3510 durch 1210 im Dualsystem.

Lösungen

  1. 11.25: 1011.012, 13.28, B.416
    33.50: 100001.12, 41.48, 21.816
  2. 3067.758 = 37.F416,
    4A3.D416 = 2243.658
  3. a) 0 011 45613 b) 0 007 715000 c) 1 1011 110010
  4.                    2710           3510 
    (B-1)-Komplement:  11100100     11011100
    B-Komplement:      11100101     11011101
    
  5. 3510 - 2710:
    00100011
    11100101
    00001000
    
  6. a)  0000 11002   1210
    b)  1111 01002  -1210
    c)  0001 10002   2410   
    
  7. 1310 * 1210 = 100111002
  8. 3510 / 1210 = 000000102, Rest 000010112

257 885 161 - 1

lautet neuerdings (Anfang 2013) die größte bekannte Primzahl. Sie wurde an der Untiversity of Central Missouri ermittelt, wo rund 1000 Computer 39 Tage lange rechnen mussten, um die Zahl zu ermitteln. Ausgeschrieben wäre sie 17 000 000 Ziffern lang. Sie ist gleichzeitig eine Mersenne-Primzahl. Mersenne-Zahlen lassen sich als 2n - 1 schreiben. Die ersten acht Mersenne-Zahlen sind 0, 1, 3, 7, 15, 31, 63 und 127. Mersenne-Primzahlen sind gleichzeitig auch noch Primzahlen. Die ersten acht Mersenne-Primzahlen sind 3, 7, 31, 127, 8191, 131071, 524287 und 2147483647 (für die Exponenten 2, 3, 5, 7, 13, 17, 19, 31).

Zum vorhergehenden Abschnitt Zum Inhaltsverzeichnis Zum nächsten Abschnitt


Copyright © Hochschule München, FK 04, Prof. Jürgen Plate
Letzte Aktualisierung: