Aufgaben:Aufgabe 2.09: Reed–Solomon–Parameter: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 2: Zeile 2:
  
 
[[Datei:P_ID2523__KC_A_2_9_neu.png|right|frame|Einige Reed–Solomon–Codes]]
 
[[Datei:P_ID2523__KC_A_2_9_neu.png|right|frame|Einige Reed–Solomon–Codes]]
Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes, die bekanntlich auf einem Galoisfeld  ${\rm GF}(q) = {\rm GF}(2^m)$  basieren. Der Parameter  $m$  gibt an, mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt:
+
Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes,  die bekanntlich auf einem Galoisfeld  ${\rm GF}(q) = {\rm GF}(2^m)$  basieren.  Der Parameter  $m$  gibt an,  mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt:
 
* $m = 4$  (rote Schrift),
 
* $m = 4$  (rote Schrift),
 +
 
* $m = 5$  (blaue Schrift),
 
* $m = 5$  (blaue Schrift),
 +
 
* $m = 6$  (grüne Schrift).
 
* $m = 6$  (grüne Schrift).
  
  
 
Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet:   ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.
 
Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet:   ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.
 
  
 
Die Parameter haben folgende Bedeutung:
 
Die Parameter haben folgende Bedeutung:
* $n$&nbsp; gibt die Anzahl der Symbole eines Codewortes&nbsp; $\underline{c}$&nbsp; an &nbsp; &#8658; &nbsp; <b>Länge</b> des Codes,
+
# $n$&nbsp; gibt die Anzahl der Symbole eines Codewortes&nbsp; $\underline{c}$&nbsp; an &nbsp; &#8658; &nbsp; <b>Länge</b>&nbsp; des Codes.
* $k$&nbsp; gibt die Anzahl der Symbole eines Informationsblocks&nbsp; $\underline{u}$&nbsp; an &nbsp; &#8658; &nbsp; <b>Dimension</b> des Codes,
+
# $k$&nbsp; gibt die Anzahl der Symbole eines Informationsblocks&nbsp; $\underline{u}$&nbsp; an &nbsp; &#8658; &nbsp; <b>Dimension</b>&nbsp; des Codes.
* $d_{\rm min}$&nbsp; kennzeichnet die&nbsp; <b>minimale Distanz </b>&nbsp; zwischen zwei Codeworten <br>$($bei allen Reed&ndash;Solomon&ndash;Codes gleich&nbsp; $n-k+1)$,
+
# $d_{\rm min}$&nbsp; kennzeichnet die&nbsp; <b>minimale Distanz </b>&nbsp; zwischen zwei Codeworten <br>$($bei allen Reed&ndash;Solomon&ndash;Codes gleich&nbsp; $n-k+1)$.
* $q$&nbsp; gibt einen Hinweis auf die Verwendung des Galoisfeldes&nbsp; ${\rm GF}(q)$.
+
# $q$&nbsp; gibt einen Hinweis auf die Verwendung des Galoisfeldes&nbsp; ${\rm GF}(q)$.
  
  
 
Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben:  
 
Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben:  
*Bei dieser Realisierung eines RS&ndash;Codes wird jedes Informations&ndash; und Codesymbol durch&nbsp; $m$&nbsp; Bit dargestellt.  
+
# Bei dieser Realisierung eines RS&ndash;Codes wird jedes Informations&ndash; und Codesymbol durch&nbsp; $m$&nbsp; Bit dargestellt.  
*Beispielsweise erkennt man aus der ersten Zeile, dass die minimale Distanz hinsichtlich der Bits ebenfalls&nbsp; $d_{\rm min} = 5$&nbsp; ist, wenn in&nbsp; ${\rm GF}(2^m)$&nbsp; die minimale Distanz&nbsp; $d_{\rm min} = 5$&nbsp; beträgt.  
+
# Beispielsweise erkennt man aus der ersten Zeile, dass die minimale Distanz hinsichtlich der Bits ebenfalls&nbsp; $d_{\rm min} = 5$&nbsp; ist, wenn in&nbsp; ${\rm GF}(2^m)$&nbsp; die minimale Distanz&nbsp; $d_{\rm min} = 5$&nbsp; beträgt.  
*Damit können bis zu&nbsp; $t = 2$&nbsp; Bitfehler (oder Symbolfehler) korrigiert und bis zu&nbsp; $e = 4$&nbsp; Bitfehler (oder Symbolfehler) erkannt werden.
+
# Damit können bis zu&nbsp; $t = 2$&nbsp; Bitfehler (oder Symbolfehler) korrigiert und bis zu&nbsp; $e = 4$&nbsp; Bitfehler (oder Symbolfehler) erkannt werden.
  
  
Zeile 27: Zeile 28:
  
  
 +
