Codierung digitaler Daten

Zuerst werden wir uns mit der digitalen Darstellung von Zahlenwerten als elementaren Daten in verschiedenen Zahlensystemen beschäftigen, insbesondere im Binärsystem.

Als Aufgabe zum Einstieg vorweg: Der Bahnhof St. Gallen in der Schweiz besitzt seit 2018 eine Uhr der besonderen Art. Finden Sie heraus, wie spät es auf diesem Bild gerade ist? Als Tipp: Die obere Zeile stellt die Stunden dar, die mittlere die Minuten und die untere die Sekunden.

Bits und Bytes

Die einfachste Form der digitalen Darstellung ist die Binärdarstellung, in der nur zwei verschiedene Werte verwendet werden, die üblicherweise als 0 und 1 dargestellt werden. Diese kleinste digitale Informationseinheit wird als Bit bezeichnet. Binärdaten werden durch Bitfolgen, also Folgen von Nullen und Einsen dargestellt.

Digitale Daten lassen sich dabei immer auch durch Binärdaten repräsentieren, indem jedem der abzählbar vielen Werte eine eindeutige Bitfolge zugewiesen wird.

Beispiel: Die Minuten einer digitalen Uhrzeit können 60 verschiedene Werte annehmen. Jeder Minutenwert lässt sich binär mit 6 Bit beschreiben, da eine Bitfolge der Länge 6 insgesamt 2⁶ = 64 verschiedene Zustände einnehmen kann.

Die Binärdarstellung ist besonders relevant, da Rechner Daten intern als Bitfolgen speichern und verarbeiten. Üblicherweise verarbeiten Rechner Bits aber nicht einzeln, sondern in 8-Bit-Blöcken. Ein solcher 8-Bit-Block wird als Byte bezeichnet und kann entsprechend 2⁸ = 256 viele Zustände einnehmen, die sich als Ganzzahlen von 0 bis 255 interpretieren lassen.

Die Binärdarstellung von Zahlen ist in vielen Anwendungsfällen hilfreich, beispielsweise um Daten im Speicher zu interpretieren, die Funktionsweise eines Rechners auf Hardwareebene zu verstehen, die Kommunikation zwischen Rechnern in Netzwerken oder die Adressierung von Rechnern in hierarchischen Rechnernetzen nachzuvollziehen.

Binärzahlen

Wenn wir binäre Daten untersuchen, macht es Sinn, die einzelnen Werte nicht im Dezimalsystem, sondern als Binärzahl darzustellen, also im Dualsystem (“Zweiersystem”), dem Stellenwertsystem zur Basis 2. Im Dualsystem werden Zahlen nur mit den beiden Ziffern 0 und 1 dargestellt. Die Stellenwerte sind durch die Potenzen der Basis 2 festgelegt, also (von rechts nach links) 2⁰ = 1, 2¹ = 2, 2² = 4, … – analog zu den Stellenwerten im Dezimalsystem: 10⁰ = 1, 10¹ = 10, 10² = 100, …

Die folgende Tabelle stellt die Zweierpotenzen bis 2¹⁶ dar, um einen Eindruck von den Größenordnungen zu bekommen:

Um eine Binärzahl in eine Dezimalzahl umzuwandeln, werden die Ziffern mit den entsprechenden Stellenwerten (= Zweierpotenzen) multipliert und summiert (oder einfacher: Es werden diejenigen Zweierpotenzen summiert, an deren Stellen die Ziffer 1 steht).

Tool: In dieser interaktiven Anzeige können Sie die Binärdarstellung von Ganzzahlen selbst untersuchen. Klicken Sie auf die oberen Binärziffern, um ihre Werte zu ändern.

In der Binärdarstellung entspricht jede Ziffer einem Datenbit. Ein Byte ist also durch eine Binärzahl mit 8 Stellen repräsentiert (ggf. mit führenden Nullen).

Beispiel: Die Binärzahl 00101010 entspricht der Dezimalzahl 2⁵ + 2³ + 2¹ = 32 + 8 + 2 = 42.

