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

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:56:23Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:56, 16 March 2026
Line 153:		Line 153:

	[[Category:Information Theory: Exercises\|^2.1 General Description^]]		[[Category:Information Theory: Exercises\|^2.1 General Description^]]
	[[de:Aufgaben:2.~~02_Kraftsche_Ungleichung~~]]		[[de:Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:47:44Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:47, 16 March 2026
Line 126:		Line 126:
	:$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$		:$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$
	For given  $N_1 = 1$  and  $N_2 = 2$  , this is satisfied as long as holds:		For given  $N_1 = 1$  and  $N_2 = 2$  , 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		:$$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}.$$
	\hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
	The additional code words are  $\rm 210, \,211, \,212, \,220, \,221, \,222$.		The additional code words are  $\rm 210, \,211, \,212, \,220, \,221, \,222$.

Maintenance script: Add German interlanguage link

2026-03-16T12:30:43Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 154:		Line 154:

	[[Category:Information Theory: Exercises\|^2.1 General Description^]]		[[Category:Information Theory: Exercises\|^2.1 General Description^]]
			[[de:Aufgaben:2.02_Kraftsche_Ungleichung]]

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"

← Older revision		Revision as of 14:07, 16 August 2021
Line 6:		Line 6:
	In the figure some exemplary binary and ternary codes are given.		In the figure some exemplary binary and ternary codes are given.

	*With the binary code  $\rm B1$  all possible source symbols  $q_\mu$  $($with index  $\mu = 1$, ... , $8)$  are represented by a ~~code symbol~~ sequence  $\langle c_\mu \rangle $  of uniform length  $L_\mu = 3$ .		*With the binary code  $\rm B1$  all possible source symbols  $q_\mu$  $($with index  $\mu = 1$, ... , $8)$  are represented by a encoded sequence  $\langle c_\mu \rangle $  of uniform length  $L_\mu = 3$ .
	*This code is unsuitable for data compression for this reason.		*This code is unsuitable for data compression for this reason.

Guenter at 12:08, 10 August 2021

2021-08-10T12:08:45Z

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

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

Noah at 20:29, 6 August 2021

2021-08-06T20:29:38Z

← Older revision		Revision as of 22: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]].

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

