Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Coding-WS16-04


Inhaltsbereich

Coding-WS16-04

Plain Text icon Codierung-WS16-04.txt — Plain Text, 14 KB (14804 bytes)

File contents

Definition[(n,k,d)-Code]: Ein (n,k,d)-Code ist ein Code C der Laenge n
mit |C|=k vielen Codewoertern und Minimaldistanz d. Die 3 Zahlen
(n,k,d) sind die Parameter von C. 

Satz (Kugelpackungsschranke): Sei C ein 
Code der Laenge n mit Minimaldistanz d>=2e+1 fuer e:N. Es gilt: 

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

Beweis: Unter den Voraussetzungen gilt K_e(x) \cap K_e(y) = {} fuer
x,y:C und x=/=y. Die Behauptung folgt aus der Groessenformel fuer
Hamming-Kugeln.

Korollar: Erlaubt ein Code C der Laenge n die Korrektur von bis zu t
Fehlern, so gilt

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

Lemma: Wenn p<1/2, so gilt 

sum_{i=0}^{np}binom(n,i) <= 2^{n*h(p)}  
Beweis: 1 = (p + (1-p))^n >= 
sum_{i=0}^{np} binom(n,i)p^i * (1-p)^{n-i} =
(1-p)^n * sum_{i=0}^{np} binom(n,i)(p/1-p)^i >= 
(1-p)^n * sum_{i=0}^{np} binom(n,i)(p/1-p)^(np) >=  /* p/(1-p)<=1 */
p^{np} * (1-p)^{n*(1-p)} * sum_{i=0}^{np} binom(n,i). 

Also: 

sum_{i=0}^{np} binom(n,i) <= 
2^{-log(p^{np} * (1-p)^{n*(1-p)})} = 
2^{n*h(p)} 

Definition: Ein Code C der Laenge n mit Minimaldistanz d=2e+1 ist
perfekt, wenn gilt

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

Perfekte Codes schoepfen also die Kugelpackungsschranke voll
aus. 

Beispiele: Der (7,16,3) Hamming Code ist perfekt, denn es gilt: 

                              2^7 = 16*(1 + 7)

Jeder Code mit den Parametern (n,1,2*n+1) ist perfekt (trivialer Code).
Der Code mit den Parametern (n,2^n,1) ist perfekt. 
Der Code C = {0^{2e+1}, 1^{2e+1}} ist ein perfekter (2e+1,2,e)-Code.

Leider gibt es ausser den aufgefuehrten trivialen Beispielen keine
perfekten Codes einer Minimaldistanz >= 7. 

Satz (Singleton Schranke): Ist C ein Code der Minimaldistanz d+1, so gilt: 
log(|C|) <= n-d.

Beweis: Die Projektion auf n-d Koordinaten ist injektiv. 

Definition: Ein Code, der die Singleton Schranke realisiert, fuer den
also gilt: log(|C|) = n-d, heisst MDS-Code (maximum distance separable).


6. Shannons Kanalcodierungssatz:
--------------------------------

Ein Kanal uebertraegt Symbole aus einem Alphabet. Oft ist das Alphabet
{0,1}. Es kann aber auch groesser sein. Wir betrachten der Einfachheit
halber hier nur das Alphabet {0,1}. Aehnlich wie bei den Quellen gehen
wir stets von Gedaechtnislosigkeit aus und erlauben ausserdem keine
Ausloeschung. D.h. ein Symbol x wird mit einer gewissen
Wahrscheinlichkeit korrekt uebertragen. Diese W. haengt nur vom
gesendeten Symbol, nicht aber von der Vorgeschichte ab. Wird das
Symbol nicht korrekt uebertragen, so erscheint am Ausgang ein anderes
Symbol. 

Beispiel (binaer symmetrischer Kanal): 
Ein binaer symmetrischer Kanal liegt vor, wenn: 

Ein Parameter p < 1/2 existiert, sodass gilt: 

