Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:35:29Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:35 Uhr
Zeile 151:		Zeile 151:

	[[Category:Aufgaben zu Informationstheorie\|^2.1 Allgemeine Beschreibung^]]		[[Category:Aufgaben zu Informationstheorie\|^2.1 Allgemeine Beschreibung^]]
			[[en:Aufgaben:Exercise_2.2:_Kraft–McMillan_Inequality]]

Maintenance script: Join multi-line formulas for MW 1.43 parser compat

2026-02-24T13:38:46Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:38 Uhr
Zeile 125:		Zeile 125:
	:$$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:		Bei gegebenem  $N_1 = 1$  und  $N_2 = 2$  wird dies erfüllt, solange gilt:
	:$$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$.		Die zusätzlichen Codeworte sind  $\rm 210, \,211, \,212, \,220, \,221, \,222$.

Guenter am 7. Juli 2021 um 14:18 Uhr

2021-07-07T14:18:20Z

← Nächstältere Version		Version vom 7. Juli 2021, 16:18 Uhr
Zeile 16:		Zeile 16:

	Diese Eigenschaft weist zum Beispiel der Binärcode  $\rm B2$  auf:		Diese Eigenschaft weist zum Beispiel der Binärcode  $\rm B2$  auf:
	*Je ein Codewort hat hier die Länge  $1$,  $2$  bzw.  $3$  $(N_1 = N_2 = N_3 = 1)$.		*Je ein Codewort hat hier die Länge  $1$,  $2$  bzw.  $3$  $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
	*Zwei Codeworte haben die Länge  $L_\mu = 4$  $(N_4 = N_5 = 2)$.		*Zwei Codeworte haben die Länge  $L_\mu = 4$  $(N_4 = N_5 = 4)$.

Guenter am 7. Juli 2021 um 14:02 Uhr

2021-07-07T14:02:16Z

← Nächstältere Version		Version vom 7. Juli 2021, 16:02 Uhr
Zeile 27:		Zeile 27:

	Hierbei bezeichnen		Hierbei bezeichnen
	* $M$  die Anzahl der möglichen Quellensymbole  $q_\mu$,		* $M$  die Anzahl der möglichen Quellensymbole  $q_\mu$   ⇒   &bdquo;Symbolumfang”,
	* $L_\mu$  die Länge des zum Quellensymbol  $q_\mu$  gehörigen Codewortes  $c_\mu$,		* $L_\mu$  die Länge des zum Quellensymbol  $q_\mu$  gehörigen Codewortes  $c_\mu$,
	* $D = 2$  kennzeichnet einen Binärcode  $(\rm 0$ oder  $\rm 1)$  und  $D = 3$  einen Ternärcode  $(\rm 0$,  $\rm 1$,  $\rm 2)$.		* $D = 2$  kennzeichnet einen Binärcode  $(\rm 0$ oder  $\rm 1)$  und  $D = 3$  einen Ternärcode  $(\rm 0$,  $\rm 1$,  $\rm 2)$.


	Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist.  Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.		Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist.  <br>Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.

Guenter am 21. Januar 2020 um 17:16 Uhr

2020-01-21T17:16:05Z

Guenter am 21. Januar 2020 um 17:08 Uhr

2020-01-21T17:08:38Z

