Disuguaglianza di Kraft-McMillan

In teoria dei codici la disuguaglianza di Kraft-McMillan fornisce una condizione necessaria e sufficiente per l'esistenza di un codice binario univocamente decodificabile per un insieme di simboli.

EnunciatoModifica

Ogni codice binario univocamente decodificabile per i simboli   deve soddisfare la disuguaglianza:

 

dove   è la lunghezza della stringa binaria corrispondente ad  . Dati invece gli interi  ,   soddisfacenti la disuguaglianza precedente, esiste un codice binario per l'alfabeto   tale per cui la parola   ha lunghezza   e non esiste alcuna parola uguale ad un suo prefisso.

Dimostrazione (per codici a prefisso)Modifica

È possibile dimostrare in modo semplice che il teorema è vero per codici a prefisso. Tali codici possono essere scritti tramite alberi binari nei quali ad ogni ramo corrisponde un bit   o  . Sui nodi interni non termina alcuna parola del codice, altrimenti si avrebbero parole con il medesimo prefisso. Le foglie sono associate ciascuna ad una parola del codice. Si può supporre che il codice sia costituito da   parole e che le loro lunghezze siano   con  , senza perdita di generalità. Essendo il codice a prefisso è possibile associare ad ogni foglia una diversa parola. L'albero ha altezza   e quindi un numero di foglie al più pari a  . Procedendo ad un assegnamento delle parole di codice ai simboli che esse devono rappresentare, si può affermare che associando la foglia di profondità   si rimuovono tutte le parole con medesimo prefisso, che sono  . La condizione da rispettare è che, una volta assegnate   parole di codice ad altrettanti simboli, si abbia almeno ancora una foglia a cui assegnare il simbolo rimanente, quindi deve essere vera la seguente disuguaglianza:

 

Ciò significa che:

 

ossia:

 

che può essere riscritta come:

 

che è appunto la disuguaglianza di Kraft-McMillan.
In modo analogo si può dimostrare che dato un codice con parole di lunghezza   che verificano la disuguaglianza di Kraft-McMillan è possibile porle in corrispondenza biunivoca con le parole di un codice binario a prefisso dove la lunghezza   viene associata alla foglia a profondità   nell'albero binario.

BibliografiaModifica

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica