Pagina:Codifica numerica del segnale audio.djvu/99

3 - Codifica di sorgente

81

Fig. 3.2 - Costruzione di un albero relativo ad una codifica a lunghezza variabile a partire da un albero bilanciato.

costruzione, la condizione del prefisso. Notando che al livello j-esimo risulta

$\sum _{k=1}^{j}{\frac {2^{R_{MAX}-R_{k}}}{2^{R_{MAX}}}}=\sum _{k=1}^{j}2^{-R_{k}}<\sum _{k=1}^{L}2^{R_{k}}\leq 1$

(3.15)

risulta provato che la condizione è sufficiente. Per provare che la disuguaglianza di Kraft è una condizione necessaria, si osserva che i numeri di nodi eliminati al livello R_MAX è pari a

$\sum _{k=1}^{L}2^{R_{MAX}-R_{k}}\leq 2^{R_{MAX}}$

(3.16)

Dividendo tale relazione per il numero totale di nodi terminali si riottiene

$\sum _{k=1}^{L}2^{-R_{k}}\leq 1$

(3.17)

Esempio: si consideri una sorgente discreta che emetta 4 simboli e se ne consideri una codifica a lunghezza variabile ottenuta secondo il procedimento descritto per la disuguaglianza di Kraft. La codifica risultante è riportata nella