Cryptography Reference
In-Depth Information
Beispiel 8.5.15
Für
l
=4
und
g
(
x
)=
m
0
(
x
)=
x
+1
ist das Kodealphabet
A
zu beschreiben.
Lösung:
Mit
k
=
grad
g
(
x
)=1
ist die Gesamtkodewortlänge
n
=5
. Die Anwendung
des Multiplikationsverfahrens (s. Abschn. 8.5.2.2) führt auf das folgende Kode-
alphabet
A
:
i a
i
a
i
0 0000 00000
1 0001 00011
2 0010 00110
3 0011 00101
4 0100 01100
5 0101 01111
6 0110 01010
7 0111 01001
i a
i
a
i
8 1000 11000
9 1001 11011
10 1010 11110
11 1011 11101
12 1100 10100
13 1101 10111
14 1110 10010
15 1111 10001
Anhand der Gewichtsverteilung in
A
ist
d
min
=2
.
Alle Kanalkodewörter ha-
ben geradzahliges Gewicht. Das Ergebnis ist ein
(5
,
4
,
2)
Kode.
Mit
m
0
(
x
)
in
g
(
x
)
werden immer Kanalkodewörter mit geradzahligem Gewicht
gebildet. Alle ungeradzahligen Fehler sind somit erkennbar.
Ist
m
0
(
x
)
nicht Bestandteil von
g
(
x
)
, werden die Parameter eines bestehenden
Kodes mit „Erweiterung“ um
m
0
(
x
)
wie folgt beeinflusst:
(
n, l −
1
,d
min
+1)
.
Die Verbesserung der Erkennbarkeit wird durch den Verlust einer Informati-
onsstelle erkauft. Für einen verkürzten Kode mit
n<p
ändert sich die Gesamt-
kodewortlänge und damit die Beschreibung in
(
n
+1
,l,d
min
+1)
. Die zyklische
Eigenschaft bleibt erhalten, solange
n
=
p
gilt.
Eine andere Möglichkeit ist die Erweiterung um eine Paritätsstelle (s. Abschn.
8.4.3) über die
n
=
p
Kodewortstellen, natürlich vorausgesetzt, dass
m
0
(
x
)
nicht Bestandteil von
g
(
x
)
ist. Es entsteht ein erweiterter
(
n
+1
,l,d
min
+1)
BCH-Kode. Die Rekonstruktion erfolgt zunächst unabhängig von der erwei-
terten Paritätsstelle. Anschließend wird über die Paritätssummen
s
0
, gebildet
über die
(
n
+1)
-Empfangsfolge, und
s
1
, gebildet über die rekonstruierte
n
-
Folge, auf Korrektur oder Rekonstruktionsversagen entschieden. Ein typischer
Vertreter ist auch der erweiterte
(24
,
12
,
8)
GOLAY-Kode
19
.
19
Bei einem geradzahligen Fehler ist
s
0
=0
. Bei einem Vierfachfehler in der um die Pa-
ritätsstelle verkürzten Empfangsfolge ändert der Korrekturalgorithmus (s. S. 203) drei
zusätzliche Bits, um das nächste Kodewort zu erhalten, welches einen Abstand von ins-
gesamt sieben zum Originalkodewort hat. Das heißt aber, insgesamt wurden sieben Bits
verändert und damit ist
s
1
=1
.
Die Auswertung der Paritätssummen (
s
0
=0
,s
1
=1
)
verhindert eine Falschkorrektur und entscheidet auf Rekonstruktionsversagen.
Ein Vierfachfehler mit einem der Fehler im Paritätsbit wird dagegen korrekt dekodiert
(
s
0
=0
,s
1
=0
).