Pagina:Codifica numerica del segnale audio.djvu/98

Da Wikisource.
Jump to navigation Jump to search
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)

  (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 Rmax. È 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 2Rmax-Ri 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