← Older revision		Revision as of 22:53, 29 June 2021
Line 91:		Line 91:
	</quiz>		</quiz>

	===~~Musterlösung~~===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  ~~Richtig sind die~~ <u>~~Lösungsvorschläge~~ 1, 2 ~~und~~ 3.</u>  ~~Für die angegebenen Binärcodes gilt~~:		'''(1)'''  The correct <u>solutions are 1, 2 and 3.</u>  The following applies to the binary codes given:
	* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   ~~Bedingung erfüllt~~,		* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   condition fulfilled,
	* $\rm B2$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   ~~Bedingung erfüllt~~,		* $\rm B2$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition met,
	* $\rm B3$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   ~~Bedingung erfüllt~~,		* $\rm B3$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition met,
	* $\rm B4$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3} + 1 \cdot 2^{-4}= 17/16$   ⇒   ~~Bedingung~~ <u>~~nicht~~</u> ~~erfüllt~~.		* $\rm B4$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3} + 1 \cdot 2^{-4}= 17/16$   ⇒   condition <u>not</u> met.



	'''(2)'''  ~~Richtig sind die~~ <u>~~Lösungsvorschläge~~ 1 ~~und~~ 2:</u>		'''(2)'''  <u>Proposed solutions 1 and 2</u> are correct:
	*~~Der Code~~  $\rm B4$, ~~der die Kraftsche Ungleichung nicht erfüllt~~, ~~ist mit Sicherheit auch nicht präfixfrei~~.		*The code  $\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~~  $\rm B3$  ~~ist~~ "10" ~~der Beginn des Codewortes~~ "1011".		*In code  $\rm B3$  "10" is the beginning of the code word "1011".
	*~~Dagegen sind die Codes~~  $\rm B1$  ~~und~~  $\rm B2$  ~~tatsächlich präfixfrei~~.		*In contrast, codes  $\rm B1$  and  $\rm B2$  are actually prefix-free.



	'''(3)'''  ~~Richtig sind die~~ <u>~~Antworten~~ 1 ~~und~~ 3</u>:		'''(3)'''  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~~  $\rm T1$  ~~und~~  $\rm T3$  ~~tatsächlich präfixfrei~~.		*As can be seen from the table, codes  $\rm T1$  and  $\rm T3$  are indeed prefix-free.
	*~~Der Code~~  $\rm T2$  ~~ist dagegen nicht präfixfrei~~, da "1" ~~der Beginn des Codewortes~~ "10" ~~ist~~.		*The code  $\rm T2$ , on the other hand, is not prefix-free because "1" is the beginning of the codeword "10".



	'''(4)'''  $N_i$  ~~gibt an, wieviele Codeworte mit~~  $i$  ~~Symbolen es im Code gibt~~.  ~~Für den Code~~  $\rm T1$  ~~gilt~~:		'''(4)'''  $N_i$  indicates how many codewords with  $i$  symbols there are in the code.  For the code  $\rm T1$  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}.$$		:$$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)'''  ~~Nach der Kraftschen Ungleichung muss gelten~~		'''(5)'''  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}.$$		:$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$
	~~Bei gegebenem~~  $N_1 = 1$  ~~und~~  $N_2 = 2$  ~~wird dies erfüllt~~, ~~solange gilt~~:		For given  $N_1 = 1$  and  $N_2 = 2$  , 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		:$$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}.$$		\hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
	~~Die zusätzlichen Codeworte sind~~  $\rm 210, \,211, \,212, \,220, \,221, \,222$.		The additional code words are  $\rm 210, \,211, \,212, \,220, \,221, \,222$.



	'''(6)'''  ~~Für den Code~~  $\rm T3$  ~~gilt~~:		'''(6)'''  For code  $\rm T3$  it is:
	*$S({\rm T3})= 2 \cdot 3^{-1} +  2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$		*$S({\rm T3})= 2 \cdot 3^{-1} +  2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
	*~~Wegen~~  $S({\rm T3}) \le 1$  ~~erfüllt der Ternärcode~~  $\rm T3$  ~~die Kraftsche Ungleichung und er ist zudem auch präfixfrei~~.		*Because of  $S({\rm T3}) \le 1$  the ternary code  $\rm T3$  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)$:		* 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)$:		* 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)$:		* 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~~  $N = 9$  ~~Codeworte des präfixfreien Codes~~  $\rm T6$:		For example, the total  $N = 9$  codewords of the prefix-free code are  $\rm T6$:
	:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$		:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
	{{ML-Fuß}}		{{ML-Fuß}}

← Older revision		Revision as of 16:52, 1 November 2022
Line 16:		Line 16:

	For example, the binary code  $\rm B2$  has this property:		For example, the binary code  $\rm B2$  has this property:
	*Here, one ~~codeword~~ each has the length   $1$,  $2$  and  $3$, respectively  $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.		*Here, one code word each has the length   $1$,  $2$  and  $3$, respectively  $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
	*Two code words have the length  $L_\mu = 4$  $(N_4 = N_5 = 4)$.		*Two code words have the length  $L_\mu = 4$  $(N_4 = N_5 = 4)$.


	A prerequisite for the decodability of such a code is that the code is  '''prefix-free''' .		A prerequisite for the decodability of such a code is that the code is  '''prefix-free''' .
	*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  '''Kraft's inequality''':		*A necessary condition for a code for data compression to be prefix-free was stated by Leon Kraft in 1949, called  '''Kraft's inequality''':
Line 28:		Line 28:
	Here denote		Here denote
	* $M$  the number of possible source symbols  $q_\mu$   ⇒   "symbol set size",		* $M$  the number of possible source symbols  $q_\mu$   ⇒   "symbol set size",
	* $L_\mu$  the length of the ~~codeword~~  $c_\mu$  associated with the source symbol  $q_\mu$,		* $L_\mu$  the length of the code word  $c_\mu$  associated with the source symbol  $q_\mu$,
	* $D = 2$  denotes a binary code  $(\rm 0$  or  $\rm 1)$  and  $D = 3$  denotes a ternary code  $(\rm 0$,  $\rm 1$,  $\rm 2)$.		* $D = 2$  denotes a binary code  $(\rm 0$  or  $\rm 1)$  and  $D = 3$  denotes a ternary code  $(\rm 0$,  $\rm 1$,  $\rm 2)$.

