Programming lesson
Informationstheorie Grundlagen: Entropie, Hamming-Code und Funktionen einer Zufallsvariablen – Tutorial zu EE276 Homework #1
Lerne die wichtigsten Konzepte der Informationstheorie anhand von Beispielen aus EE276 Homework #1: Gemeinsame Entropie, Hamming-Code, Entropie von Funktionen und Münzwürfen. Ideal für Studierende der Nachrichtentechnik.
Einführung in die Informationstheorie
Die Informationstheorie ist ein zentrales Gebiet der Nachrichtentechnik und Informatik. Sie beschäftigt sich mit der Quantifizierung von Information, der Datenkompression und der zuverlässigen Übertragung über gestörte Kanäle. In diesem Tutorial behandeln wir grundlegende Konzepte wie Entropie, bedingte Entropie, Transinformation und die Anwendung auf den Hamming-Code. Die Beispiele orientieren sich an den Aufgaben aus EE276 Homework #1 und sind für Studierende der Elektrotechnik und Informatik gedacht.
1. Gemeinsame Entropie und Transinformation
Gegeben sei eine gemeinsame Verteilung p(x,y) über zwei Zufallsvariablen X und Y. Die Entropie H(X) misst die Unsicherheit von X, während H(X|Y) die verbleibende Unsicherheit von X nach Kenntnis von Y angibt. Die Transinformation I(X;Y) quantifiziert die gemeinsam geteilte Information. Ein Venn-Diagramm veranschaulicht die Beziehungen: H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) und I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X).
2. Entropie des Hamming-Codes
Der Hamming-Code (7,4) ist ein fehlerkorrigierender Code, der bis zu einen Bitfehler korrigieren kann. Die Informationsbits X1...X4 sind gleichverteilt, und die Prüfbits X5...X7 werden so gewählt, dass die Parität in bestimmten Kreisen gerade ist. Die Gesamtentropie H(X1,...,X7) beträgt 4 Bit, da die Prüfbits deterministisch aus den Informationsbits folgen. Wird ein Fehlervektor e (gleichverteilt über 8 Möglichkeiten) addiert, so kann der Empfänger den Fehler lokalisieren und korrigieren. Daher ist H(X|Y)=0 und I(X;Y)=H(X)=4 Bit. Die Entropie von Y ist H(Y)=H(X)+H(e)=4+log2(8)=7 Bit.
3. Entropie von Funktionen einer Zufallsvariablen
Sei g eine deterministische Funktion. Dann gilt H(g(X)) ≤ H(X). Dies folgt aus der Kettenregel: H(X,g(X)) = H(X) + H(g(X)|X) = H(X) (da g(X) durch X bestimmt ist). Andererseits ist H(X,g(X)) = H(g(X)) + H(X|g(X)) ≥ H(g(X)). Also H(X) ≥ H(g(X)). Dieses Prinzip findet Anwendung in der Datenkompression: Eine Funktion kann die Entropie nicht erhöhen.
4. Münzwürfe und optimale Fragen
Eine faire Münze wird geworfen, bis zum ersten Kopf. Die Anzahl der Würfe X ist geometrisch verteilt mit P(X=n)=1/2^n. Die Entropie H(X) = 2 Bit (Berechnung über die Summe). Ein optimaler Fragebaum (z.B. binäre Suche) benötigt im Mittel etwa 2 Fragen, was der Entropie entspricht. Dies zeigt die praktische Relevanz der Entropie als untere Schranke für die mittlere Codewortlänge.
5. Minimale Entropie
Die Entropie H(p1,...,pn) ist minimal, wenn die Verteilung deterministisch ist, also ein pi=1 und alle anderen 0. Der Minimalwert ist 0. Dies entspricht der Tatsache, dass bei sicherer Vorhersage keine Information übertragen wird.
6. Mischen erhöht die Entropie
Wird eine Wahrscheinlichkeitsverteilung gemischt (z.B. zwei Komponenten ausgetauscht oder gemittelt), so steigt die Entropie. Dies folgt aus der Konkavität der Entropie. Ein Beispiel: Die Verteilung (0.5,0.5) hat höhere Entropie als (1,0).
7. Unendliche Entropie (Bonus)
Eine diskrete Zufallsvariable kann unendliche Entropie haben, wenn die Verteilung nur langsam abfällt. Mit P(X=n) = 1/(A n log^2 n) für n≥2 ist die Entropie unendlich, da die Summe divergiert. Dies zeigt, dass Entropie nicht immer endlich sein muss.
Fazit
Die Informationstheorie liefert mächtige Werkzeuge zur Analyse von Kommunikationssystemen. Die behandelten Konzepte – Entropie, Transinformation, Hamming-Code – sind grundlegend für das Verständnis moderner Technologien wie Mobilfunk, Internet und Datenkompression. Übe die Berechnungen an konkreten Beispielen, um ein tieferes Verständnis zu entwickeln.