Difference between revisions of "Information Theory/Discrete Sources with Memory"

From LNTwww
 
(64 intermediate revisions by 7 users not shown)
Line 1: Line 1:
  
 
{{Header
 
{{Header
|Untermenü=Entropie wertdiskreter Nachrichtenquellen
+
|Untermenü=Entropy of Discrete Sources
|Vorherige Seite=Gedächtnislose Nachrichtenquellen
+
|Vorherige Seite=Discrete Memoryless Sources
|Nächste Seite=Natürliche wertdiskrete Nachrichtenquellen
+
|Nächste Seite=Natural Discrete Sources
 
}}
 
}}
  
==Ein einfaches einführendes Beispiel  ==
+
==A simple introductory example ==
Zu Beginn des ersten Kapitels haben wir eine gedächtnislose Nachrichtenquelle mit dem Symbolvorrat $\rm \{A, B, C, D\}$   ⇒   $M = 4$ betrachtet. Eine beispielhafte Symbolfolge ist in der nachfolgenden Grafik als Quelle $\rm Q1$ nochmals dargestellt. Mit den Symbolwahrscheinlichkeiten $p_{\rm A} = 0.4 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.3 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.2 \hspace{0.05cm},\hspace{0.2cm}  
+
<br>
p_{\rm D} = 0.1\hspace{0.05cm}$ ergibt sich die Entropie zu
+
{{GraueBox|TEXT= 
 +
$\text{Example 1:}$&nbsp;
 +
At the&nbsp; [[Information_Theory/Discrete Memoryless Sources#Model_and_requirements|"beginning of the first chapter"]]&nbsp; we have considered a memoryless message source with the symbol set&nbsp; $\rm \{A, \ B, \ C, \ D\}$ &nbsp; ⇒ &nbsp; $M = 4$ &nbsp;. &nbsp; An exemplary symbol sequence is shown again in the following figure as source&nbsp; $\rm Q1$&nbsp;.  
 +
 
 +
*With the symbol probabilities&nbsp; $p_{\rm A} = 0.4 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.3 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.2 \hspace{0.05cm},\hspace{0.2cm}  
 +
p_{\rm D} = 0.1\hspace{0.05cm}$&nbsp; the entropy is
 
   
 
   
:$$H \hspace{-0.05cm}= 0.4 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.4} + 0.3 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.3} +0.2 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.2} +0.1 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.1} \approx 1.84 \hspace{0.05cm}{\rm bit/Symbol}
+
:$$H \hspace{-0.05cm}= 0.4 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.4} + 0.3 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.3} + 0.2 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.2} + 0.1 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.1} \approx 1.84 \hspace{0.05cm}{\rm bit/symbol}
 
  \hspace{0.01cm}.$$
 
  \hspace{0.01cm}.$$
  
Aufgrund der ungleichen Auftrittswahrscheinlichkeiten der Symbole ist die Entropie kleiner als der Entscheidungsgehalt $H_0 = \log_2 M = 2 \hspace{0.05cm} \rm bit/Symbol$.
+
*Due to the unequal symbol probabilities the entropy is smaller than&nbsp; $H_0 = \log_2 M = 2 \hspace{0.05cm} \rm bit/symbol$.
  
[[File:P_ID2238__Inf_T_1_2_S1a_neu.png|frame|Quaternäre Nachrichtenquelle ohne/mit Gedächtnis]]
+
[[File:EN_Inf_T_1_2_S1a.png|right|frame|Quaternary source without/with memory]]
 +
<br><br>
 +
The source&nbsp; $\rm Q2$&nbsp; is almost identical to the source&nbsp; $\rm Q1$, except that each individual symbol is output not only once, but twice in a row:&nbsp; $\rm A ⇒ AA$,&nbsp; $\rm B ⇒ BB$,&nbsp; and so on.
 +
*It is obvious that&nbsp; $\rm Q2$&nbsp; has a smaller entropy (uncertainty) than&nbsp; $\rm Q1$.
 +
*Because of the simple repetition code,&nbsp; the entropy
 +
:$$H = 1.84/2 = 0.92 \hspace{0.05cm} \rm bit/symbol$$
 +
:has only half the size, although the occurrence probabilities have not changed.}}
  
Die Quelle $\rm Q2$ ist weitgehend identisch mit der Quelle $\rm Q1$, außer, dass jedes einzelne Symbol nicht nur einmal, sondern zweimal nacheinander ausgegeben wird: $\rm A ⇒ AA$, $\rm B ⇒ BB$, usw.
 
*Es ist offensichtlich, dass $\rm Q2$ eine kleinere Entropie (Unsicherheit) aufweist als $\rm Q1$.
 
*Aufgrund des einfachen Wiederholungscodes ist nun $H = 1.84/2 = 0.92 \hspace{0.05cm} \rm bit/Symbol$ nur halb so groß, obwohl sich an den Auftrittswahrscheinlichkeiten nichts geändert hat.
 
  
 
+
{{BlaueBox|TEXT= 
Dieses Beispiel zeigt:
+
$\text{Conclusion:}$&nbsp;
*Die Entropie einer gedächtnisbehafteten Quelle ist kleiner als die Entropie einer gedächtnislosen Quelle mit gleichen Symbolwahrscheinlichkeiten.
+
This example shows:
*Es müssen nun auch die statistischen Bindungen innerhalb der Folge $〈 q_ν 〉$ berücksichtigt werden, nämlich die Abhängigkeit des Symbols $q_ν$ von den Vorgängersymbolen $q_{ν–1}$, $q_{ν–2}$, ...  
+
#The entropy of a source with memory is smaller than the entropy of a memoryless source with equal symbol probabilities.
 +
#The statistical bindings within the sequence&nbsp; $〈 q_ν 〉$&nbsp; have to be considered now,  
 +
#namely the dependency of the symbol&nbsp; $q_ν$&nbsp; from the predecessor symbols&nbsp; $q_{ν-1}$,&nbsp; $q_{ν-2}$, ... }}
 
   
 
   
 
 
 
 
==Entropie hinsichtlich Zweiertupel ==  
+
== Entropy with respect to two-tuples ==  
Wir betrachten weiterhin die Quellensymbolfolge $〈 q_1, \hspace{0.05cm} q_2$, ... , $q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1}〉$, ..., interessieren uns aber nun für die Entropie zweier aufeinanderfolgender Quellensymbole. Alle Quellensymbole $q_ν$ entstammen einem Alphabet mit dem Symbolunfang $M$, so dass es für die Kombination  $(q_ν, \hspace{0.05cm}q_{ν+1})$ genau $M^2$ mögliche Symbolpaare mit folgenden [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Verbundwahrscheinlichkeiten]] gibt:
+
<br>
 +
We continue to look at the source symbol sequence&nbsp; $〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν-1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} .\hspace{0.05cm}\text{...} \hspace{0.05cm}〉$&nbsp; and now consider the entropy of two successive source symbols.  
 +
*All source symbols&nbsp; $q_ν$&nbsp; are taken from an alphabet with the symbol set size&nbsp; $M$,&nbsp; so that for the combination&nbsp; $(q_ν, \hspace{0.05cm}q_{ν+1})$&nbsp; there are exactly&nbsp; $M^2$&nbsp; possible symbol pairs with the following&nbsp; [[Theory_of_Stochastic_Signals/Set_Theory_Basics#Intersection_set|"combined probabilities"]]:
 
   
 
   
 
:$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1})
 
:$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Daraus ist die ''Verbundentropie'' eines Zweier–Tupels berechenbar:
+
*From this, the&nbsp; &raquo;'''compound entropy'''&laquo;&nbsp; of two consecutive symbols can be computed:
 
   
 
   
:$$H_2' = \sum_{q_{\nu} \in \{ q_{\mu}\hspace{-0.08cm} \}} \sum_{q_{\nu+1} \in \{ q_{\mu}\hspace{-0.08cm} \}}\hspace{-0.1cm}{\rm Pr}(q_{\nu}\cap q_{\nu+1}) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu}\cap q_{\nu+1})} \hspace{0.4cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Zweiertupel})
+
:$$H_2\hspace{0.05cm}' = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} \ \sum_{q_{\nu+1}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm} q_{\mu}\hspace{0.01cm} \}}\hspace{-0.1cm}{\rm Pr}(q_{\nu}\cap q_{\nu+1}) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu}\cap q_{\nu+1})} \hspace{0.4cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/two&ndash;tuple})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Der Index 2 symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht. Um den mittleren Informationsgehalt pro Symbol zu erhalten, muss $H_2'$ noch halbiert werden:
+
:The index "2" symbolizes that the entropy thus calculated refers to&nbsp; &raquo;'''two-tuples'''&laquo;.  
 +
 
 +
*To get the average information content per symbol,&nbsp; $H_2\hspace{0.05cm}'$&nbsp; has to be divided in half:
 
   
 
   
:$$H_2 = {H_2'}/{2}  \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
+
:$$H_2 = {H_2\hspace{0.05cm}'}/{2}  \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die im Kapitel [[Informationstheorie/Gedächtnislose_Nachrichtenquellen#Modell_und_Voraussetzungen|Gedächtnislose Nachrichtenquellen]] definierte Entropie mit $H_1$:
+
*In order to achieve a consistent nomenclature, we now label the entropy defined in chapter&nbsp; [[Information_Theory/Discrete_Memoryless_Sources#Model_and_requirements|"Memoryless Message Sources"]]&nbsp; with&nbsp; $H_1$:
+
 
:$$H_1 = \sum_{q_{\nu}\in \{ q_{\mu}\hspace{-0.03cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm ld}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu})} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
+
:$$H_1 = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu})} \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Der Index 1 soll darauf hinweisen, dass $H_1$ ausschließlich die Symbolwahrscheinlichkeiten berücksichtigt und nicht statistischen Bindungen zwischen Symbolen innerhalb der Folge. Mit dem Entscheidungsgehalt $H_0 = \log_2 \ M$ ergibt sich dann folgende Größenbeziehung:
+
*The index "1" is supposed to indicate that&nbsp; $H_1$&nbsp; considers only the symbol probabilities and not statistical bindings between symbols within the sequence.&nbsp; With&nbsp; $H_0 = \log_2 \ M$&nbsp; the following size relation results:
 
   
 
   
 
:$$H_0 \ge H_1 \ge H_2
 
:$$H_0 \ge H_1 \ge H_2
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Bei statistischer Unabhängigkeit der Folgenelemente ist $H_2 = H_1$.
+
*With statistical independence of the sequence elements &nbsp; &rArr; &nbsp; $H_2 = H_1$.
 
 
Die bisherigen Gleichungen geben jeweils einen Scharmittelwert an. Die für die Berechnung von $H_1$ und $H_2$ benötigten Wahrscheinlichkeiten lassen sich aber auch als Zeitmittelwerte aus einer sehr langen Folge berechnen oder – etwas genauer ausgedrückt – durch die entsprechenden [[Stochastische_Signaltheorie/Wahrscheinlichkeit_und_relative_Häufigkeit#Bernoullisches_Gesetz_der_gro.C3.9Fen_Zahlen|relativen Häufigkeiten]] annähern.
 
  
Verdeutlichen wir uns nun die Berechnung der Entropienäherungen $H_1$ und $H_2$ an drei Beispielen.
 
  
 +
The previous equations each indicate an&nbsp; "ensemble mean value". &nbsp; The probabilities required for the calculation of&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; can, however, also be calculated as time averages from a very long sequence or, more precisely, approximated by the corresponding&nbsp; [[Theory_of_Stochastic_Signals/From_Random_Experiment_to_Random_Variable#Bernoulli.27s_law_of_large_numbers|"relative frequencies"]].
  
{{Beispiel}}&nbsp; '''[A]'''
+
Let us now illustrate the calculation of entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; with three examples.
Wir betrachten zunächst die Folge $〈 q_1$, ... , $q_{50}$ 〉 gemäß der folgernden Grafik, wobei die Folgenelemente $q_ν$ dem Alphabet $\rm \{A, B, C \}$ entstammen  &nbsp; ⇒  &nbsp; Symbolumfang $M = 3$.
 
  
[[File:Inf_T_1_2_S2_vers2.png|frame|Ternäre Symbolfolge und Bildung von Zweier–Tupeln]]
+
[[File:Inf_T_1_2_S2_vers2.png|right|frame|Ternary symbol sequence and formation of two-tuples]]
 +
{{GraueBox|TEXT= 
 +
$\text{Example 2:}$&nbsp;
 +
We will first look at the sequence&nbsp; $〈 q_1$, ... , $q_{50} \rangle $&nbsp; according to the graphic, where the sequence elements&nbsp; $q_ν$&nbsp; originate from the alphabet $\rm \{A, \ B, \ C \}$ &nbsp; ⇒ &nbsp; the symbol set size is&nbsp; $M = 3$.
  
Durch Zeitmittelung über die $50$ Symbole erhält man die Symbolwahrscheinlichkeiten $p_{\rm A} ≈ 0.5$, $p_{\rm B} ≈ 0.35$ und $p_{\rm C} ≈ 0.2$, womit man die Entropienäherung erster Ordnung berechnen kann:
+
*By time averaging over&nbsp; $50$&nbsp; symbols one gets the symbol probabilities&nbsp; $p_{\rm A} ≈ 0.5$, &nbsp; $p_{\rm B} ≈ 0.3$ &nbsp;and&nbsp; $p_{\rm C} ≈ 0.2$, with which one can calculate the first order entropy approximation:
 
   
 
   
:$$H_1 = 0.5 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.5} + 0.3 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.3} +0.2 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.2}  \approx \, 1.486 \,{\rm bit/Symbol}
+
:$$H_1 = 0.5 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.5} + 0.3 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.3} + 0.2 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.2}  \approx \, 1.486 \,{\rm bit/symbol}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Aufgrund der nicht gleichwahrscheinlichen Symbole ist $H_1 < H_0 = 1.585 \hspace{0.05cm} \rm bit/Symbol$. Als Näherung für die Wahrscheinlichkeiten von Zweiertupeln erhält man aus der obigen Folge:
+
*Due to the not equally probable symbols&nbsp; $H_1 < H_0 = 1.585 \hspace{0.05cm}. \rm bit/symbol$.&nbsp; As an approximation for the probabilities of two-tuples one gets from the above sequence:
 
   
 
   
:$$\begin{align*}p_{\rm AA} \hspace{-0.1cm}& = \hspace{-0.1cm} 14/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AB} = 8/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AC} = 3/49\hspace{0.05cm}, \\
+
:$$\begin{align*}p_{\rm AA} \hspace{-0.1cm}& = \hspace{-0.1cm} 14/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AB} = 8/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AC} = 3/49\hspace{0.05cm}, \\\
  p_{\rm BA} \hspace{-0.1cm}& = \hspace{0.07cm} 7/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm BB} = 2/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm BC} = 5/49\hspace{0.05cm}, \\
