Title

Einführung in die Technische Informatik
Prof. Jian-Jia Chen | Dr.-Ing. Christian Hakert | Dr. rer. nat. Marcus Völker
RWTH Aachen University

Kapitel 1: Zahlendarstellung

Anwendungsbeispiel

images/Kapitel 01 - Zahlendarstellung/s001_seg15_snap.png

Abschnitt 1.1

  • Zahlendarstellungen
  • b-adische Darstellung natürlicher Zahlen

Zahlendarstellungen

Endliches Alphabet:

  • z.B. im Dezimalsystem: \(\sum_{10}{={0,1,2,3,4,5,6,7,8,9}}\)
  • allgemein: \(\sum_{b}{={0,1,\ldots,b−1}}\), wobei \(b\) Basis genannt wird

b-adische Zahlen mit endlicher Wortlänge n: \(\sum_{b}^{n}{ }\)

  • Beispiel: \(00456\in\sum_{10}^{5}{ }\)

Wichtige Zahlensysteme in der Informatik:

  • Dual-/Binärsystem: \(\sum_{2}{={0,1}}\)
  • Oktalsystem: \(\sum_{8}{={0,1,2,3,4,5,6,7}}\)
  • Hexadezimalsystem: \(\sum_{16}{={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}}\)

Wahl der Basis

  • Warum keine Basis 10?
    • Natürliche Darstellung für Finanztransaktionen, etwa € 1.20
    • Verbreitet in Wissenschaft, z.B. \(6.6206 ∙ {10}^{34}\)
  • Aber elektronische Bearbeitung schwierig
    • Speicherung anspruchsvoll, der ENIAC benutzte 10 Röhren pro Ziffer
    • Übertragung von 10 Signalniveaus auf einer Leitung benötigt hohe Präzision
    • Implementierung von Addition & Co ist schwierig

b-adische Darstellung natürlicher Zahlen

  • Sei \(b\in{}N\) mit \(b>1\). Dann ist jede natürliche Zahl \(z\) mit \(0\leq{}z\leq{b}^{n}−1\)
  • (und \(n\in{}N\)) eindeutig als Wort der Länge \(n\) über \(\sum_{b}^{n}{ }\)darstellbar durch

\[ z=\sum_{i=0}^{n−1}{{z}_{i}{b}^{i}} \]

mit \({z}_{i}\in\sum_{b}{=\left\{0,1,\ldots,b−1\right\}}\) für \(i=0,1,\ldots,n−1\).

  • Als vereinfachende Schreibweise ist dabei die folgende
  • Ziffernschreibweise üblich:

\[ z={\left({z}_{n−1}{z}_{n−2}\ldots{z}_{1}{z}_{0}\right)}_{b} \]

Wichtiger Spezialfall: \(b=2\) („Binärdarstellung“ natürlicher Zahlen)

Beispiel: Binäre Zahlendarstellung

  • Betrachte \(z={\left(0110\right)}_{2}\)
  • Als natürliche Zahl interpretiert als:

\[ z=\sum_{i=0}^{3}{{2}^{i}\cdot{z}_{i}={2}^{0}\cdot0+{2}^{1}\cdot1+{2}^{2}\cdot1+{2}^{3}\cdot0=6} \]

  • Größte darstellbare Zahl mit \(n\) Bits:

\[ {z}_{max}=\sum_{i=0}^{n−1}{{2}^{i}={2}^{n}−1} \]

  • Beispiel: z ist 3-stellig \(\Rightarrow{z}_{max}={\left(111\right)}_{2}={\left(7\right)}_{10}=2^{3}−1\)

Hexadezimalsystem

  • Basis \(b = 16\), d.h. wir benötigen 16 verschiedene Ziffern
  • Die Ziffern \(0\) bis \(9\) reichen nur für die Wertigkeiten \(0\) bis \(9\)
  • Ab der Wertigkeit \(10\) wird mit Buchstaben weitergezählt:
Ziffer 0 1 … 8 9 A B C D E F
Wert 0 1 … 8 9 10 11 12 13 14 15
  • Wert einer Hexadezimalzahl: \(z=\sum_{i=0}^{n-1}{z_i \cdot 16^{i}}\)
  • Eine Hexadezimalziffer entspricht genau 4 Bit, da \(16 = 2^4\)
    • Kompakte Schreibweise für Binärzahlen, z.B. \((1111)_2 = (\mathrm{F})_{16}\)

Horner-Schema

  • Schema zur Umrechnung zwischen
    Zahlensystemen mit unterschiedlichen Basen

\[ w=\sum_{i=0}^{n−1}{{z}_{i}{b}^{i}={z}_{0}+b\cdot({z}_{1}+b\cdot({z}_{2}+\ldots\left(b\cdot\left({z}_{n−3}+b\cdot\left({z}_{n−2}+b\cdot{z}_{n−1}\right)\right)\ldots\right))} \]

  • Ermittle Sequenz durch Division mit Rest:

\(\frac{w}{b}={z}_{1}+b\cdot({z}_{2}+\ldots\left(b\cdot\left({z}_{n−3}+b\cdot\left({z}_{n−2}+b\cdot{z}_{n−1}\right)\right)\ldots\right))\) Rest \({z}_{0}\)

\(\frac{{w}_{1}}{b}={z}_{2}+\ldots\left(b\cdot\left({z}_{n−3}+b\cdot\left({z}_{n−2}+b\cdot{z}_{n−1}\right)\right)\ldots\right))\) Rest \({z}_{1}\)

\(\frac{{w}_{n−2}}{b}={z}_{n−1}\) Rest \({z}_{n−2}\)

\(\frac{{w}_{n−1}}{b}=0\) Rest \({z}_{n−1}\)

Beispiel: Horner-Schema

Beispiel: \({\left(2595\right)}_{10}\) nach Basis 11

\[ \frac{{\left(2595\right)}_{10}}{11}={\left(235\right)}_{10} \]

