Information & Kommunikation 41 Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 27.4

Information & Kommunikation 4

1

Information und Kommunikation

Hartmut KlauckUniversität Frankfurt

SS 0727.4.


2

Random Access Codes

• Wir geben eine einfache Anwendung von Fanos Ungleichung

• Strings x2{0,1}n werden mit uniformer Verteilung zufällig gezogen

• Wir suchen einen Code, der es erlaubt, für i2{1,…,n} das Bit xi zu bestimmen, dabei soll die durchschnittliche Erfolgswahrscheinlichkeit sein.

• D.h. es sei erlaubt, für einige x,i die falsche Antwort zu geben.

• Wir nennen solche Codes „random access codes“• Z.B. reicht es aus, die ersten n von x Bits als

Code zu verwenden.


3

Random Access Codes

• Gibt es kurze Random Access Codes?• Theorem 4.1

Jeder Random Access Code hat mindestens (1-H())n Bits Länge.

• Bemerkung: Für konstant muss der Code (n) Bits haben.Die Schranke in 4.1 ist dicht bis auf O(log n)


4

Random Access Codes• Beweis:

– X sei die Zufallsvariable der zu kodierenden x– H(X)=n– M sei die Zufallsvariable, die dem Code entspricht, m die

Länge des Codes

– Wenn wir Xi mit Ws. i dekodieren können, dann gilt

nach Fano 1-H(i))· I(Xi:M)

– Nach Kettenregel gilt m¸H(M)¸I(X:M)=i=1,…,n I(Xi:M|X1,…,Xi-1)¸i=1,…,n I(Xi:M), da

die Xi unabhängig sind– Also ist die Länge des Codes mindestens i=1,…,n (1-H(i))

= n-n Ei=1,…,n H(i)– Ei[i]=und daher Ei=1,…,n H(i)· H(), da H konkav– Es folgt eine Codelänge von mindestens n(1-H())


5

Ein Kommunikationsspiel

• Wir haben implizit folgendes Spiel analysiert:– Alice erhält x2{0,1}n

– Bob erhält i2{1,…,n}– Alice sendet eine Nachricht zu Bob– Bobs Aufgabe ist es, xi zu berechnen– Die durchschnittliche Erfolgswahrscheinlichkeit

sei • Dann muss Alices Nachricht mindestens

(1-H())n Bits haben• Auf der anderen Seite, wenn Bob eine

Nachricht senden darf, sind nur log n Bits Kommunikation nötig, damit Alice xi lernt


6

Datenkompression

• Wir kehren nun zur Frage des noiseless coding zurück

• Ein Code für eine Zufallsvariable X über {1,…,m} mit Verteilung p ist eine Abbildung C von {1,…,m} nach {0,1,…,D-1}*. D sei die Größe des Codealphabets.

• li sei die Länge von C(i)

• Die erwartete Codelänge ist L(C)=i p(i) li

• Beispiel: Die Buchstaben des Alphabets sollen binär kodiert werden. Häufigere Buchstaben wie „e“ oder „r“ sollen kürzere Codes erhalten


7

Datenkompression

• Wir wollen aber noch weitere Eigenschaften– Die Kodierung soll eindeutig sein, d.h. für ij

soll C(i)C(j) gelten– Wenn wir kodierte Zeichen übertragen, muss

der Empfänger wissen, wann ein Zeichen endet. Wir wollen kein bestimmtes Ende Symbol zusätzlich verwenden

• Definition– Ein Code ist präfixfrei, wenn C(i) kein Präfix von

C(j) ist für alle ij


8

Beispiel

• Wir wollen A,B,C,D kodieren• 0,1,01,10 ist ein eindeutiger Code,

aber nicht präfixfrei• 0,10,110,111 ist präfixfrei

– Die Folge 011010111 kann ohne Trennzeichen dekodiert werden


9

Eine Eigenschaft präfixfreier Codes

• Theorem 4.2 [Kraftsche Ungleichung]– Ein präfixfreier Code mit m

Codewortlängen l1,…,lm über einem Alphabet der Größe D erfüllt:i D-li· 1

– Gegeben l1,..,lm, die diese Ungleichung erfüllen, gibt es einen präfixfreien Code mit diesen Codewortlängen


10

Kraftsche Ungleichung

• Beweis– Teil 1: Gegeben ein präfixfreier Code

mit Längen l1,…,lm– Wir betrachten einen Baum mit Grad D– Die Verzweigungen entsprechen den

Buchstaben des Alphabets– Die Blätter den Codeworten


11


• Beispiel:– A,B,C,D mit Codeworten 0,10,110,111


12

Kraftsche Ungleichung• Die Präfixeigenschaft impliziert, dass kein Vorgänger eines

Blattes ein Codewort ist• lm sei die größte Codewortlänge• Alle (möglichen) Knoten in Tiefe lm sind entweder

Codeworte, Nachfolger von Codeworten, oder keins von beidem

• Ein Codewort in Tiefe li schließt Dlm-li viele Knoten in Ebene lm als Codeworte aus

• Alle diese Mengen von ausgeschlossenen Knoten sind paarweise disjunkt

• Es werden höchstens Dlm Knoten in Tiefe lm ausgeschlossen• D.h. i Dlm-li· D-lm

• ) i D-li · 1


13



14


• Teil 2:– Gegeben l1,…,lm mit i D-li · 1– Wir wollen „Worte“ 1,…,m kodieren– Der (lexikographisch) erste Knoten in Tiefe l1

ist der Code von 1 (bzw. der Pfad zum Knoten ist mit dem Codewort gelabelt).

– Alle Nachfolger des Blattes werden entfernt– Iteration

• Klar: wir erzeugen einen präfixfreien Code• Übung: zeigen, dass dies tatsächlich

funktioniert.


15

Optimale Codewortlängen

• Wir haben nun eine hinreichende und notwendige Bedingung für präfixfreie Codes

• Was ist nun die erwartete Codewortlänge?

• Wir definierenHD(X)=-i p(i) logD(pi),die Entropie zur Basis D


16


• Theorem 4.3

Jeder präfixfreie Code mit Alphabet{0,..,D-1} für eine Zufallsvariable X auf {1,…,m} hat erwartete Länge

i p(i) li¸ HD(X)


17


• Beweis– Wir setzen L= i p(i) li und betrachten

L-HD(X)=


18


• DD(p||r) ist die relative Entropie zur Basis D

• c·1 wegen der Kraft Ungleichung


19


• Wir kennen nun eine untere Schranke für die erwartete Codelänge

• Unser Ziel ist es, eine obere Schranke zu finden, d.h. einen Code zu konstruieren

• Gegeben ist also eine Zufallsvariable X auf {1,…,m} mit Entropie HD(X) und wir wollen einen Code mit Alphabet {0,…,D-1} konstruieren


20


• Theorem 4.4– Zu X gibt es einen Code mit erwarteter

Länge <HD(X)+1

• Beweis:– Wir wollen p(i)li minimieren, dabei

muss D-li· 1 gelten

– Wir setzen


21


• Diese Wahl erfüllt die Kraft Ungleichung

• Es gilt


22


• Wir können nun wie in der Konstruktion zur Kraft Ungleichung einen Code angeben.

• Diese Konstruktion liefert uns also einen Code mit erwarteter Länge zwischen HD(X) und HD(X)+1

• Der erhaltene Code ist nicht unbedingt optimal!

Documents

Information & Kommunikation 41 Information und Kommunikation Hartmut Klauck Universität Frankfurt SS 07 27.4