Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei BDD: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
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–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&nbsp; $\underline{c}_j$. Alle rot umrandeten Punkte&nbsp; $\underline{y}_i$&nbsp; in einer Hyperkugel um diesen Punkt&nbsp; $\underline{c}_j$&nbsp; mit dem Parameter&nbsp; $t$&nbsp; als Radius können korrigiert werden. Mit der Nomenklatur gemäß der&nbsp; [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD|Grafik]]&nbsp; im Theorieteil gilt dann&nbsp; $\underline{z}_i = \underline{c}_j$ &nbsp; <br>&#8658; &nbsp; &bdquo;Die Fehlerkorrektur ist erfolgreich&rdquo;.
 
  
* Bei sehr vielen Symbolfehlern kann&nbsp; $\underline{c}_j$&nbsp; in einen blauen (oder weißblauen) Punkt&nbsp; $\underline{y}_j$&nbsp; verfälscht werden, der zur Hyperkugel eines anderen Codewortes&nbsp; $\underline{c}_{k &ne; j}$&nbsp; gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung &nbsp; <br>&#8658; &nbsp; &bdquo;Das Empfangswort&nbsp; $\underline{y}_j$&nbsp; wird falsch decodiert&rdquo;.
+
Die Grafik zeigt einen solchen Raum in vereinfachender, schematischer zweidimensionaler Darstellung.&nbsp; Die Abbildung ist wie folgt zu interpretieren:
 +
# Gesendet wurde der rote Punkt&nbsp; $\underline{c}_j$.&nbsp; Alle rot umrandeten Punkte&nbsp; $\underline{y}_i$&nbsp; in einer Hyperkugel um diesen Punkt&nbsp; $\underline{c}_j$&nbsp; mit dem Parameter&nbsp; $t$&nbsp; als Radius können korrigiert werden.&nbsp; Mit der Nomenklatur gemäß der&nbsp; [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD|$\rm Grafik$]]&nbsp; im Theorieteil gilt&nbsp; $\underline{z}_i = \underline{c}_j$ &nbsp; <br>&#8658; &nbsp; &bdquo;Die Fehlerkorrektur ist erfolgreich&rdquo;.
 +
# Bei sehr vielen Symbolfehlern kann&nbsp; $\underline{c}_j$&nbsp; in einen blauen&nbsp; $($oder weißblauen$)$&nbsp; Punkt&nbsp; $\underline{y}_j$&nbsp; verfälscht werden,&nbsp; der zur Hyperkugel eines anderen Codewortes&nbsp; $\underline{c}_{k &ne; j}$&nbsp; gehört.&nbsp; In diesem Fall trifft der Decoder eine falsche Entscheidung &nbsp; <br>&#8658; &nbsp; &bdquo;Das Empfangswort&nbsp; $\underline{y}_j$&nbsp; wird falsch decodiert&rdquo;.
 +
# Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben,&nbsp; die zu keiner Hyperkugel gehören &nbsp; <br>&#8658; &nbsp; &bdquo;Das Empfangswort&nbsp; $\underline{y}_j$&nbsp; ist nicht decodierbar&rdquo;.
  
* Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören &nbsp; <br>&#8658; &nbsp; &bdquo;Das Empfangswort&nbsp; $\underline{y}_j$&nbsp; ist nicht decodierbar&rdquo;.
 
  
 +
In dieser Aufgabe sollen Sie entscheiden,&nbsp; welches der beiden Coderaumschemata geeignet ist zur Beschreibung von
 +
* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|Bounded Distance Decoding  von Hamming&ndash;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&ndash;Solomon&ndash;Codes]].
* [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|Bounded Distance Decoding &nbsp;(BDD) von Hamming&ndash;Codes]] bzw.
 
* [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD|Bounded Distance Decoding &nbsp;(BDD) von Reed&ndash;Solomon&ndash;Codes]].
 
  
  
Zeile 23: Zeile 24:
  
  
 +
<u>Hinweise:</u>
 +
* Die Aufgabe ergänzt die Thematik des Kapitels&nbsp; [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete|"Fehlerwahrscheinlichkeit und Anwendungsgebiete"]].
  
 
''Hinweise:''
 
* Die Aufgabe ergänzt die Thematik des Kapitels&nbsp; [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete|Fehlerwahrscheinlichkeit und Anwendungsgebiete]].
 
 
* Sie soll signifikante Unterschiede bei der Decodierung von Reed&ndash;Solomon&ndash;Codes und Hamming&ndash;Codes verdeutlichen.
 
* Sie soll signifikante Unterschiede bei der Decodierung von Reed&ndash;Solomon&ndash;Codes und Hamming&ndash;Codes verdeutlichen.
  
