Information Theory/Discrete Sources with Memory - Revision history

Guenter at 15:19, 14 February 2023

2023-02-14T15:19:50Z

Show changes

Hwang at 11:25, 13 February 2023

2023-02-13T11:25:02Z

Hwang at 11:23, 13 February 2023

2023-02-13T11:23:28Z

Hwang at 11:19, 13 February 2023

2023-02-13T11:19:26Z

Hwang at 11:17, 13 February 2023

2023-02-13T11:17:22Z

Hwang at 11:13, 13 February 2023

2023-02-13T11:13:30Z

Hwang at 11:01, 13 February 2023

2023-02-13T11:01:58Z

Hwang at 10:57, 13 February 2023

2023-02-13T10:57:03Z

Show changes

Hwang at 12:45, 23 January 2023

2023-01-23T12:45:26Z

Hwang at 23:31, 12 November 2022

2022-11-12T23:31:20Z

@@ Line 359: / Line 359: @@
 *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.
-*The two models&nbsp; $\rm MQ3$&nbsp; and&nbsp; $\rm MQ4$&nbsp; were created during the attempt to calculate the&nbsp; [[Information_Theory/Sources_with_Memory#The_Entropy_of_AMI.E2.80. 93Codes|$\text{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".
+*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|$\text{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".
 *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.
 *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)$.

@@ Line 330: / Line 330: @@
 ''Notes'':
-*In the&nbsp; [[Aufgaben:Exercise_1.6:_Non-Binary_Markov_Sources|"Exercise 1.5"]]&nbsp; the above equations are applied to the more general case of an asymmetric binary source.
+*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.
@@ Line 352: / Line 352: @@
 *a quaternary Markov source&nbsp; $\rm MQ4$&nbsp; $(M = 4$,&nbsp; red color$)$.
 <br clear=all>
-In&nbsp; [[Aufgaben:1.6_Nichtbinäre_Markovquellen|"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&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]]

@@ Line 248: / Line 248: @@
 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 Memoryless Sources#Generalization_to_.7F.27 .22.60UNIQ-MathJax109-QINU.60.22.27.7F.E2.80.93Tuple_and_boundary.C3.BCtransition|$\text{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.
+*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|$\text{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.

@@ Line 207: / Line 207: @@
 <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:
+*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}

@@ Line 193: / Line 193: @@
 ==The entropy of the AMI code ==
 <br>
-In chapter&nbsp; [[Digital_Signal_Transmission/Symbol-Wise Coding with Pseudo Ternary Codes#Properties_of_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.
+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]]
@@ Line 223: / Line 223: @@
-The&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_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.
+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.

@@ Line 40: / Line 40: @@
 <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$, 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 [[Theory_of_Stochastic_Signals/Set Theory Basics#Intersection|$\text{combined probabilities}$]]:
+*All source symbols&nbsp; $q_ν$&nbsp; are taken from an alphabet with the symbol set size&nbsp; $M$, 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 [[Theory_of_Stochastic_Signals/Set_Theory_Basics#Intersection_set|$\text{combined probabilities}$]]:
 :$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1})
@@ Line 57: / Line 57: @@
   \hspace{0.05cm}.$$
-*In order to achieve a consistent nomenclature, we now label the entropy defined in chapter&nbsp; [[Information_Theory/Discrete Memoryless Sources#Model_and_Prerequisites|"Memoryless Message Sources"]]&nbsp; with&nbsp; $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}\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})
@@ Line 70: / Line 70: @@
-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's_Law_of_Large_Numbers|$\text{relative frequencies}$]].
+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|$\text{relative frequencies}$]].
 Let us now illustrate the calculation of entropy approximations&nbsp; $H_1$&nbsp; and&nbsp; $H_2$&nbsp; with three examples.
@@ Line 116: / Line 116: @@
 *The repeated symbols are marked by corresponding lower case letters.&nbsp; But it still applies&nbsp; $M=2$.
 *Because of the equally probable binary symbols, this also results in&nbsp; $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/symbol$.
-*As shown in&nbsp; [[Aufgaben:1.3_Entropienäherungen|"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
+*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} +
 \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

@@ Line 204: / Line 204: @@
 *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 code sequence does not contain a DC component.
+*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) code 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:
+*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}

@@ Line 175: / Line 175: @@
 {{BlaueBox|TEXT=
-$\text{Summary of the results of the last pages:}$&nbsp;
+$\text{Summary of the results of the last sections:}$&nbsp;
 *Generally it applies to the&nbsp; '''entropy of a message source''':
@@ Line 268: / Line 268: @@
 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 pages 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}$, ...
+*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}$, ...
@@ Line 274: / Line 274: @@
 <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 on the previous page, we use the following nomenclature for
+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;
 *the ergodic probabilities &nbsp; &rArr; &nbsp; $p_{\text{A}}$&nbsp; and&nbsp; $p_{\text{B}}$,
@@ Line 331: / Line 331: @@
 ''Notes'':
 *In the&nbsp; [[Aufgaben:Exercise_1.6:_Non-Binary_Markov_Sources|Exercise 1.5]]&nbsp; the above equations are applied to the more general case of an asymmetric binary source.
-*All equations on this page also apply to non-binary Markov sources&nbsp; $(M > 2)$ as shown on the next page.
+*All equations in this section also apply to non-binary Markov sources&nbsp; $(M > 2)$ as shown in the next section.
@@ Line 366: / Line 366: @@
-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 on this page):
+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).