Skript Teil 2
skript2.txt
—
Plain Text,
15 KB (15974 bytes)
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)}
Artikelaktionen