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

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

onde ${\displaystyle r}$ é o número de símbolos do alfabeto do código, ${\displaystyle M}$ o total de palavras-código e ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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á ${\displaystyle 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 ${\displaystyle r^{l_{max}}}$. Somando essas contribuições, temos:

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

Simplificando, obtemos

${\displaystyle \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 ${\displaystyle 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.[2]

Referências

1. Moser, Stefan M.; Chen, Po-Ning (2012). A Student's Guide to Coding and Information Theory. New York: Cambridge 
2. Figueiredo, Mário T. A. «Elementos de Teoria da Informação» (PDF). Consultado em 12 de agosto de 2016