Difference between revisions of "Aufgaben:Exercise 1.6: Non-Binary Markov Sources"
From LNTwww
| Line 46: | Line 46: | ||
| − | {Wie groß sind für '''MQ3''' die | + | {Wie groß sind für '''MQ3''' die tatsächliche Quellenentropie H und die Näherungen H3 und H4? |
|type="{}"} | |type="{}"} | ||
H = { 1.25 3% } bit/Symbol | H = { 1.25 3% } bit/Symbol | ||
| Line 63: | Line 63: | ||
| − | {Wie groß sind für '''MQ4'''die Näherungen H3 und H4 | + | {Wie groß sind für '''MQ4''' die tatsächliche Quellenentropie H und die Näherungen H3 und H4? |
|type="{}"} | |type="{}"} | ||
| + | H = { 1 3% } bit/Symbol | ||
H3 = { 1.333 3% } bit/Symbol | H3 = { 1.333 3% } bit/Symbol | ||
H4 = { 1.25 3% } bit/Symbol | H4 = { 1.25 3% } bit/Symbol | ||
| − | |||
Revision as of 10:25, 2 May 2017
Die Grafik zeigt zwei ergodische Markovquellen (MQ):
- Die Quelle MQ3 ist durch M=3 Zustände (Symbole) N, M, P gekennzeichnet. Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
- pN=1/2,pM=pP=1/4.
- Bei der Quelle MQ4 ist zusätzlich der Zustand O möglich ⇒ M=4. Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
- pN=pM=pO=pP=1/4.
Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen – und nur bei diesen – durch
- H1 (Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und
- H2 (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel)
gleichzeitig auch bestimmt sind:
- die weiteren Entropienäherungen Hk mit k=3,4, ... und
- die tatsächliche Quellenentropie H.
Es gelten folgende Bestimmungsgleichungen:
- H=2⋅H2−H1,Hk=1/k⋅[H1+(k−1)⋅H].
Hinweise:
- Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.
- Bezug genommen wird insbesondere auf die Seite Nichtbinäre Markovquellen.
- Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
- 1. Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben. Daraus lässt sich die Entropienäherung H1 berechnen:
- H1=1/2⋅log2(2)+2⋅1/4⋅log2(4)=1.5bit/Symbol_.
- 2. Die Verbundwahrscheinlichkeit ist pXY = pX · pY|X, wobei pX die Symbolwahrscheinlichkeit von X angibt und pY|X die bedingte Wahrscheinlichkeit für Y, unter der Voraussetzung, dass vorher X aufgetreten ist. X und Y sind hier Platzhalter für die Symbole N, P, M. Dann gilt:
- pNN=1/2⋅1/2=1/4,pPP=1/4⋅0=0,pMM=1/4⋅0=0,pNP=1/2⋅1/4=1/8,pPM=1/4⋅1/2=1/8,pMN=1/4⋅1/2=1/8,pNM=1/2⋅1/4=1/8,pMP=1/4⋅1/2=1/8,pPN=1/4⋅1/2=1/8
- ⇒H2=12⋅[1/4⋅log2(4)+6⋅1/8⋅log2(8)]=1.375bit/Symbol_.
- 3. Da MQ3 Markoveigenschaften aufweist, können aus H1 und H2 alle Entropienäherungen <nobr>Hk (k = 3, 4, ... )</nobr> direkt angegeben werden und auch der Grenzwert H = Hk für k → ∞:
- H=2⋅H2−H1=2⋅1.375−1.5=1.250bit/Symbol_,H3=(H1+2⋅H)/3=(1.5+2⋅1.25)/3=1.333bit/Symbol_,H4=(H1+3⋅H)/4=(1.5+3⋅1.25)/4=1.3125bit/Symbol_.
- Die 10. Entropienäherung unterscheidet sich noch immer, wenn auch nur geringfügig (um 2%) vom Endwert H = 1.25 bit/Symbol:
- H10=(H1+9⋅H)/10=(1.5+9⋅1.25)/10=1.275bit/Symbol.
- 4. Entsprechend der Angabe sind hier die Symbole gleichwahrscheinlich. Daraus folgt:
- H1=H0=log2(4)=2bit/Symbol_.
- 5. Von den M2 = 16 möglichen Zweiertupeln sind acht Kombinationen nicht möglich: NP, NO, PP, PO, OM, ON, MM, MN. Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert 1/8, wie an zwei Beispielen gezeigt werden soll:
- pNN=pN⋅pN|N=1/4⋅1/2=1/8,pMP=pM⋅pP|M=1/4⋅1/2=1/8.
- ⇒H2=12⋅[8⋅18⋅log2(8)]=1.5bit/Symbol_.
- 6. Aufgrund der Markoveigenschaft gilt hier:
- H=2⋅H2−H1=2⋅1.5−2=1bit/Symbol_,H3=(H1+2⋅H)/3=(2+2⋅1)/3=1.333bit/Symbol_,H4=(H1+3⋅H)/4=(2+3⋅1)/4=1.250bit/Symbol_.
- Auch hier unterscheidet sich die 10. Näherung noch deutlich vom Endwert, nämlich um 10%:
- H10=(H1+9⋅H)/10=(2+9⋅1)/10=1.1bit/Symbol.
- Eine Abweichung um 2% ergibt sich hier erst für k = 50. Zum Vergleich: Bei der Markovquelle MQ3 wurde diese Annäherung bereits mit k = 10 erreicht.
