Coding-WS16-03
Codierung-WS16-03.txt
—
Plain Text,
7 KB (7210 bytes)
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. []
Document Actions