Um eine Dezimalzahl ins Binärsystem umzuwandeln, wird die Zahl wiederholt mit Rest durch die Basis 2 geteilt, bis der Quotient 0 ergibt. Die Werte der Teilungsreste ergeben dann von oben nach unten gelesen die Ziffern der Binärdarstellung von rechts nach links gelesen.

Beispiel: Hier wird die Zahl 71 ins Binärsystem umgewandelt:

• 71 / 2 = 35 Rest 1
• 35 / 2 = 17 Rest 1
• 17 / 2 = 8 Rest 1
• 8 / 2 = 4 Rest 0
• 4 / 2 = 2 Rest 0
• 2 / 2 = 1 Rest 0
• 1 / 2 = 0 Rest 1

Die Binärdarstellung mit 8 Stellen lautet hier also 01000111.

Hexadezimalzahlen

Da Byte-Folgen in der Binärdarstellung schnell sehr lang und unübersichtlich werden, wird zur Darstellung von Bytes statt des Binärsystems oft auch das Hexadezimalsystem verwendet, in dem Zahlen in einem Stellenwertsystem zur Basis 16 dargestellt werden. Neben den Zeichen 0 bis 9 werden hier die Buchstaben A bis F für die sechs zusätzlichen Ziffern verwendet (A entspricht dabei der Dezimalzahl 10 und F der Dezimalzahl 15).

Tool: In dieser interaktiven Anzeige können Sie die Hexadezimaldarstellung von Ganzzahlen selbst untersuchen. Klicken Sie auf die oberen Hexadezimalziffern, um ihre Werte zu ändern.

Beispiel: Die Hexadezimalzahl CAFE entspricht der Dezimalzahl 12·16³ + 10·16² + 15·16 + 14·1 = 51966.

Um eine Dezimalzahl ins Hexadezimalsystem umzuwandeln, wird die Zahl wiederholt mit Rest durch 16 geteilt.

Beispiel: Für die Dezimalzahl 172 gilt: 172 / 16 = 10 Rest 12, also lautet ihre Hexadezimaldarstellung AC.

Ein Byte entspricht im Hexadezimalsystem jeweils einer Hexidezimalzahl mit zwei Ziffern (ggf. mit einer führenden Null).

Die Umrechnung zwischen Binär- und Hexadezimalsystem lässt sich sehr einfach lösen, indem je 4 Binärziffern zusammengefasst und durch die entsprechende Hexadezimalziffer ersetzt werden:

Konvertierung

Tool: Mit diesem Formular können Sie die Repräsentation von Ganzzahlen zwischen dem Dezimalsystem, Hexadezimalsystem und Binärsystem umrechnen.

Größeneinheiten

Um größere Datenmengen von Bits und Bytes zu beschreiben, werden meistens die bekannten Dezimalpräfixe für Maßeinheiten (auch SI-Präfixe genannt) verwendet, mit denen 1000er-Potenzen von Bytes zu je einer Maßeinheit zusammengefasst werden:

Daneben werden auch Binärpräfixe (auch IEC-Präfixe genannt) verwendet, die Vielfache bestimmter Zweierpotenzen bezeichnen (hier: Potenzen von 1024), da binäre Datenmengen aus technischen Gründen oft in diesen Größenordnungen auftreten. Grund dafür ist, dass die SI-Präfixe früher je nach Kontext mal als Dezimalpräfixe und mal als Binärpräfixe verwendet wurden, z. B. konnte mit “1 Kilobyte” entweder 1000 Byte oder 1024 Byte gemeint sein. Um hier Klarheit zu schaffen, wurden Ende der 90er Jahre von der IEC (International Electrotechnical Commission) eigene Präfixe für Zweierpotenzen eingeführt:¹

Codierung von Zahlen

Ganzzahlen ohne Vorzeichen

Natürliche Zahlen (also vorzeichenlose Ganzzahlen) werden in Rechnern als Bitfolgen codiert, wobei sich die Werte der einzelnen Bits aus der Binärdarstellung der Zahl ergeben.

Formel: Für die Bitfolge b₁ b₂ … b_N-1 b_N der Länge N ist die entsprechende Dezimalzahl d also durch die folgende Formel gegeben: $$d = b_1 \cdot 2^{N-1} + b_2 \cdot 2^{N-2} + … + b_{N-1} \cdot 2 + b_N$$

