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

From LNTwww
 
(83 intermediate revisions by 10 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 { '''A''', '''B''', '''C''', '''D'''} ⇒ $M$ = 4 betrachtet. Eine beispielhafte Symbolfolge ist in der nachfolgenden Grafik als Quelle Q1 nochmals dargestellt. Mit den Symbolwahrscheinlichkeiten $p_A$ = 0.4, $p_B$ = 0.3, $p_C$ = 0.2 und $p_D$ = 0.1 ergibt sich die Entropie zu
+
<br>
 +
{{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
 
   
 
   
−
Aufgrund der ungleichen Auftrittswahrscheinlichkeiten der Symbole ist die Entropie kleiner als der Entscheidungsgehalt $H_0$ = log2 $M$ = 2 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}.$$
 +
 
 +
*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: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 Q2 ist weitgehend identisch mit der Quelle Q1, außer, dass jedes einzelne Symbol nicht nur einmal, sondern zweimal nacheinander ausgegeben wird: '''A''' ⇒ '''AA''', '''B''' ⇒ '''BB''', usw.. Es ist offensichtlich, dass Q2 eine kleinere Entropie (Unsicherheit) aufweist als Q1. Aufgrund des einfachen Wiederholungscodes ist nun $H$ = 1.84/2 = 0.92 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$, $q_2$, ... , $q_{ν–1}$, $q_ν$, $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_ν$, $q_{ν+1}$ ) genau $M^2$ mögliche Symbolpaare mit folgenden 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"]]:
 
   
 
   
−
Daraus ist die ''Verbundentropie'' eines Zweier–Tupels berechenbar:
+
:$${\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&nbsp; &raquo;'''compound entropy'''&laquo;&nbsp; of two consecutive symbols can be computed:
 
   
 
   
−
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:
+
:$$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}.$$
−
Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die in Kapitel 1.1 definierte Entropie mit $H_1$:
 
−
 
−
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$ = log2 $M$ ergibt sich dann folgende Größenbeziehung:
 
−
   
 
−
Bei statistischer Unabhängigkeit der Folgenelemente ist $H_2$ gleich $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 relativen Häufigkeiten annähern.
 
−
Auf den nächsten Seiten werden die Aussagen dieser Seite anhand von Beispielen verdeutlicht.
 
  
−
{{Beispiel}}
+
:The index "2" symbolizes that the entropy thus calculated refers to&nbsp; &raquo;'''two-tuples'''&laquo;.  
−
Wir betrachten die Folge 〈 $q_1$, ... , $q_{50}$ 〉 entsprechend der folgernden Grafik:
 
−
*Die Folgenlänge ist $N$ = 50.
 
−
*Die Folgenelemente $q_ν$ entstammen dem Alphabet {'''A''', '''B''', '''C'''}  ⇒  Symbolumfang $M$ = 3.
 
  
−
Durch Zeitmittelung über die 50 Symbole erhält man die Symbolwahrscheinlichkeiten $p_A$ ≈ 0.5, $p_B$ ≈ 0.3 und $p_C$ ≈ 0.2, womit man die Entropienäherung erster Ordnung berechnen kann:
+
*To get the average information content per symbol,&nbsp; $H_2\hspace{0.05cm}'$&nbsp; has to be divided in half:
 
   
 
   
−
Aufgrund der nicht gleichwahrscheinlichen Symbole ist $H_1$ < $H_0$ = 1.585 bit/Symbol. Als Näherung für die Wahrscheinlichkeiten von Zweiertupeln erhält man aus der obigen Folge:
+
:$$H_2 = {H_2\hspace{0.05cm}'}/{2}  \hspace{0.5cm}({\rm unit\hspace{-0.1cm}: \hspace{0.1cm}bit/symbol})
−
+
\hspace{0.05cm}.$$
−
Beachten Sie, dass aus den 50 Folgenelementen nur 49 Zweiertupel ('''AA''', ... , '''CC''') gebildet werden können, die in der obigen Grafik farblich unterschiedlich markiert sind.
 
−
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: $H_2$ ≈ 1.39 bit/Symbol.
 
  
−
{{end}}
+
*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$:
  
−
Verdeutlichen wir uns die Berechnung der Entropienäherungen $H_1$ und $H_2$ an weiteren Beispielen.
+
:$$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}.$$
  
−
{{Beispiel}}
+
*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:
−
Wir betrachten eine gedächtnislose Binärquelle mit gleichwahrscheinlichen Symbolen, das heißt es gelte $p_A$ = $p_B$ = 1/2.
 
−
*Die ersten zwanzig Folgeelemente lauten:
 
−
〈 $q_ν$ 〉 = '''BBAAABAABBBBBAAAABAB''' ...
 
−
*Aufgrund der gleichwahrscheinlichen Symbole und $M$ = 2 gilt:
 
−
$H_1$ = $H_0$ = 1 bit/Symbol.
 
−
*Die Verbundwahrscheinlichkeit $p_{AB}$ der Kombination '''AB''' ist gleich $p_A · p_B$ = 1/4. Ebenso gilt $p_{AA}$ = $p_{BB}$ = $p_{BA}$ = 1/4. Damit erhält man für die zweite Entropienäherung
 
 
   
 
   
−
''Hinweis'': Aus der oben angegebenen Folge ergeben sich aufgrund der kurzen Länge etwas andere Verbundwahrscheinlichkeiten, nämlich $p_{AA}$ = 6/19, $p_{BB}$ = 5/19 und $p_{AB}$ = $p_{BA}$ = 4/19.
+
:$$H_0 \ge H_1 \ge H_2
 +
\hspace{0.05cm}.$$
  
−
{{end}}
+
*With statistical independence of the sequence elements &nbsp; &rArr; &nbsp; $H_2 = H_1$.
  
  
−
Das nächste Beispiel liefert dagegen das Ergebnis $H_2$ < $H_1$.
+
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"]].
  
 +
Let us now illustrate the calculation of entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; with three examples.
  
−
{{Beispiel}}
+
[[File:Inf_T_1_2_S2_vers2.png|right|frame|Ternary symbol sequence and formation of two-tuples]]
−
Die zweite hier betrachtete Folge ergibt sich aus der oberen Folge durch Anwendung eines einfachen Wiederholungscodes (wiederholte Symbole in Grau):
+
{{GraueBox|TEXT= 
−
〈 $q_ν$ 〉 = '''BBBBAAAAAABBAAAABBBB''' ...
+
$\text{Example 2:}$&nbsp;
−
*Aufgrund der gleichwahrscheinlichen Symbole und $M$ = 2 ergibt sich auch hier:
+
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$.
−
$H_1$ = $H_0$ = 1 bit/Symbol.
+
 
−
*Wie in Aufgabe A1.3 gezeigt wird, gilt aber nun für die Verbundwahrscheinlichkeiten $p_{AA}$ = $p_{BB}$ = 3/8 und $p_{AB}$ = $p_{BA}$ = 1/8. Daraus folgt:
+
*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:
 
   
 
   
−
Wenn man sich die Aufgabenstellung genauer betrachtet, kommt man zu dem Schluss, dass hier die Entropie $H$ = 0.5 bit/Symbol sein müsste (jedes zweite Symbol liefert keine neue Information). Die zweite Entropienäherung $H_2$ = 0.906 bit/Symbol ist aber deutlich größer als die Entropie $H$.
+
:$$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}.$$
  
−
{{end}}
+
*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}, \\\
 +
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&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.
  
−
Dieses Beispiel legt den Schluss nahe, dass zur Entropiebestimmung die Näherung zweiter Ordnung nicht ausreicht. Vielmehr muss man größere zusammenhängende Blöcke mit $k$ > 2 Symbolen betrachten. Einen solchen Block bezeichnen wir im Folgenden als $k$–Tupel.
+
#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.
 +
#Because of the short sequence length&nbsp; $N = 50$&nbsp; and the resulting statistical inaccuracy, however, a smaller value results: &nbsp;
 +
::$$H_2 ≈ 1.39\hspace{0.05cm} \rm bit/symbol.$$}}
  