+
  p_{\rm BA} \hspace{-0.1cm}& = \hspace{0.07cm} 7/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm BB} = 2/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm BC} = 5/49\hspace{0.05cm}, \\\
  p_{\rm CA} \hspace{-0.1cm}& = \hspace{0.07cm} 4/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm CB} = 5/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm CC} = 1/49\hspace{0.05cm}.\end{align*}$$
+
  p_{\rm CA} \hspace{-0.1cm}& = \hspace{0.07cm} 4/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm CB} = 5/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm CC} = 1/49\hspace{0.05cm}.\end{align*}$$
 +
 
 +
*Please note that the&nbsp; $50$&nbsp; sequence elements can only be formed from&nbsp; $49$&nbsp; two-tuples&nbsp; $(\rm AA$, ... , $\rm CC)$&nbsp; which are marked in different colors in the graphic.
  
Beachten Sie, dass aus den $50$ Folgenelementen nur $49$ Zweiertupel $(\rm AA$, ... , $\rm AACC)$ gebildet werden können, die in der obigen Grafik farblich unterschiedlich markiert sind.
+
#The entropy approximation&nbsp; $H_2$&nbsp; should actually be equal to&nbsp; $H_1$&nbsp; since the given symbol sequence comes from a memoryless source.  
Die daraus berechenbare Entropienäherung $H_2$ sollte eigentlich gleich $H_1$ sein, da die gegebene Symbolfolge von einer gedächtnislosen Quelle stammt. Aufgrund der kurzen Folgenlänge $N = 50$ und der daraus resultierenden statistischen Ungenauigkeit ergibt sich ein etwas kleinerer Wert: &nbsp; $H_2 ≈ 1.39\hspace{0.05cm} \rm   bit/Symbol$.
+
#Because of the short sequence length&nbsp; $N = 50$&nbsp; and the resulting statistical inaccuracy, however, a smaller value results: &nbsp;  
{{end}}
+
::$$H_2 ≈ 1.39\hspace{0.05cm} \rm bit/symbol.$$}}
  
  
{{Beispiel}}&nbsp; '''[B]'''
+
{{GraueBox|TEXT= 
Nun betrachten wir eine ''gedächtnislose Binärquelle'' mit gleichwahrscheinlichen Symbolen, das heißt es gelte $p_{\rm A} = p_{\rm A} = 1/2$. Die ersten zwanzig Folgeelemente lauten: &nbsp; $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABAB$ ...
+
$\text{Example 3:}$&nbsp;
*Aufgrund der gleichwahrscheinlichen Binärsymbole ist $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
+
Now let us consider a&nbsp; &raquo;'''memoryless&nbsp; binary source'''&laquo;&nbsp; with equally probable symbols, i.e. there would be&nbsp; $p_{\rm A} = p_{\rm B} = 1/2$.&nbsp; The first twenty subsequent elements are &nbsp; $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABABAB$ ...
*Die Verbundwahrscheinlichkeit $p_{\rm AB}$ der Kombination $\rm AB$ ist gleich $p_{\rm A} · p_{\rm B} = 1/4$. Ebenso gilt $p_{\rm AA} = p_{\rm BB} = p_{\rm BA} = 1/4$. Damit erhält man für die zweite Entropienäherung
+
*Because of the equally probable binary symbols &nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
 +
 
 +
*The compound probability&nbsp; $p_{\rm AB}$&nbsp; of the combination&nbsp; $\rm AB$&nbsp; is equal to&nbsp; $p_{\rm A} \cdot p_{\rm B} = 1/4$.&nbsp; Also $p_{\rm AA} = p_{\rm BB} = p_{\rm BA} = 1/4$.
 +
 +
*This gives for the second entropy approximation
 
   
 
   
:$$H_2 = {1}/{2} \cdot \left [ {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 + {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 \right ] = 1 \,{\rm bit/Symbol} = H_1 = H_0
+
:$$H_2 = {1}/{2} \cdot \big [ {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 + {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 \big ] = 1 \,{\rm bit/symbol} = H_1 = H_0
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
''Hinweis'': Aus der oben angegebenen Folge ergeben sich aufgrund der kurzen Länge etwas andere Verbundwahrscheinlichkeiten, nämlich $p_{\rm AA} = 6/19$, $p_{\rm BB} = 5/19$ und $p_{\rm AB} = p_{\rm BA} = 4/19$.
+
<u>Note</u>: &nbsp; Due to the short length of the given sequence the probabilities are slightly different:&nbsp; $p_{\rm AA} = 6/19$,&nbsp; $p_{\rm BB} = 5/19$,&nbsp; $p_{\rm AB} = p_{\rm BA} = 4/19$.}}
{{end}}
+
 
  
 +
{{GraueBox|TEXT= 
 +
$\text{Example 4:}$&nbsp;
 +
The third sequence considered here results from the binary sequence of&nbsp; $\text{Example 3}$&nbsp; by using a simple repeat code:
 +
:$$〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb \text{...} $$
 +
*The repeated symbols are marked by corresponding lower case letters.&nbsp; But it still applies&nbsp; $M=2$.
  
{{Beispiel}}&nbsp; '''[C]'''
+
*Because of the equally probable binary symbols, this also results in&nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
Die dritte hier betrachtete Folge ergibt sich aus  der Folge von Beispiel [B] durch Anwendung eines einfachen Wiederholungscodes (wiederholte Symbole als Kleinbuchstaben): &nbsp; $〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb$ ...
+
 
*Aufgrund der gleichwahrscheinlichen Binärsymbole ergibt sich auch hier  $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
+
*As shown in&nbsp; [[Aufgaben:Exercise_1.3:_Entropy_Approximations|"Exercise 1.3"]]&nbsp; for the compound probabilities we obtain&nbsp; $p_{\rm AA}=p_{\rm BB} = 3/8$&nbsp; and&nbsp; $p_{\rm AB}=p_{\rm BA} = 1/8$.&nbsp; Hence
*Wie in [[Aufgaben:1.3_Entropienäherungen|Aufgabe1.3]] gezeigt wird, gilt nun für die Verbundwahrscheinlichkeiten $p_{\rm AA}=p_{\rm BB} = 3/8$ und $p_{\rm ABA}=p_{\rm BAB} = 1/8$. Daraus folgt:
+
:$$\begin{align*}H_2 ={1}/{2} \cdot \big [ 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm} {8}/{3} +  
:$$\begin{align*}H_2 ={1}/{2} \cdot \left [ 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm} {8}/{3} +  
+
  2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8\big ] = {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 - {3}/{8} \cdot{\rm log}_2\hspace{0.1cm}3 + {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 \approx 0.906 \,{\rm bit/symbol} < H_1 = H_0
  2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8\right ] = {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 - {3}/{8} \cdot{\rm log}_2\hspace{0.1cm}3 +   {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 \approx= 0.906 \,{\rm bit/Symbol} < H_1 = H_0
 
 
  \hspace{0.05cm}.\end{align*}$$
 
  \hspace{0.05cm}.\end{align*}$$
  
Betrachtet man sich die Aufgabenstellung genauer, so kommt man zu folgendem Schluss:  
+
A closer look at the task at hand leads to the following conclusion:  
*Die Entropie müsste eigentlich $H = 0.5 \hspace{0.05cm} \rm bit/Symbol$ sein (jedes zweite Symbol liefert keine neue Information).  
+
*The entropy should actually be&nbsp; $H = 0.5 \hspace{0.05cm} \rm bit/symbol$&nbsp; (every second symbol does not provide new information).
*Die zweite Entropienäherung $H_2 = 0.906 \hspace{0.05cm} \rm bit/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.  
+
*The second entropy approximation&nbsp; $H_2 = 0.906 \hspace{0.05cm} \rm bit/symbol$&nbsp; is much larger than the entropy&nbsp; $H$.
*Einen solchen Block bezeichnen wir im Folgenden als $k$–Tupel.
+
 
{{end}}
+
*For the entropy  determination,  the second order approximation is not sufficient.&nbsp; Rather, one must consider larger contiguous blocks of&nbsp; $k > 2$&nbsp; symbols.
 +
 
 +
*In the following, such a block is referred to as&nbsp; "$k$&ndash;tuple".}}
  
 
 
 
 
==Verallgemeinerung auf ''k''–Tupel und Grenzübergang ==
+
==Generalization to $k$-tuple and boundary crossing ==
 
+
<br>
Zur Abkürzung schreiben wir mit der Verbundwahrscheinlichkeit $p_i^{(k)}$ eines $k$–Tupels allgemein:
+
For abbreviation we write using the compound probability&nbsp; $p_i^{(k)}$&nbsp; for a&nbsp; $k$&ndash;tuple in general:
 
   
 
   
:$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{M^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{p_i^{(k)}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
+
:$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{M^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{p_i^{(k)}} \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Die Laufvariable $i$ steht jeweils für eines der $M^k$ Tupel. Die vorher berechnete Näherung $H_2$ ergibt sich mit $k = 2$.
+
*The control variable&nbsp; $i$&nbsp; stands for one of the&nbsp; $M^k$&nbsp; tuples.&nbsp;
 +
 
 +
*The previously calculated approximation&nbsp; $H_2$&nbsp; results with&nbsp; $k = 2$.
  
{{Definition}}
+
 
Die '''Entropie''' einer Nachrichtenquelle '''mit Gedächtnis''' ist der folgende Grenzwert:  
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp;
 +
The&nbsp; &raquo;'''entropy of a discrete source with memory'''&laquo;&nbsp; has the following limit:  
 
:$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$
 
:$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$
  
Für die ''Entropienäherungen'' $H_k$ gelten folgende Größenrelationen ($H_0$ ist der Entscheidungsgehalt):
+
*For the&nbsp; &raquo;'''entropy approximations'''&laquo;&nbsp; $H_k$&nbsp; the following relations apply&nbsp; $(H_0=\log_2  M)$:
:$$H \le \text{...} \le H_k \le \text{...} \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$${{end}}
+
:$$H \le \text{...} \le H_k \le \text{...} \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$}}
 +
 
 +
 
 +
The computational effort will increase with increasing&nbsp; $k$&nbsp; except for a few special cases (see the following example) and depends on the symbol set size&nbsp; $M$&nbsp; of course:
 +
*For the calculation of&nbsp; $H_{10}$&nbsp; for a binary source&nbsp; $(M = 2)$&nbsp; one must average over&nbsp; $2^{10} = 1024$&nbsp; terms.
 +
 
 +
*With each further increase of&nbsp; $k$&nbsp; by&nbsp; $1$&nbsp; the number of sum terms doubles.
 +
 
 +
*In case of a quaternary source&nbsp; $(M = 4)$&nbsp; it must already be averaged over&nbsp; $4^{10} = 1\hspace{0.08cm}048\hspace{0.08cm}576$&nbsp; summation terms for the determination of&nbsp; $H_{10}$.
 +
 
 +
* Considering that each of these&nbsp; $4^{10} =2^{20} >10^6$&nbsp; $k$&ndash;tuple should occur in simulation/time averaging about&nbsp; $100$&nbsp; times (statistical guideline) to ensure sufficient simulation accuracy, it follows that the sequence length should be in this case greater than&nbsp; $N = 10^8$.
  
  
Der Rechenaufwand wird bis auf wenige Sonderfälle (siehe nachfolgendes Beispiel) mit zunehmendem $k$ immer größer und hängt natürlich auch vom Symbolumfang $M$ ab:
+
{{GraueBox|TEXT= 
*Zur Berechnung von $H_{10}$ einer Binärquelle $(M = 2)$ ist über $2^{10} = 1024$ Terme zu mitteln. Mit jeder weiteren Erhöhung von $k$ um $1$ verdoppelt sich die Anzahl der Summenterme.
+
$\text{Example 5:}$&nbsp;
*Bei einer Quaternärquelle $(M = 42)$ muss zur $H_{10}$–Bestimmung bereits über $4^{10} = 1\hspace{0.05cm}048\hspace{0.05cm}.576$ Summenterme gemittelt werden.
+
We consider an alternating binary sequence &nbsp; ⇒ &nbsp; $〈 q_ν 〉 =\rm ABABABAB$ ... &nbsp;.&nbsp; Accordingly it holds that&nbsp; $H_0 = H_1 = 1 \hspace{0.1cm} \rm bit/symbol$.  
*Berücksichtigt man, dass jedes dieser $4^{10} =2^{20} >10^6$ $k$–Tupel bei Simulation/Zeitmittelung etwa $100$ mal (statistischer Richtwert) vorkommen sollte, um ausreichende Simulationsgenauigkeit zu gewährleisten, so folgt daraus, dass die Folgenlänge größer als $N = 10^8$ sein sollte.
 
  
 +
In this special case, the&nbsp; $H_k$ approximation must be determined independently from&nbsp; $k$&nbsp; by averaging only two compound probabilities:
 +
* $k = 2$: &nbsp;&nbsp; $p_{\rm AB} = p_{\rm BA} = 1/2$ &nbsp; &nbsp; ⇒ &nbsp; &nbsp; $H_2 = 1/2 \hspace{0.2cm} \rm bit/symbol$,
  
{{Beispiel}}
+
* $k = 3$: &nbsp;&nbsp; $p_{\rm ABA} = p_{\rm BAB} = 1/2$ &nbsp; &nbsp; ⇒ &nbsp; &nbsp; $H_3 = 1/3 \hspace{0.2cm} \rm bit/symbol$,
Wir betrachten eine alternierende Binärfolge  ⇒  $〈 q_ν 〉 =\rm ABABABAB$ ... entsprechend $H_0 = H_1 = 1 \hspace{0.05cm} \rm bit/Symbol$. In diesem Sonderfall muss zur Bestimmung der $H_k$–Näherung unabhängig von $k$ stets nur über zwei Verbundwahrscheinlichkeiten gemittelt werden:
 
* $k = 2$: &nbsp;&nbsp;   $p_{\rm AB} = p_{\rm BA} = 1/2$           ⇒  $H_2 =  1/2 \hspace{0.05cm} \rm bit/Symbol$,
 
* $k = 3$:  &nbsp;&nbsp;   $p_{\rm ABA} = p_{\rm BAB} = 1/2$      $H_3 =  1/3 \hspace{0.05cm} \rm bit/Symbol$,
 
* $k = 4$:  &nbsp;&nbsp; $p_{\rm ABAB} = p_{\rm BABA} = 1/2$  ⇒  $H_4 =  1/4 \hspace{0.05cm} \rm bit/Symbol$.
 
  
 +
* $k = 4$:  &nbsp;&nbsp; $p_{\rm ABAB} = p_{\rm BABA} = 1/2$ &nbsp; &nbsp; ⇒ &nbsp; &nbsp; $H_4 = 1/4 \hspace{0.2cm} \rm bit/symbol$.
  
Die Entropie dieser alternierenden Binärfolge ist demzufolge
 
$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$
 
  
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:  
+
The entropy of this alternating binary sequence is therefore
*„Tritt '''A''' zu den geraden oder ungeraden Zeitpunkten auf?”
+
:$$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$$
*Man erkennt aber auch, dass $H_k$ diesem Endwert $H = 0$ nur sehr langsam näher kommt: Die zwanzigste Entropienäherung  liefert immer noch $H_{20} = 0.05 \hspace{0.05cm} \rm bit/Symbol$.
 
{{end}}
 
  
 +
The result was to be expected, since the considered sequence has only minimal information, which does not affect the entropy end value&nbsp; $H$,&nbsp; namely: <br> &nbsp; &nbsp; "Does&nbsp; $\rm A$&nbsp; occur at the even or the odd times?"
  
{{Box}}'''Zusammenfassung''' der Ergebnisse der letzten Seiten:
+
You can see that&nbsp; $H_k$&nbsp; comes closer to this final value&nbsp; $H = 0$&nbsp; very slowly:&nbsp; The twentieth entropy approximation still returns&nbsp; $H_{20} = 0.05 \hspace{0.05cm} \rm bit/symbol$. }}
  
*Allgemein gilt für die Entropie einer Nachrichtenquelle:
+
 
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Summary of the results of the last sections:}$&nbsp;
 +
 
 +
*Generally it applies to the&nbsp; &raquo;'''entropy of a message source'''&laquo;:
 
:$$H \le \text{...} \le H_3 \le H_2 \le H_1 \le H_0  
 
:$$H \le \text{...} \le H_3 \le H_2 \le H_1 \le H_0  
 
  \hspace{0.05cm}.$$  
 
  \hspace{0.05cm}.$$  
*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 die ''relative Redundanz'' ):
+
*A&nbsp; &raquo;'''redundancy-free source'''&laquo; &nbsp; exists if all&nbsp; $M$&nbsp; symbols are equally probable and there are no statistical bindings within the sequence. <br> For these hold&nbsp; $(r$&nbsp; denotes the ''relative redundancy'' $)$:
 
:$$H = H_0 = H_1 = H_2 = H_3 = \text{...}\hspace{0.5cm}
 
:$$H = H_0 = H_1 = H_2 = H_3 = \text{...}\hspace{0.5cm}
 
\Rightarrow \hspace{0.5cm} r = \frac{H - H_0}{H_0}= 0 \hspace{0.05cm}.$$  
 
\Rightarrow \hspace{0.5cm} r = \frac{H - H_0}{H_0}= 0 \hspace{0.05cm}.$$  
*Eine '''gedächtnislose Quelle''' kann durchaus redundant sein $(r> 0)$. Diese Redundanz geht dann allerdings allein auf die Abweichung der Symbolwahrscheinlichkeiten von der Gleichverteilung zurück. Hier gelten folgende Relationen:
+
*A&nbsp; &raquo;'''memoryless source'''&laquo; &nbsp; can be quite redundant&nbsp; $(r> 0)$.&nbsp; This redundancy then is solely due to the deviation of the symbol probabilities from the uniform distribution.&nbsp; Here the following relations are valid:
:$$H = H_1 = H_2 = H_3 = ... \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm}0 \le r = \frac{H_1 - H_0}{H_0}< 1 \hspace{0.05cm}.$$  
+
:$$H = H_1 = H_2 = H_3 = \text{...} \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm}0 \le r = \frac{H_1 - H_0}{H_0}< 1 \hspace{0.05cm}.$$  
*Die entsprechende Bedingung für eine '''gedächtnisbehaftete Quelle''' lautet:
+
*The corresponding condition for a&nbsp; &raquo;'''source with memory'''&laquo;&nbsp; is
:$$ H < ... < H_3 < H_2 < H_1 \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm} 0 < r = \frac{H_1 - H_0}{H_0}\le1 \hspace{0.05cm}.$$
+
:$$ H <\text{...} < H_3 < H_2 < H_1 \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm} 0 < r = \frac{H_1 - H_0}{H_0}\le1 \hspace{0.05cm}.$$
*Ist $H_2 < H_1$, dann gilt (nach Meinung des Autors) auch $H_3 < H_2$, $H_4 < H_3$, ... , also es ist das „≤”–Zeichen in der allgemeinen Gleichung durch das „<”–Zeichen zu ersetzen. Sind die Symbole gleichwahrscheinlich, so gilt wieder $H_1 = H_0$, bei nicht gleichwahrscheinlichen Symbolen $H_1 < H_0$.
+
*If&nbsp; $H_2 < H_1$, then&nbsp; $H_3 < H_2$, &nbsp; $H_4 < H_3$, etc. &nbsp; &rArr; &nbsp; In the general equation, the&nbsp; "≤" character must be replaced by the&nbsp; "<" character.  
{{end}}
+
 
 +
*If the symbols are equally probable, then again&nbsp; $H_1 = H_0$,&nbsp; while&nbsp; $H_1 < H_0$&nbsp; applies to symbols which are not equally probable.}}
 
 
 
 
  
