INF-Daten - Informationssysteme, Codierung und Zahlensysteme — Informatik · Matura-Zusammenfassung

Bits, Bytes und Stellenwertsysteme#

~5 Min LesezeitBasisINF-Daten-1.1INF-Daten-2.1

Jede Information in einem Computer - Text, Bild, Ton, Programmcode - wird letztlich als Folge von Bits gespeichert. Ein Bit ist die kleinste Informationseinheit und kennt nur zwei Zustände, geschrieben als

0

und

1

(technisch z. B. Spannung an/aus, magnetisiert/nicht). Entscheidend ist die Kombination: Mit

n

Bit lassen sich

2^{n}

verschiedene Muster bilden, weil jedes zusätzliche Bit die Zahl der Möglichkeiten verdoppelt. Acht Bit bilden ein Byte und codieren damit

2^{8}=256

Werte - genug für den erweiterten ASCII-Zeichensatz.

Damit aus Bitmustern Zahlen werden, braucht es ein Stellenwertsystem. Zur Basis

b

sind die zulässigen Ziffern

\{0,1,\dots,b-1\}

, und jede Stelle

i

(von rechts mit

0

beginnend) trägt den Wert

z_{i}\cdot b^{i}

bei. Das Dezimalsystem (

b=10

) ist nur ein Spezialfall:

205 = 2\cdot 10^{2}+0\cdot 10^{1}+5\cdot 10^{0}

. Genau dasselbe Prinzip im Binärsystem (

b=2

): In

10101101_{2}

sind die Stellen mit den Werten

128, 32, 8, 4, 1

gesetzt, deren Summe

173

ergibt ().

Binärumrechnung 173 = 10101101₂

Abb. 1Gesetzte Bits (Beitrag ungleich 0) summieren sich zu 128 + 32 + 8 + 4 + 1 = 173. Das höchstwertige Bit b7 steht ganz links.

Abb. 1 ↓

Das Binärsystem ist maschinennah, für Menschen aber unübersichtlich. Hier hilft das Hexadezimalsystem (Basis 16, Ziffern

0

-

9

sowie

A

-

F

für

10

-

15

): Weil

16=2^{4}

gilt, entspricht genau eine Hexziffer einer Vierergruppe (einem Nibble) von Bits. Man liest eine Binärzahl daher bequem als Hex, indem man sie von rechts in Vierergruppen zerlegt:

1010\,1101 = A\,D = \mathrm{AD}_{16}

