Aufgaben:Exercise 2.10Z: Code Rate and Minimum Distance

• Return to book

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

Solution

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