In diesem Kapitel befassen wir uns mit Zahlen, Information und ihrer Codierung.

Zahlensysteme und die Darstellung von Zahlen

Bearbeiten

Rechnen in verschiedenen Zahlensystemen

Bearbeiten
binär (dual) 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000
oktal 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20
dezimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
hexadezimal 0 1 2 3 4 5 6 7 8 9 A B C D E F 10

Anwendungsbeispiele

Bearbeiten
Hex. Dualsystem Dez.
0 0 0 0 0 00
1 0 0 0 1 01
2 0 0 1 0 02
3 0 0 1 1 03
4 0 1 0 0 04
5 0 1 0 1 05
6 0 1 1 0 06
7 0 1 1 1 07
8 1 0 0 0 08
9 1 0 0 1 09
A 1 0 1 0 10
B 1 0 1 1 11
C 1 1 0 0 12
D 1 1 0 1 13
E 1 1 1 0 14
F 1 1 1 1 15

Oktalsystem

Bearbeiten

Unix-Dateirechte lassen sich mit dem Befehl chmod ändern. Dabei kann u.a. eine oktale Notation verwendet werden (siehe Manual Page, man man: man chmod):

chmod 0644 DATEI

chmod 0755 VERZEICHNIS

Mit einer oktalen Ziffer 0 … 7 werden dabei jeweils 3 Bits, (für rwx bzw. setuid bit, setgid bit, und sticky bit) gesetzt.

Hexadezimalsystem

Bearbeiten

Zahlensysteme des Rechners

Bearbeiten

Bytes in Binärschreibweise darzustellen erfordert viele Ziffern und wird schnell unübersichtlich. Darum stellt man meist ein halbes Byte, also vier Bit, mit einer hexadezimalen Ziffer dar. Man bezeichnet ein halbes Byte als Nibble. Ein Nibble kann die Werte 0 bist 15 annehmen, was genau den möglichen Werten einer hexidezimalen Ziffer entspricht. Wenn klar ist, um welches Zahlensystem es sich handelt, wird die Vorsilbe 0b oder 0x meist weggelassen.

Beispiele:

0b11111111 = 0xff
0b11110000 = 0xf0
0b00001111 = 0x0f
0b10101010 = 0xaa
0b01010101 = 0x55
0b11010101 = 0xd5

Darstellung und Analyse von Binärdaten (siehe auch: Hexdump, man echo, man xxd, man hexdump):

echo Text | xxd
echo -n Text | xxd
echo Text | xxd
echo  Text | hexdump -C
hexdump -C DATEI

Gleitkommazahlen

Bearbeiten

FIXME IEEE 754

Kodierung von Information

Bearbeiten
 
Dateiformate können schnell etwas unübersichtlich werden.

Rechner können nur mit Zahlen arbeiten. Daher muss Information in Zahlen „übersetzt“, d.h. kodiert werden, um sie auf Rechnern verarbeiten und in Dateien speichern zu können. Ohne Kenntnis dieser Kodierung, d.h. ohne Kenntnis der Übersetzung Daten ⟷ Information ist die Datei wertlos und stellt nur eine Aneinanderreihung von Zahlen, d.h. Bits und Bytes, dar.

Dateiformate

Bearbeiten

Dieser Abschnitt wurde bereits im Kapitel Dateiformate im Wikibook Informationstechnische Grundlagen behandelt und soll hier nicht noch einmal abgehandelt werden.

Aufgabe: Arbeite den Abschnitt Dateiformate durch!

Dateiformate erkennen

Bearbeiten

Das Dateiformat kann man oft (und je nach Betriebssystem ist das die (einzige) Methode der Wahl) durch Interpretation der Dateiendung erkennen. Diese lässt sich aber durch umbenennen der Datei leicht ändern. Ein besseres Verfahren zur Bestimmung des Dateiformats ist:

  • Interpretation von Metadaten, oder
  • Interpretation des Dateiinhalts.

Das auf GNU/Linux oder Unix Systemen vorhandenen Kommando file arbeitet mit genau diesen Verfahren. Details findet man in der Manual-Page mit man file.

Rechnen mit Binärzahlen

Bearbeiten
 
Überlauf eines Kilometerzählers.

Computer rechnen: Die Verarbeitung von Information erfolgt durch logische und arithmetisch Operationen. Dazu besitzt jeder Rechner eine „arithmetisch-logische Einheit“ (arithmetic logic unit (ALU)), die aus Bits und Bytes andere Bits und Bytes erzeugt. Wir betrachten hier exemplarisch die Addition und Subtraktion zweier Zahlen.

Addition

Bearbeiten

Wir können Binärzahlen addieren, indem wir stellenweise vorgehen und entstehende Überträge bei der nächsten Stelle berücksichtigen.

Addition zweier positiver Binärzahlen (rechts bei 4 Bit-Zahler Überlauf)

 

 