. Diese 1:1-Beziehung ist der Grund, warum Speicheradressen, Farbwerte (#RRGGBB) und Maschinencode fast immer hexadezimal angegeben werden.

Die Umrechnung Dezimal nach Binär gelingt zuverlässig durch wiederholte Division durch 2: Bei jeder Division notiert man den Rest (

0

oder

1

) und liest die Reste am Ende von unten nach oben - also rückwärts - ab. Für

173

etwa:

173:2=86\,\text{R}\,1

,

86:2=43\,\text{R}\,0

, weiter bis

1:2=0\,\text{R}\,1

; die Reste rückwärts gelesen ergeben

10101101_{2}

. Zur Gegenprobe addiert man die Stellenwerte der gesetzten Bits - stimmt die Summe mit der Ausgangszahl, war die Rechnung korrekt.

Eine notorische Fehlerquelle sind die Größenpräfixe. Umgangssprachlich meint „Kilobyte" oft

1024

Byte, die Norm IEC 60027-2 trennt das aber sauber:

1\,\text{kB}=1000\,\text{B}

(dezimal, Zehnerpotenz),

1\,\text{KiB}=2^{10}=1024\,\text{B}

(binär); analog MB/MiB und GB/GiB. Faustregel: Speichergrößen (RAM, Dateien) werden meist binär (

2^{n}

) gemessen, Übertragungsraten dezimal (

10^{n}

) - genau deshalb erscheint eine als „500 GB" beworbene Festplatte im Betriebssystem als rund

465\,\text{GiB}

.

Für Prüfungsaufgaben ist sprachliche Genauigkeit entscheidend. „Wie viele Werte stellen

n

Bit dar?" ist

2^{n}

, der größte darstellbare Wert dagegen

2^{n}-1

(weil bei

0

begonnen wird). Werteanzahl, größter Wert und Wertebereich sind drei verschiedene Größen, die man nicht verwechseln darf. Und eine Binärzahl ist erst mit angegebener Bitbreite vollständig: korrekt ist „

10101101_{2}

(8-Bit)", nicht bloß „

10101101

".

Vokabeln

→ Kartei

BitKleinste Informationseinheit mit den Zuständen 0 und 1.
ByteGruppe von acht Bit; sie kann 256 verschiedene Werte annehmen.
StellenwertsystemZahlensystem, in dem die Position einer Ziffer ihren Wert bestimmt.
BasisAnzahl der Ziffern eines Zahlensystems; 2 binär, 10 dezimal, 16 hexadezimal.
most significant bitHöchstwertiges Bit; ganz links und mit dem größten Stellenwert.
BinärpräfixVorsatz für Zweierpotenzen wie Kibi, Mebi und Gibi; abzugrenzen von Kilo, Mega, Giga.

Allgemeine Stellenwertdarstellung

\text{Wert} = \sum_{i=0}^{n-1} z_{i}\cdot b^{i}

$z_{i}$ ist die Ziffer an Position $i$ , $b$ die Basis des Zahlensystems und $n$ die Stellenzahl. Gezählt wird von RECHTS beginnend bei Position 0 - genau dort entsteht der häufigste Umrechnungsfehler.

Binäre vs. dezimale Speicherpräfixe

2^{10} = 1024 = 1\,\text{KiB},\quad 10^{3} = 1000 = 1\,\text{kB}

Die Binärpräfixe Kibi, Mebi und Gibi zählen Zweierpotenzen, die SI-Präfixe Kilo, Mega und Giga Zehnerpotenzen. Der Unterschied beträgt bei Kilo 2,4 % und wächst mit jeder Stufe - bei Terabyte sind es bereits rund 10 %.

Musterbeispiel

Dezimal 173 in Binaer und Hex umrechnen

Wandle 173_10 in eine 8-Bit-Binaerzahl und in Hexadezimal um.

Wiederholte Division durch 2
173 = 286 + 1; 86 = 243 + 0; 43 = 221 + 1; 21 = 210 + 1; 10 = 25 + 0; 5 = 22 + 1; 2 = 21 + 0; 1 = 20 + 1. Reste rückwärts: 10101101.
Quergegenprüfung Stellenwerte
128 + 32 + 8 + 4 + 1 = 173.
In Hex zusammenfassen
10101101 = 1010 1101 = A D = AD_16.

Ergebnis: 173_10 = 10101101_2 = AD_16.

Schritt-für-Schritt Erklärung3 Schritte

1
Stell dir Stellenwertsysteme als Stapel von Karten vor: jede Karte trägt eine Zweierpotenz.
Binärumrechnung 173 = 10101101₂
Abb.Gesetzte Bits (Beitrag ungleich 0) summieren sich zu 128 + 32 + 8 + 4 + 1 = 173. Das höchstwertige Bit b7 steht ganz links.
2
Beim Umrechnen von Dezimal in Binaer ist die wiederholte Division durch 2 ein verlässlicher Algorithmus.
3
Hex ist nichts anderes als Binaer in Vierergruppen: leichter zu lesen, identische Bits.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Erkläre am Beispiel der Zahl 205_10, wie eine Dezimalzahl in das Binaer- und Hexadezimalsystem umgewandelt wird. Begründe den Zusammenhang zwischen Hexadezimal- und Binärdarstellung.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Die Stellen werden von links gezählt; die Zählung beginnt RECHTS bei Position 0.
kB und KiB werden gleichgesetzt: $1\,\mathrm{kB}=10^{3}$ Byte, $1\,\mathrm{KiB}=2^{10}=1024$ Byte.
Die Hexziffern werden falsch zugeordnet; A entspricht 10, C entspricht 12, F entspricht 15.
$2^{n}$ und $2^{n}-1$ werden verwechselt; das eine ist die Anzahl, das andere der größte Wert.
Bit und Byte werden vermengt; Bandbreiten werden meist in Bit je Sekunde, Speichergrößen in Byte angegeben.

Aktive Wiederholung

Wandle die Hexadezimalzahl 2F_16 in das Dezimalsystem und in eine 8-Bit-Binaerzahl um. Wie viele verschiedene Werte können 12 Bit darstellen?

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: AHS-Lehrplan Informatik - Wahlpflichtgegenstand (BMBWF / RIS) · IEC 60027-2 - Binärpräfixe (IEC)

Vorzeichen, Zweierkomplement und Overflow#

~4 Min LesezeitStandardINF-Daten-2.2

Computer müssen negative Zahlen mit derselben Schaltung verarbeiten wie positive. Die naive Idee, das oberste Bit als reines Vorzeichen zu reservieren (Vorzeichen-Betrag), erzeugt jedoch zwei Nullen (

+0

und

-0

) und verlangt getrennte Logik für Addition und Subtraktion. Das Zweierkomplement löst beide Probleme elegant und ist deshalb der universelle Standard für ganze Zahlen.

Bei

k

Bit hat unsigned den Wertebereich

0

bis

2^{k}-1

, signed im Zweierkomplement

-2^{k-1}

bis

2^{k-1}-1

- bei 8 Bit also

-128

bis

+127

(). Der Bereich ist asymmetrisch: Es gibt eine negative Zahl mehr als positive, weil die

0

einen der „positiven" Plätze belegt.

Wertebereich 8-Bit-Zweierkomplement

Abb. 28-Bit-Zweierkomplement: -128 (10000000) bis +127 (01111111), Null ist 00000000. Das höchstwertige Bit ist das Vorzeichen (MSB = 1 bedeutet negativ); der Bereich ist asymmetrisch, es gibt eine negative Zahl mehr.

Abb. 2 ↓

Der Kern des Verfahrens ist die Stellenwertformel

\text{Wert} = -z_{k-1}\cdot 2^{k-1} + \sum_{i=0}^{k-2} z_{i}\cdot 2^{i}

: Das höchstwertige Bit (MSB) erhält ein negatives Gewicht, alle übrigen Stellen positives. So ist

11010110_{2} = -128+64+16+4+2 = -42

. Das MSB wirkt damit gleichzeitig als Vorzeichen (

1

negativ,

0

nicht-negativ) und trägt seinen Stellenwert - es ist kein bloßes Vorzeichenflag.

Eine Zahl negiert man, indem man alle Bits invertiert und 1 addiert (Einerkomplement + 1). Das funktioniert, weil

x + \bar{x} = 11\dots1 = -1 \pmod{2^{k}}

ist, also

\bar{x}+1 \equiv -x

. Beispiel

+42 = 00101010 \to

invertieren

11010101 \to +1 \to 11010110 = -42

. Die häufigste Falle: das abschließende

+1

vergessen - dann erhält man das Einerkomplement (mit eigener

-0

), nicht das Zweierkomplement.

Die Addition läuft bitweise identisch zur unsigned-Addition - das ist der eigentliche Gewinn des Systems, eine einzige Addierschaltung genügt. Ein Overflow entsteht, wenn das mathematisch richtige Ergebnis den Wertebereich verlässt; man erkennt ihn am Vorzeichen: Haben beide Summanden dasselbe Vorzeichen, das Ergebnis aber das andere, liegt Overflow vor. Beispiel

96+64

:

01100000+01000000=10100000 = -96

statt

160

- zwei Positive ergeben ein Negatives, also Overflow (die Hardware setzt ein Overflow-Flag). Achtung: ein Carry-out aus dem MSB ist nicht dasselbe wie signed-Overflow.

Das Zweierkomplement gilt nur für ganze Zahlen. Gleitkommazahlen (IEEE 754) bestehen aus Vorzeichen, Exponent und Mantisse und folgen einem völlig anderen Schema - man darf Zweierkomplement-Überlegungen nicht auf Floats übertragen. In der Matura gilt: zuerst die Bitbreite festlegen (4/8/16/32), denn

-5

ist bei 4 Bit „

1011

", bei 8 Bit aber „

11111011

".

Vokabeln

→ Kartei

ZweierkomplementStandarddarstellung negativer Ganzzahlen; invertieren und eins addieren.
EinerkomplementBitweise Invertierung ohne die Addition von eins; kennt zwei Nullen.
ÜberlaufErgebnis außerhalb des darstellbaren Wertebereichs.
VorzeichenbitHöchstwertiges Bit; im Zweierkomplement trägt es das Gewicht $-2^{k-1}$.
WertebereichVon $-2^{n-1}$ bis $2^{n-1}-1$ bei $n$ Bit im Zweierkomplement.
ÜbertragBit, das über die höchste Stelle hinaus entsteht; nicht mit dem Überlauf gleichzusetzen.

Negation im Zweierkomplement

\text{Negation: } \bar{x} + 1 \equiv -x \pmod{2^{k}}

$\bar x$ ist die bitweise Invertierung, $k$ die Bitbreite. Die Rechnung modulo $2^{k}$ bedeutet, dass der Übertrag über die höchste Stelle hinaus einfach entfällt - genau deshalb funktioniert dieselbe Addierschaltung für positive und negative Zahlen.

Stellenwertformel im Zweierkomplement

\text{Wert} = -z_{k-1}\cdot 2^{k-1} + \sum_{i=0}^{k-2} z_{i}\cdot 2^{i}

$z_{k-1}$ ist das höchstwertige Bit; es trägt das NEGATIVE Gewicht $-2^{k-1}$ , alle anderen die gewohnten positiven. Daraus folgt der unsymmetrische Wertebereich von $-2^{k-1}$ bis $2^{k-1}-1$ .

Wiedergabe lädt Inhalte von YouTube (Google).Auf YouTube öffnen ↗

Musterbeispiel

Negative Zahl im 8-Bit-Zweierkomplement

Stelle -42 als 8-Bit-Zweierkomplement dar.

+42 binaer
42 = 32 + 8 + 2 = 00101010_2.
Bits invertieren
00101010 -> 11010101.
1 addieren
11010101 + 1 = 11010110.
Probe
11010110 als signed = -(2^7) + 64 + 16 + 4 + 2 = -128 + 86 = -42.

Ergebnis: -42 entspricht im 8-Bit-Zweierkomplement der Bitfolge 11010110_2 (= D6_16).

Schritt-für-Schritt Erklärung3 Schritte

1
Beim Zweierkomplement wird das Vorzeichen nicht extra gespeichert, sondern in das höchstwertige Bit eingebaut.
Wertebereich 8-Bit-Zweierkomplement
Abb.8-Bit-Zweierkomplement: -128 (10000000) bis +127 (01111111), Null ist 00000000. Das höchstwertige Bit ist das Vorzeichen (MSB = 1 bedeutet negativ); der Bereich ist asymmetrisch, es gibt eine negative Zahl mehr.
2
Wenn du eine Zahl negierst, invertierst du alle Bits und addierst 1; das funktioniert weil $\bar{x}+x = -1 \pmod{2^{k}}$ .
3
Overflow erkennst du am Vorzeichenwechsel bei gleichen Vorzeichen der Summanden.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erläutere das Zweierkomplement bei 8 Bit. Berechne

96+64

bitweise und entscheide, ob es bei signed-Interpretation zu einem Overflow kommt.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Nach dem Invertieren fehlt die Addition von eins; das Ergebnis ist dann das Einerkomplement.
Die Bitbreite wird weggelassen; ohne sie ist eine negative Zahl nicht eindeutig.
Das MSB wird wie bei Vorzeichen-Betrag als reines Vorzeichen gelesen.
Der Wertebereich wird symmetrisch angenommen; bei 8 Bit reicht er von $-128$ bis $+127$ .
Ein Überlauf wird mit einem Übertrag aus der höchsten Stelle gleichgesetzt; die beiden sind nicht dasselbe.

Aktive Wiederholung

Berechne -17 im 8-Bit-Zweierkomplement. Prüfe Overflow bei der 8-Bit-Addition $96 + 64$ .

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Tanenbaum: Structured Computer Organization, 6. Auflage (Pearson)

ASCII, Unicode und UTF-8#

~4 Min LesezeitStandardINF-Daten-3.1

Ein Computer speichert nur Zahlen - für Text braucht es eine Abbildung von Zeichen auf Zahlen. Dahinter stehen zwei getrennte Fragen, deren Verwechslung die klassische Prüfungsfalle ist: Welche Zeichen gibt es und welche Zahl bekommt jedes (der Zeichensatz bzw. Codepunkt), und wie wird diese Zahl zu Bytes (die Codierung). Ein Codepunkt wird hexadezimal mit „U+" notiert, z. B. U+0041 für „A".

ASCII (1963) belegt 7 Bit und deckt damit 128 Codepunkte ab: Steuerzeichen (

0

-

31

), Ziffern, Groß- und Kleinbuchstaben des lateinischen Alphabets, Satzzeichen. Für Englisch genügt das, aber Umlaute, Akzente oder nichtlateinische Schriften fehlen - es entstanden zahllose inkompatible 8-Bit-Erweiterungen (Latin-1 usw.), die dasselbe Byte je nach Region anders deuteten.

Unicode vereinheitlicht das: eine universelle Tabelle, die jedem Zeichen jeder Schrift einen eindeutigen Codepunkt im Bereich U+0000 bis U+10FFFF zuweist (heute über 150 000 belegt), etwa U+00E4 für „ä" oder U+20AC für „€". Wichtig: Unicode ist nur die Nummerierung und sagt noch nichts über Bytes aus.

UTF-8 ist die dominierende Byte-Codierung von Unicode und variabel lang: 1 Byte für U+0000-U+007F, 2 bis U+07FF, 3 bis U+FFFF, 4 für die höheren Ebenen (). Die führenden Bits des ersten Bytes geben die Bytezahl an (

0\dots

,

110\dots

,

1110\dots

,

11110\dots

), Folgebytes beginnen stets mit

10\dots

. Daraus folgt zweierlei: reiner ASCII-Text ist in UTF-8 byteidentisch (Rückwärtskompatibilität), und nach einem kaputten Byte kann ein Parser sich wieder synchronisieren.

UTF-8 - Bytemuster nach Codepunktbereich

Abb. 3Je nach Codepunkt nutzt UTF-8 1 bis 4 Bytes; der ASCII-Bereich bleibt 1 Byte (Rückwärtskompatibilität).

Abb. 3 ↓

Konkret: „€"

=

U+20AC liegt im 3-Byte-Bereich, Schema

1110xxxx\,10xxxxxx\,10xxxxxx

; setzt man die Bits

0010\,0000\,1010\,1100

ein, ergibt sich E2 82 AC (siehe Beispiel). Daraus folgt direkt die häufigste Fehleinschätzung: Die Länge eines Strings in Zeichen ist nicht gleich der Länge in Bytes.

Alternativen: UTF-16 nutzt 2 oder 4 Byte (Surrogatpaare), UTF-32 feste 4 Byte (verschwenderisch, dafür

O(1)

-Indizierung). Mojibake (z. B. „Ã¤" statt „ä") entsteht, wenn Bytes einer Codierung mit einer anderen gelesen werden; die Abhilfe ist die deklarierte Codierung (HTTP-Header, `<meta charset="utf-8">`). UTF-8 ist der Web-Standard, gerade weil es ASCII-kompatibel ist und keinen BOM benötigt.

Vokabeln

→ Kartei

CodepunktEindeutige Nummer eines Zeichens im Unicode-Zeichenvorrat.
CodierungRegel, wie ein Codepunkt in Bytes umgesetzt wird.
ASCII7-Bit-Code mit 128 Zeichen; die Grundlage aller späteren Erweiterungen.
UTF-8Codierung variabler Länge von einem bis vier Byte; rückwärtskompatibel zu ASCII.
BOMByte Order Mark; Kennung am Dateianfang, kein darstellbares Zeichen.
MojibakeUnlesbare Zeichenfolge durch Lesen mit der falschen Codierung.

UTF-8 Bytemuster

\text{UTF-8 Schemata: } 0xxxxxxx \mid 110xxxxx\,10xxxxxx \mid 1110xxxx\,10xxxxxx\,10xxxxxx

Die führenden Bits geben die Länge an: Ein Byte beginnt mit 0, ein Startbyte mehrerer Bytes mit so vielen Einsen, wie Bytes folgen, und jedes Folgebyte mit 10. An diesem Muster erkennt ein Decoder auch mitten im Strom, wo ein Zeichen beginnt.

Musterbeispiel

UTF-8 Codierung des Eurozeichens

Wie wird das Eurozeichen U+20AC in UTF-8 als Bytefolge codiert?

Codepunkt binaer
U+20AC = 0010 0000 1010 1100.
Bereich erkennen
U+0800 bis U+FFFF -> 3 Bytes, Schema 1110xxxx 10xxxxxx 10xxxxxx.
Bits einsetzen
0010 -> erstes Byte 11100010; 000010 -> zweites Byte 10000010; 101100 -> drittes Byte 10101100.
Hex umrechnen
11100010 10000010 10101100 = E2 82 AC.

Ergebnis: Das Eurozeichen U+20AC wird in UTF-8 als drei Bytes E2 82 AC codiert.

Schritt-für-Schritt Erklärung3 Schritte

1
Unicode ist die Landkarte aller Zeichen; UTF-8 ist eine Art, diese Karte in Bytes zu pressen.
2
Das raffinierte an UTF-8: Englischer Text bleibt 1 Byte pro Zeichen, Umlaute kosten ein zweites Byte.
3
Wenn du im Browser kryptische Zeichen siehst, ist meist die falsche Codierung gewählt.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Beschreibe den Unterschied zwischen ASCII, Unicode und UTF-8. Veranschauliche an einem konkreten Sonderzeichen (z.B. einem Umlaut), wie viele Bytes UTF-8 benötigt und warum.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Zeichenanzahl und Bytezahl werden gleichgesetzt; in UTF-8 stimmen sie nur bei reinem ASCII überein.
„Unicode" und „UTF-8" werden synonym verwendet; das eine ist der Zeichenvorrat, das andere eine Codierung.
Das BOM wird als sichtbares Zeichen gedeutet; es ist eine Kennung am Dateianfang.
ASCII wird als 8-Bit-Code beschrieben; es ist ein 7-Bit-Code mit 128 Positionen.
Aus einem Anzeigefehler wird auf beschädigte Daten geschlossen; meist liest das Programm die Bytes nur mit der falschen Codierung.

Aktive Wiederholung

Codiere die Zeichenkette "Caf\u00e9!" in UTF-8 und gib die Bytefolge in Hex an. Wie viele Bytes belegt der String?

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Unicode Standard 16.0 (Unicode Consortium) · RFC 3629 - UTF-8, a transformation format of ISO 10646 (IETF)

Datenkompression - verlustfrei und verlustbehaftet#

~4 Min LesezeitVertiefungINF-Daten-4.1

Kompression tauscht Rechenzeit gegen Speicher und Bandbreite, indem sie Redundanz entfernt. Dabei gibt es zwei grundverschiedene Ziele: verlustfreie Kompression rekonstruiert das Original Bit für Bit (ZIP, gzip, PNG, FLAC), verlustbehaftete Kompression verwirft gezielt Information, die das menschliche Wahrnehmungssystem ohnehin kaum bemerkt (JPEG, MP3, MPEG-4) - und ist damit unumkehrbar.

Die einfachste verlustfreie Idee ist Run-Length-Encoding (RLE): Folgen gleicher Symbole werden durch das Paar (Symbol, Anzahl) ersetzt, „AAAAABBB" wird zu „5A3B". Das eignet sich hervorragend für große einfarbige Flächen (Fax, schlichte Bitmaps), ist aber bei verrauschten Daten nutzlos oder sogar kontraproduktiv, weil dort kaum Wiederholungen auftreten.

Die Huffman-Codierung nutzt die Häufigkeit der Symbole: Häufige Symbole bekommen kurze, seltene lange Codes. Der Baum wächst gierig von unten () - man vereinigt wiederholt die zwei seltensten Knoten zu einem Elternknoten (Summe der Häufigkeiten), bis ein einziger Baum bleibt; linke Kante

=0

, rechte

=1

, und der Code jedes Blatts ist der Pfad ab der Wurzel. Weil kein Code Präfix eines anderen ist (präfixfrei), lässt sich der Bitstrom ohne Trennzeichen eindeutig decodieren.

Huffman-Baum für A:5, B:3, C:2, D:1

Abb. 4Häufige Symbole liegen nahe der Wurzel (kurzer Code), seltene tief unten. Hervorgehoben: Pfad zum längsten Codewort C = 111.

Abb. 4 ↓

Konkret für A:5, B:3, C:2, D:1: zuerst C+D

\to 3

, dann B+3

\to 6

, dann A+6

\to 11

; entlang der Pfade liest man A

=0

, B

=10

, D

=110

, C

=111

ab. Die mittlere Länge

\bar{l} = \tfrac{5\cdot 1+3\cdot 2+1\cdot 3+2\cdot 3}{11} \approx 1{,}82

Bit/Zeichen liegt deutlich unter den

2

Bit, die ein fester Code für vier Symbole bräuchte.

Wie weit kann verlustfreie Kompression gehen? Shannon bewies, dass die mittlere Codewortlänge die Entropie

H(X)=-\sum_{i} p_{i}\log_{2} p_{i}

nicht unterschreiten kann; Huffman bleibt stets innerhalb von 1 Bit davon (

\bar{l} \in [H, H+1)

). Im Beispiel ist

H \approx 1{,}79

Bit, Huffmans

1{,}82

also fast optimal. Die Entropie ist eine Grenze, kein erreichbarer Zielwert - zufällige Daten haben maximale Entropie und lassen sich gar nicht komprimieren.

Verlustbehaftete Verfahren ergänzen Wahrnehmungsmodelle: JPEG transformiert

8\times 8

-Blöcke per Diskreter Kosinustransformation und quantisiert die hohen Frequenzen, die das Auge kaum sieht; MP3 verwirft psychoakustisch verdeckte Töne. Typische Fallen: JPEG ist nicht verlustfrei (jedes erneute Speichern verschlechtert das Bild), Huffman ist nicht ASCII, und Kompression kann zufällige Daten sogar vergrößern. Beim Kompressionsverhältnis stets die Konvention angeben - komprimiert/original in Prozent versus original/komprimiert als „3:1".

Vokabeln

→ Kartei

verlustfreie KompressionDie Originaldaten lassen sich vollständig wiederherstellen.
verlustbehaftete KompressionNicht wahrnehmbare Anteile werden weggelassen; die Rückgewinnung ist unvollständig.
LauflängencodierungErsetzt Wiederholungen durch Anzahl und Zeichen.
Huffman-CodePräfixfreier Code variabler Länge; häufige Symbole erhalten kurze Codewörter.
PräfixfreiheitKein Codewort ist Anfang eines anderen; sichert die eindeutige Decodierung.
EntropieMittlerer Informationsgehalt je Symbol; untere Grenze der Codelänge.

Shannon-Entropie einer diskreten Quelle

H(X) = -\sum_{i=1}^{n} p_{i}\,\log_{2}(p_{i})

$p_{i}$ ist die Auftrittswahrscheinlichkeit des $i$ -ten Symbols; das Ergebnis hat die Einheit Bit je Symbol. Die Entropie ist maximal bei Gleichverteilung und null, wenn nur ein Symbol vorkommt - genau dann ist nichts zu komprimieren.

Shannon-Quellencodierungs-Theorem (Schranke)

\bar{l} \geq H(X) \geq \bar{l} - 1

$\bar l$ ist die mittlere Codewortlänge. Die Entropie ist die untere GRENZE, die kein verlustfreies Verfahren unterschreiten kann; der Huffman-Code kommt ihr bis auf weniger als ein Bit je Symbol nahe.

Musterbeispiel

Huffman-Code aus Häufigkeiten

Konstruiere für A:5, B:3, C:2, D:1 einen Huffman-Code.

Kleinste Häufigkeiten kombinieren
C (2) + D (1) -> Knoten CD (3).
Nächste Kombination
B (3) + CD (3) -> Knoten BCD (6).
Letzte Kombination
A (5) + BCD (6) -> Wurzel (11).
Codes ablesen
A: 0; B: 10; C: 111; D: 110 (links 0, rechts 1).
Mittlere Länge
$\bar{l} = \frac{5\cdot 1 + 3\cdot 2 + 2\cdot 3 + 1\cdot 3}{11} = \frac{20}{11} \approx 1{,}82$ Bit/Zeichen.
Entropie
$H = -(0{,}45\log_{2}0{,}45 + 0{,}27\log_{2}0{,}27 + 0{,}18\log_{2}0{,}18 + 0{,}09\log_{2}0{,}09) \approx 1{,}79$ Bit.

Ergebnis: Huffman-Code A=0, B=10, C=111, D=110; mittlere Codelänge ~1,82 Bit liegt sehr nahe an der Entropie ~1,79 Bit.

Schritt-für-Schritt Erklärung3 Schritte

1
Kompression nutzt Redundanz: Wiederholungen, Vorhersagbarkeit oder Wahrnehmungsschwellen.
2
Huffman ist eine "gierige" Strategie: immer die seltensten Symbole zuerst verbinden.
3
Shannon hat bewiesen, dass die Entropie die theoretische Untergrenze bildet, die kein Verfahren unterschreiten kann.

SRDP-Aufgaben

SelbsttestAus der Fragenbank8 Punkte

Aufgabenstellung

Vergleiche verlustfreie und verlustbehaftete Kompression an je einem typischen Anwendungsfall. Erläutere die Huffman-Codierung an einem selbstgewählten Beispiel und nenne den theoretischen Bezug zur Shannon-Entropie.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

JPEG wird als verlustfrei eingestuft; verlustfrei sind PNG, ZIP und FLAC.
Der Huffman-Code wird mit ASCII verwechselt; er ist ein Code variabler Länge ohne feste Zuordnung.
Es wird angenommen, Kompression mache Daten immer kleiner; bei bereits komprimierten oder zufälligen Daten wächst die Datei.
Die Lauflängencodierung wird auf Daten ohne Wiederholungen angewandt; dort verlängert sie das Ergebnis.
Präfixfreiheit wird nicht geprüft; ohne sie ist der Huffman-Code nicht eindeutig decodierbar.

Aktive Wiederholung

Konstruiere für die Symbolhäufigkeiten A=5, B=3, C=2, D=1 einen Huffman-Code und berechne die mittlere Codewortlänge sowie die Entropie.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Shannon: A Mathematical Theory of Communication (Bell System Technical Journal) · David Salomon: Data Compression - The Complete Reference (Springer)

Fehlererkennung und Prüfsummen#

~4 Min LesezeitStandardINF-Daten-5.1

Daten, die über einen verrauschten Kanal laufen oder auf alternden Medien liegen, können kippen. Fehlererkennung fügt kontrollierte Redundanz hinzu, sodass der Empfänger merkt, ob die Daten unversehrt ankamen - und sie manchmal sogar repariert. Der Preis sind zusätzliche Bits; die Kunst ist maximale Erkennung pro Redundanzbit ( stellt die gängigen Verfahren gegenüber).

Fehlererkennung im Vergleich

Abb. 5Parität, Prüfziffer, CRC und Hamming-Code unterscheiden sich in Erkennungs- und Korrekturleistung.

Abb. 5 ↓

Das billigste Verfahren ist ein einzelnes Paritätsbit: Man hängt ein Bit an, sodass die Gesamtzahl der Einsen gerade (Even) oder ungerade (Odd) wird; gleichbedeutend ist

p = \bigoplus_{i} b_{i}

, die XOR-Summe aller Datenbits. Der Empfänger rechnet die Parität nach - stimmt sie nicht, liegt ein Fehler vor. Beispiel:

1011001

hat vier Einsen (gerade), das Even-Paritätsbit ist also

0

.

Parität erkennt jede ungerade Zahl von Bitfehlern, korrigiert aber keinen und übersieht jede gerade Zahl: Zwei gleichzeitig kippende Bits stellen die Parität wieder her und bleiben unbemerkt. Deshalb sichert ein einzelnes Paritätsbit nur Kanäle mit sehr niedriger Fehlerrate; für stärkere Garantien nutzt man Blockverfahren.

Die CRC (Cyclic Redundancy Check) fasst die Nachricht als Koeffizienten eines Polynoms

m(x)

auf, multipliziert mit

x^{k}

und dividiert durch ein festes Generatorpolynom

g(x)

; der Rest

r(x)=m(x)\cdot x^{k} \bmod g(x)

wird angehängt. So werden alle Bündelfehler bis zum Grad von

g(x)

erkannt, und das Verfahren ist in Hardware billig (Schieberegister + XOR) - daher setzen Ethernet (CRC-32), ZIP und PNG darauf. Eine 32-Bit-CRC muss man nicht von Hand rechnen, aber das Prinzip der Polynomdivision erklären können.

Um nicht nur zu erkennen, sondern zu korrigieren, legt der Hamming-Code Paritätsbits an Positionen ab, die Zweierpotenzen sind (

1, 2, 4, 8, \dots

); jedes prüft eine feste Teilmenge der Datenbits. Die XOR-Kombination der fehlschlagenden Prüfungen (das „Syndrom") zeigt direkt den Index des gekippten Bits an, das dann invertiert wird. So lässt sich ein 1-Bit-Fehler korrigieren und (mit einem Zusatzbit, SECDED) ein 2-Bit-Fehler erkennen - die Grundlage von ECC-RAM.

Eine Prüfziffer ist eine menschenlesbare Kontrollstelle (EAN-13, IBAN, SVNR), berechnet aus einer gewichteten Ziffernsumme (EAN-13: abwechselnd Faktoren

1

und

3

, Ergänzung zum nächsten Zehner). Sie fängt typische Tippfehler und Zifferndreher ab. Entscheidende Abgrenzung: All diese Verfahren sind keine kryptografischen Hashes - sie schützen vor zufälliger Verfälschung, nicht vor einem Angreifer, der die Prüfsumme einfach neu berechnen kann.

Vokabeln

→ Kartei

ParitätZusatzbit, das die Anzahl der Einsen gerade oder ungerade macht.
PrüfsummeAus den Daten berechneter Wert zur Erkennung von Übertragungsfehlern.
CRCZyklische Redundanzprüfung; der Rest einer Polynomdivision dient als Prüfwert.
Hamming-CodeCode, der Ein-Bit-Fehler nicht nur erkennt, sondern auch korrigiert.
Hamming-AbstandZahl der unterschiedlichen Bitstellen zweier Codewörter.
RedundanzZusätzliche Information, die keine Nutzdaten trägt, aber Fehler erkennbar macht.

Even-Parität = XOR aller Datenbits

p = \bigoplus_{i=0}^{n-1} b_{i}

$\oplus$ ist die exklusive Oder-Verknüpfung, $b_{i}$ sind die Datenbits. Das Ergebnis ist genau dann 1, wenn die Anzahl der Einsen ungerade ist - angehängt macht es die Gesamtzahl gerade.

CRC: Rest der Polynomdivision

\text{CRC: } r(x) = m(x) \cdot x^{k} \bmod g(x)

$m(x)$ ist die als Polynom gedeutete Nachricht, $g(x)$ das vereinbarte Generatorpolynom vom Grad $k$ ; die Multiplikation mit $x^{k}$ schafft Platz für die Prüfbits. Gerechnet wird modulo 2, das heißt ohne Überträge - Addition und Subtraktion sind beide das XOR.

Musterbeispiel

Even-Parität für 1011001

Berechne das Even-Paritätsbit für 1011001.

Einsen zählen
1+0+1+1+0+0+1 = 4 Einsen.
Paritätsbit setzen
Anzahl Einsen bereits gerade -> Paritätsbit = 0.
Resultierendes Codewort
10110010 (8 Bit, davon 4 Einsen).

Ergebnis: Paritätsbit = 0; Codewort 10110010. Bei einem 1-Bit-Fehler wird die Parität ungerade -> Fehler erkannt. Bei zwei kippenden Bits bleibt sie gerade -> Fehler unerkannt.

Schritt-für-Schritt Erklärung3 Schritte

1
Prüfsummen geben einen Hinweis darauf, ob Daten unversehrt angekommen sind.
2
Parität ist die einfachste Variante - eine zusätzliche XOR-Summe über alle Datenbits.
3
Industriestandard ist CRC: schnell in Hardware, erkennt nahezu alle Bursts bis zur Polynomlänge.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Erkläre das Prinzip eines Paritaetsbits und veranschauliche es an einer 7-Bit-Folge. Diskutiere die Grenzen des Verfahrens und nenne ein leistungsfähigeres Prüfverfahren.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Das Paritätsbit wird als Korrekturmechanismus dargestellt; es zeigt nur an, DASS ein Fehler vorliegt.
CRC wird mit einem kryptografischen Hash verwechselt; CRC schützt gegen Übertragungsfehler, nicht gegen Manipulation.
Bei der EAN-Prüfziffer werden alle Ziffern gleich gewichtet.
Zwei gekippte Bits werden als von der Parität erkennbar angenommen.
Die Prüfsumme wird als Bestandteil der Nutzdaten mitgezählt; sie ist Redundanz.

Aktive Wiederholung

Berechne das Even-Paritätsbit zur Bitfolge 1011001. Erläutere, warum 2-Bit-Fehler nicht erkannt werden.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: IEEE 802.3 - Ethernet CRC-32 (IEEE)

Gleitkommazahlen nach IEEE 754#

~4 Min LesezeitVertiefungINF-Daten-2.3

Ganze Zahlen können weder

3{,}14

noch

6{,}02\cdot 10^{23}

ausdrücken. Gleitkommazahlen speichern eine Zahl wie in der wissenschaftlichen Notation - ein Vorzeichen, eine gebrochene Mantisse und einen skalierenden Exponenten - und überspannen so mit fester Bitzahl einen riesigen Wertebereich, zum Preis endlicher Genauigkeit. IEEE 754 ist der universelle Standard, den jeder moderne Prozessor umsetzt.

Ein Float packt drei Felder (): Vorzeichen

s

(1 Bit), Exponent

e

(8 Bit Single / 11 Bit Double), Mantisse

m

(23 / 52 Bit); Single

=32

Bit, Double

=64

Bit. Der Wert ist

x=(-1)^{s} \cdot 1{,}m \cdot 2^{e - \text{Bias}}

mit Bias

127

(Single) bzw.

1023

(Double): Der Exponent wird biased gespeichert (als vorzeichenlose Verschiebung), damit Vergleiche funktionieren und kein eigenes Exponenten-Vorzeichen nötig ist.

IEEE 754 - Single und Double Precision

Abb. 6Aufteilung der Bits auf Vorzeichen, Exponent und Mantisse sowie der zugehörige Bias.

Abb. 6 ↓

Ein zentraler Kniff ist die implizite führende 1: Eine normalisierte Binärzahl beginnt immer mit

1{,}\dots

, also wird diese

1

gar nicht gespeichert - die 23-Bit-Mantisse liefert effektiv 24 Bit Genauigkeit. Beispiel

-6{,}5

: Vorzeichen

1

;

6{,}5=110{,}1_{2}=1{,}101\cdot 2^{2}

, also Exponent

2+127=129=10000001

und Mantisse

101000\dots

, zusammengesetzt 0xC0D00000 (siehe Beispiel).

Reservierte Exponentenmuster codieren Sonderwerte: lauter Nullen im Exponenten ergeben

\pm 0

und subnormale Zahlen (gradueller Unterlauf nahe null); lauter Einsen ergeben

\pm\infty

(Überlauf, Division durch 0) und NaN (z. B.

0/0

,

\sqrt{-1}

). NaN bedeutet „not a number" und ist mit nichts gleich, nicht einmal mit sich selbst - eine häufige Verwechslung mit

\infty

.

Weil die Mantisse endlich ist, sind die meisten Dezimalbrüche nicht exakt darstellbar.

0{,}1

ist im Binärsystem periodisch (

0{,}0\overline{0011}_{2}

) und wird gerundet; die winzigen Fehler summieren sich, weshalb

0{,}1 + 0{,}2 \neq 0{,}3

in fast jeder Sprache gilt. Die Granularität heißt Maschinengenauigkeit:

\varepsilon \approx 1{,}19\cdot 10^{-7}

bei Single,

\approx 2{,}22\cdot 10^{-16}

bei Double.

Praktische Konsequenz: Floats nie mit

=

vergleichen, sondern mit Toleranz

|a-b| < \varepsilon

. Auch die Subtraktion fast gleicher Zahlen (Auslöschung) und das Addieren stark unterschiedlicher Größenordnungen kosten Genauigkeit. In der Matura sollte man den Feldaufbau skizzieren, eine kleine Zahl umrechnen und

0{,}1+0{,}2

über die Binärperiodizität und Rundung erklären können.

Vokabeln

→ Kartei

MantisseSignifikand der Gleitkommazahl; sie trägt die Genauigkeit.
ExponentZweierpotenz der Gleitkommazahl; gespeichert mit Bias.
BiasKonstanter Versatz des gespeicherten Exponenten; 127 bei single.
NormalisierungDarstellung mit genau einer Stelle vor dem Komma; das führende Eins-Bit wird impliziert.
NaNNot a Number; Ergebnis undefinierter Operationen wie $0/0$.
MaschinengenauigkeitKleinster relativer Abstand zweier darstellbarer Gleitkommazahlen.

Normalisierte IEEE-754-Gleitkommazahl

x = (-1)^{s} \cdot 1{,}m \cdot 2^{e - \text{Bias}}

$s$ ist das Vorzeichenbit, $m$ die gespeicherte Mantisse, $e$ der gespeicherte Exponent und der Bias 127 bei einfacher bzw. 1023 bei doppelter Genauigkeit. Die führende 1 vor dem Komma wird NICHT gespeichert - sie ergibt sich aus der Normalisierung.

Musterbeispiel

-6,5 als IEEE 754 Single

Wandle $-6{,}5$ in IEEE 754 Single Precision (32 Bit) um.

Vorzeichen
s = 1 (negativ).
Binärumrechnung
$6{,}5 = 110{,}1_{2}$ .
Normalisieren
$110{,}1 = 1{,}101 \cdot 2^{2}$ -> Mantisse 101, Exponent 2.
Bias addieren
Exponent + 127 = 129 = 10000001.
Mantisse füllen
Mantisse 10100000000000000000000 (23 Bit, fuhrendes 1 implizit).
Zusammensetzen
Bitfolge: 1 10000001 10100000000000000000000 = 0xC0D00000.

Ergebnis: $-6{,}5_{10}$ = 0xC0D00000 in IEEE 754 Single Precision.

Schritt-für-Schritt Erklärung3 Schritte

1
IEEE 754 ist der Welt-Standard für Gleitkommazahlen - jeder moderne Prozessor folgt ihm.
2
Der Trick: das fuhrende 1-Bit wird nicht gespeichert, denn es ist immer da.
3
Wer Floats vergleicht, sollte immer mit Toleranz arbeiten - exakte Gleichheit ist meist unrealistisch.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre den Aufbau von Gleitkommazahlen nach IEEE 754. Warum ergibt

0{,}1 + 0{,}2

in vielen Programmiersprachen nicht exakt

0{,}3

?

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Der Bias wird vergessen; der Exponent kommt dadurch um 127 bzw. 1023 daneben.
Das implizite führende Eins-Bit wird ignoriert.
NaN und Inf werden verwechselt; das eine entsteht bei undefinierten Operationen, das andere bei Überlauf oder Division durch null.
Rundungsfehler werden als Programmfehler gedeutet; sie sind eine Eigenschaft des Formats.
Für Geldbeträge werden Gleitkommazahlen verwendet; dort gehören Ganzzahl-Cent oder ein Dezimaltyp hin.

Aktive Wiederholung

Rechne die Dezimalzahl $-6{,}5$ in IEEE 754 Single Precision um. Welche Bits ergeben sich für Vorzeichen, Exponent und Mantisse?

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: IEEE 754-2019 - Floating-Point Arithmetic (IEEE)