Fundamentos de
Codificação de Sinais
Prof. Marcus Vinicius Lamar
1
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1. Introdução
-Importância da codificação nos dias de hoje:
-Internet, TV, telefone, celular, modem, ...
Compressão de Dados:
Arte ou Ciência de representar a informação de uma forma
compacta.
Identificando e usando estruturas presentes nos dados ou
explorando características do usuário final.
Objetivo: Transmissão ou Armazenamento eficiente.
TE073 – Processamento Digital de Sinais II
2
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.:
3 minutos de música qualidade de CD – estéreo necessita:
bytes
3 60seg  44100amostras

2
seg
amostra  2 canais 31.752.000bytes 30,28Mibytes
10 Fotos 10x15cm com resolução de 600dpi(240dpc) coloridas:
pixel
bytes
10 fotos 10cm  240 pixel

15
cm

240

3
 247,19 Mibytes
cm
cm
pixel
TE073 – Processamento Digital de Sinais II
3
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
2 horas de vídeo tamanho VGA true color necessita:
pixel
bits
24 pixel
 640 480 quadro
 24 quadros
seg  2  60 60seg  148,32Gibytes
Ou
pixel
bits
24 pixel
 640 480quadro
 24 quadros
seg  168,75Mibits / seg
TE073 – Processamento Digital de Sinais II
4
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
A tecnologia que define a capacidade de armazenamento e/ou
transmissão está em constante crescimento,
porém a necessidade humana cresce 2 vezes mais rápido.
Lei de Parkinson:
“O trabalho se expande de modo a ocupar todo tempo disponível”
Além do mais, existem limites a serem atingidos.
Transmissão: propriedades do canal (banda) e ruído
Armazenamento: limites físicos (átomo, elétron, sub-atômicas)
TE073 – Processamento Digital de Sinais II
5
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Primeira forma de codificação/compressão de sinais:
Código Morse (Samuel Morse, metade século XIX)
-A cada letra é alocado um símbolo (pontos e linhas) cujo comprimento é
inversamente proporcional à sua probabilidade de ocorrência. Aumentando assim
a velocidade média da transmissão
Ex:
e: a: –
q: – –  – j:  – – –
>Inspirou o código de Huffman
Outros: Alfabeto Braille (array 2x3)
Logo posso representar 26=64 símbolos, 26 letras
Braille 2 usa os 38 restantes para codificar números e palavras freqüentemente
usadas.
TE073 – Processamento Digital de Sinais II
6
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Usou-se nesses exemplos a estrutura estatística para fazer a compressão.
Outros tipos de estruturas:
-Voz: produzida pelo aparelho vocal humano é limitada, logo há uma
estrutura que pode ser utilizada.
Vocoder LPC (1936/39, Bell Labs.) Ex.:Spelling&Spell (E.T.)
Outra forma de compressão explora as limitações do consumidor final
do sinal.
Ex.: Humanos: não conseguem ouvir altas frequência. que cães podem.
Visão humana também é limitada em resolução espacial, temporal
e de crominâncias.
Se algo não é perceptível para que preservá-lo?
TE073 – Processamento Digital de Sinais II
7
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1.1. Técnicas de Compressão
2 algoritmos: Codificador/Compressor e Decodificador/Descompressor
X
coder
Xc
decoder
Y
Canal
s/ ruído
X=Y
Codificação sem perdas (lossless compression)
XY
Codificação com perdas (lossy compression)
TE073 – Processamento Digital de Sinais II
8
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1.1.1. Codificação sem Perdas
Não há perda de informação durante o processo de
Codificação/Decodificação.
Usado em sistemas onde erros não são tolerados:
- Compressão de arquivos de texto, executáveis, dados
“Alteraxão da enforcação não é bolerada”
- Compressão de imagens médicas
Vidas em risco
TE073 – Processamento Digital de Sinais II
9
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1.1.2. Codificação com Perdas
Há algum tipo de perda de informação durante o processo de
Codificação/Decodificação. O dado original dificilmente pode ser
recuperado.
O ganho de ter distorção no dado recuperado é um ganho de
codificação muito maior (maior compressão).
Ex.: Voz, não necessita ser exatamente igual, basta ser inteligível.
Imagem, basta ter qualidade aceitável
Necessitamos de meios para medir o desempenho.
TE073 – Processamento Digital de Sinais II
10
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1.1.3. Medidas do desempenho
Medidas de desempenho de um algoritmo de codificação:
-Complexidade computacional
-Aplicabilidade em tempo-real (ex:celular, HDTV,etc)
-Medida pelo tempo gasto em uma determinada máquina
-Medida pelo número e tipo de operações matemáticas e lógicas
(,,,log,raiz, sen, if, etc) e memória requerida.
TE073 – Processamento Digital de Sinais II
11
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
-Ganho de codificação (taxa de compressão)
Ex.: imagem 256x256 pixels a 8 bits/pixel (gray)
necessita 65536 bytes
comprimido resultou um arquivo de 16384 bytes
-Porcentagem do resultante em relação ao original: 75%
-Proporção 4:1
-Taxa de bits: 2 bits/pixel
-Qualidade da Reconstrução:
Sem Perdas: Qualidade total
Com perdas: Há distorção do sinal recuperado, medida através
de EMQ, SNR, PSNR, distâncias: Euclidiana, Mahalanobis, etc.
TE073 – Processamento Digital de Sinais II
12
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
1.2. Modelagem e Codificação
Um sistema de codificação pode ser dividido em 2 partes:
-Modelagem
-Codificação
Criar um modelo para o dado e uma descrição sobre como o
dado real difere do modelo.
TE073 – Processamento Digital de Sinais II
13
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Exemplo 1:
Considere a seguinte seqüência de números {x1,x2,x3,...}:
9 , 11 , 11 , 11 , 14 , 13 , 15 , 17 , 16 , 17 , 20 , 21
Para transmitir esta sequência necessitamos representar cada um
usando 5 bits por amostra. Totalizando: 12x5=60 bits
TE073 – Processamento Digital de Sinais II
14
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Observando sua representação gráfica:
25
20
15
10
5
0
0
2
4
6
8
10
12
14
Nota-se que podemos modelar estes dados como:
TE073 – Processamento Digital de Sinais II
xˆn  n  8
15
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Logo a estrutura dos dados pode ser caracterizada por uma eq.
O resíduo do dado real e o modelo pode ser calculado como:
en  xn  xˆn
Que resulta na sequência:
0 , 1 , 0 , –1 , 1 , –1 , 0 , 1 , –1 , –1 , 1 , 1
Que pode ser representada com apenas 2 bits / amostra
Assim, codificamos o sinal através do armazenamento/transmissão
do modelo e do resíduo.
Resultado: 3 bits modelo + 12x2 resíduo: total: 27 bits
Compressão de 2,22:1 ou 2,25 bits/amostra
TE073 – Processamento Digital de Sinais II
16
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex. 2: Considere a sequência
27 , 28 , 29, 28 , 26 , 27, 29 , 28 , 30 , 32 , 34 , 36 , 38
Requerendo: 13 x 6 = 78 bits
Não há um modelo simples para representar.
Porém observa-se pelo gráfico que os valores seguintes são
próximos dos anteriores:
40
35
30
25
20
15
10
5
0
0
2
4
6
8
10
12
TE073 – Processamento Digital de Sinais II
14
17
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Enviando o primeiro valor e depois as diferenças entre o atual e o
seguinte obtemos a sequência:
27, 1, 1, -1, -2, 1, 2, -1, 2, 2, 2, 2, 2
Que pode ser enviada usando: 5 + 3 x 12=41 bits
Técnica chamada: Codificação Preditiva
TE073 – Processamento Digital de Sinais II
18
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.3: Modelo estatístico
Considere a seguinte sequência:
a_barayaran_array_ran_far_faar_faaar_away
Há 8 diferentes símbolos, que requerem 3 bits p/ representação
Resultando em 41x3=123 bits
Porém, se utilizarmos a tabela:
Necessitamos 106 bits p/ representar a
sequência,
O que gera uma taxa de 2.58 bits/símbolo
TE073 – Processamento Digital de Sinais II
a
1
_
001
b
01100
f
0100
n
0111
r
000
w
01101
y
0101
19
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Em textos é comum encontrarmos palavras que se repetem com
frequência, que podem ser agrupadas em um dicionário e
representadas apenas pelo índice neste dicionário. (LZ77, LZW)
Decompor os dados em diversas componentes, analisando os
modelos para cada componente, é outra alternativa (Subbandas,
Transformadas, Wavelets)
Padrões internacionais foram criados de modo a permitir que
diferentes pudessem implementações de codificadores comunicarse entre si. JPEG, MPEG, H.261, H.263, etc...
TE073 – Processamento Digital de Sinais II
20
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
2. Conceitos Matemáticos Importantes
- Pré-requisito: Conhecimentos de Probabilidade e Estatística
2.1. Introdução à Teoria da Informação:
Claude Elwood Shannon (Bell Labs) criou esta área do
conhecimento em 1948 com a publicação de um artigo que define os
conceitos mais básicos da Teoria da Informação.
C.E.Shannon. A Mathematical Theory of Communication. Bell System
Technical Journal. 27:379-423, 623-656, 1948
TE073 – Processamento Digital de Sinais II
21
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantidade de Informação:
 1 
   logb P( A)
