Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 4.5

Information und Kommunikation

Hartmut KlauckUniversität Frankfurt

SS 074.5.

Information & Kommunikation 6

2

Beispiele

• 5) Erasure Kanal– Symbole werden mit Wahrscheinlichkeit

gelöscht. Dies wird bemerkt.– Matrix:

– C=maxp(x) H(Y)-H()

– Was ist H(Y)?


3

Beispiele

• E sei die Indikatorzufallsvariable von „Y=e“• H(Y)=H(Y,E)=H(E)+H(Y|E)

• Wir setzen Prob(X=1)=p(1)= und erhaltenH(Y)

= H( (1-)(1-), (1-) ), ) = H()+¢0+(1-)H()

• C=maxp H(Y)-H()=max (1-) H()=1-(wenn =1/2)


4

Beispiele

• Intuitiv: ein -Anteil der Bits geht verloren, 1- Bits werden übertragen

• Wenn der Sender „feedback“ erhält, ist es leicht, die verlorenen Bits neu zu senden

• Aber es geht auch ohne Feedback!


5

Eigenschaften der Kanalkapazität

• Theorem 6.1– Für alle Kanäle gilt:– Die Kapazität C¸0, da I(X:Y)¸0– C· log |X|; C· log |Y|,

da I(X:Y)· H(X),H(Y)– I(X:Y) ist eine stetige Funktion von p(x)– I(X:Y) ist eine konkave Funktion von p(x)


6

Eigenschaften der Kanalkapazität

• I(X:Y) ist eine konkave Funktion auf einer geschlossenen konvexen Menge (der Menge der Verteilungen p(x))

• Ein lokales Maximum ist damit auch ein globales Maximum

• Das Maximum der I(X:Y) ist endlich (und tatsächlich ein Maximum, anstelle eines Supremums)

• Die Kapazität eines gegebenen Kanals kann daher mit Standard Optimierungsmethoden bestimmt werden.


7

Kodierung

• Wir wollen nun Shannons Theorem zur Kodierung auf Kanälen zeigen.

• Das Theorem besagt, dass wir mit einer „Rate“ entsprechend der Kapazität Information über den Kanal schicken können, ohne wesentlich Daten zu verlieren

• Dazu müssen Daten kodiert werden– Fehlerkorrigierende Codes


8

Kodierung

• Wir betrachten Kommunikationssysteme wie folgendes:

• Nachrichten W aus einer Menge {1,…,M} werden kodiert über Xn, als strings der Länge n über dem Eingabealphabet des Kanal

• Der Kanal wird n mal benutzt• Empfangen wird ein Element von Yn

• Der Empfänger dekodiert zu W‘


9

Kodierung

• Definition 6.2– Das n-fache Produkt eines Kanals (mit

Matrix p(y|x)) ist gegeben durch

• Definition 6.3– Ein (M,n)-Code für einen Kanal besteht aus

• Einer Kodierungsfunktion C:{1,…,M}! Xn

• Einer Dekodierungsfunktion D:Yn !{1,…,M}


10

Kodierung

• Definition 6.4– Die Fehlerwahrscheinlichkeit eines

Code/Kanal-Paars auf Eingabe i2{1,…,M} ist

– Die maximale Fehlerwahrscheinlichkeit ist

– Die durchschnittliche Fehlerwahrscheinlichkeit ist


11

Kodierung

• Definition 6.5– Die Rate eines Codes ist durch

R=log M/n gegeben

• Die Rate misst also, wie viel Information pro Zeichen übertragen wird

• Definition 6.6– Eine Rate R heißt erreichbar für einen Kanal,

wenn es eine Folge von (d 2nRe, n)-Codes für alle n gibt, so dass die maximale Fehlerwahrscheinlichkeit der Codes mit n gegen 0 geht


12

Ausblick

• Wir werden zeigen, dass alle Raten unterhalb der Kanalkapazität erreichbar sind

• Dazu müssen wir zu jedem gegebenen Kanal einen Code konstruieren

