Skript Teil 4

Dateiinhalt

Hier noch einmal der Nachtrag zur Syndromdekodierung. 

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

Beweis: Sei x ein Codewort und x1=x+e1 und x2=x+e2 zwei Woerter, wobei
w(e1) <= e und w(e2)<=e. Ausserdem sei H e1 = H e2. Es sind e1 und e2
zwei Fehlervektoren vom Gewicht <=e und mit demselben Syndrom (NB: H
x1 = H e1 = H e2 = H x2). Es ist H (e1-e2) = 0 und w(e1-e2) <= 2e, da
man ja, um von e1 zu e2 zu gelangen, schlimmstenfalls alle Bits, die
in e1 gesetzt sind, auf 0 setzen muss und dann alle in e2 gesetzten
auf Eins setzen muss. Somit muss e1-e2=0 sein, denn 0:C, und es ist
e1=e2. []

Man kann also zu jedem Syndrom in einer Tabelle einen entsprechenden
Fehlervektor vom minimalen Gewicht auflisten und dann zur effizienten
Dekodierung einfach diese Tabelle verwenden. Man spricht dann von
Syndromdekodierung.


Blockcodes ueber beliebigem Alphabet
------------------------------------

Wir verallgemeinern die Definition und Theorie der Blockcodes auf
groessere Alphabete als nur {0,1}. Dies erlaubt es uns, lineare Codes
ueber einem anderen Koerper als GF(2) als Blockcodes aufzufassen
(implizit bereits geschehen). Ein Blockcode der Laenge n ueber einem
Alphabet Sigma besteht also aus Woertern ueber Sigma der Laenge
n. Insbesondere ist ein linearer [n,k,d]_q Code dann ein
(q^n,k,d)-Blockcode ueber einem Alphabet der Groesse q. Der
Hammingabstand zweier solcher Woerter ist wiederum die Zahl der
Positionen, an denen sie sich unterscheiden. Die Kugelpackungsschranke
und die Singleton-Schranke gelten sinngemaess fort:

Satz (verallgemeinerte Kugelpackungsschranke): Sei C ein Code der
Laenge n ueber einem Alphabet Sigma mit |Sigma|=q und mit
Minimaldistanz d>=2e+1 fuer e:N. Es gilt:

q^n >= |C| * sum_{i=0}^e binom(n,i)

Beweis: die Anzahl aller moeglichen Woerter ist q^n. Der Rest des
Beweis geht wie im Fall q=2.

Satz (verallgemeinerte Singleton Schranke): Ist C ein Code der
Minimaldistanz d+1 ueber einem Alphabet Sigma mit |Sigma|=q, so gilt:
log(|C|) <= (n-d) * log(q).

Beweis: wie der Beweis fuer q=2 unter Beachtung der Rechenregel
log_q(x)=log(x)/log(q).

Zur Beachtung: oft sind die Alphabetgroessen q Zweierpotenzen, also
q=2^k. Man repraesentiert Woerter der Laenge n ueber einem solchen
Alphabet dann gerne als Woerter der Laenge nk ueber {0,1}, wobei sich
die Alphabetsymbole durch 0-1-Woerter der Laenge k codiert verstehen
und diese Codierungen einfach hintereinandergeschrieben werden. Der
Hammingabstand zweier Woerter entspricht dann aber nicht der Zahl der
Bits an denen sie sich unterscheiden, sondern vielmehr der Zahl der
k-Bloecke, in denen mindestens ein Fehler aufgetreten ist.

Beispiel: Ist Sigma={a,b,c,d} und wird die Codierung a->00, b->01,
c->10, d->11 zugrundegelegt, so entspricht 001011 dem Wort acd und
110011 dem Wort dad. Diese haben den Abstand 2, obwohl sich die
Bitfolgen an drei Positionen unterscheiden.



Satz von Varsamov
-----------------

Als Anwendung der Charakterisierung des Minimalabstandes durch
t-Unabhaengigkeit bringen wir jetzt den Satz von Varsamov, der ein
Konstruktionsprinzip fuer Codes mit groesseren Distanzen liefert. 


Satz (Varsamov)
Seien n,k,d natuerliche Zahlen mit d<=n. Gilt 
 
 V_q^{n-1}(d-2)<q^{n-k}
 
 dann existiert ein linearer [n,k,d]_q-Code.
                                            ( n-1 )
 Dabei ist V_q^{n-1}(d-2) = Sum_{i=0}^{d-2} (  i  ) (q-1)^i
 das Volumen der n-1 dimensionalen Kugel vom Radius d-2.


Bemerkung
  Die Kugelpackungsschranke liefert uns, dass fuer einen linearen
  [n,k,d]_q-Code gelten muss, dass

  V_q^n([(d-1)/2]) <= q^{n-k}

  Dieser Satz betrachtet also Kugeln mit (nahezu) dem doppelten 
  Radius (dafuer aber in einer Dimension weniger). Insbesondere
  sichert dieses Resultat *nicht* die Existenz perfekter Codes.