i( A)  logb 
 P( A) 
Indicando que dado um evento A com probabilidade de ocorrência P(A). A
quantidade de informação que ele carrega é inversamente proporcional à sua
probabilidade:
P(A)=1 (evento sempre ocorre) i(A)=0
P(A)=0 (evento nunca ocorre) i(A)=infinito
Dado 2 eventos independentes A e B: P(A,B)=P(A).P(B)


1
   logb ( P( A) P( B))
i ( AB)  logb 
 P( A) P( B) 
i ( AB)   logb P( A)  logb P( B)
i ( AB)  i ( A)  i ( B)
TE073 – Processamento Digital de Sinais II
22
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
A unidade de informação depende da base do log:
base 2  bits
base e  nats
base 10  hartleys
Ex.1: Lançamento de uma moeda: P (C )  P ( K ) 
Logo: i(C)  i( K )   log2 ( 12 )  1bit
1
2
1
7
Ex.2: Lançamento de uma moeda viciada: P(C )  P( K ) 
8
8
Maior informação
i (C )   log 2 ( 18 )  3 bits
Logo:
i ( K )   log 2 ( 78 )  0.193 bits
TE073 – Processamento Digital de Sinais II
23
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Considere um conjunto de eventos independentes Ai que são
Resultados de um experimento S
S A