Dabei wird üblicherweise eine feste Länge für die Bitfolgen verwendet – es wird also festgelegt, also wie vielen Bits eine Zahl besteht. In der Praxis werden meistens 1, 2, 4 oder 8 Byte verwendet. Der Umfang des darstellbaren Zahlenbereichs ist durch die Anzahl an Bits, die zur Darstellung einer Zahl verwendet werden, eingeschränkt.

Die folgende Tabelle zeigt einen Ausschnitt aus dem Coderaum der 8-Bit-Ganzzahlen:

Wird 1 Byte (= 8 Bit) pro Zahl verwendet, lassen sich damit 2⁸ verschiedene Werte darstellen, also alle natürlichen Zahlen von 0 bis einschließlich 2⁸-1 = 255. Allgemein wäre für N Byte (= 8N Bit) die größte darstellbare natürliche Zahl 2^8N-1.

Ganzzahlen mit Vorzeichen

Damit sich auch negative Ganzzahlen (bzw. allgemeiner vorzeichenbehaftete Ganzzahlen) darstellen lassen, gibt es verschiedene Möglichkeiten. Die einfachste Variante besteht darin, dass das erste Bit der Bitfolge als Vorzeichenbit verwendet wird (0 für positives Vorzeichen, 1 für negatives Vorzeichen). Die Darstellung der Zahl -42 als 8-Bit-Zahl mit Vorzeichenbit lautet so beispielsweise: 10101010

Da hier 7 Bit für den Betrag ohne Vorzeichen übrigbleiben, wäre der darstellbare Zahlenbereich -127 bis 127. Bei 16 Bit lassen sich die Zahlen -32 767 bis 32 767 darstellen (es gilt: 2¹⁵-1 = 32 767).

Die folgende Tabelle zeigt einen Ausschnitt aus dem Coderaum der 8-Bit-Ganzzahlen in der Darstellung mit Vorzeichenbit:

Diese Darstellung hat allerdings zwei Nachteile: Zum einen ist die Darstellung der Null uneindeutig, da auch sie zwei Repräsentationen besitzt (mit Vorzeichenbit 0 oder 1, also quasi “+0” und “-0”).

Zum anderen muss beim Addieren von Ganzzahlen in dieser Darstellung unterschieden werden, ob Summanden negativ sind und in diesem Fall ein anderer Algorithmus verwendet werden. Dieses Problem entsteht dadurch, dass die negativen Zahlen im Coderaum “falschherum” angeordnet sind (von der größten zur kleinsten).

Beispiel: Werden die 8-Bit-Repräsentationen der Zahlen -42 und 1 ohne Rücksicht auf das Vorzeichenbit summiert, ist das Ergebnis 10101011, was der Zahl -43 entspricht, nicht der erwarteten Zahl -41.

Daher verwenden Rechner in der Regel ein anderes Format zur Binärcodierung von negativen Ganzzahlen, die sogenannte Zweierkomplementdarstellung: Die erste Hälfte der N-Bit-Binärcodes stellt die nicht-negativen Ganzzahlen von 0 bis 2^N-1-1 dar, danach folgen die negativen Zahlen von 2^N-1 bis -1.

Auf diese Weise wird das doppelte Vorkommen der Null verhindert, die Null wird nun nur noch durch eine Folge aus 0-Bits repräsentiert (hier: 00000000). Außerdem liefert die binäre Addition von Ganzzahlen hier unabhängig von den Vorzeichen der Summanden das richtige Ergebnis, da die negativen Zahlen im Coderaum “richtigherum” angeordnet sind (also in aufsteigender Reihenfolge).

Die folgende Tabelle zeigt einen Ausschnitt aus dem Coderaum der 8-Bit-Ganzzahlen mit Vorzeichen in der Zweierkomplementdarstellung:

