Aufgaben:Exercise 2.5: Residual Redundancy with LZW Coding - Revision history

Guenter at 12:12, 10 August 2021

2021-08-10T12:12:53Z

Guenter at 10:09, 10 August 2021

2021-08-10T10:09:47Z

Guenter at 09:54, 10 August 2021

2021-08-10T09:54:12Z

Guenter at 09:52, 10 August 2021

2021-08-10T09:52:00Z

Guenter at 15:15, 9 August 2021

2021-08-09T15:15:01Z

Noah at 20:05, 6 August 2021

2021-08-06T20:05:16Z

Noah at 18:35, 31 July 2021

2021-07-31T18:35:46Z

Noah at 18:03, 31 July 2021

2021-07-31T18:03:41Z

Show changes

Noah at 19:44, 30 July 2021

2021-07-30T19:44:49Z

Guenter at 12:00, 13 July 2021

2021-07-13T12:00:46Z

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

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Komprimierung nach Lempel~~, ~~Ziv und Welch~~	+	{{quiz-Header\|Buchseite=Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch
	}}		}}

@@ Line 98: / Line 98: @@
 {According to this result, what source entropy&nbsp; $H$&nbsp; could&nbsp; $\rm BQ3$&nbsp; ?&nbsp; <u>Hint:</u>&nbsp; Exactly one answer is correct.
 |type="()"}
-- $H = 1.00 \ \rm bit/source symbol$,
+- $H = 1.00 \ \rm bit/source\hspace{0.15cm}symbol$,
-- $H = 0.75 \ \rm bit/source symbol$,
+- $H = 0.75 \ \rm bit/source\hspace{0.15cm} symbol$,
-- $H = 0.50 \ \rm bit/source symbol$,
+- $H = 0.50 \ \rm bit/source\hspace{0.15cm} symbol$,
-+ $H = 0.25 \ \rm bit/source symbol$.
++ $H = 0.25 \ \rm bit/source\hspace{0.15cm} symbol$.
@@ Line 124: / Line 124: @@
 '''(3)'''&nbsp; In general, &nbsp;$r(N) = 1 - {H}/{K(N)} \hspace{0.05cm}.$&nbsp;
-*$\rm BQ1$&nbsp; has entropy&nbsp; $H = 0.5$ bit/symbol.&nbsp;
+*$\rm BQ1$&nbsp; has entropy&nbsp; $H = 0.5$ bit/source symbol.&nbsp;
-*It follows that because &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N)$&nbsp; für&nbsp; $K(N_3) = 0.6$:
+*It follows that because &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N)$&nbsp; for&nbsp; $K(N_3) = 0.6$:
-:$$r(N_{\rm c}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm}
+:$$r(N_{\rm 3}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm}
 {\rm lg}\hspace{0.1cm}N_{\rm 3} = \frac{A}{0.167} = 6.36
 \hspace{0.1cm}\Rightarrow\hspace{0.1cm}
@@ Line 135: / Line 135: @@
 [[File:EN_Inf_A_2_5d_v2.png|right|frame|Results for&nbsp;  $\rm BQ2$]]
-'''(4)'''&nbsp; For&nbsp; $N = 10000$&nbsp; gilt &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N) = 0.19$:
+'''(4)'''&nbsp; For&nbsp; $N = 10000$ &nbsp; &rArr; &nbsp; $r(N) &asymp; r\hspace{0.05cm}'(N) = 0.19$:
 :$$\frac{A}{{\rm lg}\hspace{0.1cm}10000} = 0.19 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 A = 0.19 \cdot 4 = 0.76 \hspace{0.05cm}. $$
@@ Line 144: / Line 144: @@
 r'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.063}.$$
