Uma fonte X produz símbolos com probabilidades \left(\begin{array}{lllllll}0,49 & 0,26 & 0,12 & 0,04 & 0,04 & 0,03 & 0,02\end{array}\right). Para esta fonte:
(a) Calcule a sua entropia;
(b) Ache um código de Shannon-Fano binário e calcule seu comprimento médio e eficiência;
(c) Ache um código de Huffman binário e calcule seu comprimento médio e eficiência.
(d) Ache um código de Huffman ternário e calcule seu comprimento médio e eficiência;
(e) Compare os resultados obtidos nos ítens (b)-(d) com aquele obtido no item (a).

Passo 1

O enunciado dá uma fonte X com sete símbolos cujas probabilidades, em ordem, são
\bigl(0,49,\;0,26,\;0,12,\;0,04,\;0,04,\;0,03,\;0,02\bigr).
As perguntas são:
(a) Calcular a entropia da fonte (em bits/símbolo).
(b) Construir um código de Shannon–Fano binário e calcular seu comprimento médio e eficiência.
(c) Construir um código de Huffman binário e calcular seu comprimento médio e eficiência.
(d) Construir um código de Huffman ternário e calcular seu comprimento médio (em trits e em bits) e eficiência.
(e) Comparar os resultados dos itens (b)–(d) com a entropia do item (a).
Lista explícita das probabilidades (vou chamar os símbolos de x_1,\dots,x_7 na mesma ordem):
p_1=0,49,\; p_2=0,26,\; p_3=0,12,\; p_4=0,04,\; p_5=0,04,\; p_6=0,03,\; p_7=0,02.

Passo 2

(a) Entropia: fórmula e interpretação.
A entropia de uma fonte discreta X é
H(X)=-\sum_{i=1}^{7} p_i\log_2 p_i,
onde \log_2 é o logaritmo na base 2 e H(X) tem unidades de bits por símbolo. Cada termo -p_i\log_2 p_i mede a “incerteza” associada ao símbolo i.
Vou calcular termo a termo (mostrando os passos de cálculo):
Para p_1=0,49:
-p_1\log_2 p_1 = -0,49\log_2(0,49) \approx 0,49\cdot 1,02917 \approx 0,50431.
Para p_2=0,26:
-p_2\log_2 p_2 \approx 0,26\cdot 1,94342 \approx 0,50529.
Para p_3=0,12:
-p_3\log_2 p_3 \approx 0,12\cdot 3,05797 \approx 0,36696.
Para p_4=0,04 (os dois símbolos com 0,04 darão o mesmo termo):
-p_4\log_2 p_4 \approx 0,04\cdot 4,64386 \approx 0,18575.
Como há dois símbolos com 0,04, a contribuição total desses dois é 2\cdot 0,18575 \approx 0,37151.
Para p_6=0,03:
-p_6\log_2 p_6 \approx 0,03\cdot 5,05889 \approx 0,15177.
Para p_7=0,02:
-p_7\log_2 p_7 \approx 0,02\cdot 5,64386 \approx 0,11288.
Agora somo todos os termos para obter H(X):
H(X)\approx 0,50431+0,50529+0,36696+0,37151+0,15177+0,11288 \approx 2,01272\\ \text{bits/símbolo}.í
Portanto a entropia da fonte é aproximadamente \,H(X)\approx 2,013\\ \text{bits/símbolo}.í

Passo 3