Hinweise:
 +
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| "Definition und Eigenschaften von Reed&ndash;Solomon&ndash;Codes"]].
  
 
+
* Bezug genommen wird aber auch auf das Kapitel&nbsp; [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]].
''Hinweise:''
 
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| Definition und Eigenschaften von Reed&ndash;Solomon&ndash;Codes]].
 
* Bezug genommen wird aber auch auf das Kapitel&nbsp; [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]].
 
 
   
 
   
  
Zeile 38: Zeile 38:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Es gelte&nbsp; $c_i &#8712; {\rm GF}(2^m)$. Welche RS&ndash;Codeparameter&nbsp; $n$&nbsp; ergeben sich?
+
{Es gelte&nbsp; $c_i &#8712; {\rm GF}(2^m)$.&nbsp; Welche Codeparameter&nbsp; $n$&nbsp; ergeben sich?
 
|type="{}"}
 
|type="{}"}
 
$m = 4 \text{:} \hspace{0.4cm} n \ = \ ${ 15 }
 
$m = 4 \text{:} \hspace{0.4cm} n \ = \ ${ 15 }
Zeile 44: Zeile 44:
 
$m = 6 \text{:} \hspace{0.4cm} n \ = \ ${ 63 }
 
$m = 6 \text{:} \hspace{0.4cm} n \ = \ ${ 63 }
  
{Im Folgenden werden zwei spezielle RS&ndash;Codes&nbsp; ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$&nbsp; und&nbsp; ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$&nbsp; betrachtet. <br>Mit welchem RS&ndash;Parameter&nbsp; $k$&nbsp; lassen sich genau&nbsp; $t$&nbsp; Symbolfehler korrigeren?
+
{Im Folgenden werden zwei spezielle Reed&ndash;Solomon&ndash;Codes&nbsp; ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$&nbsp; und&nbsp; ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$&nbsp; betrachtet. <br>Mit welchem Parameter&nbsp; $k$&nbsp; lassen sich genau&nbsp; $t$&nbsp; Symbolfehler korrigeren?
 
|type="{}"}
 
|type="{}"}
 
