Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei BDD - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:35:21Z

Add English interlanguage link

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

	[[Category:Aufgaben zu Kanalcodierung\|^2.6 RSC–Fehlerwahrscheinlichkeit^]]		[[Category:Aufgaben zu Kanalcodierung\|^2.6 RSC–Fehlerwahrscheinlichkeit^]]
			[[en:Aufgaben:Exercise_2.16:_Bounded_Distance_Decoding:_Decision_Regions]]

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

2026-02-24T13:38:42Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:38 Uhr
Zeile 82:		Zeile 82:

	*Wäre dieser Code perfekt,  so müsste es also innerhalb jeder Kugel  $8^4 = 4096$  Punkte geben.  Es gilt aber:		*Wäre dieser Code perfekt,  so müsste es also innerhalb jeder Kugel  $8^4 = 4096$  Punkte geben.  Es gilt aber:
	:$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)}		:$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)} = {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079 \hspace{0.05cm}.$$
	= {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079
	\hspace{0.05cm}.$$

	*Für  ${\rm Pr}(f = 1)$  ist berücksichtigt,  dass es  "$7 \rm \ über \ 1$"  $= 7$  Fehlerpositionen geben kann,  und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte.  Entsprechendes ist auch für  ${\rm Pr}(f = 2)$  berücksichtigt.		*Für  ${\rm Pr}(f = 1)$  ist berücksichtigt,  dass es  "$7 \rm \ über \ 1$"  $= 7$  Fehlerpositionen geben kann,  und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte.  Entsprechendes ist auch für  ${\rm Pr}(f = 2)$  berücksichtigt.
Zeile 95:		Zeile 93:
	*Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:		*Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:

	:$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)}		:$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)} = {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}\hspace{0.05cm}.$$
	= {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}
	\hspace{0.05cm}.$$
	*Für den  ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$  liefert diese obere Schranke den Wert  $1/(16!) < 10^{-14}$.		*Für den  ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$  liefert diese obere Schranke den Wert  $1/(16!) < 10^{-14}$.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 2. November 2022 um 16:27 Uhr

2022-11-02T16:27:49Z

