TU Wien:Technische Grundlagen der Informatik VU (Kastner)/Kapitel Zahlendarstellung

• 01 Zahlendarstellung
• 02 Numerik
• 03 Codierung
• 04 Informationstheorie
• 05 Boolesche Algebra
• 06 KV-Diagramme und BDD
• 07 Moore- & Mealy-AutomatenTGI+GDS

  ---

• 08 Digitalschaltungen, KominatorikTGI
• 09 Sequentielle Logik
• 10 Speicher
• 14 Micro16
• 15 Befehlssatz
• 16 Pipelining
• 17 Speichermanagement
• 18 Chipsatz
• 19 Multi-Core
• 20 Netzwerke

Zahlensysteme

Zahlschrift

Die Zahlschrift besteht aus einzelnen Zeichen denen ein Wert zugeordnet ist. Sie sind miteinander kombinierbar. Darunter fallen etwa die römischen Zahlen, die kumulativ-additiv sind; XIII = 10 + 1 + 1+ 1 = 13.

Die Schreibweise, die sich durchgesetzt hat, ist die Indisch-arabische, beziffernd-positionell ist und die Basis 10 hat; 1x10 + 3x1 = 13.

Dezimalsystem

Das Dezimale Zahlensystem, auch Zehnersystem genannt, ist ein Stellenwertsystem, wo die (additive) Wertigkeit eines Symbols von seiner Position, der Stelle, abhängt. Das Dezimalsystem wurde in Indien um 600 n. Chr. entwickelt und später im gesamten arabisch beeinflussten Raum verbreitet.

Ihre Darstellung erfolgt durch

• die Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

• an bestimmten Stellen (Einer, Zehner, Hunderter, Tausender, …) und

• hat die Basis 10.

Allgemeine Stellenwertsysteme

Die Basis b ist die Anzahl der verwendeten Ziffern. Um den Wert der Zahl (…a₃, a₂, a₁, a₀) zu erhalten, multipliziert man sie mit dem Wert der Stelle (…b³, b², b¹, b⁰). Nachkommastellen werden mit negativen Tief-/Hochzahlen dargestellt.

$(...a_{3}a_{2}a_{1}a_{0}.a_{-1}a_{-2}...)_{b}=...+a_{3}b^{3}+a_{2}b^{2}+a_{1}b^{1}+a_{0}b^{0}+a_{-1}b^{-1}+a_{-2}b^{-2}...$

Binäres Zahlensystem

Ein Zahlensystem mit der Basis 2 nennt man binäres Zahlensystem. Es wird mit den Ziffern 0 und 1 dargestellt, man kann aber auch L (Low) und H (High) verwenden.

Hexadezimales Zahlensystem

Ein System mit Basis 16 wird hexadezimales Zahlensystem genannt. Neben den üblichen Ziffern verwendet es auch die Buchstaben A bis F, wobei jedem einzelnen ein Wert zugewiesen ist.

A = 10, B = 11, C = 12, D = 13, E = 14, F = 15

---

Zahlenumwandlungen

Um von einem Quellsystem in ein Zielsystem umzuwandeln müssen Zahlen mit Nachkommastellen (reelle Zahlen) in ihren Vor- und Nachkommateil aufgeteilt werden. Danach werden beide getrennt umgerechnet.

Vorkommateil

Von Dezimal in ein anderes System

Hierzu muss einfach die dezimale Zahl modulo der Basis des Zielsystems genommen werden. Den Rest von unten nach oben aneinandergereiht ergibt die Zahl im gewünschten System. Der Vorgang wird abgebrochen, wenn nicht weiter dividiert werden kann.

$\left.{\begin{array}{r}21\,{\bmod {\,}}8=5\\2\,{\bmod {\,}}8=2\end{array}}\right\uparrow$ (21)₁₀ = (25)₈

$\left.{\begin{array}{r}21\,{\bmod {\,}}16=5\\1\,{\bmod {\,}}16=1\end{array}}\right\uparrow$ (21)₁₀ = (15)₁₆

Zurück ins Dezimalsystem

$(25)_{8}\to (...)_{10}\ mit\ Hornerschema\colon \ (2\cdot 8+5)=21$ $(101\ 010)_{2}\to (...)_{10}\ mit\ Hornerschema\colon \ ((((1\cdot 2+0)\cdot 2+1)\cdot 2+0)\cdot 2+1)\cdot 2+0=42$ $(101\ 010)_{2}\to (...)_{10}\ mit\ VarianteB\colon \ 1\cdot 2^{5}+0\cdot 2^{4}+1\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+0\cdot 2^{0}=42$

Größeres Zahlensystem nach Kleineres

