Disuguaglianza di Kraft-McMillan

Questa voce o sezione sugli argomenti teorie dell'informatica e matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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.

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

${\displaystyle \sum _{i=1}^{N}2^{-l\left(\alpha _{i}\right)}\leq 1}$

dove ${\displaystyle l\left(\alpha _{i}\right)}$ è la lunghezza della stringa binaria corrispondente ad ${\displaystyle \alpha _{i}}$. Dati invece gli interi ${\displaystyle l\left(\alpha _{i}\right)}$, ${\displaystyle i=1,...,N}$ soddisfacenti la disuguaglianza precedente, esiste un codice binario per l'alfabeto ${\displaystyle A}$ tale per cui la parola ${\displaystyle C\left(\alpha _{i}\right)}$ ha lunghezza ${\displaystyle l\left(\alpha _{i}\right)}$ e non esiste alcuna parola uguale ad un suo 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 ${\displaystyle 0}$ o ${\displaystyle 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 ${\displaystyle N}$ parole e che le loro lunghezze siano ${\displaystyle m_{1},m_{2},...,m_{N}}$ con ${\displaystyle 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 ${\displaystyle m_{N}}$ e quindi un numero di foglie al più pari a ${\displaystyle 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à ${\displaystyle j}$ si rimuovono tutte le parole con medesimo prefisso, che sono ${\displaystyle 2^{m_{N}-j}}$. La condizione da rispettare è che, una volta assegnate ${\displaystyle 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:

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

Ciò significa che:

${\displaystyle 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:

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

che può essere riscritta come:

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle m_{i}}$ viene associata alla foglia a profondità ${\displaystyle m_{i}}$ nell'albero binario.

• 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.

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