← Nächstältere Version		Version vom 2. November 2022, 18:27 Uhr
Zeile 58:		Zeile 58:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Richtig ist der <u>Lösungsvorschlag 1</u>, da das Codierraumschema  $\rm A$  einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist:		'''(1)'''  Richtig ist der  <u>Lösungsvorschlag 1</u>,  da das Codierraumschema  $\rm A$  einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$  ein perfekter Code ist:
	*Bei einem jeden Hamming–Code $(n, \, k, \, 3)$ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden.		*Bei einem jeden Hamming–Code $(n, \, k, \, 3)$  gibt es insgesamt  $2^n$  mögliche Empfangsworte  $\underline{y}_i$,  die bei der Syndromdecodierung einem von  $2^k$  möglichen Codeworten  $\underline{c}_j$  zugeordnet werden.
	*Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel
			*Aufgrund der  HC–Eigenschaft $d_{\rm min} = 3$  haben alle Kugeln im  $n$–dimensionalen Raum den Radius  $t = 1$.  In allen Kugeln gibt es somit  $2^{n-k}$  Punkte,  zum Beispiel
	:* $\text{HC (7, 4, 3)}$:   einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.		:* $\text{HC (7, 4, 3)}$:   einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.
	:* $\text{HC (15, 11, 3)}$:   einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.		:* $\text{HC (15, 11, 3)}$:   einen Punkt für die fehlerfreie Übertragung und nun fünfzehn Punkte für einen Bitfehler   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.

	''Hinweis:''  Da der Hamming–Code ein Binärcode ist, hat hier der Coderaum die Dimension  $n$.		<u>Hinweis:</u>  Da der Hamming–Code ein Binärcode ist,  hat hier der Coderaum die Dimension  $n$.



	'''(2)'''  Richtig ist die <u>Antwort 1</u>:		'''(2)'''  Richtig ist die  <u>Antwort 1</u>:
	*Im grauen Bereich außerhalb von &bdquo;Kugeln” gibt es bei einem perfekten Code keinen einzigen Punkt.		*Im grauen Bereich außerhalb von &bdquo;Kugeln” gibt es bei einem perfekten Code keinen einzigen Punkt.
	*Dies wurde auch in der Rechnung zur Teilaufgabe (1) gezeigt.
			*Dies wurde auch in der Rechnung zur Teilaufgabe  '''(1)'''  gezeigt.



	'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema  $\rm B$  beschrieben  ⇒  <u>Antwort 2</u>.		'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema  $\rm B$  beschrieben  ⇒  <u>Antwort 2</u>.
	*Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei ~~<i>~~Bounded Distance Decoding~~</i> (BDD)~~ keiner Kugel zugeordnet werden können.		*Hier gibt es zahlreiche gelbe Punkte im grauen Bereich,  also Punkte die bei  "Bounded Distance Decoding"  keiner Kugel zugeordnet werden können.
	*Betrachten wir beispielweise den $\rm RSC \, (7, \, 3, \, 5)_8$ mit den Codeparametern $n = 7, \, k = 3$ und $t = 2$, so gibt es hier insgesamt $8^7 = 2097152$ Punkte und $8^3 = 512$ Hyperkugeln.
	*Wäre dieser Code perfekt, so müsste es also innerhalb jeder Kugel $8^4 = 4096$ Punkte geben. Es gilt aber:		*Betrachten wir beispielweise den  $\rm RSC \, (7, \, 3, \, 5)_8$  mit den Codeparametern  $n = 7, \, k = 3$ und $t = 2$,  so gibt es hier insgesamt  $8^7 = 2097152$  Punkte und  $8^3 = 512$  Hyperkugeln.

			*Wäre dieser Code perfekt,  so müsste es also innerhalb jeder Kugel  $8^4 = 4096$  Punkte geben.  Es gilt aber:
	:$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)}		:$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)}
	= {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079		= {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	*Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es &~~bdquo~~;$7 \rm \ über \ 1$&~~rdquo~~; $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.		*Für  ${\rm Pr}(f = 1)$  ist berücksichtigt,  dass es  "$7 \rm \ über \ 1$"  $= 7$  Fehlerpositionen geben kann,  und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte.  Entsprechendes ist auch für  ${\rm Pr}(f = 2)$  berücksichtigt.



	'''(4)'''  Richtig ist die <u>Antwort 3</u>:		'''(4)'''  Richtig ist die  <u>Antwort 3</u>:
	*Ein Punkt im grauen Niemandsland wird mit weniger Symbolfehlern erreicht als ein Punkt in einer anderen Hyperkugel.		*Ein Punkt im grauen Niemandsland wird mit weniger Symbolfehlern erreicht als ein Punkt in einer anderen Hyperkugel.

	*Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:		*Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:

Zeile 93:		Zeile 98:
	= {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}		= {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$
	*Für den ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$ liefert diese obere Schranke den Wert $1/(16!) < 10^{-14}$.		*Für den  ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$  liefert diese obere Schranke den Wert  $1/(16!) < 10^{-14}$.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 2. November 2022 um 14:55 Uhr

2022-11-02T14:55:13Z

← Nächstältere Version		Version vom 2. November 2022, 16:55 Uhr
Zeile 2:		Zeile 2:

	[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|Betrachtete Codierraumschemata]]		[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|Betrachtete Codierraumschemata]]
	Wir gehen von einem Blockcode der Länge  $n$  mit Symbolen  $c_i ∈ {\rm GF}(2^m)$  aus, der bis zu  $t$  Symbole korrigieren kann. Jedes mögliche Empfangswort  $\underline{y}_i$  kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden~~. Geht man von der Basis  ${\rm GF}(2) = \{0, \, 1\}$  aus, so beträgt die Dimension  $n \cdot m$~~.		Wir gehen von einem Blockcode der Länge  $n$  mit Symbolen  $c_i ∈ {\rm GF}(2^m)$  aus,  der bis zu  $t$  Symbole korrigieren kann.
			*Jedes mögliche Empfangswort   $\underline{y}_i$   kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden.

	~~Die Grafik zeigt einen solchen Raum in vereinfachender~~, ~~schematischer 2D~~&~~ndash~~;~~Darstellung~~.		*Geht man von der Basis  ${\rm GF}(2) = \{0, \, 1\}$  aus,  so beträgt die Dimension  $n \cdot m$.

	~~Die Abbildung ist wie folgt zu interpretieren:~~
	* Gesendet wurde der rote Punkt  $\underline{c}_j$. Alle rot umrandeten Punkte  $\underline{y}_i$  in einer Hyperkugel um diesen Punkt  $\underline{c}_j$  mit dem Parameter  $t$  als Radius können korrigiert werden. Mit der Nomenklatur gemäß der  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]]  im Theorieteil gilt dann  $\underline{z}_i = \underline{c}_j$   <br>⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.

	* Bei sehr vielen Symbolfehlern kann  $\underline{c}_j$  in einen blauen (oder weißblauen) Punkt  $\underline{y}_j$  verfälscht werden, der zur Hyperkugel eines anderen Codewortes  $\underline{c}_{k ≠ j}$  gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  wird falsch decodiert”.		Die Grafik zeigt einen solchen Raum in vereinfachender, schematischer zweidimensionaler Darstellung.  Die Abbildung ist wie folgt zu interpretieren:
			# Gesendet wurde der rote Punkt  $\underline{c}_j$.  Alle rot umrandeten Punkte  $\underline{y}_i$  in einer Hyperkugel um diesen Punkt  $\underline{c}_j$  mit dem Parameter  $t$  als Radius können korrigiert werden.  Mit der Nomenklatur gemäß der  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|$\rm Grafik$]]  im Theorieteil gilt  $\underline{z}_i = \underline{c}_j$   <br>⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.
			# Bei sehr vielen Symbolfehlern kann  $\underline{c}_j$  in einen blauen  $($oder weißblauen$)$  Punkt  $\underline{y}_j$  verfälscht werden,  der zur Hyperkugel eines anderen Codewortes  $\underline{c}_{k ≠ j}$  gehört.  In diesem Fall trifft der Decoder eine falsche Entscheidung   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  wird falsch decodiert”.
			# Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben,  die zu keiner Hyperkugel gehören   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  ist nicht decodierbar”.

	* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  ist nicht decodierbar”.

			In dieser Aufgabe sollen Sie entscheiden,  welches der beiden Coderaumschemata geeignet ist zur Beschreibung von
			* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|Bounded Distance Decoding von Hamming–Codes]] bzw.

	~~In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung von~~		* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Bounded Distance Decoding von Reed–Solomon–Codes]].
	* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|Bounded Distance Decoding  (BDD) von Hamming–Codes]] bzw.
	* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Bounded Distance Decoding ~~ (BDD)~~ von Reed–Solomon–Codes]].