Die Zahl mit der größeren Basis wird modulo der Basis des kleineren Systems genommen. Dabei ist zu beachten, wenn das Zielsystem eine Potenz des Ursprungssystems ist, so ist je eine Ziffer des Ursprungs so viele Ziffern im Zielsystem wie die Hochzahl.

$(5E)_{16}\to (...)_{2}\ \ \ 16=2^{4}$
$\left.{\begin{array}{r}5\,{\bmod {\,}}2=1\\2\,{\bmod {\,}}2=0\\1\,{\bmod {\,}}2=1\end{array}}\right\uparrow$ $\left.{\begin{array}{r}14\,{\bmod {\,}}2=1\\7\,{\bmod {\,}}2=0\\3\,{\bmod {\,}}2=1\\1\,{\bmod {\,}}2=1\end{array}}\right\uparrow$

Da je eine Hexadezimalzahl vier Binärziffern ergibt, muss eine Null vorne angehängt werden.

$(5E)_{16}\to (0101\ 1110)_{2}$

$(58)_{9}\to (...)_{3}\ \ \ 9=3^{2}$
$\left.{\begin{array}{r}5\,{\bmod {\,}}3=2\\1\,{\bmod {\,}}3=1\end{array}}\right\uparrow$ $\left.{\begin{array}{r}8\,{\bmod {\,}}3=2\\2\,{\bmod {\,}}3=2\end{array}}\right\uparrow$

$(58)_{9}\to (1222)_{3}$

Kleines Zahlensystem nach Größeren

Ist das Zielsystem kleiner als das Ursprungssystem, und möchte man keinen Umweg über das Dezimalsystem machen, muss man sich die Basen ansehen. Ist die kleinere Basis eine Potenz der Größeren, so können je Hochzahl mal Ziffern des Ursprungssystems in das Zielsystem umgewandelt werden.

$(2223)_{4}\to (...)_{16}\ \ \ 4^{2}=16$
$(2\cdot 4^{3}+2\cdot 4^{2})\ \thicksim \ (2\cdot 4^{1}+3\cdot 4^{0})=$
$=(2\cdot 4\cdot 16+2\cdot 16)\ \thicksim \ (2\cdot 4+3\cdot 1)=$
$=16\cdot (2\cdot 4+2)\ \thicksim \ (8+3)=$
$=16\cdot (10)\ \thicksim \ (11)=10\ 11$
$(2223)_{4}\to (AB)_{16}$

Nachkommateil

Zurück ins Dezimal

(0,011)₂

${\begin{array}{l}Variante\ A\colon \\1\cdot 1=1\\1\cdot 2=2\\0\cdot 4=0\end{array}}$ ${\begin{array}{l}1+2=3\\3\div 8=0{,}375\end{array}}$

${\begin{array}{l}Variante\ B\colon \\2^{-1}\to 0{,}5\cdot 0=0\\2^{-2}\to 0{,}25\cdot 1=0{,}25\\2^{-3}\to 0{,}125\cdot 1=0{,}125\\\end{array}}$ ${\begin{array}{l}0{,}25+0{,}125=0{,}375\end{array}}$

Von Dezimal in ein anderes System

Hier wird die Gleitkommazahl mit der Basis des Zielsystems multipliziert. Dabei entsteht entweder ein Vorkommateil ungleich Null oder bleibt als Null bestehen, dieser wird als Ziffer des Zielsystems genommen und zwar von oben nach unten. Der Vorgang wird abgebrochen, wenn das Ergebnis 0 ist oder gemäß Vorgabe, falls keine endliche Entwicklung.

$(0{,}8)_{10}\to (...)_{2}$
$\left.{\begin{array}{l}0{,}8\cdot 2=1{,}6\to 1\\0{,}6\cdot 2=1{,}2\to 1\\0{,}2\cdot 2=0{,}4\to 0\\0{,}4\cdot 2=0{,}8\to 0\\0{,}8\cdot 2=1{,}6\to 1\\0{,}6\cdot 2=1{,}2\to 1\\0{,}2\cdot 2=0{,}4\to 0\end{array}}\right\downarrow$
$(0{,}8)_{10}\to (0{,}1100\ 110...)_{2}$

$(0{,}8)_{10}\to (...)_{16}$
$\left.{\begin{array}{l}0{,}8\cdot 16=12{,}8\to 12\\0{,}8\cdot 16=12{,}8\to 12\end{array}}\right\downarrow$
$(0{,}8)_{10}\to (0{,}CC...)_{16}$

Umwandeln ohne Dezimalsystem

Hier erfolgen die Rechenschritte wie oben beim Vorkommateil. Auch hier muss darauf geachtet werden, welches System größer ist und ob Potenzen existieren. Hat ein System weniger Ziffern als benötigt, muss, von der Kommastelle weg, eine Null angehängt werden.