-*For the compression factor, (the apostrophe indicates that the approximation &nbsp;$r\hspace{0.05cm}'(N)$&nbsp; was assumed):
+*For the compression factor &nbsp; &ndash; &nbsp; the apostrophe indicates that the approximation &nbsp;$r\hspace{0.05cm}'(N)$&nbsp; was assumed:
 :$$K\hspace{0.05cm}'(N) = \frac{1}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$
 *Thus, for the length of the LZW output string:
@@ Line 152: / Line 152: @@
 [[File:EN_Inf_A_2_5e_v2.png|right|frame|Results for&nbsp; $\rm BQ3$]]
-'''(5)'''&nbsp; Following a similar procedure as in subtask&nbsp; '''(4)'''&nbsp; we obtain the fitting parameter&nbsp; $\rm BQ3$&nbsp; for the binary source&nbsp; $A = 1.36$&nbsp; and from this the results according to the table with a blue background.
+'''(5)'''&nbsp; Following a similar procedure as in subtask&nbsp; '''(4)'''&nbsp; we obtain the fitting parameter&nbsp; $A = 1.36$&nbsp; for the binary source&nbsp; $\rm BQ3$&nbsp; and from this the results according to the table with a blue background.
-<u>Hint:</u> &nbsp; The last column of this table is only understandable with knowledge of subtask&nbsp; '''(6)'''&nbsp;. There it is shown that the source&nbsp; $\rm BQ3$&nbsp; has the entropy&nbsp; $H = 0.25$ bit/source symbol.
+<u>Hint:</u> &nbsp; The last column of this table is only understandable with knowledge of subtask&nbsp; '''(6)'''.&nbsp; There it is shown that the source&nbsp; $\rm BQ3$&nbsp; has the entropy&nbsp; $H = 0.25$&nbsp; bit/source symbol.
 *In this case, the following applies to the compression factor:
@@ Line 161: / Line 161: @@
 :$$r\hspace{0.05cm}'(N = 50000)\hspace{0.15cm}\underline{ = 0.289},\hspace{0.3cm}r\hspace{0.05cm}'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.227},\hspace{0.3cm}
 r\hspace{0.05cm}'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.113}.$$
-*Thus, for&nbsp; $N = 10^{12}$&nbsp; , the compression factor&nbsp; $(0.282)$&nbsp; still deviates significantly from the entropy&nbsp; $(0.25)$&nbsp; which can only be achieved for&nbsp; $N \to \infty$&nbsp; (source coding theorem).
+*Thus, for&nbsp; $N = 10^{12}$&nbsp; , the compression factor&nbsp; $(0.282)$&nbsp; still deviates significantly from the entropy&nbsp; $(0.25)$&nbsp; which can only be achieved for&nbsp; $N \to \infty$&nbsp; ("Source Coding Theorem").
@@ Line 169: / Line 169: @@
 # Source&nbsp; $\rm BQ1$&nbsp; with&nbsp; $H = 0.50$ &nbsp; &rArr; &nbsp; $A = 1.06$ &nbsp; &rArr; &nbsp; according to the specification sheet,
 # Source&nbsp; $\rm BQ2$&nbsp; with&nbsp; $H = 1.00$ &nbsp; &rArr; &nbsp; $A = 0.76$ &nbsp; &rArr; &nbsp; see subtask&nbsp; '''(4)''',
-# Source&nbsp; $\rm BQ3$&nbsp; $(H$ unknown$)$: $A = 4 &middot; 0.34 =1.36$ &nbsp; &rArr; &nbsp; corresponding to the last column in the table.
+# Source&nbsp; $\rm BQ3$&nbsp; $(H$ unknown$)$: $A = 4 &middot; 0.34 =1.36$ &nbsp; &rArr; &nbsp; corresponding to the table on the right.
 *Obviously, the smaller the entropy&nbsp; $H$&nbsp; the larger the adjustment factor&nbsp; $A$&nbsp; (and vice versa).
-*Since exactly one solution is possible, &nbsp; $H = 0.25$&nbsp; bit/source symbol must be correct &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>answer 4</u>.
+*Since exactly one solution is possible, &nbsp; $H = 0.25$&nbsp; bit/source&nbsp; symbol must be correct &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>answer 4</u>.
-*In fact, the probabilities&nbsp;$p_{\rm A} = 0.96$&nbsp; and &nbsp;$p_{\rm B} = 0.04$&nbsp; &nbsp; &#8658; &nbsp; $H &asymp; 0.25$ were used in the simulation for source&nbsp; $\rm BQ3$&nbsp;.
+*In fact, the probabilities&nbsp;$p_{\rm A} = 0.96$&nbsp; and &nbsp;$p_{\rm B} = 0.04$&nbsp; &nbsp; &#8658; &nbsp; $H &asymp; 0.25$ were used in the simulation for the source&nbsp; $\rm BQ3$.
 {{ML-Fuß}}

