Cryptography Reference
In-Depth Information
d
min
;
f
k
;
S
(
x
);
ρ
;
U
ρ
=0
i
=1
(1 +
x
i
· x
)
r
−
1
(
x
):=
x
d
min
−
1
;
r
0
(
x
):=(
S
(
x
)
· u
(
x
))
ρ
u
(
x
):=1
u
(
x
):=
x
d
min
−
1
w
−
1
(
x
):=0;
w
0
(
x
):=
u
(
x
);
i
:= 0
r
i
(
x
)
≥
2
f
k
+
ρ
2
i
:=
i
+1
r
i
(
x
):=
r
i
−
2
(
x
)
r
i
−
1
(
x
)
r
i
−
1
(
x
)
w
i
(
x
):=
w
i
−
2
(
x
)+
q
(
x
)
· w
i
−
1
(
x
)
Λ(
x
)
EUKL
:=
w
i
(
x
)
·
q
(
x
):=
r
i
−
2
(
x
)
1
w
i,
0
;
ν
:=
w
i
(
x
)
− ρ
Λ(
x
)
EUKL
;
ν
Beispiel 8.5.24
BM- und EUKLID-Algorithmus ermöglichen bei Eingabe von Auslöschungs-
stellen auch die Suche nach weiteren zufällig aufgetretenen Fehlern.
Für einen
(7
,
3
,
5)
RS-Kode
(
GF
(2
3
)
/x
3
+
x
+1)
liegt eine Empfangsfolge
b
=(
α
2
0
α
5
0
α
4
0
α
2
)
mit
U
=(
α,α
3
)
vor. Es ist zunächst das Lokatorpolynom
bei Anwendung des EUKLID-Algorithmus zu bestimmen.
Lösung:
0.
Prüfung entfällt, da
U
gegeben
1.
s
1
=
α
5
,s
2
=
α,s
3
=1
,s
4
=
α
6
−→ S
(
x
)=
α
6
x
3
+
x
2
+
αx
+
α
5
2.
Abarbeitungsprotokoll:
i
r
i
(
x
)
q
(
x
)
w
i
(
x
)
u
(
x
)
α
4
x
2
+
x
+1
-1
x
4
0
α
3
x
3
+
α
5
x
2
+
α
6
x
α
5
α
4
x
2
+
+
x
+1
0
α
6
x
2
+
α
3
x
α
4
α
4
x
α
6
αx
3
+
α
6
x
2
+
α
3
x
α
6
1
+
+
+
−→
Ausgabe:
Λ(
x
)
EUKL
=(
αx
3
+
α
6
x
2
+
α
3
x
+
α
6
)
α
−
6
=1+
α
4
x
+
x
2
+
α
2
x
3
ν
=3
−
2=1
.
Der Berechnung des Lokatorpolynoms folgt dann wieder die Nullstellensuche
(
3.
Schritt des Korrekturalgorithmus):
Dazu bietet es sich an,
Λ(
x
)
BM/EUKL
=1+Λ
1
x
+Λ
2
x
2
+
...
+Λ
ν
x
ν
in die
Struktur von
σ
(
x
)
=
x
ν
+
σ
1
x
ν
−
1
+
...
+
σ
ν
−
1
x
+
σ
ν
zu
transformieren
.