Aufgaben:Exercise 2.2: Kraft–McMillan Inequality - Revision history

Hwang at 14:52, 1 November 2022

2022-11-01T14:52:32Z

Javier: Text replacement - "code symbol sequence" to "encoded sequence"

2021-08-16T12:07:57Z

Text replacement - "code symbol sequence" to "encoded sequence"

Guenter at 12:08, 10 August 2021

2021-08-10T12:08:45Z

Noah at 20:29, 6 August 2021

2021-08-06T20:29:38Z

Guenter at 14:39, 7 July 2021

2021-07-07T14:39:32Z

Guenter at 14:28, 7 July 2021

2021-07-07T14:28:45Z

Noah at 20:53, 29 June 2021

2021-06-29T20:53:49Z

Noah at 20:26, 29 June 2021

2021-06-29T20:26:48Z

Guenter at 15:05, 26 June 2021

2021-06-26T15:05:18Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung to Aufgaben:Exercise 2.2: Kraft–McMillan Inequality

2021-06-26T15:02:07Z

Guenter moved page Aufgabe 2.2: Kraftsche Ungleichung to Exercise 2.2: Kraft–McMillan Inequality

@@ Line 16: / Line 16: @@
 For example, the binary code&nbsp;  $\rm B2$&nbsp; has this property:   &nbsp;
-*Here, one codeword each has the length &nbsp; $1$,&nbsp; $2$&nbsp; and&nbsp; $3$, respectively&nbsp; $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
+*Here, one code word each has the length &nbsp; $1$,&nbsp; $2$&nbsp; and&nbsp; $3$, respectively&nbsp; $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
 *Two code words have the length&nbsp; $L_\mu = 4$&nbsp; $(N_4 = N_5 = 4)$.
 A prerequisite for the decodability of such a code is that the code is&nbsp; '''prefix-free'''&nbsp;.&nbsp;
-*That is, no codeword may be the prefix (i.e., the beginning) of a longer codeword.
+*That is, no code word may be the prefix (i.e., the beginning) of a longer code word.
 *A necessary condition for a code  for data compression to be prefix-free was stated by Leon Kraft in 1949, called&nbsp;  '''Kraft's inequality''':
@@ Line 28: / Line 28: @@
 Here denote
 * $M$&nbsp; the number of possible source symbols&nbsp; $q_\mu$ &nbsp; &rArr; &nbsp; "symbol set size",
-* $L_\mu$&nbsp; the length of the codeword&nbsp; $c_\mu$&nbsp; associated with the source symbol&nbsp;  $q_\mu$,
+* $L_\mu$&nbsp; the length of the code word&nbsp; $c_\mu$&nbsp; associated with the source symbol&nbsp;  $q_\mu$,
 * $D = 2$&nbsp; denotes a binary code&nbsp; $(\rm 0$&nbsp;  or&nbsp; $\rm 1)$&nbsp; and&nbsp; $D = 3$&nbsp; denotes a ternary code&nbsp; $(\rm 0$,&nbsp; $\rm 1$,&nbsp; $\rm 2)$.