Zeile 23:		Zeile 24:


			<u>Hinweise:</u>
			* Die Aufgabe ergänzt die Thematik des Kapitels  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|"Fehlerwahrscheinlichkeit und Anwendungsgebiete"]].


	~~''Hinweise:''~~
	* Die Aufgabe ergänzt die Thematik des Kapitels  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|Fehlerwahrscheinlichkeit und Anwendungsgebiete]].
	* Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.		* Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.

Zeile 38:		Zeile 38:
	- Codierraumschema  $\rm B$.		- Codierraumschema  $\rm B$.

	{Welche Aussage gilt für die Wahrscheinlichkeit, dass bei Hamming–Codierung ein Empfangswort  $\underline{y}$  nicht decodiert werden kann?		{Welche Aussage gilt für die Wahrscheinlichkeit,  dass bei Hamming–Codierung ein Empfangswort  $\underline{y}$  nicht decodiert werden kann?
	\|type="[]"}		\|type="[]"}
	+ Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist exakt Null.		+ Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \hspace{0.15cm}ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$  ist exakt Null.
	- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist ungleich Null, aber vernachlässigbar.		- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$  ist ungleich Null, aber vernachlässigbar.
	- Es gilt  ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.		- Es gilt  ${\rm Pr}(\underline{y} {\rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar}) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} wird \hspace{0.15cm} falsch \hspace{0.15cm} decodiert)$.

	{Welches Codierraumschema trifft für die Reed–Solomon–Codes zu?		{Welches Codierraumschema trifft für die Reed–Solomon–Codes zu?
Zeile 51:		Zeile 51:
	{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort  $\underline{y}$  nach Reed–Solomon–Codierung nicht decodiert werden kann?		{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort  $\underline{y}$  nach Reed–Solomon–Codierung nicht decodiert werden kann?
	\|type="[]"}		\|type="[]"}
	- Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist exakt Null.		- Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \hspace{0.15cm}ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$  ist exakt Null.
	- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist ungleich Null, aber vernachlässigbar.		- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$  ist ungleich Null, aber vernachlässigbar.
	+ Es gilt  ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.		+ Es gilt  ${\rm Pr}(\underline{y} {\rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar}) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} wird \hspace{0.15cm} falsch \hspace{0.15cm} decodiert)$.
	</quiz>		</quiz>