@@ Line 57: / Line 57: @@
 *The task belongs to the chapter&nbsp;  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Compression according to Lempel, Ziv and Welch]].
 *In particular, reference is made to the pages
-:: [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Remaining_redundancy_as_a_measure_for_the_efficiency_of_coding_methods|Residual redundancy as a measure for the efficiency of coding methods]],
+:: [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Remaining_redundancy_as_a_measure_for_the_efficiency_of_coding_methods|Remaining redundancy as a measure for the efficiency of coding methods]],
 :: [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Efficiency_of_Lempel-Ziv_coding|Efficiency of Lempel-Ziv coding]] and
 :: [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_statements_on_asymptotic_optimality|Quantitative statements on asymptotic optimality]].

@@ Line 20: / Line 20: @@
 whereby we have restricted ourselves to sequence lengths&nbsp; $N &#8804; 50000$&nbsp; in the simulation.
-The&nbsp; "relative redundancy of the output sequence" &ndash; simplified called&nbsp; !residual redundancy" &ndash;  can be calculated from
+The&nbsp; "relative redundancy of the output sequence" &ndash; simplified called&nbsp; "residual redundancy" &ndash;  can be calculated from
 * the length&nbsp;  $N$&nbsp;  of the input sequence,
 * the length&nbsp;  $L(N)$&nbsp;  of the output sequence and
@@ Line 38: / Line 38: @@
 :$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$
-In the&nbsp;  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_statements_on_asymptotic_optimality|theory section]]&nbsp;  it was shown that the residual redundancy&nbsp;  $r(n)$&nbsp;  is often given by the function
+In the&nbsp;  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_statements_on_asymptotic_optimality|theory section]]&nbsp;  it was shown that the residual redundancy&nbsp;  $r(n)$&nbsp;  is well approximated by the function
 :$$r\hspace{0.05cm}'(N) =\frac {A}{{\rm lg}\hspace{0.1cm}(N)}
 \hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)}
 \hspace{0.05cm}.$$
-is well approximated.
 *This approximation&nbsp;  $r\hspace{0.05cm}'(N)$&nbsp;  is given for&nbsp;  $\rm BQ1$&nbsp;  in the second column of the table above.
