Entropie und Näherungen binärer Nachrichtenquellen
Contents
Programmbeschreibung
Dieses Applet soll den Begriff „Entropie” am Beispiel einer binären Nachrichtenquelle verdeutlichen. Die Quellensymbolfolge lautet somit 〈q1,q2, ...,qν–1,qν,qν+1, ...〉 mit qi∈{A,B} für i≥1. Betrachtet werden sowohl eine gedächtnisfreie Quelle als auch eine Markovquelle (mit Gedächtnis „1”, deren Entropien H jeweils in geschlossener Form angegeben werden können. Implizit vorausgesetzt ist hierbei die Folgenlänge N→∞.
Die Entropie H lässt sich aber auch aus einer begrenzten Quellensymbolfolge 〈q1〉=〈q1, ...,qN〉 annähern, also auch dann, wenn die statistischen Eigenschaften der Binärquelle unbekannt sind. Auch hierauf wird in der folgenden Beschreibung eingegangen mit dem Fazit:
- Die Näherung ist natürlich um so genauer, je größer N ist.
- Ist über die Quelle nichts weiter bekannt als die beispielhafte Folge, so ist der Rechenaufwand enorm.
Theoretischer Hintergrund
Die Entropie spielt in vielen naturwissenschaftlichen Fachgebieten eine große Rolle. Beschränken wir uns auf unser Fachgebiet der Statistik und der Informationstechnik, so ist die Entropie nach der Definition von Claude E. Shannon unter anderem ein Maß für die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses, die „Zufälligkeit” dieses Ereignisses und den mittleren Informationsgehalt einer Zufallsgröße.
Entropie einer gedächtnislosen Binärquelle
Wir setzen voraus, dass die Auftrittwahrscheinlichkeiten der beiden Symbole A und B unabhängig von den vorherigen Symbolen innerhalb der Folg gleich pA=p und pB=1–p seien. Für die Entropie dieser „gedächtnislosen” Binärquelle gilt:
- H=Hbin(p)=p⋅log21p+(1−p)⋅log211−p(Einheit:bitoderbit/Symbol).
Man bezeichnet diese Funktion Hbin(p) als die binäre Entropiefunktion. Aus der Grafik erkennt man:
- Der Maximalwert H0=1bit ergibt sich für p=0.5, also für gleichwahrscheinliche Binärsymbole. Dann liefern A und B jeweils den gleichen Beitrag zur Entropie. H0 nennt man auch den Informationsgehalt.
- Hbin(p) ist symmetrisch um p=0.5. Eine Quelle mit pA=0.1 und pB=0.9 hat die gleiche Entropie H=0.469bit wie eine Quelle mit pA=0.9 und pB=0.1.
- Die Differenz ΔH=H0−H gibt die Redundanz der Quelle an und r=ΔH/H0 die relative Redundanz. Im Beispiel ergeben sich ΔH=0.531bit bzw. r=53.1%.
- Für p=0 ergibt sich H=0, da hier die Symbolfolge B B B... mit Sicherheit vorhergesagt werden kann. Eigentlich ist nun der Symbolumfang nur noch M=1. Gleiches gilt für p=1, also für die Symbolfolge AAA...
Entropie hinsichtlich Zweiertupel
Wir teilen nun die Quellensymbolfolge 〈q1,q2, ...,qν–1,qν,qν+1, ...〉 in Zweiertupel auf (siehe Grafik) auf und betrachten dadurch die Entropie zweier aufeinanderfolgender Quellensymbole.
Für die Kombination (qν,qν+1) gibt es 22=4 mögliche Symbolpaare (farblich markiert) mit folgenden Verbundwahrscheinlichkeiten:
- Pr(qν∩qν+1)≤Pr(qν)⋅Pr(qν+1).
Daraus ist die Verbundentropie eines Zweier–Tupels berechenbar (der Index „2” symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht):
- H2′=∑qν∈{qμ}∑qν+1∈{qμ}Pr(qν∩qν+1)⋅log21Pr(qν∩qν+1)(Einheit:bit/Zweiertupel).
Um den mittleren Informationsgehalt pro Symbol zu erhalten, muss H2′ noch halbiert werden:
- H2=H2′/2(Einheit:bit/Symbol).
Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die im letzten Abschnitt definierte Entropie mit H1:
- H1=∑qν∈{qμ}Pr(qν)⋅log21Pr(qν)(Einheit:bit/Symbol).
Der Index „1” soll darauf hinweisen, dass H1 ausschließlich die Symbolwahrscheinlichkeiten berücksichtigt und nicht statistischen Bindungen zwischen Symbolen innerhalb der Folge. Mit dem Entscheidungsgehalt H0=log22=1 ergibt sich dann folgende Größenbeziehung:
- H0≥H1≥H2.
Verdeutlichen wir uns nun die Berechnung der Entropienäherungen H1 und H2 an zwei Beispielen.
Beispiel 1: Wir betrachten zunächst eine gedächtnislose Binärquelle mit gleichwahrscheinlichen Symbolen, das heißt es gelte pA=pB=1/2. Die ersten zwanzig Folgenelemente lauten: 〈qν〉=BBAAABAABBBBBAAAABAB ...
- Aufgrund der gleichwahrscheinlichen Binärsymbole ist H1=H0=1bit/Symbol.
- Die Verbundwahrscheinlichkeit pAB der Kombination AB ist gleich pA·pB=1/4. Ebenso gilt pAA=pBB=pBA=1/4.
- Damit erhält man für die zweite Entropienäherung
- H2=1/2⋅[1/4⋅log24+1/4⋅log24+1/4⋅log24+1/4⋅log24]=1bit/Symbol=H1=H0.
Beispiel 2: Die zweite hier betrachtete Folge ergibt sich aus der Folge von Beispiel 1 durch Anwendung eines einfachen Wiederholungscodes:
- 〈qν〉=BbBbAaAaAaBbAaAaBbBb...
- Die wiederholten Symbole sind durch entsprechende Kleinbuchstaben markiert.
- Aufgrund der gleichwahrscheinlichen Binärsymbole ergibt sich auch hier H1=H0=1bit/Symbol.
- Für die Verbundwahrscheinlichkeiten pAA=pBB=3/8 und pABA=pBAB=1/8 gilt nun. Daraus folgt:
- H2=1/2⋅[2⋅3/8⋅log28/3+2⋅1/8⋅log28]=3/8⋅log28−3/8⋅log23+1/8⋅log28≈0.906bit/Symbol<H1=H0.
Betrachtet man sich die Aufgabenstellung genauer, so kommt man zu folgendem Schluss:
- Die Entropie müsste eigentlich H=0.5bit/Symbol sein (jedes zweite Symbol liefert keine neue Information).
- Die zweite Entropienäherung H2=0.906bit/Symbol ist aber deutlich größer als die Entropie H.
- Zur Entropiebestimmung reicht die Näherung zweiter Ordnung nicht aus. Vielmehr muss man größere zusammenhängende Blöcke mit k>2 Symbolen betrachten. Einen solchen Block bezeichnen wir im Folgenden als k–Tupel.
Fazit:
- Bei statistischer Unabhängigkeit der Folgenelemente ist H=H2=H1≤H0.
- Bei statistischer Abhängigkeit der Folgenelemente gilt dagegen H<H2<H1≤H0.
Verallgemeinerung auf k–Tupel und Grenzübergang
Wir schreiben zur Abkürzung mit der Verbundwahrscheinlichkeit p(k)i eines k–Tupels allgemein:
- Hk=1k⋅Mk∑i=1p(k)i⋅log21p(k)i(Einheit:bit/Symbol).
- Die Laufvariable i steht jeweils für eines der Mk Tupel. Bei den hier betrachteten Binärquellen gilt M=2.
- Die vorher berechnete Näherung H2 ergibt sich mit k=2.
- Für die Entropienäherungen Hk gelten folgende Größenrelationen (H0 ist der Entscheidungsgehalt):
- H≤...≤Hk≤...≤H2≤H1≤H0.
- Die Entropie einer Nachrichtenquelle mit Gedächtnis ist der folgende Grenzwert:
- H=limk→∞Hk.
Der Rechenaufwand wird bis auf wenige Sonderfälle (siehe nachfolgendes Beispiel 3) mit zunehmendem k immer größer:
- Zur Berechnung von H10 einer Binärquelle (M=2) ist über 210=1024 Terme zu mitteln.
- Mit jeder weiteren Erhöhung von k um 1 verdoppelt sich die Anzahl der Summenterme.
Beispiel 3: Wir betrachten eine alternierende Binärfolge ⇒ 〈qν〉=ABABABAB ... . Entsprechend gilt H0=H1=1bit/Symbol.
In diesem Sonderfall muss zur Bestimmung der Hk–Näherung unabhängig von k stets nur über zwei Verbundwahrscheinlichkeiten gemittelt werden:
- k=2: pAB=pBA=1/2 ⇒ H2=1/2bit/Symbol,
- k=3: pABA=pBAB=1/2 ⇒ H3=1/3bit/Symbol,
- k=4: pABAB=pBABA=1/2 ⇒ H4=1/4bit/Symbol.
Die (tatsächliche) Entropie dieser alternierenden Binärfolge ist demzufolge
- H=limk→∞1/k=0.
Dieses Ergebnis war zu erwarten, da die betrachtete Folge nur minimale Information besitzt, die sich allerdings im Entropie–Endwert H nicht auswirkt, nämlich die Information: „Tritt A zu den geraden oder ungeraden Zeitpunkten auf?”
Man erkennt, dass Hk diesem Endwert H=0 nur sehr langsam näher kommt: Die zwanzigste Entropienäherung liefert immer noch H20=0.05bit/Symbol.
Zusammenfassung der Ergebnisse der letzten Seiten:
- Allgemein gilt für die Entropie einer Nachrichtenquelle:
- H≤...≤H3≤H2≤H1≤H0.
- Eine redundanzfreie Quelle liegt vor, falls alle M Symbole gleichwahrscheinlich sind und es keine statistischen Bindungen innerhalb der Folge gibt.
Für diese gilt ( r bezeichnet hierbei die relative Redundanz ):
- H=H0=H1=H2=H3=...⇒r=H−H0H0=0.
- Eine gedächtnislose Quelle kann durchaus redundant sein (r>0). Diese Redundanz geht dann allein auf die Abweichung der Symbolwahrscheinlichkeiten von der Gleichverteilung zurück. Hier gelten folgende Relationen:
- H=H1=H2=H3=...≤H0⇒0≤r=H1−H0H0<1.
- Die entsprechende Bedingung für eine gedächtnisbehaftete Quelle lautet:
- H<...<H3<H2<H1≤H0⇒0<r=H1−H0H0≤1.
- Ist H2<H1, dann gilt auch H3<H2, H4<H3, usw. ⇒ In der allgemeinen Gleichung ist also das „≤”–Zeichen durch das „<”–Zeichen zu ersetzen.
- Sind die Symbole gleichwahrscheinlich, so gilt wieder H1=H0, während bei nicht gleichwahrscheinlichen Symbolen H1<H0 zutrifft.
Binärquellen mit Markoveigenschaften
Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch Markovprozesse modelliert, wobei wir uns hier auf binäre Markovprozesse erster Ordnung mit den Zuständen (Symbolen) A und Bbeschränken.
Rechts sehen Sie das Übergangsdiagramm für einen binären Markovprozess erster Ordnung. Von den vier angegebenen Übertragungswahrscheinlichkeiten sind allerdings nur zwei frei wählbar, zum Beispiel
- pA|B=Pr(A|B) ⇒ bedingte Wahrscheinlichkeit, dass A auf B folgt.
- pB|A=Pr(B|A) ⇒ bedingte Wahrscheinlichkeit, dass B auf A folgt.
Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann pA|A=1−pB|A und pB|B=1−pA|B.
Aufgrund der vorausgesetzten Eigenschaften Stationarität und Ergodizität gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:
- pA=Pr(A)=pA|BpA|B+pB|A,pB=Pr(B)=pB|ApA|B+pB|A.
Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:
- Für pA|B=pB|A sind die Symbole gleichwahrscheinlich ⇒ pA=pB=0.5. Die erste Entropienäherung liefert H1=H0=1bit/Symbol, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten pA|B bzw. pB|A.
- Die Quellenentropie H als der Grenzwert (für k→∞) der Entropienäherung k–ter Ordnung ⇒ Hk hängt aber sehr wohl von den tatsächlichen Werten von pA|B und pB|A ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.
Beispiel 4: Wir betrachten drei binäre symmetrische Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten pA|B=pB|A unterscheiden. Für die Symbolwahrscheinlichkeiten gilt somit pA=pB=0.5, und die anderen Übergangswahrscheinlichkeiten haben dann die Werte
- pA|A=1−pB|A=pB|B.
- Die mittlere (blaue) Symbolfolge mit pA|B=pB|A=0.5 besitzt die Entropie H≈1bit/Symbol. Das heißt: In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge.
- Die linke (rote) Folge mit pA|B=pB|A=0.25 weist weniger Wechsel zwischen A und B auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun H≈0.72bit/Symbol kleiner.
- Die rechte (grüne) Symbolfolge mit pA|B=pB|A=0.8 hat die genau gleiche Entropie H≈0.72bit/Symbol wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... ABABAB ... ).
Für den allgemeineren Fall pA≠pB ist die Entropieberechnung der Zweiertupel etwas komplizierter. Mit den Verbundwahrscheinlichkeiten, zum Beispiel pAB=pA·pB|A, kann geschrieben werden:
- H2′=pA⋅pA|A⋅log21pA⋅pA|A+pA⋅pB|A⋅log21pA⋅pB|A+pB⋅pA|B⋅log21pB⋅pA|B+pB⋅pB|B⋅log21pB⋅pB|B.
Ersetzt man nun die Logarithmen der Produkte durch entsprechende Summen von Logarithmen, so erhält man das Ergebnis H2′=H1+HM mit
- H1=pA⋅(pA|A+pB|A)⋅log21pA+pB⋅(pA|B+pB|B)⋅log21pB=pA⋅log21pA+pB⋅log21pB=Hbin(pA)=Hbin(pB),
- HM=pA⋅pA|A⋅log21pA|A+pA⋅pB|A⋅log21pB|A+pB⋅pA|B⋅log21pA|B+pB⋅pB|B⋅log21pB|B.
Fazit: Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):
- H2=1/2⋅H2′=1/2⋅[H1+HM].
Anzumerken ist:
- Der erste Summand H1 ⇒ erste Entropienäherung ist allein abhängig von den Symbolwahrscheinlichkeiten.
- Bei einem symmetrischen Markovprozess ⇒ pA|B=pB|A ⇒ pA=pB=1/2 ergibt sich für diesen ersten Summanden H1=1bit/Symbol.
- Der zweite Summand HM muss gemäß der zweiten der oberen Gleichungen berechnet werden.
- Bei einem symmetrischen Markovprozess erhält man HM=Hbin(pA|B).
Nun wird dieses Ergebnis auf die k–te Entropienäherung erweitert. Hierbei wird der Vorteil von Markovquellen gegenüber anderen Quellen ausgenutzt, dass sich die Entropieberechnung für k–Tupel sehr einfach gestaltet. Für jede Markovquelle gilt nämlich:
- Hk=1/k⋅[H1+(k−1)⋅HM]⇒H2=1/2⋅[H1+HM],H3=1/3⋅[H1+2⋅HM],H4=1/4⋅[H1+3⋅HM],usw.
Zu diesem Beispiel ist noch anzumerken:
- Hätte man nicht die Markoveigenschaften der roten und der grünen Folge ausgenutzt, so hätte man das Ergebnis H≈0.72bit/Symbol erst nach langwierigen Berechnungen erhalten.
- Auf den nächsten Seiten wird gezeigt, dass bei einer Quelle mit Markoveigenschaften der Endwert H allein aus den Entropienäherungen H1 und H2 ermittelt werden kann. Ebenso lassen sich aus H1 und H2 alle Entropienäherungen Hk für k–Tupel in einfacher Weise berechnen ⇒ H3, H4, H5, ... , H100, ...
Fazit: Bildet man den Grenzübergang für k→∞, so erhält man für die tatsächliche Quellenentropie:
- H=limk→∞Hk=HM.
Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:
- Bei Markovquellen genügt die Bestimmung der Entropienäherungen H1 und H2. Damit lautet die Entropie einer Markovquelle:
- H=2⋅H2−H1.
- Durch H1 und H2 liegen auch alle weiteren Entropienäherungen Hk für k≥3 fest:
- Hk=2−kk⋅H1+2⋅(k−1)k⋅H2.
Diese Näherungen haben allerdings keine große Bedeutung. Wichtig ist meist nur der Grenzwert H. Bei Quellen ohne Markoveigenschaften berechnet man die Näherungen Hk nur deshalb, um den Grenzwert, also die tatsächliche Entropie, abschätzen zu können.
Über die Autoren
Dieses interaktive Berechnungstool wurde am Lehrstuhl für Nachrichtentechnik der Technischen Universität München konzipiert und realisiert.
- Die erste Version wurde 2007 von Thomas Großer im Rahmen seiner Diplomarbeit mit „FlashMX–Actionscript” erstellt (Betreuer: Günter Söder).
- 2018 wurde das Programm von Marwen Ben Ammar und Xiaohan Liu (Bachelorarbeit, Betreuer: Tasnád Kernetzky ) auf „HTML5” umgesetzt und neu gestaltet.
