Aufgaben:Aufgabe 2.09: Reed–Solomon–Parameter

• Zurück zum Buch

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:

• Die Aufgabe gehört zum Kapitel  "Definition und Eigenschaften von Reed–Solomon–Codes".

• Bezug genommen wird aber auch auf das Kapitel  "Erweiterungskörper".

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

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

• 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:

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