==Die Entropie des AMI–Codes  ==
+
==The entropy of the AMI code ==
 +
<br>
 +
In chapter&nbsp; [[Digital_Signal_Transmission/Symbolwise_Coding_with_Pseudo-Ternary_Codes#Properties_of_the_AMI_code|"Symbol-wise Coding with Pseudo-Ternary Codes"]]&nbsp; of the book&nbsp; "Digital Signal Transmission", among other things, the AMI pseudo-ternary code is discussed.
 +
[[File:EN_Inf_T_1_2_S4.png|right|frame|Signals and symbol sequences for AMI code]]
 +
 +
*This converts the binary sequence&nbsp; $〈 q_ν 〉$&nbsp; with&nbsp; $q_ν ∈ \{ \rm L, \ H \}$&nbsp; into the ternary sequence&nbsp; $〈 c_ν 〉$&nbsp; with&nbsp; $q_ν ∈ \{ \rm M, \ N, \ P \}$.
 +
 
 +
*The names of the source symbols stand for&nbsp; $\rm L$(ow)&nbsp; and&nbsp; $\rm H$(igh)&nbsp; and those of the code symbols for&nbsp; $\rm M$(inus),&nbsp; $\rm P$(lus),&nbsp; and&nbsp; $\rm N$(ull) &nbsp; &rArr; &nbsp; "Zero".
  
Im Kapitel [[Digitalsignalübertragung/Symbolweise_Codierung_mit_Pseudoternärcodes#Eigenschaften_des_AMI-Codes|Symbolweise Codierung mit Pseudoternärcodes]] des Buches „Digitalsignalübertragung” wird unter Anderem der AMI–Pseudoternärcode behandelt.
 
*Dieser wandelt die Binärfolge $〈 q_ν 〉$ mit $q_ν ∈ \{ \rm L, H \}$ in die Ternärfolge $〈 c_ν 〉$ mit $q_ν ∈ \{ \rm M, N, P \}$.
 
*Die Bezeichnungen der Quellensymbole stehen für „Low” und „High” und die der Codesymbole für „Minus”, „Null” und „Plus”.
 
  
 +
The coding rule of the AMI code ("Alternate Mark Inversion") is:
  
Die Codierregel des AMI–Codes (diese Kurzform steht für „Alternate Mark Inversion”) lautet:
+
*Each binary symbol&nbsp; $q_ν =\rm L$&nbsp; is represented by the code symbol&nbsp; $c_ν =\rm N$&nbsp;.
*Jedes Binärsymbol $q_ν =\rm L$ wird durch das Codesymbol $c_ν =\rm N$ dargestellt.
 
*Dagegen wird $q_ν =\rm H$ abwechselnd mit $c_ν =\rm P$ und $c_ν =\rm M$ codiert  ⇒  Name „AMI”.
 
  
:[[File:P_ID2240__Inf_T_1_2_S4_neu.png|frame|Signale und Symbolfolgen beim AMI–Code]]
+
*In contrast,&nbsp; $q_ν =\rm H$&nbsp; alternates with&nbsp; $c_ν =\rm P$&nbsp; and&nbsp; $c_ν =\rm M$&nbsp; coded &nbsp; ⇒ &nbsp; name "Alternate Mark Inversion".
  
Durch die Codierung wird Redundanz hinzugefügt mit dem Ziel, dass die Codefolge keinen Gleichanteil beinhaltet. Wir betrachten hier jedoch nicht die spektralen Eigenschaften des AMI–Codes, sondern interpretieren diesen Code informationstheoretisch:
+
*This special encoding adds redundancy with the sole purpose of ensuring that the encoded sequence does not contain a DC component.
*Aufgrund der Stufenzahl $M = 3$ ist der Entscheidungsgehalt der (ternären) Codefolge gleich $H_0 = \log_2 \ 3 ≈ 1.585 \hspace{0.05cm} \rm bit/Symbol$. Die erste Entropienäherung liefert $H_1 = 1.5 \hspace{0.05cm} \rm bit/Symbol$, wie nachfolgende Rechnung zeigt:
+
<br clear=all>
 +
However, we do not consider the spectral properties of the AMI code here, but interpret this code information-theoretically:
 +
*Based on the symbol set size&nbsp; $M = 3$&nbsp; the decision content of the (ternary) encoded sequence is equal to&nbsp; $H_0 = \log_2 \ 3 ≈ 1.585 \hspace{0.05cm} \rm bit/symbol$.&nbsp; The first entropy approximation returns&nbsp; $H_1 = 1.5 \hspace{0.05cm} \rm bit/symbol$, as shown in the following calculation:
 
    
 
    
 
:$$p_{\rm H} = p_{\rm L} = 1/2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 
:$$p_{\rm H} = p_{\rm L} = 1/2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 
p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P}= p_{\rm H}/2 = 1/4\hspace{0.3cm}
 
p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P}= p_{\rm H}/2 = 1/4\hspace{0.3cm}
\Rightarrow \hspace{0.3cm} H_1 = 1/2 \cdot {\rm log}_2\hspace{0.1cm}2 + 2 \cdot 1/4 \cdot{\rm log}_2\hspace{0.1cm}4 = 1.5 \,{\rm bit/Symbol}
+
\Rightarrow \hspace{0.3cm} H_1 = 1/2 \cdot {\rm log}_2\hspace{0.1cm}2 + 2 \cdot 1/4 \cdot{\rm log}_2\hspace{0.1cm}4 = 1.5 \,{\rm bit/symbol}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
*Betrachten wir nun Zweiertupel. Beim AMI–Code kann $\rm P$ nicht auf $\rm P$ und $\rm M$ nicht auf $\rm M$ folgen. Die Wahrscheinlichkeit für $\rm NN$ ist gleich $p_{\rm L} · p_{\rm L} = 1/4$. Alle anderen (sechs) Zweiertupel treten mit der Wahrscheinlichkeit $1/8$ auf. Daraus folgt für die zweite Entropienäherung:
+
*Let's now look at two-tuples.&nbsp; With the AMI code,&nbsp; $\rm P$&nbsp; cannot follow&nbsp; $\rm P$&nbsp; and&nbsp; $\rm M$&nbsp; cannot follow&nbsp; $\rm M$.&nbsp; The probability for&nbsp; $\rm NN$&nbsp; is equal to&nbsp; $p_{\rm L} \cdot p_{\rm L} = 1/4$.&nbsp; All other (six) two-tuples occur with the probability&nbsp; $1/8$.&nbsp; From this follows for the second entropy approximation:
:$$H_2 = 1/2 \cdot [ 1/4 \cdot {\rm ld}\hspace{0.1cm}4 + 6 \cdot 1/8 \cdot {\rm ld}\hspace{0.1cm}8 ] = 1.375 \,{\rm bit/Symbol}
+
:$$H_2 = 1/2 \cdot \big [ 1/4 \cdot {\rm log_2}\hspace{0.1cm}4 + 6 \cdot 1/8 \cdot {\rm log_2}\hspace{0.1cm}8 \big ] = 1,375 \,{\rm bit/symbol} \hspace{0.05cm}.$$
\hspace{0.05cm}.$$
+
 
 +
*For the further entropy approximations&nbsp; $H_3$,&nbsp; $H_4$, ...&nbsp; and the actual entropy&nbsp; $H$&nbsp; will apply:
 +
:$$ H < \hspace{0.05cm}\text{...}\hspace{0.05cm} < H_5 < H_4 < H_3 < H_2 = 1.375 \,{\rm bit/symbol} \hspace{0.05cm}.$$
  
*Für die weiteren Entropienäherungen $H_3$, $H_43$, ...und die tatsächliche Entropie $H$ wird gelten:
+
*Exceptionally in this example we know the actual entropy&nbsp; $H$&nbsp; of the encoded sequence&nbsp; $〈 c_ν 〉$: &nbsp; Since no new information is added by the coder and no information is lost, it is the same entropy&nbsp; $H = 1 \,{\rm bit/symbol} $&nbsp; as the one of the redundancy-free binary sequence $〈 q_ν 〉$.
:$$ H < ... < H_5 < H_4 < H_3 < H_2  = 1.375 \,{\rm bit/Symbol} \hspace{0.05cm}.$$
 
  
*Bei diesem Beispiel kennt man die tatsächliche Entropie $H$ der Codesymbolfolge $〈 c_ν 〉$. Da durch den Coder keine neue Information hinzukommt, aber auch keine verloren geht, ergibt sich die gleiche Entropie $H  = 1 \,{\rm bit/Symbol} $ wie für die redundanzfreie Binärfolge $〈 q_ν 〉$:
 
  
 +
The&nbsp; [[Aufgaben:Exercise_1.4:_Entropy_Approximations_for_the_AMI_Code|"Exercise 1.4"]]&nbsp; shows the considerable effort required to calculate the entropy approximation&nbsp; $H_3$. &nbsp; Moreover,&nbsp; $H_3$&nbsp; still deviates significantly from the final value&nbsp; $H = 1 \,{\rm bit/symbol} $.&nbsp; A faster result is achieved if the AMI code is described by a Markov chain as explained in the next section.
  
Die [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]] zeigt den bereits beträchtlichen Aufwand zur Berechnung der Entropienäherung $H_3$; zudem weicht $H_3$ noch deutlich vom Endwert $H  = 1 \,{\rm bit/Symbol} $ ab. Schneller kommt man zum Ergebnis, wenn man den AMI–Code durch eine Markovkette entsprechend dem nächsten Abschnitt beschreibt.
 
  
 +
==Binary sources with Markov properties ==
 +
<br>
 +
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markov processes with&nbsp; $M = 2$&nbsp; states]]
  