\[ \frac{{\left(235\right)}_{10}}{11}={\left(21\right)}_{10} \]

Rest: \({\left(10\right)}_{10}={\left(A\right)}_{11}\)

Rest: \({\left(4\right)}_{10}={\left(4\right)}_{11}\)

\[ \frac{{\left(21\right)}_{10}}{11}={\left(1\right)}_{10} \]

\[ \frac{{\left(1\right)}_{10}}{11}={\left(0\right)}_{10} \]

Rest: \({\left(10\right)}_{10}={\left(A\right)}_{11}\)

Rest: \({\left(1\right)}_{10}={\left(1\right)}_{11}\)

\[ {\left(2595\right)}_{10}={\left(1A4A\right)}_{11} \]

Divisionsmethode: Algorithmus

  • Umrechnung einer natürlichen Zahl \(z\) (dezimal) in eine Darstellung zur Basis \(b\)
  • Idee: Der Rest der Division durch \(b\) liefert jeweils die nächste Ziffer von rechts
Eingabe:  natürliche Zahl z, Basis b > 1
Ausgabe:  Ziffern z_(n-1) ... z_1 z_0 zur Basis b

i := 0
wiederhole
    z_i := z mod b        // Rest = nächste Ziffer
    z   := z div b        // ganzzahliger Quotient
    i   := i + 1
solange z > 0

Ergebnis: (z_(i-1) ... z_1 z_0)_b
  • Die Reste werden also von unten nach oben gelesen

Beispiel: Umrechnung Dezimal- zu Binärsystem

  • 47 : 2 = 23 Rest 1

  • 23 : 2 = 11 Rest 1

  • 11 : 2 = 5 Rest 1

  • 5 : 2 = 2 Rest 1

  • 2 : 2 = 1 Rest 0

  • 1 : 2 = 0 Rest 1

  • \[(47)_{10} = ( ? )_2\]

Beispiel: Hexadezimalsystem

  • Hexadezimal → Dezimal: Betrachte \(z = (\mathrm{2AF})_{16}\)

\[ z = 2 \cdot 16^2 + 10 \cdot 16^1 + 15 \cdot 16^0 = 512 + 160 + 15 = (687)_{10} \]

  • Dezimal → Hexadezimal mit der Divisionsmethode:
    • 687 : 16 = 42 Rest 15 \(\rightarrow\) F
    • 42 : 16 = 2 Rest 10 \(\rightarrow\) A
    • 2 : 16 = 0 Rest 2 \(\rightarrow\) 2
    • Reste von unten nach oben gelesen: \((687)_{10} = (\mathrm{2AF})_{16}\)
  • Hexadezimal ↔︎ Binär: jede Ziffer einzeln in 4 Bit umwandeln
    • \((\mathrm{2AF})_{16} = (0010\ 1010\ 1111)_2\)

Addition

  • mod-Operation („modulo“): \(a mod b\) ist der Rest der Division von \(a\) durch \(b\)
  • Resultat von \(x+y\) ist definiert für \(n\) Bits als \(\left(x+y\right) mod{ 2}^{n}\)
  • Beispiel:

\[ \begin{array}{rr} &0011\\ +&0010\\ \hline &0101 \end{array} \]

\[ \begin{array}{rrr} 3&=&2^0+2^1\\ 2&=&2^1\\ \hline 5&=&2^0+2^2 \end{array} \]

  • Überlauf eines jeden Bits ergibt Übertrag

Überlauf bei Addition

Beispiel: Was geschieht bei \(15 + 2\)?

\[ \begin{array}{rr} &1111\\ +&0010\\ \hline &0001 \end{array} \]

\[ \begin{array}{rrr} 15&=&2^0+2^1+2^2+2^3\\ 2&=&2^1\\ \hline 1&=&2^1 \end{array} \]

\[ 1=\left(15+2\right) mod {2}^{4} \]

  • Überläufe entstehen durch endliche Präzision. Die implementierte Addition ist daher „modular“, und das Resultat von \(x+y\) bei \(n\) Bits ist definiert als \(\left(x+y\right) mod {2}^{n}\)

Multiplikation

Schulmethode:

Sei \(x\) der Multiplikand, \(y=({y}_{n−1},\ldots,{y}_{0})\) der Multiplikator, dann ist

\[ x\cdot{}y=x\cdot{y}_{0}+x\cdot{y}_{1}\cdot2+x\cdot{y}_{2}\cdot{2}^{2}+\ldots+x\cdot{y}_{n−1}\cdot{2}^{n−1} \]

\[ =\sum_{i=0}^{n−1}{x\cdot{y}_{i}\cdot{2}^{i}} \]

  • In der Praxis ist es sinnvoll, jeden Term der Form \(x\cdot{y}_{i}\cdot{2}^{i}\)
  • zu addieren, sobald er generiert wurde:

\[ x\cdot{}y=\left(\ldots\left(\left(x\cdot{y}_{0}+x\cdot{y}_{1}\cdot2\right)+x\cdot{y}_{2}\cdot{2}^{2}\right)+\ldots\right)+x\cdot{y}_{n−1}\cdot{2}^{n−1} \]

Abschnitt 1.2

Ganze Zahlen

  • Darstellung ganzer Zahlen im Rechner
  • Alternative Darstellungen ganzer Zahlen
  • BCD-Code

Darstellung ganzer Zahlen im Rechner

  • Bisher wurden nur natürliche Zahlen betrachtet. Wie sollte man ganze Zahlen darstellen?

  • Der konzeptionell einfachste Ansatz:

  • Dualdarstellung wie bisher plus Vorzeichen-Bit

  • 0 = +, 1 = -, Bsp. +5 = 0101, -5 = 1101

  • Nachteile: 0 hat zwei Darstellungen und man braucht sowohl Addier- als auch Subtrahierwerk:

