Kapitel 3: Coding
1. Überblick über Kodierungsarten
Kodierung dient dazu, Informationen für die Speicherung oder Übertragung aufzubereiten.
Kodierungsart Ziel Typische Beispiele
Redundanz entfernen und Daten Run-Length Encoding, Huffman-Kodierung,
Quellkodierung
komprimieren ZIP, JPEG, MPEG
Redundanz hinzufügen, um Fehler zu erkennen Parität, Hamming-Code, CRC, Internet
Kanalkodierung
oder zu korrigieren Checksum
Physikalische Aufbereitung der Bits für die
Leitungskodierung Blockcodes, Manchester-Code
Übertragungsleitung
Beim Senden eines Bildes kann diese Reihenfolge auftreten: Zuerst wird das Bild komprimiert, dann eventuell verschlüsselt,
anschließend mit Prüfsummen oder Fehlerkorrektur geschützt und zum Schluss in ein Leitungssignal umgesetzt. Beim Empfänger
werden diese Schritte in umgekehrter Reihenfolge zurückgerechnet.
2. Quellkodierung
Ziel: Geringerer Speicherbedarf und schnellere Übertragung.
Verlustfreie Quellkodierung: Originaldaten können exakt wiederhergestellt werden.
Verlustbehaftete Quellkodierung: Ein Teil der Information wird bewusst entfernt, zum Beispiel bei Bildern
oder Videos.
Lauflängenkodierung (Run-Length Encoding - RLE):
o Ersetzt Folgen gleicher Symbole durch das Symbol und die Anzahl seiner Wiederholungen.
o Verbesserung: Einsatz eines Markers (Escape-Symbol) und Festlegung einer Mindestanzahl an
Wiederholungen, ab der komprimiert wird.
o Das Verfahren ist verlustfrei.
o Es funktioniert gut, wenn viele gleiche Zeichen hintereinander auftreten.
o Es funktioniert schlecht, wenn Wiederholungen selten sind, weil Zusatzinformationen die Daten
sogar vergrößern können.
o 00000000000000000000FF00000000000000000BBBFFFFFFFF → A014FFA011BBBAF08
Informationsgehalt & Entropie:
Begriff Bedeutung Formel
Je seltener ein Symbol ist, desto größer ist sein I(xi) = ld(1 / p(xi)) bit
Informationsgehalt I(xi) Informationsgehalt.
p ist die Auftrittswahrscheinlichkeit
beschreibt, wie viele Bits pro Symbol 𝑯∗ = ∑𝒏𝒊 𝟏 p(xi) * ld(1 / p(xi)) bit
Entropie H* theoretisch mindestens nötig sind.
Maß für den mittleren Informationsgehalt
Erwartete Anzahl von Bits pro Symbol bei 𝑯∗ = ∑𝒏𝒊 Si * p(xi) bit
Mittlere Codewortlänge Sm 𝟏
einem konkreten Code.
Differenz zwischen mittlerer Codewortlänge Rc = Sm – H*
Redundanz Rc
und Entropie.
Satz von Shanon Es existiert immer ein Code mit H∗ ≤ Sm ≤ H*+1
Kapitel 3 - Coding
1. Überblick über Kodierungsarten
Kodierung dient dazu, Informationen für die Speicherung oder Übertragung aufzubereiten.
Kodierungsart Ziel Typische Beispiele
Redundanz entfernen und Daten Run-Length Encoding, Huffman-Kodierung,
Quellkodierung
komprimieren ZIP, JPEG, MPEG
Redundanz hinzufügen, um Fehler zu erkennen Parität, Hamming-Code, CRC, Internet
Kanalkodierung
oder zu korrigieren Checksum
Physikalische Aufbereitung der Bits für die
Leitungskodierung Blockcodes, Manchester-Code
Übertragungsleitung
Beim Senden eines Bildes kann diese Reihenfolge auftreten: Zuerst wird das Bild komprimiert, dann eventuell verschlüsselt,
anschließend mit Prüfsummen oder Fehlerkorrektur geschützt und zum Schluss in ein Leitungssignal umgesetzt. Beim Empfänger
werden diese Schritte in umgekehrter Reihenfolge zurückgerechnet.
2. Quellkodierung
Ziel: Geringerer Speicherbedarf und schnellere Übertragung.
Verlustfreie Quellkodierung: Originaldaten können exakt wiederhergestellt werden.
Verlustbehaftete Quellkodierung: Ein Teil der Information wird bewusst entfernt, zum Beispiel bei Bildern
oder Videos.
Lauflängenkodierung (Run-Length Encoding - RLE):
o Ersetzt Folgen gleicher Symbole durch das Symbol und die Anzahl seiner Wiederholungen.
o Verbesserung: Einsatz eines Markers (Escape-Symbol) und Festlegung einer Mindestanzahl an
Wiederholungen, ab der komprimiert wird.
o Das Verfahren ist verlustfrei.
o Es funktioniert gut, wenn viele gleiche Zeichen hintereinander auftreten.
o Es funktioniert schlecht, wenn Wiederholungen selten sind, weil Zusatzinformationen die Daten
sogar vergrößern können.
o 00000000000000000000FF00000000000000000BBBFFFFFFFF → A014FFA011BBBAF08
Informationsgehalt & Entropie:
Begriff Bedeutung Formel
Je seltener ein Symbol ist, desto größer ist sein I(xi) = ld(1 / p(xi)) bit
Informationsgehalt I(xi) Informationsgehalt.
p ist die Auftrittswahrscheinlichkeit
beschreibt, wie viele Bits pro Symbol 𝑯∗ = ∑𝒏𝒊 𝟏 p(xi) * ld(1 / p(xi)) bit
Entropie H* theoretisch mindestens nötig sind.
Maß für den mittleren Informationsgehalt
Erwartete Anzahl von Bits pro Symbol bei 𝑯∗ = ∑𝒏𝒊 Si * p(xi) bit
Mittlere Codewortlänge Sm 𝟏
einem konkreten Code.
Differenz zwischen mittlerer Codewortlänge Rc = Sm – H*
Redundanz Rc
und Entropie.
Satz von Shanon Es existiert immer ein Code mit H∗ ≤ Sm ≤ H*+1
Kapitel 3 - Coding