==Binärquellen mit Markoveigenschaften  ==
+
Sequences with statistical bindings between the sequence elements (symbols) are often modeled by&nbsp; [[Theory_of_Stochastic_Signals/Markov_Chains|$\text{Markov processes}$]]&nbsp; where we limit ourselves here to first-order Markov processes.&nbsp; First we consider a binary Markov process&nbsp; $(M = 2)$&nbsp; with the states (symbols)&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$.
  
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit ''M'' = 2 Zuständen]]
+
On the right, you can see the transition diagram for a first-order binary Markov process&nbsp; however, only two of the four transfer probabilities given are freely selectable, for example
 +
* $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$ &nbsp; ⇒ &nbsp; conditional probability that&nbsp; $\rm A$&nbsp; follows&nbsp; $\rm B$&nbsp;.
  
Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch [[Stochastische_Signaltheorie/Markovketten|Markovprozesse]] modelliert, wobei wir uns hier auf Markovprozesse erster Ordnung beschränken. Zunächst betrachten wir einen binären Markovprozess ($(M = 2)$ mit den Zuständen (Symbolen) $\rm A$ und $\rm B$.
+
* $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = \rm Pr(B\hspace{0.01cm}|\hspace{0.01cm}A)$  &nbsp; &nbsp; conditional probability that&nbsp; $\rm B$&nbsp; follows&nbsp; $\rm A$&nbsp;.
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
 
* $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$  ⇒  bedingte Wahrscheinlichkeit, dass $\rm A$ auf $\rm B$ folgt.
 
* $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = \rm Pr(B\hspace{0.01cm}|\hspace{0.01cm}A)$  ⇒   bedingte Wahrscheinlichkeit, dass $\rm A$ auf $\rm A$ folgt.
 
  
  
Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}
+
For the other two transition probabilities:&nbsp; $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$ &nbsp;and &nbsp; $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
\hspace{0.05cm}, \hspace{0.2cm}p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
 
 
  \hspace{0.05cm}.$
 
  \hspace{0.05cm}.$
  
Aufgrund der vorausgesetzten Eigenschaften [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Station.C3.A4re_Zufallsprozesse|Stationarität]] und [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Ergodische_Zufallsprozesse|Ergodizität]] gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:
+
Due to the presupposed properties&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Stationary_random_processes|$\text{Stationarity}$]]&nbsp; and&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Ergodic_random_processes|$\text{Ergodicity}$]]&nbsp; the following applies to the state or symbol probabilities:
 
   
 
   
 
:$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 
:$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
  \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
+
  \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:
+
These equations allow first information&ndash;theoretical statements about the Markov processes:
* Für $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$ sind die Symbole gleichwahrscheinlich &nbsp; ⇒ &nbsp; $p_{\text{A}} = p_{\text{B}}= 0.5$. Die erste Entropienäherung liefert $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten $p_{\text{A|B}}$ bzw. $p_{\text{B|A}}$.
+
* For&nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$&nbsp; the symbols are equally likely &nbsp; ⇒ &nbsp; $p_{\text{A}} = p_{\text{B}}= 0.5$.&nbsp; The first entropy approximation returns&nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$, independent of the actual values of the (conditional) transition probabilities&nbsp; $p_{\text{A|B}}$&nbsp; and&nbsp; $p_{\text{B|A}}$.
*Die Quellenentropie $H$ als der Grenzwert der [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Verallgemeinerung_auf_k.E2.80.93Tupel_und_Grenz.C3.BCbergang|Entropienäherung $k$–ter Ordnung]] $H_k$ für $k \to \infty$  hängt aber sehr wohl von den tatsächlichen Werten von $p_{\text{A|B}}$ und $p_{\text{B|A}}$ ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.
+
 
 +
*But the source entropy&nbsp; $H$&nbsp; as the limit value&nbsp; $($for&nbsp; $k \to \infty)$&nbsp; of the&nbsp; [[Information_Theory/Discrete_Sources_with_Memory#Generalization_to_.7F.27.22.60UNIQ-MathJax111-QINU.60.22.27.7F-tuple_and_boundary_crossing|"Entropy approximation of order&nbsp; $k$"]] &nbsp; &rArr; &nbsp; $H_k$&nbsp; depends very much on the actual values of&nbsp; $p_{\text{A|B}}$ &nbsp;and&nbsp; $p_{\text{B|A}}$&nbsp; and not only on their quotients.&nbsp; This is shown by the following example.
  
  
{{Beispiel}}
+
{{GraueBox|TEXT= 
Wir betrachten drei binäre symmetrische Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$ unterscheiden. Für die  Symbolwahrscheinlichkeiten gilt somit: $p_{\rm A} = p_{\rm B}= 0.5$ und die  anderen Übergangswahrscheinlichkeiten haben dann die Werte: $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}A}} = 1 - p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} =
+
$\text{Example 6:}$&nbsp;
p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}B}}.$
+
We consider three binary symmetric Markov sources that are represented by the numerical values of the symmetric transition probabilities&nbsp; $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$.&nbsp; For the symbol probabilities the following applies:&nbsp; $p_{\rm A} = p_{\rm B}= 0.5$, and the other transition probabilities have the values
  
[[File:P_ID2242__Inf_T_1_2_S5b_neu.png|frame|Drei Beispiele binärer Markovquellen]]
+
[[File:EN_Inf_T_1_2_S5b.png|right|frame|Three examples of binary Markov sources with&nbsp; $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$&nbsp;]]  
 +
:$$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =
 +
p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}B} }.$$
  
*Die mittlere (blaue) Symbolfolge mit $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = 0.5$ besitzt die Entropie $H ≈ 1 \hspace{0.05cm}  \rm bit/Symbol$. Das heißt: In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge.
+
*The middle (blue) sequence with&nbsp; $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.5$&nbsp; has the entropy&nbsp; $H ≈ 1 \hspace{0.1cm}  \rm bit/symbol$.&nbsp; That means: &nbsp; In this special case there are no statistical bindings within the sequence.
*Die linke (rote) Folge mit $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = 0.25$ weist weniger Wechsel zwischen $\rm A$ und $\rm B$ auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun  $H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$ kleiner.
 
*Die rechte (grüne) Symbolfolge mit $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = 0.8$ hat die genau gleiche Entropie $H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$ wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... $\rm ABABAB$ ... ).
 
  
{{end}}
+
*The left (red) sequence with&nbsp; $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$&nbsp; has less changes between&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$.&nbsp;  Due to statistical dependencies between neighboring symbols the entropy is now smaller:&nbsp; $H ≈ 0.72 \hspace{0.1cm} \rm bit/symbol$.
  
 +
*The right (green) symbol sequence with&nbsp; $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$&nbsp; has the exact same entropy&nbsp; $H ≈ 0.72 \hspace{0.1cm}  \rm bit/symbol$&nbsp; as the red sequence.&nbsp; Here you can see many regions with alternating symbols&nbsp; $($... $\rm ABABAB$ ... $)$.}}
  
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.72 \hspace{0.05cm}  \rm bit/Symbol$ erst nach langwierigen Berechnungen erhalten.
+
This example is worth noting:
*Auf den nächsten Seiten wird gezeigt, dass bei einer Quelle mit Markoveigenschaften dieser Endwert $H$ allein aus den Entropienäherungen $H_1$ und $H_2$ ermittelt werden kann.
+
#If you had not used the Markov properties of the red and green sequences, you would have reached the respective result&nbsp; $H ≈ 0.72 \hspace{0.1cm}  \rm bit/symbol$&nbsp; only after lengthy calculations.
*Ebenso lassen sich aus $H_1$ und $H_2$ alle Entropienäherungen $H_k$ für $k$–Tupel in einfacher Weise berechnen    $H_3$, $H_4$, $H_5$, ... , $H_{100}$, ...
+
#The following sections show that for a source with Markov properties the final value&nbsp; $H$&nbsp; can be determined from the entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; alone. &nbsp; Likewise, all entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; can also be calculated from&nbsp; $H_k$&nbsp; for&nbsp; $k$&ndash;tuples in a simple manner &nbsp; &nbsp; $H_3$,&nbsp; $H_4$,&nbsp; $H_5$, ... &nbsp; $H_{100}$, ...
 
 
 
   
 
   
==Vereinfachte Entropieberechnung bei Markovquellen  ==
+
== Simplified entropy calculation for Markov sources ==
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit ''M'' = 2 Zuständen]]
+
<br>
Wir gehen weiterhin von der symmetrischen binären Markovquelle erster Ordnung aus. Wie auf der vorherigen Seite verwenden wir folgende Nomenklatur für
+
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markov processes with&nbsp; $M = 2$&nbsp; states]]
*die Übergangswahrscheinlichkeiten $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, ...
+
We continue to assume the first-order symmetric binary Markov source.&nbsp; As in the previous section, we use the following nomenclature for
*die ergodischen Wahrscheinlichkeiten $p_{\text{A}}$ und $p_{\text{B}}$,
+
*the transition probabilities &nbsp; &rArr; &nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$,&nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}A}}= 1- p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}B}} = 1 - p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp;
*die Verbundwahrscheinlichkeiten, zum Beispiel $p_{\text{AB}} = p_{\text{A}} · p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.
+
 +