Guenter am 31. Mai 2019 um 11:32 Uhr

2019-05-31T11:32:48Z

← Nächstältere Version		Version vom 31. Mai 2019, 13:32 Uhr
Zeile 58:		Zeile 58:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Richtig ist der <u>Lösungsvorschlag 1</u>, da das Codierraumschema ~~<b>~~A~~</b>~~ einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist:		'''(1)'''  Richtig ist der <u>Lösungsvorschlag 1</u>, da das Codierraumschema  $\rm A$  einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist:
	*Bei einem jeden Hamming–Code $(n, \, k, \, 3)$ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden.		*Bei einem jeden Hamming–Code $(n, \, k, \, 3)$ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden.
	*Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel		*Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel
	:* ~~<b>~~HC (7, 4, 3)~~</b>~~: einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.		:* $\text{HC (7, 4, 3)}$:   einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.
	:* ~~<b>~~HC (15, 11, 3)~~</b>~~: einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.		:* $\text{HC (15, 11, 3)}$:   einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.

			''Hinweis:''  Da der Hamming–Code ein Binärcode ist, hat hier der Coderaum die Dimension  $n$.

	~~''Hinweis:'' Da der Hamming–Code ein Binärcode ist, hat hier der Coderaum die Dimension $n$.~~


Zeile 73:		Zeile 73:


	'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema ~~<b>~~B~~</b>~~ beschrieben  ⇒  <u>Antwort 2</u>.
			'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema  $\rm B$  beschrieben  ⇒  <u>Antwort 2</u>.
	*Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei <i>Bounded Distance Decoding</i> (BDD) keiner Kugel zugeordnet werden können.		*Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei <i>Bounded Distance Decoding</i> (BDD) keiner Kugel zugeordnet werden können.
	*Betrachten wir beispielweise den $\rm RSC \, (7, \, 3, \, 5)_8$ mit den Codeparametern $n = 7, \, k = 3$ und $t = 2$, so gibt es hier insgesamt $8^7 = 2097152$ Punkte und $8^3 = 512$ Hyperkugeln.		*Betrachten wir beispielweise den $\rm RSC \, (7, \, 3, \, 5)_8$ mit den Codeparametern $n = 7, \, k = 3$ und $t = 2$, so gibt es hier insgesamt $8^7 = 2097152$ Punkte und $8^3 = 512$ Hyperkugeln.
Zeile 81:		Zeile 82:
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	*Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es &bdquo;$7 \rm \ über \ 1$” $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch 7 unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.		*Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es &bdquo;$7 \rm \ über \ 1$” $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.

Guenter am 31. Mai 2019 um 11:23 Uhr

2019-05-31T11:23:18Z

← Nächstältere Version		Version vom 31. Mai 2019, 13:23 Uhr
Zeile 4:		Zeile 4:
	Wir gehen von einem Blockcode der Länge  $n$  mit Symbolen  $c_i ∈ {\rm GF}(2^m)$  aus, der bis zu  $t$  Symbole korrigieren kann. Jedes mögliche Empfangswort  $\underline{y}_i$  kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis  ${\rm GF}(2) = \{0, \, 1\}$  aus, so beträgt die Dimension  $n \cdot m$.		Wir gehen von einem Blockcode der Länge  $n$  mit Symbolen  $c_i ∈ {\rm GF}(2^m)$  aus, der bis zu  $t$  Symbole korrigieren kann. Jedes mögliche Empfangswort  $\underline{y}_i$  kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis  ${\rm GF}(2) = \{0, \, 1\}$  aus, so beträgt die Dimension  $n \cdot m$.

	Die Grafik zeigt einen solchen Raum in ~~stark~~ vereinfachender 2D–Darstellung. Die Abbildung ist wie folgt zu interpretieren:		Die Grafik zeigt einen solchen Raum in vereinfachender, schematischer 2D–Darstellung.

			Die Abbildung ist wie folgt zu interpretieren:
	* Gesendet wurde der rote Punkt  $\underline{c}_j$. Alle rot umrandeten Punkte  $\underline{y}_i$  in einer Hyperkugel um diesen Punkt  $\underline{c}_j$  mit dem Parameter  $t$  als Radius können korrigiert werden. Mit der Nomenklatur gemäß der  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]]  im Theorieteil gilt dann  $\underline{z}_i = \underline{c}_j$   <br>⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.		* Gesendet wurde der rote Punkt  $\underline{c}_j$. Alle rot umrandeten Punkte  $\underline{y}_i$  in einer Hyperkugel um diesen Punkt  $\underline{c}_j$  mit dem Parameter  $t$  als Radius können korrigiert werden. Mit der Nomenklatur gemäß der  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]]  im Theorieteil gilt dann  $\underline{z}_i = \underline{c}_j$   <br>⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.