Nachteile der vorzeichenlosen Version  Verwendung von K1(x) und K2(x)

1. +x, +y x+y Add.
2. -x,-y -(x+y) Add.
3. +x, -y (x ≥ y) x-y Subtr.
-x, +y (y ≥ x) y-x Subtr.
4. +x, -y (x < y) -(y-x) Subtr.
-x, +y (y < x) -(x-y) Subtr.

Exzessdarstellung

  • Idee: Zu jeder Zahl \(z\) wird ein fester Wert \(q\) addiert (Exzess, auch Bias). Gespeichert wird die vorzeichenlose Binärzahl \(z+q\).
  • Rückrechnung: \(z=(x_{n-1}\ldots x_0)_2-q\)
  • Üblich bei \(n\) Bit: \(q=2^{n-1}\) \(\Rightarrow\) Wertebereich \(-2^{n-1}\leq z\leq 2^{n-1}-1\)
  • Beispiel: \(n=4\), \(q=8\)
\(z\) \(z+8\) Bitfolge
\(-8\) \(0\) 0000
\(-3\) \(5\) 0101
\(0\) \(8\) 1000
\(+5\) \(13\) 1101
\(+7\) \(15\) 1111
  • Die Reihenfolge der Bitfolgen entspricht der Reihenfolge der Zahlen: Vergleich wie bei vorzeichenlosen Zahlen
  • Anwendung: Exponent von Gleitkommazahlen (IEEE 754, dort mit \(q=2^{k-1}-1\), siehe Abschnitt 1.4)

Darstellung ganzer Zahlen im Rechner

  • Wir arbeiten hauptsächlich auf der Menge \(\sum_{2}{={0,1}}.\)
  • \(\sum_{2}^{n}{ }\)beschreibt dann die Menge der n-stelligen Binärzahlen.

  • Sei \(x={\left({x}_{n−1}\ldots{x}_{0}\right)}_{2}\in\) \(\sum_{2}^{n}{ }\)eine \(n\)-stellige Binärzahl.

  • \({K}_{1}\left(x\right)≔{\left(\overline{{x}_{n−1}},\ldots,\overline{{x}_{0}} \right)}_{2}\) heißt Einer-Komplement von \(x\)

  • \({K}_{2}\left(x\right)≔{\left(\overline{{x}_{n−1}},\ldots,\overline{{x}_{0}}\right)}_{2}+1={K}_{1}\left(x\right)+1 \left(modulo\right) {2}^{n}\) heißt Zweier-Komplement von \(x\)

Beispiel: \(x\) = 10110010: \({K}_{1}\left(x\right)=01001101\) \({K}_{2}\left(x\right)=01001110\)

Umrechnungsregeln

  • Einerkomplement: Invertierung

Beispiel: \(x\) \(=10110010\)

\({K}_{1}(x)\) \(=01001101\)

  • Zweierkomplement: Invertierung \(+ 1\)

Beispiel: \(x\) \(=10110010\)

\({K}_{1}(x)\) \(=01001101\)

\({K}_{2}(x)\) \(=01001110\)

Beispiel: Vorzeichenbehaftete Zahlen mit 4 Bit

  • Das MSB legt das Vorzeichen fest

  • \({\left(0???\right)}_{2}\)

  • \({\left(1???\right)}_{2}\)

    • Wie interpretieren wir die Bits bei den Fragezeichen?

Einerkomplement

  • \({\left(0???\right)}_{2}\): wird interpretiert wie im vorzeichenlosen Fall
  • \({\left(1???\right)}_{2}\): Bilde Einerkomplement \({K}_{1}\)
  • Beispiel:

\[ (0010)_2 = +(010)_2 = (2)_{10} \]

\[ (1010)_2=-K_1(1010)_2 = -(0101)_2 = -(5)_10 \]

  • \(K_1(K_1(x))=x\)

Addition im Einerkomplement

Beispiel: \((3)_{10}+(-6)_{10}=(-3)_{10}\)

\((3)_{10}=(0011)_2\)

\(-{6}_{10}=K_1(0110)_2=(1001)_2\)

\[ \begin{array}{rr} &0011\\ +&1001\\ \hline &1100 \end{array} \]

\[ (1100)_2=-K_1(1100)_2=-(0011)_2=-(3)_{10} \]

Zweierkomplement

  • \((0???)_{2}\): wird interpretiert wie im vorzeichenlosen Fall

  • \((1???)_{2}\): Bilde Zweierkomplement \({K}_{2}\)

  • Beispiel:

  • \((0010)_2 = +(010)_2 = (2)_{10}\)

  • \((1010)_2 = -K_2(1010)_2 = -(0101 + 1)_2 = -(6)_{10}\)

  • \({K}_{2}({K}_{2}(x))= x\)

Addition im Zweierkomplement

  • Beispiel: \((3)_{10}+(−6)_{10}= -(3)_{10}\)

  • \((3)_{10} = (0011)_2\)

  • \(-(6)_{10} = K_2(0110)_2 = (1001 + 1)_2 = (1010)_2\)

\[ \begin{array}{rr} &0011\\ +&1010\\ \hline &1101 \end{array} \]

  • \((1101)_2 = -K_2(1101)_2 = -(0010 + 1)_2\)
  • \(= -(3)_{10}\)

Darstellungsbereiche bei 4 Bit

  • Vorzeichenlos:

  • \((0)_{10} \cdot\cdot\cdot (15)_{10}\)

  • Einerkomplement:

  • \(-(7)_{10} \cdot\cdot\cdot (7)_{10}\)

  • Zweierkomplement:

  • \(-(8)_{10} \cdot\cdot\cdot (7)_{10}\)

