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
p_{1}=0,4,\quad p_{2}=0,19,\quad p_{3}=0,16,\quad p_{4}=0,15,\quad p_{5}=0,10.
As perguntas pedem:
  • (a) construir um código de Shannon–Fano;
  • (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):
\begin{aligned} -&p_1\log_2 p_1 = -0,4\log_2(0,4)=0,4\cdot1,321928\approx0,528771,\\[4pt] -&p_2\log_2 p_2 = -0,19\log_2(0,19)=0,19\cdot2,395928\approx0,455226,\\[4pt] -&p_3\log_2 p_3 = -0,16\log_2(0,16)=0,16\cdot2,643856\approx0,423017,\\[4pt] -&p_4\log_2 p_4 = -0,15\log_2(0,15)=0,15\cdot2,736966\approx0,410545,\\[4pt] -&p_5\log_2 p_5 = -0,10\log_2(0,10)=0,10\cdot3,321928\approx0,332193. \end{aligned}
Somando todas as contribuições:
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\}.
  1. 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
\text{grupo A}=\{0,4;\\\ 0,19\}\quad(\text{soma }0,59),\qquad \text{grupo B}=\{0,16;\\\ 0,15;\\\ 0,10\}\quad(\text{soma }0,41).
Atribui-se prefixo 0 ao grupo A e prefixo 1 ao grupo B.
  1. Dentro de grupo A ( \{0,4,0,19\}):
  • São dois símbolos; atribui-se 0 ao mais provável e 1 ao outro (após o prefixo do grupo).
    Portanto:
p_1\\ (0,4)\to 0\underbrace{0}=00,\qquad p_2\\ (0,19)\to 0\underbrace{1}=01.
  1. Dentro de grupo B ( \{0,16,0,15,0,10\}):
  • Tentar dividir em dois grupos com soma próxima a 0,205.
  • Primeiro item sozinho: 0,16 vs 0,15+0,10=0,25. Essa separação é razoável (mais equilibrada que as alternativas).
    Então:
\text{subgrupo B1}=\{0,16\}\quad(\text{soma }0,16)\\ \text{recebe prefixo }10,
\text{subgrupo B2}=\{0,15;\\\ 0,10\}\quad(\text{soma }0,25)\\ \text{recebe prefixo }11.
No subgrupo B2 (dois símbolos) atribuem-se bits finais 0 e 1:
p_4\\ (0,15)\to 11\underbrace{0}=110,\qquad p_5\\ (0,10)\to 11\underbrace{1}=111.
Para p_3 (0,16) já temos prefixo 10, como é um único símbolo ali seu código final é 10.
Resultado final do código de Shannon–Fano:
\begin{aligned} p_1 &= 00\quad(\text{comprimento }2),\\\ p_2 &= 01\quad(\text{comprimento }2),\\\ p_3 &= 10\quad(\text{comprimento }2),\\\ p_4 &= 110\quad(\text{comprimento }3),\\\ p_5 &= 111\quad(\text{comprimento }3). \end{aligned}
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.
Usando os comprimentos obtidos:
\ell_1=2,\\ \ell_2=2,\\ \ell_3=2,\\ \ell_4=3,\\ \ell_5=3.
Cálculo:
\bar{L}_{\text{SF}}=0,4\cdot2+0,19\cdot2+0,16\cdot2+0,15\cdot3+0,10\cdot3.
Agrupando:
\bar{L}_{\text{SF}}=(0,4+0,19+0,16)\cdot2+(0,15+0,10)\cdot3=0,75\cdot2+0,25\cdot3=1,5+0,75=2,25.
Portanto
\bar{L}_{\text{SF}}=2,25\\ \text{bits por símbolo}.í
Fórmula da eficiência:
\eta=\frac{H}{\bar{L}}.
Usando H\approx2,149752 e \bar{L}_{\text{SF}}=2,25:
\eta_{\text{SF}}=\frac{2,149752}{2,25}\approx0,955445\approx95,54\%.
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\}.
  1. Combine os dois menores: 0,10+0,15=0,25. Nova lista:
\{0,16;\\\ 0,19;\\\ 0,25;\\\ 0,4\}.
  1. Combine os dois menores da nova lista: 0,16+0,19=0,35. Nova lista:
\{0,25;\\\ 0,35;\\\ 0,4\}.
  1. Combine os dois menores: 0,25+0,35=0,60. Nova lista:
\{0,4;\\\ 0,60\}.
  1. 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):
\begin{aligned} p_1\\ (0,4) &\to 0\quad(\text{comprimento }1),\\\ p_2\\ (0,19) &\to 1\;1\;1 = 111\quad(\text{comprimento }3),\\\ p_3\\ (0,16) &\to 1\;1\;0 = 110\quad(\text{comprimento }3),\\\ p_4\\ (0,15) &\to 1\;0\;1 = 101\quad(\text{comprimento }3),\\\ p_5\\ (0,10) &\to 1\;0\;0 = 100\quad(\text{comprimento }3). \end{aligned}
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.
Usando comprimentos:
\ell_1=1,\quad \ell_2=\ell_3=\ell_4=\ell_5=3.
Cálculo do comprimento médio:
\bar{L}_{\text{H}}=0,4\cdot1+0,19\cdot3+0,16\cdot3+0,15\cdot3+0,10\cdot3.
Simplificando o segundo termo (soma das probabilidades dos símbolos com comprimento 3 é 0,19+0,16+0,15+0,10=0,60):
\bar{L}_{\text{H}}=0,4\cdot1+0,60\cdot3=0,4+1,8=2,2.
Portanto
\bar{L}_{\text{H}}=2,20\\ \text{bits por símbolo}.í
Eficiência:
\eta_{\text{H}}=\frac{H}{\bar{L}_{\text{H}}}=\frac{2,149752}{2,2}\approx0,977161\approx97,72\%.
Interpretação: o código de Huffman tem comprimento médio menor que o de Shannon–Fano aqui ( 2,20 vs 2,25), aproximando-se mais do limite H.

Passo 7

Comparação final das eficiências e conclusão numérica.
  • Entropia da fonte: H\approx2,1498\\ \text{bits/símbolo}í (valor comum aos dois códigos).
  • Código Shannon–Fano: \bar{L}_{\text{SF}}=2,25 bits/símbolo, \eta_{\text{SF}}\approx95,54\%.
  • Código Huffman: \bar{L}_{\text{H}}=2,20 bits/símbolo, \eta_{\text{H}}\approx97,72\%.
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
d) H\approx2,1498\\ \text{bits/símbolo}í
\bar{L}_{\text{H}}=2,20\\ \text{bits/símbolo}í
\eta_{\text{H}}\approx97,72\%
e) Comparação: o código de Huffman é mais eficiente (≈97,72% vs ≈95,54%), com comprimento médio menor ( 2,20 vs 2,25 bits/símbolo).

Exercícios relacionados