Fonte → Canal: Codificação em Dois Estágios
O Capítulo 10 de Hamming abre com o modelo de comunicação de Shannon, que se aplica a cada sistema que move informação: chamadas telefônicas, rádio, discos rígidos, replicação de DNA, memória de computador.
A Arquitetura de Dois Estágios
Estágio 1: Codificação de fonte (compressão). Converta a mensagem de origem para uma representação compacta. Objetivo: remover redundância nativa da fonte. Código Morse faz isso: letras comuns recebem códigos curtos, letras raras recebem códigos longos.
Estágio 2: Codificação de canal (proteção de erro). Adicione redundância controlada adaptada às características de ruído do canal. Uma linha telefônica com ruído precisa de mais redundância do que um cabo de fibra óptica. Os dois estágios se desacoplam: otimize cada um independentemente para sua própria tarefa.
A interface comum entre os dois estágios — um fluxo de bits padronizado — significa que qualquer fonte pode ser emparelhada com qualquer canal. Essa modularidade é a perspectiva arquitetônica-chave de Shannon.
Armazenamento como comunicação. Hamming observa que enviar uma mensagem pelo espaço (transmissão) e enviar pelo tempo (armazenamento) usam o mesmo modelo. Uma unidade de backup é um canal barulhento no tempo.
O Papel do Ruído
O modelo de Shannon faz uma suposição radical: o ruído é inevitável. Cada canal, cada meio de armazenamento, cada circuito de comutação introduz alguma probabilidade de erro. A pergunta não é 'como eliminamos o ruído?' mas 'como recuperamos a mensagem original apesar do ruído?'
Isso contrasta com a física clássica, onde o ruído entra como uma ideia posterior (o princípio da incerteza). Shannon trata o ruído como a condição fundamental — toda a teoria é construída a partir dele.
Por enquanto, o Capítulo 10 se concentra no caso sem ruído: codificação de fonte sem erros. O problema de codificação de canal (correção de erro) espera pelos capítulos posteriores.
Quando Você Pode Decodificar Univocamente?
Para que um código de comprimento variável seja útil, o receptor deve decodificar um fluxo de bits sem ambiguidade. Hamming ilustra com um código de 4 símbolos que falha neste teste, depois introduz a correção: códigos livres de prefixo.
Condição Livre de Prefixo
Um código é livre de prefixo (ou instantâneo) se nenhuma palavra-código é um prefixo de qualquer outra palavra-código. Dado um fluxo de bits recebido, você sabe que um símbolo terminou no momento em que atinge uma folha na árvore de decodificação — nenhuma pré-visualização necessária.
Exemplo de código livre de prefixo para {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifique: 0 não é um prefixo de 10, 110 ou 111. 10 não é um prefixo de 110 ou 111 (10 seguido por mais bits dá 100... ou 101..., nenhum dos quais começa com 110 ou 111). O código se qualifica.
O procedimento de decodificação: siga a árvore, ramifique em cada bit recebido, emita o símbolo quando atingir uma folha, retorne à raiz.
A Desigualdade de Kraft
Para qualquer código binário livre de prefixo com comprimentos de palavras-código l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
A igualdade vale quando o código é completo (folhas ladrilham a árvore binária completa sem lacunas). Esta é uma condição necessária: nenhum código livre de prefixo pode violá-la. Inversamente, para qualquer conjunto de comprimentos satisfazendo a desigualdade de Kraft, existe um código livre de prefixo.
Aplicando a Desigualdade de Kraft
Dados os comprimentos de código, verifique Kraft: Σ 2^(−l_i) ≤ 1.
Para {s1=0, s2=10, s3=110, s4=111}: comprimentos são 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Entropia de Shannon
O comprimento médio do código de um código de comprimento variável: L = Σ p_i · l_i, onde p_i é a probabilidade do símbolo s_i e l_i é seu comprimento de código.
Quão curto L pode ficar? A resposta de Shannon: não abaixo da entropia da fonte.
Entropia de Shannon: H = −Σ p_i · log₂(p_i) (unidades: bits/símbolo)
Entropia mede a informação média por símbolo. Alta entropia significa que os símbolos têm aproximadamente a mesma probabilidade (máxima imprevisibilidade). Baixa entropia significa que alguns símbolos dominam (alta previsibilidade, mais compressível).
Teorema de Codificação Sem Ruído
Para qualquer código livre de prefixo, H(fonte) ≤ L ≤ H(fonte) + 1.
Nenhum código pode vencer a entropia. A codificação de Huffman (próximo capítulo) atinge o limite superior: L < H + 1. Para códigos de bloco sobre n símbolos, o limite se aperta: H ≤ L/n < H + 1/n.
Entropia é também o limite teórico de compressão: você não pode comprimir uma fonte abaixo de H bits por símbolo sem perder informação.
Calculando Entropia
Exemplo: 4 símbolos com probabilidades p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits/símbolo
E o código de Huffman {0, 10, 110, 111} atinge L = 1.75 = H exatamente.
Por Que Entropia é um Limite Inferior
O limite inferior do teorema de codificação sem ruído não é apenas uma fórmula — reflete algo profundo sobre informação: você não pode comprimir o que já é maximamente imprevisível.
Quando todos os símbolos são igualmente prováveis (distribuição uniforme), entropia H = log₂(n) para n símbolos. Um código de bloco de comprimento log₂(n) bits atinge exatamente H. Nenhum código pode fazer melhor.
Quando um símbolo domina (digamos, p(A) = 0.99, p(B) = 0.01), H é pequeno — perto de 0. Um código de comprimento variável pode atribuir a A um código muito curto, codificando o fluxo de forma muito eficiente.
O aprendizado prático: grandes ganhos de compressão existem apenas quando as probabilidades dos símbolos diferem substancialmente. Se a fonte já é 'uniforme' (parecida com aleatória), a codificação de Huffman não ganha nada.