*the ergodic probabilities &nbsp; &rArr; &nbsp; $p_{\text{A}}$&nbsp; and&nbsp; $p_{\text{B}}$,
 +
 
 +
*the compound probabilities, for example &nbsp; &rArr; &nbsp; $p_{\text{AB}} = p_{\text{A}} - p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.
  
  
Wir berechnen nun die [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|Entropie eines Zweiertupels]] (mit der Einheit „bit/Zweiertupel”):
+
We now compute the&nbsp; [[Information_Theory/Discrete_Sources_with_Memory#Entropy_with_respect_to_two-tuples|"Entropy of a two-tuple"]]&nbsp; (with the unit "bit/two-tuple"):
 
   
 
   
:$$H_2' = p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
+
:$$H_2\hspace{0.05cm}' = p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Ersetzt man nun die Logarithmen der Produkte durch entsprechende Summen von Logarithmen, so erhält man das Ergebnis $H_2' = H_1 + H_{\text{M}}$ mit  
+
If one now replaces the logarithms of the products by corresponding sums of logarithms, one gets the result&nbsp; $H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$&nbsp; with  
 
:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
 
:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
 
  \hspace{0.05cm},$$
 
  \hspace{0.05cm},$$
Line 261: Line 312:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):
+
{{BlaueBox|TEXT= 
:$$H_2 = {1}/{2} \cdot {H_2'} = {1}/{2} \cdot [ H_{\rm 1} + H_{\rm M}]  
+
$\text{Conclusion:}$&nbsp; Thus the&nbsp; &raquo;'''second entropy approximation'''&laquo;&nbsp; (with the unit "bit/symbol")&nbsp; is:
  \hspace{0.05cm}.$$
+
:$$H_2 = {1}/{2} \cdot {H_2\hspace{0.05cm}'} = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big]  
 +
  \hspace{0.05cm}.$$}}
 +
 
  
Anzumerken ist:
+
It is to be noted:
*Der erste Summand wurde nicht zufällig mit $H_1$ abgekürzt, sondern ist tatsächlich gleich der ersten Entropienäherung, allein abhängig von den Symbolwahrscheinlichkeiten.
+
#The first summand&nbsp; $H_1$ &nbsp; ⇒ &nbsp; first entropy approximation depends only on the symbol probabilities.
*Bei einem symmetrischen Markovprozess      $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$     $p_{\text{A}} = p_{\text{B}} = 1/2$ &nbsp; ergibt sich für diesen ersten Summanden $H_1 = 1 \hspace{0.05cm} \rm bit/Symbol$.
+
#For a symmetrical Markov process &nbsp; &nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} $ &nbsp; &nbsp; $p_{\text{A}} = p_{\text{B}} = 1/2$ &nbsp; the result for this first summand is&nbsp; $H_1 = 1 \hspace{0.1cm} \rm bit/symbol$.
*Der zweite Summand $H_{\text{M}}$ muss gemäß der zweiten der oberen Gleichungen berechnet werden. Bei einem symmetrischen Markovprozess erhält man $H_{\text{M}} = H_{\text{bin}}(p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}})$.
+
#The second summand&nbsp; $H_{\text{M}}$&nbsp; must be calculated according to the second of the two upper equations.  
 +
#For a symmetrical Markov process you get&nbsp; $H_{\text{M}} = H_{\text{bin}}(p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}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:
+
Now, this result is extended to the&nbsp; $k$&ndash;th entropy approximation.&nbsp; Here, the advantage of Markov sources over other sources is taken advantage of, that the entropy calculation for&nbsp; $k$&ndash;tuples is very simple.&nbsp; For each Markov source, the following applies
 
   
 
   
:$$H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
+
:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
  H_2 = \frac{1}{2} \cdot [ H_{\rm 1} + H_{\rm M}]\hspace{0.05cm}, \hspace{0.3cm}
+
  H_2 = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big ]\hspace{0.05cm}, \hspace{0.3cm}
  H_3 =\frac{1}{3} \cdot [ H_{\rm 1} + 2 \cdot H_{\rm M}] \hspace{0.05cm},\hspace{0.3cm}
+
  H_3 ={1}/{3} \cdot \big [ H_{\rm 1} + 2 \cdot H_{\rm M}\big ] \hspace{0.05cm},\hspace{0.3cm}
  H_4 = \frac{1}{4} \cdot [ H_{\rm 1} + 3 \cdot H_{\rm M}]  
+
  H_4 = {1}/{4} \cdot \big [ H_{\rm 1} + 3 \cdot H_{\rm M}\big ]  
 
  \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}$$
 
  \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}$$
  
Bildet man den Grenzübergang für $k \to \infty$, so erhält man für die tatsächliche Quellenentropie:
+
{{BlaueBox|TEXT= 
:$$H = \lim_{k \rightarrow \infty } H_k = H_{\rm M} \hspace{0.05cm}.$$
+
$\text{Conclusion:}$&nbsp; With the boundary condition for&nbsp; $k \to \infty$, one obtains the actual source entropy
Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:
+
:$$H = \lim_{k \rightarrow \infty} H_k = H_{\rm M} \hspace{0.05cm}.$$
*Bei Markovquellen genügt die Bestimmung der Entropienäherungen $H_1$ und $H_2$. Damit lautet die Entropie einer Markovquelle:
+
From this simple result important insights for the entropy calculation follow:
:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm}.$$
+
*For Markov sources it is sufficient to determine the entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$.&nbsp; Thus, the entropy of a Markov source is
 +
:$$H = 2 \cdot H_2 - H_{\rm 1}  \hspace{0.05cm}.$$
  
*Durch $H_1$ und $H_2$ liegen auch alle weiteren Entropienäherungen $H_k$ für $k \ge 3$ fest:
+
*Through&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; all further entropy approximations&nbsp; $H_k$&nbsp; are also fixed for&nbsp; $k \ge 3$&nbsp;:
 
   
 
   
:$$H_k = \frac{2-k}{k} \cdot H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot H_{\rm 2}
+
:$$H_k = \frac{2-k}{k} \cdot H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot H_{\rm 2}
  \hspace{0.05cm}.$$
+
  \hspace{0.05cm}.$$}}
 +
 
 +
 
 +
However, these approximations are not very important.&nbsp; Mostly only the limit value&nbsp; $H$&nbsp; is of interest.&nbsp; For sources without Markov properties the approximations&nbsp; $H_k$&nbsp; are calculated only to be able to estimate this limit value, i.e. the actual entropy.
 +
 
  
*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 $H_k$ nur deshalb, um den Grenzwert, also die tatsächliche Entropie, abschätzen zu können.
+
<u>Notes</u>:
*Alle auf dieser Seite angegebenen Gleichungen gelten auch für nichtbinäre Markovquellen $(M > 2)$, wie auf der nächsten Seite gezeigt wird.
+
*In the&nbsp; [[Aufgaben:Exercise_1.5:_Binary_Markov_Source|"Exercise 1.5"]]&nbsp; the above equations are applied to the more general case of an asymmetric binary source.
  
 +
*All equations in this section also apply to non-binary Markov sources&nbsp; $(M > 2)$ as shown in the next section.
  
''Hinweis'': In der [[Aufgaben:1.5_Binäre_Markovquelle|Aufgabe 1.5]] werden die obigen Gleichungen auf den allgemeineren Fall einer unsymmetrischen Binärquelle angewendet.
 
  
  
==Nichtbinäre Markovquellen ==
+
==Non-binary Markov sources ==
 +
<br>
 +
[[File:EN_Inf_T_1_2_S6.png|right|frame|Ternary and quaternary first order Markov source]]
  
Für jede Markovquelle gelten unabhängig vom Symbolumfang die folgenden Gleichungen:
+
The following equations apply to each Markov source regardless of the symbol set size&nbsp; $M$:
 
   
 
   
:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm},\hspace{0.3cm} H_k = {1}/{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm},\hspace{0.3cm} \lim_{k \rightarrow \infty } H_k = H  
+
:$$H = 2 \cdot H_2 - H_{\rm 1}  \hspace{0.05cm},$$
 +
:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.05cm},$$
 +
:$$ \lim_{k \rightarrow \infty} H_k = H  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Diese ermöglichen die einfache Berechnung der Entropie $H$ aus den Näherungen $H_1$ und $H_2$.
+
These equations allow the simple calculation of the entropy&nbsp; $H$&nbsp; from the approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$.
  
[[File:P_ID2243__Inf_T_1_2_S6_neu.png|frame|Ternäre und quaternäre Markovquelle erster Ordnung]]
+
We now look at the transition diagrams sketched on the right:
 +
*A ternary Markov source&nbsp; $\rm MQ3$&nbsp; $(M = 3$,&nbsp; blue coloring$)$,&nbsp; and
  
Wir betrachten nun eine ternäre Markovquelle $\rm MQ3$ (Stufenzahl $M = 3$, blaue Farbgebung) und eine quaternäre Markovquelle $\rm MQ4$ ( $M = 4$, rot ) entsprechend den obigen Übergangsdiagrammen.
+
*a quaternary Markov source&nbsp; $\rm MQ4$&nbsp; $(M = 4$,&nbsp; red color$)$.
 +
<br clear=all>
 +
In&nbsp; [[Aufgaben:Exercise_1.6:_Non-Binary_Markov_Sources|"Exercise 1.6"]]&nbsp; the entropy approximations&nbsp; $H_k$&nbsp; and the total entropy&nbsp; $H$&nbsp; are calculated as the limit of&nbsp; $H_k$&nbsp; for&nbsp; $k \to \infty$&nbsp;. &nbsp; The results are shown in the following figure.&nbsp; All entropies specified there have the unit "bit/symbol".
  
In der [[Aufgaben:1.6_Nichtbinäre_Markovquellen|Aufgabe 1.6]] werden die Entropienäherungen $H_k$ und die jeweiligen Quellenentropien $H$ als der Grenzwert von $H_k$ für $k \to \infty$ berechnet. Die Ergebnisse sind in der folgenden Grafik zusammengestellt. Alle Entropien haben die Einheit „bit/Symbol”.
+
[[File:EN_Inf_T_1_2_S6b.png|right|frame|Entropies for&nbsp; $\rm MQ3$,&nbsp; $\rm MQ4$&nbsp; and the&nbsp; $\rm AMI$&nbsp; code]]
  
[[File:P_ID2244__Inf_T_1_2_S6b_neu.png|frame|Entropien für MQ3, MQ4 und AMI–Code]]
+
These results can be interpreted as follows:
 +
*For the ternary markov source&nbsp; $\rm MQ3$&nbsp; the entropy approximations of&nbsp; $H_1 = 1.500$&nbsp; above&nbsp; $H_2 = 1.375$&nbsp; up to the limit&nbsp; $H = 1.250$&nbsp; continuously decreasing.&nbsp; Because of&nbsp; $M = 3$&nbsp; &rArr; &nbsp; $H_0 = 1.585$.
  
Diese Ergebnisse lassen sich wie folgt interpretieren:
+
*For the quaternary Markov source&nbsp; $\rm MQ4$&nbsp; one receives&nbsp; $H_0 = H_1 = 2.000$&nbsp; (since four equally probable states) and&nbsp; $H_2 = 1.5$. &nbsp; From the&nbsp; $H_1$-&nbsp; and&nbsp; $H_2$-values all entropy approximations&nbsp; $H_k$&nbsp; and the final value&nbsp; $H = 1.000$&nbsp; can be calculated.
*Bei der ternären Markovquelle $\rm MQ3$ nehmen die Entropienäherungen von $H_1 = 1.500$ über $H_2 = 1.375$ bis zum Grenzwert $H = 1.250$ kontinuierlich ab. Wegen $M = 3$ beträgt der Entscheidungsgehalt $H_0 = 1.585$.
 
*Für die quaternäre Markovquelle $\rm MQ4$ (rote Markierungen) erhält man $H_0 = H_1 = 2.000$ (wegen den vier gleichwahrscheinlichen Zuständen) und $H_2$ = 1.5. Aus dem $H_1$– und $H_2$–Wert lassen sich auch hier alle Entropienäherungen $H_k$ und auch der Endwert $H = 1.000$ berechnen.
 