@@ Line 78: / Line 78: @@
-{How many trivalent codewords&nbsp; $(L_\mu = 3)$&nbsp; could be added to the&nbsp; $\rm T1$&nbsp; code without changing the prefix freedom?
+{How many trivalent code words&nbsp; $(L_\mu = 3)$&nbsp; could be added to the&nbsp; $\rm T1$&nbsp; code without changing the prefix freedom?
 |type="{}"}
 $\Delta N_3 \ = \ $ { 6 }
-{The ternary code&nbsp; $\rm T3$&nbsp; is to be expanded to a total of&nbsp; $N = 9$&nbsp; codewords.&nbsp; How to achieve this without violating the prefix freedom?
+{The ternary code&nbsp; $\rm T3$&nbsp; is to be expanded to a total of&nbsp; $N = 9$&nbsp; code words.&nbsp; How to achieve this without violating the prefix freedom?
 |type="[]"}
-- Addition of four three-valued codewords.
+- Addition of four three-valued code words.
-+ Addition of four four-valued codewords.
++ Addition of four four-valued code words.
-+ Addition of one trivalent and three tetravalent codewords.
++ Addition of one trivalent and three tetravalent code words.
@@ Line 106: / Line 106: @@
 *The code&nbsp; $\rm B4$, which does not satisfy Kraft's inequality, is certainly not prefix-free either.
 *But if Kraft's inequality is fulfilled, it is still not certain that this code is also prefix-free.
-*In code&nbsp; $\rm B3$&nbsp; the codeword&nbsp;  "10"&nbsp; is the beginning of the codeword&nbsp; "1011".
+*In code&nbsp; $\rm B3$&nbsp; the code word&nbsp;  "10"&nbsp; is the beginning of the code word&nbsp; "1011".
 *In contrast, codes&nbsp; $\rm B1$&nbsp; and&nbsp; $\rm B2$&nbsp; are actually prefix-free.
@@ Line 114: / Line 114: @@
 *Kraft's inequality is satisfied by all three codes.
 *As can be seen from the table, codes&nbsp; $\rm T1$&nbsp; and&nbsp; $\rm T3$&nbsp; are indeed prefix-free.
-*The code&nbsp; $\rm T2$&nbsp;, on the other hand, is not prefix-free because "1" is the beginning of the codeword "10".
+*The code&nbsp; $\rm T2$&nbsp;, on the other hand, is not prefix-free because "1" is the beginning of the code word "10".
-'''(4)'''&nbsp; $N_i$&nbsp; indicates how many codewords with&nbsp; $i$&nbsp; symbols there are in the code.&nbsp; For the code&nbsp; $\rm T1$&nbsp; it is:
+'''(4)'''&nbsp; $N_i$&nbsp; indicates how many code words with&nbsp; $i$&nbsp; symbols there are in the code.&nbsp; For the code&nbsp; $\rm T1$&nbsp; it is:
 :$$N_1 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}, \hspace{0.2cm}N_2 \hspace{0.15cm}\underline{= 2}\hspace{0.05cm}, \hspace{0.2cm}N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
@@ Line 147: / Line 147: @@
 Thus, <u>the two last proposed solutions</u> are correct.
-For example, the total&nbsp; $N = 9$&nbsp; codewords of the prefix-free code&nbsp; $\rm T6$&nbsp;  are:
+For example, the total&nbsp; $N = 9$&nbsp; code words of the prefix-free code&nbsp; $\rm T6$&nbsp;  are:
 :$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
 {{ML-Fuß}}

@@ Line 6: / Line 6: @@
 In the figure some exemplary binary and ternary codes are given.
-*With the  binary code&nbsp; $\rm B1$&nbsp; all possible source symbols&nbsp; $q_\mu$&nbsp; $($with index&nbsp; $\mu = 1$, ... , $8)$&nbsp; are represented by a code symbol sequence&nbsp; $\langle c_\mu \rangle $&nbsp; of uniform length&nbsp; $L_\mu = 3$&nbsp;.
+*With the  binary code&nbsp; $\rm B1$&nbsp; all possible source symbols&nbsp; $q_\mu$&nbsp; $($with index&nbsp; $\mu = 1$, ... , $8)$&nbsp; are represented by a encoded sequence&nbsp; $\langle c_\mu \rangle $&nbsp; of uniform length&nbsp; $L_\mu = 3$&nbsp;.
 *This code is unsuitable for data compression for this reason.

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

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Allgemeine Beschreibung~~	+	{{quiz-Header\|Buchseite=Information_Theory/General_Description
	}}		}}

← Older revision		Revision as of 20:29, 6 August 2021
Line 39:		Line 39:


−	''Hint:''	+	Hint:
	*The exercise belongs to the chapter  [[Information_Theory/Allgemeine_Beschreibung\|General Description of Source Coding]].		*The exercise belongs to the chapter  [[Information_Theory/Allgemeine_Beschreibung\|General Description of Source Coding]].

@@ Line 97: / Line 97: @@
 '''(1)'''&nbsp; The correct <u>solutions are 1, 2 and 3.</u>&nbsp; The following applies to the binary codes given:
 * $\rm B1$:&nbsp;&nbsp;&nbsp; $8 \cdot 2^{-3} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition fulfilled,
-* $\rm B2$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition met,
+* $\rm B2$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition fulfilled,
-* $\rm B3$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition met,
+* $\rm B3$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition fulfilled,
-* $\rm B4$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3}  + 1 \cdot 2^{-4}= 17/16$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition <u>not</u> met.
+* $\rm B4$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3}  + 1 \cdot 2^{-4}= 17/16$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition <u>not</u> fulfilled.
@@ Line 106: / Line 106: @@
 *The code&nbsp; $\rm B4$, which does not satisfy Kraft's inequality, is certainly not prefix-free either.
 *But if Kraft's inequality is fulfilled, it is still not certain that this code is also prefix-free.
