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çãoEditar

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çãoEditar

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  .

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.

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

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]

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