Pr(x kommt an | x wurde gesendet) = 1-p
Pr(x kommt an | y wurde gesendet) = p, falls x=/=y

Die Wahrscheinlichkeit eines Uebertragungsfehlers ist also gleich p
und unabhaengig vom gesendeten Symbol. Die Bedingung p < 1/2 ist
gleichbedeutend damit, dass das gesendete Symbol die wahrscheinlichste
Ausgabe ist.

Verbindet man den Eingang eines Kanals mit einer Quelle X, so wird der
Kanalausgang zu einer anderen Quelle Y. Die Transinformation I(X;Y)
ist ein Mass fuer die gegenseitige Abhaengigkeit von X und Y. Je
groesser sie ist, desto geringer ist die Stoerung, die der Kanal
beitraegt und umso mehr Information laesst sich ueber den Kanal
uebertragen.


Definition(Maximum-Likelihood Decodierung): Es werden Woerter eines
Blockcodes C ueber einen Kanal uebermittelt. Kommt ein Wort x : {0,1}\C
an, so decodiert man zu demjenigen Wort x':C, welches die
Wahrscheinlichkeit, dass x ankommt, maximiert. 


Satz: Bei Maximum-Likelihood Decodierung wird ein Wort x zu demjenigen
Wort in C decodiert, welches von x die geringste Hamming-Distanz
hat. Erreichen mehrere Codewoerter die minimale Distanz, so kann man
sich eines beliebig aussuchen. 

Beweis: Uebung. 


Definition (Kanalkapazitaet): Die Kapazitaet eines Kanals ist definiert als 
                             max_X I(X;Y)
wobei das Maximum ueber alle binaeren (Symbolvorrat {0,1}) Quellen X rangiert. 

Satz: Die Kapazitaet eines BSC mit Parameter p ist 1 - h(p). 
Beweis: Fuer eine Quelle X gelte p_0 = q und p_1 = 1-q. Es ist H(X)=h(q) 
H(X*Y) = -(q*(1-p)*log(q*(1-p)) + 
           q*p*log(q*p) + 
           (1-q)*p*log((1-q)*p) + 
           (1-q)*(1-p)*log((1-q)*(1-p)))
       = -(q * (1-p) * (log(q) + log(1-p)) + 
           q * p * (log(q) + log(p)) + ... )
       = -q * log(q) + q * h(p) -
        (1-q) * log(1-q) + (1-q)*h(p) = 
       = h(p) + h(q) 
H(X) = h(q)

H(Y) = h((1-q)(1-p) + pq)

I(X;Y) = h(q) + h((1-q)(1-p)+pq) - h(p) - h(q) = 
         h((1-q)(1-p)+pq) - h(p). 
         
Dies wird maximal fuer q=1/2, denn dann ist h((1-q)(1-p)+pq)=h(1/2)=1. 
Es ist dann wie behauptet I(X;Y) = 1-h(p).                          []

Beispiel: Im Grenzfall p=1/2 (nicht zugelassen) ist die Kapazitaet
Null. Intuitiv kann ueber einen Kanal, der mit W. 1/2 verfaelscht,
keine Information uebermittelt werden, da sich die Ausgabe des Kanals
vom Ergebnis eines fairen Muenzwurfs in keiner Weise unterscheidet. 

Im Grenzfall p=0 ist die Kapazitaet 1. 

Im Falle p=0,25 ist kappa = 1 - 1/2 - 3/4 * log(3/4) = 0,189 

Im Falle p=0,01 ist kappa = 0,92

Dem Shannonschen Hauptsatz der Kanalcodierung, 
den wir nun formulieren werden, liegt folgendes Szenario zugrunde. 