← Nächstältere Version		Version vom 21. Januar 2020, 19:08 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID2416__Inf_A_2_2.png\|right\|frame\|~~Beispielhafte Binär–~~ und Ternärcodes]]		[[Datei:P_ID2416__Inf_A_2_2.png\|right\|frame\|Vier Beispiele für Binärcodes und dazu drei Ternärcodes]]
	In der Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.		In der Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.

	Beim Binärcode $\rm B1$ werden alle möglichen Quellensymbole $q_\mu$ (mit Laufindex $\mu = 1$, ... , $8$) durch jeweils eine Codesymbolfolge $\langle c_\mu \rangle $ einheitlicher Länge $L_\mu = 3$ dargestellt. Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.		*Beim Binärcode  $\rm B1$  werden alle möglichen Quellensymbole  $q_\mu$  $($mit Laufindex  $\mu = 1$, ... , $8)$  durch jeweils eine Codesymbolfolge  $\langle c_\mu \rangle $  einheitlicher Länge  $L_\mu = 3$  dargestellt.
			*Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.


	Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn		Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn
	* die $M$ Quellensymbole nicht gleichwahrscheinlich ~~sind~~, und		* die  $M$  Quellensymbole nicht gleichwahrscheinlich, und
	*die Länge $L_\mu$ der Codeworte unterschiedlich sind.		*die Länge  $L_\mu$  der Codeworte unterschiedlich sind.


	Diese Eigenschaft weist zum Beispiel der Binärcode $\rm B2$ auf:		Diese Eigenschaft weist zum Beispiel der Binärcode  $\rm B2$  auf:
	*Je ein Codewort hat hier die Länge $1$, $2$ bzw. $3$ ($N_1 = N_2 = N_3 = 1$).		*Je ein Codewort hat hier die Länge  $1$,  $2$  bzw.  $3$  $(N_1 = N_2 = N_3 = 1)$.
	*Zwei Codeworte haben die Länge $L_\mu = 4$ ($N_4 = N_5 = 2$).		*Zwei Codeworte haben die Länge  $L_\mu = 4$  $(N_4 = N_5 = 2)$.


	Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code '''präfixfrei''' ist. Das heißt, dass kein Codewort der Präfix (also der Beginn) eines längeren Codewortes sein darf.		Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code  '''präfixfrei'''  ist.
			*Das heißt, dass kein Codewort der Präfix (also der Beginn) eines längeren Codewortes sein darf.

	Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte '''Kraftsche Ungleichung''':		*Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte  '''Kraftsche Ungleichung''':
	:$$\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}.$$

	Hierbei bezeichnen		Hierbei bezeichnen
	* $M$ die Anzahl der möglichen Quellensymbole $q_\mu$,		* $M$  die Anzahl der möglichen Quellensymbole  $q_\mu$,
	* $L_\mu$ die Länge des zum Quellensymbol $q_\mu$ gehörigen Codewortes $c_\mu$,		* $L_\mu$  die Länge des zum Quellensymbol  $q_\mu$  gehörigen Codewortes  $c_\mu$,
	* $D = 2$ kennzeichnet einen Binärcode ($\rm 0$ oder $\rm 10$) und $D = 32$ einen Ternärcode ($\rm 0$, $\rm 1$, $\rm 2$).		* $D = 2$  kennzeichnet einen Binärcode  $(\rm 0$ oder  $\rm 1)$  und  $D = 3$  einen Ternärcode  $(\rm 0$,  $\rm 1$,  $\rm 2)$.


			Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist.  Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.



	Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist. Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.


	''Hinweis:''		''Hinweis:''
	*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].		*Die Aufgabe gehört zum Kapitel  [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].


Zeile 63:		Zeile 69:


	{Wie lauten die Kenngrößen des Ternärecodes $\rm T1$?		{Wie lauten die Kenngrößen des Ternärecodes  $\rm T1$?
	\|type="{}"}		\|type="{}"}
	$ N_1 \ = \ $ { 1 }		$ N_1 \ = \ $ { 1 }
Zeile 71:		Zeile 77:


	{Wieviel 3&~~ndash~~;~~wertige Codeworte~~ $(L_\mu = 3)$ könnte man dem Code $\rm T1$ hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?		{Wieviel dreiwertige Codeworte  $(L_\mu = 3)$  könnte man dem Code  $\rm T1$  hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?
	\|type="{}"}		\|type="{}"}
	$\Delta N_3 \ = \ $ { 6 }		$\Delta N_3 \ = \ $ { 6 }


	{Der Ternärcode $\rm T3$ soll auf insgesamt $N = 9$ Codeworte erweitert werden. ~~<br>~~Wie erreicht man das ohne Verletzung der Präfixfreiheit?		{Der Ternärcode  $\rm T3$  soll auf insgesamt  $N = 9$  Codeworte erweitert werden.  Wie erreicht man das ohne Verletzung der Präfixfreiheit?
	\|type="[]"}		\|type="[]"}
	- Ergänzung um vier ~~3–wertige~~ Codeworte.		- Ergänzung um vier dreiwertige Codeworte.
	+ Ergänzung um vier ~~4–wertige~~ Codeworte.		+ Ergänzung um vier vierwertige Codeworte.
	+ Ergänzung um ein ~~3–wertiges~~ und drei ~~4–wertige~~ Codeworte.		+ Ergänzung um ein dreiwertiges und drei vierwertige Codeworte.

Guenter am 23. September 2018 um 13:36 Uhr

2018-09-23T13:36:52Z

Guenter am 23. September 2018 um 13:21 Uhr

2018-09-23T13:21:40Z