$(0{,}41)\to (...)_{3}\ \ \ 9=3^{2}$
$\left.{\begin{array}{r}4\,{\bmod {\,}}3=1\\1\,{\bmod {\,}}3=1\end{array}}\right\uparrow$ $\left.{\begin{array}{r}1\,{\bmod {\,}}3=1\\(0\,{\bmod {\,}}3=0)\end{array}}\right\uparrow$
$(0{,}41)\to (0{,}1101)_{3}$
Eine Null muss vor die letzte Eins gestellt werden, da je eine Ziffer der Basis 9 zwei Ziffern der Basis 3 ergeben.

$(0{,}11101)_{2}\to (...)_{4}\ \ \ 2^{2}=4$
$(1\cdot 2^{5}+1\cdot 2^{4})\ \thicksim \ (1\cdot 2^{3}+0\cdot 2^{2})\ \thicksim \ (1\cdot 2^{1}+0\cdot 2^{0})=$
Eine Null muss in der letzten Klammer angehängt werden, da je zwei Ziffern der Basis 2 eine Ziffer der Baisis 4 ergeben. $=(2+1)\ \thicksim \ (2+0)\ \thicksim \ (2+0)=(0{,}322)_{10}$

---

Rechnen im binären System

Addition

Die Addition im Binärsystem ist dem im Dezimalsystem sehr ähnlich. Die Ziffern werden von rechts nach links aufaddiert. Zwischenergebnisse werden unten notiert, jedoch nur die letzte Stelle. Die erste Stelle, der Übertrag, muss beim Ausarbeiten der jeweils nächsten Spalte berücksichtigt werden. Die Additionsregeln im binären Zahlensystem sind wie folgt:

${\begin{aligned}0+0&=0&&\ &\ 110110\\0+1&=1&&+&\ 011011\\1+0&=1&&=&1010001\\1+1&=10\end{aligned}}$

Bei $1+1$ wird jedoch nur die letzte Ziffer $0$ unten notiert und der Übertrag $1$ zur nächsten Spalte dazugerechnet.

Subtraktion

Falls bei der Subtraktion zweier Ziffern, die Ziffer des Minuenden kleiner als die des Subtrahenden ist, muss von der höherwertigen Stelle eine Zahl im Wert der Basis ausgeborgt werden. Der Minuend wird um diesen Wert erhöht und das Zwischenergebnis der Subtraktion der Ziffern wird angeschrieben. Anschließend wird der höherwertige Subtrahend um eins erhöht.

${\begin{aligned}0-1&={\color {Red}{\boldsymbol {1}}}\\1-1&=1&&\\1-0&=0&&\\0-{\color {Red}{\boldsymbol {1}}}&={\color {Red}{\boldsymbol {1}}}\\1-{\color {Red}{\boldsymbol {1}}}&={\color {Red}{\boldsymbol {1}}}\\1-{\color {Red}{\boldsymbol {0}}}&=0\end{aligned}}$

Die obigen gekennzeichneten Ziffern sind Positionen mit Übertrag oder ergeben zusätzlich einen Übertrag.

Multiplikation

Die Multiplikation im binären Zahlensystem ist einfacher, da es nur 2 Zahlen besitzt. Man kann dieselbe Methode wie bei den Dezimalzahlen verwenden. Zeilen, die durch die Multiplikation mit 0 entstehen, können auch weggelassen werden, jedoch muss man die folgende Zeile entsprechend einrücken. Die Regeln lauten:

${\begin{aligned}0\cdot 0&=0\\0\cdot 1&=0\\1\cdot 0&=0\\1\cdot 1&=1\end{aligned}}$

Für die Implementierung im Rechner ist es günstiger, mit der am weitesten rechts stehenden Ziffer des Multiplikators zu beginnen. Die Teilergebnisse werden dadurch nach links verschoben. So müssen nicht alle Zwischenergebnisse gespeichert werden und jedes Teilergebnis kann sofort zum Endergebnis addiert werden. Dies ermöglicht eine effizientere Implementierung.

Division

Bei der Division wird entschieden, ob der Divisor kleiner oder gleich eines Teils des Dividenden ist. Ist die Antwort „ja“ so ist die Quotientenziffer $1$, ansonsten $0$.

Runden

Die allgemeine Regel beim Runden von binären Faktoren zur n-ten Stelle ist, dass man die darauffolgende Ziffer betrachtet. Ist die Ziffer $0$, dann sollte die Zahl immer abgerundet werden. Ist sie stattdessen $1$ und min. eine folgenden Ziffern auch $1$ ist, dann sollte die Zahl aufgerundet werden. Falls aber alle folgenden Ziffern $0$ sind, dann kommt „ties to even“ ins Spiel. Diese Regel sagt, dass man zur Ziffer, die $0$ an der $n$-ten Stelle hat, runden soll.