(b) Código de Shannon–Fano (binário): explicação do método e construção.
Breve explicação do método Shannon–Fano: ordenar símbolos por probabilidade decrescente; dividir a lista em dois grupos com somas de probabilidade o mais próximas possível; atribuir aos dois grupos bits distintos (por exemplo 0 e 1); repetir recursivamente em cada grupo até que cada símbolo tenha um código. Não é garantidamente ótimo, mas é um esquema direto.
Aplicando ao nosso vetor ordenado (já ordenado):
0,49;\;0,26;\;0,12;\;0,04;\;0,04;\;0,03;\;0,02.
  1. Divisão inicial: melhor separação é after 0,49 (soma 0,49 vs 0,51). Logo x_1 recebe prefixo 0 e os demais prefixo 1.
  2. No grupo com soma 0,51 (os outros seis), melhor separação é \{0,26\} vs \{0,12,0,04,0,04,0,03,0,02\}. Então x_2 recebe prefixo 10 e o restante 11.
  3. No grupo com soma 0,25 (desde 0,12 em diante), separar 0,12 vs 0,13 (resto). Assim x_3 recebe 110 e o restante 111.
  4. No grupo 0,13 (os quatro menores) a melhor separação foi \{0,04,0,04\} vs \{0,03,0,02\} — a divisão usada aqui acabou sendo \{0,04,0,04\} com prefixo 1110 e \{0,03,0,02\} com prefixo 1111.
  5. Dividindo as duplas finais em símbolos individuais, obtém-se códigos finais.
Códigos Shannon–Fano resultantes (associados a x_1,\dots,x_7 na ordem dada):
\begin{array}{lcl} x_1 &:& 0\\[2pt] x_2 &:& 10\\[2pt] x_3 &:& 110\\[2pt] x_4 &:& 11100\\[2pt] x_5 &:& 11101\\[2pt] x_6 &:& 11110\\[2pt] x_7 &:& 11111 \end{array}
Comprimentos \ell_i: 1,2,3,5,5,5,5.
Agora o comprimento médio L_{SF} é
L_{SF}=\sum_{i=1}^7 p_i\ell_i.
Calculando termo a termo:
\begin{aligned} 0,49\cdot 1 &=0,49,\\\\ 0,26\cdot 2 &=0,52,\\\\ 0,12\cdot 3 &=0,36,\\\\ 0,04\cdot 5 &=0,20,\\\\ 0,04\cdot 5 &=0,20,\\\\ 0,03\cdot 5 &=0,15,\\\\ 0,02\cdot 5 &=0,10. \end{aligned}
Somando:
L_{SF}\approx 2,02\\ \text{bits/símbolo}.í
Eficiência do código (definição): \eta = \dfrac{H(X)}{L}. Então
\eta_{SF}=\frac{2,01272}{2,02}\approx 0,9964\quad(\text{ou }99,64\%).]

Passo 4

(c) Código de Huffman binário: algoritmo, construção e cálculo.
Explicação rápida do algoritmo Huffman (binário): combinar repetidamente os dois símbolos/nós de menor probabilidade, formando um nó com probabilidade igual à soma; repetir até restar um nó. Em seguida, atribuir 0/1 a cada bifurcação para obter códigos prefixos ótimos (mínimo comprimento médio possível em código binário prefixo).
Construção passo a passo (probabilidades iniciais):
0,49;\;0,26;\;0,12;\;0,04;\;0,04;\;0,03;\;0,02.
  1. Combinar 0,02 e 0,03 \to 0,05.
  2. Agora temos 0,04,0,04,0,05,0,12,0,26,0,49. Combinar 0,04 e 0,04 \to 0,08.
  3. Lista: 0,05,0,08,0,12,0,26,0,49. Combinar 0,05 e 0,08 \to 0,13.
  4. Lista: 0,12,0,13,0,26,0,49. Combinar 0,12 e 0,13 \to 0,25.
  5. Lista: 0,25,0,26,0,49. Combinar 0,25 e 0,26 \to 0,51.
  6. Finalmente combinar 0,49 e 0,51 \to raiz 1,0.