← Nächstältere Version		Version vom 23. September 2018, 15:21 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID2416__Inf_A_2_2.png\|right\|Beispielhafte Binär– und Ternärcodes]]		[[Datei:P_ID2416__Inf_A_2_2.png\|right\|frame\|Beispielhafte Binär– und Ternärcodes]]
	In der ~~rechten~~ Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.		In der Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.

	Beim Binärcode ~~'''~~B1~~'''~~ werden alle möglichen Quellensymbole $q_\mu$ (mit Laufindex $\mu = 1$, ... , $8$) durch jeweils eine Codesymbolfolge $\langle q_\mu \rangle $ einheitlicher Länge $L_\mu = 3$ dargestellt. Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.		Beim Binärcode $\rm B1$ werden alle möglichen Quellensymbole $q_\mu$ (mit Laufindex $\mu = 1$, ... , $8$) durch jeweils eine Codesymbolfolge $\langle c_\mu \rangle $ einheitlicher Länge $L_\mu = 3$ dargestellt. Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.

	Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn		Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn
Zeile 13:		Zeile 13:


	Diese Eigenschaft weist zum Beispiel der Binärcode ~~'''~~B2~~'''~~ auf: Je ein Codewort hat hier die Länge $1$, $2$ bzw. $3$ ($N_1 = N_2 = N_3 = 1$) ~~und zwei~~ Codeworte haben die Länge $L_\mu = 4$ ($N_4 = N_5 = 2$).		Diese Eigenschaft weist zum Beispiel der Binärcode $\rm B2$ auf:
			*Je ein Codewort hat hier die Länge $1$, $2$ bzw. $3$ ($N_1 = N_2 = N_3 = 1$).
			*Zwei Codeworte haben die Länge $L_\mu = 4$ ($N_4 = N_5 = 2$).

	~~Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code '''präfixfrei''' ist. Das heißt, dass kein Codewort der Präfix (der Beginn) eines längeren Codewortes sein darf.~~

	Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte Kraftsche Ungleichung:		Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code '''präfixfrei''' ist. Das heißt, dass kein Codewort der Präfix (also der Beginn) eines längeren Codewortes sein darf.

			Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte '''Kraftsche Ungleichung''':
	:$$\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}.$$

	Hierbei bezeichnen		Hierbei bezeichnen
	* $M$ die Anzahl der möglichen Quellensymbole $q_\mu$,		* $M$ die Anzahl der möglichen Quellensymbole $q_\mu$,
	* $L_\mu$ die Länge des zum Quellensymbol $L_\mu$ gehörigen Codewortes $c_\mu$,		* $L_\mu$ die Länge des zum Quellensymbol $q_\mu$ gehörigen Codewortes $c_\mu$,
	* $D = 2$ einen Binärcode ($\rm 0$ oder $\rm 10$) und $D = 32$ einen Ternärcode ($\rm 0$, $\rm 1$, $\rm 2$).		* $D = 2$ kennzeichnet einen Binärcode ($\rm 0$ oder $\rm 10$) und $D = 32$ einen Ternärcode ($\rm 0$, $\rm 1$, $\rm 2$).


	Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist. Die Umkehrung gilt nicht: Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.		Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist. Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.


	''~~Hinweise~~:''		''Hinweis:''
	*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].		*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].

Zeile 39:		Zeile 42:
	{Welche der Binärcodes erfüllen die Kraftsche Ungleichung?		{Welche der Binärcodes erfüllen die Kraftsche Ungleichung?
	\|type="[]"}		\|type="[]"}
	+ B1,		+ $\rm B1$,
	+ B2,		+ $\rm B2$,
	+ B3,		+ $\rm B3$,
	- B4.		- $\rm B4$.


	{Welche der vorgegebenen Binärcodes sind präfixfrei?		{Welche der vorgegebenen Binärcodes sind präfixfrei?
	\|type="[]"}		\|type="[]"}
	+ B1,		+ $\rm B1$,
	+ B2,		+ $\rm B2$,
	- B3,		- $\rm B3$,
	- B4.		- $\rm B4$.


	{Welche der vorgegebenen Ternärcodes sind präfixfrei?		{Welche der vorgegebenen Ternärcodes sind präfixfrei?
	\|type="[]"}		\|type="[]"}
	+ T1,		+ $\rm T1$,
	- T2,		- $\rm T2$,
	+ T3.		+ $\rm T3$.


	{Wie lauten die Kenngrößen des Ternärecodes ~~'''~~T1~~'''~~?		{Wie lauten die Kenngrößen des Ternärecodes $\rm T1$?
	\|type="{}"}		\|type="{}"}
	$ N_1 \ = $ { 1 }		$ N_1 \ = \ $ { 1 }
	$ N_2 \ = $ { 2 }		$ N_2 \ = \ $ { 2 }
	$ N_3 \ = $ { 6 }		$ N_3 \ = \ $ { 6 }



	{Wieviel 3–wertige Codeworte ($L_\mu = 3$) könnte man dem Code ~~'''~~T1~~'''~~ hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?		{Wieviel 3–wertige Codeworte $(L_\mu = 3)$ könnte man dem Code $\rm T1$ hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?
	\|type="{}"}		\|type="{}"}
	$\Delta N_3 \ = $ { 6 }		$\Delta N_3 \ = \ $ { 6 }


	{Der Ternärcode ~~'''~~T3~~'''~~ soll auf insgesamt $N = 9$ Codeworte erweitert werden. Wie erreicht man das ohne Verletzung der Präfixfreiheit?		{Der Ternärcode $\rm T3$ soll auf insgesamt $N = 9$ Codeworte erweitert werden. <br>Wie erreicht man das ohne Verletzung der Präfixfreiheit?
	\|type="[]"}		\|type="[]"}
	- Ergänzung um vier 3–wertige Codeworte.		- Ergänzung um vier 3–wertige Codeworte.

Mwiki-lnt: Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

2018-05-29T12:02:42Z

Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

← Nächstältere Version		Version vom 29. Mai 2018, 14:02 Uhr
Zeile 31:		Zeile 31:
	''Hinweise:''		''Hinweise:''
	*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].		*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Allgemeine_Beschreibung\|Allgemeine Beschreibung der Quellencodierung]].
	*Sollte die Eingabe des Zahlenwertes &bdquo;0” erforderlich sein, so geben Sie bitte &bdquo;0.” ein.

Guenter: Guenter verschob die Seite Aufgaben:2.2 Kraftsche Ungleichung nach Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung

2018-01-03T13:57:00Z

Guenter verschob die Seite Aufgaben:2.2 Kraftsche Ungleichung nach Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung

← Nächstältere Version		Version vom 3. Januar 2018, 15:57 Uhr
(kein Unterschied)

← Nächstältere Version		Version vom 21. Januar 2020, 19:16 Uhr
Zeile 94:		Zeile 94:
	===Musterlösung===		===Musterlösung===
	{{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)'''  Richtig sind die <u>Lösungsvorschläge 1, 2 und 3.</u>  Für die angegebenen Binärcodes gilt:
	* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   Bedingung erfüllt,		* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   Bedingung erfüllt,
	* $\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$   ⇒   Bedingung erfüllt,
	* $\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$   ⇒   Bedingung erfüllt,
	* $\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$   ⇒   Bedingung <u>nicht</u> erfüllt.



	'''(2)'''  Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>		'''(2)'''  Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>
	*Der Code $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.		*Der Code  $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.
	*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.		*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.
	*Beim Code $\rm B3$ ist &bdquo;10” der Beginn des Codewortes &bdquo;1011”.		*Beim Code  $\rm B3$  ist &bdquo;10” der Beginn des Codewortes &bdquo;1011”.
	*Dagegen sind die Codes $\rm B1$ und $\rm B2$ tatsächlich präfixfrei.		*Dagegen sind die Codes  $\rm B1$  und  $\rm B2$  tatsächlich präfixfrei.



	'''(3)'''  Richtig sind die <u>Antworten 1 und 3</u>:		'''(3)'''  Richtig sind die <u>Antworten 1 und 3</u>:
	*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.		*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
	*Wie aus der Tabelle hervorgeht, sind die Codes $\rm T1$ und $\rm T3$ tatsächlich präfixfrei.		*Wie aus der Tabelle hervorgeht, sind die Codes  $\rm T1$  und  $\rm T3$  tatsächlich präfixfrei.
	*Der Code $\rm T2$ ist dagegen nicht präfixfrei, da &bdquo;1” der Beginn des Codewortes &bdquo;10” ist.		*Der Code  $\rm T2$  ist dagegen nicht präfixfrei, da &bdquo;1” der Beginn des Codewortes &bdquo;10” ist.


	'''(4)'''  $N_i$ gibt an, wieviele Codeworte mit $i$ Symbolen es im Code gibt. Für den Code $\rm T1$ gilt:
			'''(4)'''  $N_i$  gibt an, wieviele Codeworte mit  $i$  Symbolen es im Code gibt.  Für den Code  $\rm T1$  gilt:
	:$$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)'''  Nach der Kraftschen Ungleichung muss gelten
	:$$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:		Bei gegebenem  $N_1 = 1$  und  $N_2 = 2$  wird dies erfüllt, solange gilt:
	:$$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$.		Die zusätzlichen Codeworte sind  $\rm 210, \,211, \,212, \,220, \,221, \,222$.



	'''(6)'''  Für den Code $\rm T3$ gilt:		'''(6)'''  Für den Code  $\rm T3$  gilt:
	*$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.		*Wegen  $S({\rm T3}) \le 1$  erfüllt der Ternärcode  $\rm T3$  die Kraftsche Ungleichung und er ist zudem auch präfixfrei.


Zeile 140:		Zeile 145:

	Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.		Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.
	Beispielsweise lauten die insgesamt $N = 9$ Codeworte des präfixfreien Codes $\rm T6$:		Beispielsweise lauten die insgesamt  $N = 9$  Codeworte des präfixfreien Codes  $\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ß}}