• $0{,}11\mid 001\ =$ rundet runter zu $0{,}11$, da die Ziffer and der dritten Stelle $0$ ist.
• $0{,}11\mid 101\ =$ aufrunden zu $1{,}00$, da die Ziffer an der dritten Stelle $1$ ist und eine folgende Ziffer $1$ ist.
• $0{,}11\mid 100\ =$ "ties to even"; aufrunden zu $1{,}00$, da die Ziffer an dritter Stelle $1$ ist und die folgende $0$.
• $0{,}10\mid 001\ =$ "ties to even"; abrunden zu $0{,}10$

Darstellung negativer Zahlen

Vorzeichen und Betrag

Bei dieser Darstellung wird das positive Vorzeichen mit $0$ dargestellt und das negative Vorzeichen mit einer $1$. Die restlichen Bits sind der Betrag der darzustellenden Zahl. Vorzeichen müssen getrennt vom Betrag behandelt werden. Die Ordnungsrelation gilt nur innerhalb der positiven Zahlen. Negative Zahlen werden hinten einfach angeknüpft. Die Zahl $0$ besitzt daher zwei Darstellungen $(+0/-0)$

Einerkomplement

Hier unterscheiden sich negative Zahlen von den positiven durch das Vertauschen von $0$ und $1$ im Betrag und Vorzeichen. Der Ausgangspunkt ist immer der positive Betrag der Zahl. Auch hier besitzt $0$ zwei Darstellungen Positive und negative Zahlen können am führenden Bit unterschieden werden.

${\begin{aligned}+27&&00011011\\-27&&11100100\end{aligned}}$

Die Ordnungsrelation gilt getrennt innerhalb der positiven und negativen Zahlen, aber auch hier werden die negativen Zahlen „hinter“ den positiven positioniert. Denkt man sich die Zahlen auf einem Kreis angeordnet, erkennt man, dass aufgrund der zweifachen Darstellung der $0$ Probleme auftreten können. Daher muss bei einem Überlauf $1$ addiert werden.

Eine tatsächliche Überschreitung des Zahlenbereiches kann durch einen Plausibilitätstest des Vorzeichens erkannt werden. Z. B. kann die Summe zweier negativer Zahlen nicht positiv sein, also muss bei der Addition ein wirklicher Überlauf entstanden sein.

Zweierkomplement

Bei der Zweierkomplementdarstellung ist der Ausgangspunkt das Einerkomplement der Zahl. Bei der Berechnung negativer Zahlen muss eine $1$ dazu addiert werden.

Alternativ können die binären Ziffern der positiven Zahl von rechts nach links exkl. der ersten $1$ kopiert werden und die restlichen Ziffern werden komplementiert.

$00011011\to 1110010{\boldsymbol {1}}$

Die Ordnungsrelation ist wie beim Einerkomplement. Jedoch hat die Zahl $0$ eine eindeutige Darstellung, wodurch man Überläufe bei Rechnungen ignorieren kann. Positive und negative Zahlen können am führenden Bit unterschieden werden. Eine tatsächliche Überschreitung des Zahlenbereiches kann wieder durch einen Plausibilitätstest des Vorzeichens erkannt werden.

Bei der Multiplikation müssen die Faktoren vor Durchführung der Rechenoperation um 2mal der ursprünglichen Bitstellen erweitert werden. Dabei ist zu beachten, dass positive Zahlen mit Nullen und negative mit Einsern ergänzt werden müssen, um das Vorzeichen nicht zu zerstören.

Exzessdarstellung

Bei dieser Darstellung wird ein Exzess $e$ addiert, sodass Zahlen nicht mehr negativ sind. Das heißt, dass Zahlen in Exzessdarstellung um $e$ größer sind als sie eigentlich sind. Exzess ergibt sich aus dem Betrag der kleinsten negativen Zahl. Bei einem symmetrischen Exzess liegt die $0$ halbwegs in der Mitte des Zahlenstrahls. Die Darstellung ist ordnungshaltend; kleinere Zahlen sind auch in Exzessdarstellung kleiner. Die Zahl $0$ hat eine eindeutige Darstellung. Ist die Darstellung nicht symmetrisch, wird trotzdem die kleinste darstellbare negative Zahl als Exzess verwendet.

Rechenoperationen

Bei Additionen muss der Exzess von der Summe subtrahiert werden und bei Subtraktionen zur Summe addiert.

Nützliche Links

• Online-Umrechner für verschiedene Zahlensysteme [1]
• Binär-Rechner [2]
• Umrechnung von Zahlensystemen mit Erklärung [3]

Quellen

Erster TGI-Foliensatz "Zahlendarstellung"

Blieberger, J.; Burgstaller, B.; Schildt, G.-H.: Informatik, Grundlagen, 2011. Fünfte Auflage.