Pagina:Codifica numerica del segnale audio.djvu/98

80

Codifica numerica del segnale audio

altre parole di codice (condizione del prefisso). Condizione necessaria e sufficiente affinché un codice a lunghezza variabile soddisfi la condizione del prefisso è che (disuguaglianza di Kraft)

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

(3.14)

Fig. 3.1 - Rappresentazione grafica di codici a lunghezza fissa e variabile.

Per provare che la disuguaglianza di Kraft è una condizione sufficiente, si consideri il processo di costruzione dell’albero relativo ad una codifica a lunghezza variabile a partire da un albero binario bilanciato di ordine pari alla massima lunghezza di codice (fig. 3.2). Il numero di nodi terminali di tale albero è pari a 2 R_max. È poi possibile costruire un albero sbilanciato corrispondente ad una codifica a lunghezza variabile iniziando ad eliminare uno dei due possibili sotto-alberi relativi al livello 1 (dove il livello 0 è la radice dell’albero). In tal modo si è realizzato un nodo terminale, che corrisponde alla prima parola di codice, eliminandone contemporaneamente altri 2^R_max-R_i dall'albero completo. Continuando tale procedura, la frazione di nodi che vengono eliminati ad ogni passo (rispetto al totale dei nodi terminali) decresce progressivamente. D’altra parte, il codice generato assegnando a ciascuno dei nodi terminali che vengono via via creati una parola di codice soddisfa, per