Desigualdade de Kraft
A Desigualdade de Kraft é um importante teorema da Teoria de Códigos e Teoria da Informação usado para verificar se um código é livre de prefixo, ou seja, se todas as palavras-código são folhas na representação em árvore.
Definição
Em codificação de fonte, é necessário que todo código seja unicamente decodificável. Porém, ter esta condição como verdadeira muitas vezes não é o suficiente para uma decodificação prática, uma vez que, se o código não for livre de prefixo, mesmo sendo unicamente decodificável, há um acréscimo computacional no algoritmo de decodificação. Por esse motivo, é interessante uma codificação livre de prefixo, de forma que a decodificação possa ser instantânea.[1]
Assim vemos que, para uma boa codificação de dados, é necessário impor restrições na estrutura de um código instantâneo de comprimento variável de modo a garantir a unicidade da decodificação.
A Desigualdade de Kraft estabelece a condição necessária e suficiente de existência de um código instantâneo formado por palavras de comprimento variável, que é:
,
onde é o número de símbolos do alfabeto do código, o total de palavras-código e é o comprimento associado à i-ésima palavra-código.
Demonstração
Provamos a desigualdade de Kraft usando um raciocínio simples baseado na árvore de codificação.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Arvore2.png/220px-Arvore2.png)
Consideremos uma árvore r–ária onde cada nó tem r descendentes. Suponhamos ainda que cada ramo representa um símbolo da palavra-código. Por exemplo, os r ramos que partem da raiz da árvore representam os r possíveis valores do primeiro símbolo da palavra-código. Cada palavra-código corresponde a uma folha da árvore. O percurso entre a raiz e uma dessas folhas identifica os símbolos que fazem parte da palavra-código, conforme mostrado na Figura 1, para o caso binário .
A condição do código ser livre de prefixo implica que nenhuma palavra-código seja ancestral de qualquer outra palavra-código na árvore, ou seja, um ramo não pode ser uma palavra-código, somente as folhas podem exercer esse papel. Assim, cada palavra-código elimina os seus descendentes como possíveis palavras-código. Seja o comprimento da palavra mais longa do código. Consideremos todas as folhas ao nível máximo da árvore, como visto na Figura 2. Algumas folhas são palavras-código, enquanto outras são descendentes de palavras-código.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Arvore1.png/220px-Arvore1.png)
Qualquer palavra código terá descendentes no nível máximo, assim o número total de nós desse conjunto deverá ser inferior ou igual a . Somando essas contribuições, temos:
.
Simplificando, obtemos
,
que é a desigualdade de Kraft, conforme definimos na primeira seção.
Por outro lado, dado um conjunto de comprimentos de palavras-código que satisfazem a desigualdade de Kraft, é sempre possível construir uma árvore semelhante à da Figura 1, de modo a se obter um código livre de prefixo cujas palavras têm os comprimentos especificados.[2]