Darstellungsbereiche

  • Sei \(x=({x}_{n−1}\ldots{x}_{0})_{2}\in{B}^{n}\) eine \(n\)-stellige Binärzahl.

  • Im Einerkomplement: \(−\left({2}^{n−1}−1\right)\leq{}x\leq{2}^{n−1}−1\)

  • Im Zweierkomplement: \({−2}^{n−1}\leq{}x\leq{2}^{n−1}−1\)

  • Wegen der doppelten Darstellung der 0 im Einerkomplement lässt sich im Zweierkomplement eine Zahl mehr darstellen
  • Einfache (technische) Umsetzung arithmetischer Operationen
  • Addition bspw. genauso wie vorzeichenlos

Alternative Darstellung ganzer Zahlen

Bitfolge Darstellung in Dezimalnotation
Vorz./Betrag K1 K2
0000 +0 +0 +0
0001 +1 +1 +1
0010 +2 +2 +2
0011 +3 +3 +3
0100 +4 +4 +4
0101 +5 +5 +5
0110 +6 +6 +6
0111 +7 +7 +7
1000 -0 -7 -8
1001 -1 -6 -7
1010 -2 -5 -6
1011 -3 -4 -5
1100 -4 -3 -4
1101 -5 -2 -3
1110 -6 -1 -2
1111 -7 -0 -1

Zahlenrad: Einer- vs. Zweierkomplement

ti-1-deck-code-7e0d903b.tex.svg
  • \(+1\) entspricht einem Schritt im Uhrzeigersinn, der Überlauf liegt zwischen \(0111\) und \(1000\)
  • Einerkomplement: zwei Darstellungen der 0 (\(0000\) und \(1111\)), beim Schritt von \(-0\) nach \(0\) geht ein Schritt verloren
  • Zweierkomplement: jede Bitfolge steht für genau eine Zahl, z.B. \(-1+1=0\) ohne Korrektur

Übersicht: Darstellung ganzer Zahlen

kleinste Zahl größte Zahl \(n=4\) Vorteile Nachteile
Vorzeichen/ Betrag \({-(2^{n-1}-1)}\) \({2^{n-1}-1}\) \(-7\ldots 7\) intuitiv; Negation durch Kippen des Vorzeichenbits zwei Darstellungen der 0; Addier- und Subtrahierwerk nötig
Einer­komplement \({-(2^{n-1}-1)}\) \({2^{n-1}-1}\) \(-7\ldots 7\) Negation durch Invertieren; Subtraktion als Addition zwei Darstellungen der 0; Übertrag muss bei der Addition zurückgeführt werden
Zweier­komplement \({-2^{n-1}}\) \({2^{n-1}-1}\) \(-8\ldots 7\) eindeutige 0; Addition wie vorzeichenlos; Standard in Rechnern asymmetrisch (\(-2^{n-1}\) hat kein positives Gegenstück); Negation: Invertieren \(+1\)
Exzess-\(2^{n-1}\) \({-2^{n-1}}\) \({2^{n-1}-1}\) \(-8\ldots 7\) eindeutige 0; Vergleich wie vorzeichenlos Addition braucht Korrektur um \(q\); 0 ist nicht \(00\ldots0\)

BCD-Code

Binary Coded Decimal

  • Ziffern werden einzeln mit 4 Bits als vorzeichenlose Binärzahl
  • dargestellt.

Beispiel: 4739 = 0100 0111 0011 1001

  • 6 Bitmuster ungenutzt, erlaubt Darstellung der Vorzeichen:
  • z.B. + = 1010 und - = 1011

Nachteil: Erschwerte Addition

0100 0111 0011 1001
0001 0010 1000 0111
0101 1001 1100 0000

Beispiel: 4739 + 1287 = 6026

Z.B. Fehler an der letzten Stelle wegen des Übertrags.

BCD-Code

  • Korrektur: Bei jedem Übertrag und bei jeder ungültigen
  • BCD-Darstellung 6 aufaddieren:
0101 1001 1100 0000
0110
0101 1001 1100 0110
0110
0101 1010 0010 0110
0110
0110 0000 0010 0110
6 0 2 6

Exkurs: Anwendungen BCD Code

  • Vorteil von BCD: Einfache Konvertierung in Dezimalsystem, daher BCD Code für Anzeigen sinnvoll
  • Konkrete Anwendungsbeispiele
    • DCF Funkuhr Signal
    • Bis heute existieren Hardwarebausteine (IC), welche u.a. BCD Codes für 7 Segment Displays dekodieren
    • Taschenrechner (u.a. von Texas Instruments) nutzen die freien Kombinationen für weitere Symbole (z.B. unendlich)

Abschnitt 1.3

Festkommazahlen

Festkomma-Darstellung

Instagram

images/Kapitel 01 - Zahlendarstellung/ti_rwth_qr.png

Motivation: Festkommazahlen

  • Fest vorgegebene Anzahl an Vor- und Nachkommastellen
  • Getrennt voneinander binär dargestellt
  • Häufig aus Performancegründen eingesetzt

Festkomma-Darstellung

  • Komma rechts von der Stelle mit dem niedrigsten Wert:

  • ein \(n\)-Bit Wort \(({z}_{n−1}\ldots{z}_{0})_{2}\) stellt dann die Zahl

  • \(z=\sum_{i=0}^{n−1}{{z}_{i}\cdot{2}^{i}}\) dar, z.B. 110101.0

  • Komma links von der Stelle mit dem höchsten Wert:

  • ein \(n\)-Bit Wort \(({x}_{1}\ldots{x}_{n})_{2}\) stellt dann die Zahl

  • \(z=\sum_{i=1}^{n}{{z}_{i}\cdot{2}^{−i}}\) dar, z.B. 0.110101

  • Allgemein stellt eine Bitfolge \(({x}_{n−1},\ldots,{x}_{1},{x}_{0},{x}_{−1},\ldots,{x}_{−m})_{2}\),

  • falls das Komma zwischen \({x}_{0}\) und \({x}_{−1}\) angenommen wird, die Zahl

  • \(z=\sum_{i=−m}^{n−1}{{z}_{i}\cdot{2}^{i}}\) dar, z.B. 1101.01

