Aufgaben:Exercise 1.6: Non-Binary Markov Sources - Revision history

Guenter at 12:05, 10 August 2021

2021-08-10T12:05:03Z

Guenter at 11:43, 30 June 2021

2021-06-30T11:43:37Z

Guenter at 13:49, 21 June 2021

2021-06-21T13:49:42Z

Guenter at 13:45, 21 June 2021

2021-06-21T13:45:21Z

Guenter at 13:19, 21 June 2021

2021-06-21T13:19:43Z

Guenter at 13:08, 21 June 2021

2021-06-21T13:08:57Z

Guenter at 12:36, 21 June 2021

2021-06-21T12:36:28Z

Javier: Text replacement - "„" to """

2021-05-28T14:43:40Z

Text replacement - "„" to """

Javier: Text replacement - "”" to """

2021-05-28T14:39:58Z

Text replacement - "”" to """

Guenter at 16:39, 25 May 2021

2021-05-25T16:39:44Z

← Older revision		Revision as of 12:05, 10 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Nachrichtenquellen mit Gedächtnis~~	+	{{quiz-Header\|Buchseite=Information_Theory/Discrete_Sources_with_Memory
	}}		}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2253__Inf_A_1_6.png|right|frame|Markov sources with <br>$M = 3$&nbsp; and&nbsp; $M = 4$]]
+[[File:EN_Inf_A_1_6.png|right|frame|Markov sources with <br>$M = 3$&nbsp; and&nbsp; $M = 4$]]
 The graph shows two ergodic Markov sources &nbsp; $($German:&nbsp; "Markovquellen" &nbsp; &rArr; &nbsp; "$\rm MQ$"$)$:

@@ Line 53: / Line 53: @@
-{What are the actual source entropy&nbsp; $H$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ3$&nbsp;?
+{What are the actual source entropy&nbsp; $H= H_{k \to \infty}$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ3$&nbsp;?
 |type="{}"}
 $H \ = \ $ { 1.25 3% } $\ \rm bit/symbol$
@@ Line 69: / Line 69: @@
-{What are the actual source entropy&nbsp; $H$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ4$&nbsp;?
+{What are the actual source entropy&nbsp; $H= H_{k \to \infty}$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ4$&nbsp;?
 |type="{}"}
 $H \ = \ $ { 1 3% } $\ \rm bit/symbol$

@@ Line 24: / Line 24: @@
 The following equations of determination apply:
-:$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},$$
+:$$H= H_{k \to \infty} = 2 \cdot H_2 - H_1\hspace{0.05cm},$$
 :$$H_k =  {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ]
   \hspace{0.05cm}.$$

@@ Line 66: / Line 66: @@
 {Calculate the entropy approximation&nbsp; $H_2$&nbsp; of the Markov source&nbsp; $\rm MQ4$
 |type="{}"}
-$H_2 \ = \ $ { 1.5 3% } $\ \rm bit/symbol$.
+$H_2 \ = \ $ { 1.5 3% } $\ \rm bit/symbol$
@@ Line 79: / Line 79: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben.
+'''(1)'''&nbsp; The symbol probabilities of the ternary Markov source are given.
-*Daraus lässt sich die Entropienäherung&nbsp; $H_1$&nbsp; berechnen:
+*From this, the entropy approximation&nbsp; $H_1$&nbsp; can be calculated:
-:$$H_{\rm 1}  =  1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 )  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}
+:$$H_{\rm 1} = 1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 ) \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/symbol}}
   \hspace{0.05cm}.$$