-*In code&nbsp; $\rm B3$&nbsp; "10" is the beginning of the code word "1011".
+*In code&nbsp; $\rm B3$&nbsp; the codeword&nbsp;  "10"&nbsp; is the beginning of the codeword&nbsp; "1011".
 *In contrast, codes&nbsp; $\rm B1$&nbsp; and&nbsp; $\rm B2$&nbsp; are actually prefix-free.
@@ Line 132: / Line 132: @@
-'''(6)'''&nbsp; For code&nbsp; $\rm T3$&nbsp; it is:
+'''(6)'''&nbsp; For code&nbsp; $\rm T3$&nbsp; it holds:
 *$S({\rm T3})= 2 \cdot 3^{-1} + &nbsp;2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
 *Because of&nbsp; $S({\rm T3}) \le 1$&nbsp; the ternary code&nbsp; $\rm T3$&nbsp; satisfies Kraft's inequality and it is also prefix-free.
@@ Line 139: / Line 139: @@
 Let us now consider the proposed new codes.
 * Code $\rm T4$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 5)$:
-:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}is\hspace{0.15cm} not suitable}\hspace{0.05cm},$$
+:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}is\hspace{0.15cm} unsuitable}\hspace{0.05cm},$$
 * Code $\rm T5$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 1, \ N_4 = 4)$:
 :$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}is\hspace{0.15cm} suitable}\hspace{0.05cm},$$
@@ Line 145: / Line 145: @@
 :$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}is\hspace{0.15cm} suitable}\hspace{0.05cm}.$$
 Thus, <u>the two last proposed solutions</u> are correct.
-For example, the total&nbsp; $N = 9$&nbsp; codewords of the prefix-free code are&nbsp; $\rm T6$:
 :$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
 {{ML-Fuß}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2416__Inf_A_2_2.png|right|frame|Four examples of binary codes and in addition three ternary codes]]
+[[File:P_ID2416__Inf_A_2_2.png|right|frame|Four examples of binary codes and three ternary codes]]
 In the figure some exemplary binary and ternary codes are given.
-*In binary code&nbsp; $\rm B1$&nbsp; all possible source symbols&nbsp; $q_\mu$&nbsp; $($with run index&nbsp; $\mu = 1$, ... , $8)$&nbsp; are each represented by a code symbol sequence&nbsp; $\langle c_\mu \rangle $&nbsp; of uniform length&nbsp; $L_\mu = 3$&nbsp;.
+*With the  binary code&nbsp; $\rm B1$&nbsp; all possible source symbols&nbsp; $q_\mu$&nbsp; $($with index&nbsp; $\mu = 1$, ... , $8)$&nbsp; are represented by a code symbol sequence&nbsp; $\langle c_\mu \rangle $&nbsp; of uniform length&nbsp; $L_\mu = 3$&nbsp;.
 *This code is unsuitable for data compression for this reason.
 The possibility of data compression arises only when
-* the&nbsp; $M$&nbsp; Quellensymbole nicht gleichwahrscheinlich, und
+*the&nbsp; $M$&nbsp; source symbols are not equally likely, and
-*die Länge&nbsp; $L_\mu$&nbsp; der Codeworte unterschiedlich sind.
+*the length&nbsp; $L_\mu$&nbsp; of the code words are different.
 For example, the binary code&nbsp;  $\rm B2$&nbsp; has this property:   &nbsp;
-*Here, one codeword each has the length &nbsp; $1$,&nbsp; $2$&nbsp; and&nbsp; $3$, respectively&nbsp; $(N_1 = N_2 = N_3 = 1)$.
+*Here, one codeword each has the length &nbsp; $1$,&nbsp; $2$&nbsp; and&nbsp; $3$, respectively&nbsp; $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
-*Two code words have the length&nbsp; $L_\mu = 4$&nbsp; $(N_4 = N_5 = 2)$.
+*Two code words have the length&nbsp; $L_\mu = 4$&nbsp; $(N_4 = N_5 = 4)$.
@@ Line 23: / Line 23: @@
 *That is, no codeword may be the prefix (i.e., the beginning) of a longer codeword.
