Fundamentos de

Codificação de Sinais

1
 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

 Ex.:
3 minutos de música qualidade de CD – estéreo necessita:
3  60seg  44100 amostras
seg  2 amostra  2 canais  31.752.000 bytes  30,28 Mibytes
bytes

10 Fotos 10x15cm com resolução de 600dpi(240dpc) coloridas:

10 fotos 10cm  240 pixel
cm
 15 cm  240 pixel
cm
 3 bytes
pixel
 247,19 Mibytes

TE073 – Processamento Digital de Sinais II 3

 2 horas de vídeo tamanho VGA true color necessita:
24 pixel
bits
 640  480 quadro
pixel
 24 quadros
seg  2  60  60 seg  148,32Gibytes

Ou
24 pixel
bits
 640  480 quadro
pixel
 24 quadros
seg  168,75Mibits / seg

TE073 – Processamento Digital de Sinais II 4

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)

5
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

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

 1.1. Técnicas de Compressão
2 algoritmos: Codificador/Compressor e Decodificador/Descompressor

Xc Y
X coder decoder
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

 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

 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
 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

-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
 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

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

 Observando sua representação gráfica:
25

20

15

10

0
0 2 4 6 8 10 12 14

Nota-se que podemos modelar estes dados como: xˆn  n  8

TE073 – Processamento Digital de Sinais II 15

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

 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 14

TE073 – Processamento Digital de Sinais II 17

 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

 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
a 1
Porém, se utilizarmos a tabela:
_ 001
Necessitamos 106 bits p/ representar a b 01100
sequência, f 0100
O que gera uma taxa de 2.58 bits/símbolo n 0111
r 000
w 01101
y 0101
TE073 – Processamento Digital de Sinais II 19
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 comunicar-
se entre si. JPEG, MPEG, H.261, H.263, etc...

TE073 – Processamento Digital de Sinais II 20

 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.

[Link]. A Mathematical Theory of Communication. Bell System

Technical Journal. 27:379-423, 623-656, 1948

TE073 – Processamento Digital de Sinais II 21

  1 
Quantidade de Informação: i ( A)  log b     log b P ( A)
 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 
i ( AB)  log b     log b ( P ( A) P ( B ))
 P ( A) P ( B ) 
i ( AB)   log b P ( A)  log b P ( B )
i ( AB)  i ( A)  i ( B )
TE073 – Processamento Digital de Sinais II 22
 A unidade de informação depende da base do log:
base 2  bits
base e  nats
base 10  hartleys
1
Ex.1: Lançamento de uma moeda: P (C )  P ( K ) 
2
Logo: i (C )  i ( K )   log 2 ( 12 )  1bit

1 7
Ex.2: Lançamento de uma moeda viciada: P(C )  P( K ) 
8 8
i (C )   log 2 ( 18 )  3 bits Maior informação
Logo:
i ( K )   log 2 ( 78 )  0.193 bits

TE073 – Processamento Digital de Sinais II 23

 Considere um conjunto de eventos independentes Ai que são
Resultados de um experimento S S  Ai 
A média da quantidade de informação associada com este
experimento aleatório é dado por:

H   P ( Ai ).i ( Ai )   P ( Ai ). log b 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

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

 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
Gn     ...  P X 1  i1 , X 2  i2 ,... X n  in . log b P X 1  i1 , X 2  i2 ,... X n  in 
i1 1 i2 1 in 1

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: i m
Gn  n  P X 1  i1 . log b P X 1  i1 
1

i1 1

TE073 – Processamento Digital de Sinais II 26

Logo a expressão para a entropia da fonte torna-se:

H ( s )   P( X 1 ). log b P( X 1 ) Entropia de primeira-ordem

TE073 – Processamento Digital de Sinais II 27

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:
1
P (1)  P (6)  P (7)  P (10) 
16
2
P (2)  P (3)  P (4)  P (5)  P (8)  P (9) 
16

Assumindo que a sequência é iid, a entropia da sequência é a

dada pela entropia de primeira-ordem:
10
H   P(i ). log 2 P(i )  3.25 bits / símbolo
i 1

TE073 – Processamento Digital de Sinais II 28

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.69621bits / simbolo
16 16 16 16
Obviamente o receptor deve conhecer o modelo utilizado.

TE073 – Processamento Digital de Sinais II 29

 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

 Ex.2: Considere a sequência:
12123333123333123312
Qual a estrutura?
1 1
P (1)  P (2)  P (3)  Resultando em 1.5 bits/símbolo de entropia
4 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
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

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

 • 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

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

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 Sb

P(w|w) P(w|b) P(b|b)

TE073 – Processamento Digital de Sinais II 36

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

No exemplo da imagem binária:
H ( S w )   P(b | w). log 2 P(b | w)  P( w | w). log 2 P( w | w)

Onde: P ( w | w)  1  P (b | w)

Analogamente:
H ( S b )   P ( w | b). log 2 P ( w | b)  P (b | b). log 2 P (b | b)

Onde: P (b | b)  1  P ( w | b)

TE073 – Processamento Digital de Sinais II 38

 30 1
Numericamente, dados: P( S w )  P( Sb ) 
31 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:

30 30 1 1
H  . log 2  . log 2  0.20559 bits / simbolo
31 31 31 31
Calculo da Entropia usando o modelo de Markov:
H ( Sb )  0.3 log 2 0.3  0.7 log 2 0.7  0.88129
H ( S w )  0.99 log 2 0.99  0.01 log 2 0.01  0.08079
Logo:
30 1
H 0.08079  0.88129  0.10661bits / símbolo
31 31
Logo modelo de Markov modelou melhor a entropia da fonte
TE073 – Processamento Digital de Sinais II 39