← Nächstältere Version		Version vom 23. September 2018, 15:36 Uhr
Zeile 89:		Zeile 89:
	{{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)'''  Richtig sind die <u>Lösungsvorschläge 1, 2 und 3.</u> Für die angegebenen Binärcodes gilt:
	* B1:    $8 \cdot 2^{-3} = 1$   ⇒   Bedingung erfüllt,		* $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   Bedingung erfüllt,
	* 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$   ⇒   Bedingung erfüllt,
	* 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$   ⇒   Bedingung erfüllt,
	* 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$   ⇒   Bedingung <u>nicht</u> erfüllt.


	'''(2)'''  Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>		'''(2)'''  Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>
	*Der Code B4, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.		*Der Code $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.
	*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.		*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.
	*Beim Code B3 ist &bdquo;10” der Beginn des Codewortes &bdquo;1011”.		*Beim Code $\rm B3$ ist &bdquo;10” der Beginn des Codewortes &bdquo;1011”.
	*Dagegen sind die Codes B1 und B2 tatsächlich präfixfrei.		*Dagegen sind die Codes $\rm B1$ und $\rm B2$ tatsächlich präfixfrei.


	'''(3)'''  Richtig sind die <u>Antworten 1 und 3</u>:		'''(3)'''  Richtig sind die <u>Antworten 1 und 3</u>:
	*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.		*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
	*Wie aus der Tabelle hervorgeht, sind die Codes T1 und T3 tatsächlich präfixfrei.		*Wie aus der Tabelle hervorgeht, sind die Codes $\rm T1$ und $\rm T3$ tatsächlich präfixfrei.
	*Der Code T2 ist dagegen nicht präfixfrei, da &bdquo;1” der Beginn des Codewortes &bdquo;10” ist.		*Der Code $\rm T2$ ist dagegen nicht präfixfrei, da &bdquo;1” der Beginn des Codewortes &bdquo;10” ist.


	'''(4)'''  $N_i$ gibt an, wieviele Codeworte mit $i$ Symbolen es im Code gibt. Für den Code T1 gilt:		'''(4)'''  $N_i$ gibt an, wieviele Codeworte mit $i$ Symbolen es im Code gibt. Für den Code $\rm T1$ gilt:
	:$$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}.$$

Zeile 120:		Zeile 120:


	'''(6)'''  Für den Code T3 gilt: $S({\rm T3})= 2 \cdot 3^{-1} + 2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$		'''(6)'''  Für den Code $\rm T3$ gilt:
	Wegen $S(T3) \le 1$ erfüllt der Ternärcode T3 die Kraftsche Ungleichung und er ist zudem auch präfixfrei. Betrachten wir nun die vorgeschlagenen neuen Codes.		*$S({\rm T3})= 2 \cdot 3^{-1} + 2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
	* Code T4 ($N_1 = 2, N_2 = 2, N_3 = 5$:		*Wegen $S({\rm T3}) \le 1$ erfüllt der Ternärcode $\rm T3$ die Kraftsche Ungleichung und er ist zudem auch präfixfrei.


			Betrachten wir nun die vorgeschlagenen neuen 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}ist\hspace{0.15cm} ungeeignet}\hspace{0.05cm},$$
	* Code 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}ist\hspace{0.15cm} geeignet}\hspace{0.05cm},$$
	* Code 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}ist\hspace{0.15cm} geeignet}\hspace{0.05cm}.$$

	Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.		Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.
	Beispielsweise lauten die insgesamt $N = 9$ Codeworte des präfixfreien Codes T6:		Beispielsweise lauten die insgesamt $N = 9$ Codeworte des präfixfreien Codes $\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ß}}