Skript Teil 2

Dateiinhalt

Satz (Shannons Quellencodierungssatz): Die mittlere Wortlaenge l bei
optimaler Kodierung einer Quelle Q erfuellt die Ungleichung

           H(Q) <= l < H(Q)+1 

wobei H(Q) die Entropie der Quelle ist. 

Beweis: Wir zeigen zunaechst die Ungleichung H <= l durch Induktion
ueber einen beliebigen Kodebaum t. Habe dieser etwa die Teilbaeume t1 und t2 mit Haeufigkeiten p und q und mittleren Tiefen l_t1 und l_t2. 

Es gilt dann 
l_t = 1 + p*l_t1 + q*l_t2 

Nach Induktionsvoraussetzung gilt 

H(ps/p) <= l_t1
H(qs/q) <= l_t2

Wir erlauben formal auch die Notation H(ps) = -sum_i p_i*log(p_i) falls sum_i p_i < 1. 

l_t = 1 + p*l_t1 + q*l_t2 >= 1+p*H(ps/p)+q*H(qs/q) 
= 1+p*log(p)+q*log(q)+H(ps,qs) >= H(ps,qs)

Im letzten Schritt benutzen wir, dass p*log(p)+q*log(q) = -h(p) >= -1. 

Fuer die Umkehrung setzen wir die Kraftsche Ungleichung ein mit 
l_i := ceil(-log(p_i)). 

Wir erhalten dann einen Praefixcode mit mittlerer Wortlaenge 

sum_i p_i * ceil(-log(p_i)) <
sum_i p_i * (1-log(p_i)) =
sum_i p_i + H  = 1+H

Der optimale Praefixcode ist mindestens genauso gut und erfuellt daher
die Ungleichung erst recht. Der Praefixcode aus dem Beweis der
Kraftschen Ungleichung ist uebrigens i.a. nicht optimal. 

Bemerkung: Shannon erlaubte urspruenglich die Zusammenfassung mehrerer
Quellensymbole zu einem einzigen, welches dann als ganzes kodiert
wird. Hierdurch kann das stoerende "+1" zu einem "+epsilon" reduziert
werden (wobei mit kleinerem epsilon entsprechend mehr Symbole
zusammenzufassen sind.)

Informelle Deutung: Information einer Nachricht ist gleich der Zahl der Bits, die man benoetigt. um sie zu uebermitteln. 

3. Entropie und Transinformation
--------------------------------

Wir werden ab jetzt fuer den Symbolvorrat einer Quelle X einfach X
schreiben anstelle von Sigma_X, sofern keine Verwechslungsgefahr
besteht. Wenn x:X so schreiben wir p_x oder Pr(X=x) fuer die W., dass
X das Symbol x generiert.

Sei X eine Quelle und f:X->Y eine Funktion mit Wertemenge Y. Man
bildet die Quelle Y=f(X), die das Symbol t:Y mit W. sum_{f(x)=y}p_x
generiert.

Satz: Ist Y=f(X) so gilt H(Y) <= H(X). Falls f injektiv ist, so gilt
sogar H(Y)=H(X). Beweis: Uebung.

Definition (Produkt von Quellen): Sind X und Y Quellen, 
so bildet man die Produktquelle X*Y
mit Symbolvorrat X*Y und Pr(X*Y=(x,y)) =
Pr(X=x /\ Y=y). 

Satz: Es gilt H(X*Y) <= H(X)+H(Y). Sind X und Y statistisch
unabhaengig, dann sogar H(X*Y) = H(X)+H(Y). 

Beweis: 
H(X)+H(Y)-H(X*Y) = /* Linearitaet des Erwartungswertes */
E[-log(Pr(X))-log(Pr(Y))+log(Pr(X*Y))] = 
E[-log(Pr(X)*Pr(Y) / Pr(X*Y))] >=  /* konvexe Funktion aus 
				      dem E[-] rausziehen*/
-log(-E[Pr(X)*Pr(Y) / Pr(X*Y)]  = 
-log(sum_{x,y|Pr(X=x,Y=y)=/=0} Pr(X=x,Y=y) * Pr(X=x)*Pr(Y=y) /
Pr(X=x,Y=y)) >=
-log(sum_{x,y}Pr(X=x)*Pr(Y=y)) = 0 


Definition (Transinformation): Man definiert die Transinformation
zweier Quellen X und Y durch I(X;Y) = H(X)+H(Y)-H(X*Y). 

Sind die Quellen unabhaengig, so ist die Transinformation Null. Man
kann aus dem Beobachten keiner Quelle eine Information ueber die
andere erhalten. Ist umgekehrt Y=f(X), so ist I(X;Y) =
H(X)+H(Y)-H(X*Y) = H(X)+H(f(X))-H(X) = H(f(X)).

Korollar (Nichtnegativitaet der Transinformation): Fuer beliebige
Quellen X und Y gilt: I(X;Y) >= 0. 

Korollar: Fuer beliebige Funktionen f gilt: H(X*f(X))=H(X). 
Deutung: Durch (deterministische) Berechnung kann der
Informationsgehalt nicht erhoeht werden. 


Satz (Shannon's Theorem von der perfekten Verschluesselung): 
Es seien 3 Quellen M (message),K (key), C (cipher) gegeben, mit 

i) H(K*C) = H(M*K*C) (Deutung: M kann aus K und C rekonstruiert
		     werden)

ii) I(M;C) = 0 (Deutung: M und C sind statistisch unabhaengig, aus C
alleine kann keine wie auch immer geartete Information ueber M
errechnet werden.)

Dann gilt: H(K)>=H(M) (Deutung: Der Schluessel muss im Mittel, selbst
bei optimaler Verschluesselung, mindestens so lang wie die zu
verschluesselnde Botschaft sein)

Beweis: 

Also: H(C) = H(M) - H(M*C) 

0 <= I(C;K) = H(C) + H(K) - H(C*K)
Also: H(K) >= H(C*K)-H(C)

H(M*C*K) >= H(M*C). (M*C aus M*C*K ausrechenbar) 

 H(K) >= H(C*K) - H(C) = H(C*K) + H(M) - H(M*C) =  
H(M*C*K) + H(M) - H(M*C) >= H(M). []

Definition: Seien X, Y Quellen und y:Y. Man definiert eine Quelle X|y
mit Symbolvorrat Sigma_{X|y}=X und Pr(X|y = x) = Pr(X=x|Y=y) =
Pr(X=x/\Y=y)/Pr(Y=y). (Bedingte W.) 

Satz: Seien X Y Quellen. Es gilt: 

        H(X*Y)-H(Y) = sum_{y:Y} p_y * H(X|y) 

Beweis: Uebung. 

Bemerkung: Man fuehrt die Notation H(X|Y) := H(X*Y)-H(Y) ein und
nennt H(X|Y) die bedingte Entropie von X und Y.

Satz (Ungleichung von Fano): Es seien X, Y Quellen und g:Y->X eine
beliebige Funktion. Fuer Pe := Pr(X=/=g(Y)) = Pr({x,y | g(y)=/=x})
gilt die Ungleichung:

h(Pe) + Pe * log(|X|-1) >= H(X*Y)-H(Y)

Deutung: Pe ist die Fehlerwahrscheinlichkeit bei der Schaetzung
(Rekonstruktion, Decodierung) von X ausgehend von Y. 

Beweis: Wir fuehren eine neue Quelle E mit Symbolvorrat E={0,1} ein,
wobei Pr(E=1) = Pr(X=/=g(Y)) und Pr(E=0)=1-Pr(E=1). 

Es gilt: H(X*Y)-H(Y) = 
H(X*E*Y) - H(Y) = 
H(E*Y)-H(Y) + H(X*E*Y) - H(E*Y) <= 
h(Pe) + Pe * log(|X|-1)

Die letztere Ungleichung begruendet sich wie folgt: 

H(E*Y)-H(Y) <= H(E) = h(Pe) (Nichtnegativitaet der Transinformation)

H(X*E*Y)-H(E*Y) = Pr(E=0)*sum_{y:Y}Pr(Y=y)*H(X|y,0) + 
		  Pr(E=1)*sum_{y:Y}Pr(Y=y)*H(X|y,1) 
                = Pr(E=1)*sum_{y:Y}Pr(Y=y)*H(X|y,1) 
                = Pe * log(|X|-1)