Beweis (Satz von Varsamov)
  Es genuegt, die Existenz einer d-1 unabhaengigen (n-k) x n Matrix zu
  zeigen. Diese Matrix wird dann als Check Matrix fungieren (was in
  der Tat zu einem mindestens n - (n-k) dimensionalen Coderaum
  fuehrt).

  Wir fuegen die einzelnen Spalten schrittweise hinzu, und zwar so,
  dass wir die (d-1)-Unabhaengigkeit nicht verletzen. Wir koennen
  einen weiteren weiteren Spaltenvektor hinzufuegen, wenn er sich
  nicht als Linearkombination von hoechstens d-2 der vorhanden
  Vektoren schreiben laesst. Es gibt q^{n-k} moegliche Spaltenvektoren
  der Laenge (n-k). Wenn wir schon i-1 < n Spalten haben dann
  verbieten sich folgende Vektoren.

  - Linearkombinationen mit genau 0 von 0 verschiedenen Koeffizienten:
    ein Vektor (der Nullvektor)

  - Linearkombinationen mit genau 1 von 0 verschiedenem Koeffizienten:
    i-1 moegliche Vektoren und q-1 moegliche Koeffizienten

  - Linearkombinationen mit genau 2 von 0 verschiedenen Koeffizienten:
    (i-1)(i-2)/2 moegliche Vektoren und (q-1)^2 moegliche Koeffizienten

  -  ...

  - Linearkombinationen mit genau j von 0 verschiedenen Koeffizienten:
    ( i-1 )                          j
    ( j   ) moegliche Vektoren, (q-1)  verschiedene Koeffizienten

  - ...

  - ...mit d-2...

  Macht zusammen

     d-2    ( i - 1)      j      i-1             n-2
    Sum     (      ) (q-1)   = V     (d-2) <=   V    (d-2)
     j=0    (  j   )            q                q


  Wenn also V_q^{n-2}(d-2) < q^{n-k} ist, was ja die Voraussetzung des
  Satzes ist, dann ist eine Verlaengerung moeglich. []

Bemerkung: der soeben bewiesene Satz ist in der Literatur auch als
Gilbert-Varsamov Schranke bekannt. In der Tat liefert er ja eine
untere Schranke an die Groesse des bestmoeglichen Codes mit gegebener
Laenge und Minimalabstand. Die Formulierung als "Schranke" traegt der
Tatsache Rechnung, dass der Beweis des Satzes kein effizientes
Verfahren zur Bestimmung eines entsprechenden Codes liefert.


Dualer Code
-----------

Zu einem linearen [n,k,d]_q Code C definiert man den zu C dualen Code
C* als die Menge aller Woerter w:GF(q)^n, sodass gilt w^T x = 0 fuer
alle x:C. Man verifiziert leicht, dass C* Untervektorraum ist. 

Betrachten wir als Beispiel das Wort w=(0001111)^T. Es ist
w^T(1110000)^T=0, w^T(1001100)^T=0, w^T(01010101)^T=0 und
w^T(1101001)^T=0. Damit gilt w^T x = 0 fuer alle Codewoerter des
[7,4,3]-Hammingcodes und w ist ein Element des zu diesem Code dualen
Codes.

Die Abbildung x |-> w^T x ist ja linear; daher genuegt es, wie im
Beispiel geschehen, die Bedingung fuer die Basisvektoren zu
ueberpruefen.

Satz: Sei C Code der Laenge n und der Dimension k. Die Dimension von
C* ist n-k.Beweis: C* ist gerade der Loesungsraum des homogenen
Linearen Gleichungssystems v_i^T x = 0 fuer i=1..k, wobei v_1..v_k
eine Basis von C bilden, z.B. die Spalten einer Generatormatrix. Die k
Gleichungen des Systems sind also linear unabhaengig und nach dem
Dimensionssatz hat der Loesungsraum dann die Dimension n-k.

Satz: Der Code C habe Kontrollmatrix H und Generatormatrix G. Die
Matrix H^T ist eine Generatormatrix fuer C*, die Matrix G^T bildet
eine Kontrollmatrix fuer C*.

Beweis: Die von den Spalten von H^T, also den Zeilen von H, erzeugten
Woerter liegen alle in C*, denn sie "stehen senkrecht" auf allen
Spalten von G. Die Kontrollmatrix hat aber gerade n-k Zeilen; aus
Dimensionsgruenden liefert dies somit bereits ganz C*. Andererseits
ist G^T H^T = (HG)^T = 0 und es folgt, dass G^T eine Kontrollmatrix
ist.

Korollar: Fuer jeden linearen Code C gilt C**=C. 

Definition: Der zum [2^n-1,2^n-1-n,3] Hamming Code duale Code heisst
Simplex-Code der Dimension n.

