Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Coding-WS16-02


Inhaltsbereich

Coding-WS16-02

Plain Text icon Codierung-WS16-02.txt — Plain Text, 2 KB (2051 bytes)

File contents

Fuer Zahlen p_1,...,p_k im Bereich 

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 (englisch): We show the inequality H(X) <= l by induction on an arbitrary code tree. If the code tree is empty (base case) we have only one symbol encoded by the empty word and the inequality becomes 0<=0. Otherwise, t has two subtrees t0 and t1  corresponding to a partition Sigma_X = U u V of the symbols with the symbols in U being encoded by t0 and V being encoded by t1. Suppose that
U has probability p_U = sum_(x:U) p_x and V has probability p_V, so p_U+p_V=1.

Furthermore, let l_0 and l_1 be the mean depth (code lengths) of t0 and t1. We then have  

l = 1 + p_U *l_0 + p_V * l_1 

The induction hypothesis yields 

- sum_(x:U) p_x/p_U * log(p_x/p_U) <= l_0
- sum_(x:V) p_x/p_V * log(p_x/p_V) <= l_1

So,

l = 1 + p_U * l_0 + p_V * l_1 >=
1 - sum_(x:U) p_x * log(p_x/p_U) - sum_(x:V) p_x * log(p_x/p_V) =
1 - sum_(x:U) p_x * log(p_x) - sum_(x:V) p_x * log(p_x)
  + sum_(x:U) p_x * log(p_U) + + sum_(x:V) p_x * log(p_V) =
1 + H(X) + p_U*log(p_U) + p_V*log(p_V) = 1+H(X) - h(p_U)

where h(p) = -p*log(p) - (1-p)*log(1-p) (entropy function).
One has h(p) <= 1 for p:[0,1], so 1 - h(p_U) >= 0 and the claim follows.

For the converse we use Kraft's inequality with 
l_i := ceil(-log(p_i)) where ceil(x)="least integer >= x". 

This yields a prefix code of mean code length 

sum_i p_i * ceil(-log(p_i)) <
sum_i p_i * (1-log(p_i)) =
sum_i p_i + H(X)  = 1+H(X)              Q.E.D.


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. 

Document Actions


Funktionsleiste

Servicebereich
News and Events

For news and events please switch to the German page.