−
 
−
==Verallgemeinerung auf k–Tupel und Grenzübergang ==
 
  
−
Zur Abkürzung schreiben wir mit der Verbundwahrscheinlichkeit $p_i^{(k)}$ eines $k$–Tupels allgemein:
+
{{GraueBox|TEXT= 
−
+
$\text{Example 3:}$&nbsp;
−
Die Laufvariable $i$ steht jeweils für eines der $M^k$ Tupel. Die Näherung $H_2$ ergibt sich mit $k$ = 2.
+
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$ ...
 +
*Because of the equally probable binary symbols &nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
  
−
{{Definition}}
+
*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$.
−
Die Entropie einer Nachrichtenquelle mit Gedächtnis ist der folgende Grenzwert:
 
 
   
 
   
−
Für die Entropienäherungen Hk gelten folgende Größenrelationen (H0: Entscheidungsgehalt):
+
*This gives for the second entropy approximation
 
   
 
   
−
{{end}}
+
:$$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}.$$
 +
 
 +
<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$.}}
  
  
−
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 4:}$&nbsp;
−
*Bei einer Quaternärquelle ( $M$ = 4 ) muss zur $H_{10}$–Bestimmung bereits über $4^{10}$ = 1.048.576 Summenterme gemittelt werden.
+
The third sequence considered here results from the binary sequence of&nbsp; $\text{Example 3}$&nbsp; by using a simple repeat code:
−
*Berücksichtigt man, dass jedes dieser $4^{10}$ = $2^{20}$ > $10^6$ $k$–Tupel bei Simulation und 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.
+
:$$〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb \text{...} $$
 +