i
A média da quantidade de informação associada com este
experimento aleatório é dado por:
H   P( Ai ).i( Ai )   P( Ai ).logb P( Ai )
H é chamada de Entropia associada ao experimento.
Shannon demonstrou que se o experimento é uma fonte que gera como saídas
símbolos Ai a partir de um conjunto A, então a entropia é uma medida da média
do número de símbolos binários necessários para codificar a saída desta fonte.
TE073 – Processamento Digital de Sinais II
24
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Shannon mostrou, ainda, que o melhor que um sistema de
compressão sem perdas pode fazer é codificar a saída de uma
fonte com o número de bits médio igual a entropia da fonte.
O conjunto de símbolos A é chamado alfabeto da fonte e os
símbolos são chamados letras.
TE073 – Processamento Digital de Sinais II
25
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Para uma fonte S com alfabeto A={1,2,...,m} que gera uma
sequência {X1,X2,...} a entropia é dado por:
1
H ( S )  lim Gn
n  n
Onde:
i1 m i2 m
in  m
i1 1 i2 1
in 1
Gn    ... P X1  i1 , X 2  i2 ,...X n  in . logb P X1  i1 , X 2  i2 ,...X n  in 
e {X1,X2,...,Xn} é uma sequência de tamanho n gerada pela fonte.
Se cada elemento for independente e identicamente distribuído
(iid), prova-se:
i1  m
Gn  n  P X1  i1 . logb P X1  i1 
i1 1
TE073 – Processamento Digital de Sinais II
26
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Logo a expressão para a entropia da fonte torna-se:
H (s)   P( X1 ).logb P( X1 )
Entropia de primeira-ordem
TE073 – Processamento Digital de Sinais II
27
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.: Estimando a entropia
Considere a sequência: 1 2 3 2 3 4 5 4 5 6 7 8 9 8 9 10
Assumindo que a frequência de ocorrência de cada número é
refletido pelo número que o mesmo aparece na sequência, podemos
estimar a probabilidade de cada símbolo como:
P (1)  P (6)  P (7)  P (10) 
1
16
P (2)  P (3)  P (4)  P (5)  P (8)  P (9) 
2
16
Assumindo que a sequência é iid, a entropia da sequência é a
dada pela entropia de primeira-ordem:
10
H   P(i).log2 P(i)  3.25bits / sím bolo
i 1
TE073 – Processamento Digital de Sinais II
28
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Entretanto, supondo que exista uma correlação entre uma amostra e
a anterior, pode-se remover esta correlação fazendo a
diferença entre a atual e a anterior obtendo o sinal residual:
1 1 1 –1 1 1 1 –1 1 1 1 1 1 –1 1 1
Esta sequência tem apenas 2 símbolos com probabilidades:
13
3
P (1) 
P (1) 
16
16
Resultando em uma entropia:
13
13 3
3
H   . log 2  . log 2
 0.69621 bits / simbolo
