Uma fonte discreta sem memória (DMS) emite cinco símbolos com probabilidades
p_{1}=0.4, p_{2}=0.19, p_{3}=0.16, p_{4}=0.15 \text { e } p_{5}=0.1
Pede-se:
a) Construa um código de Shannon-Fano.
b) Calcule a entropia da fonte, o comprimento médio do código do item anterior e a sua eficiência.
c) Construa um código de Huffman.
d) Calcule a entropia da fonte, o comprimento médio do código do item anterior e a sua eficiência.
e) Compare a eficiência alcançada nas duas formas de codificação.
Passo 1
O enunciado dá uma fonte discreta sem memória com cinco símbolos e probabilidades
(b) calcular a entropia da fonte, o comprimento médio do código do item (a) e a eficiência desse código;
(c) construir um código de Huffman;
(d) calcular a entropia da fonte, o comprimento médio do código do item (c) e a eficiência desse código;
(e) comparar as eficiências obtidas em (b) e (d).
Anotações úteis (dados já listados): a soma das probabilidades é 1. A solução precisa mostrar os códigos, os cálculos de entropia, os comprimentos médios e as eficiências.
Passo 2
Vou calcular a entropia da fonte passo a passo e explicar a fórmula usada.
Definição / fórmula usada:
H = -\sum_{i=1}^{5} p_i \log_2 p_i,
onde H é a entropia em bits por símbolo, p_i é a probabilidade do i-ésimo símbolo e \log_2 é o logaritmo em base 2. Essa fórmula mede a quantidade média de informação por símbolo; cada termo -p_i\log_2 p_i é a contribuição média do símbolo i.
Cálculo termo a termo (apresento os valores numéricos aproximados):
H \approx 0,528771+0,455226+0,423017+0,410545+0,332193=2,149752.
Arredondando de forma prática para uso posterior:
H \approx 2,1498\\ \text{bits por símbolo}.
Comentário didático rápido: a entropia nos dá um limite teórico inferior para o comprimento médio de qualquer código prefixo (em bits por símbolo). Idealmente deseja-se um código com comprimento médio próximo a H.]
Passo 3
Construção do código de Shannon–Fano (explicação do método e aplicação passo a passo).
Regra do método Shannon–Fano (em palavras simples):
Ordene os símbolos por probabilidade decrescente.
Divida a lista em duas partes cujo somatório de probabilidades seja o mais próximo possível entre as duas partes.
Atribua um bit (por exemplo 0 ao grupo da esquerda e 1 ao da direita).
Repita recursivamente dentro de cada grupo, concatenando bits, até cada símbolo ter um código único.
Aplicação aos nossos dados (ordem decrescente já dada):
\{0,4;\\\ 0,19;\\\ 0,16;\\\ 0,15;\\\ 0,10\}.
Primeiro corte: procurar separação com somas próximas a 0,5.
Soma dos dois primeiros: 0,4+0,19=0,59.
Soma do primeiro sozinho: 0,4.
Escolhe-se a separação que dá soma mais próxima (neste caso entre os dois primeiros e os três últimos), formando os grupos
Observação: há decisões de emparelhamento que podem levar a códigos diferentes em algumas implementações de Shannon–Fano, mas o procedimento acima é o padrão de divisão por soma próxima.
Passo 4
Cálculo do comprimento médio do código Shannon–Fano e da eficiência (explicando as fórmulas).
Fórmula do comprimento médio:
\bar{L}=\sum_{i=1}^{5} p_i \ell_i,
onde \ell_i é o comprimento (número de bits) do código do símbolo i.
Interpretação curta: o código de Shannon–Fano atingiu comprimento médio 2,25 e eficiência cerca de 95,54\%, ou seja, estamos razoavelmente próximos do limite teórico H.
Passo 5
Construção do código de Huffman (explicação do método e aplicação passo a passo).
Regra do método Huffman (passos resumidos):
Ordene as probabilidades em ordem crescente.
Combine os dois símbolos (ou nós) com menores probabilidades em um nó novo cuja probabilidade é a soma das duas.
Repetir: inserir esse novo nó na lista e combinar novamente os dois menores, até restar um único nó.
Ao construir a árvore, atribui-se bits 0 e 1 às duas ramificações a partir de cada nó (a escolha 0/1 à esquerda/direita é arbitrária, o que importa é mantê-la consistente). O código de cada símbolo é a sequência de bits do caminho da raiz até a folha correspondente.
Aplicação aos nossos dados (lista inicial em ordem crescente):
\{0,10;\\\ 0,15;\\\ 0,16;\\\ 0,19;\\\ 0,4\}.
Combine os dois menores: 0,10+0,15=0,25. Nova lista:
\{0,16;\\\ 0,19;\\\ 0,25;\\\ 0,4\}.
Combine os dois menores da nova lista: 0,16+0,19=0,35. Nova lista:
\{0,25;\\\ 0,35;\\\ 0,4\}.
Combine os dois menores: 0,25+0,35=0,60. Nova lista:
\{0,4;\\\ 0,60\}.
Combine os últimos: 0,4+0,60=1,0 — árvore completa.
Agora atribuímos bits subindo pela árvore (uma escolha consistente):
No último passo combinei 0,4 com 0,60; dou bit 0 para o ramo de 0,4 e bit 1 para o ramo de 0,60.
Em 0,60 (que veio de 0,25 e 0,35): dou 0 para 0,25 e 1 para 0,35.
Em 0,25 (que veio de 0,10 e 0,15): dou 0 para 0,10 e 1 para 0,15.
Em 0,35 (que veio de 0,16 e 0,19): dou 0 para 0,16 e 1 para 0,19.
Lendo os códigos da raiz até as folhas obtemos (cada passo concatena o bit correspondente):
Observação: a ordem dos bits 0/1 em cada ramificação poderia ser trocada (por exemplo dar 1 à esquerda), isso só altera os códigos por permutação, sem afetar comprimentos médios.
Passo 6
Cálculo do comprimento médio do código Huffman e da eficiência.
Conclusão direta: o código de Huffman é mais eficiente neste caso, alcançando cerca de 2,18 pontos percentuais a mais de eficiência absoluta (aproximadamente 97,72\%-95,54\%=2,18\%) e tendo comprimento médio 0,05 bits por símbolo menor que o de Shannon–Fano.
Resposta
a) Código de Shannon–Fano: p_1=00,\\ p_2=01,\\ p_3=10,\\ p_4=110,\\ p_5=111
b) H\approx2,1498\\ \text{bits/símbolo}í \bar{L}_{\text{SF}}=2,25\\ \text{bits/símbolo}í \eta_{\text{SF}}\approx95,54\%
c) Código de Huffman: p_1=0,\\ p_2=111,\\ p_3=110,\\ p_4=101,\\ p_5=100