Dies ist elektronisch über ein Addierwerk leicht zu realisieren, allerdings müssen wir beachten, dass je nach Datentyp möglicherweise das Ergebnis unserer Rechnung nicht mehr darstellbar ist. So „passt“ im Beispiel das Ergebnis nicht mehr in 4 Bit. Es kommt zum arithmetischen Überlauf (Zählerüberlauf). Je nachdem ob Vorkehrungen getroffen wurden, um einen solchen Zählerüberlauf adäquat zu behandeln, kann es weitreichende Folgen haben, wenn der Zähler „plötzlich“ wieder bei 0 anfängt und es gibt in der Geschichte bereits viele Beispiele für bereits erfolgte Überläufe (oder verwandte Problematiken) als auch noch zu erwartende:

Das Zweierkomplement

Bearbeiten
 
Darstellung des Zweierkomplements bei einer Ganzzahl aus vier Bit.
 
Darstellung des Zweierkomplements bei einer Ganzzahl aus drei Bit.

Bevor wir Zahlen subtrahieren, müssen wir uns überlegen, wie wir negative Zahlen darstellen. Wie wir im Folgenden sehe werden, bietet ich dazu das Zweierkomplement an. Beim Zweierkomplement bekommt der Wert des höchstwertigen Bits ein negatives Vorzeichen, also bei acht Bit den Wert -2⁷ = -128, bei vier Bit den Wert -2³ = -8.

Stelle 8 7 6 5 4 3 2 1
Unsigned Integer (vorzeichenlose Ganzzahl) 2⁷ = 128 2⁶ = 64 2⁵ = 32 2⁴ = 16 2³ = 8 2² = 4 2¹ = 2 2⁰ = 1
Signed Integer (vorzeichenbehaftete Ganzzahl) -2⁷ = -128 2⁶ = 64 2⁵ = 32 2⁴ = 16 2³ = 8 2² = 4 2¹ = 2 2⁰ = 1

Damit können nun z.B. mit einem Byte die folgenden Zahlen dargestellt werden:

-128 = 0b10000000
-127 = 0b10000001
-1 = 0b11111111
 0 = 0b0
 127 = 0b01111111

Subtraktion

Bearbeiten
 
Darstellung des Jahr-2038-Problems:
Zeile 1: Zeitdarstellung im Binärsystem
Zeile 2: die dazugehörige Dezimalzahl
Zeile 3: Fehlerhafte Darstellung der Zeit
Zeile 4: Korrekte Zeitangabe

Die Darstellung negativer Zahlen durch das Zweierkomplement erlaubt die Subtraktion auf die Addition zurückzuführen. Wir subtrahieren, indem wir das Zweierkomplement addieren und den Überlauf ignorieren:

Subtraktion als Addition von Binärzahlen verschiedenen Vorzeichens

 

 

Wie bei der vorzeichenlosen Addition müssen wir dabei aber sicherstellen, dass das Ergebnis durch die für den gewählten Datentyp zur Verfügung stehenden Bits darstellbar ist. Ansonsten wird das Ergebnis falsch interpretiert, erhält falschen Wert und Vorzeichen. Entsprechend springt ein Zähler nach seinem höchsten positiven Wert 0b011…111 auf den kleinsten, negativen Wert 0b100…000.

 -6 + (-3) = -9 entspricht:
   0b1010
+  0b1101
---------
= 0b10111  wäre -16 + 7 = -9, aber bei Beschränkung auf 4 Bit: 0b0111 = 7      


Aufgaben

Bearbeiten

Zahlensysteme

Bearbeiten

Umrechnen von Zahlen

Bearbeiten

Rechne die folgenden Zahlen jeweils in zwei andere Zahlensysteme um:

64, 1024, 2021, 0b1111, 0xA, 0xF, 0b01010101, 0b11010101, 0xAFFE, 0xCAFE, 0xBEEF, 111, 0x111, 0xFE, 0o644, 0o755, 0o1777, 0o4777, 0o7777

Überprüfe die Ergebnisse mit Python.

Darstellung von Bytes mit Hexadezimalzahlen

Bearbeiten

Zur Darstellung von Bytes verwenden wir pro Byte zwei hexadezimale Ziffern, 0, 1, …, 9, A, B, C, D, E, F. Wir stellen damit jeweils vier Bit, also ein Nibble dar. Warum hat man sich nicht für die Darstellung eines Bytes mit einer Ziffer entschieden?

Unix-Zugriffsrechte im Oktalmode

Bearbeiten
  1. Erzeuge eine Datei mit touch datei. Setze mit z.B. chmod 644, chmod 755 unterschiedliche Dateirechte für den Besitzer (user), die Gruppe (group) und alle anderen (others). Untersuche das Ergebnis mit ls -l datei.
  2. (↯) Erzeuge ein Verzeichnis mit mkdir verzeichnis und setze die Dateirechte mit chmod 1777 verzeichnis. Welche Bedeutung haben diese Zugriffsrechte und welches Verzeichnis hat üblicherweise genau diese gesetzt? Untersuche mit ls -ld verzeichnis, ls -ld /tmp.