Atribuindo bits (uma escolha consistente: sempre “esquerda=0, direita=1”) e lendo do topo para as folhas obtemos, por exemplo, os códigos:
\begin{array}{lcl} x_1 &:& 0\\[2pt] x_2 &:& 11\\[2pt] x_3 &:& 100\\[2pt] x_4 &:& 10110\\[2pt] x_5 &:& 10111\\[2pt] x_6 &:& 10101\\[2pt] x_7 &:& 10100 \end{array}
(repare que os comprimentos resultam iguais aos do Shannon–Fano neste caso: 1,2,3,5,5,5,5).
Comprimento médio L_{H}:
os mesmos termos que no passo anterior dão
L_{H}=\sum_{i} p_i\ell_i \approx 2,02\\ \text{bits/símbolo}.í
Eficiência:
\eta_{H}=\frac{H(X)}{L_H}=\frac{2,01272}{2,02}\approx 0,9964\\ (99,64\%).
Observação didática curta: Huffman é ótimo entre códigos prefixos binários, portanto não existe código binário prefixo com comprimento médio menor que 2,02 para esta distribuição (exceto empacotamento/variação de blocos). O Shannon–Fano aqui foi quase tão bom quanto o Huffman, produzindo o mesmo comprimento médio.]

Passo 5

(d) Código de Huffman ternário: regra geral, ajuste e construção.
Para Huffman em alfabeto ternário (símbolos do código com 3 valores: por ex. \{0,1,2\}), a versão geral do algoritmo combina os D menores nós a cada etapa, mas é preciso primeiro verificar a condição para que a árvore fique completa: com n símbolos e alfabeto de ordem D a condição para não precisar inserir símbolos fictícios é (n-1)\bmod(D-1)=0. Aqui n=7 e D=3, então D-1=2 e (7-1)\bmod 2 = 6\bmod 2=0. Logo não é necessário acrescentar símbolos fictícios.
Procedimento (combinar três menores a cada passo):
Probabilidades iniciais ordenadas:
0,02;\;0,03;\;0,04;\;0,04;\;0,12;\;0,26;\;0,49.
  1. Combinar os três menores 0,02+0,03+0,04=0,09 (formando nó A).
    Restam 0,04,0,09,0,12,0,26,0,49.
  2. Combinar os três menores 0,04+0,09+0,12=0,25 (formando nó B).
    Restam 0,25,0,26,0,49.
  3. Combinar esses três 0,25+0,26+0,49=1,0 (raiz). Fim.
Atribuindo os dígitos ternários (por exemplo 0,1,2 em cada nó, da esquerda para a direita), uma possível atribuição de códigos (em trits) é:
  • Na raiz: filho correspondente a B → prefixo 0; filho correspondente a x_2 (0,26) → prefixo 1; filho correspondente a x_1 (0,49) → prefixo 2. Assim x_1 e x_2 têm códigos de comprimento 1 trit.
  • No nó B (prefixo 0), seus filhos eram x_4 (0,04), A (0,09) e x_3 (0,12). Atribuindo em ordem 0,1,2 temos:
    • x_4: 00 (2 trits)
    • A: 01 (prefixo para os três mais pequenos)
    • x_3: 02 (2 trits)
  • No nó A (prefixo 01), filhos x_7 (0,02), x_6 (0,03), x_5 (0,04) recebem 0,1,2 respectivamente:
    • x_7: 010 (3 trits)
    • x_6: 011 (3 trits)
    • x_5: 012 (3 trits)
Resumo dos códigos ternários (em trits) para x_1,\dots,x_7:
\begin{array}{lcl} x_1 &:& 2 \quad (\ell=1)\\[2pt] x_2 &:& 1 \quad (\ell=1)\\[2pt] x_3 &:& 02 \quad (\ell=2)\\[2pt] x_4 &:& 00 \quad (\ell=2)\\[2pt] x_5 &:& 012 \quad (\ell=3)\\[2pt] x_6 &:& 011 \quad (\ell=3)\\[2pt] x_7 &:& 010 \quad (\ell=3) \end{array}
Comprimento médio em trits:
L_{3}=\sum_{i=1}^7 p_i\ell_i = 0,49\cdot1+0,26\cdot1+0,12\cdot2+0,04\cdot2+0,04\cdot3+0,03\cdot3+0,02\cdot3.
Calculando:
L_{3}\approx 0,49+0,26+0,24+0,08+0,12+0,09+0,06=1,34\\ \text{trits/símbolo}.í
Cada trit representa \log_2 3\approx 1,5849625 bits. Portanto o comprimento médio em bits é
L_{3,\text{bits}} = L_{3}\log_2 3 \approx 1,34\cdot 1,5849625 \approx 2,12385\\ \text{bits/símbolo}.í
Eficiência:
\eta_{3}=\frac{H(X)}{L_{3,\text{bits}}}=\frac{2,01272}{2,12385}\approx 0,9472\quad(94,72\%).]