*The repeated symbols are marked by corresponding lower case letters.&nbsp; But it still applies&nbsp; $M=2$.
  
−
{{Beispiel}}
+
*Because of the equally probable binary symbols, this also results in&nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
−
Wir betrachten eine alternierende Binärfolge  ⇒  〈 $q_ν$ 〉 = '''ABABABAB''' ... entsprechend $H_0$ = $H_1$ = 1 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:    $p_{AB}$ =$ p_{BA}$ = 1/2          ⇒  $H_2$ = 1/2 bit/Symbol,
 
−
* $k$ = 3:    $p_{ABA}$ = $p_{BAB}$ = 1/2      ⇒  $H_3$ = 1/3 bit/Symbol,
 
−
* $k$ = 4:    $p_{ABAB}$ =$p_{BABA}$ = 1/2  ⇒  $H_4$ = 1/4 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
 +
:$$\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*}$$
  
−
Die Entropie dieser alternierenden Binärfolge ist demzufolge
+
A closer look at the task at hand leads to the following conclusion:
 +
*The entropy should actually be&nbsp; $H = 0.5 \hspace{0.05cm} \rm bit/symbol$&nbsp; (every second symbol does not provide new information).
 
   
 
   
−
Dieses Ergebnis war zu erwarten, da die betrachtete Folge nur minimale Information besitzt, die sich allerdings im Entropie–Endwert $H$ nicht auswirkt, nämlich: „Tritt '''A''' zu den geraden oder ungeraden Zeitpunkten auf?”
+
*The second entropy approximation&nbsp; $H_2 = 0.906 \hspace{0.05cm} \rm bit/symbol$&nbsp; is much larger than the entropy&nbsp; $H$.
−
Man erkennt aber auch, dass $H_k$ diesem Endwert $H$ = 0 nur sehr langsam näher kommt: Die Näherung $H_{20}$ liefert immer noch 0.05 bit/Symbol.  
 
  
−
{{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".}}
  
−
Die Ergebnisse der letzten Seiten sollen hier kurz zusammengefasst werden:
+
−
*Allgemein gilt für die Entropie einer Nachrichtenquelle:
+
==Generalization to $k$-tuple and boundary crossing ==
 +
<br>
 +
For abbreviation we write using the compound probability&nbsp; $p_i^{(k)}$&nbsp; for a&nbsp; $k$&ndash;tuple in general:
 
   
 
   
−
*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$ nennt man ''relative Redundanz'' ):
+
:$$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}.$$
−
+
 
−
*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:
+
*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$.
−
*Die entsprechende Bedingung für eine gedächtnisbehaftete Quelle lautet:
+
 
−
+
 
−
   
+
{{BlaueBox|TEXT=  
−
*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$.
+
$\text{Definition:}$&nbsp;
−
+
The&nbsp; &raquo;'''entropy of a discrete source with memory'''&laquo;&nbsp; has the following limit:
−
==Die Entropie des AMI–Codes  ==
+
:$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$
 +
 
 +
*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}.$$}}
  
−
Im Buch „Digitalsignalübertragung” – Kapitel 2.4 wurde der AMI–Pseudoternärcode behandelt. Dieser wandelt die Binärfolge 〈 $q_ν$ 〉 mit $q_ν$ ∈ {'''L''', '''H'''} in die Ternärfolge 〈 $c_ν$ 〉 mit $c_ν$ ∈ {'''M''', '''N''', '''P'''}. Die Bezeichnungen der Quellensymbole stehen für „Low” und „High” und die der Codesymbole für „Minus”, „Null” und „Plus”. Die Codierregel des AMI–Codes (diese Kurzform steht für „Alternate Mark Inversion”) lautet:
 