${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ ${ 7 }
 
${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ ${ 7 }
Zeile 51: Zeile 51:
 
{Welche Bezeichnungen sind für&nbsp; $\rm RSC \ 1$&nbsp; bzw.&nbsp; $\rm RSC \ 2$&nbsp; richtig?
 
{Welche Bezeichnungen sind für&nbsp; $\rm RSC \ 1$&nbsp; bzw.&nbsp; $\rm RSC \ 2$&nbsp; richtig?
 
|type="[]"}
 
|type="[]"}
+ $\rm RSC \ 1$&nbsp; nennt man auch&nbsp; $\rm RSC \, (15, \, 7, \, 9)_{16}$.
+
+ $\rm RSC \ 1$&nbsp; nennt man auch&nbsp; "$\rm RSC \, (15, \, 7, \, 9)_{16}$".
- $\rm RSC \ 1$&nbsp; nennt man auch&nbsp; $\rm RSC \, (15, \, 7, \, 4)_4$.
+
- $\rm RSC \ 1$&nbsp; nennt man auch&nbsp; "$\rm RSC \, (15, \, 7, \, 4)_4$".
- $\rm RSC \ 2$&nbsp; nennt man auch&nbsp; $\rm RSC \, (31, \, 17, \, 15)_{32}$.
+
- $\rm RSC \ 2$&nbsp; nennt man auch&nbsp; "$\rm RSC \, (31, \, 17, \, 15)_{32}$".
+ $\rm RSC \ 2$&nbsp; nennt man auch&nbsp; $\rm  RSC \, (31, \, 15, \, 17)_{32}$.
+
+ $\rm RSC \ 2$&nbsp; nennt man auch&nbsp; "$\rm  RSC \, (31, \, 15, \, 17)_{32}$".
  
 
{Wieviele Symbolfehler&nbsp; $(e)$&nbsp; können höchstens erkannt werden?  
 
{Wieviele Symbolfehler&nbsp; $(e)$&nbsp; können höchstens erkannt werden?  
Zeile 63: Zeile 63:
 
{Wie lauten die betrachteten Codes in Binärschreibweise?
 
{Wie lauten die betrachteten Codes in Binärschreibweise?
 
|type="[]"}
 
|type="[]"}
- $\rm RSC \ 1$&nbsp; entspricht dem Code&nbsp; $\rm RSC \, (60, \, 28, \, 36)_2$.
+
- $\rm RSC \ 1$&nbsp; entspricht dem Code&nbsp; "$\rm RSC \, (60, \, 28, \, 36)_2$".
+ $\rm RSC \ 1$&nbsp; entspricht dem Code&nbsp; $\rm RSC \, (60, \, 28, \, 9)_2$.
+
+ $\rm RSC \ 1$&nbsp; entspricht dem Code&nbsp; "$\rm RSC \, (60, \, 28, \, 9)_2$".
+ $\rm RSC \ 2$&nbsp; entspricht dem Code&nbsp; $\rm RSC \, (155, \, 75, \, 17)_2$.
+
+ $\rm RSC \ 2$&nbsp; entspricht dem Code&nbsp; "$\rm RSC \, (155, \, 75, \, 17)_2$".
- $\rm RSC \ 2$&nbsp; entspricht dem Code&nbsp; $\rm RSC \, (124, \, 60, \, 17)_2$.
+
- $\rm RSC \ 2$&nbsp; entspricht dem Code&nbsp; "$\rm RSC \, (124, \, 60, \, 17)_2$".
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Für die Codelänge der Reed&ndash;Solomon&ndash;Codes gilt allgemein.
+
'''(1)'''&nbsp; Für die Codelänge der Reed&ndash;Solomon&ndash;Codes gilt allgemein:
 
:$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow  \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm},  
 
:$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow  \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm},  
 
\hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm}  
 
\hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm}  
 
m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$
 
m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$
  
'''(2)'''&nbsp; Um $t$ Symbolfehler korrigieren zu können, muss die minimale Distanz $d_{\rm min} = 2t + 1$ betragen. Der Reed&ndash;Solomon&ndash;Code ist ein sogenannter MDS&ndash;Code (<i>Maximum Distance Separable</i>). Für diese gilt:
+
 
 +
'''(2)'''&nbsp; Um&nbsp; $t$&nbsp; Symbolfehler korrigieren zu können,&nbsp; muss die minimale Distanz mindestens &nbsp; $d_{\rm min} = 2t + 1$ &nbsp; betragen.  
 +
*Der Reed&ndash;Solomon&ndash;Code ist ein sogenannter MDS&ndash;Code&nbsp; ("Maximum Distance Separable").&nbsp; Für diese gilt:
 
:$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}k = n -2t =  2^m - ( 2t+1) \hspace{0.05cm}. $$
 
:$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}k = n -2t =  2^m - ( 2t+1) \hspace{0.05cm}. $$
  