Zeile 13:		Zeile 15:

	In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung von		In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung von
	* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|''Bounded Distance Decoding'' (BDD) von Hamming–Codes]] bzw.		* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|Bounded Distance Decoding  (BDD) von Hamming–Codes]] bzw.
	* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|''Bounded Distance Decoding'' (BDD) von Reed–Solomon–Codes]].		* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Bounded Distance Decoding  (BDD) von Reed–Solomon–Codes]].





Zeile 21:		Zeile 26:

	''Hinweise:''		''Hinweise:''
	* Die Aufgabe ergänzt die Thematik des Kapitels [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|Fehlerwahrscheinlichkeit und Anwendungsgebiete]].		* Die Aufgabe ergänzt die Thematik des Kapitels  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|Fehlerwahrscheinlichkeit und Anwendungsgebiete]].
	* Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.		* Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.

Zeile 30:		Zeile 35:
	{Welches Codierraumschema trifft für die Hamming–Codes zu?		{Welches Codierraumschema trifft für die Hamming–Codes zu?
	\|type="()"}		\|type="()"}
	+ Codierraumschema ~~<b>~~A~~</b>~~,		+ Codierraumschema  $\rm A$,
	- Codierraumschema ~~<b>~~B~~</b>~~.		- Codierraumschema  $\rm B$.

	{Welche Aussage gilt für die Wahrscheinlichkeit, dass bei Hamming–Codierung ein Empfangswort $\underline{y}$ nicht decodiert werden kann?		{Welche Aussage gilt für die Wahrscheinlichkeit, dass bei Hamming–Codierung ein Empfangswort  $\underline{y}$  nicht decodiert werden kann?
	\|type="[]"}		\|type="[]"}
	+ Die Wahrscheinlichkeit ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist exakt ~~$0$~~.		+ Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist exakt Null.
	- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist ungleich ~~$0$~~, aber vernachlässigbar.		- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist ungleich Null, aber vernachlässigbar.
	- Es gilt ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.		- Es gilt  ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.

	{Welches Codierraumschema trifft für die Reed–Solomon–Codes zu?		{Welches Codierraumschema trifft für die Reed–Solomon–Codes zu?
	\|type="()"}		\|type="()"}
	- Codierraumschema ~~<b>~~A~~</b>~~,		- Codierraumschema  $\rm A$,
	+ Codierraumschema ~~<b>~~B~~</b>~~.		+ Codierraumschema  $\rm B$.

	{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort $\underline{y}$ nach Reed–Solomon–Codierung nicht decodiert werden kann?		{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort  $\underline{y}$  nach Reed–Solomon–Codierung nicht decodiert werden kann?
	\|type="[]"}		\|type="[]"}
	- Die Wahrscheinlichkeit ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist exakt ~~$0$~~.		- Die Wahrscheinlichkeit  ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist exakt Null.
	- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist ungleich ~~$0$~~, aber vernachlässigbar.		- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$  ist ungleich Null, aber vernachlässigbar.
	+ Es gilt ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.		+ Es gilt  ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.
	</quiz>		</quiz>

Guenter am 30. Mai 2019 um 16:19 Uhr

2019-05-30T16:19:36Z