Line 78:		Line 78:


	{How many trivalent ~~codewords~~  $(L_\mu = 3)$  could be added to the  $\rm T1$  code without changing the prefix freedom?		{How many trivalent code words  $(L_\mu = 3)$  could be added to the  $\rm T1$  code without changing the prefix freedom?
	\|type="{}"}		\|type="{}"}
	$\Delta N_3 \ = \ $ { 6 }		$\Delta N_3 \ = \ $ { 6 }


	{The ternary code  $\rm T3$  is to be expanded to a total of  $N = 9$  ~~codewords~~.  How to achieve this without violating the prefix freedom?		{The ternary code  $\rm T3$  is to be expanded to a total of  $N = 9$  code words.  How to achieve this without violating the prefix freedom?
	\|type="[]"}		\|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  $\rm B4$, which does not satisfy Kraft's inequality, is certainly not prefix-free either.		*The code  $\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.		*But if Kraft's inequality is fulfilled, it is still not certain that this code is also prefix-free.
	*In code  $\rm B3$  the ~~codeword~~  "10"  is the beginning of the ~~codeword~~  "1011".		*In code  $\rm B3$  the code word  "10"  is the beginning of the code word  "1011".
	*In contrast, codes  $\rm B1$  and  $\rm B2$  are actually prefix-free.		*In contrast, codes  $\rm B1$  and  $\rm B2$  are actually prefix-free.

Line 114:		Line 114:
	*Kraft's inequality is satisfied by all three codes.		*Kraft's inequality is satisfied by all three codes.
	*As can be seen from the table, codes  $\rm T1$  and  $\rm T3$  are indeed prefix-free.		*As can be seen from the table, codes  $\rm T1$  and  $\rm T3$  are indeed prefix-free.
	*The code  $\rm T2$ , on the other hand, is not prefix-free because "1" is the beginning of the ~~codeword~~ "10".		*The code  $\rm T2$ , on the other hand, is not prefix-free because "1" is the beginning of the code word "10".



	'''(4)'''  $N_i$  indicates how many ~~codewords~~ with  $i$  symbols there are in the code.  For the code  $\rm T1$  it is:		'''(4)'''  $N_i$  indicates how many code words with  $i$  symbols there are in the code.  For the code  $\rm T1$  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}.$$		:$$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.		Thus, <u>the two last proposed solutions</u> are correct.

	For example, the total  $N = 9$  ~~codewords~~ of the prefix-free code  $\rm T6$  are:		For example, the total  $N = 9$  code words of the prefix-free code  $\rm T6$  are:
	:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$		:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
	{{ML-Fuß}}		{{ML-Fuß}}

← Older revision		Revision as of 16:39, 7 July 2021
Line 97:		Line 97:
	'''(1)'''  The correct <u>solutions are 1, 2 and 3.</u>  The following applies to the binary codes given:		'''(1)'''  The correct <u>solutions are 1, 2 and 3.</u>  The following applies to the binary codes given:
	* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   condition fulfilled,		* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   condition fulfilled,
	* $\rm B2$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition ~~met~~,		* $\rm B2$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition fulfilled,
	* $\rm B3$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition ~~met~~,		* $\rm B3$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   condition fulfilled,
	* $\rm B4$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3} + 1 \cdot 2^{-4}= 17/16$   ⇒   condition <u>not</u> ~~met~~.		* $\rm B4$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3} + 1 \cdot 2^{-4}= 17/16$   ⇒   condition <u>not</u> fulfilled.


Line 106:		Line 106:
	*The code  $\rm B4$, which does not satisfy Kraft's inequality, is certainly not prefix-free either.		*The code  $\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.		*But if Kraft's inequality is fulfilled, it is still not certain that this code is also prefix-free.
	*In code  $\rm B3$  "10" is the beginning of the ~~code word~~ "1011".		*In code  $\rm B3$  the codeword  "10"  is the beginning of the codeword  "1011".
	*In contrast, codes  $\rm B1$  and  $\rm B2$  are actually prefix-free.		*In contrast, codes  $\rm B1$  and  $\rm B2$  are actually prefix-free.