*Die beiden Quellenmodelle $\rm MQ3$ und $\rm MQ4$ entstanden bei dem Versuch, den [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Die_Entropie_des_AMI.E2.80.93Codes|AMI–Code]] informationstheoretisch durch Markovquellen zu beschreiben. Die Symbole $\rm M$, $\rm N$ und $\rm PM$ stehen hierbei für „Minus”, „Null” und „Plus”.
 
*Die Entropienäherungen $H_1$, $H_2$ und $H_3$ des AMI–Codes (grüne Markierungen) wurden in [[Aufgaben:1.4_Entropienäherungen_Hk|Aufgabe A1.4]] berechnet. Auf die Berechnung von $H_4$, $H_5$, ... musste aus Aufwandsgründen verzichtet werden. Bekannt ist aber der Endwert von $H_k$ für $k \to \infty$    ⇒    $H = 1.000$.
 
*Man erkennt, dass das Markovmodell $\rm MQ3$ für $H_0 = 1.585$, $H_1 = 1.5$ und $H_2 = 1.375$ genau die gleichen Zahlenwerte liefert wie der AMI–Code. Dagegen unterscheiden sich $H_3$ ($1.333$ gegenüber $1.292$) und insbesondere der Endwert $H$ ($1.250$ gegenüber $1.000$).
 
*Das Modell $\rm MQ4$ ($M = 4$) unterscheidet sich vom AMI–Code ($M = 3$) hinsichtlich des Entscheidungsgehaltes $H_0$ und auch bezüglich aller Entropienäherungen $H_k$. Trotzdem ist $\rm MQ4$ das geeignete Modell für den AMI–Code, da der Endwert $H = 1.000$ übereinstimmt.
 
*Das [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Modell MQ3]] liefert deshalb zu große Entropiewerte, da hier die Folgen '''PNP''' und '''MNM''' möglich sind, die beim AMI–Code nicht auftreten können. Bereits bei $H_3$ macht sich der Unterschied geringfügig bemerkbar, im Endwert $H$ deutlich (1.25 gegenüber 1).
 
  
 +
*The two models&nbsp; $\rm MQ3$&nbsp; and&nbsp; $\rm MQ4$&nbsp; were created during the attempt to calculate the&nbsp; [[Information_Theory/Discrete_Sources_with_Memory#The_entropy_of_the_AMI_code|"AMI code"]]&nbsp; to be described information&ndash;theoretically by Markov sources.&nbsp; The symbols&nbsp; $\rm M$,&nbsp; $\rm N$&nbsp; and&nbsp; $\rm P$&nbsp; stand for&nbsp; "minus",&nbsp; "zero"&nbsp; and&nbsp; "plus".
  
Beim Modell $\rm MQ4$ wurde der Zustand „Null” aufgespalten in zwei Zustände $\rm N$ und $\rm O$ (siehe rechte obere Grafik auf dieser Seite):
+
*The entropy approximations&nbsp; $H_1$,&nbsp; $H_2$&nbsp; and&nbsp; $H_3$&nbsp; of the AMI code (green markers) were calculated in the&nbsp; [[Aufgaben:Aufgabe 1.4: Entropienäherungen für den AMI-Code|"Exercise 1.4"]].&nbsp; On the calculation of&nbsp; $H_4$,&nbsp; $H_5$, ... had to be omitted for reasons of effort.&nbsp; But the final value of&nbsp; $H_k$&nbsp; for&nbsp; $k \to \infty$ &nbsp; ⇒ &nbsp; $H = 1.000$&nbsp; is known.
*Hierbei gilt für den Zustand $\rm N$: Das aktuelle Binärsymbol $\rm L$ wird mit dem Amplitudenwert „0” dargestellt, wie es der AMI–Regel entspricht. Das nächste auftretende $\rm H$–Symbol wird als „-1” (Minus) dargestellt, weil das letzte $\rm H$–Symbol als „+1” (Plus) codiert wurde.
 
*Auch beim Zustand $\rm O$ wird das aktuelle Binärsymbol $\rm L$ mit dem Ternärwert „0” dargestellt. Im Unterschied zum Zustand $\rm N$ wird aber nun das nächste auftretende $\rm H$–Symbol als „+1” (Plus) dargestellt werden, da das letzte $\rm H$–Symbol als „-1” (Minus) codiert wurde.
 
  
 +
*You can see that the Markov model&nbsp; $\rm MQ3$&nbsp; for&nbsp; $H_0 = 1.585$,&nbsp; $H_1 = 1.500$&nbsp; and&nbsp; $H_2 = 1.375$&nbsp; yields exactly the same numerical values as the AMI code. &nbsp; On the other hand&nbsp; $H_3$&nbsp; &rArr; &nbsp; $(1.333$&nbsp; instead of&nbsp; $1.292)$&nbsp; and especially the final value&nbsp; $H$&nbsp; &rArr; &nbsp; $(1.250$&nbsp; compared to&nbsp; $1.000)$.
  
Die von $\rm MQ4$ ausgegebene Symbolfolge entspricht tatsächlich den Regeln des AMI–Codes und weist die Entropie $H = 1.000 \hspace{0.05cm} \rm bit/Symbol$ auf. Aufgrund des neuen Zustandes $\rm O$ ist nun allerdings $H_0 = 2.000 \hspace{0.05cm} \rm bit/Symbol$ (gegenüber $1.585 \hspace{0.05cm} \rm bit/Symbol$) deutlich zu groß und auch alle $H_k$–Näherungen sind größer als beim AMI–Code. Erst für $k \to \infty$ stimmen $\rm MQ4$ und AMI-Code überein: &nbsp; $H = 1.000 \hspace{0.05cm} \rm bit/Symbol$.
+
*The model&nbsp; $\rm MQ4$&nbsp; $(M = 4)$&nbsp; differs from the AMI code&nbsp; $(M = 3)$&nbsp; with respect to the decision content&nbsp; $H_0$&nbsp; and also with respect to all entropy approximations&nbsp; $H_k$. &nbsp; Nevertheless, $\rm MQ4$&nbsp; is the more suitable model for the AMI code, since the final value&nbsp; $H = 1,000$&nbsp; is the same.
 +
 
 +
*The model&nbsp; $\rm MQ3$&nbsp; yields entropy values that are too large, since the sequences&nbsp; $\rm PNP$&nbsp; and&nbsp; $\rm MNM$&nbsp; are possible here, which cannot occur in the AMI code. &nbsp; Already with the approximation&nbsp; $H_3$&nbsp; the difference is slightly noticeable, in the final value&nbsp; $H$&nbsp; even clearly&nbsp; $(1.25$&nbsp; instead of&nbsp; $1)$.
 +
 
 +
 
 +
In the model&nbsp; $\rm MQ4$&nbsp; the state&nbsp; "Zero"&nbsp; was split into two states&nbsp; $\rm N$&nbsp; and&nbsp; $\rm O$&nbsp; (see upper right figure in this section):
 +
*Here applies to the state&nbsp; $\rm N$: &nbsp; The current binary symbol&nbsp; $\rm L$&nbsp; is encoded with the amplitude value&nbsp; $0$&nbsp; (zero), as per the AMI rule.&nbsp; The next occurring&nbsp; $\rm H$ symbol, on the other hand, is displayed as&nbsp; $-1$&nbsp; (minus), because the last symol&nbsp; $\rm H$&nbsp; was encoded as&nbsp; $+1$&nbsp; (plus).
 +
 
 +
*Also with the state&nbsp; $\rm O$&nbsp; the current binary symbol&nbsp; $\rm L$&nbsp; is represented with the ternary value&nbsp; $0$.&nbsp; In contrast to the state&nbsp; $\rm N$&nbsp; however, the next occurring&nbsp; $\rm H$ symbol is now encoded as&nbsp; $+1$&nbsp; (plus) since the last&nbsp; $\rm H$ symbol was encoded as&nbsp; $-1$&nbsp; (minus).
 +
 
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Conclusion:}$&nbsp;
 +
#The&nbsp; $\rm MQ4$ output sequence actually follows the rules of the AMI code and has entropy&nbsp; $H = 1.000 \hspace{0.15cm} \rm bit/symbol$.  
 +
#But because of the new state&nbsp; $\rm O$&nbsp; now&nbsp; $H_0 = 2.000 \hspace{0.15cm} \rm bit/symbol$&nbsp; $($against&nbsp; $1.585 \hspace{0.15cm} \rm bit/symbol)$&nbsp; is clearly too large.
 +
#Also all&nbsp; $H_k$ approximations are larger than with the AMI code.&nbsp; First for &nbsp;$k \to \infty$&nbsp; the model&nbsp; $\rm MQ4$&nbsp; and the AMI code match exactly: &nbsp; $H = 1.000 \hspace{0.15cm} \rm bit/symbol$.}}
  
 
   
 
   
==Aufgaben zum Kapitel==
+
== Exercises for the chapter==
 
+
<br>
[[Aufgaben:1.3 Entropienäherungen|Aufgabe 1.3: &nbsp; Entropienäherungen]]
+
[[Aufgaben:Exercise_1.3:_Entropy_Approximations|Exercise 1.3: Entropy Approximations]]
  
[[Aufgaben:1.4 Entropienäherungen für den AMI-Code|Aufgabe 1.4: &nbsp; Entropienäherungen für den AMI-Code]]
+
[[Aufgaben:Exercise_1.4:_Entropy_Approximations_for_the_AMI_Code|Exercise 1.4: Entropy Approximations for the AMI Code]]
  
[[Aufgaben:1.4Z Entropie der AMI-Codierung|Zusatzaufgabe 1.4Z: &nbsp; Entropie der AMI-Codierung]]
+
[[Aufgaben:Exercise_1.4Z:_Entropy_of_the_AMI_Code|Exercise 1.4Z: Entropy of the AMI Code]]
  
[[Aufgaben:1.5 Binäre Markovquelle|Aufgabe 1.5: &nbsp; Binäre Markovquelle]]
+
[[Aufgaben:Exercise_1.5:_Binary_Markov_Source|Exercise 1.5: Binary Markov Source]]
  
[[Aufgaben:1.5Z Symmetrische Markovquelle|Zusatzaufgabe 1.5Z: &nbsp; Symmetrische Markovquelle]]
+
[[Aufgaben:Exercise_1.5Z:_Symmetrical_Markov_Source|Exercise 1.5Z: Symmetrical Markov Source]]
  
[[Aufgaben:1.6 Nichtbinäre Markovquellen|Aufgabe 1.65: &nbsp; Nichtbinäre Markovquellen]]
+
[[Aufgaben:Exercise_1.6:_Non-Binary_Markov_Sources|Exercise 1.6: Non-Binary Markov Sources]]
  
[[Aufgaben:1.6Z Ternäre Markovquelle|Zusatzaufgabe 1.65Z: &nbsp; Ternäre Markovquelle]]
+
[[Aufgaben:Exercise_1.6Z:_Ternary_Markov_Source|Exercise 1.6Z:Ternary Markov Source]]
  
  
 
{{Display}}
 
{{Display}}

Latest revision as of 16:19, 14 February 2023

A simple introductory example


$\text{Example 1:}$  At the  "beginning of the first chapter"  we have considered a memoryless message source with the symbol set  $\rm \{A, \ B, \ C, \ D\}$   ⇒   $M = 4$  .   An exemplary symbol sequence is shown again in the following figure as source  $\rm Q1$ .

  • With the symbol probabilities  $p_{\rm A} = 0.4 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.3 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.2 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.1\hspace{0.05cm}$  the entropy is
$$H \hspace{-0.05cm}= 0.4 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.4} + 0.3 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.3} + 0.2 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.2} + 0.1 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.1} \approx 1.84 \hspace{0.05cm}{\rm bit/symbol} \hspace{0.01cm}.$$
  • Due to the unequal symbol probabilities the entropy is smaller than  $H_0 = \log_2 M = 2 \hspace{0.05cm} \rm bit/symbol$.
Quaternary source without/with memory



The source  $\rm Q2$  is almost identical to the source  $\rm Q1$, except that each individual symbol is output not only once, but twice in a row:  $\rm A ⇒ AA$,  $\rm B ⇒ BB$,  and so on.

  • It is obvious that  $\rm Q2$  has a smaller entropy (uncertainty) than  $\rm Q1$.
  • Because of the simple repetition code,  the entropy
$$H = 1.84/2 = 0.92 \hspace{0.05cm} \rm bit/symbol$$
has only half the size, although the occurrence probabilities have not changed.


$\text{Conclusion:}$  This example shows:

  1. The entropy of a source with memory is smaller than the entropy of a memoryless source with equal symbol probabilities.
  2. The statistical bindings within the sequence  $〈 q_ν 〉$  have to be considered now,
  3. namely the dependency of the symbol  $q_ν$  from the predecessor symbols  $q_{ν-1}$,  $q_{ν-2}$, ...


Entropy with respect to two-tuples


