Skript Teil 3
skript3a.txt
—
Plain Text,
5 KB (6031 bytes)
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.
Artikelaktionen