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