Exercise 1.5: Binary Markov Source
Die Aufgabe 1.4 hat gezeigt, dass die Berechnung der Entropie bei einer gedächtnisbehafteten Quelle sehr aufwändig sein kann. Man muss dann zunächst (sehr viele) Entropienäherungen Hk für k–Tupel berechnen und kann erst dann mit dem Grenzübergang k→∞ die Quellenentropie ermitteln:
- H=limk→∞Hk.
Oft tendiert dabei Hk nur sehr langsam gegen den Grenzwert H.
Der Rechengang wird drastisch reduziert, wenn die Nachrichtenquelle Markoveigenschaften besitzt. Die Grafik zeigt das Übergangsdiagramm für eine binäre Markovquelle mit den zwei Zuständen (Symbolen) A und B.
- Dieses ist durch die beiden bedingten Wahrscheinlichkeiten pA|B=p und pB|A=q eindeutig bestimmt.
- Die bedingten Wahrscheinlichkeiten pA|A und pB|B sowie die Symbolwahrscheinlichkeiten pA und pB lassen sich daraus ermitteln.
Die Entropie der binären Markovkette (mit der Einheit „bit/Symbol”) lautet dann:
- H=HM=pAA⋅log21pA|A+pAB⋅log21pB|A+pBA⋅log21pA|B+pBB⋅log21pB|B.
Bei dieser Gleichung ist zu beachten, dass im Argument des Logarithmus dualis jeweils die bedingten Wahrscheinlichkeiten pA|A, pB|A, ... einzusetzen sind, während für die Gewichtung die Verbundwahrscheinlichkeiten pAA, pAB, ... zu verwenden sind.
Mit der Entropienäherung erster Ordnung,
- H1=pA⋅log21pA+pB⋅log21pB(Einheit:bit/Symbol),
sowie der oben angegebenen (tatsächlichen) Entropie H=HM lassen sich bei einer Markovquelle auch alle weiteren Entropienäherungen (k=2,,3, ...) direkt berechnen:
- Hk=1k⋅[H1+(k−1)⋅HM].
Hinweise:
- Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.
- Bezug genommen wird insbesondere auch auf die beiden Seiten Schnittmenge und Bedingte Wahrscheinlichkeit.
- Mit Ausnahme der Teilaufgabe (6) gelte stets p=1/4 und q=1/2.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
- Für die (ergodischen) Symbolwahrscheinlichkeiten einer Markovkette erster Ordnung gilt:
- pA=pA|BpA|B+pB|A,pB=pB|ApA|B+pB|A.
Fragebogen
Musterlösung
- 1. Hier gilt für die Übergangswahrscheinlichkeiten:
- pA|A=1−pB|A=1−q=0.5_,pB|B=1−pA|B=1−p=0.75_.
- Nach A sind A und B gleichwahrscheinlich. Nach B tritt B sehr viel häufiger als A auf.
- 2. Entsprechend den angegebenen Gleichungen gilt:
- pA=pp+q=0.250.25+0.50=0.333_,
- pB=qp+q=0.500.25+0.50=0.667_.
- 3. Mit den unter (b) berechneten Wahrscheinlichkeiten gilt:
- H1=Hbin(pA)=1/3⋅log2(3)+2/3⋅log2(1.5)=1.585−2/3=0.918bit/Symbol_.
- 4. Die Entropie der Markovquelle lautet entsprechend der Angabe
- H=pAA⋅log21pA|A+pAB⋅log21pB|A+pBA⋅log21pA|B+pBB⋅log21pB|B.
- Für die Verbundwahrscheinlichkeiten gilt:
- pAA=pA|A⋅pA=(1−q)⋅pp+q=1/2⋅1/43/4=16,pAB=pB|A⋅pA=q⋅pp+q=1/2⋅1/43/4=16,pBA=pA|B⋅pB=p⋅qp+q=pAB=16,pBB=pB|B⋅pB=(1−p)⋅qp+q=3/4⋅1/23/4=12
- ⇒H=1/6⋅log2(2)+1/6⋅log2(2)+1/6⋅log2(4)+1/2⋅log2(4/3)==1/6+1/6+2/6+1−1/2⋅log2(3)=0.875bit/Symbol_.
- 5. Allgemein gilt mit HM = H für die k–Entropienäherung:
- Hk=1k⋅[H1+(k−1)⋅HM].
- Daraus folgt:
- H2=12⋅[0.918+1⋅0.875]=0.897bit/Symbol_,H3=13⋅[0.918+2⋅0.875]=0.889bit/Symbol_,H4=14⋅[0.918+3⋅0.875]=0.886bit/Symbol_.
- 6. Mit dem neuen Parametersatz (p = 1/4, q = 3/4) erhält man für die Symbolwahrscheinlichkeiten: pA = 1/4 und pB = 3/4. Dieser Sonderfall führt demnach zu statistisch unabhängigen Symbolen:
- pA=pA|A=pA|B,pB=pB|A=pB|B.
- Damit ist die Entropie H identisch mit der Entropienäherung H1:
- H=H1=1/4⋅log2(4)+3/4⋅log2(4/3)=2−0.75⋅log2(3)=0.811bit/Symbol_.
- Die Entropienäherungen H2, H3, H4, ... liefern hier ebenfalls das Ergebnis 0.811 bit/Symbol.
