Mit Google fortfahren
Informationstheorie: Entropie, Codes und Fehler
Die Informationstheorie beschreibt mathematisch, wie überraschend Daten sind, wie stark sie sich komprimieren lassen und wie Übertragungsfehler erkannt werden können. Dabei untersucht sie statistische Eigenschaften – nicht die Bedeutung einer Nachricht.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was untersucht die Informationstheorie?
Eine Nachricht besteht aus Zeichen einer Quelle. Das können Buchstaben, Messwerte oder Bits sein. Die Informationstheorie fragt beispielsweise:
- Wie überraschend ist ein bestimmtes Zeichen?
- Wie viele Bits werden im Mittel zum Codieren benötigt?
- Wie lassen sich Daten eindeutig decodieren?
- Wie können Übertragungsfehler erkannt werden?
Statistische Information
Statistische Information beschreibt die Unsicherheit und Überraschung von Daten anhand ihrer Wahrscheinlichkeiten. Ob eine Nachricht sinnvoll, lustig oder wichtig ist, wird dabei nicht bewertet.
Deshalb können ein sinnvoller Satz und eine zufällige Zeichenfolge für die Theorie ähnliche statistische Eigenschaften besitzen, obwohl ihre Bedeutung verschieden ist.
Ein Kommunikationssystem lässt sich vereinfacht so betrachten:
- Eine Quelle erzeugt Daten.
- Die Quellencodierung versucht, unnötige Wiederholungen zu entfernen.
- Die Kanalcodierung fügt gezielt Prüfdaten hinzu.
- Ein Kanal überträgt die Daten und kann sie dabei stören.
- Die empfangenen Daten werden geprüft und decodiert.
Quellencodierung entfernt Redundanz zur Kompression. Kanalcodierung fügt Redundanz zur Fehlersicherung hinzu.
Wie viel Information steckt in einem Zeichen?
Ein seltenes Zeichen überrascht stärker als ein häufiges. Sein Informationsgehalt ist deshalb größer.
Informationsgehalt
Hat ein Zeichen $x$ die Wahrscheinlichkeit $p(x)$, dann beträgt sein Informationsgehalt
$$I(x)=-\log_2 p(x)=\log_2\frac{1}{p(x)}.$$
Bei Logarithmusbasis 2 wird das Ergebnis in Bit angegeben.
Die Formel erfüllt drei wichtige Erwartungen:
- Für ein sicheres Zeichen mit $p(x)=1$ gilt $I(x)=0$ Bit.
- Für zwei gleich wahrscheinliche Zeichen mit $p(x)=0{,}5$ gilt jeweils $I(x)=1$ Bit.
- Bei unabhängigen Zeichen addieren sich ihre Informationsgehalte.
Eine Quelle sendet die Zeichen 0 und 1 unabhängig voneinander und gleich häufig. Für beide gilt:
$$I(0)=I(1)=-\log_2(0{,}5)=1.$$
Die Folge 1011 besitzt damit insgesamt $4$ Bit Informationsgehalt: vier Zeichen mal $1$ Bit.
Ein häufiger Fehler ist die Aussage: „Ein häufiges Zeichen enthält besonders viel Information.“ Statistisch gilt das Gegenteil: Je unwahrscheinlicher ein Zeichen ist, desto größer ist seine Überraschung.
Wie misst Entropie die mittlere Unsicherheit?
Der Informationsgehalt bezieht sich auf ein einzelnes Ergebnis. Die Entropie betrachtet dagegen den Durchschnitt über alle möglichen Zeichen.
Entropie
Für Zeichen $x_1,\ldots,x_n$ mit Wahrscheinlichkeiten $p(x_i)$ ist die Entropie
$$H(X)=-\sum_{i=1}^{n}p(x_i)\log_2 p(x_i).$$
Gleichwertig ist $H(X)=\sum p(x_i)I(x_i)$. Die Entropie gibt den mittleren Informationsgehalt pro Zeichen in Bit an.
Bei einem festen endlichen Alphabet ist die Entropie am größten, wenn alle Zeichen gleich wahrscheinlich sind. Ist ein Ergebnis sicher, beträgt sie $0$ Bit.
Eine Quelle besitzt die Verteilung
- $p(a)=1/2$,
- $p(b)=1/4$,
- $p(c)=p(d)=1/8$.
Die Informationsgehalte betragen $1$, $2$, $3$ und $3$ Bit. Damit folgt:
$$H(X)=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=1{,}75\text{ Bit}.$$
Das bedeutet: Ein Zeichen liefert im langfristigen Mittel $1{,}75$ Bit Information.
Informationsgehalt beschreibt die Überraschung eines einzelnen Ergebnisses. Entropie ist der gewichtete Mittelwert dieser Informationsgehalte.
Wie hängen Entropie und Codierung zusammen?
Eine Binärcodierung ordnet jedem Quellzeichen ein Wort aus 0 und 1 zu. Bei einem variablen Code dürfen häufige Zeichen kurze und seltene Zeichen längere Codewörter erhalten.
Präfixcode
Bei einem Präfixcode ist kein vollständiges Codewort der Anfang eines anderen Codeworts. Dadurch kann eine zusammenhängende Bitfolge sofort und eindeutig von links nach rechts decodiert werden.
Für die Verteilung aus dem Entropiebeispiel ist dieser Code präfixfrei:
- $a\mapsto1$
- $b\mapsto01$
- $c\mapsto000$
- $d\mapsto001$
Nach 1 ist sofort $a$ erkannt. Beginnt die Folge mit 0, wird weitergelesen, bis eines der anderen vollständigen Codewörter erreicht ist.
Die mittlere Codewortlänge lautet
$$L=\sum_i p(x_i)l_i,$$
wobei $l_i$ die Länge des jeweiligen Codeworts bezeichnet.
Beim Präfixcode haben die Wörter die Längen $1$, $2$, $3$ und $3$. Daher gilt:
$$L=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=1{,}75\text{ Bit pro Zeichen}.$$
Ein Festlängencode mit vier Wörtern benötigt dagegen stets $2$ Bit pro Zeichen. Für ihn gilt $L=2$.
Die Code-Redundanz $R=L-H$ beträgt beim Festlängencode $0{,}25$ Bit und beim gezeigten Präfixcode $0$ Bit pro Zeichen.
Für jeden eindeutig decodierbaren Binärcode gilt die Entropieschranke $H\le L$. Blockcodierung kann die mittlere Länge pro Zeichen beliebig nahe an die Entropie heranführen.
Huffman-Codierung
Das Huffman-Verfahren konstruiert einen Präfixcode mit minimaler mittlerer Wortlänge:
- Wähle die beiden kleinsten Wahrscheinlichkeiten.
- Fasse sie zu einem gemeinsamen Knoten zusammen und addiere ihre Werte.
- Wiederhole den Vorgang, bis nur noch ein Baum übrig ist.
- Beschrifte seine beiden Zweige jeweils mit
0und1.
Die genaue Zuordnung von 0 und 1 kann wechseln. Entscheidend sind Präfixfreiheit und Codewortlängen.
Wie macht Redundanz Fehler sichtbar?
Bei der Kompression soll Redundanz sinken. Bei einer störanfälligen Übertragung ist zusätzliche Redundanz nützlich: Sie schafft erkennbare Regeln, die ein fehlerhaftes Wort verletzen kann.
Hamming-Distanz
Die Hamming-Distanz zweier gleich langer Bitwörter ist die Zahl der Positionen, an denen sie sich unterscheiden. Die minimale Hamming-Distanz eines Codes ist der kleinste Abstand zwischen zwei verschiedenen gültigen Codewörtern.
Betrachte die gültigen Wörter 000, 011, 101 und 110. Je zwei dieser Wörter unterscheiden sich an genau zwei Stellen. Die minimale Hamming-Distanz beträgt daher $2$.
Verändert sich bei der Übertragung genau ein Bit, entsteht kein anderes gültiges Codewort. Der Fehler wird erkannt. Aus diesem Abstand allein lässt sich jedoch nicht eindeutig bestimmen, welches Bit falsch ist.
Allgemein kann ein Code mit minimaler Hamming-Distanz $d$ bis zu $d-1$ Bitfehler sicher erkennen. Für die eindeutige Korrektur von $t$ Fehlern muss $d\ge 2t+1$ gelten.
Paritätsbit
Ein Paritätsbit ergänzt ein Datenwort so, dass die Gesamtzahl der Einsen einer vereinbarten Regel folgt. Bei gerader Parität muss sie beispielsweise gerade sein.
Wird genau ein Bit verändert, wechselt die Parität und der Fehler fällt auf. Zwei veränderte Bits können die gerade Parität jedoch wiederherstellen und unbemerkt bleiben.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Informationstheorie
- misst statistische Überraschung mit dem Informationsgehalt
- mittelt Informationsgehalte zur Entropie
- begrenzt die mittlere Länge eindeutig decodierbarer Codes
- nutzt Präfix- und Huffman-Codes zur verlustfreien Codierung
- entfernt Redundanz bei der Quellencodierung
- ergänzt Redundanz bei der Kanalcodierung
- bewertet Fehlerschutz mit der Hamming-Distanz
Abschluss-Check
Du hast den Kern verstanden, wenn du jetzt drei Fragen beantworten kannst: Wie überraschend ist ein Zeichen? Wie groß ist die mittlere Unsicherheit der Quelle? Welche Redundanz soll entfernt und welche bewusst hinzugefügt werden?