@@ Line 96: / Line 96: @@
-{According to this result, what source entropy&nbsp; $H$&nbsp; could&nbsp; $\rm BQ3$&nbsp; ?&nbsp; <i>Hint:</i> Exactly one answer is correct.
+{According to this result, what source entropy&nbsp; $H$&nbsp; could&nbsp; $\rm BQ3$&nbsp; ?&nbsp; <u>Hint:</u>&nbsp; Exactly one answer is correct.
 |type="()"}
 - $H = 1.00 \ \rm bit/source symbol$,

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2446__Inf_A_2_5_neu.png|right|frame|Residual redundancy&nbsp; $r(N)$&nbsp; & approximation &nbsp; $r\hspace{0.05cm}'(N)$&nbsp; of three binary sources]]
+[[File:P_ID2446__Inf_A_2_5_neu.png|right|frame|Residual redundancy&nbsp; $r(N)$&nbsp; and approximation &nbsp; $r\hspace{0.05cm}'(N)$&nbsp; of three sources]]
-We assume here a binary input sequence of length&nbsp; $N$&nbsp; and consider three different binary message sources:
+We assume here a binary input sequence of length&nbsp; $N$&nbsp; and consider three different binary sources:
-* $\rm BQ1$: &nbsp; Symbol probabilities&nbsp;   $p_{\rm A} = 0.89$&nbsp; and&nbsp; $p_{\rm B} = 0.11$, i.e. different<br> &nbsp;  &#8658; &nbsp; entropy &nbsp; $H = 0.5\text{ bit/source symbol}$ &nbsp; &#8658; &nbsp; the source is redundant.
+* $\rm BQ1$: &nbsp; Symbol probabilities&nbsp;   $p_{\rm A} = 0.89$&nbsp; and&nbsp; $p_{\rm B} = 0.11$, i.e. different<br> &nbsp;  &#8658; &nbsp; entropy &nbsp; $H = 0.5\text{ bit/source&nbsp;symbol}$ &nbsp; &#8658; &nbsp; the source is redundant.
 * $\rm BQ2$:  &nbsp; $p_{\rm A} = p_{\rm B} = 0.5$&nbsp; (equally probable)<br> &nbsp; &#8658; &nbsp; entropy &nbsp; $H = 1\text{ bit/source symbol}$ &nbsp; &#8658; &nbsp; the source is redundancy-free.
 * $\rm BQ3$: &nbsp;   There is no concrete information on the statistics here.&nbsp; <br>In subtask&nbsp; '''(6)'''&nbsp; you are to estimate the entropy&nbsp; $H$&nbsp; of this source.
-For these three sources, the respective <i>residual redundancy</i>&nbsp; $r(N)$&nbsp; was determined by simulation, which remains in the binary sequence after&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv-Welch_algorithm |Lempel&ndash;Ziv&ndash;Welch&ndash;coding]]&nbsp; in der Binärfolge verbleibt.&nbsp;
+For these three sources, the respective&nbsp; "residual redundancy"&nbsp; $r(N)$&nbsp; was determined by simulation, which remains in the binary sequence after&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv-Welch_algorithm |Lempel&ndash;Ziv&ndash;Welch coding]].&nbsp;
 The results are shown in the first column of the above table for the sources
@@ Line 20: / Line 20: @@
 whereby we have restricted ourselves to sequence lengths&nbsp; $N &#8804; 50000$&nbsp; in the simulation.
-The <i>relative redundancy of the output sequence</i> &ndash; simplified called <i>residual redundancy</i> &ndash;  can be calculated from
+The&nbsp; "relative redundancy of the output sequence" &ndash; simplified called&nbsp; !residual redundancy" &ndash;  can be calculated from
 * the length&nbsp;  $N$&nbsp;  of the input sequence,
 * the length&nbsp;  $L(N)$&nbsp;  of the output sequence and
@@ Line 26: / Line 26: @@
-can be calculated in the following way:
+in the following way:
 :$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 -  \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$
 This takes into account that with perfect source coding the length of the output sequence could be lowered to the value&nbsp;   $L_{\rm min} = N &middot; H$&nbsp;.
-*With non-perfect source coding,&nbsp;  $L(n) - N &middot; H$&nbsp;  gives the remaining redundancy (with the pseudo&ndash;unit "bit").
+*With non-perfect source coding,&nbsp;  $L(n) - N &middot; H$&nbsp;  gives the remaining redundancy&nbsp; (with the pseudo&ndash;unit&nbsp; "bit").
-*After dividing by&nbsp;  $L(n)$&nbsp;  , one obtains the relative redundancy&nbsp;  $r(n)$&nbsp;  with the value range between zero and one; $r(n)$ should be as small as possible.
+*After dividing by&nbsp;  $L(n)$,&nbsp;  one obtains the relative redundancy&nbsp;  $r(n)$&nbsp;  with the value range between zero and one;&nbsp; $r(n)$&nbsp; should be as small as possible.
-A second parameter for measuring the efficiency of LZW coding is the&nbsp;  <i>compression factor</i>&nbsp;  $K(N)$, which should also be small as the quotient of the lengths of the output and input sequences:
+A second parameter for measuring the efficiency of LZW coding is the&nbsp;  "compression factor"&nbsp;  $K(N)$&nbsp; as the quotient of the lengths of the output and input sequences, which should also be very small:
 :$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$