16
16 16
16
Obviamente o receptor deve conhecer o modelo utilizado.
TE073 – Processamento Digital de Sinais II
29
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Um modelo pode ser:
-Estático: quando não varia com n
-Adaptativo: quando variar com n
Logo: conhecendo alguma coisa sobre a estrutura dos dados
pode ajudar a “reduzir a entropia”.
Na verdade a Entropia não é alterada, pois ela é uma medida da
quantidade de informação gerada pela fonte, que não é conhecível.
O que se reduz é a nossa estimativa da entropia, uma vez que
qualquer pista que se tenha sobre a estrutura dos dados nos ajuda
a estimar a real entropia da fonte. ninfinito
TE073 – Processamento Digital de Sinais II
30
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.2: Considere a sequência:
12123333123333123312
Qual a estrutura?
P(1)  P(2) 
1
4
P(3) 
1
Resultando em 1.5 bits/símbolo de entropia
2
Como temos 20 símbolos, necessitamos de 30 bits p/ representa-la.
Se considerarmos blocos de 2 teremos apenas 2 blocos:
1
1
P(1 2) 
P(3 3) 
Resultando em uma entropia de 1 bit/símbolo
2
2
Como temos 10 símbolos, logo necessitamos 10 bits p/ representa-la.
TE073 – Processamento Digital de Sinais II
31
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
A teoria diz que podemos sempre extrair a estrutura dos
dados considerando blocos de tamanho cada vez maiores.
Na prática há limitações.
Na prática, podemos tentar superar estas limitações
obtendo um modelo preciso para os dados e codificar
a fonte com respeito a este modelo.
TE073 – Processamento Digital de Sinais II
32
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
2.3. Modelos
Quanto mais o modelo se aproxima do real modelo para
a fonte dos dados, melhor será a codificação.
•Modelos Físicos:
•Baseados em características físicas da fonte.
•Difíceis de serem extraídos
•Ex.: Modelo do trato vocal
•Modelos Probabilísticos:
•Baseados na observação das características estatísticas dos dados
•Pode ser complexo se fontes forem não independentes e formas de
correlacionar as amostras forem necessárias
TE073 – Processamento Digital de Sinais II
33
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
• Modelo de Markov
•Andrei Andrevich Markov (1856-1922)
•Tipo específico de processo de Markov:
Cadeia de Markov a tempo discreto
Seja {xn} uma sequência de observações.
Esta sequência é dita seguir o modelo de Markov de k-ésima ordem, se:
P( xn | xn1,...x nk )  P( xn | xn1,...x nk ,....)
Isto é, o conhecimento das últimos k símbolos é equivalente ao conhecimento
de todo o passado do processo.
Os valores tirados do conjunto {xn-1,...,xn-k} são os estados do processo
Se o alfabeto tem tamanho l, então teremos lk estados.
TE073 – Processamento Digital de Sinais II
34
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
O modelo mais popularmente usado é o Modelo de Markov
de primeira ordem, isto é:
P( xn | xn1 )  P( xn | xn1, xn2 , xn3...)
O modelo diz que a amostra atual depende de alguma forma
apenas da amostra anterior, sem especificar essa dependência.
TE073 – Processamento Digital de Sinais II
35
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.: Codificação de imagem binária (preto e branco) (1 bit/pixel)
Sabemos que a ocorrência de um pixel branco depende, em algum grau, se o
pixel atual é branco ou preto.
Então podemos modelar o processo como uma cadeia de Markov Discreta,
Definindo:
2 estados Sw e Sb para designar que o pixel atual é branco ou preto.
Probabilidades de transição de estados: P(w|b) P(b|w)
Probabilidade de cada estado: P(Sb) e P(Sw)
P(b|w)
Sw
P(w|w)
Sb
P(w|b)
P(b|b)
TE073 – Processamento Digital de Sinais II
36
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
A entropia de um processo de estados finitos é dada pela
média da entropia de cada estado:
M
H   P( Si ).H ( Si )
i 1
TE073 – Processamento Digital de Sinais II
37
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
No exemplo da imagem binária:
H (Sw )  P(b | w).log2 P(b | w)  P(w | w).log2 P(w | w)
Onde: P(w | w)  1  P(b | w)
Analogamente:
H (Sb )  P(w | b).log2 P(w | b)  P(b | b).log2 P(b | b)
Onde:
P(b | b)  1  P(w | b)
TE073 – Processamento Digital de Sinais II
38
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Numericamente, dados:
P( S w ) 
30
31
P( Sb ) 
1
31
P(w | w)  0.99 P(b | w)  0.01 P(b | b)  0.7 P(w | b)  0.3
Calculo da Entropia usando o modelo Probabilístico:
H 
30
30 1
1
. log 2
 . log 2
 0.20559 bits / simbolo
31
31 31
31
Calculo da Entropia usando o modelo de Markov:
H (Sb )  0.3 log2 0.3  0.7 log2 0.7  0.88129
H (S w )  0.99log2 0.99  0.01log2 0.01  0.08079
Logo:
30
1
H  0.08079  0.88129  0.10661 bits / símbolo
31
31
Logo modelo de Markov modelou melhor a entropia da fonte
TE073 – Processamento Digital de Sinais II
39
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
2.3.4. Modelo de fonte composta
Em muitas aplicações é difícil usar um único modelo para
descrever a fonte.
Pode-se usar então a composição de vários modelos de fontes de
modo a representar uma fonte mais complexa
Fonte 1
Fonte 2
Fonte n
TE073 – Processamento Digital de Sinais II
40
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
2.4. Codificação
Alocação de um código binário a um símbolo de um alfabeto.
Idéia do código Morse, alocar menores códigos para símbolos
mais frequentes, de modo a diminuir a taxa.
Problema: Unicidade da decodificação
TE073 – Processamento Digital de Sinais II
41
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ex.:
Símbolo
Probabilidade Código 1 Código 2 Código 3 Código 4
a1
0.5
0
0
0
0
a2
0.25
0
1
10
01
a3
0.125
1
00
110
011
a4
0.125
10
11
111
0111
1.125
1.25
1.75
1.875
Comprimento Médio(l)
4
l   P(ai ).n(ai )
i 1
TE073 – Processamento Digital de Sinais II
42
Codificação de Huffman
43
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificação Huffman
O processo de Huffman é baseado em 2
observações:


Símbolos que ocorrem mais freqüentemente terão
um código menor que os símbolos que ocorrem
menos freqüentemente.
Os dois símbolos que ocorrem com menor freqüência
terão o mesmo tamanho.
TE073 – Processamento Digital de Sinais II
44
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificação Huffman com Probabilidade da Fonte
Conhecida
Exemplo 3.2.1: Dado um alfabeto A com as seguintes letras {a1, a2, a3,
a4, a5} com a distribuição de probabilidade mostrada na tabela abaixo:
Letra
Probabilidade
Código
a2
0.4
0.2
0.2
c(a2)
c(a1)
c(a3)
0.1
0.1
c(a4)
c(a5)
a1
a3
a4
a5
Entropia: 2.122 bits/símbolo
TE073 – Processamento Digital de Sinais II
45
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Huffman coder
a2 (0.4)
a2 (0.4)
a1 (0.2)
a1 (0.2)
a3 (0.2)
a3 (0.2)
a4 (0.2)
a4 (0.1)
a3(0.6)
a2 (0.4)
a3 (0.4)
a2 (0.4)
a1 (0.2)
a5 (0.1)
a2 (0.4)
a3 (0.4) 0
a2 (0.4)
a2 (0.4)
a1 (0.2)
a1 (0.2)
a3 (0.2)
a3 (0.2) 0
a4 (0.2)
a4 (0.1) 0
a5 (0.1) 1
a1 (0.2)
0
1
a3(0.6)
a2 (0.4)
1
1
TE073 – Processamento Digital de Sinais II
46
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Mínima Variância no Código de Huffman
Forma 1
Forma 2
Letra
Probabilidade
Código
Letra
Probabilidade
Código
a2
0.4
1
a2
0.4
10
a1
0.2
01
a1
0.2
00
a3
0.2
000
a3
0.2
11
a4
0.1
0010
a4
0.1
010
a5
0.1
0011
a5
0.1
011
Redundância: Diferença entre a entropia e o tamanho médio do código.
Se a redundância é zero -> as probabilidades são potência de 2!
Exemplo: Qual a melhor forma de codificação para se transmitir
10.000 símbolos/s do alfabeto em um canal de 22.000 bits/s?
TE073 – Processamento Digital de Sinais II
47
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Diagrama em Forma de Árvore - Decoder
Diagrama em forma de árvore das 2 formas de implementação.
Através dele podemos encontrar qual código representa cada
símbolo.
TE073 – Processamento Digital de Sinais II
48
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificação Huffman com Probabilidade da
Fonte desconhecida
Modo 1: Dois passos

A estatística dos dados é coletada num primeiro passo e depois
a fonte é codificada.
Modo 2: Um passo