Line 132:		Line 132:


	'''(6)'''  For code  $\rm T3$  it is:		'''(6)'''  For code  $\rm T3$  it holds:
	*$S({\rm T3})= 2 \cdot 3^{-1} +  2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$		*$S({\rm T3})= 2 \cdot 3^{-1} +  2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
	*Because of  $S({\rm T3}) \le 1$  the ternary code  $\rm T3$  satisfies Kraft's inequality and it is also prefix-free.		*Because of  $S({\rm T3}) \le 1$  the ternary code  $\rm T3$  satisfies Kraft's inequality and it is also prefix-free.
Line 139:		Line 139:
	Let us now consider the proposed new codes.		Let us now consider the proposed new codes.
	* Code $\rm T4$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 5)$:		* 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)$:		* 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},$$		:$$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}.$$		:$$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.		Thus, <u>the two last proposed solutions</u> are correct.
	For example, the total  $N = 9$  codewords of the prefix-free code ~~are~~  $\rm T6$:
			For example, the total  $N = 9$  codewords of the prefix-free code  $\rm T6$  are:
	:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$		:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
	{{ML-Fuß}}		{{ML-Fuß}}

← Older revision		Revision as of 16:28, 7 July 2021
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 the figure some exemplary binary and ternary codes are given.

	*In binary code  $\rm B1$  all possible source symbols  $q_\mu$  $($with ~~run~~ index  $\mu = 1$, ... , $8)$  are ~~each~~ represented by a code symbol sequence  $\langle c_\mu \rangle $  of uniform length  $L_\mu = 3$ .		*With the binary code  $\rm B1$  all possible source symbols  $q_\mu$  $($with index  $\mu = 1$, ... , $8)$  are represented by a code symbol sequence  $\langle c_\mu \rangle $  of uniform length  $L_\mu = 3$ .
	*This code is unsuitable for data compression for this reason.		*This code is unsuitable for data compression for this reason.


	The possibility of data compression arises only when		The possibility of data compression arises only when
	* the  $M$  ~~Quellensymbole nicht gleichwahrscheinlich~~, ~~und~~		*the  $M$  source symbols are not equally likely, and
	*~~die Länge~~  $L_\mu$  ~~der Codeworte unterschiedlich sind~~.		*the length  $L_\mu$  of the code words are different.


	For example, the binary code  $\rm B2$  has this property:		For example, the binary code  $\rm B2$  has this property:
	*Here, one codeword each has the length   $1$,  $2$  and  $3$, respectively  $(N_1 = N_2 = N_3 = 1)$.		*Here, one codeword each has the length   $1$,  $2$  and  $3$, respectively  $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
	*Two code words have the length  $L_\mu = 4$  $(N_4 = N_5 = 2)$.		*Two code words have the length  $L_\mu = 4$  $(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.		*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  '''Kraft's inequality''':		*A necessary condition for a code for data compression to be prefix-free was stated by Leon Kraft in 1949, called  '''Kraft's inequality''':
	:$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu}} \le 1 \hspace{0.05cm}.$$		:$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu}} \le 1 \hspace{0.05cm}.$$

	Here denote		Here denote
	* $M$  the number of possible source symbols  $q_\mu$,		* $M$  the number of possible source symbols  $q_\mu$   ⇒   "symbol set size",
	* $L_\mu$  the length of the codeword  $q_\mu$  associated with the source symbol  $c_\mu$,		* $L_\mu$  the length of the codeword  $c_\mu$  associated with the source symbol  $q_\mu$,
	* $D = 2$  denotes a binary code  $(\rm 0$ or  $\rm 1)$  and  $D = 3$  denotes a ternary code  $(\rm 0$,  $\rm 1$,  $\rm 2)$.		* $D = 2$  denotes a binary code  $(\rm 0$  or  $\rm 1)$  and  $D = 3$  denotes a ternary code  $(\rm 0$,  $\rm 1$,  $\rm 2)$.


	A code can be prefix-free only if Kraft's inequality is satisfied.  The converse does not hold:   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.

			The converse does not hold:   If Kraft's inequality is satisfied, it does not mean that this code is actually prefix-free.


Line 38:		Line 40:

	''Hint:''		''Hint:''
	*The ~~task~~ 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]].