Cryptography Reference
In-Depth Information
8.5.5
Fehlerkorrekturverfahren
Das Rekonstruktionsverfahren geht auf PETERSON (1960, für die Klasse bi-
närer Kodes) und ZIERLER-GORENSTEIN (1961, für nichtbinäre BCH- und
RS-Kodes) zurück und wird in der Literatur kurz als PZG-Verfahren bezeich-
net. Die Anwendung ist nur für kleine Fehlerkorrekturgrade (
f
k
≤
6
) sinnvoll.
Der Durchbruch für die praktische Anwendung von BCH- und RS-Kodes wurde
mit den Verfahren nach BERLEKAMP-MASSEY (1969) und EUKLID (1975)
erzielt.
Die Verfahren basieren auf dem Vorhandensein/Nichtvorhandensein der Auf-
einanderfolge der Nullstellen im Empfangspolynom
b
(
x
)
. Für jedes Kodepo-
lynom
a
(
x
)
gilt:
a
(
x
=
α
j
)=0(
j
=1
,
2
, ...,
2
f
k
)
,
μ
=1
vorausgesetzt. Die
Überlagerung von
a
(
x
)
durch ein Fehlerpolynom
e
(
x
)
, das nicht die Struktur
eines Kodepolynoms besitzt, führt auf ein Empfangspolynom
b
(
x
)
, welches die
notwendige Nullstellenfolge nicht enthält.
Der
Korrekturalgorithmus
hat die folgenden Bearbeitungsschritte:
0.
r
(
x
)=
b
(
x
)
mod
g
(
x
)=0?
Fehlerkorrektur
1.
Berechnung der Fehlersyndrome des Empfangspolynoms
2.
Bestimmung des Lokator- bzw. Fehlerstellenpolynoms aus den Fehlersyn-
dromen (PZG-, BERLEKAMP-MASSEY-(BM-) oder EUKLID-Verfahren)
3.
Bestimmung der Fehlerstellen im Empfangspolynom aus dem Lokatorpoly-
nom
4.
nur für RS-Kodes:
Berechnung des Fehlerwertes jeder Fehlerstelle.
nein:
b/
∈
A
−→
Das folgende Bild stellt den Ablauf schematisch dar:
Im Abschn. 8.5.5.1 soll zunächst die Fehlerkorrektur von BCH-Kodes auf der
Basis des PZG-Verfahrens gezeigt werden. Die Fehlerkorrektur von RS-Kodes
baut auf den Beziehungen für BCH-Kodes auf. Darüber hinaus ist ein 4. Schritt
zur Fehlerwertberechnung erforderlich (s. Abschn. 8.5.5.2). Abschn. 8.5.5.3
setzt sich dann mit der Auslöschungskorrektur auseinander. Im Abschn. 8.5.5.4
werden die Verfahren nach BERLEKAMP-MASSEY und EUKLID beschrie-
ben.
