Aufgabe 2.10Z: Coderate und minimale Distanz

Aus LNTwww
Wechseln zu:Navigation, Suche

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:



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

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