−
*Jedes Binärsymbol $q_ν$ = '''L''' wird durch das Codesymbol $c_ν$ = '''N''' dargestellt.
 
−
*Dagegen wird $q_ν$ = '''H''' abwechselnd mit $c_ν$ = '''P''' und $c_ν$ = '''M''' codiert  ⇒  Name „AMI”.
 
  
 +
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.
  
−
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:
+
*With each further increase of&nbsp; $k$&nbsp; by&nbsp; $1$&nbsp; the number of sum terms doubles.
−
*Aufgrund der Stufenzahl $M$ = 3 ist der Entscheidungsgehalt der (ternären) Codefolge gleich $H_0$ = $\log_2$ 3 ≈ 1.585 bit/Symbol. Die erste Entropienäherung liefert $H_1$ = 1.5 bit/Symbol, wie nachfolgende Rechnung zeigt:
 
−
 
 
−
*Betrachten wir nun Zweiertupel. Beim AMI–Code kann „P” nicht auf „P” und „M” nicht auf „M” folgen. Die Wahrscheinlichkeit für „NN” ist gleich $p_L · p_L$ = 1/4. Alle anderen (sechs) Zweiertupel treten mit der Wahrscheinlichkeit 1/8 auf. Daraus folgt für die zweite Entropienäherung:
 
−
 
−
*Für die weiteren Entropienäherungen und die tatsächliche Entropie $H$ wird gelten:
 
−
 
−
*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 wie für die redundanzfreie Binärfolge 〈 $q_ν$ 〉:
 
−
 
  
−
Aufgabe A1.4 zeigt den bereits beträchtlichen Aufwand zur Berechnung der Entropienäherung $H_3$; zudem weicht $H_3$ noch deutlich vom Endwert $H$ = 1 bit/Symbol ab. Schneller kommt man zum Ergebnis, wenn man den AMI–Code durch eine Markovkette beschreibt.
+
*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$.
  
−
==Binärquellen mit Markoveigenschaften  ==
 
  
−
Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch 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) '''A''' und '''B'''.
+
{{GraueBox|TEXT=
−
Oben 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
+
$\text{Example 5:}$&nbsp;
−
* $p_{\text{A|B}}$ = Pr(A|B)  ⇒  bedingte Wahrscheinlichkeit, dass '''A''' auf '''B''' folgt.
+
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$.  
−
* $p_{\text{B|A}}$ = Pr(B|A)  ⇒  bedingte Wahrscheinlichkeit, dass '''B''' auf '''A''' folgt.
 
  
 +
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$,
  
−
Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann
+
* $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$,
−
 
−
Aufgrund der vorausgesetzten Eigenschaften Stationarität und Ergodizität gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:
 
−
 
−
Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:
 
−
* Für $p_{\text{A|B}$ = $p_{\text{B|A}}$ ergeben sich gleichwahrscheinliche Symbole ⇒ $p_{\text{A}}$ = $p_{\text{B}}$ = 0.5. Damit liefert die erste Entropienäherung $H_1$ = $H_0$ = 1 bit/Symbol, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten $p_{\text{A|B}}$ bzw. $p_{\text{B|A}}$.
 
−
*Die Quellenentropie $H$ als der Grenzwert der Entropienäherung $k$–ter Ordnung $H_k$ für $k$ → ∞ 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.
 
  
 +
* $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$.
  
−
Wir gehen von einer binären Markovquelle erster Ordnung aus und setzen nun voraus:
 
−
*Die 4 bedingten Wahrscheinlichkeiten seien symmetrisch, das heißt, es gelte $p_{\text{A|B}}$ = $p_{\text{B|A}}$, $p_{\text{A|A}}$ = $p_{\text{B|B}}$.
 
−
*Für die beiden Symbolwahrscheinlichkeiten gilt somit:  $p_A$ = $p_B$ = 0.5.
 
  
 +
The entropy of this alternating binary sequence is therefore
 +
:$$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$$
  
−
{{Beispiel}}
+
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?"
−
Wir betrachten hier drei solche binäre Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten $p_{\text{A|B}}$ = $p_{\text{B|A}}$unterscheiden. Die beiden anderen Übergangswahrscheinlichkeiten haben dann folgende Werte: $p_{\text{A|A}}$ = 1 – $p_{\text{B|A}}$ = $p_{\text{B|B}}$.
 
  
−
*Die mittlere Symbolfolge (mit $p_{\text{A|B}}$ = $p_{\text{B|A}}$ = 0.5) besitzt die Entropie $H$ = 1 bit/Symbol. Das heißt: In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge.
+
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$. }}
−
*Die linke (rote) Folge mit $p_{\text{A|B}}$ = $p_{\text{B|A}}$ = 0.2 weist weniger Wechsel zwischen '''A''' und '''B''' auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun $H$ ≈ 0.72 bit/Symbol kleiner.
 
−
*Die rechte (grüne) Symbolfolge mit $p_{\text{A|B}}$ = $p_{\text{B|A}}$ = 0.8 hat die genau gleiche Entropie wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... '''ABABAB''' ... ).
 
  
−
{{end}}
 
  
  