← Nächstältere Version		Version vom 30. Mai 2019, 18:19 Uhr
Zeile 1:		Zeile 1:
	{{quiz-Header\|Buchseite=Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete}}		{{quiz-Header\|Buchseite=Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete}}

	[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|~~Zwei unterschiedliche~~ Codierraumschemata]]		[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|Betrachtete Codierraumschemata]]
	Wir gehen von einem Blockcode der Länge $n$ mit Symbolen $c_i ∈ {\rm GF}(2^m)$ aus, der bis zu $t$ Symbole korrigieren kann. Jedes mögliche Empfangswort $\underline{y}_i$ kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis ${\rm GF}(2) = \{0, \, 1\}$ aus, so beträgt die Dimension $n \cdot m$.		Wir gehen von einem Blockcode der Länge  $n$  mit Symbolen  $c_i ∈ {\rm GF}(2^m)$  aus, der bis zu  $t$  Symbole korrigieren kann. Jedes mögliche Empfangswort  $\underline{y}_i$  kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis  ${\rm GF}(2) = \{0, \, 1\}$  aus, so beträgt die Dimension  $n \cdot m$.

	Die Grafik zeigt einen solchen Raum in stark vereinfachender 2D–Darstellung. Die Abbildung ist wie folgt zu interpretieren:		Die Grafik zeigt einen solchen Raum in stark vereinfachender 2D–Darstellung. Die Abbildung ist wie folgt zu interpretieren:
	* Gesendet wurde der rote Punkt $\underline{c}_j$. Alle rot umrandeten Punkte $\underline{y}_i$ in einer Hyperkugel um diesen Punkt $\underline{c}_j$ mit dem Parameter $t$ als Radius können korrigiert werden. Mit der Nomenklatur gemäß der [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]] im Theorieteil gilt dann $\underline{z}_i = \underline{c}_j$   ⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.		* Gesendet wurde der rote Punkt  $\underline{c}_j$. Alle rot umrandeten Punkte  $\underline{y}_i$  in einer Hyperkugel um diesen Punkt  $\underline{c}_j$  mit dem Parameter  $t$  als Radius können korrigiert werden. Mit der Nomenklatur gemäß der  [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]]  im Theorieteil gilt dann  $\underline{z}_i = \underline{c}_j$   <br>⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.

	* Bei sehr vielen Symbolfehlern kann $\underline{c}_j$ in einen blauen (oder weißblauen) Punkt $\underline{y}_j$ verfälscht werden, der zur Hyperkugel eines anderen Codewortes $\underline{c}_{k ≠ j}$ gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung   ⇒   &bdquo;Das Empfangswort $\underline{y}_j$ wird falsch decodiert”.		* Bei sehr vielen Symbolfehlern kann  $\underline{c}_j$  in einen blauen (oder weißblauen) Punkt  $\underline{y}_j$  verfälscht werden, der zur Hyperkugel eines anderen Codewortes  $\underline{c}_{k ≠ j}$  gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  wird falsch decodiert”.

	* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören   ⇒   &bdquo;Das Empfangswort $\underline{y}_j$ ist nicht decodierbar”.		* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören   <br>⇒   &bdquo;Das Empfangswort  $\underline{y}_j$  ist nicht decodierbar”.


	In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung ~~der~~		In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung von
	* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|''Bounded Distance Decoding'' (BDD) von Hamming–Codes]] bzw.		* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|''Bounded Distance Decoding'' (BDD) von Hamming–Codes]] bzw.
	* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|''Bounded Distance Decoding'' (BDD) von Reed–Solomon–Codes]].		* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|''Bounded Distance Decoding'' (BDD) von Reed–Solomon–Codes]].

Guenter am 16. Januar 2018 um 06:57 Uhr

2018-01-16T06:57:24Z

← Nächstältere Version		Version vom 16. Januar 2018, 08:57 Uhr
Zeile 13:		Zeile 13:

	In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung der		In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung der
	* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|~~&bdquo;~~Bounded Distance~~” Decodierung~~ von Hamming–Codes]] bzw.		* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|''Bounded Distance Decoding'' (BDD) von Hamming–Codes]] bzw.
	* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|~~&bdquo;~~Bounded Distance~~” Decodierung~~ von Reed–Solomon–Codes]].		* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|''Bounded Distance Decoding'' (BDD) von Reed–Solomon–Codes]].


Zeile 53:		Zeile 53:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  ~~Das~~ Codierraumschema <b>A</b> ~~beschreibt~~ einen perfekten Code~~. Da~~ jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist, ~~gilt <u>Antwort 1</u>. Bei diesen~~ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden. Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel		'''(1)'''  Richtig ist der <u>Lösungsvorschlag 1</u>, da das Codierraumschema <b>A</b> einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist:
	* ~~<span style="color: rgb(204, 0, 0);">~~<b>HC (7, 4, 3)</b~~></span~~>: ~~Einen~~ Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler  ⇒  $1 + 7 = 8 = 2^3 = 2^{7-4}$.		*Bei einem jeden Hamming–Code $(n, \, k, \, 3)$ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden.
	* ~~<span style="color: rgb(204, 0, 0);">~~<b>HC (15, 11, 3)</b~~></span~~>: ~~Auch hier wieder~~ einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler  ⇒  $1 + 15 = 16 = 2^4 = 2^{15-11}$.		*Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel
			:* <b>HC (7, 4, 3)</b>: einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.
			:* <b>HC (15, 11, 3)</b>: einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.