Faller e Gallagher desenvolveram um algoritmo adaptativo para
construir o código de Huffman baseado em estatísticas de
símbolos previamente encontrados.
TE073 – Processamento Digital de Sinais II
49
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
3.8.1 - Aplicações – Compressão de Imagens sem perdas
Compressão usando codificação
Huffman sobre os valores do pixel
Imagem
bits/pixel
Tamanho
(bytes)
Razão de
Compressão
Sena
7.01
57.504
1.14
Sensin
7.49
61.430
1.07
Terra
4.94
40.534
1.62
Omaha
7.12
58.374
1.12
TE073 – Processamento Digital de Sinais II
50
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Compressão de Imagens sem perdas
(Continuação)
Imagem
bits/pixel
Tamanho
(bytes)
Razão de
Compressão
Sena
4.02
32.968
1.99
Sensin
4.70
38.541
1.70
Terra
4.13
33.880
1.93
Omaha
6.42
52.643
1.24
Imagem
bits/pixel
Tamanho
(bytes)
Razão de
Compressão
Sena
3.93
32.261
2.03
Sensin
4.63
37.896
1.73
Terra
4.82
39.504
1.66
Omaha
6.39
52.321
1.25
Compressão usando codificação
Huffman sobre a diferença nos
valores de pixel
Compressão usando codificação
Huffman
adaptativa
sobre
a
diferença nos valores de pixel
TE073 – Processamento Digital de Sinais II
51
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Aplicação: Compressão de Texto
Através da tabela ao lado podemos
Letra
Prob.
Letra
Prob.
A
0.057305
N
0.056035
ver a probabilidade de ocorrência
B
0.014876
O
0.058215
C
0.025775
P
0.021034
das letras na constituição dos EUA.
D
0.026811
Q
0.000973
E
0.112578
R
0.048819
F
0.022875
S
0.060289
G
0.009523
T
0.078085
H
0.042915
U
0.018474
I
0.053475
V
0.009882
J
0.002031
W
0.007576
K
0.001016
X
0.002264
L
0.031403
Y
0.011702
M
0.015892
Z
0.001502
Note que a probabilidade a letra E
é a maior dentre as outras.
TE073 – Processamento Digital de Sinais II
52
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Aplicação: Compressão de Áudio
3.28 - Utilizando codificação Huffman
Nome do
Arquivo
Tamanho
Original
(bytes)
Entropia
(bits)
Tamanho estimado do
arquivo compactado
(bytes)
Razão de
Compressão
Mozart
939.862
12.8
725.420
1.30
Cohn
402.442
13.8
349.300
1.15
Mir
884.020
13.7
759.540
1.16
3.29 - Utilizando codificação Huffman com diferença entre amostras
Nome do
Arquivo
Tamanho
Original
(bytes)
Entropia
(bits)
Tamanho estimado do
arquivo compactado
(bytes)
Razão de
Compressão
Mozart
939.862
9.7
569.792
1.65
Cohn
402.442
10.4
261.590
1.54
Mir
884.020
10.9
602.240
1.47
TE073 – Processamento Digital de Sinais II
53
Codificação Aritmética
54
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Por que Codificação Aritmética?
Exemplo 4.2.1: Considere uma fonte com alfabeto A={a1, a2, a3) com
P(a1)=0.95, P(a2)=0.02 e P(a3)=0.03. Encontre a entropia, o código de
huffman e o tamanho médio do código.
Letra
Probabilidade
Código
a1
0.95
1
a2
0.02
11
a3
0.03
10
H=0.335 bits/símbolo
Tamanho médio=1.05 bits/símbolo
Diferença de 0.715 bits/símbolo que é 213 % da entropia!!!
TE073 – Processamento Digital de Sinais II
55
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificação Aritmética
Idéia
Vamos ver que é mais eficiente designar uma palavra de código para
uma seqüência em particular do que ter que gerar palavra de código
para cada símbolo na seqüências.

Um único identificador ou tag é gerada para toda a seqüência a ser
codificada. Esta tag corresponde a uma fração binária, que torna-se um
código binário para a seqüência.

Um único código aritmético pode ser gerado para uma seqüência de
tamanho m sem a necessidade de gerar palavras de código para todas
as seqüências de tamanho m.

TE073 – Processamento Digital de Sinais II
56
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificando uma seqüência

Para distinguir uma seqüência de símbolos, é necessário criar uma tag com
um único identificador. Uma tag para representar uma seqüência de símbolos
pode ser qualquer número no intervalo unitário de [0,1).