@@ Line 109: / Line 109: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Die Näherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; stimmt per Definition für die Folgenlänge&nbsp;  $N = 10000$&nbsp; mit der per Simulation ermittelten Restredundanz&nbsp; $r(N) = 0.265$&nbsp; exakt überein.
+'''(1)'''&nbsp; The approximation&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; agrees exactly by definition for the sequence length&nbsp;  $N = 10000$&nbsp; with the residual redundancy&nbsp; $r(N) = 0.265$&nbsp; determined by simulation.
-*Damit ist
+*Thus
 :$$A = 4 \cdot  r(N = 10000) =4 \cdot {0.265} \hspace{0.15cm}\underline{= 1.06}
 \hspace{0.05cm}. $$
@@ Line 116: / Line 116: @@
-'''(2)'''&nbsp; Aus der Beziehung&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N) &#8804; 0.05$ &nbsp;&nbsp;&nbsp;&#8658;&nbsp;&nbsp;&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N) = 0.05$&nbsp; folgt:
+'''(2)'''&nbsp; From the relationship&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N) &#8804; 0.05$ &nbsp;&nbsp;&nbsp;&#8658;&nbsp;&nbsp;&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N) = 0.05$&nbsp; it follows:
 :$${{\rm lg}\hspace{0.1cm}N_{\rm 2}} = \frac{A}{0.05} = 21.2 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 N_{\rm 2} = 10^{21.2} \hspace{0.15cm}\underline{= 1.58 \cdot 10^{21}}
@@ Line 123: / Line 123: @@
-'''(3)'''&nbsp; Allgemein gilt &nbsp;$r(N) = 1 - {H}/{K(N)} \hspace{0.05cm}.$&nbsp;
+'''(3)'''&nbsp; In general, &nbsp;$r(N) = 1 - {H}/{K(N)} \hspace{0.05cm}.$&nbsp;
-*$\rm BQ1$&nbsp; hat die Entropie&nbsp; $H = 0.5$ bit/Symbol.&nbsp;
+*$\rm BQ1$&nbsp; has entropy&nbsp; $H = 0.5$ bit/symbol.&nbsp;
-*Daraus folgt wegen &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N)$&nbsp; für&nbsp; $K(N_3) = 0.6$:
+*It follows that because &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N)$&nbsp; für&nbsp; $K(N_3) = 0.6$:
 :$$r(N_{\rm c}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm}
 {\rm lg}\hspace{0.1cm}N_{\rm 3} = \frac{A}{0.167} = 6.36
@@ Line 134: / Line 134: @@
-[[File:EN_Inf_A_2_5d_v2.png|right|frame|Ergebnisse für&nbsp;  $\rm BQ2$]]
+[[File:EN_Inf_A_2_5d_v2.png|right|frame|Results for&nbsp;  $\rm BQ2$]]
-'''(4)'''&nbsp; Für&nbsp; $N = 10000$&nbsp; gilt &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N) = 0.19$:
+'''(4)'''&nbsp; For&nbsp; $N = 10000$&nbsp; gilt &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N) = 0.19$:
 :$$\frac{A}{{\rm lg}\hspace{0.1cm}10000} = 0.19 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 A = 0.19 \cdot 4 = 0.76 \hspace{0.05cm}. $$
-*Die Ergebnisse sind in nebenstehender Tabelle zusammengefasst.
+*The results are summarised in the table opposite.
-*Man erkennt die sehr gute Übereinstimmung zwischen&nbsp; &nbsp;$r(N)$&nbsp; und  &nbsp;$r\hspace{0.05cm}'(N)$.
+*One can see the very good agreement between&nbsp; &nbsp;$r(N)$&nbsp; and  &nbsp;$r\hspace{0.05cm}'(N)$.
-*Die gesuchten Zahlenwerte sind in der Tabelle rot markiert:
+*The numerical values sought are marked in red in the table:
 $$r'(N = 50000)\hspace{0.15cm}\underline{ = 0.162},\hspace{0.3cm}r'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.127},\hspace{0.3cm}
 r'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.063}.$$
