Cryptography Reference
In-Depth Information
8.5.5.2 Fehlerkorrektur von RS-Kodes
Die Fehlerkorrektur von RS-Kodes erfordert zunächst auch die Ausführung der
Bearbeitungsschritte 1. - 3. (s. Abschn. 8.5.5.1). Die nichtbinäre Eigenschaft
dieser Kodes führt zu einem weiteren Bearbeitungsschritt:
4. Berechnung des Fehlerwertes jeder Fehlerstelle
An den Fehlerstellen exp(
x
i
) im Fehlerpolynom
e
(
x
)
sind die Fehlerwerte
y
i
zu berechnen. Im binären Fall (BCH-Kodes) sind die Fehlerwerte
y
i
=1
.Für
den nichtbinären Fall, wie bei den RS-Kodes, sind die Fehlerwerte
y
i
über den
bereits bekannten Zusammenhang (Gl. (8.38), hier für
y
i
∈
k
1
GF
(2
)
)
ν
y
i
x
i
s
j
=
(
j
=1
,
2
, ..., ν
≤
f
k
)
(8.41)
i
=1
zu bestimmen.
(Diese recht anschauliche Berechnung ist nur e
zient und praktikabel für kleine
Werte von
f
k
. Sie stellt eine Alternative zum FORNEY-Algorithmus dar, u. a.
[BOS 98].)
Mit dem Fehlerpolynom
e
(
x
)=
y
ν
x
exp(
x
ν
)
+
y
ν−
1
x
exp(
x
ν−
1
)
+
...
+
y
1
x
exp(
x
1
)
kann das Empfangspolynom mit
b
korr
(
x
)=
b
(
x
)+
e
(
x
)
korrigiert werden.
Beispiel 8.5.20
Gegeben sei ein RS-Kode über
GF
(2
3
)
/x
3
+
x
+1
mit
d
min
=3
.
Das Kodepolynom
a
(
x
)=
α
5
x
6
+
α
5
x
5
+
α
6
x
4
+
α
0
x
3
+
α
5
x
2
+
α
2
x
+
α
5
wird
nach einer gestörten Übertragung als
b
(
x
)=
α
5
x
6
+
α
3
x
5
+
α
6
x
4
+
α
0
x
3
+
α
5
x
2
+
α
2
x
+
α
5
empfangen. Dieses Empfangspolynom ist zu korrigieren.
Lösung:
0.
b/
A
1.
s
1
=
b
(
x
=
α
1
)=
α
4
+
α
+
α
3
+
α
3
+1+
α
3
+
α
5
=1
,
s
2
=
b
(
x
=
α
2
)=
α
3
+
α
6
+1+
α
6
+
α
2
+
α
4
+
α
5
=
α
5
.
2.
s
1
σ
1
=
s
2
−→
∈
α
5
1
=
α
5
σ
(
x
)=
x
+
σ
1
=
x
+
α
5
=(
x
+
x
1
)
3.
x
1
=
α
5
e
(
x
)=
y
1
x
5
4.
s
1
=
y
1
x
1
−→
σ
1
=
α
0
y
1
=
α
5
=
α
2
e
(
x
)=
α
2
x
5
b
korr
(
x
)=
b
(
x
)+
e
(
x
)=
a
(
x
)
,a
=(
α
5
α
5
α
6
α
0
α
5
α
2
α
5
)
.