É necessário então uma função que mapeie seqüências neste intervalo
unitário. A função chama-se função de distribuição acumulativa (cdf) de
variáveis randômicas associadas com a fonte. Esta é a função que será
utilizada na codificação aritmética.
Exemplo: Lançamento de uma moeda: Podemos designar cara=1 e coroa=0,
como também podemos designar cara=2367.5 e coroa=-190.2).
TE073 – Processamento Digital de Sinais II
57
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Formulação Matemática
Precisamos mapear os símbolos da fonte ou letras para números.
Por conveniência, iremos usar o mapeamento:
X (ai )  i ai  A
Onde A={a1, a2,..., am} é o alfabeto para uma fonte discreta e X é a
variável randômica. Este mapeamento significa que dada um modelo de
probabilidade P para a fonte, nós temos uma função densidade de
probabilidade para a variável randômica
P( X  i)  P(ai )
e a função de densidade acumulativa pode ser definida como:
i
Fx (i)   P( X  k )
k 1
Note que para cada símbolo ai nós teremos um distinto
valor de Fx(i).
TE073 – Processamento Digital de Sinais II
58
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Gerando uma Tag
Exemplo 4.3.1: Considere um alfabeto de 3 letras A={a1, a2, a3} com
P(a1)=0.7, P(a2)=0.1 e P(a3)=0.2. Usando a função de densidade acumulativa
obtemos Fx(1)=0.7, Fx(2)=0.8 e Fx(3)=1. Isto particiona o intervalo unitário
como mostrado na figura abaixo:
TE073 – Processamento Digital de Sinais II
59
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Procedimento Matemático para Geração
de uma Tag
Para
entendermos
como
a
geração
de
uma
tag
funciona
matematicamente, começaremos com uma seqüência de comprimento
unitário. Suponha uma alfabeto A= {a1, a2, a3}. Podemos mapear os
_
símbolos {ai} para números reais {i}. Definimos Tx (ai )
_
como:
i 1
_
1
1
Tx (ai )   P( X  k )  P( X  i) Portanto: Tx (ai )  Fx (i  1)  P( X  i )
2
2
k 1
_
Para cada valor de ai,
Tx (ai )
tem um único valor. Esse valor pode ser
usado como a tag para ai.
TE073 – Processamento Digital de Sinais II
60
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Procedimento Matemático para Geração
de uma Tag (continuação)
Exemplo 4.3.2: Considere o experimento de jogar um dado. O resultado
pode ser mapeado nos números {1, 2, ..., 6}. Para um dado não viciado:
P( X  k ) 
1
6
para k=1,2,...,6
Então, por exemplo, podemos encontrar a tag para X=2 como sendo:
_
1
1 1
Tx(2)  P( X  1)  P( X  2)    0.25
2
6 12
E para X=5 como sendo:
_
4
1
Tx(5)   P( X  1)  P( X  5)  0.75
2
k 1
As tags para os outros valores são:
Resultado
Tag
1
0.0833
3
0.4166
4
0.5833
6
0.9166
TE073 – Processamento Digital de Sinais II
61
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Procedimento Matemático para Geração
de uma Tag (continuação)
Vamos ver agora o procedimento para a geração de uma tag de uma seqüência
de comprimento inteiro qualquer. Para uma particular seqüência xi temos:
_
( m)
x
T
1
( xi )   P( y)  P( xi )
2
y  xi
[4.4]
Onde y<x significa que y procede x na ordem, e o sobrescrito significa o
tamanho da seqüência.
TE073 – Processamento Digital de Sinais II
62
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Procedimento Matemático para Geração
de uma Tag (continuação)
Exemplo 4.3.3: Uma derivação do ex. 4.3.2, agora a seqüência consiste
de 2 jogadas dos dados. O resultado (em ordem) pode ser 11 12 13 ...
66. Utilizando a eq. 4.4, a tag para a seqüência pode ser:
_
1
Tx(13)  P( X  11)  P( X  12)  P( X  13)
2
1 / 36  1 / 36  1 / 2(1 / 36)
 5 / 72
TE073 – Processamento Digital de Sinais II
63
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Comparação entre a
Codificação Huffman e Aritmética

Codificação Aritmética é mais complicada que a Huffman porém permite que
sejam codificados seqüências de símbolos.

Quão bem um tipo trabalha melhor que o outro depende. Para a codificação
aritmética, quanto maior for a sequência, mais o código se aproxima da entropia.
Porém devemos escolher o tamanho da seqüência de forma que torne-se viável.
A tamanho médio da codificação aritmética e Huffman é dado pelas equações
abaixo: onde m é o tamanho da seqüência.
2
m
1
H ( X )  lH  H ( X ) 
m
H ( X )  lA  H ( X ) 
No entanto: Sequência de 20 símbolos de
um alfabeto de 16 símbolos requer tabela de
Huffman de tamanho 1620!
TE073 – Processamento Digital de Sinais II
64
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Comparação entre a
Codificação Huffman e Aritmética
Veja a seguinte equação:
Tmáx  H  pmáx  0.086
- A eq. acima diz qual é a taxa máxima que se pode obter com a
codificação Huffman. Se o alfabeto for grande, a probabilidade máxima é
baixa e portanto o código de Huffman se comporta melhor que o código
aritmético.
- Uma grande vantagem da codificação aritmética é a facilidade de se
implementar sistemas com múltiplos codificadores aritméticos.
– É muito mais simples adaptar o código aritmético para mudar a
estatística. Somente o que precisamos é estimar a probabilidade do
alfabeto de entrada. Não há necessidade de preservar a árvore como na
codificação Huffman.
TE073 – Processamento Digital de Sinais II
65
Codificação baseada em dicionário
66
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Técnicas Baseadas em Dicionários


Até agora estudamos técnicas que assumem que a fonte gera
seqüências de símbolos independentes
Porém a maioria das fontes possuem alto grau de correlação
entre os símbolos adjacentes. Portanto é comum usar técnicas
de descorrelação em um passo anterior (ex. DPCM).

A idéia aqui é incorporar a estrutura dos dados ao codificador.

Duas metodologias:

Estática

Adaptativa (dinâmica)

Muito utilizados em fontes que repetem um pequeno número de
sequências padrões muito frequentemente (ex. Texto, C).

Exemplos de utilização: UNIX compress , modem V.42, GIF
TE073 – Processamento Digital de Sinais II
67
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Introdução

Em muitas aplicações temos padrões que se repetem
muito:
“Dar fundamentos teóricos e práticos de forma profundamente,
completamente e razoavelmente condescendente com quem
mente.”
 Ou que são muito improváveis:
“Supercalifragilisticexpialidocious é improvável (2940) porém