Dateiformate und Kodierung

Bearbeiten

ASCII–Format

Bearbeiten
Binärer Inhalt einer Datei:
4772 6174 756c 6174 696f 6e2c 2044 7520
6861 7374 2064 6965 7365 7320 4461 7465
6966 6f72 6d61 7420 6572 666f 6c67 7265
6963 6820 656e 7473 6368 6c75 6573 7365
6c74 210a 4461 7320 4153 4349 492d 466f
726d 6174 2065 6967 6e65 7420 7369 6368
207a 756d 2073 7065 6963 6865 726e 2065
696e 6661 6368 6572 2054 6578 742d 4461
7465 6965 6e20 6f68 6e65 2055 6d6c 6175
7465 2e0a
  1. Eine Datei ist im ASCII–Format gespeichert, ihr binärer Inhalt ist rechts im Hexadezimalsystem dargestellt. Dekodiere diesen Inhalt. Welche Vorteile hat die UTF-8–Kodierung im Vergleich zur ASCII–Kodierung?
  2. Das ASCII–Format ordnet u.a. jedem Buchstaben eine Zahl zu. Damit können wir Text in Zahlen umwandeln und mit dem Rechner verarbeiten. Wie kann man die Information eines Bildes in Zahlen beschreiben und damit der digitalen Verarbeitung zugänglich machen?
  3. ASCII–Kodierung verwendet 7 Bit, das verbleibende 8. Bit hat immer den Wert 0. Welche Hexadezimalzahl kann demnach maximal für das höherwertige Nibble eines Bytes auftreten?
  4. Arbeite den Abschnitt Dateiformate im Wikibook ITG durch.

Rastergrafik

Bearbeiten

Wir untersuchen eine Rastergrafik im Bitmap .bmp Format.

  1. Erzeuge mit dem Bildbearbeitungsprogramm GIMP ein 3×2 Pixel kleines „Bild“ und speichere es als Bitmap .bmp. Wähle beim Abspeichern 24 Bit Farbauflösung ‚R8 G8 B8‘.
  2. Finde heraus, welche Bytes der Bilddatei zum Pixel oben links, welche zum Pixel unten rechts gehören. Untersuche dazu die erzeugte Datei mit einem Hex-Editor (z.B. Emacs: Alt-x, hexl-mode; oder auch xxd, hexdump) und verändere einzelne Pixel.
  3. Ordne die Farbkanäle Rot, Grün, Blau eines Pixels den jeweiligen Bytes zu.
  4. Untersuche den Datei-Header und vergleiche mit dem Bitmap .bmp-Format.

Vektorgrafik

Bearbeiten

Wir untersuchen eine Vektorgrafik im Scalable-Vector-Graphics-Format .svg.

  1. Erzeuge mit dem Bildbearbeitungsprogramm Inkscape eine Grafik mit einem Kreis und einer Linie.
  2. Untersuche, wie die Information dieses mal kodiert ist. Ändere dazu Eigenschaften der Figuren in Inkscape und direkt in der .svg-Datei.
  3. Diskutiere Vor- und Nachteile von Raster- und Vektorgrafik.

Büro-Dokument

Bearbeiten
  1. Erstelle ein Office-Textdokument mit etwas Text und einem Bild.
  2. Such Informationen über das Format, in dem die Datei abgespeichert wurde.
  3. Wende den Befehl unzip auf die abgespeicherte Datei an und untersuche das Ergebnis.
  4. Ändere Inhalte und füge sie anschließend mit dem Befehl zip wieder zu einer einzelnen Datei zusammen. Prüfe das Ergebnis mit dem ursprünglichen Textverarbeitungsprogramm nach.

Dateiformate mit file

Bearbeiten
  1. Rufe man file auf und schaue die Beispiele an.
  2. Wende file auf einige bekannte Dateien an und betrachte die Ausgabe: file DATEI.TYP
  3. Vertausche die Dateiendungen und führe file DATEI.FALSCHERTYP aus. Vergleiche mit dem vorherigen Aufruf bei korrekten Dateiendung.

Rechnen mit Binärzahlen

Bearbeiten

Untersuche den Zählerüberlauf mit Python anhand folgender Beispiele:

$ python3
>>> from numpy import int8, uint8  ## lade die Datentypen 8-Bit Ganzzahl mit/ohne (unsigned) Vorzeichen
>>> uint8(0b111111111)
255
>>> uint8(256)
0
>>> uint8(257)
1
>>> int8(0b10000000)
-128
>>> int8(127)
127
>>> int8(128)
-128