-'''(2)'''&nbsp; Die Verbundwahrscheinlichkeit ist&nbsp; $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$,&nbsp; wobei&nbsp; $p_{\rm X}$&nbsp; die Symbolwahrscheinlichkeit von&nbsp; $\rm X$&nbsp; angibt und&nbsp; $p_{\rm Y|X}$&nbsp; die bedingte Wahrscheinlichkeit für&nbsp; $\rm Y$, unter der Voraussetzung, dass vorher&nbsp; $\rm X$&nbsp; aufgetreten ist.
+'''(2)'''&nbsp; The composite probability is&nbsp; $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$,&nbsp; where&nbsp; $p_{\rm X}$&nbsp; gives the symbol probability of&nbsp; $\rm X$&nbsp; and&nbsp; $p_{\rm Y|X}$&nbsp; gives the conditional probability of&nbsp; $\rm Y$, given that previously&nbsp; $\rm X$&nbsp; occurred.
-*$\rm X$&nbsp; und&nbsp; $\rm Y$&nbsp; sind hier Platzhalter für die Symbole&nbsp; $\rm N$,&nbsp; $\rm P$&nbsp; und&nbsp; $\rm M$.&nbsp; Dann gilt:
+*$\rm X$&nbsp; and&nbsp; $\rm Y$&nbsp; are here placeholders for the symbols&nbsp; $\rm N$,&nbsp; $\rm P$&nbsp; and&nbsp; $\rm M$.&nbsp; Then holds:
 :$$p_{\rm NN} = 1/2 \cdot 1/2 = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm PP} =  1/4 \cdot 0 = 0\hspace{0.05cm},\hspace{0.2cm}p_{\rm MM} =  1/4 \cdot 0 = 0 \hspace{0.05cm},$$
 :$$ p_{\rm NP} =  1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm PM} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm MN} =  1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$
@@ Line 97: / Line 97: @@
-'''(3)'''&nbsp; $\rm MQ3$&nbsp; weist Markoveigenschaften auf.
+'''(3)'''&nbsp; $\rm MQ3$&nbsp; has Markov properties.
-* Deshalb können aus&nbsp; $H_1$&nbsp; und&nbsp; $H_2$&nbsp; alle Näherungen&nbsp; $H_3$,&nbsp; $H_4$,&nbsp; ... und auch der Grenzwert&nbsp; $H =H_\infty$&nbsp;  für&nbsp; $k \to \infty$&nbsp; angegeben werden:
+* Therefore, from&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; all approximations&nbsp; $H_3$,&nbsp; $H_4$,&nbsp; ... and also the limit&nbsp; $H =H_\infty$&nbsp; for&nbsp; $k \to \infty$&nbsp; are given:
-:$$H  =  2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
+:$$H = 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/symbol}}\hspace{0.05cm},$$
-:$$ H_3 \hspace{0.1cm} =  \hspace{0.1cm}=  (H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
+:$$ H_3 \hspace{0.1cm} = \hspace{0.1cm}(H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/symbol}}\hspace{0.05cm},$$
-:$$ H_4 = (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
+:$$ H_4 = (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/symbol}}\hspace{0.05cm}.$$
-*Die zehnte Entropienäherung unterscheidet sich noch immer vom Endwert&nbsp; $H = 1.25 \, \rm bit/Symbol$,&nbsp; wenn auch nur  geringfügig&nbsp; $($um $2\%)$&nbsp;:
+*The tenth entropy approximation still differs from the final value&nbsp; $H = 1.25 \,\rm bit/symbol$,&nbsp; albeit only slightly&nbsp; $($by $2\%)$&nbsp;:
-:$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10  {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
+:$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10 {= 1.275 \,{\rm bit/symbol}}\hspace{0.05cm}.$$
-'''(4)'''&nbsp; Entsprechend der Angabe sind bei&nbsp; $\rm MQ4$&nbsp; die&nbsp; $M = 4$&nbsp; Symbole gleichwahrscheinlich.
+'''(4)'''&nbsp; According to the specification, for&nbsp; $\rm MQ4$&nbsp; the&nbsp; $M = 4$&nbsp; symbols are equally probable.
-*Daraus folgt:
+*From this follows:
-:$$H_{\rm 1}  = H_{\rm 0}  = {\rm log}_2\hspace{0.1cm} (4)  \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}}
+:$$H_{\rm 1} = H_{\rm 0} = {\rm log}_2\hspace{0.1cm} (4) \hspace{0.15cm} \underline {= 2 \,{\rm bit/symbol}}
   \hspace{0.05cm}.$$