−
Zu diesem Beispiel ist noch anzumerken:
+
{{BlaueBox|TEXT= 
−
*Hätte man nicht die Markoveigenschaften der roten und der grünen Folge ausgenutzt, so hätte man das Ergebnis $H$ ≈ 0.72 bit/Symbol erst nach langwierigen Berechnungen erhalten.
+
$\text{Summary of the results of the last sections:}$&nbsp;
−
*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.
 
−
*Ebenso lassen sich aus H1 und H2 alle Entropienäherungen $H_k$ für $k$–Tupel in einfacher Weise berechnen  ⇒  $H_3$, $H_4$, $H_5$, ... , $H_{100}$, ...
 
−
 
  
−
Wir gehen weiterhin von der symmetrischen binären Markovquelle erster Ordnung aus. Wie auf der vorherigen Seite verwenden wir folgende Nomenklatur:
+
*Generally it applies to the&nbsp; &raquo;'''entropy of a message source'''&laquo;:
−
*Übergangswahrscheinlichkeiten $p_{\text{B|A}}$, ...
+
:$$H \le \text{...} \le H_3 \le H_2 \le H_1 \le H_0
−
*ergodische Wahrscheinlichkeiten $p_(\text{A}}$ und $p_(\text{B}}$,
+
\hspace{0.05cm}.$$  
−
*Verbundwahrscheinlichkeiten, zum Beispiel $p_{\text{AB}}$ = $$p_(\text{A}}$ · $p_{\text{B|A}}$.
+
*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}
 +
\Rightarrow \hspace{0.5cm} r = \frac{H - H_0}{H_0}= 0 \hspace{0.05cm}.$$  
 +
*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 = \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&nbsp; &raquo;'''source with memory'''&laquo;&nbsp; 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&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.  
  
 +
*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.}}
 +
  
−
Wir berechnen nun die Entropie eines Zweiertupels (mit der Einheit „bit/Zweiertupel”):
+
==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]]
 
   
 
   
−
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
+
*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".
 +
 
 +
 
 +
The coding rule of the AMI code ("Alternate Mark Inversion") is:
 +
 
 +
*Each binary symbol&nbsp; $q_ν =\rm L$&nbsp; is represented by the code symbol&nbsp; $c_ν =\rm N$&nbsp;.
 +
 
 +
*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".
 +
 
 +
*This special encoding adds redundancy with the sole purpose of ensuring that the encoded sequence does not contain a DC component.
 +
<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:
 
    
 
    
−
Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):
+
:$$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.&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 \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&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}.$$
 +
 
 +
*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_ν 〉$.
 +
 
 +
 
 +
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.
 +
 
 +
 
 +
==Binary sources with Markov properties ==
 +
<br>
 +
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markov processes with&nbsp; $M = 2$&nbsp; states]]
 +
 
 +
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$.
 +
 
 +
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;.
 +
 
 +
* $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;.
 +
 
 +
 
 +
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}.$
 +
 
 +
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:
 
   
 
   
−
Anzumerken ist:
+
:$$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}}
−
*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.
+
\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}}
−
*Bei einem symmetrischen Markovprozess ( $p_{\text{A|B}}$ = $p_{\text{B|A}}$   ⇒   $p_(\text{A}}$ = $p_(\text{B}}$ = 1/2) ergibt sich für diesen ersten Summanden $H_1$ = 1 bit/Symbol.
+
\hspace{0.05cm}.$$
−
*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_{\text{A|B}})$.
+
 
 +
