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 de qualquer código unicamente decodificável devem satisfazer a desigualdade de Kraft dada abaixo, onde é o número de palavras-código e é o número de símbolos do alfabeto do código[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[2].
Consequências
[editar | editar código-fonte]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.
Referências
- ↑ McMillan, Brockway (1956), "Two inequalities implied by unique decipherability", IEEE Trans. Information Theory 2 (4): 115–116, doi:10.1109/TIT.1956.1056818.
- ↑ Moser, M. Stefan and Chen, Po-Ning. A Student’s Guide to Coding and Information Theory.