-'''(5)'''&nbsp; Von den&nbsp; $M^2 = 16$&nbsp; möglichen Zweiertupeln sind nun acht Kombinationen nicht möglich:
+*The eight other combinations (two-tuples) each yield the composite probability value&nbsp; $1/8$, as shown in two examples:
-:$$\rm NP, NO, PP, PO, OM, ON, MM,  MN.$$
+:$$p_{\rm NN} = p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\hspace{0.5cm}
 {{ML-Fuß}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2253__Inf_A_1_6.png|right|frame|Markovquellen mit <br>$M = 3$&nbsp; und&nbsp; $M = 4$]]
+[[File:P_ID2253__Inf_A_1_6.png|right|frame|Markov sources with <br>$M = 3$&nbsp; and&nbsp; $M = 4$]]
-Die Grafik zeigt zwei ergodische Markovquellen&nbsp; $\rm (MQ)$:
+The graph shows two ergodic Markov sources &nbsp; $($German:&nbsp; "Markovquellen" &nbsp; &rArr; &nbsp; "$\rm MQ$"$)$:
-* Die Quelle&nbsp; $\rm MQ3$&nbsp; ist durch&nbsp; $M = 3$&nbsp; Zustände (Symbole)&nbsp; $\rm N$,&nbsp; $\rm M$,&nbsp; $\rm P$&nbsp; gekennzeichnet.&nbsp; Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
+* The source&nbsp; $\rm MQ3$&nbsp; is denoted by&nbsp; $M = 3$&nbsp; states&nbsp; (symbols)&nbsp; $\rm N$,&nbsp; $\rm M$,&nbsp; $\rm P$.&nbsp; Due to stationarity, the probabilities have the following values:
-:$$p_{\rm N} =  1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
+:$$p_{\rm N} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
-* Bei der Quelle&nbsp; $\rm MQ4$&nbsp; ist zusätzlich der Zustand&nbsp; $\rm O$&nbsp; möglich &nbsp; &#8658; &nbsp; $M = 4$.&nbsp; Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
+* For the source&nbsp; $\rm MQ4$&nbsp; the state&nbsp; $\rm O$&nbsp; is additionally possible &nbsp; &#8658; &nbsp; $M = 4$.&nbsp; Due to the symmetric transitions, the stationary probabilities are all equal:
-:$$p_{\rm N} = p_{\rm M} = p_{\rm O} =  p_{\rm P} = 1/4\hspace{0.05cm}.$$
+:$$p_{\rm N} = p_{\rm M} = p_{\rm O} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
-Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen &ndash; und nur bei diesen &ndash; durch
+In terms of information theory, Markov sources are of particular importance, since with these &ndash; and only with these &ndash; by
-* $H_1$&nbsp;  (erste Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und
+* $H_1$&nbsp; (first entropy approximation, based only on the symbol probabilities), and
-* $H_2$&nbsp; (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel)
+* $H_2$&nbsp; (second entropy approximation, computable with the composite probabilities for all two-tuples)
-gleichzeitig auch bestimmt sind:
+are also determined at the same time:
-* die weiteren Entropienäherungen&nbsp; $H_k$&nbsp; mit&nbsp; $k = 3, \ 4$,&nbsp; ...  und
+* the further entropy approximations&nbsp; $H_k$&nbsp; with&nbsp; $k = 3, \ 4$,&nbsp; ...,  and
-* die tatsächliche Quellenentropie&nbsp; $H$.
+* the actual (final) source entropy&nbsp; $H$.
-Es gelten folgende Bestimmungsgleichungen:
+The following equations of determination apply:
 :$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},$$
 :$$H_k =  {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ]
@@ Line 32: / Line 32: @@
@@ Line 45: / Line 43: @@
 <quiz display=simple>