Zeile 38: Zeile 38:
 
- Codierraumschema &nbsp;$\rm B$.
 
- Codierraumschema &nbsp;$\rm B$.
  
{Welche Aussage gilt für die Wahrscheinlichkeit, dass bei Hamming&ndash;Codierung ein Empfangswort&nbsp; $\underline{y}$&nbsp; nicht decodiert werden kann?
+
{Welche Aussage gilt für die Wahrscheinlichkeit,&nbsp; dass bei Hamming&ndash;Codierung ein Empfangswort&nbsp; $\underline{y}$&nbsp; nicht decodiert werden kann?
 
|type="[]"}
 
|type="[]"}
+ Die Wahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$&nbsp; ist exakt Null.
+
+ Die Wahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{y} \rm \hspace{0.15cm}ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$&nbsp; ist exakt Null.
- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$&nbsp; ist ungleich Null, aber vernachlässigbar.  
+
- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$&nbsp; ist ungleich Null, aber vernachlässigbar.  
- Es gilt&nbsp; ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.
+
- Es gilt&nbsp; ${\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&ndash;Solomon&ndash;Codes zu?
 
{Welches Codierraumschema trifft für die Reed&ndash;Solomon&ndash;Codes zu?
Zeile 51: Zeile 51:
 
{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort&nbsp; $\underline{y}$&nbsp; nach Reed&ndash;Solomon&ndash;Codierung nicht decodiert werden kann?
 
{Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort&nbsp; $\underline{y}$&nbsp; nach Reed&ndash;Solomon&ndash;Codierung nicht decodiert werden kann?
 
|type="[]"}
 
|type="[]"}
- Die Wahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$&nbsp; ist exakt Null.
+
- Die Wahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{y} \rm \hspace{0.15cm}ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$&nbsp; ist exakt Null.
- ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$&nbsp; ist ungleich Null, aber vernachlässigbar.  
+
- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} ist \hspace{0.15cm} nicht \hspace{0.15cm} decodierbar)$&nbsp; ist ungleich Null, aber vernachlässigbar.  
+ Es gilt&nbsp; ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.
+
+ Es gilt&nbsp; ${\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>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>, da das Codierraumschema &nbsp;$\rm A$&nbsp; einen perfekten Code  beschreibt und jeder Hamming&ndash;Code $(n, \, k, \, 3)$ ein perfekter Code ist:  
+
'''(1)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 1</u>,&nbsp; da das Codierraumschema &nbsp;$\rm A$&nbsp; einen perfekten Code  beschreibt und jeder Hamming&ndash;Code $(n, \, k, \, 3)$&nbsp; ein perfekter Code ist:  
*Bei einem jeden Hamming&ndash;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&ndash;Code $(n, \, k, \, 3)$&nbsp; gibt es insgesamt&nbsp; $2^n$&nbsp; mögliche Empfangsworte&nbsp; $\underline{y}_i$,&nbsp; die bei der Syndromdecodierung einem von&nbsp; $2^k$&nbsp; möglichen Codeworten&nbsp; $\underline{c}_j$&nbsp; zugeordnet werden.
*Aufgrund der HC&ndash;Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$&ndash;dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel
+
 +
*Aufgrund der&nbsp; HC&ndash;Eigenschaft $d_{\rm min} = 3$&nbsp; haben alle Kugeln im&nbsp; $n$&ndash;dimensionalen Raum den Radius&nbsp; $t = 1$.&nbsp; In allen Kugeln gibt es somit&nbsp; $2^{n-k}$&nbsp; Punkte,&nbsp; zum Beispiel
 
:* $\text{HC (7, 4, 3)}$: &nbsp; einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler &nbsp; &#8658; &nbsp; $1 + 7 = 8 = 2^3 = 2^{7-4}$.
 
:* $\text{HC (7, 4, 3)}$: &nbsp; einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler &nbsp; &#8658; &nbsp; $1 + 7 = 8 = 2^3 = 2^{7-4}$.
:* $\text{HC (15, 11, 3)}$: &nbsp; einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler &nbsp; &#8658; &nbsp; $1 + 15 = 16 = 2^4 = 2^{15-11}$.
+
:* $\text{HC (15, 11, 3)}$: &nbsp; einen Punkt für die fehlerfreie Übertragung und nun fünfzehn Punkte für einen Bitfehler &nbsp; &#8658; &nbsp; $1 + 15 = 16 = 2^4 = 2^{15-11}$.
  
''Hinweis:'' &nbsp;Da der Hamming&ndash;Code ein Binärcode ist, hat hier der Coderaum die Dimension&nbsp; $n$.
+
<u>Hinweis:</u> &nbsp;Da der Hamming&ndash;Code ein Binärcode ist,&nbsp; hat hier der Coderaum die Dimension&nbsp; $n$.
  
  
  
'''(2)'''&nbsp; Richtig ist die <u>Antwort 1</u>:  
+
'''(2)'''&nbsp; Richtig ist die&nbsp; <u>Antwort 1</u>:  
 
*Im grauen Bereich außerhalb von &bdquo;Kugeln&rdquo; gibt es bei einem perfekten Code keinen einzigen Punkt.
 
*Im grauen Bereich außerhalb von &bdquo;Kugeln&rdquo; 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&nbsp; '''(1)'''&nbsp; gezeigt.  
  
  
  
 
'''(3)'''&nbsp; Die Reed&ndash;Solomon&ndash;Codes werden durch das Codierraumschema &nbsp;$\rm B$&nbsp; beschrieben &nbsp;&#8658;&nbsp; <u>Antwort 2</u>.  
 
'''(3)'''&nbsp; Die Reed&ndash;Solomon&ndash;Codes werden durch das Codierraumschema &nbsp;$\rm B$&nbsp; beschrieben &nbsp;&#8658;&nbsp; <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,&nbsp; also Punkte die bei&nbsp; "Bounded Distance Decoding"&nbsp; 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&nbsp; $\rm RSC \, (7, \, 3, \, 5)_8$&nbsp; mit den Codeparametern&nbsp; $n = 7, \, k = 3$ und $t = 2$,&nbsp; so gibt es hier insgesamt&nbsp; $8^7 = 2097152$&nbsp; Punkte und&nbsp; $8^3 = 512$&nbsp; Hyperkugeln.
 +
 +
*Wäre dieser Code perfekt,&nbsp; so müsste es also innerhalb jeder Kugel&nbsp; $8^4 = 4096$&nbsp; Punkte geben.&nbsp; 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&nbsp; ${\rm Pr}(f = 1)$&nbsp; ist berücksichtigt,&nbsp; dass es&nbsp; "$7 \rm \ über \ 1$"&nbsp; $= 7$&nbsp; Fehlerpositionen geben kann,&nbsp; und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte.&nbsp; Entsprechendes ist auch für&nbsp; ${\rm Pr}(f = 2)$&nbsp; berücksichtigt.
  
  
  
'''(4)'''&nbsp; Richtig ist die <u>Antwort 3</u>:
+
'''(4)'''&nbsp; Richtig ist die&nbsp; <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&nbsp; ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$&nbsp; liefert diese obere Schranke den Wert&nbsp; $1/(16!) < 10^{-14}$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 2. November 2022, 17:27 Uhr

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$.


Die Grafik zeigt einen solchen Raum in vereinfachender, schematischer zweidimensionaler Darstellung.  Die Abbildung ist wie folgt zu interpretieren:

  1. 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  $\rm Grafik$  im Theorieteil gilt  $\underline{z}_i = \underline{c}_j$  
    ⇒   „Die Fehlerkorrektur ist erfolgreich”.
  2. 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  
    ⇒   „Das Empfangswort  $\underline{y}_j$  wird falsch decodiert”.
  3. Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben,  die zu keiner Hyperkugel gehören  
    ⇒   „Das Empfangswort  $\underline{y}_j$  ist nicht decodierbar”.


In dieser Aufgabe sollen Sie entscheiden,  welches der beiden Coderaumschemata geeignet ist zur Beschreibung von




Hinweise:

  • Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.


Fragebogen

1

Welches Codierraumschema trifft für die Hamming–Codes zu?

Codierraumschema  $\rm A$,
Codierraumschema  $\rm B$.

2

Welche Aussage gilt für die Wahrscheinlichkeit,  dass bei Hamming–Codierung ein Empfangswort  $\underline{y}$  nicht decodiert werden kann?

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 \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 \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)$.

3

Welches Codierraumschema trifft für die Reed–Solomon–Codes zu?

Codierraumschema  $\rm A$,
Codierraumschema  $\rm B$.

4

Welche Aussage gilt für die Wahrscheinlichkeit, dass ein Empfangswort  $\underline{y}$  nach Reed–Solomon–Codierung nicht decodiert werden kann?

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 \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 \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)$.


Musterlösung

(1)  Richtig ist der  Lösungsvorschlag 1,  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.
  • 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 (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$.


(2)  Richtig ist die  Antwort 1:

  • Im grauen Bereich außerhalb von „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  $\rm B$  beschrieben  ⇒  Antwort 2.

  • 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:
$${\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}.$$
  • 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  Antwort 3:

  • 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{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}$.