-*A necessary condition for a code to be prefix-free for data compression was stated by Leon Kraft in 1949, called&nbsp;  '''Kraft's inequality''':
+*A necessary condition for a code  for data compression to be prefix-free was stated by Leon Kraft in 1949, called&nbsp;  '''Kraft's inequality''':
 :$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu}} \le 1 \hspace{0.05cm}.$$
 Here denote
-* $M$&nbsp; the number of possible source symbols&nbsp; $q_\mu$,
+* $M$&nbsp; the number of possible source symbols&nbsp; $q_\mu$ &nbsp; &rArr; &nbsp; "symbol set size",
-* $L_\mu$&nbsp; the length of the codeword&nbsp; $q_\mu$&nbsp; associated with the source symbol&nbsp;  $c_\mu$,
+* $L_\mu$&nbsp; the length of the codeword&nbsp; $c_\mu$&nbsp; associated with the source symbol&nbsp;  $q_\mu$,
-* $D = 2$&nbsp; denotes a binary code&nbsp; $(\rm 0$  or&nbsp; $\rm 1)$&nbsp; and&nbsp; $D = 3$&nbsp; denotes a ternary code&nbsp; $(\rm 0$,&nbsp; $\rm 1$,&nbsp; $\rm 2)$.
+* $D = 2$&nbsp; denotes a binary code&nbsp; $(\rm 0$&nbsp;  or&nbsp; $\rm 1)$&nbsp; and&nbsp; $D = 3$&nbsp; denotes a ternary code&nbsp; $(\rm 0$,&nbsp; $\rm 1$,&nbsp; $\rm 2)$.
-A code can be prefix-free only if Kraft's inequality is satisfied.&nbsp; The converse does not hold: &nbsp; if Kraft's inequality is satisfied, it does not mean that this code is actually prefix-free.
+A code can be prefix-free only if Kraft's inequality is satisfied.&nbsp;
@@ Line 38: / Line 40: @@
 ''Hint:''
-*The task belongs to the chapter&nbsp; [[Information_Theory/Allgemeine_Beschreibung|General description of source coding]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Allgemeine_Beschreibung|General Description of Source Coding]].

