Teorema de McMillan

O Teorema de McMillan (ou desigualdade de McMillan) é um teorema publicado em 1956 pelo cientista norte-americano Brockway McMillan que diz que os comprimentos das palavras-código $l_{i}$ de qualquer código unicamente decodificável devem satisfazer a desigualdade de Kraft dada abaixo, onde $r$ é o número de palavras-código e $D$ é o número de símbolos do alfabeto do código:

$\sum _{i=1}^{r}D^{-l_{i}}\leq 1$

Ou seja, ele reduz a existência de códigos unicamente decodificáveis aos que satisfazem a desigualdade de Kraft. Esse Teorema pode ser visto como um caso da Desigualdade de Kraft para códigos unicamente decodificáveis, sendo também chamado de teorema de Kraft-McMillan. O resultado desses dois teoremas é que não há benefício algum de se criar um código unicamente decodificável que não seja livre de prefixo.

Consequências

Nota-se que todo código livre de prefixo também atende à desigualdade de Kraft. Então, para qualquer código unicamente decodificável, também existe um outro código com os mesmos comprimentos de palavras que, além disso, é livre de prefixo. Mas, se os comprimentos são os mesmos, o desempenho será igual e a melhor escolha deve ser sempre por aquele que é livre de prefixo para que a decodificação possa ser instantânea.

---