Skript Teil 3

Dateiinhalt

Lineare Codes
-------------

Es bietet sich an, die 0en und 1en als Elemente des zweielementigen
Koerpers GF(2) verstehen. + = XOR, * = AND. Die Woerter einer festen
Laenge n bilden dann einen Vektorraum ueber diesem Koerper. Man kann
das auch mit allgemeiner fuer andere endliche Koerper tun: hat man
einen endlichen Koerper F, so bilden die Woerter der Laenge n mit
Eintraegen aus F einen n-dimensionalen Vektorraum ueber F.

Definition: Sei F ein endlicher Koerper. Ein linearer Code der Laenge
n ist ein Untervektorraum von F^n.

In einem linearen Code ist es also so, dass die Summe zweier
Codewoerter wieder ein Codewort ist und ebenso auch skalare
Vielfache. Ist F = GF(2), so bedeutet dies, dass die XOR Ueberlagerung
zweier Codewoerter wieder ein Codewort ist.

Lineare Codes bieten eine Menge Vorteile: 

1. Die Zugehoerigkeit zum Code kann durch Multiplikation mit einer
Matrix geprueft werden, diese heisst Kontroll- oder Checkmatrix.

x : C <==> Hx = 0 
(Untervektorraum dargestellt als Kern einer Matrix)

2. Die Codierung kann ebenfalls durch Multiplikation mit einer Matrix
erfolgen, der Generatormatrix G.

x : C <==> x=Gu fuer ein u 

Codierung bildet u auf Gu ab. 

(Untervektorraum dargestellt als Bild einer Matrix mit vollem Spaltenrang)

3. Fehler koennen als Addition eines Fehlervektors aufgefasst werden:
   Das Codewort x wird zum fehlerhaften Wort x' = x+e abgeaendert. e
   ist der Fehlervektor. Es gilt nun H(x') = H(x+e) = He, da Hx=0. Den
   Vektor He bezeichnet man als Syndrom zum Fehler e. Aus dem Syndrom
   kann der Fehler u.U. rekonstruiert werden.

Bevor wir weitermachen, illustrieren wir diese Konzepte am Beispiel des
(7,16,3)-Hamming Codes.

Er hat die Kontrollmatrix 

    0001111
H = 0110011
    1010101

Codewoerter sind alle (Spalten-) Vektoren, die von dieser Matrix
annulliert werden. Addiert man zu so einem Codewort einen
Einheitsvektor (Verfaelschung genau eines Bits), so ergibt sich gerade
dessen Nummer in Binaerdarstellung als Syndrom.

                H (0010000)^T = (011)^T

Insbesondere gehoert zu jedem Syndrom genau ein Fehlervektor mit nur
einem von Null verschiedenen Eintrag (mit "Gewicht" Eins).

Man erhaelt eine Generatormatrix, indem man H durch elementare
Zeilenumformungen auf reduzierte Stufenform bringt (Gauss-Jordan),
dann kann die Generatormatrix abgelesen werden.  Im Beispiel liegt die
reduzierte Stufenform bereits vor:

    0001111
H = 0110011
    1010101
    ^^ ^

Die erforderlichen Einheitsspalten sind markiert. Man erhaelt
dementsprechend die Generatormatrix zu

    1101
    1011
    1000 <
G = 0111
    0100 <
    0010 <
    0001 <
    
Die Generatormatrix hat soviele Einheitszeilen, wie die Kontrollmatrix
Nicht-Einheitsspalten hat, also hier vier. Diese entsprechen den frei
waehlbaren Parametern beim Gleichungssystem Hx=0, also der Dimension
des Kerns. Die drei verbleibenden Werte sind dann so zu waehlen, dass
Hx tatsaechlich Null wird. Dazu muss man die Parameter auf die andere
Seite bringen, das entstehende Minuszeichen sieht man bei GF(2) aber
nicht, da dort ja -1=1 ist. Die Eintraege in der 1., 2., 4. Zeile der
Generatormatrix entsprechen also genau den Zeilen der Kontrollmatrix
vermindert um die Einheitsspalten und entsprechend
zugeordnet. Z.B. findet sich die 1101 der ersten Zeile von G gerade
3. Zeile von H wieder, wenn man die markierten Spalten ignoriert.

Die so erhaltene Generatormatrix erlaubt die Codierung von Woertern
der Laenge vier durch Hinzufuegen von Pruefbits an den Stellen 1,2 und
4. Alternativ kann man, wie in der ersten Vorlesung geschehen, die
Pruefbits am Ende anhaengen; dann entspricht das Syndrom aber nicht
mehr exakt der Binaerdarstellung. Die Kontrollmatrix waere dann z.B.

      0111100
      1011010
      1101001

und die Generatormatrix entsprechend: 

      1000
      0100
      0010
      0001
      0111
      1011
      1101


Allgemeiner Hammingcode: 

Dieses Beispiel zeigt auch, wie der allgemeine Hammingcode konstruiert
wird: Gegeben eine Zahl n (im Beispiel war n=3), schreibt man die
Binaerzahlen von 1 bis 2^n-1 der Reihe nach als Spalten auf und
erhaelt so die Kontrollmatrix der Dimension n x (2^n-1). Durch
Umformung erhaelt man die Generatormatrix der Dimension 2^n-1 x
(2^n-1-n). Sie erlaubt die Aufblaehung einer Botschaft der Laenge
2^n-1-n zu einem Codewort der Laenge 2^n-1 und Fehler vom Gewicht 1
koennen korrigiert werden, da ein entsprechender Fehler gerade seine
Binaerdarstellung als Syndrom hat. Man erhaelt also einen
(2^n-1,2^(2^n-1-n),3)-Code.


Die Anzahl der Codewoerter bei einem linearen Code muss immer eine
Potenz der Kardinalitaet des Koerpers sein, naemlich gerade die
Dimension. Deshalb fuehrt man fuer lineare Codes eine Notation mit
eckigen Klammern ein, die statt der Groesse des Codes nur dessen
Dimension vermerkt. In diesem Sinne waere der Hammingcode ein
[2^n-1,2^n-1-n,3]-Code, bzw in unserem Spezialfall ein [7,4,3]-Code. 

Definition: Das Gewicht w(x) eines Vektors ist die Anzahl der von Null
verschiedenen Eintraege. 

Satz: In einem linearen Code gilt d(C) = min{w(x) | x:C \ {0}}
Beweisskizze: Es ist d(x,y) = w(x-y) und x-y : C \ {0}, wenn x =/= y. 

Definition: Eine Matrix ist t unabhaengig, wenn jede Auswahl von t
Spalten linear unabhaengig ist.

Satz: Ist die Kontrollmatrix H eines linearen Codes t unabhaengig, so
folgt d(C)>t. Umgekehrt ist die Kontrollmatrix eines linearen Codes t
unabhaengig fuer jedes t < d(C).

Beweis: "=>": Sei x=/=0 ein Codewort mit w(x)=a. Da Hx=0 findet man
eine Auswahl von a Spalten von H, die zu 0 kombiniert werden koennen,
also linear abhaengig sind. Daher muss a>t sein.  "<=" Sei jetzt
t<d(C) und eine beliebige Auswahl von t Spalten s1..st vorgelegt. Wenn
l1*s1 + ... ln*st = 0, so folgt Hx = 0 wobei x an der Stelle der
Spalte i den Eintrag li hat und Nullen sonst. Es ist also w(x)<=t und
somit muss x=0 sein.

Satz: Sei C linearer Code mit Minimalabstand d=2e+1. Zu jedem Syndrom
existiert hoechstens ein Fehlervektor vom Gewicht <=
e. (Syndromdecodierung).

Beweis: wird nachgereicht.