Passo 6

(e) Comparação e interpretação dos resultados.
Resumo numérico (para fácil comparação):
  • Entropia: H(X)\approx 2,01272\\ \text{bits/símbolo}.í
  • Shannon–Fano (binário): L_{SF}\approx 2,02 bits/símbolo, \eta_{SF}\approx 0,9964. Redundância L-H\approx 0,00728 bits/símbolo.
  • Huffman (binário): L_{H}\approx 2,02 bits/símbolo, \eta_{H}\approx 0,9964. (Huffman é ótimo entre códigos binários prefixo; aqui o comprimento médio coincide com o do SF.)
  • Huffman (ternário): L_3\approx 1,34 trits/símbolo \Rightarrow L_{3,\text{bits}}\approx 2,12385 bits/símbolo, \eta_3\approx 0,9472. Redundância L_{3,\text{bits}}-H\approx 0,11113 bits/símbolo.
Interpretação intuitiva e motivação para a diferença:
  • A entropia é um limite teórico para o melhor comprimento médio possível em bits por símbolo (sem restrições sobre o alfabeto do código ou estrutura).
  • Entre códigos binários prefixo, o código de Huffman é ótimo; aqui ele alcançou L\approx 2,02, muito próximo de H (diferença \approx 0,007 bits por símbolo). Isso significa que com código binário simples obteve-se eficiência superior a 99{,}6\%.
  • O código ternário tem menos “granularidade” porque trabalha em trits (cada trit = 1{,}58496 bits). Mesmo tendo comprimentos médios menores em trits (1,34 trits), ao converter para bits isso ficou mais longe da entropia (≈2,124 bits), portanto eficiência menor. Em outras palavras, a base do código (2 vs 3) influencia a aproximação ao valor real da entropia em bits; escolher alfabetos com tamanho que não se harmoniza bem com a entropia em bits pode produzir maior “espaço desperdiçado”.
  • Conclusão prática: para esta distribuição a escolha binária com Huffman é quase ideal; o código ternário resulta em maior comprimento médio em bits.

Resposta

(a) H(X)\approx 2,01272\\ \text{bits/símbolo}.í
(b) Código Shannon–Fano (associado a x_1,\dots,x_7): x_1:0,\;x_2:10,\;x_3:110,\;x_4:11100,\;x_5:11101,\;x_6:11110,\;x_7:11111. Comprimento médio L_{SF}\approx 2,02\\ \text{bits/símbolo}í. Eficiência \eta_{SF}\approx 0,9964 (99,64%).
(c) Código Huffman binário (uma escolha possível): x_1:0,\;x_2:11,\;x_3:100,\;x_4:10110,\;x_5:10111,\;x_6:10101,\;x_7:10100. Comprimento médio L_H\approx 2,02\\ \text{bits/símbolo}í. Eficiência \eta_H\approx 0,9964 (99,64%).
(d) Código Huffman ternário (em trits): x_1:2,\;x_2:1,\;x_3:02,\;x_4:00,\;x_5:012,\;x_6:011,\;x_7:010. Comprimento médio L_3\approx 1,34\\ \text{trits/símbolo}í, que equivale a L_{3,\text{bits}}\approx 2,12385\\ \text{bits/símbolo}í. Eficiência \eta_3\approx 0,9472 (94,72%).
(e) Comparação: os códigos binários (Shannon–Fano e Huffman) chegam muito perto da entropia (diferença ≈ 0,0073 bits/símbolo, eficiência ≈ 99,64%). O Huffman ternário, quando convertido para bits, fica mais longe da entropia (diferença ≈ 0,1111 bits/símbolo, eficiência ≈ 94,72%). Portanto, para esta distribuição, o código binário Huffman é praticamente ótimo e melhor que a alternativa ternária.

Exercícios relacionados