We continue to look at the source symbol sequence  $〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν-1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} .\hspace{0.05cm}\text{...} \hspace{0.05cm}〉$  and now consider the entropy of two successive source symbols.

  • All source symbols  $q_ν$  are taken from an alphabet with the symbol set size  $M$,  so that for the combination  $(q_ν, \hspace{0.05cm}q_{ν+1})$  there are exactly  $M^2$  possible symbol pairs with the following  "combined probabilities":
$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1}) \hspace{0.05cm}.$$
  • From this, the  »compound entropy«  of two consecutive symbols can be computed:
$$H_2\hspace{0.05cm}' = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} \ \sum_{q_{\nu+1}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm} q_{\mu}\hspace{0.01cm} \}}\hspace{-0.1cm}{\rm Pr}(q_{\nu}\cap q_{\nu+1}) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu}\cap q_{\nu+1})} \hspace{0.4cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/two–tuple}) \hspace{0.05cm}.$$
The index "2" symbolizes that the entropy thus calculated refers to  »two-tuples«.
  • To get the average information content per symbol,  $H_2\hspace{0.05cm}'$  has to be divided in half:
$$H_2 = {H_2\hspace{0.05cm}'}/{2} \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol}) \hspace{0.05cm}.$$
$$H_1 = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu})} \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol}) \hspace{0.05cm}.$$
  • The index "1" is supposed to indicate that  $H_1$  considers only the symbol probabilities and not statistical bindings between symbols within the sequence.  With  $H_0 = \log_2 \ M$  the following size relation results:
$$H_0 \ge H_1 \ge H_2 \hspace{0.05cm}.$$
  • With statistical independence of the sequence elements   ⇒   $H_2 = H_1$.


The previous equations each indicate an  "ensemble mean value".   The probabilities required for the calculation of  $H_1$  and  $H_2$  can, however, also be calculated as time averages from a very long sequence or, more precisely, approximated by the corresponding  "relative frequencies".

Let us now illustrate the calculation of entropy approximations  $H_1$  and  $H_2$  with three examples.

Ternary symbol sequence and formation of two-tuples

$\text{Example 2:}$  We will first look at the sequence  $〈 q_1$, ... , $q_{50} \rangle $  according to the graphic, where the sequence elements  $q_ν$  originate from the alphabet $\rm \{A, \ B, \ C \}$   ⇒   the symbol set size is  $M = 3$.

  • By time averaging over  $50$  symbols one gets the symbol probabilities  $p_{\rm A} ≈ 0.5$,   $p_{\rm B} ≈ 0.3$  and  $p_{\rm C} ≈ 0.2$, with which one can calculate the first order entropy approximation:
$$H_1 = 0.5 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.5} + 0.3 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.3} + 0.2 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.2} \approx \, 1.486 \,{\rm bit/symbol} \hspace{0.05cm}.$$
  • Due to the not equally probable symbols  $H_1 < H_0 = 1.585 \hspace{0.05cm}. \rm bit/symbol$.  As an approximation for the probabilities of two-tuples one gets from the above sequence:
$$\begin{align*}p_{\rm AA} \hspace{-0.1cm}& = \hspace{-0.1cm} 14/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AB} = 8/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AC} = 3/49\hspace{0.05cm}, \\\ p_{\rm BA} \hspace{-0.1cm}& = \hspace{0.07cm} 7/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm BB} = 2/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm BC} = 5/49\hspace{0.05cm}, \\\ p_{\rm CA} \hspace{-0.1cm}& = \hspace{0.07cm} 4/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm CB} = 5/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm CC} = 1/49\hspace{0.05cm}.\end{align*}$$
  • Please note that the  $50$  sequence elements can only be formed from  $49$  two-tuples  $(\rm AA$, ... , $\rm CC)$  which are marked in different colors in the graphic.
  1. The entropy approximation  $H_2$  should actually be equal to  $H_1$  since the given symbol sequence comes from a memoryless source.
  2. Because of the short sequence length  $N = 50$  and the resulting statistical inaccuracy, however, a smaller value results:  
$$H_2 ≈ 1.39\hspace{0.05cm} \rm bit/symbol.$$


$\text{Example 3:}$  Now let us consider a  »memoryless  binary source«  with equally probable symbols, i.e. there would be  $p_{\rm A} = p_{\rm B} = 1/2$.  The first twenty subsequent elements are   $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABABAB$ ...

  • Because of the equally probable binary symbols   $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
  • The compound probability  $p_{\rm AB}$  of the combination  $\rm AB$  is equal to  $p_{\rm A} \cdot p_{\rm B} = 1/4$.  Also $p_{\rm AA} = p_{\rm BB} = p_{\rm BA} = 1/4$.
  • This gives for the second entropy approximation
$$H_2 = {1}/{2} \cdot \big [ {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 + {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 \big ] = 1 \,{\rm bit/symbol} = H_1 = H_0 \hspace{0.05cm}.$$

Note:   Due to the short length of the given sequence the probabilities are slightly different:  $p_{\rm AA} = 6/19$,  $p_{\rm BB} = 5/19$,  $p_{\rm AB} = p_{\rm BA} = 4/19$.


$\text{Example 4:}$  The third sequence considered here results from the binary sequence of  $\text{Example 3}$  by using a simple repeat code:

$$〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb \text{...} $$
  • The repeated symbols are marked by corresponding lower case letters.  But it still applies  $M=2$.
  • Because of the equally probable binary symbols, this also results in  $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
  • As shown in  "Exercise 1.3"  for the compound probabilities we obtain  $p_{\rm AA}=p_{\rm BB} = 3/8$  and  $p_{\rm AB}=p_{\rm BA} = 1/8$.  Hence
$$\begin{align*}H_2 ={1}/{2} \cdot \big [ 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm} {8}/{3} + 2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8\big ] = {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 - {3}/{8} \cdot{\rm log}_2\hspace{0.1cm}3 + {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 \approx 0.906 \,{\rm bit/symbol} < H_1 = H_0 \hspace{0.05cm}.\end{align*}$$

A closer look at the task at hand leads to the following conclusion:

  • The entropy should actually be  $H = 0.5 \hspace{0.05cm} \rm bit/symbol$  (every second symbol does not provide new information).
  • The second entropy approximation  $H_2 = 0.906 \hspace{0.05cm} \rm bit/symbol$  is much larger than the entropy  $H$.
  • For the entropy determination, the second order approximation is not sufficient.  Rather, one must consider larger contiguous blocks of  $k > 2$  symbols.
  • In the following, such a block is referred to as  "$k$–tuple".


Generalization to $k$-tuple and boundary crossing


For abbreviation we write using the compound probability  $p_i^{(k)}$  for a  $k$–tuple in general:

$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{M^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{p_i^{(k)}} \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol}) \hspace{0.05cm}.$$
  • The control variable  $i$  stands for one of the  $M^k$  tuples. 
  • The previously calculated approximation  $H_2$  results with  $k = 2$.


$\text{Definition:}$  The  »entropy of a discrete source with memory«  has the following limit:

$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$
  • For the  »entropy approximations«  $H_k$  the following relations apply  $(H_0=\log_2 M)$:
$$H \le \text{...} \le H_k \le \text{...} \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$


The computational effort will increase with increasing  $k$  except for a few special cases (see the following example) and depends on the symbol set size  $M$  of course:

  • For the calculation of  $H_{10}$  for a binary source  $(M = 2)$  one must average over  $2^{10} = 1024$  terms.
  • With each further increase of  $k$  by  $1$  the number of sum terms doubles.
  • In case of a quaternary source  $(M = 4)$  it must already be averaged over  $4^{10} = 1\hspace{0.08cm}048\hspace{0.08cm}576$  summation terms for the determination of  $H_{10}$.
  • Considering that each of these  $4^{10} =2^{20} >10^6$  $k$–tuple should occur in simulation/time averaging about  $100$  times (statistical guideline) to ensure sufficient simulation accuracy, it follows that the sequence length should be in this case greater than  $N = 10^8$.


$\text{Example 5:}$  We consider an alternating binary sequence   ⇒   $〈 q_ν 〉 =\rm ABABABAB$ ...  .  Accordingly it holds that  $H_0 = H_1 = 1 \hspace{0.1cm} \rm bit/symbol$.

In this special case, the  $H_k$ approximation must be determined independently from  $k$  by averaging only two compound probabilities:

  • $k = 2$:    $p_{\rm AB} = p_{\rm BA} = 1/2$     ⇒     $H_2 = 1/2 \hspace{0.2cm} \rm bit/symbol$,
  • $k = 3$:    $p_{\rm ABA} = p_{\rm BAB} = 1/2$     ⇒     $H_3 = 1/3 \hspace{0.2cm} \rm bit/symbol$,
  • $k = 4$:    $p_{\rm ABAB} = p_{\rm BABA} = 1/2$     ⇒     $H_4 = 1/4 \hspace{0.2cm} \rm bit/symbol$.


The entropy of this alternating binary sequence is therefore

$$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$$

The result was to be expected, since the considered sequence has only minimal information, which does not affect the entropy end value  $H$,  namely:
    "Does  $\rm A$  occur at the even or the odd times?"

You can see that  $H_k$  comes closer to this final value  $H = 0$  very slowly:  The twentieth entropy approximation still returns  $H_{20} = 0.05 \hspace{0.05cm} \rm bit/symbol$.


$\text{Summary of the results of the last sections:}$ 

  • Generally it applies to the  »entropy of a message source«:
$$H \le \text{...} \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$
  • A  »redundancy-free source«   exists if all  $M$  symbols are equally probable and there are no statistical bindings within the sequence.
    For these hold  $(r$  denotes the relative redundancy $)$:
$$H = H_0 = H_1 = H_2 = H_3 = \text{...}\hspace{0.5cm} \Rightarrow \hspace{0.5cm} r = \frac{H - H_0}{H_0}= 0 \hspace{0.05cm}.$$
  • A  »memoryless source«   can be quite redundant  $(r> 0)$.  This redundancy then is solely due to the deviation of the symbol probabilities from the uniform distribution.  Here the following relations are valid:
$$H = H_1 = H_2 = H_3 = \text{...} \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm}0 \le r = \frac{H_1 - H_0}{H_0}< 1 \hspace{0.05cm}.$$
  • The corresponding condition for a  »source with memory«  is
$$ H <\text{...} < H_3 < H_2 < H_1 \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm} 0 < r = \frac{H_1 - H_0}{H_0}\le1 \hspace{0.05cm}.$$
  • If  $H_2 < H_1$, then  $H_3 < H_2$,   $H_4 < H_3$, etc.   ⇒   In the general equation, the  "≤" character must be replaced by the  "<" character.
  • If the symbols are equally probable, then again  $H_1 = H_0$,  while  $H_1 < H_0$  applies to symbols which are not equally probable.


The entropy of the AMI code


In chapter  "Symbol-wise Coding with Pseudo-Ternary Codes"  of the book  "Digital Signal Transmission", among other things, the AMI pseudo-ternary code is discussed.

Signals and symbol sequences for AMI code
  • This converts the binary sequence  $〈 q_ν 〉$  with  $q_ν ∈ \{ \rm L, \ H \}$  into the ternary sequence  $〈 c_ν 〉$  with  $q_ν ∈ \{ \rm M, \ N, \ P \}$.
  • The names of the source symbols stand for  $\rm L$(ow)  and  $\rm H$(igh)  and those of the code symbols for  $\rm M$(inus),  $\rm P$(lus),  and  $\rm N$(ull)   ⇒   "Zero".


The coding rule of the AMI code ("Alternate Mark Inversion") is:

  • Each binary symbol  $q_ν =\rm L$  is represented by the code symbol  $c_ν =\rm N$ .
  • In contrast,  $q_ν =\rm H$  alternates with  $c_ν =\rm P$  and  $c_ν =\rm M$  coded   ⇒   name "Alternate Mark Inversion".
  • This special encoding adds redundancy with the sole purpose of ensuring that the encoded sequence does not contain a DC component.


However, we do not consider the spectral properties of the AMI code here, but interpret this code information-theoretically:

  • Based on the symbol set size  $M = 3$  the decision content of the (ternary) encoded sequence is equal to  $H_0 = \log_2 \ 3 ≈ 1.585 \hspace{0.05cm} \rm bit/symbol$.  The first entropy approximation returns  $H_1 = 1.5 \hspace{0.05cm} \rm bit/symbol$, as shown in the following calculation:
$$p_{\rm H} = p_{\rm L} = 1/2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P}= p_{\rm H}/2 = 1/4\hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_1 = 1/2 \cdot {\rm log}_2\hspace{0.1cm}2 + 2 \cdot 1/4 \cdot{\rm log}_2\hspace{0.1cm}4 = 1.5 \,{\rm bit/symbol} \hspace{0.05cm}.$$
  • Let's now look at two-tuples.  With the AMI code,  $\rm P$  cannot follow  $\rm P$  and  $\rm M$  cannot follow  $\rm M$.  The probability for  $\rm NN$  is equal to  $p_{\rm L} \cdot p_{\rm L} = 1/4$.  All other (six) two-tuples occur with the probability  $1/8$.  From this follows for the second entropy approximation:
