Cryptography Reference
In-Depth Information
Das Rekonstruktionsergebnis kann sowohl korrekt als auch falsch sein. Dieser
Kode sollte daher nur Anwendung finden, wenn überwiegend Ein- und Zwei-
fachfehler auftreten.
c) Bei der Binärfolge
b
3
ist das Fehlersyndrom
s
=(011)
T
und
s
0
=0
,d.h.,es
liegt ein erkennbarer, geradzahliger Fehler in
b
3
vor. Dieser kann jedoch nicht
durch Rekonstruktion beseitigt werden. Man erkennt demnach einen Zweifach-
fehler mit Sicherheit.
d) Die Syndrombelegungen für
b
4
sind
s
=
0
und
s
0
=1
, d. h., der Fehler liegt
im Paritätselement. Aus der Kanalkodefolge
b
4
,korr
=(10101010)
entnimmt
man die Quellenkodefolge
b
4
=(1011)
.
Die erweiterten HAMMING-Kodes finden aufgrund der einfachen Kombina-
tion von Fehlererkennung (
f
e
=2
)
und
Fehlerkorrektur (
f
k
=1
) in vielen
Arbeitsspeichertechnologien Anwendung. Auftretende Zweifachfehler (genau-
er: geradzahlige Fehler) führen nicht zu Fehlinterpretationen.
8.4.4
Aufgaben
Abschn. 8.4:
Fehlerkorrigierende HAMMING-Kodes
1. Die Quellenkodewörter des Alphabets
A
∗
, die die Länge
l
haben, sollen durch
einen einfehlerkorrigierenden HAMMING-Kode gesichert werden.
a) Wie viele Kontrollstellen sind erforderlich?
b) Geben Sie an, wie die Kontrollelemente aus den
l
Elementen der Quellenkode-
wörter aus
A
∗
abgeleitet werden!
c) Prüfen Sie die Empfangsfolgen
b
1
=(1010101)
,
=4
2
=(0010110)
,
und korrigieren Sie diese, falls erforderlich!
2. Konstruieren Sie einen erweiterten HAMMING-Kode für
l
b
3
=(1000101)
=7
.
a) Wie berechnen Sie die Kontrollelemente?
b) Geben Sie für
a
∗
=(1010100)
das Kanalkodewort
a
an.
c) Sind die Empfangsfolgen
b
1
=(101101010000)
,b
2
=(101001010110)
,
b
3
=(111001000001)
korrigierbar und damit auch dekodierbar?
3. Für das Erreichen einer gesicherten Übertragung ist ein einfehlerkorrigierender
HAMMING-Kode anzuwenden. Das Quellenalphabet umfasst
200
Zeichen.
a) Berechnen Sie die Parameter
des Kodes. Wieviel Kanalkodewörter
sind im Kodealphabet
A
maximal definiert?
b) Überprüfen Sie das Empfangswort
b
, in Polynomschreibweise
b
(
n,l,d
min
)
x
7
+
x
3
+
x
,
und geben Sie, wenn möglich, das dekodierte, binäre Quellenkodewort
b
∗
an!
Welche Rückschlüsse liefert das Ergebnis hinsichtlich des Fehlermusters?
c) Wie viele Fehlermuster
e
führen auf ein Empfangswort mit
b
=
a ⊕ e ∈ A
?
(
x
)=