Cryptography Reference
In-Depth Information
8.3
Lineare Blockkodes
8.3.1
Begriffsbestimmung
Definition 8.3.1
Ein Kode heißt
linearer Blockkode
,oderkurzLinear-
kode, wenn der Kanalkodierer für die Transformation von Quellenkodewör-
tern der Länge
l
aus dem Alphabet
A
∗
(Quellenkode) in Kanalkodewörter der
Länge
n
des Alphabets
A
(Kanalkode) nur Operationen verwendet, die in der
algebraischen Struktur einer Gruppe definiert sind.
Die lineare Verknüpfung von Kanalkodewörtern führt dann wieder zu einem
Kanalkodewort. Das Nullwort ist immer auch Kanalkodewort.
l
Kanalkodewörtern und
einer minimalen HAMMING-Distanz
d
min
ist ein
(
n, l, d
min
)
Kanalkode
A
Ein Linearkode der Länge
n
=
l
+
k
mit
L
=2
⊂
n
.
{
0
,
1
}
Bei der Fehlerkorrektur durch Wiederholung sind mit Sicherheit
f
e
=
d
min
−
1
Fehlerstellen erkennbar und durch Rekonstruktion
f
k
=
d
min
−
1
2
Fehlerstellen
korrigierbar. Bei mehr als
f
k
erkannten Fehlern findet entweder eine Falsch-
korrektur statt oder es kommt zu Rekonstruktionsversagen.
8.3.2
Darstellung von Linearkodes als Gruppen
Betrachten wir die Kanalkodewörter aus
A
als
Elemente einer Gruppe
und
nehmen wir für die Verknüpfungsoperation die mit
bezeichnete stellenwei-
se Modulo-2-Addition, so gelten für diese die bekannten Gruppenaxiome (s.
Abschn. Algebraische Strukturen und Vektorräume). Zusätzlich erfüllen die
Kanalkodewörter das Kommutativgesetz
a
i
⊕
⊕
A
und bilden damit eine
abelsche Gruppe
.
a
j
=
a
j
⊕
a
i
mit
a
i
,a
j
∈
Beispiel 8.3.1
Das Kodealphabet
A
bestehe aus den Kanalkodewörtern
a
0
=(00000)
a
1
=(10010)
a
2
=(01011)
a
3
=(00101)
a
4
=(11001)
a
5
=(10111)
a
6
=(01110)
a
7
=(11100)
.
Es ist zu zeigen, dass dieser Kode die Gruppenaxiome erfüllt.
Lösung:
Axiom G1: Abgeschlossenheit