$$H_2 = 1/2 \cdot \big [ 1/4 \cdot {\rm log_2}\hspace{0.1cm}4 + 6 \cdot 1/8 \cdot {\rm log_2}\hspace{0.1cm}8 \big ] = 1,375 \,{\rm bit/symbol} \hspace{0.05cm}.$$
  • For the further entropy approximations  $H_3$,  $H_4$, ...  and the actual entropy  $H$  will apply:
$$ H < \hspace{0.05cm}\text{...}\hspace{0.05cm} < H_5 < H_4 < H_3 < H_2 = 1.375 \,{\rm bit/symbol} \hspace{0.05cm}.$$
  • Exceptionally in this example we know the actual entropy  $H$  of the encoded sequence  $〈 c_ν 〉$:   Since no new information is added by the coder and no information is lost, it is the same entropy  $H = 1 \,{\rm bit/symbol} $  as the one of the redundancy-free binary sequence $〈 q_ν 〉$.


The  "Exercise 1.4"  shows the considerable effort required to calculate the entropy approximation  $H_3$.   Moreover,  $H_3$  still deviates significantly from the final value  $H = 1 \,{\rm bit/symbol} $.  A faster result is achieved if the AMI code is described by a Markov chain as explained in the next section.


Binary sources with Markov properties


Markov processes with  $M = 2$  states

Sequences with statistical bindings between the sequence elements (symbols) are often modeled by  $\text{Markov processes}$  where we limit ourselves here to first-order Markov processes.  First we consider a binary Markov process  $(M = 2)$  with the states (symbols)  $\rm A$  and  $\rm B$.

On the right, you can see the transition diagram for a first-order binary Markov process  however, only two of the four transfer probabilities given are freely selectable, for example

  • $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$   ⇒   conditional probability that  $\rm A$  follows  $\rm B$ .
  • $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = \rm Pr(B\hspace{0.01cm}|\hspace{0.01cm}A)$   ⇒   conditional probability that  $\rm B$  follows  $\rm A$ .


For the other two transition probabilities:  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$  and   $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.05cm}.$

Due to the presupposed properties  $\text{Stationarity}$  and  $\text{Ergodicity}$  the following applies to the state or symbol probabilities:

$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}.$$

These equations allow first information–theoretical statements about the Markov processes:

  • For  $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$  the symbols are equally likely   ⇒   $p_{\text{A}} = p_{\text{B}}= 0.5$.  The first entropy approximation returns  $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$, independent of the actual values of the (conditional) transition probabilities  $p_{\text{A|B}}$  and  $p_{\text{B|A}}$.
  • But the source entropy  $H$  as the limit value  $($for  $k \to \infty)$  of the  "Entropy approximation of order  $k$"   ⇒   $H_k$  depends very much on the actual values of  $p_{\text{A|B}}$  and  $p_{\text{B|A}}$  and not only on their quotients.  This is shown by the following example.


$\text{Example 6:}$  We consider three binary symmetric Markov sources that are represented by the numerical values of the symmetric transition probabilities  $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$.  For the symbol probabilities the following applies:  $p_{\rm A} = p_{\rm B}= 0.5$, and the other transition probabilities have the values

Three examples of binary Markov sources with  $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$ 
$$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}B} }.$$
  • The middle (blue) sequence with  $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.5$  has the entropy  $H ≈ 1 \hspace{0.1cm} \rm bit/symbol$.  That means:   In this special case there are no statistical bindings within the sequence.
  • The left (red) sequence with  $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$  has less changes between  $\rm A$  and  $\rm B$.  Due to statistical dependencies between neighboring symbols the entropy is now smaller:  $H ≈ 0.72 \hspace{0.1cm} \rm bit/symbol$.
  • The right (green) symbol sequence with  $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$  has the exact same entropy  $H ≈ 0.72 \hspace{0.1cm} \rm bit/symbol$  as the red sequence.  Here you can see many regions with alternating symbols  $($... $\rm ABABAB$ ... $)$.


This example is worth noting:

  1. If you had not used the Markov properties of the red and green sequences, you would have reached the respective result  $H ≈ 0.72 \hspace{0.1cm} \rm bit/symbol$  only after lengthy calculations.
  2. The following sections show that for a source with Markov properties the final value  $H$  can be determined from the entropy approximations  $H_1$  and  $H_2$  alone.   Likewise, all entropy approximations  $H_1$  and  $H_2$  can also be calculated from  $H_k$  for  $k$–tuples in a simple manner   ⇒   $H_3$,  $H_4$,  $H_5$, ...   $H_{100}$, ...


Simplified entropy calculation for Markov sources


Markov processes with  $M = 2$  states

We continue to assume the first-order symmetric binary Markov source.  As in the previous section, we use the following nomenclature for

  • the transition probabilities   ⇒   $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$,   $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$,  $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}A}}= 1- p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$,   $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}B}} = 1 - p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$,  
  • the ergodic probabilities   ⇒   $p_{\text{A}}$  and  $p_{\text{B}}$,
  • the compound probabilities, for example   ⇒   $p_{\text{AB}} = p_{\text{A}} - p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.


We now compute the  "Entropy of a two-tuple"  (with the unit "bit/two-tuple"):

$$H_2\hspace{0.05cm}' = p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.$$

If one now replaces the logarithms of the products by corresponding sums of logarithms, one gets the result  $H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$  with

$$H_1 = p_{\rm A} \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B} \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = p_{\rm A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B}) \hspace{0.05cm},$$
$$H_{\rm M}= p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.$$

$\text{Conclusion:}$  Thus the  »second entropy approximation«  (with the unit "bit/symbol")  is:

$$H_2 = {1}/{2} \cdot {H_2\hspace{0.05cm}'} = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big] \hspace{0.05cm}.$$


It is to be noted:

  1. The first summand  $H_1$   ⇒   first entropy approximation depends only on the symbol probabilities.
  2. For a symmetrical Markov process   ⇒   $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} $   ⇒   $p_{\text{A}} = p_{\text{B}} = 1/2$   the result for this first summand is  $H_1 = 1 \hspace{0.1cm} \rm bit/symbol$.
  3. The second summand  $H_{\text{M}}$  must be calculated according to the second of the two upper equations.
  4. For a symmetrical Markov process you get  $H_{\text{M}} = H_{\text{bin}}(p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}})$.


Now, this result is extended to the  $k$–th entropy approximation.  Here, the advantage of Markov sources over other sources is taken advantage of, that the entropy calculation for  $k$–tuples is very simple.  For each Markov source, the following applies

$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_2 = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big ]\hspace{0.05cm}, \hspace{0.3cm} H_3 ={1}/{3} \cdot \big [ H_{\rm 1} + 2 \cdot H_{\rm M}\big ] \hspace{0.05cm},\hspace{0.3cm} H_4 = {1}/{4} \cdot \big [ H_{\rm 1} + 3 \cdot H_{\rm M}\big ] \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}$$

$\text{Conclusion:}$  With the boundary condition for  $k \to \infty$, one obtains the actual source entropy

$$H = \lim_{k \rightarrow \infty} H_k = H_{\rm M} \hspace{0.05cm}.$$

From this simple result important insights for the entropy calculation follow:

  • For Markov sources it is sufficient to determine the entropy approximations  $H_1$  and  $H_2$.  Thus, the entropy of a Markov source is
$$H = 2 \cdot H_2 - H_{\rm 1} \hspace{0.05cm}.$$
  • Through  $H_1$  and  $H_2$  all further entropy approximations  $H_k$  are also fixed for  $k \ge 3$ :
$$H_k = \frac{2-k}{k} \cdot H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot H_{\rm 2} \hspace{0.05cm}.$$


However, these approximations are not very important.  Mostly only the limit value  $H$  is of interest.  For sources without Markov properties the approximations  $H_k$  are calculated only to be able to estimate this limit value, i.e. the actual entropy.


Notes:

  • In the  "Exercise 1.5"  the above equations are applied to the more general case of an asymmetric binary source.
  • All equations in this section also apply to non-binary Markov sources  $(M > 2)$ as shown in the next section.


Non-binary Markov sources


Ternary and quaternary first order Markov source

The following equations apply to each Markov source regardless of the symbol set size  $M$:

$$H = 2 \cdot H_2 - H_{\rm 1} \hspace{0.05cm},$$
$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.05cm},$$
$$ \lim_{k \rightarrow \infty} H_k = H \hspace{0.05cm}.$$

These equations allow the simple calculation of the entropy  $H$  from the approximations  $H_1$  and  $H_2$.

We now look at the transition diagrams sketched on the right:

  • A ternary Markov source  $\rm MQ3$  $(M = 3$,  blue coloring$)$,  and
  • a quaternary Markov source  $\rm MQ4$  $(M = 4$,  red color$)$.


In  "Exercise 1.6"  the entropy approximations  $H_k$  and the total entropy  $H$  are calculated as the limit of  $H_k$  for  $k \to \infty$ .   The results are shown in the following figure.  All entropies specified there have the unit "bit/symbol".

Entropies for  $\rm MQ3$,  $\rm MQ4$  and the  $\rm AMI$  code

These results can be interpreted as follows:

  • For the ternary markov source  $\rm MQ3$  the entropy approximations of  $H_1 = 1.500$  above  $H_2 = 1.375$  up to the limit  $H = 1.250$  continuously decreasing.  Because of  $M = 3$  ⇒   $H_0 = 1.585$.
  • For the quaternary Markov source  $\rm MQ4$  one receives  $H_0 = H_1 = 2.000$  (since four equally probable states) and  $H_2 = 1.5$.   From the  $H_1$-  and  $H_2$-values all entropy approximations  $H_k$  and the final value  $H = 1.000$  can be calculated.
  • The two models  $\rm MQ3$  and  $\rm MQ4$  were created during the attempt to calculate the  "AMI code"  to be described information–theoretically by Markov sources.  The symbols  $\rm M$,  $\rm N$  and  $\rm P$  stand for  "minus",  "zero"  and  "plus".
  • The entropy approximations  $H_1$,  $H_2$  and  $H_3$  of the AMI code (green markers) were calculated in the  "Exercise 1.4".  On the calculation of  $H_4$,  $H_5$, ... had to be omitted for reasons of effort.  But the final value of  $H_k$  for  $k \to \infty$   ⇒   $H = 1.000$  is known.
  • You can see that the Markov model  $\rm MQ3$  for  $H_0 = 1.585$,  $H_1 = 1.500$  and  $H_2 = 1.375$  yields exactly the same numerical values as the AMI code.   On the other hand  $H_3$  ⇒   $(1.333$  instead of  $1.292)$  and especially the final value  $H$  ⇒   $(1.250$  compared to  $1.000)$.
  • The model  $\rm MQ4$  $(M = 4)$  differs from the AMI code  $(M = 3)$  with respect to the decision content  $H_0$  and also with respect to all entropy approximations  $H_k$.   Nevertheless, $\rm MQ4$  is the more suitable model for the AMI code, since the final value  $H = 1,000$  is the same.
  • The model  $\rm MQ3$  yields entropy values that are too large, since the sequences  $\rm PNP$  and  $\rm MNM$  are possible here, which cannot occur in the AMI code.   Already with the approximation  $H_3$  the difference is slightly noticeable, in the final value  $H$  even clearly  $(1.25$  instead of  $1)$.


In the model  $\rm MQ4$  the state  "Zero"  was split into two states  $\rm N$  and  $\rm O$  (see upper right figure in this section):

  • Here applies to the state  $\rm N$:   The current binary symbol  $\rm L$  is encoded with the amplitude value  $0$  (zero), as per the AMI rule.  The next occurring  $\rm H$ symbol, on the other hand, is displayed as  $-1$  (minus), because the last symol  $\rm H$  was encoded as  $+1$  (plus).
  • Also with the state  $\rm O$  the current binary symbol  $\rm L$  is represented with the ternary value  $0$.  In contrast to the state  $\rm N$  however, the next occurring  $\rm H$ symbol is now encoded as  $+1$  (plus) since the last  $\rm H$ symbol was encoded as  $-1$  (minus).


$\text{Conclusion:}$ 

  1. The  $\rm MQ4$ output sequence actually follows the rules of the AMI code and has entropy  $H = 1.000 \hspace{0.15cm} \rm bit/symbol$.
  2. But because of the new state  $\rm O$  now  $H_0 = 2.000 \hspace{0.15cm} \rm bit/symbol$  $($against  $1.585 \hspace{0.15cm} \rm bit/symbol)$  is clearly too large.
  3. Also all  $H_k$ approximations are larger than with the AMI code.  First for  $k \to \infty$  the model  $\rm MQ4$  and the AMI code match exactly:   $H = 1.000 \hspace{0.15cm} \rm bit/symbol$.


Exercises for the chapter


Exercise 1.3: Entropy Approximations

Exercise 1.4: Entropy Approximations for the AMI Code

Exercise 1.4Z: Entropy of the AMI Code

Exercise 1.5: Binary Markov Source

Exercise 1.5Z: Symmetrical Markov Source

Exercise 1.6: Non-Binary Markov Sources

Exercise 1.6Z:Ternary Markov Source