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.

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 é:

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

onde $r$ é o número de símbolos do alfabeto do código, $M$ o total de palavras-código e $l_{i}$ é 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.

Figura 1: Árvore de codificação

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 $r=2$.

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 $l_{max}$ 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.

Figura 2: Árvore de codificação com todas as folhas no mesmo comprimento que a mais longa

Qualquer palavra código terá $r^{(l_{max}-l_{i})}$ descendentes no nível máximo, assim o número total de nós desse conjunto deverá ser inferior ou igual a $r^{l_{max}}$. Somando essas contribuições, temos:

$\sum _{i=1}^{M}r^{(l_{max}-l_{i})}\leq r^{l_{max}}$.

Simplificando, obtemos

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

que é a desigualdade de Kraft, conforme definimos na primeira seção.

Por outro lado, dado um conjunto de comprimentos $l_{1},l_{2},...,l_{M}$ 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.