Auch bei der Zweierkomplementdarstellung übernimmt das erste Bit die Rolle eines Vorzeichenbits – sein Wert bestimmt, ob eine Bitfolge eine negative oder nicht-negative Zahl darstellt. Bei 8 Bit werden also durch die Bitfolgen 00000000 bis 01111111 alle nicht-negativen Zahlen dargestellt (0 bis 2⁷-1 = 127) und durch 10000000 bis 11111111 alle negativen Zahlen (-2⁷ = -128 bis -1).

Um das Vorzeichen einer Zahl zu ändern, kann ein sehr einfacher Algorithmus verwendet werden: Es werden alle Bits der Binärdarstellung der Zahl “gekippt” (invertiert) und zum Ergebnis 1 hinzuaddiert. Diese Operation wird als Zweierkomplement bezeichnet (daher der Name dieser Darstellung).

Beispiel: Es soll die Zweierkomplementdarstellung der Zahl -42 mit 8 Bit berechnet werden:

• 00101010 ← Binärdarstellung von 42 mit 8 Bit
• 11010101 ← Invertieren aller Bits
• 11010110 ← Hinzuaddieren von 1

Tool: In dieser interaktiven Anzeige können Sie die Zweierkomplementdarstellung selbst untersuchen. Klicken Sie auf die oberen Binärziffern, um ihre Werte zu ändern.

Formel: Für die Bitfolge b₁ b₂ … b_N-1 b_N der Länge N ist die entsprechende Dezimalzahl d also durch die folgende Formel gegeben: $$d = -b_1 \cdot 2^{N-1} + b_2 \cdot 2^{N-2} + … + b_{N-1} \cdot 2 + b_N$$

Rationale Zahlen

Um rationale Zahlen oder “Kommazahlen” binär darzustellen, gibt es ebenfalls mehrere Möglichkeiten. Sehr einfach zu interpretieren ist die Darstellung als Festkommazahl. Hier wird festgelegt, dass eine bestimmte Anzahl von Bits zur Darstellung der Nachkommastellen verwendet wird. Bei einer Repräsentation mit 8 Bit kann beispielsweise vereinbart werden, dass die ersten 5 Bit die Stellen vor dem Komma darstellen und die letzten 3 Bit für die Nachkommastellen stehen. Die Stellen entsprechen dann von links nach rechts den Zweierpotenzen 2⁴, …, 2⁰, 2^-1, 2^-2 und 2^-3. Zur Erinnerung: 2^-n ist gleich 1 / 2ⁿ.

Beispiel: Die Binärdarstellung von 10.75 als Festkommazahl mit 8 Bit, davon 3 Nachkommastellenbits, lautet: 01010110. Die linken 5 Stellen codieren die Ganzzahl 10, die rechten 3 Stellen den Nachkommaanteil 1·2^-1 + 1·2^-2 + 0·2^-3 = 0.5 + 0.25 = 0.75.

Tool: In dieser interaktiven Anzeige können Sie die Binärdarstellung von Festkommazahlen selbst untersuchen. Klicken Sie auf die oberen Binärziffern, um ihre Werte zu ändern, und verwenden Sie die unteren Schaltflächen, um die Anzahl der Nachkommastellenbits zu ändern.

Formel: Für die Bitfolge b₁ b₂ … b_N-1 b_N der Länge N mit M Nachkommstellenbits ist die entsprechende Dezimalzahl d also durch die folgende Formel gegeben: $$d = \left( b_1 \cdot 2^{N-1} + b_2 \cdot 2^{N-2} + … + b_{N-1} \cdot 2 + b_N \right) /\ 2^M$$

Rationale Zahlen mit Vorzeichen lassen sich auf dieselbe Weise repräsentieren wie Ganzzahlen mit Vorzeichen, also üblicherweise in der Zweierkomplementdarstellung.

Beispiel: Die Zweierkomplementdarstellung von -10.75 als 8-Bit-Festkommazahl mit 3 Nachkommastellenbits lautet:

• 01010110 ← Binärdarstellung von 10.75
• 10101001 ← Invertieren aller Bits
• 10101010 ← Hinzuaddieren von 1

Vertiefung: Byte-Reihenfolge

