Teorema di Kraft-McMillan

Da Wikipedia, l'enciclopedia libera.

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

Enunciato[modifica | modifica sorgente]

Ogni codice binario univocamente decodificabile per i simboli \alpha\in A=\alpha_{1},...,\alpha_{N} deve soddisfare la disuguaglianza:

\sum_{i=1}^{N}2^{-l\left(\alpha_{i}\right)}\leq1

dove l\left(\alpha_{i}\right) è la lunghezza della stringa binaria corrispondente ad \alpha_{i}. Dati invece gli interi l\left(\alpha_{i}\right), i=1,...,N soddisfacenti la disuguaglianza precedente, esiste un codice binario per l'alfabeto A tale per cui la parola C\left(\alpha_{i}\right) ha lunghezza l\left(\alpha_{i}\right) e non esiste alcuna parola uguale ad un suo prefisso.

Dimostrazione (per codici a prefisso)[modifica | modifica sorgente]

È 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 0 o 1. 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 N parole e che le loro lunghezze siano m_{1}, m_{2}, ..., m_{N} con m_{1}\leq m_{2}\leq...\leq m_{N}, senza perdita di generalità. Essendo il codice a prefisso è possibile associare ad ogni foglia una diversa parola. L'albero ha altezza m_{N} e quindi un numero di foglie al più pari a 2^{m_{N}}. Procedendo ad un assegnamento delle parole di codice ai simboli che esse devono rappresentare, si può affermare che associando la foglia di profondità j si rimuovono tutte le parole con medesimo prefisso, che sono 2^{m_{N}-j}. La condizione da rispettare è che, una volta assegnate N-1 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:

2^{m_{N}}-\sum_{i=1}^{N-1}2^{m_{N}-m_{i}}\geq1

Ciò significa che:

2^{m_{N}}-\sum_{i=1}^{N-1}2^{m_{N}}\cdot\frac{1}{2^{m_{i}}}=2^{m_{N}}\cdot\left(1-\sum_{i=1}^{N-1}\frac{1}{2^{m_{i}}}\right)\geq1

ossia:

1-\sum_{i=1}^{N-1}2^{-m_{i}}\geq2^{-m_{N}}

che può essere riscritta come:

\sum_{i=1}^{N}2^{-m_{i}}\leq1

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

Bibliografia[modifica | modifica sorgente]

Information Theory, Inference & Learning Algorithms Cambridge University Press New York, NY, USA ©2002 ISBN:0521642981