These equations allow first information&ndash;theoretical statements about the Markov processes:
 +
* 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}}$.
 +
 
 +
*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.
 +
 
 +
 
 +
{{GraueBox|TEXT=
 +
$\text{Example 6:}$&nbsp;
 +
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: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} }.$$
  
 +
*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.
  
−
Im nächsten Abschnitt wird dieses Ergebnis auf die $k$–te Entropienäherung erweitert.
+
*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$ ... $)$.}}
  
−
Der Vorteil von Markovquellen gegenüber anderen Quellen ist, dass sich die Entropieberechnung für $k$–Tupel sehr einfach gestaltet. Für jede Markovquelle gilt:
+
 
 +
This example is worth noting:
 +
#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.
 +
#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}$, ...
 +
 
   
 
   
−
Bildet man den Grenzübergang für $k$ → ∞, so erhält man für die tatsächliche Quellenentropie:
+
== Simplified entropy calculation for Markov sources ==
 +
<br>
 +
[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markov processes with&nbsp; $M = 2$&nbsp; states]]
 +
We continue to assume the first-order symmetric binary Markov source.&nbsp; As in the previous section, we use the following nomenclature for
 +
*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;
 
   
 
   
−
Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:
+
*the ergodic probabilities &nbsp; &rArr; &nbsp; $p_{\text{A}}$&nbsp; and&nbsp; $p_{\text{B}}$,
−
*Bei Markovquellen genügt die Bestimmung der Entropienäherungen $H_1$ und $H_2$. Damit lautet die Entropie einer Markovquelle:
+
 
 +
*the compound probabilities, for example &nbsp; &rArr; &nbsp; $p_{\text{AB}} = p_{\text{A}} - p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.
 +
 
 +
 
 +
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\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&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})
 +
\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}.$$
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Conclusion:}$&nbsp; Thus the&nbsp; &raquo;'''second entropy approximation'''&laquo;&nbsp; (with the unit "bit/symbol")&nbsp; 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:
 +
#The first summand&nbsp; $H_1$ &nbsp; ⇒ &nbsp; first entropy approximation depends only on the symbol probabilities.
 +
#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$.
 +
#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}})$.
 +
 
 +
 
 +
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
 
   
 
   
−
*Durch $H_1$ und $H_2$ liegen auch alle weiteren Entropienäherungen $H_k$ fest:
+
:$$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.}$$
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Conclusion:}$&nbsp; With the boundary condition for&nbsp; $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&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}.$$
 +
 
 +
*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;:
 
   
 
   
−
*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.
+
:$$H_k = \frac{2-k}{k} \cdot H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot H_{\rm 2}
−
*Alle auf dieser Seite angegebenen Gleichungen gelten auch für nichtbinäre Markovquellen ( $M$ > 2 ), wie auf der nächsten Seite gezeigt wird.
+
\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.
 +
 
 +
 
 +
<u>Notes</u>:
 +
*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 Aufgabe A1.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$:
 
   
 
   
−
Diese ermöglichen die einfache Berechnung der Entropie $H$ aus den Näherungen $H_1$ und $H_2$.
+
:$$H = 2 \cdot H_2 - H_{\rm 1}  \hspace{0.05cm},$$
−
Wir betrachten nun eine ternäre Markovquelle MQ3 (Stufenzahl $M$ = 3, blaue Farbgebung) und eine quaternäre Markovquelle MQ4 ( $M$ = 4, rot ) mit folgenden Übergangsdiagrammen:
+
:$$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&nbsp; $H$&nbsp; from the approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$.
 +
 
 +
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
 +
 
 +
*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".
 +
 
 +
[[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]]
  
−
In der Aufgabe A1.6 werden die Entropienäherungen $H_k$ und die jeweiligen Quellenentropien $H$ als der Grenzwert von $H_k$ für $k$ → ∞ berechnet. Die Ergebnisse sind in der folgenden Grafik zusammengestellt. Alle Entropien haben die Einheit „bit/Symbol”.
+
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$.
  
 +
*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.
  
