Cryptography Reference
In-Depth Information
8.5
Zyklische Kodes
Definition 8.5.1
Ein Kode heißt
zyklisch
, wenn durch zyklische Verschie-
bung eines Kanalkodeworts um
z
Stellen wieder ein Kanalkodewort entsteht:
a
j
(
x
)=
a
i
(
x
)
x
z
mod
(
x
n
+1)
.
11
(8.25)
Ein zyklischer Kode ist ein spezieller Linearkode, der Körperaxiome und da-
mit auch Gruppen- und Ringaxiome erfüllt.
Die Beschreibung zyklischer Kodes soll anhand der Klasse der BCH-Kodes
(Elemente in
GF
(2)
) und der RS-Kodes (Elemente in
GF
(2
k
1
)
) erfolgen. Das
heißt jedoch nicht, dass die Gültigkeit der folgenden Ausführungen auf diese
Kodeklassen und dessen
GF
-Beschränkung begrenzt ist.
Im Gegensatz zu den Kodeklassen, mit denen wir uns bisher beschäftigt ha-
ben, lassen sich die nach BOSE, CHAUDHURI (1960) und HOQUENGHEM
(1959) benannten BCH-Kodes und die nach REED und SOLOMON (1960)
benannten RS-Kodes für einen beliebig vorgebbaren Entwurfsabstand
d
E
,be-
stimmt von der Vorgabe eines beliebigen Grades der Fehlererkennung (
f
e
,Gl.
(8.6)) oder der Fehlerkorrektur (
f
k
, Gl. (8.7)), konstruieren.
Für alle zyklischen Kodes ist das sogenannte
Generatorpolynom
von funda-
mentaler Bedeutung.
Das Generatorpolynom
g
(
x
)
ist i. Allg. ein Produkt von irreduziblen Mini-
malpolynomen
m
i
(
x
)
. Es beschreibt den zyklischen Kode, d. h., die Menge
seiner Kodewörter vollständig.
Für die Beschreibung zyklischer Kodes sind verschiedene Begriffe der Alge-
bra, wie Erweiterungskörper, Minimalpolynome usw. notwendig. Diese werden
im Abschn. 8.5.1 erklärt. Im Abschn. 8.5.2 folgen Verfahren zur Bildung des
Kanalkodealphabets (Kodierung) und das Prinzip der Fehlererkennung, wo-
bei zunächst die Kenntnis eines Generatorpolynoms vorausgesetzt wird. Diese
Zusammenhänge gelten für alle zyklischen Kodes. In den Abschn. 8.5.3 und
8.5.4 werden dann für beliebig vorgebbare Leistungsfähigkeit die Konstruk-
tionsprinzipien für Generatorpolynome von BCH- und RS-Kodes dargestellt.
Abschn. 8.5.5 beschäftigt sich im Weiteren mit unterschiedlichen Verfahren der
Fehlerkorrektur von zyklischen Kodes.
11
Die Restbildung ersetzt die durch Multiplikation mit
x
z
berechneten Exponenten
r ≥ n
durch
r
mod
n.
