Cryptography Reference
In-Depth Information
Abstand der Exponenten von α i der aufeinanderfolgenden Nullstellen ist be-
liebig wählbar, muss aber konstant sein. Beispiele findet man bei ATM mit
123
143
g ( x )=
( x + α i
) oder im NASA-Standard mit g ( x )=
( x + α 11 i
) .
i =120
i =112
Im Weiteren sei für μ und für den Abstand der Exponenten jeweils Eins ange-
nommen.
Die Kodeparameter eines RS-Kodes leiten sich aus bereits von BCH-Kodes be-
kannten Zusammenhängen ab. Das primitive Modularpolynom bestimmt die
realisierbare Kodewortlänge mit n =2
k 1
1 .IndiesemFallsindes n Elemente,
darstellbar in n·k 1 Bit . Die Anzahl der Kontrollelemente hängt vom Grad des
Generatorpolynoms mit k = grad g ( x ) ab. Damit können maximal l = n − k
Informationselemente kanalkodiert werden.
Zur Abschätzung von Kodeparametern gibt es verschiedene Schranken. So wird
neben der HAMMING-Schranke (s. Abschn. 8.1.3, S. 136) die SINGLETON-
Schranke mit
k ≥ d min 1 .
(8.34)
benutzt. Der RS-Kode ist neben trivialen binären Kodes 20 der einzige Kode,
der diesen Zusammenhang mit Gleichheit erfüllt. Man bezeichnet diesen Kode
deshalb auch als MDS[maximum distance separable]-Kode .
Damit lässt sich das Gewicht der Kanalkodewörter 21 auch wie folgt ausdrücken:
w ( a i ) ≥ k +1 für alle a i ∈ A \{a 0 }
.
Mit d min =2 f k +1 und k = d min 1 hängt damit der Fehlerkorrekturgrad
unmittelbar von k ab:
k
2
f k =
.
(8.35)
k
2
Der RS-Kode ist damit in der Lage, mit Sicherheit
Einzelfehler zu je k 1 Bit
k
oder Bündelfehler der Länge ((
2 1) k 1 +1) Bit zu korrigieren.
Folgendes Beispiel zeigt die Bildung eines RS-Kodes. Für das Rechnen mit
nichtbinären Koe zienten sei auch auf die Fußnote 13, S. 166 verwiesen.
20 Es handelt sich dabei um die folgenden
( n,l,d min )
Kodes:
( n, 1 ,n )
Wiederholungskode,
Quellenkode.
21 Erwähnenswert: Nur für wenige Kodes existiert ein Zusammenhang zur Berechnung der
Gewichtsverteilung eines Kanalkodes (eine experimentelle Untersuchung bietet sich nur
für kurze Kodes an). Für RS-Kodes kann die Anzahl w i der Kodewörter mit dem Gewicht
i wie folgt berechnet werden [PEW 91]:
( n,n − 1 , 2)
Paritätskode,
( n,n, 1)
n
i
i− 1 −k
( 1) j i
j
((2 k 1 ) i−j−k 1) ( i = k +1 ,k +2 , ..., n ) ,w 0 =1 ,w 1 , 2 ,...,k =0 .
w i =
j =0
Search WWH ::




Custom Search