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

Bits, Bytes und Stellenwertsysteme#

BasisINF-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.

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

".

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

Allgemeine Stellenwertdarstellung

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

Binäre vs. dezimale Speicherpräfixe

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

Stellen werden von links nach rechts statt von rechts nach links (Position 0) gezählt.
kB/KiB werden gleichgesetzt; insbesondere bei Bandbreiten- vs. Speichergrößen falsch.
Hexziffern A-F werden in der Reihenfolge vertauscht (z.B. C = 12, nicht 11).

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?

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#

StandardINF-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.

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

".

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

Negation im Zweierkomplement

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

Stellenwertformel im Zweierkomplement

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

Invertieren ohne anschliessende +1 -> ergibt Einerkomplement.
Bitbreite vergessen: -5 als "1011" reicht nicht, korrekt sind je nach Bitbreite z.B. "11111011" bei 8 Bit.
MSB als reines Vorzeichen interpretieren (wie Vorzeichen-Magnitude) statt mit Stellenwert $-2^{k-1}$ .

Aktive Wiederholung

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

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

ASCII, Unicode und UTF-8#

StandardINF-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).

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.

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

UTF-8 Bytemuster

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

Anzahl Zeichen = Anzahl Bytes wird angenommen, was bei UTF-8 mit Sonderzeichen falsch ist.
"Unicode" und "UTF-8" werden synonym verwendet.
BOM (Byte Order Mark) wird als sichtbares Zeichen interpretiert.

Aktive Wiederholung

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

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#

VertiefungINF-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.

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".

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

Shannon-Entropie einer diskreten Quelle

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

Shannon-Quellencodierungs-Theorem (Schranke)

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.
Huffman-Code wird mit ASCII verwechselt.
Annahme, dass Kompression immer kleiner macht - bei zufälligen Daten kann das Ergebnis größer sein.

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.

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#

StandardINF-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.

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.

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

Even-Parität = XOR aller Datenbits

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

CRC: Rest der Polynomdivision

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

Paritätsbit wird als Korrekturmechanismus dargestellt.
CRC wird mit Krypto-Hash (MD5/SHA) verwechselt.
EAN-Prüfziffer wird nicht mit gewichteter Summe (Faktoren 1 und 3 abwechselnd) berechnet.

Aktive Wiederholung

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

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Gleitkommazahlen nach IEEE 754#

VertiefungINF-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.

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.

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

Normalisierte IEEE-754-Gleitkommazahl

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

Bias vergessen (single Bias = 127, double Bias = 1023).
Fuhrendes implizites 1-Bit ignoriert.
NaN mit Inf verwechselt.

Aktive Wiederholung

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

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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