@@ Line 91: / Line 91: @@
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1, 2 und 3.</u>&nbsp; Für die angegebenen Binärcodes gilt:
+'''(1)'''&nbsp; The correct <u>solutions are 1, 2 and 3.</u>&nbsp; The following applies to the binary codes given:
-* $\rm B1$:&nbsp;&nbsp;&nbsp; $8 \cdot 2^{-3} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
+* $\rm B1$:&nbsp;&nbsp;&nbsp; $8 \cdot 2^{-3} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition fulfilled,
-* $\rm B2$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
+* $\rm B2$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition met,
-* $\rm B3$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
+* $\rm B3$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition met,
-* $\rm B4$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3}  + 1 \cdot 2^{-4}= 17/16$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung <u>nicht</u> erfüllt.
+* $\rm B4$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3}  + 1 \cdot 2^{-4}= 17/16$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; condition <u>not</u> met.
-'''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>
+'''(2)'''&nbsp; <u>Proposed solutions 1 and 2</u> are correct:
-*Der Code&nbsp; $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.
+*The code&nbsp; $\rm B4$, which does not satisfy Kraft's inequality, is certainly not prefix-free either.
-*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.
+*But if Kraft's inequality is fulfilled, it is still not certain that this code is also prefix-free.
-*Beim Code&nbsp; $\rm B3$&nbsp; ist "10" der Beginn des Codewortes "1011".
+*In code&nbsp; $\rm B3$&nbsp; "10" is the beginning of the code word "1011".
-*Dagegen sind die Codes&nbsp; $\rm B1$&nbsp; und&nbsp; $\rm B2$&nbsp; tatsächlich präfixfrei.
+*In contrast, codes&nbsp; $\rm B1$&nbsp; and&nbsp; $\rm B2$&nbsp; are actually prefix-free.
-'''(3)'''&nbsp; Richtig sind die <u>Antworten 1 und 3</u>:
+'''(3)'''&nbsp; The correct <u>solutions are 1 and 3</u>:
-*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
+*Kraft's inequality is satisfied by all three codes.
-*Wie aus der Tabelle hervorgeht, sind die Codes&nbsp; $\rm T1$&nbsp; und&nbsp; $\rm T3$&nbsp; tatsächlich präfixfrei.
+*As can be seen from the table, codes&nbsp; $\rm T1$&nbsp; and&nbsp; $\rm T3$&nbsp; are indeed prefix-free.
-*Der Code&nbsp; $\rm T2$&nbsp; ist dagegen nicht präfixfrei, da "1" der Beginn des Codewortes "10" ist.
+*The code&nbsp; $\rm T2$&nbsp;, on the other hand, is not prefix-free because "1" is the beginning of the codeword "10".
-'''(4)'''&nbsp; $N_i$&nbsp; gibt an, wieviele Codeworte  mit&nbsp; $i$&nbsp; Symbolen  es im Code gibt.&nbsp; Für den Code&nbsp; $\rm T1$&nbsp; gilt:
+'''(4)'''&nbsp; $N_i$&nbsp; indicates how many codewords with&nbsp; $i$&nbsp; symbols there are in the code.&nbsp; For the code&nbsp; $\rm T1$&nbsp; it is:
 :$$N_1 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}, \hspace{0.2cm}N_2 \hspace{0.15cm}\underline{= 2}\hspace{0.05cm}, \hspace{0.2cm}N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
-'''(5)'''&nbsp; Nach der Kraftschen Ungleichung muss gelten
+'''(5)'''&nbsp; According to Kraft's inequality, the following must be true
 :$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$
-Bei gegebenem&nbsp; $N_1 = 1$&nbsp; und&nbsp;  $N_2 = 2$&nbsp; wird dies erfüllt, solange gilt:
+For given&nbsp; $N_1 = 1$&nbsp; and&nbsp;  $N_2 = 2$&nbsp; , this is satisfied as long as holds:
 :$$N_3 \cdot 3^{-3 } \le 1 - 1/3 - 2/9 = 4/9 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}N_3  \le 12 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm \Delta}\,N_3
 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
-Die zusätzlichen Codeworte sind&nbsp; $\rm 210, \,211, \,212, \,220, \,221, \,222$.
+The additional code words are&nbsp; $\rm 210, \,211, \,212, \,220, \,221, \,222$.
-'''(6)'''&nbsp; Für den Code&nbsp; $\rm T3$&nbsp; gilt:
+'''(6)'''&nbsp; For code&nbsp; $\rm T3$&nbsp; it is:
 *$S({\rm T3})= 2 \cdot 3^{-1} + &nbsp;2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
-*Wegen&nbsp; $S({\rm T3}) \le 1$&nbsp; erfüllt der Ternärcode&nbsp; $\rm T3$&nbsp; die Kraftsche Ungleichung und er ist zudem auch präfixfrei.
+*Because of&nbsp; $S({\rm T3}) \le 1$&nbsp; the ternary code&nbsp; $\rm T3$&nbsp; satisfies Kraft's inequality and it is also prefix-free.
-Betrachten wir nun die vorgeschlagenen neuen Codes.
+Let us now consider the proposed new codes.
 * Code $\rm T4$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 5)$:
-:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}ist\hspace{0.15cm} ungeeignet}\hspace{0.05cm},$$
+:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}is\hspace{0.15cm} not suitable}\hspace{0.05cm},$$
 * Code $\rm T5$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 1, \ N_4 = 4)$:
-:$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm},$$
+:$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}is\hspace{0.15cm} suitable}\hspace{0.05cm},$$
 * Code $\rm T6$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 2, \ N_4 = 3)$:
-:$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm}.$$
+:$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}is\hspace{0.15cm} suitable}\hspace{0.05cm}.$$
-Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.
+Thus, <u>the two last proposed solutions</u> are correct.
-Beispielsweise lauten die insgesamt&nbsp; $N = 9$&nbsp; Codeworte des präfixfreien Codes&nbsp; $\rm T6$:
+For example, the total&nbsp; $N = 9$&nbsp; codewords of the prefix-free code are&nbsp; $\rm T6$:
 :$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
 {{ML-Fuß}}

← Older revision		Revision as of 15:05, 26 June 2021
Line 151:		Line 151:


−	[[Category:Information Theory: Exercises\|^2.1 ~~Allgemeine Beschreibung~~^]]	+	[[Category:Information Theory: Exercises\|^2.1 General Description^]]

← Older revision	Revision as of 15:02, 26 June 2021
(No difference)