|
3 - Codifica di sorgente |
83 |
si ottiene
|
|
(3.23)
|
Essendo, ovviamente, P k < 1
|
|
(3.24)
|
Riconoscendo, poi, nella sommatoria che appare nell'ultima equazione il primo membro della disuguaglianza di Kraft, rimane provato che
|
|
(3.25)
|
Per la dimostrazione del del limite superiore, è necessario esplicitare il tipo di codifica adottata. Nel caso di codifiche a lunghezza variabile univocamente ed istantaneamente decodificabili, la scelta degli interi Rk può essere fatta in modo tale che
|
|
(3.26)
|
In tal modo si ha innanzitutto il vantaggio di legare la lunghezza della codifica alla probabilità del simbolo. Inoltre, tale codifica è valida in quanto, sommando il termine
|
|
(3.27)
|
si riottiene la disuguaglianza di Kraft. D’altra parte, considerando il logaritmo del termine
|
P_k < 2^{-R_k+1}</math>
|
(3.28)
|
si ottiene
|
|
|
|
|
(3.29)
|