Codierungstheorie

Lineare Codes

Definition: Ein Blockcode C enthalten boolesche Menge ⁿ heißt linearer Code, wenn die Summe zweier Codewörter wieder ein Codewort ist, d.h. wenn gilt

für alle x, y Element C : x Exklusiv-Oder y Element C

C bildet damit einen Vektorraum, und zwar einen Teilraum des Vektorraums boolesche Menge ⁿ.

Beispiel: Der 3-Bit-Binärcode mit Paritätsbit C4,3 ist ein linearer Code:

0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Die Menge T = {1 0 0 1, 0 1 0 1, 0 0 1 1} ist eine Basis von C4,3. Somit hat C4,3 die Dimension 3.

Satz: Sei C enthalten boolesche Menge ⁿ ein linearer Code. Dann ist der Hamming-Abstand von C gleich dem minimalen Hamming-Gewicht aller von 0 verschiedenen Codewörter:

d(C) = min{ w(x) | x Element C, x ungleich 0 }

Der obige lineare Code C4,3 hat den Hamming-Abstand 2, da alle von 0 verschiedenen Codewörter mindestens das Hamming-Gewicht 2 haben, d.h. mindestens 2 Einsen enthalten.

Definition: Sei C enthalten boolesche Menge ⁿ ein linearer Code der Dimension k und sei {b₁, ..., b_k} eine Basis von C.

Die mit den Basisvektoren als Zeilen gebildete k kreuz n-Matrix

G =

b₁

b_k

heißt Generatormatrix von C.

Die Generatormatrix G erzeugt den Code C, indem alle Produkte von Vektoren aus boolesche Menge ^k und G gebildet werden:

C = { a·G | a Element boolesche Menge ^k }

Anders ausgedrückt ist C der Zeilenraum der Matrix G.

Satz: Durch elementare Zeilenumformungen und Spaltenvertauschungen kann G in die systematische Form

G' = Z·G·S = [ I_k P ]

gebracht werden. Hierbei ist I_k die k kreuz k-Einheitsmatrix und P eine k kreuz (n-k)-Matrix. Die Zeilenumformungen und Spaltenvertauschungen werden repräsentiert durch die Matrizen Z und S. Die Generatormatrix G' erzeugt einen zu C äquivalenten, systematischen Code.

Beispiel: Die oben genannten Basisvektoren von C4,3 untereinander geschrieben ergeben die 3 kreuz 4-Generatormatrix G von C4,3; diese ist bereits in der systematischen Form [I₃ P]:

G' = G =

1	0	0	1
0	1	0	1
0	0	1	1

Satz: Sei C enthalten boolesche Menge ⁿ ein linearer Code der Dimension k. Dann ist C ein (n, k)-Code.

Ein linearer Code C enthalten boolesche Menge ⁿ ist ein Teilraum von ⁿ. Die Fehlererkennung wird mit Hilfe des zugehörigen Orthogonalraums C^{^} durchgeführt.

Ein Vektor x Element boolesche Menge ⁿ gehört zu C genau dann, wenn er zu allen Vektoren von C^{^} orthogonal ist. Dies ist bereits dann der Fall, wenn x zu allen Basisvektoren von C^{^} orthogonal ist. Aus den Basisvektoren von C^{^} lässt sich eine Generatormatrix H von C^{^} bilden. Ist nun x·H^T = 0, so ist das Skalarprodukt von x mit allen Basisvektoren von C^{^} gleich 0 und damit x zu allen Basisvektoren von C^{^} orthogonal.

Definition: Sei C enthalten boolesche Menge ⁿ ein linearer Code und C^{^} der Orthogonalraum von C in ⁿ. Eine Generatormatrix H von C^{^} heißt Kontrollmatrix von C.

Satz: Sei C enthalten boolesche Menge ⁿ ein linearer Code mit Kontrollmatrix H. Dann gilt für alle x Element ⁿ

x Element C genau dann wenn x·H^T = 0

Das Produkt x·H^T wird als das Syndrom von x bezeichnet. Ist das Syndrom ungleich 0, so ist ein Fehler aufgetreten.

Konstruktion einer Kontrollmatrix

Eine Kontrollmatrix H lässt sich aus der Generatormatrix G des linearen Codes konstruieren.

Sei C enthalten boolesche Menge ⁿ ein linearer Code mit Generatormatrix G. Zunächst wird G in die systematische Form

G' = Z · G · S = [I_k P]

gebracht. Die Matrix G' ist Generatormatrix eines zu C äquivalenten Codes C'.

Nun ist

H' = [P^T I_n-k]

Kontrollmatrix von C'. Durch Rückgängigmachen der durch die Permutationsmatrix S repräsentierten Spaltenvertauschungen ergibt sich eine Kontrollmatrix für den unsprünglichen Code C:

H = H' · S^T

Beispiel: Die Generatormatrix G des Codes C4,3 ist G = [I₃ P] mit P^T = [1 1 1]. Damit ergibt sich die Kontrollmatrix H = [P^T I₁] = [1 1 1 1]. Für x Element boolesche Menge ⁿ liefert x·H^T damit die Parität von x. Ist diese gleich 0, so ist x Element C, ansonsten ist x nicht Element C.