Beachte: H(X|y,0)=0, denn wenn E=0, so ergibt sich X deterministisch
aus Y. H(X|y,1) <= log(|X|-1), da |X|-1 Moeglichkeiten fuer X
verbleiben. g(y) ist ja ausgeschlossen. []

Schwaechere Versionen: 
Pe >= (H(X*Y)-H(Y) - 1)/log(|X|-1)
h(Pe) >= H(X*Y)-H(Y))/log(|X|-1)



5. Blockcodes
-------------

Definition: Ein Blockcode der Laenge n ist eine Teilmenge C von
{0,1}^n. Die Rate eines Blockcodes ist definiert durch log |C| / n 

Die Intuition ist, dass die Woerter in C zur Kodierung der zu
uebermittelnden Information dienen. Die Woerter aus {0,1}^n \ C werden
nicht zur Codierung herangezogen. Wird ein solches Wort empfangen, so
liegt ein Uebertragungsfehler vor. Die Rate ist ein Mass fuer den
Aufwand der Kodierung. Verwendet man den Code C, so koennen log(|C|)
Informationsbits mit n Datenbits uebertragen werden. Die Rate gibt
also den Anteil der "reinen" Information an.


Beispiel: Der (7,16,3)-Hammingcode ist ein Blockcode der Laenge 7. Seine
Rate ist log(16) / 7 = 4/7 = 0,571

Beispiel: Die dreifache Wiederholung von Bytes (8 Bit) ist ein
Blockcode der Laenge 24 und Rate log(8)/24 = 1/8 = 0,125

Beispiel: Die Codierung mit Paritaetsbit ist ein Blockcode der Laenge
8 und Rate 7/8 = 0,875 

Bemerkung: Der ISBN Code passt nicht in dieses Schema, da er nicht mit
dem Alphabet {0,1} arbeitet. Huffman Codes passen auch nicht in dieses
Schema, da ihre Kodewoerter unterschiedliche Laenge haben. 

Definition(Hamming-Distanz): Die Hammingdistanz d(x,y) zweier gleichlanger 
Woerter x, y ueber {0,1} ist die Anzahl der Positionen, an denen sie sich
unterscheiden. 

Beispiel: d(0010001,0010110) = 3. 

Definition(Hamming Kugel): Sei x:{0,1}^n und t<=n. Die Hamming-Kugel
K_t(x) um x mit Radius t ist definiert durch 

K_t(x) = {y : {0,1}^n | d(x,y) <= t}

Die Hamming-Kugel K_t(x) enthaelt alle Woerter, die aus x durch
maximal t Bitfehler hervorgehen. 

Definition (Fehlererkennung, -korrektur): 
Ein Code C der Laenge n erlaubt die Erkennung von bis zu t
Fehlern, wenn aus x:C und 0=/=d(x,y)<=t folgt: y nicht in C. 
Er erlaubt die Korrektur von bis zu t Fehlern, wenn zu jedem x:{0,1}^n
 hoechstens ein Codewort y existiert mit d(x,y)<=t.

Bei der Fehlererkennung meldet man einen Uebertragungsfehler, wenn das
empfangene Wort nicht in C ist. Bei der Fehlerkorrektur decodiert man
zum naechstgelegenen (im Sinne der Hammingdistanz) Codewort.

Definition (Minimaldistanz): Sei C ein Code der Laenge n. Die
Minimaldistanz d(C) von C ist definiert durch

                  d(C) = min{d(x,y) | x,y:C, x=/=y}

Satz: Code C erlaubt die Erkennung von bis zu t Fehlern, genau dann
wenn d(C) > t. Er erlaubt die Korrektur von bis zu t Fehlern, genau
dann wenn d(C) > 2t.

Beweis: 

Erkennung ist klar. Fuer die Fehlerkorrektur nehmen wir
zunaechst an, dass d(C)>2t. Gaebe es zu x:{0,1}^n zwei Codewoerter y1
und y2 mit y1=/=y2 und d(x,y1) <= t, d(x,y2) <= t, so waere
d(y1,y2)<=2t im Widerspruch zu d(C)>2t. 

Nun erlaube C die Korrektur von bis zu t Fehlern und seien y1,y2:C mit
y1=/=y2 vorgegeben. Wenn d(y1,y2)<=2t, dann gibt es ein Wort x mit d(x,y1)<=t
und d(x,y2)<=t. Ein Widerspruch. []

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 im 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)}