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.

Enunciato

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)}\leq 1$

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)

È 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}}\geq 1$

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)\geq 1$

ossia:

$1-\sum _{i=1}^{N-1}2^{-m_{i}}\geq 2^{-m_{N}}$

che può essere riscritta come:

$\sum _{i=1}^{N}2^{-m_{i}}\leq 1$

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

• Leon G. Kraft, A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA, MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology, 1949.

• Brockway McMillan, Two inequalities implied by unique decipherability, in IEEE Trans. Information Theory, vol. 2, n. 4, 1956, pp. 115–116, DOI:10.1109/TIT.1956.1056818.