Beispiel für Festkomma-Arithmethik

Verwende 4 Bits für Vor- und 3 Bits für Nachkommateil

\(3.5+2.5\) \(=\left(0011\right).\left(100\right)+\left(0010\right).\left(100\right)\)

\(=\left(0110\right).\left(000\right)\)

\(=6.0\)

Beispiel

\[ \begin{array}{lllll} 0{,}6875 & \cdot 2 & = & 1 & {,}375\\ 0{,}375 & \cdot 2 & = & 0 & {,}75\\ 0{,}75 & \cdot 2 & = & 1 & {,}5\\ 0{,}5 & \cdot 2 & = & 1 & {,}0\\ 0 \end{array} \]

  • \((0,6875)_{10} = 0,( ? )_2\)

Abschnitt 1.4

Gleitkommazahlen

  • Gleitkomma-Darstellung
  • Regeln für das Rechnen mit Gleitkommazahlen
  • Rechnerinterne Darstellung von Gleitkommazahlen
  • IEEE 754

Motivation: Gleitkommazahlen

  • Alternative zu Festkomma: approximative Darstellung reeller bzw. rationaler Zahlen
  • Bei gleicher Anzahl an Bits wie bei Festkommadarstellung wird viel größerer Zahlenbereich abgedeckt
  • Aber: Nicht jede Zahl in diesem Bereich kann exakt dargestellt werden
  • Bis in die 80er Jahre hinein gab es viele verschiedene Gleitkomma-Darstellungen.
  • Das Institute of Electrical and Electronics Engineers (IEEE) gab einen Standard für 32-, 64- und 80-Bit Gleitkommazahlen heraus.
  • Probleme durch die Behandlung von Über- bzw. Unterläufen und anderen Ausnahmen.

Gleitkomma-Darstellung

  • Jede Zahl \(z\) wird in der Form \(z=\pm{}m\cdot{b}^{\pm{}e}\) dargestellt mit \(m\) Mantisse, \(e\) Exponent, \(b\) Basis für den Exponenten.

  • Die Basis ist für alle auftretenden Exponenten die gleiche; daher rechnerinterne Darstellung einer Gleitkomma-Zahl:

\[ (\pm{}m,\pm{}e) \]

  • Beispiel: \(e=1.6∗{10}^{−19}C\)

Bit-weise Darstellung

  • Speicherung einer Gleitkomma-Zahl in drei Feldern

    • Vorzeichen \(\hat{s}\)
    • Exponent \(\hat{e}=({e}_{k−1}\ldots{e}_{0})\)
    • Mantisse \(\hat{m}=({m}_{n−1}\ldots{m}_{0})\)

  • Bei 32-Bit haben wir \(k=8\) und \(n=23\)

  • Bei 64-Bit haben wir \(k=11\) und \(n=52\)

  • Drei Fälle: normalisiert, denormalisiert und Sonderzahlen

IEEE 754 32-bit („single“)

images/Kapitel 01 - Zahlendarstellung/s037_seg11_snap.png
  • 0 bei positiven Zahlen
  • 1 bei negativen Zahlen

Vorzeichen \(\hat{s}\) der Mantisse

  • Mit dieser Aufteilung darstellbare Beträge:

\(1.18\cdot{10}^{−38}\) bis \(3.40\cdot{10}^{38}\)

Normalisierte Darstellung

  • \(\hat{e}\neq\left(0\ldots0\right)\) und \(\hat{e}\neq(1\ldots1)\)
  • Exponent \(e=\hat{e}−bias\) mit \(bias={2}^{k−1}−1\)
    • Für 32-Bit also \(bias=127\) da \(k=8\)
  • \(m\) wird interpretiert als \(m=1+\left(0,\hat{m}\right)=1,\hat{m}\)
    • Darstellungstrick für ein weiteres Bit an Präzision
  • Also gilt \(1\leq{}m<2\)

Normalisierte Darstellung

  • Zum Beispiel wird die Zahl \(z=−1.5\) dargestellt durch

\[ 10111111110000000000000000000000 \]

  • d.h.

\[ \hat{s}=1 \] \[ \begin{array}{rcl} \hat{e}&=&01111111\\ \hat{m}&=&10000000000000000000000 \end{array} \]

\[ s=1 \] \[ e=\hat{e}−127=0 \] \[ m=1.\hat{m}=1.5 \]

Normalisierte Darstellung

  • Stelle \(−2.625\) als IEEE 754 Gleitkommazahl dar
  • Vorzeichen: s = 1 → ŝ = 1
  • Mantisse: \((2,625)_{10} = (10,101)_2\)

Normalisieren: \((10,101)_2 = (1,0101)_2 \cdot (2)^1\)
m̂ = 01010… - Exponent: e = ê -127 ↔︎ ê = e + 127
ê \(= 1 + 127 = 128 = (10000000)_2\)

···

images/Kapitel 01 - Zahlendarstellung/s040_seg07_snap.png

Normalisierte Darstellung

  • Welcher Dezimalzahl entspricht die folgende Binärzahl?

\(0\ 10110011\ 010100...0000\)

  • Vorzeichen: ŝ = 0 → s = 0 → pos. Zahl
  • Exponenten: ê \(= (10110011)_2 = (179)_{10}\)
    e = ê -127 = 52
  • Mantisse: m = 1,m̂ \(= (1,0101)_2 = (1,3125)_{10}\)
  • Ergebnis: z \(= + 1,3125 \cdot 2^{52}\)

Beispiel: Dezimal \(\to\) IEEE 754 (32 Bit)