-*Für den Komprimierungsfaktor gilt (der Apostroph weist darauf hin, dass von der Näherung &nbsp;$r\hspace{0.05cm}'(N)$&nbsp; ausgegangen wurde):
+*For the compression factor, (the apostrophe indicates that the approximation &nbsp;$r\hspace{0.05cm}'(N)$&nbsp; was assumed):
 :$$K\hspace{0.05cm}'(N) = \frac{1}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$
-*Damit gilt für die Länge des LZW&ndash;Ausgabestrings:
+*Thus, for the length of the LZW output string:
 :$$L\hspace{0.05cm}'(N) = K\hspace{0.05cm}'(N) \cdot N  = \frac{N}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$
-[[File:EN_Inf_A_2_5e_v2.png|right|frame|Ergebnisse für&nbsp; $\rm BQ3$]]
+[[File:EN_Inf_A_2_5e_v2.png|right|frame|Results for&nbsp; $\rm BQ3$]]
-'''(5)'''&nbsp; Nach ähnlicher Vorgehensweise wie in der Teilaufgabe&nbsp; '''(4)'''&nbsp; erhält man für die Binärquelle&nbsp; $\rm BQ3$&nbsp; den Anpassungsparameter&nbsp; $A = 1.36$&nbsp; und daraus die Ergebnisse gemäß der blau hinterlegten Tabelle.
+'''(5)'''&nbsp; Following a similar procedure as in subtask&nbsp; '''(4)'''&nbsp; we obtain the fitting parameter&nbsp; $\rm BQ3$&nbsp; for the binary source&nbsp; $A = 1.36$&nbsp; and from this the results according to the table with a blue background.
-<u>Hinweis:</u> &nbsp; Die letzte Spalte dieser Tabelle ist nur bei Kenntnis der Teilaufgabe&nbsp; '''(6)'''&nbsp; verständlich. Dort wird gezeigt, dass die  Quelle&nbsp; $\rm BQ3$&nbsp; die Entropie&nbsp; $H = 0.25$ bit/Quellensymbol besitzt.
+<u>Hint:</u> &nbsp; The last column of this table is only understandable with knowledge of subtask&nbsp; '''(6)'''&nbsp;. There it is shown that the source&nbsp; $\rm BQ3$&nbsp; has the entropy&nbsp; $H = 0.25$ bit/source symbol.
-*In diesem Fall gilt für den Komprimierungsfaktor:
+*In this case, the following applies to the compression factor:
 :$$K\hspace{0.05cm}'(N) = \frac{H}{1 - r\hspace{0.05cm}'(N)} = \frac{0.25}{1 - r'(N)} \hspace{0.05cm}.$$
-*Damit erhält man für die gesuchten Werte der Restredundanz:
+*Thus, for the values of residual redundancy we are looking for, we obtain:
 :$$r\hspace{0.05cm}'(N = 50000)\hspace{0.15cm}\underline{ = 0.289},\hspace{0.3cm}r\hspace{0.05cm}'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.227},\hspace{0.3cm}
 r\hspace{0.05cm}'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.113}.$$
-*Für&nbsp; $N = 10^{12}$&nbsp; weicht also der Komprimierungsfaktor&nbsp; $(0.282)$&nbsp; noch deutlich von der Entropie&nbsp; $(0.25)$&nbsp; ab, die erst  für&nbsp; $N \to \infty$&nbsp; erreicht werden kann (Quellencodierungstheorem).
+*Thus, for&nbsp; $N = 10^{12}$&nbsp; , the compression factor&nbsp; $(0.282)$&nbsp; still deviates significantly from the entropy&nbsp; $(0.25)$&nbsp; which can only be achieved for&nbsp; $N \to \infty$&nbsp; (source coding theorem).
-'''(6)'''&nbsp; Die einzelnen Näherungen&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; unterscheiden sich nur durch den Parameter&nbsp; $A$.&nbsp; Dabei haben wir festgestellt:
+'''(6)'''&nbsp; The individual approximations&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; differ only by the parameter&nbsp; $A$.&nbsp; Here we found:
-# Quelle&nbsp; $\rm BQ1$&nbsp; mit&nbsp; $H = 0.50$ &nbsp; &rArr; &nbsp; $A = 1.06$ &nbsp; &rArr; &nbsp; entsprechend dem Angabenblatt,
+# Source&nbsp; $\rm BQ1$&nbsp; with&nbsp; $H = 0.50$ &nbsp; &rArr; &nbsp; $A = 1.06$ &nbsp; &rArr; &nbsp; according to the specification sheet,
-# Quelle&nbsp; $\rm BQ2$&nbsp; mit&nbsp; $H = 1.00$ &nbsp; &rArr; &nbsp; $A = 0.76$ &nbsp; &rArr; &nbsp; siehe Teilaufgabe&nbsp; '''(4)''',
+# Source&nbsp; $\rm BQ2$&nbsp; with&nbsp; $H = 1.00$ &nbsp; &rArr; &nbsp; $A = 0.76$ &nbsp; &rArr; &nbsp; see subtask&nbsp; '''(4)''',
-# Quelle&nbsp; $\rm BQ3$&nbsp; $(H$ unbekannt$)$: $A = 4 &middot; 0.34 =1.36$ &nbsp; &rArr; &nbsp; entsprechend der letzten Spalte in der Tabelle.
+# Source&nbsp; $\rm BQ3$&nbsp; $(H$ unknown$)$: $A = 4 &middot; 0.34 =1.36$ &nbsp; &rArr; &nbsp; corresponding to the last column in the table.
-*Je kleiner die Entropie&nbsp; $H$&nbsp; ist, um so größer ist offensichtlich der Anpassungsfaktor&nbsp; $A$&nbsp; (und umgekehrt).
+*Obviously, the smaller the entropy&nbsp; $H$&nbsp; the larger the adjustment factor&nbsp; $A$&nbsp; (and vice versa).
-*Da genau eine Lösung möglich ist, muss&nbsp; $H = 0.25$&nbsp; bit/Quellensymbol richtig sein &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Antwort 4</u>.
+*Since exactly one solution is possible, &nbsp; $H = 0.25$&nbsp; bit/source symbol must be correct &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>answer 4</u>.
-*Tatsächlich wurden bei der Simulation für die Quelle&nbsp; $\rm BQ3$&nbsp; die Wahrscheinlichkeiten &nbsp;$p_{\rm A} = 0.96$&nbsp; und &nbsp;$p_{\rm B} = 0.04$&nbsp; &nbsp; &#8658; &nbsp; $H &asymp; 0.25$ verwendet.
+*In fact, the probabilities&nbsp;$p_{\rm A} = 0.96$&nbsp; and &nbsp;$p_{\rm B} = 0.04$&nbsp; &nbsp; &#8658; &nbsp; $H &asymp; 0.25$ were used in the simulation for source&nbsp; $\rm BQ3$&nbsp;.
 {{ML-Fuß}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2446__Inf_A_2_5_neu.png|right|frame|Restredundanz&nbsp; $r(N)$&nbsp; & Näherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; dreier Binärquellen]]
+[[File:P_ID2446__Inf_A_2_5_neu.png|right|frame|Residual redundancy&nbsp; $r(N)$&nbsp; & approximation &nbsp; $r\hspace{0.05cm}'(N)$&nbsp; of three binary sources]]
 Wir gehen hier von einer binären Eingangsfolge der Länge&nbsp; $N$&nbsp; aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
 * $\rm BQ1$: &nbsp; Symbolwahrscheinlichkeiten&nbsp;   $p_{\rm A} = 0.89$&nbsp; und&nbsp; $p_{\rm B} = 0.11$, also unterschiedlich<br> &nbsp;  &#8658; &nbsp; Entropie&nbsp; $H = 0.5\text{ bit/Quellensymbol}$ &nbsp; &#8658; &nbsp; die Quelle ist redundant.

← Older revision		Revision as of 12:00, 13 July 2021
Line 179:		Line 179:


−	[[Category:Information Theory: Exercises\|^2.2 ~~Verfahren von~~ Lempel, Ziv, Welch^]]	+	[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]