NB Wegen 2^n-1-(2^n-1-n)=n hat dieser Simplexcode tatsaechlich Dimension n. 

Satz: Fuer jedes von Null verschiedene Wort c des [2^n -
1,n]_q-Simplex-Codes gilt w(c)=2^{n-1}, insbesondere hat dieser Code
Minimalabstand 2^{n-1}.

Beweis
  Wir bezeichnen mit s_i die i-te Spalte der Generatormatrix. Es ist
  dies die i- ten Binaerziffer entsprechende Spalte, wenn man die
  Binaerzahlen der Laenge n als Zeilen der Reihe nach
  untereinanderschreibt. Wir schreiben ausserdem kurz N= 2^n-1.

  Sei 0 =/= c = (c_1,...,c_N)^T ein Codewort, etwa c = Sum_i a_i s_i. Wir
  betrachten

    U = { (b_1,...,b_n) | Sum_i a_i b_i = 0 } subset (F_2)^n

  Dies ist (da nicht alle a_i 0 sind) ein n-1 dimensionaler UVR und
  hat also 2^{n-1}-1 von 0 verschiedene Elemente. Jedem von diesen
  entspricht genau eine Zeile der Generatormatrix, da diese ja alle
  von Null verschiedenen Zeilen der Laenge n enthaelt (in
  systematischer Reihenfolge). Das Element c_i ist aber genau dann 0,
  wenn die i-te Zeile der Generatormatrix in U liegt. Es sind also
  2^{n-1}-1 der c_i gleich Null und damit die verbleibenden 2^{n-1}
  ungleich Null, wie gewuenscht. QED

Es folgt insbesondere, dass alle Codewoerter den gleichen Abstand
voneinander haben. Diese Eigenschaft, die sie mit den Ecken eines
regulaeren Simplex teilen, erklaert auch den Namen des Codes. 

Bemerkung: 
Wir hatten gesehen, dass der Hamming Code eine hohe Datenrate (n - log
n Datenbits bei n uebertragenen bits) und geringe Fehlerkorrektur
(Minimaldistanz 3, unabhaengig von der Laenge des Code Worte). Fuer
den Simplex code ist es genau umgekehrt. Er hat eine hohe
Fehlerkorrektur (d_n/n -> 1/2) aber geringe Datenrate (log n
Datenbits, bei n uebertragenen bits, also asymptotische Datenrate 0).

Abschliessend zeigen wir noch, dass der Simplex Code in gewissem Sinne
"bestmoeglich" ist. Dazu zeigen wir eine Schranke an die Groesse von
stark fehlerkorrigierenden Codes.

Satz (Plotkin-Schranke)
 Sei C subset {0,1}^n ein (nicht notwendig linearer) Code 
 mit Minimaldistanz d > n/2. Dann gilt

    |C| <= 2d/(2d - n) 

Beweis: Wir schaetzen Sum_{x,y} d(x,y) auf zwei
verschiedene Arten ab, wobei die Summe ueber Paare (x,y) mit x:C, y:C,
x=/=y rangiert.

 * Zum einen ist d(x,y) >= d fuer x =/= y stets und wir haben
   |C| * (|C| -1) Summanden, also

   Sum_{x,y} d(x,y) >= d * |C| * (|C| - 1)

 * Wir betrachten nun eine Matrix, deren Spalten alle(!) Codewoerter
   von C umfassen, es ist also eine n x |C| Matrix. 
   Sei nun s_i die Zahl der 0en in der i-ten Zeile.
   Jede Kombination aus einer Spalte mit 0 in der i-ten Zeile und einer
   Spalte mit 1 in der i-ten Zeile traegt in der i-ten Zeile 2 zur
   Summe Sum_{x,y} d(x,y) bei. Also ist

   Sum_{x,y} d(x,y) <= Sum_i 2 s_i (|C| - s_i)

   Der Ausdruck auf der rechten Seite wird maximal fuer s_i = |C|/2, also

   Sum_{x,y} <= n * 2 * |C|/2 * |C|/2 = 1/2 * n * |C|^2

 Insgesamt ergibt sich

  1/2 * n * |C|^2 >= d * |C| * (|C| -1)
  
   n * |C| >=  2* d * (|C| -1)

   0 >= (2d -n) * |C| - 2d

  |C| <= 2d/(2d -n)

Bemerkung
  Fuer den n-dimensionalen Simplex Code gilt gerade
   * |C| = 2^n
  
   * 2d/(2d - N) = 2 * 2^{n-1} / (2*2^{n-1} - 2^n +1) =
     = 2^{n}/1 = 2^n = |C|
  Dieser Code ist also im Sinne der Plotkin-Schranke optimal.

Bemerkung: Hamming und Simplexcode lassen sich auf beliebige endliche
Koerper verallgemeinern. Man erhaelt dann Codes der Laenge
(q^n-1)/(q-1) mit q=|F|.