-{Berechnen Sie die Entropienäherung&nbsp; $H_1$&nbsp;  der Markovquelle&nbsp;  $\rm MQ3$.
+{Calculate the entropy approximation&nbsp; $H_1$&nbsp; of the Markov source&nbsp; $\rm MQ3$.
 |type="{}"}
-$H_1 \ = \ $  { 1.5 3% } $\ \rm bit/Symbol$
+$H_1 \ = \ $ { 1.5 3% } $\ \rm bit/symbol$
-{Berechnen Sie die Entropienäherung&nbsp; $H_2$&nbsp;  der Markovquelle&nbsp;  $\rm MQ3$.
+{Calculate the entropy approximation&nbsp; $H_2$&nbsp; of the Markov source&nbsp; $\rm MQ3$.
 |type="{}"}
-$H_2 \ = \  $ { 1.375 3% } $\ \rm bit/Symbol$
+$H_2 \ = \ $ { 1.375 3% } $\ \rm bit/symbol$
-{Wie groß sind für&nbsp; $\rm MQ3$&nbsp; die tatsächliche Quellenentropie&nbsp; $H$&nbsp; und die Näherungen&nbsp; $H_3$&nbsp; und&nbsp; $H_4$?
+{What are the actual source entropy&nbsp; $H$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ3$&nbsp;?
 |type="{}"}
-$H \ = \ $  { 1.25 3% } $\ \rm bit/Symbol$
+$H \ = \ $ { 1.25 3% } $\ \rm bit/symbol$
-$H_3 \ = \ $ { 1.333 3% } $\ \rm bit/Symbol$
+$H_3 \ = \ $ { 1.333 3% } $\ \rm bit/symbol$
-$H_4 \ = \ $ { 1.3125 3% } $\ \rm bit/Symbol$
+$H_4 \ = \ $ { 1.3125 3% } $\ \rm bit/symbol$
+{Calculate the entropy approximation&nbsp; $H_1$&nbsp; of the Markov source&nbsp; $\rm MQ4$.
 |type="{}"}
-$H_1 \ = \  $ { 2 3% } $\ \rm bit/Symbol$
+$H_1 \ = \ $ { 2 3% } $\ \rm bit/symbol$
-{Berechnen Sie die Entropienäherung&nbsp; $H_2$&nbsp;  der Markovquelle&nbsp;  $\rm MQ4$.
+{Calculate the entropy approximation&nbsp; $H_2$&nbsp; of the Markov source&nbsp; $\rm MQ4$
 |type="{}"}
-$H_2 \ =  \ $ { 1.5 3% } $\ \rm bit/Symbol$
+$H_2 \ = \ $ { 1.5 3% } $\ \rm bit/symbol$.
-{Wie groß sind für&nbsp; $\rm MQ4$&nbsp; die tatsächliche Quellenentropie&nbsp; $H$&nbsp; und die Näherungen&nbsp; $H_3$&nbsp; und&nbsp; $H_4$?
+{What are the actual source entropy&nbsp; $H$&nbsp; and the approximations&nbsp; $H_3$&nbsp; and&nbsp; $H_4$ for&nbsp; $\rm MQ4$&nbsp;?
 |type="{}"}
-$H \ =  \ $ { 1 3% } $\ \rm bit/Symbol$
+$H \ = \ $ { 1 3% } $\ \rm bit/symbol$
-$H_3 \ =  \ $ { 1.333 3% } $\ \rm bit/Symbol$
+$H_3 \ = \ $ { 1.333 3% } $\ \rm bit/symbol$
-$H_4 \ =  \ $ { 1.25 3% } $\ \rm bit/Symbol$
+$H_4 \ = \ $ { 1.25 3% } $\ \rm bit/symbol$
 </quiz>

@@ Line 36: / Line 36: @@
 ''Hinweise:''
-*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Discrete_Sources_with_Memory|Discrete Sources with Memory]].
 *Bezug genommen wird insbesondere auf die Seite&nbsp;  [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]].
 *Bei allen Entropien ist die Pseudoeinheit "bit/Symbol" hinzuzufügen.

@@ Line 38: / Line 38: @@
 *Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
 *Bezug genommen wird insbesondere auf die Seite&nbsp;  [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]].
-*Bei allen Entropien ist die Pseudoeinheit &bdquo;bit/Symbol&rdquo; hinzuzufügen.
+*Bei allen Entropien ist die Pseudoeinheit &bdquo;bit/Symbol" hinzuzufügen.

← Older revision		Revision as of 16:39, 25 May 2021
Line 140:		Line 140:


−	[[Category:Information Theory: Exercises\|^1.2 ~~Nachrichtenquellen mit Gedächtnis~~^]]	+	[[Category:Information Theory: Exercises\|^1.2 Sources with Memory^]]