Gegeben ist ein Kanal der Kapazitaet kappa, z.B. ein BSC. Man
verwendet nun einen Blockcode C um Daten ueber den Kanal zu
uebertragen. Evtl Uebertragungsfehler koennen dann bei der Decodierung
ausgeglichen werden. Mithilfe der Ungleichung von Fano koennen wir
eine untere Schranke an die Fehlerwahrscheinlichkeit Pe
ableiten. Fehlerwahrscheinlichkeit bezieht sich hier auf die trotz
Fehlerkorrektur verbleibenden Fehler, zu denen es immer dann kommt,
wenn bei der Uebertragung mehr Bits verfaelscht werden, als mithilfe
des eingesetzten Codes korrigiert werden koennen.

Satz: Fuer jedes R > kappa existiert epsilon > 0, sodass bei
Verwendung eines Codes der Rate R die Fehlerwahrscheinlichkeit
mindestens epsilon ist. 

Beweis: Die Quelle X liefere uniform verteilt Codewoerter aus
C. Formal hat X also C als Symbolvorrat. Die Entropie von X ist somit
log(|C|) = n*R. Die am Ausgang des Kanals ankommenden Woerter der
Laenge n modellieren wir als eine Quelle Y mit Symbolvorrat {0,1}^n. Es gilt nun: 

n*R = H(X) = H(X*Y)-H(Y) + I(X;Y) /* I(X;Y) = H(X)+H(Y)-H(X*Y) */
<= H(X*Y)-H(Y) + n*kappa          /* Definition der Kanalkapazitaet */
<= 1 + Pe*n*R + n*kappa           /* Fano Ungleichung */ 

Es folgt: (1-Pe)*n*R <= 1 + n*kappa
       1-Pe <= (1+n*kappa)/(n*R)
 Pe >= 1 - (1+n*kappa)/(n*R) = (R-kappa+1/n) / R >= (R-kappa)/R > 0. []

Uebersteigt also die verlangte Rate die Kapazitaet, so kann eine
bestimmte Fehlerwahrscheinlichkeit, die nur von R und kappa abhaengt,
nicht aber von der Blocklaenge n oder gar vom Code C nicht
unterschritten werden.

Erstaunlicherweise gilt auch die Umkehrung dieses Satzes im folgenden Sinne: 

Satz: Fuer jedes R < kappa und epsilon > 0 existiert ein Code C,
dessen Verwendung eine Fehlerwahrscheinlichkeit Pe <= epsilon erlaubt.

Beweisidee: Die Existenz des Codes C zeigt man mit der
probabilistischen Methode, d.h. man zeigt, dass sogar die mittlere
Fehlerwahrscheinlichkeit gemittelt ueber alle Codes der Rate R den
gewuenschten Schranken genuegt. Hierbei beachtet man, dass im Mittel
np Fehler passieren werden und verwendet die Abschaetzung

p < 1/2 ==> sum_{i=0}^{np} binom(n,i) <= 2^{n*h(p)}  




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

Es bietet sich an, die 0en und 1en als Elemente des zweielementigen
Koerpers GF(2) zu verstehen. + = XOR, * = AND. Die Woerter einer
festen Laenge n bilden dann einen Vektorraum ueber diesem Koerper. Man
kann das auch 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:

    1010101
H = 0110011
    0001111
    ^^ ^

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

    1101
    1011
    1000 <
G = 0011
    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 Zeilen 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.

Wir geben hier noch einen Algorithmus zur Konstruktion der
Generatormatrix dieses Codes, der sich direkt aus der Herleitung aus
der Kontrollmatrix ergibt:

Die Zeilen mit den Nummern 1,2,4,8,16... entsprechen den Kontrollbits.
Die Zeile 2^i hat eine 1 genau dort, wo die entsprechende Binaerstelle
in der Nummer des Datenbits vorkommt. Mit anderen Worten erhaelt man
diese Zeilen durch Streichen der Einheitsspalten in der
Kontrollmatrix. Die restlichen Zeilen der Generatormatrix sind
Einheitszeilen und sorgen dafuer, dass die Datenbits "durchgereicht"
werden.


Syndromdecodierung: 

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, also minimalem
Gewicht 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.

Document Actions


Funktionsleiste