VictorBenso é muito mais improvável (3).

Dividido em duas classes:


Quando o padrão existe no dicionário é codificado com uma referência ao
dicionário. (padrões que ocorrem muito)
Quando não existe no dicionário é codificado com uma forma menos
eficiente. (padrões que ocorrem pouco)
TE073 – Processamento Digital de Sinais II
68
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica

Exemplo:
Texto de 4 caracteres (26 letras + ; : , . ? !)




32 caracteres (5 bits)
32^4 = 1.048.576 combinações diferentes
Selecionado as 256 sequências mais comuns (8 bits)
O primeiro bit indica se a sequência é conhecida.




P- probabilidade de encontrar sequência no dicionário




4x5=20 bits por sequência sem codificação
9 bits caso a sequência seja conhecida (2,25 bits)
21 bits caso não seja conhecida (5,25 bits)
R=9.p + 21.(1 - p)= 21 - 12p (taxa de bits média)
Será eficiente quando R<20 logo : P0,083333
Não parece tão grande. Porém: Caso a probabilidade seja
igualmente distribuída a probabilidade de 1 padrão no
dicionário é: P<0,00025
Conhecer a fonte (estático) ou criar um dicionário
específico (dinâmico)
TE073 – Processamento Digital de Sinais II
69
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Dicionário estático


Fonte previamente conhecida
Aplicações específicas:

Armazenar receitas:







sal
açúcar
batata
xícara
colher de chá
Mexa constantemente em banho maria até dissolver bem.
Se usar este esquema para codificação de um livro
de software não ajudaria muito, podendo até causar
expansão no volume de dados.
TE073 – Processamento Digital de Sinais II
70
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Código de diagrama – Dic. Estático



Alfabeto é formado por letras e completado por sequências
freqüentes.
Ex: para ASCII caracteres poderíamos usar os 95 primeiros
números para letras imprimíveis e os outros 161 para
sequências, completando 256
Ex:

Fonte A = {a,b,c,d,r}





000
001
010
011
–
–
–
–
a
b
c
d
100
101
110
111
-r
- ab
- ac
– ad
abracadabra : 101 100 110 111 010 101 100 000

Original: 3 bits/símbolo codificado:2,18 bits/símbolo (sem dicionário!)
TE073 – Processamento Digital de Sinais II
71
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Dicionário Adaptativo

Teoria baseada em dois artigos:


Jacob Ziv (LZ77 ou familia LZ1)
Abraham Lempel (LZ78 ou família LZ2)
TE073 – Processamento Digital de Sinais II
72
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Dicionário Adaptativo – LZ77

Divide as amostras em duas janelas




Search buffer (amostra codificada atual)
Look-Ahead buffer (amostra a ser codificada)
Procura sequências repetidas nas amostras
Quando encontra substitui por <O,L,C> onde




O = offset
L = length
C = codeword do símbolo
Envia <0,0,C> caso o símbolo não esteja presente no
buffer.
(7,4,p)
TE073 – Processamento Digital de Sinais II
73
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Dicionário Adaptativo – LZ77



S – tamanho do buffer
W - tamanho da janela
A – tamanho do alfabeto

Numero de bits necessários
usando tamanho fixo
[log2 S ]  [log2 W ]  [log2 A]
TE073 – Processamento Digital de Sinais II
74
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Dicionário Adaptativo – LZ77

Variações do LZ77


Podemos usar tamanho de código variável
Semi-Adaptativo (2 métodos)







PKZip
Zip
LHarc
PNG
Gzip
ARJ
Adição de um bit flag para indicar quando existe o tripple
TE073 – Processamento Digital de Sinais II
75
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Aplicações

Compressão de arquivos – UNIX Compress


LZW
Tamanho do dicionário variável



Começa com 512 (9 bits)
Dobra quando é completado
Até Máximo


A partir deste momento o dicionário se torna estático
Analisa a taxa de compressão, quando cai abaixo de um
threshold o processo é reiniciado
TE073 – Processamento Digital de Sinais II
76
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Aplicações

GIF (Graphics Interchange Format)




LZW
Semelhante ao UNIX-compress
Tamanho máximo de 4096
2n Símbolos (bitmap)
Imagem
GIF
Cod. Aritmética
Cod. Aritmética
da diferença
Sena
51.085
53.431
31.847
Sensin
60.649
58.306
37.126
Earth
34.276
38.248
32.137
Omaha
61.580
56.061
51.393
TE073 – Processamento Digital de Sinais II
77
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Aplicações

MODEM – V.42 bis



As vezes a fonte não repete dados, expandindo o arquivo já
que o número de bits para o dicionário é maior que
somente para um símbolo isolado.



Não compactado
Compactado – LZW
Testes periódicos para verificar se não está expandindo
Tamanho Inicial de 512 máximo 2048
3 símbolos para controle
TE073 – Processamento Digital de Sinais II
78