Coding-WS16-03

File contents

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 

Satz: Fuer beliebige Funktionen f gilt: H(X*f(X))=H(X). 
Beweis:

Fuer x,y gilt in X*f(X), dass p_(x,y)=p_x, da y sich aus x ergibt.
Nun ist H(X*f(X)) = -sum_(x,y) p_(x,y) * log(p_(x,y)) =
-sum_(x,y) p_x * log(p_x) = H(X).

Deutung: Durch (deterministische) Berechnung kann der
Informationsgehalt nicht erhoeht werden. 


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. 


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 Codierung, bzw. Ausnutzung, mindestens so lang wie die zu
verschluesselnde Botschaft sein)

Beweis: 

Aus ii: H(C) =  H(M*C) - H(M)  

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) = sum_{x:Y,e:E}Pr(Y=y,E=e)*H(X|y,e) =
                  sum_{e:{0,1}}Pr(E=e)*sum_{y:Y}Pr(Y=y|E=e)*H(X|y,e) =
                  Pr(E=0)*sum_{y:Y}Pr(Y=y|E=0)*H(X|y,0) + 
		  Pr(E=1)*sum_{y:Y}Pr(Y=y|E=1)*H(X|y,1) 
                = Pr(E=1)*sum_{y:Y}Pr(Y=y|E=1)*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. []