Zeile 61:		Zeile 63:


	'''(2)'''  Richtig ist <u>Antwort 1</u>. Im grauen Bereich außerhalb von &bdquo;Kugeln” gibt es bei einem perfekten Code keinen einzigen Punkt~~, wie die~~ Rechnung zur Teilaufgabe (1) gezeigt ~~hat~~.		'''(2)'''  Richtig ist die <u>Antwort 1</u>:
			*Im grauen Bereich außerhalb von &bdquo;Kugeln” gibt es bei einem perfekten Code keinen einzigen Punkt.
			*Dies wurde auch in der Rechnung zur Teilaufgabe (1) gezeigt.


	'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema <b>B</b> beschrieben  ⇒  <u>Antwort 2</u>. Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei <i>Bounded Distance Decoding</i> (BDD) keiner Kugel zugeordnet werden können.		'''(3)'''  Die Reed–Solomon–Codes werden durch das Codierraumschema <b>B</b> beschrieben  ⇒  <u>Antwort 2</u>.
			*Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei <i>Bounded Distance Decoding</i> (BDD) keiner Kugel zugeordnet werden können.
			*Betrachten wir beispielweise den $\rm RSC \, (7, \, 3, \, 5)_8$ mit den Codeparametern $n = 7, \, k = 3$ und $t = 2$, so gibt es hier insgesamt $8^7 = 2097152$ Punkte und $8^3 = 512$ Hyperkugeln.
			*Wäre dieser Code perfekt, so müsste es also innerhalb jeder Kugel $8^4 = 4096$ Punkte geben. Es gilt aber:
			:$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)}
			= {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079
			\hspace{0.05cm}.$$

	~~Betrachten wir beispielweise den~~ $\rm ~~RSC \,~~ (~~7, \, 3, \, 5~~)~~_8$ mit den Codeparametern~~ $~~n = 7~~, ~~\, k = 3$ und $t = 2$, so gibt~~ es ~~hier insgesamt~~ $8^7 ~~= 2097152$ Punkte und $8^3 = 512$ Hyperkugeln. Wäre dieser Code perfekt, so müsste es also innerhalb jeder Kugel $8^4 = 4096$ Punkte geben. Es gilt aber:~~		*Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es &bdquo;$7 \rm \ über \ 1$” $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch 7 unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.
	~~:$${~~\rm ~~Pr(\underline{~~\~~it y}_{~~\~~it i} \hspace{0.15cm}liegt\hspace{0.15cm} innerhalb\hspace{0.15cm} der\hspace{0.15cm} roten\hspace{0.15cm} Kugel)}~~
	~~= {\rm Pr}(f \le t) =~~$$
	:$$~~= {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+~~{\rm Pr}(f = 2) ~~=1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079~~
	~~\hspace{0.05cm}~~.$$

	Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es &bdquo;$7 \rm \ über \ 1$” $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch 7 unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.

			'''(4)'''  Richtig ist die <u>Antwort 3</u>:
			*Ein Punkt im grauen Niemandsland wird mit weniger Symbolfehlern erreicht als ein Punkt in einer anderen Hyperkugel.
			*Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:

	'''(4)'''  Richtig ist hier die <u>Antwort 3</u>. Ein Punkt im grauen Niemandsland wird mit weniger Symbolfehlern erreicht als ein Punkt in einer anderen Hyperkugel. Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:		:$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)}
	:$${\rm Pr(\underline{~~\it~~ y}_{~~\it~~ i} \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)}
	= {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}		= {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$
			*Für den ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$ liefert diese obere Schranke den Wert $1/(16!) < 10^{-14}$.
	Für den $\rm RSC \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$ liefert diese obere Schranke den Wert $1/(16!) < 10^{-14}$.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 16. Januar 2018 um 06:29 Uhr

2018-01-16T06:29:34Z

← Nächstältere Version		Version vom 16. Januar 2018, 08:29 Uhr
Zeile 1:		Zeile 1:
	{{quiz-Header\|Buchseite=Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete}}		{{quiz-Header\|Buchseite=Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete}}

	[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|Zwei unterschiedliche Codierraumschemata\|]]		[[Datei: P_ID2583__KC_A_2_16neu.png\|right\|frame\|Zwei unterschiedliche Codierraumschemata]]
	Wir gehen von einem Blockcode der Länge $n$ mit Symbolen $c_i ∈ {\rm GF}(2^m)$ aus, der bis zu $t$ Symbole korrigieren kann. Jedes mögliche Empfangswort $\underline{y}_i$ kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis ${\rm GF}(2) = \{0, \, 1\}$ aus, so beträgt die Dimension $n \cdot m$.		Wir gehen von einem Blockcode der Länge $n$ mit Symbolen $c_i ∈ {\rm GF}(2^m)$ aus, der bis zu $t$ Symbole korrigieren kann. Jedes mögliche Empfangswort $\underline{y}_i$ kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis ${\rm GF}(2) = \{0, \, 1\}$ aus, so beträgt die Dimension $n \cdot m$.

	Die Grafik zeigt einen solchen Raum in stark vereinfachender 2D–Darstellung. Die Abbildung ist wie folgt zu interpretieren:		Die Grafik zeigt einen solchen Raum in stark vereinfachender 2D–Darstellung. Die Abbildung ist wie folgt zu interpretieren:
	* Gesendet wurde der rote Punkt $\underline{c}_j$. Alle rot umrandeten Punkte $\underline{y}_i$ in einer Hyperkugel um diesen Punkt $\underline{c}_j$ mit dem Parameter $t$ als Radius können korrigiert werden. Mit der Nomenklatur gemäß der [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]] im Theorieteil gilt dann $\underline{z}_i = \underline{c}_j$  ⇒  &bdquo;Die Fehlerkorrektur ist erfolgreich”.		* Gesendet wurde der rote Punkt $\underline{c}_j$. Alle rot umrandeten Punkte $\underline{y}_i$ in einer Hyperkugel um diesen Punkt $\underline{c}_j$ mit dem Parameter $t$ als Radius können korrigiert werden. Mit der Nomenklatur gemäß der [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|Grafik]] im Theorieteil gilt dann $\underline{z}_i = \underline{c}_j$   ⇒   &bdquo;Die Fehlerkorrektur ist erfolgreich”.

	* Bei sehr vielen Symbolfehlern kann $\underline{c}_j$ in einen blauen (oder weißblauen) Punkt $\underline{y}_j$ verfälscht werden, der zur Hyperkugel eines anderen Codewortes $\underline{c}_{k ≠ j}$ gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung  ⇒  &bdquo;Das Empfangswort $\underline{y}_j$ wird falsch decodiert”.		* Bei sehr vielen Symbolfehlern kann $\underline{c}_j$ in einen blauen (oder weißblauen) Punkt $\underline{y}_j$ verfälscht werden, der zur Hyperkugel eines anderen Codewortes $\underline{c}_{k ≠ j}$ gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung   ⇒   &bdquo;Das Empfangswort $\underline{y}_j$ wird falsch decodiert”.

	* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören  ⇒  &bdquo;Das Empfangswort $\underline{y}_j$ ist nicht decodierbar”.		* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören   ⇒   &bdquo;Das Empfangswort $\underline{y}_j$ ist nicht decodierbar”.


	In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung der		In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung der
	* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|~~BDD~~&~~ndash~~;Decodierung von Hamming–Codes]] bzw.		* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes\|&bdquo;Bounded Distance” Decodierung von Hamming–Codes]] bzw.
	* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|~~BDD~~&~~ndash~~;Decodierung von Reed–Solomon–Codes]].		* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD\|&bdquo;Bounded Distance” Decodierung von Reed–Solomon–Codes]].


	''~~Hinweis~~:''
	* Die Aufgabe ergänzt die Thematik des Kapitels [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|Fehlerwahrscheinlichkeit und Anwendungsgebiete]] ~~und~~ soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.

			''Hinweise:''
			* Die Aufgabe ergänzt die Thematik des Kapitels [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete\|Fehlerwahrscheinlichkeit und Anwendungsgebiete]].
			* Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.

Guenter: Guenter verschob die Seite Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei Bounded Distance Decoding nach Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei BDD

2018-01-16T06:21:27Z

Guenter verschob die Seite Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei Bounded Distance Decoding nach Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei BDD

← Nächstältere Version	Version vom 16. Januar 2018, 08:21 Uhr
(kein Unterschied)