In Binärdateien wird die Reihenfolge der Bytes, durch die eine Ganzzahl repräsentiert wird, aus technischen Gründen manchmal umgedreht. Die 16-Bit-Darstellung der Zahl 260 lautet dann 00000100 00000001, und nicht 00000001 00000100, wie eigentlich erwartet.

Dieses Format heißt Little Endian (“kleinendiges” Format), da das Byte, dass die kleinsten Stellen enthält, vorne (links) steht. Die übliche Reihenfolge, die der Darstellung als Binärzahl entspricht, heißt entsprechend Big Endian (“großendiges” Format). Wir gehen hier in den Übungsaufgaben der Einfachheit davon aus, dass Big Endian-Codierung verwendet wird.

Übungsaufgaben

Aufgabe 1: DNS-Sequenzen

Die genetische Information von Lebewesen – das Genom – ist im Zellkern in der Desoxyribonukleinsäure (DNS) gespeichert, konkret wird sie durch die Abfolge der Nukleinbasen in den DNS-Strängen bestimmt. Dabei kommen nur vier Nukleinbasen vor (Adenin, Cytosin, Guanin und Thymin), womit sich die in der DNS gespeicherte Information durch eine Sequenz von vier Zeichen (in der Regel die Buchstaben A, C, G und T) darstellen lässt.

In dieser Aufgabe sollen die Binärdarstellung der genetischen Information und die entstehenden Datenmengen untersucht werden.

• Wie viele Bit werden benötigt, um ein Zeichen der Basensequenz zu codieren?
• Wie würde der Binärcode für die Basensequenz CGACAT in der von Ihnen gewählten Codierung lauten?
• Wie lang kann eine Basensequenz sein, die sich mit 1 MB codieren lässt?
• Die Basensequenz der DNS von Kugelfischen (Takifugu rubripes) hat eine Gesamtlänge von 365 Millionen Zeichen. Wie groß ist die Datenmenge, die zur Speicherung dieser Sequenz benötigt wird? Geben Sie den Wert in einer geeigneten Größeneinheit an.
• Bei menschlicher DNS umfasst das Genom etwa 3.1 Milliarden Basen. Zum Speichern der Daten können Sie einen USB-Stick mit 750 MB, 1 GB, 2 GB, 4 GB oder 8 GB Speicherkapazität verwenden. Welcher USB-Stick reicht hier aus?

Angenommen, in einer Binärdatei sollen mehrere unterschiedliche lange Basensequenzen gespeichert werden. Dazu wird neben A, C, G und T ein zusätzliches Trennzeichen verwendet, um kennzuzeichnen, wo eine Sequenz endet und die nächste beginnt.

• Wie viele Bit wären nun zur Codierung jedes Zeichens in der Datei nötig?
• Wie groß wäre nun eine Datei, die nur die Basensequenz von Takifugu rubripes enthält?
• Fällt Ihnen eine andere ggf. bessere Möglichkeit ein, wie sich mehrere unterschiedlich lange Sequenzen in einer Datei speichern lassen?

Aufgabe 2: Binärdatei interpretieren

In einer Binärdatei sind Informationen über die Bevölkerungsentwicklung von Kiel gespeichert. Der Dateiinhalt hat dabei das folgende Format:

• Die Datei enthält nacheinander mehrere Datensätze, die jeweils 6 Byte umfassen.
• Jeder Datensatz besteht aus den folgenden drei Daten (jeweils 2 Byte):
  • die Jahreszahl als vorzeichenlose Ganzzahl
  • die Bevölkerungsdifferenz zum Vorjahr als Ganzzahl mit Vorzeichen in Zweierkomplementdarstellung
  • der Prozentsatz der Bevölkerungsanzahl im Vergleich zum Vorjahr als Festkommazahl mit 6 Nachkommastellenbits

Ihre Aufgabe besteht darin, den Inhalt der Binärdatei Kiel_Daten.bin zu decodieren ( Download):

00000111 11000111 00000110 00000100 00011001 00101000
00000111 11001000 00001000 00101100 00011001 00111000
00000111 11001001 11111110 11110100 00011000 11111001

Tragen Sie die in der Datei codierten Daten in die folgende Tabelle ein (als Hilfestellung ist der erste Datensatz bereits decodiert):