Il teorema di McMillan
Nella teoria dell'informazione il teorema di McMillan (o disuguaglianza di Kraft-McMillan) fornisce una condizione necessaria e sufficiente per stabilire se un codice prefisso è univocamente decodificabile oppure no. Questo teorema dice che:
Un insieme di lunghezze di stringhe \( \{s_1, s_2, ..., s_n\} \) su un alfabeto di r simboli è un codice prefisso univocamente decodificabile se e solo se la seguente disuguaglianza è soddisfatta: $$ \sum_{i=1}^{n} r^{-s_i} \leq 1 $$ Dove \( r \) è il numero di simboli nell'alfabeto del codice (ad esempio, \( r = 2 \) per un codice binario), e \( s_i \) è la lunghezza della stringa codificata corrispondente al simbolo \( i \).
Se questa somma è inferiore o uguale a 1, allora possiamo costruire un codice prefisso che sia univocamente decodificabile.
Il teorema implica anche che se un tale codice esiste, la somma delle lunghezze dei suoi codici elevati alla potenza negativa del numero di simboli nell'alfabeto non può superare 1.
In altre parole, il teorema di McMillan ci permette di capire se un insieme di stringhe {s1,s2,...,sn} ottenuto con un alfabeto di n simboli è a sua volta un alfabeto oppure no.
Il teorema di McMillan si applica sui codici prefissi. Un codice prefisso è un codice in cui ogni stringa nell'insieme deve anche essere tale che nessuna stringa è un prefisso di un'altra. Ad esempio, questo codice non è prefisso perché la stringa "0" è il prefisso della stringa "01". $$ \{s_1, s_2, s_3\} = \{"0", "01", "11"\} $$ Viceversa, questo è un codice prefisso perché nessuna stringa è prefisso di un'altra. $$ \{s_1, s_2, s_3\} = \{"00", "01", "11"\} $$
Esempio
Facciamo un esempio concreto per spiegare il teorema di McMillan.
Supponiamo di avere un semplice alfabeto binario con \( r = 2 \) simboli, che possono essere 0 e 1.
Ora creiamo un insieme di stringhe con questo alfabeto:
$$ \{s_1, s_2, s_3\} = \{"00", "01", "11"\} $$
E' un codice prefisso perché nessuna stringa è prefisso di un'altra stringa.
Bisogna però verificare se è anche un codice univocamente decodificabile. Per farlo utilizziamo il teorema di McMillan.
La lunghezza di \( s_1 = "00" \) è 2, la lunghezza di \( s_2 = "01" \) è 2, e la lunghezza di \( s_3 ="11" \) è anche 2.
Ora applichiamo il teorema:
$$ \sum_{i=1}^{3} 2^{-|s_i|} = 2^{-2} + 2^{-2} + 2^{-2} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} = \frac{3}{4} $$
In questo caso, la somma è minore di 1 e rispetta la condizione del teorema di McMillan.
$$ \sum_{i=1}^{3} 2^{-|s_i|} = \frac{3}{4} \le 1 $$
Questo significa che questo particolare insieme di stringhe {s1,s2,s3} può essere considerato un "codice univocamente decodificabile" in base ai criteri del teorema.
Nota. Se considerassimo tutte le permutazioni possibili dei simboli "0" e "1" dell'alfabeto binario otterremmo un insieme composto da quattro stringhe. $$ \{s_1, s_2, s_3, s_4\} = \{"00", "01", "11, "10""\} $$ In questo caso il teorema di McMillan restituisce esattamente una somma pari a 1. $$ \sum_{i=1}^{4} 2^{-|s_i|} = 2^{-2} + 2^{-2} + 2^{-2} + 2^{-2} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} = 1 $$ Questo ci fornisce il limite alla quantità di informazioni che possiamo rappresentare con una serie di stringhe dell'alfabeto.