Stelle \(z=12{,}375\) als IEEE 754 Gleitkommazahl dar:

  1. Vorzeichen: \(z>0\) \(\Rightarrow\) \(\hat{s}=0\)
  2. Binär umwandeln: \(12=(1100)_2\), Nachkommateil durch fortgesetztes Multiplizieren mit 2: \[ \begin{array}{rcll} 0{,}375\cdot 2 &=& 0{,}75 & \to 0\\ 0{,}75\cdot 2 &=& 1{,}5 & \to 1\\ 0{,}5\cdot 2 &=& 1{,}0 & \to 1 \end{array} \qquad\Rightarrow\quad 12{,}375=(1100{,}011)_2 \]
  3. Normalisieren: \((1100{,}011)_2=(1{,}100011)_2\cdot 2^{3}\) \(\Rightarrow\) \(e=3\), \(m=(1{,}100011)_2\)
  4. Exponent mit Bias: \(\hat{e}=e+127=130=(10000010)_2\)
  5. Mantisse: führende 1 weglassen, auf 23 Bit auffüllen: \(\hat{m}=10001100000000000000000\)

\[ \underbrace{0}_{\hat{s}}\ \underbrace{10000010}_{\hat{e}}\ \underbrace{10001100000000000000000}_{\hat{m}} \;=\; (\mathrm{41460000})_{16} \]

Beispiel: IEEE 754 (32 Bit) \(\to\) Dezimal

Welche Zahl wird durch \((\mathrm{C1A40000})_{16}\) dargestellt?

  1. Bitfolge aufteilen: \((\mathrm{C1A40000})_{16}=\underbrace{1}_{\hat{s}}\ \underbrace{10000011}_{\hat{e}}\ \underbrace{01001000000000000000000}_{\hat{m}}\)
  2. Vorzeichen: \(\hat{s}=1\) \(\Rightarrow\) negative Zahl
  3. Exponent: \(\hat{e}=(10000011)_2=131\) \(\Rightarrow\) \(e=\hat{e}-127=4\)
  4. Mantisse: führende 1 ergänzen: \(m=(1{,}01001)_2=1+\frac{1}{4}+\frac{1}{32}=1{,}28125\)
  5. Zusammensetzen: \(z=-m\cdot 2^{e}=-1{,}28125\cdot 2^{4}=-(10100{,}1)_2=-20{,}5\)

Denormalisierte Darstellung

  • Normalisiert lässt sich die \(0\) nicht darstellen wegen \(1\leq{}m\)
  • Falls \(\hat{e}=(0\ldots0)\), dann denormalisiert
    • Exponent \(e=1−bias\)
    • Mantisse \(m=\hat{m}\) ohne führende \(1 z = 0, \hat{m}\)
  • Genaue Darstellung für \(0\) und Werte nahe der \(0\)
  • Durch \(1−bias\) statt \(0−bias\) sanfter Übergang zwischen denormalisiert und normalisiert

Denormalisierte Darstellung

  • Durch \(1−bias\) statt \(0−bias\) sanfter Übergang zwischen denormalisiert und normalisiert

  • Kleinste normalisierte Zahl (Betrag)

  • Größte denormalisierte Zahl (Betrag)

\[ \begin{array}{rcl} \hat{m}&=&\left(0\ldots0\right)\\ \hat{e}&=&(0\ldots1) \end{array} \]

\[ \Rightarrow \]

\[ 1.0\cdot{2}^{−126} \]

\[ \begin{array}{rcl} \hat{m}&=&\left(1\ldots1\right)\\ \hat{e}&=&(0\ldots0) \end{array} \]

\[ (0.11111111111111111111111)_{2}\cdot{2}^{−126} \] \[ =(0.99999988079071044921875)_{10}\cdot{2}^{−126} \]

Darstellung der Null

  • Kurioserweise gibt es zwei Darstellungen für die Zahl 0:

\[ \left.\begin{pmatrix}\hat{s}=0 \\ \hat{m}=\left(0\ldots0\right) \\ \hat{e}=\left(0\ldots0\right)\end{pmatrix}\right\}\Rightarrow+0 \]

\[ \left.\begin{pmatrix}\hat{s}=1 \\ \hat{m}=\left(0\ldots0\right) \\ \hat{e}=\left(0\ldots0\right)\end{pmatrix}\right\}\Rightarrow−0 \]

  • Nach IEEE 754 manchmal gleich interpretiert (bei Vergleich z.B.), manchmal unterschiedlich

Sonderfall: Über- und Unterlauf

  • Überlauf: Das Resultat einer Gleitkomma-Operation ist zu groß, um es darzustellen (bzw. zu klein, dann Unterlauf)

  • Das Ergebnis einer solchen Gleitkomma-Operation wird durch „infinity“ gekennzeichnet, Symbole \(+\infty\) oder \(−\infty\)

  • Beispiel:

\[ \frac{1}{0}=+\infty \]

\[ \frac{1}{−0}=−\infty \]

  • Im IEEE 754 wird dies durch \(\hat{m}=(0\ldots0)\) und einen
  • Exponenten \(\hat{e}=(1\ldots1)\) mit \(\hat{s}\in{0,1}\) dargestellt

Ausnahmebedingungen: NaN

  • Wenn das Resultat einer Gleitkomma-Operation keine gültige Gleitkommazahl ist, dann wird eine Sonderzahl mit der Bedeutung „not a number“ (NaN) generiert.
    • Beispiel:

\[ +\infty+\left(−\infty\right)=NaN \]

  • NaN werden durch \(\hat{m}\neq(0\ldots0)\) und einen Exponenten
  • \(\hat{e}=(1\ldots1)\) dargestellt

Approximative Darstellung

  • Es können nicht alle Zahlen dargestellt werden

  • Beispiel: \((0.1)_{10}\)

  • Nächstkleinere Zahl

\(\hat{s}=0 (1.10011001100110011001101)_{2}\cdot{2}^{−4}\)

\(\hat{e}=\left(01111011\right) =0.100000001490116119384765625\) \[ \hat{m}=(10011001100110011001101) \]

\[ (1.10011001100110011001100)_{2}\cdot{2}^{−4} \] \[ =0.0999999940395355224609375 \]

\[ \hat{s}=0 \] \[ \hat{e}=\left(01111011\right) \] \[ \hat{m}=(10011001100110011001100) \]

Approximative Darstellung

  • float a = 0.1; float b = 0.3;

  • if (a == 0.1) ergibt true

  • Aber if (a+b == 0.4) ergibt false

  • Daher Vergleich mit Epsilon-Umgebung nötig

Rechnen mit Gleitkommazahlen

  • Seien \(x={m}_{x}\cdot{2}^{{d}_{x}}\)
    \(y={m}_{y}\cdot{2}^{{d}_{y}}\)

  • Falls \({d}_{x}\leq{d}_{y}\) dann

\[ \begin{array}{rcl} x+y&=&\left({m}_{x}\cdot{2}^{{d}_{x}−{d}_{y}}+{m}_{y}\right)\cdot{2}^{{d}_{y}}\\ x−y&=&\left({m}_{x}\cdot{2}^{{d}_{x}−{d}_{y}}−{m}_{y}\right)\cdot{2}^{{d}_{y}} \end{array} \]

Rechnen mit Gleitkommazahlen

  • Seien \(x={m}_{x}\cdot{2}^{{d}_{x}}\)
    \(y={m}_{y}\cdot{2}^{{d}_{y}}\)

  • Falls \({d}_{x}\leq{d}_{y}\) dann

\[ \begin{array}{rcl} x+y&=&\left({m}_{x}\cdot{2}^{{d}_{x}−{d}_{y}}+{m}_{y}\right)\cdot{2}^{{d}_{y}}\\ x−y&=&\left({m}_{x}\cdot{2}^{{d}_{x}−{d}_{y}}−{m}_{y}\right)\cdot{2}^{{d}_{y}} \end{array} \]

  • Ebenso \(x\cdot{}y=\left({m}_{x}\cdot{m}_{y}\right)\cdot{2}^{{d}_{x}+{d}_{y}}\)

\[ \frac{x}{y}=\frac{{m}_{x}}{{m}_{y}}\cdot{2}^{{d}_{x}−{d}_{y}} \]

Beispiel: Addition zweier IEEE 754 Zahlen (1/2)

Berechne \(x+y\) für

\[ \begin{array}{rcl} x &=& \underbrace{1}_{\hat{s}}\ \underbrace{10000001}_{\hat{e}}\ \underbrace{10100000000000000000000}_{\hat{m}}\\ y &=& \underbrace{1}_{\hat{s}}\ \underbrace{10000000}_{\hat{e}}\ \underbrace{11100000000000000000000}_{\hat{m}} \end{array} \]

  1. Zerlegen: \(x\): \(\hat{s}=1\), \(e=129-127=2\), \(m=(1{,}101)_2\) \(\Rightarrow\) \(x=-(1{,}101)_2\cdot 2^{2}\)
    \(y\): \(\hat{s}=1\), \(e=128-127=1\), \(m=(1{,}111)_2\) \(\Rightarrow\) \(y=-(1{,}111)_2\cdot 2^{1}\)
  2. Exponenten angleichen: kleineren Exponenten an den größeren anpassen, d.h. Mantisse von \(y\) um \(d_x-d_y=1\) Stelle nach rechts schieben: \[ y=-(1{,}111)_2\cdot 2^{1}=-(0{,}1111)_2\cdot 2^{2} \]
  3. Vorzeichen prüfen: beide Vorzeichen negativ \(\Rightarrow\) echte Addition der Beträge, Ergebnis negativ: \[ x+y=-\left(|x|+|y|\right) \] (Bei verschiedenen Vorzeichen: Beträge subtrahieren, Vorzeichen des betragsgrößeren Operanden)

Beispiel: Addition zweier IEEE 754 Zahlen (2/2)

  1. Mantissen binär addieren: \[ \begin{array}{rccccccc} & & 1 & , & 1 & 0 & 1 & 0\\ + & & 0 & , & 1 & 1 & 1 & 1\\ \scriptsize\text{Übertrag} & \scriptsize 1 & \scriptsize 1 & & \scriptsize 1 & \scriptsize 1 & & \\ \hline & 1 & 0 & , & 1 & 0 & 0 & 1 \end{array} \qquad\Rightarrow\quad |x|+|y|=(10{,}1001)_2\cdot 2^{2} \]
  2. Normalisieren: Mantisse muss die Form \(1{,}\ldots\) haben \(\Rightarrow\) Komma um eine Stelle nach links, Exponent \(+1\): \[ (10{,}1001)_2\cdot 2^{2}=(1{,}01001)_2\cdot 2^{3} \]
  3. Ergebnis aufschreiben: \(\hat{s}=1\), \(\hat{e}=3+127=130=(10000010)_2\), \(\hat{m}=01001000000000000000000\) \[ x+y=\underbrace{1}_{\hat{s}}\ \underbrace{10000010}_{\hat{e}}\ \underbrace{01001000000000000000000}_{\hat{m}} \]

Probe: \(x=-6{,}5\), \(y=-3{,}75\) \(\Rightarrow\) \(x+y=-10{,}25=-(1{,}01001)_2\cdot 2^{3}\) ✓

Beispiel: Multiplikation zweier IEEE 754 Zahlen (1/2)

Berechne \(x\cdot y\) für