Damit erhält man für den  
+
*Damit erhält man für den  
* $\rm RSC \ 1$ (mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
+
:* $\rm RSC \ 1$&nbsp; $($mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
* $\rm RSC \ 2$ (mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.
+
:* $\rm RSC \ 2$&nbsp; $($mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.
  
  
'''(3)'''&nbsp; Die Bezeichnung eines Reed&ndash;Solomon&ndash;Codes lautet ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ mit $q = 2^m = n + 1$. Richtig sind die <u>Lösungsvorschläge 1 und 4</u>:
+
 
 +
'''(3)'''&nbsp; Die Bezeichnung eines Reed&ndash;Solomon&ndash;Codes lautet &nbsp; ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ &nbsp; mit&nbsp; $q = 2^m = n + 1$.&nbsp; Richtig sind die&nbsp; <u>Lösungsvorschläge 1 und 4</u>:
 
* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
 
* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
 +
 
* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.
 
* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.
  
  
'''(4)'''&nbsp; Bezeichnet $d_{\rm min}$ die minimale Distanz eines Blockcodes, so können damit $e = d_{\rm min} - 1$ Symbolfehler erkannt und $t = e/2$ Symbolfehler korrigiert werden:
+
 
 +
'''(4)'''&nbsp; Bezeichnet&nbsp; $d_{\rm min}$&nbsp; die minimale Distanz eines Blockcodes,&nbsp; so können damit &nbsp; $e = d_{\rm min} - 1$ &nbsp; Symbolfehler erkannt und &nbsp; $t = e/2$ &nbsp; Symbolfehler korrigiert werden:
 
* ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$,
 
* ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$,
 +
 
* ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$.
 
* ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$.
  
  
'''(5)'''&nbsp; Richtig sind die beiden mittleren <u>Lösungsvorschläge 2 und 3</u>:  
+
 
*Bei ${\rm RSC} \ 1 \, (m = 4)$ entsprechen $n = 15$ Codesymbolen aus $\rm GF(2^5)$ gleich $60$ Bit und $k = 7$ Informationssymbole genau $28$ Bit:
+
'''(5)'''&nbsp; Richtig sind die beiden mittleren&nbsp; <u>Lösungsvorschläge 2 und 3</u>:  
 +
*Beim&nbsp; ${\rm RSC} \ 1 \, \, (m = 4)$&nbsp; entsprechen&nbsp; $n = 15$&nbsp; Codesymbole aus&nbsp; $\rm GF(2^5)$&nbsp; gleich&nbsp; $60$&nbsp; Bit&nbsp; und&nbsp; $k = 7$&nbsp; Informationssymbole genau&nbsp; $28$&nbsp; Bit:
 +
 
 
:* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$,
 
:* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$,
 +
 
:* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$.
 
:* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$.
*Für die minimale Distanz auf Bitebene &nbsp; &rArr; &nbsp; $\rm GF(2)$ ergeben sich mit $d_{\rm min} = 9$ bzw. $d_{\rm min} = 17$ die gleichen Werte wie auf Symbolebene &nbsp; &rArr; &nbsp; $\rm GF(2^4)$ bzw. $\rm GF(2^5)$ (siehe [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|Theorieteil]]).
+
 
 +
*Für die minimale Distanz auf Bitebene &nbsp; &rArr; &nbsp; $\rm GF(2)$ ergeben sich mit&nbsp; $d_{\rm min} = 9$&nbsp; bzw.&nbsp; $d_{\rm min} = 17$&nbsp; die gleichen Werte wie auf Symbolebene &nbsp; <br>&rArr; &nbsp; $\rm GF(2^4)$&nbsp; bzw.&nbsp; $\rm GF(2^5)$&nbsp; $($siehe [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|Theorieteil]]$)$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 11. Oktober 2022, 13:59 Uhr

Einige Reed–Solomon–Codes

Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes,  die bekanntlich auf einem Galoisfeld  ${\rm GF}(q) = {\rm GF}(2^m)$  basieren.  Der Parameter  $m$  gibt an,  mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt:

  • $m = 4$  (rote Schrift),
  • $m = 5$  (blaue Schrift),
  • $m = 6$  (grüne Schrift).


Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet:   ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.

Die Parameter haben folgende Bedeutung:

  1. $n$  gibt die Anzahl der Symbole eines Codewortes  $\underline{c}$  an   ⇒   Länge  des Codes.
  2. $k$  gibt die Anzahl der Symbole eines Informationsblocks  $\underline{u}$  an   ⇒   Dimension  des Codes.
  3. $d_{\rm min}$  kennzeichnet die  minimale Distanz   zwischen zwei Codeworten
    $($bei allen Reed–Solomon–Codes gleich  $n-k+1)$.
  4. $q$  gibt einen Hinweis auf die Verwendung des Galoisfeldes  ${\rm GF}(q)$.


Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben:

  1. Bei dieser Realisierung eines RS–Codes wird jedes Informations– und Codesymbol durch  $m$  Bit dargestellt.
  2. Beispielsweise erkennt man aus der ersten Zeile, dass die minimale Distanz hinsichtlich der Bits ebenfalls  $d_{\rm min} = 5$  ist, wenn in  ${\rm GF}(2^m)$  die minimale Distanz  $d_{\rm min} = 5$  beträgt.
  3. Damit können bis zu  $t = 2$  Bitfehler (oder Symbolfehler) korrigiert und bis zu  $e = 4$  Bitfehler (oder Symbolfehler) erkannt werden.



Hinweise:



Fragebogen

1

Es gelte  $c_i ∈ {\rm GF}(2^m)$.  Welche Codeparameter  $n$  ergeben sich?

$m = 4 \text{:} \hspace{0.4cm} n \ = \ $

$m = 5 \text{:} \hspace{0.4cm} n \ = \ $

$m = 6 \text{:} \hspace{0.4cm} n \ = \ $

2

Im Folgenden werden zwei spezielle Reed–Solomon–Codes  ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$  und  ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$  betrachtet.
Mit welchem Parameter  $k$  lassen sich genau  $t$  Symbolfehler korrigeren?

${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ $

${\rm RSC} \ 2 \text{:} \hspace{0.4cm} k \ = \ $

3

Welche Bezeichnungen sind für  $\rm RSC \ 1$  bzw.  $\rm RSC \ 2$  richtig?

$\rm RSC \ 1$  nennt man auch  "$\rm RSC \, (15, \, 7, \, 9)_{16}$".
$\rm RSC \ 1$  nennt man auch  "$\rm RSC \, (15, \, 7, \, 4)_4$".
$\rm RSC \ 2$  nennt man auch  "$\rm RSC \, (31, \, 17, \, 15)_{32}$".
$\rm RSC \ 2$  nennt man auch  "$\rm RSC \, (31, \, 15, \, 17)_{32}$".

4

Wieviele Symbolfehler  $(e)$  können höchstens erkannt werden?

${\rm RSC} \ 1 \text{:} \hspace{0.4cm} e \ = \ $

${\rm RSC} \ 2 \text{:} \hspace{0.4cm}e \ = \ $

5

Wie lauten die betrachteten Codes in Binärschreibweise?

$\rm RSC \ 1$  entspricht dem Code  "$\rm RSC \, (60, \, 28, \, 36)_2$".
$\rm RSC \ 1$  entspricht dem Code  "$\rm RSC \, (60, \, 28, \, 9)_2$".
$\rm RSC \ 2$  entspricht dem Code  "$\rm RSC \, (155, \, 75, \, 17)_2$".
$\rm RSC \ 2$  entspricht dem Code  "$\rm RSC \, (124, \, 60, \, 17)_2$".


Musterlösung

(1)  Für die Codelänge der Reed–Solomon–Codes gilt allgemein:

$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm}, \hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm} m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$


(2)  Um  $t$  Symbolfehler korrigieren zu können,  muss die minimale Distanz mindestens   $d_{\rm min} = 2t + 1$   betragen.

  • Der Reed–Solomon–Code ist ein sogenannter MDS–Code  ("Maximum Distance Separable").  Für diese gilt:
$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}k = n -2t = 2^m - ( 2t+1) \hspace{0.05cm}. $$
  • Damit erhält man für den
  • $\rm RSC \ 1$  $($mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
  • $\rm RSC \ 2$  $($mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.


(3)  Die Bezeichnung eines Reed–Solomon–Codes lautet   ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$   mit  $q = 2^m = n + 1$.  Richtig sind die  Lösungsvorschläge 1 und 4:

  • $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
  • $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.


(4)  Bezeichnet  $d_{\rm min}$  die minimale Distanz eines Blockcodes,  so können damit   $e = d_{\rm min} - 1$   Symbolfehler erkannt und   $t = e/2$   Symbolfehler korrigiert werden:

  • ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$,
  • ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$.


(5)  Richtig sind die beiden mittleren  Lösungsvorschläge 2 und 3:

  • Beim  ${\rm RSC} \ 1 \, \, (m = 4)$  entsprechen  $n = 15$  Codesymbole aus  $\rm GF(2^5)$  gleich  $60$  Bit  und  $k = 7$  Informationssymbole genau  $28$  Bit:
  • $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$,
  • $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$.
  • Für die minimale Distanz auf Bitebene   ⇒   $\rm GF(2)$ ergeben sich mit  $d_{\rm min} = 9$  bzw.  $d_{\rm min} = 17$  die gleichen Werte wie auf Symbolebene  
    ⇒   $\rm GF(2^4)$  bzw.  $\rm GF(2^5)$  $($siehe Theorieteil$)$.