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