Aufgaben: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, \, 33)_{256}$ mit genau der gleichen Coderate $R \ \underline{= 0.8745}$ und ebenfalls gleicher Minimaldistanz $d_{\rm min} \ \underline{= 33}$ wie dieser. 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,

• wobei es egal ist, 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.