\[ \begin{array}{rcl} x &=& \underbrace{0}_{\hat{s}}\ \underbrace{10000010}_{\hat{e}}\ \underbrace{10000000000000000000000}_{\hat{m}}\\ y &=& \underbrace{1}_{\hat{s}}\ \underbrace{01111101}_{\hat{e}}\ \underbrace{01000000000000000000000}_{\hat{m}} \end{array} \]

  1. Zerlegen: \(x\): \(\hat{s}=0\), \(e=130-127=3\), \(m=(1{,}1)_2\) \(\Rightarrow\) \(x=+(1{,}1)_2\cdot 2^{3}\)
    \(y\): \(\hat{s}=1\), \(e=125-127=-2\), \(m=(1{,}01)_2\) \(\Rightarrow\) \(y=-(1{,}01)_2\cdot 2^{-2}\)
  2. Vorzeichen: unabhängig vom Rest, einfach \(\hat{s}=\hat{s}_x \oplus \hat{s}_y = 0\oplus 1 = 1\)
    • Keine Fallunterscheidung wie bei der Addition: Mantissen werden immer als Beträge multipliziert
  3. Exponenten addieren: kein Angleichen nötig! \[ e=e_x+e_y=3+(-2)=1 \] bzw. direkt mit Bias: \(\hat{e}=\hat{e}_x+\hat{e}_y-127=130+125-127=128\)

Beispiel: Multiplikation zweier IEEE 754 Zahlen (2/2)

  1. Mantissen multiplizieren: Komma im Ergebnis nach \(2+1=3\) Nachkommastellen \[ \begin{array}{llllllll} 1{,} & 0 & 1 & \cdot & 1{,} & 1 & & \\ \hline & & & & 1 & 0 & 1 & \\ & & & & & 1 & 0 & 1 \\ \hline & & & & 1{,} & 1 & 1 & 1 \end{array} \qquad\Rightarrow\quad m=(1{,}111)_2 \]
  2. Normalisieren: \(1\leq m<2\) \(\Rightarrow\) bereits normalisiert (sonst: Komma schieben, Exponent anpassen)
  3. Ergebnis aufschreiben: \(\hat{s}=1\), \(\hat{e}=1+127=128=(10000000)_2\), \(\hat{m}=11100000000000000000000\) \[ x\cdot y=\underbrace{1}_{\hat{s}}\ \underbrace{10000000}_{\hat{e}}\ \underbrace{11100000000000000000000}_{\hat{m}} \]

Probe: \(x=12\), \(y=-0{,}3125\) \(\Rightarrow\) \(x\cdot y=-3{,}75=-(1{,}111)_2\cdot 2^{1}\) ✓

Verteilung von Gleitkommazahlen

  • Vorzeichen: 1 Bit

  • Exponent: 3 Bits

  • Mantisse: 2 Bits

  • Weicher Übergang zwischen normalisierten und denormalisierten Werten

  • Präzise Verteilung um die 0

images/Kapitel 01 - Zahlendarstellung/s051_seg10_snap.png
images/Kapitel 01 - Zahlendarstellung/s051_seg11_snap.png

IEEE 754 - 64-Bit Zahlen

  • Genau wie bei den vorgestellten 32-Bit Gleitkomma-Zahlen, jedoch:

    • Der Exponent besitzt 11 Bits (vorher: 8 Bits).
    • Die Mantisse ist 52 Bits lang (vorher: 23 Bits).

  • Außerdem beschreibt IEEE 754 auch 80-Bit Gleitkomma-Zahlen mit 15-Bit Exponenten und 64-Bit Mantisse

  • x86-Architekturen verwenden interne 80-Bit Darstellung, Speicherung erfolgt in 32- oder 64-Bit

  • 64-Bit Gleitkomma-Zahlen werden auch als double bezeichnet.

Achtung: Rechnen mit Gleitkommazahlen

  • Mit \(x,y\in{}R\) ist das Ergebnis einer IEEE 754 Operation

  • \(∘ \in{+,−,\cdot,\frac{ }{} }\)definiert als \(round(x∘y)\)

  • IEEE 754 definiert nicht, wie exakt gerundet werden muss, sondern liefert Alternativen

    • Round to zero
    • Round down
    • Round up
    • Round to nearest
      • Tie to even
      • Tie away from zero

  • D.h. die gleichen 32-Bit FP-Operationen können unterschiedliche Ergebnisse liefern, obwohl korrekt (den Standard befolgend)

Beispiel: Rundung

Modus 1.40 1.60 1.50 2.50 -1.50
Round to nearest (tie to even) 1 2 2 2 -2
Round to nearest (tie away from zero) 1 2 2 3 -2
Round toward zero 1 1 1 2 -1
Round down 1 1 1 2 -2
Round up 2 2 2 3 -1

Abschnitt 1.5

Zusammenfassung

Achtung: Fehler kosten (viel) Geld

  • Ariane 5 stürzte 37 Sekunden nach dem Start ab
  • Kosten in Höhe von mehreren Hundert Millionen US-Dollar
images/Kapitel 01 - Zahlendarstellung/s056_seg08_83c76923.jpg
images/Kapitel 01 - Zahlendarstellung/s056_seg08_574719fe.jpg
  • Was ist passiert?
  • Konvertierung eines 64-Bit Floats in einen 16-Bit Signed Integer hat zu einem Überlauf geführt

Quelle: http://www.capcomespace.net/dossiers/espace_europeen/ariane/ariane5/AR501/V88_AR501.htm

Zusammenfassung

  • Darstellung von natürlichen und ganzen Zahlen sowie deren wichtigsten Rechenoperationen
  • BCD-Kodierung
  • Festkommadarstellung und IEEE 754 Fließkommadarstellung
  • Wichtig: Operationen verhalten sich nicht immer wie erwartet

Literatur

  • W. Kahan: An Interview with the Old Man of Floating-Point (https://people.eecs.berkeley.edu/~wkahan/ieee754status/754story.html)

  • D. Goldberg: What Every Computer Scientist Should Know About Floating-Point Arithmetic. In: ACM Computing Surveys. 23, 1991, S. 5-48 (http://docs.sun.com/source/806-3568/ncg_goldberg.html)

  • R. Bryant, D. O‘Hallaron: Computer Systems – A Programmer‘s Perspective (Chapter 2). Prentice Hall