Codierungstheorie

Lineare Codes

 aufwärts

Grundlagen

Definition:  Ein Blockcode C enthalten in boolesche Werten 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 entweder oder y Element C

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

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 in boolesche Werten ein linearer Code. Dann ist der Hamming-Abstand von C gleich dem minimalen Hamming-Gewicht aller von 0 ver­schiedenen Codewörter:

d(C)  =  min{ w(x) |  x Element Cx ≠ 0 }

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

Definition:  Sei C enthalten in boolesche Werten ein linearer Code der Dimension k und sei {b1, ..., bk} eine Basis von C.

Die mit den Basis­vektoren als Zeilen gebildete k × n-Matrix

G  =  eckige Klammer auf
b1
 drei Punkte übereinander   
bk
eckige Klammer zu

heißt Generator­matrix von C.

Die Generator­matrix G erzeugt den Code C, indem alle Produkte von Vektoren aus boolesche Wertek und G gebildet werden:

C  =   { a·G  |   a Element boolesche Wertek }

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

Satz:  Durch elementare Zeilen­umformungen und Spalten­vertauschungen kann G in die systematische Form

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

gebracht werden. Hierbei ist Ik die k × k-Einheits­matrix und P eine k × (n-k)-Matrix. Die Zeilen­umformungen und Spalten­vertauschungen werden repräsentiert durch die Matrizen Z und S. Die Generator­matrix G' erzeugt einen zu C äquivalenten, systematischen Code.

Beispiel:  Die oben genannten Basis­vektoren von C4,3 unter­einander geschrieben ergeben die 3 × 4-Generator­matrix G von C4,3; diese ist bereits in der systematischen Form [I3 P]:

G'  =  G  =  eckige Klammer auf
100 1
010 1
001 1
eckige Klammer zu

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

Fehlererkennung

Ein linearer Code C enthalten in boolesche Werten ist ein Teilraum von boolesche Werten. Die Fehler­erkennung wird mit Hilfe des zugehörigen Orthogonal­raums Corthogonal durchgeführt.

Ein Vektor x Element boolesche Werten gehört zu C genau dann, wenn er zu allen Vektoren von Corthogonal orthogonal ist. Dies ist bereits dann der Fall, wenn x zu allen Basis­vektoren von Corthogonal orthogonal ist. Aus den Basis­vektoren von Corthogonal lässt sich eine Generator­matrix H von Corthogonal bilden. Ist nun x·HT = 0, so ist das Skalar­produkt von x mit allen Basis­vektoren von Corthogonal gleich 0 und damit x zu allen Basis­vektoren von Corthogonal orthogonal.

Definition:  Sei C enthalten in boolesche Werten ein linearer Code und Corthogonal der Orthogonal­raum von C in boolesche Werten. Eine Generator­matrix H von Corthogonal heißt Kontroll­matrix von C.

Satz:  Sei C enthalten in boolesche Werten ein linearer Code mit Kontroll­matrix H. Dann gilt für alle x Element boolesche Werten

x Element C    genau dann wenn    x·HT  =  0

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

Konstruktion einer Kontroll­matrix

Eine Kontroll­matrix H lässt sich aus der Generator­matrix G des linearen Codes konstruieren.

Sei C enthalten in boolesche Werten ein linearer Code mit Generator­matrix G. Zunächst wird G in die systematische Form

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

gebracht. Die Matrix G' ist Generator­matrix eines zu C äquivalenten Codes C'.

Nun ist

H'  =  [PT In-k]

Kontroll­matrix von C'. Durch Rückgängig­machen der durch die Permutationsmatrix S repräsentierten Spalten­vertauschungen ergibt sich eine Kontroll­matrix für den unsprüng­lichen Code C:

H  =  H' · ST

 

Beispiel:  Die Generator­matrix G des Codes C4,3 ist G = [I3 P] mit PT = [1 1 1]. Damit ergibt sich die Kontroll­matrix H = [PT I1] =  [1 1 1 1]. Für x Element boolesche Werten liefert x·HT damit die Parität von x. Ist diese gleich 0, so ist x Element C, ansonsten ist x nicht Element C.

Beim Hamming-Code lässt sich anhand des Syndroms sogar bestimmen, wo der Fehler aufgetreten ist, somit ist hier auch eine Fehler­korrektur möglich.

 

Weiter:   [Hamming-Code]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.03.1997   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik