Aufgabe 2.10Z: Coderate und minimale Distanz

• Zurück zum Buch

Die beiden Erfinder der Reed–Solomon–Codes

Die von  »Irving Stoy Reed«  und  »Gustave Solomon«  Anfang der 1960er Jahre entwickelten Codes werden in diesem Tutorial wie folgt bezeichnet:

$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$

Die Codeparameter haben folgende Bedeutungen:

• $q = 2^m$  ist ein Hinweis auf die  Größe des Galoisfeldes   ⇒   ${\rm GF}(q)$,

• $n = q - 1$  ist die  Codelänge  $($Symbolanzahl eines Codewortes$)$,

• $k$  gibt die  Dimension  an  $($Symbolanzahl eines Informationsblocks$)$,

• $d_{\rm min}$  bezeichnet die  minimale Distanz  zwischen zwei Codeworten. 

• Für jeden Reed–Solomon–Codes gilt 

$$d_{\rm min} = n - k + 1.$$

Mit keinem anderen Code mit gleichem  $k$  und  $n$  ergibt sich ein größerer Wert.

Hinweise:

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

• Die für diese Aufgabe relevanten Informationen finden Sie auf der Seite  "Codebezeichnung und Coderate".

Fragebogen

1

Geben Sie die Kenngrößen des  ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$  an.

$q \hspace{0.2cm} = \ $

$e \hspace{0.2cm} = \ $

$t \hspace{0.2cm} = \ $

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

2

Geben Sie die Kenngrößen des  $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$  an.

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

3

Wieviele Bitfehler  $(N_3)$  darf ein Empfangswort  $\underline{y}$  maximal aufweisen,  damit es  mit Sicherheit richtig decodiert wird?

$N_{3} \ = \ $

4

Wieviele Bitfehler  $(N_4)$  darf ein Empfangswort  $\underline{y}$  im günstigsten Fall  aufweisen,  damit es noch  richtig decodiert werden könnte?

$N_{4} \ = \ $

Musterlösung

Musterlösung

(1)  Aus der Codelänge  $n = 255$  folgt  $q \ \underline{= 256}$.

• Die Coderate ergibt sich zu  $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$

• Die minimale Distanz beträgt  $d_{\rm min} = n - k +1 = 255 - 223 +1 \hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$

• Damit können

• $e = d_{\rm min} - 1 \ \underline{= 32}$  Symbolfehler erkannt werden,  und

• $t = e/2$  $($abgerundet$)$,  also  $\underline{t = 16}$  Symbolfehler korrigiert werden.

(2)  Der Code  $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$  ist die Binärrepräsentation des unter (1) behandelten   ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_{256}$ 

• Dieser hat genau die gleiche Coderate  $R \ \underline{= 0.8745}$ und ebenfalls gleiche Minimaldistanz  $d_{\rm min} \ \underline{= 33}$.

• Hier werden pro Codesymbol  $8$  Bit   ⇒   $1$  Byte verwendet.

(3)  Aus  $d_{\rm min} = 33$  folgt wieder  $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$.

• Ist in jedem Codesymbol genau ein Bit verfälscht,  so bedeutet dies gleichzeitig auch  $16$  Symbolfehler.

• Dies ist der maximale Wert,  den der Reed–Solomon–Decoder noch verkraften kann.

(4)  Der RS–Decoder kann  $16$  verfälschte Codesymbole korrigieren.

• Dabei ist es egal,  ob in einem Codesymbol nur ein Bit oder alle  $m = 8$  Bit verfälscht wurden.
• Deshalb können bei der günstigsten Fehlerverteilung bis zu  $N_4 = 8 \cdot 16 \ \underline{= 128}$  Bit verfälscht sein,  ohne dass das Codewort falsch decodiert wird.