−
Die Ergebnisse lassen sich wie folgt interpretieren:
+
*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".
−
*Bei der ternären Markovquelle MQ3 nehmen die Entropienäherungen von $H_1$ = 1.500 über $H_2$ = 1.375 bis zum Grenzwert $H$ = 1.25 kontinuierlich ab. Wegen $M$ = 3 beträgt der Entscheidungsgehalt $H_0$ = 1.585 (alle Entropien in „bit/Symbol”) .
 
−
*Für die quaternäre Markovquelle MQ4 (rote Markierungen) erhält man $H_0$ = $H_1$ = 2 (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 berechnen.
 
−
*Die beiden Quellenmodelle MQ3 und MQ4 entstanden bei dem Versuch, den AMI–Code informationstheoretisch durch Markovquellen zu beschreiben. Die Symbole '''M''', '''N''' und '''P''' 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 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$ →  ∞    ⇒    $H$ = 1.
 
−
*Man erkennt, dass das Markovmodell MQ3 für $H_0$ = 1.585, $H_1$ = 1.500 und $H_2$ = 1.375 genau die gleichen Werte liefert wie der AMI–Code. Dagegen unterscheiden sich $H_3$ (1.333 gegenüber 1.292) und insbesondere der Endwert $H$ (1.25 gegenüber 1).
 
−
*Das Modell 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 MQ4 das geeignete Modell für den AMI–Code, da der Endwert $H$ = 1 übereinstimmt.
 
−
*Das 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 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.
  
−
Beim Modell MQ4 wurde der Zustand „Null” aufgespalten in zwei Zustände N und O:
+
*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)$.
−
*Hierbei gilt für den Zustand '''N''': Das aktuelle Binärsymbol '''L''' wird mit dem Amplitudenwert „0” dargestellt, wie es der AMI–Regel entspricht. Das nächste auftretende '''H'''–Symbol wird als '''M''' (Minus) dargestellt, weil das letzte '''H'''–Symbol als '''P''' (Plus) codiert wurde.
 
−
*Auch beim Zustand '''O'''' wird das aktuelle Binärsymbol '''L''' mit dem Ternärwert „0” dargestellt. Im Unterschied zum Zustand '''N''' wird aber nun das nächste auftretende '''H'''–Symbol als '''P''' (Plus) dargestellt werden, da das letzte '''H'''–Symbol als '''M''' (Minus) codiert wurde.
 
  
 +
*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.
  
−
Die von MQ4 ausgegebene Symbolfolge entspricht tatsächlich den Regeln des AMI–Codes und weist die Entropie $H$ = 1 bit/Symbol auf. Aufgrund des neuen Zustandes '''O''' ist nun allerdings $H_0$ = 2 bit/Symbol (gegenüber 1.585 bit/Symbol) deutlich zu groß und auch alle $H_k$–Näherungen sind größer als beim AMI–Code. Erst für $k$ → ∞ stimmen beide überein: $H$ = 1 bit/Symbol.
+
*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 zu Kapitel 1.2  ==
+
== Exercises for the chapter==
 +
<br>
 +
[[Aufgaben:Exercise_1.3:_Entropy_Approximations|Exercise 1.3: Entropy Approximations]]
 +
 
 +
[[Aufgaben:Exercise_1.4:_Entropy_Approximations_for_the_AMI_Code|Exercise 1.4: Entropy Approximations for the AMI Code]]
 +
 
 +
[[Aufgaben:Exercise_1.4Z:_Entropy_of_the_AMI_Code|Exercise 1.4Z: Entropy of the AMI Code]]
  
 +
[[Aufgaben:Exercise_1.5:_Binary_Markov_Source|Exercise 1.5: Binary Markov Source]]
  
 +
[[Aufgaben:Exercise_1.5Z:_Symmetrical_Markov_Source|Exercise 1.5Z: Symmetrical Markov Source]]
  
 +
[[Aufgaben:Exercise_1.6:_Non-Binary_Markov_Sources|Exercise 1.6: Non-Binary Markov Sources]]
  
 +
[[Aufgaben:Exercise_1.6Z:_Ternary_Markov_Source|Exercise 1.6Z:Ternary Markov Source]]
  
  
 
{{Display}}
 
{{Display}}

Latest revision as of 17:19, 14 February 2023

  1. Information Theory
  2. Entropy of Discrete Sources
  3. Discrete Sources with Memory

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



Retrieved from "http://en.lntwww.de/index.php?title=Information_Theory/Discrete_Sources_with_Memory&oldid=52706"
  • Powered by MediaWiki