• Für praktisch relevante Kanäle spielt außerdem die Effizienz von Kodierung und Dekodierung eine Rolle

• Wir werden hingegen Codes zufällig konstruieren


13

Typische Sequenzen

• Wir betrachten nun ein Hilfsmittel, um zufällige Codes zu dekodieren

• Intuitiv gesehen wollen wir, gegeben eine Produkt-Verteilung auf Xn, die strings aufteilen in typische Sequenzen, und den (unwahrscheinlichen) Rest

• Definition 6.7– p sei eine Verteilung auf X– p(x1,…,xn)=i p(xi) auf Xn

– Die typische Menge A enthält alle x1,…,xn mit


14

Typische Sequenzen

• Theorem 6.81. Wenn x1,…,xn 2 A, dann gilt

H(X)-· –log( p(x1,…,xn))/n · H(X)+

2. Prob(A)¸ 1- für genügend großes n

3. |A|· 2n(H(X)+)

4. |A|¸ (1-)2n(H(X)-) für genügend großes n

• Das bedeutet: A ist eine „kleine“ Menge, „ähnlich“ wahrscheinlicher Sequenzen, die zusammen „fast alle“ Wahrscheinlichkeit ausmachen


15

Beweis• Zu 1): Klar aus der Definition• Zu 2):• Wenn die Xi zufällig sind gilt:

E[-log(p(X1,…,Xn))/n]=E[-i log(p(Xi))/n]=H[X]• D.h. A enthält diejenigen Sequenzen, für welche -

log(p(x1,…,xn))/n nur wenig vom Erwartungswert abweicht

• Fakt: [Chebyshev]– Sei Y eine Zufallsvariable mit Erwartungswert und

Varianz 2.– Dann gilt Prob(|Y-|¸) · 2/2

• Wenn Y=i=1…n Zi/n für unabhängige Zufallsvariablen Zi, dann gilt 2(Y)= i=1…n 2(Zi)/n2=E[2(Zi)]/n


16

Beweis

• Damit gilt: Prob(|-1/n¢ log p(x1,…,xn)-H(X)|¸) geht nach 0 mit großem n

• Oder: Für alle >0 giltProb(|-1/n¢ log p(x1,…,xn)-H(X)|<)>1- für alle genügend großen n

• Wir können = setzen.


17

Beweis

• 3) |A|· 2n(H(X)+)


18

Beweis

• 4): |A|¸ (1-)2n(H(X)-) für genügend großes n

• Für genügend gr. n ist Prob(A)> 1-


19

Exkurs: Datenkompression

• Wir wollen das Konzept der typischen Sequenzen anwenden, um Daten zu komprimieren

• Seien X1,…,Xn unabhängige Zufallsvariablen auf {1,…,m}, die jeweils eine Verteilung p haben

• Idee: wir teilen alle Sequenzen auf in typische und restliche, und kodieren diese getrennt


20


• Dazu nummerieren wir die typischen Sequenzen beliebig, ebenso die übrigen

• Um eine typische Sequenz zu kodieren reichen log (|A|)+1= n(H(X)+)+1 Bits

• Die restlichen Sequenzen brauchen höchstens n log m+1 Bits.

• Wir brauchen noch 1 Bit, um anzuzeigen, ob wir eine typische Sequenz kodieren


21


• Damit ist die erwartete Codelänge


22


• Bemerkungen:– ‘= + log m + 2/n kann beliebig klein

gemacht werden durch Wahl von , n– Der Code kann „leicht“ kodiert und dekodiert

werden– Es gibt zwei Codewortlängen

• Typische Sequenzen: n(H(X)+)+2• Andere n log m +2

– Es gibt keinen Fehler bei der Dekodierung– Kleineres bewirkt, dass n größer gewählt

werden muss


23


• Theorem 6.9– Wenn X1,…,Xn unabhängig, und jeweils

mit p verteilt sind, können Sequenzen ihrer Werte mit erwarteter Codelänge n(H(X)+) für beliebig kleines (und genügend großes n) kodiert werden

Documents

Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 4.5