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, \, 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.