TÉCNICAS DE CODIFICAÇÃO DE SINAIS
COMPRESSÃO SEM PERDAS
Evelio M. G. Fernández - 2010
Exemplo
Símbolo
Prob
I
II
III
IV
A
1/2
00
0
0
0
B
1/4
01
11
10
01
C
1/8
10
00
110
011
D
1/8
11
01
1110 0111
Entropia de uma Fonte Binária sem Memória
Códigos Prefixos
• Nenhuma palavra código é prefixo de qualquer outra
palavra-código
• Todo código prefixo é instantâneo (o final das palavrascódigo é bem definido)
• Um código prefixo é sempre U.D. (a recíproca não é
sempre verdadeira)
• Existe um código prefixo binário se e somente se
K 1
lk
2
  1 Desigualdade de Kraft-McMillan
k 0
Códigos Prefixos
• Dado um conjunto de códigos que satisfaz a
desigualdade de Kraft-McMillan, SEMPRE será
possível encontrar um código prefixo com esses
comprimentos para as suas palavras-código. O
comprimento médio das palavras do código estará
limitado pela entropia da fonte de informação
Teorema da Codificação de Fonte
• Dada uma fonte discreta sem memória com entropia
H(S), o comprimento médio L de um código U.D.
para a codificação desta fonte é limitado por:
L  H S 
com igualdade se e somente se:
pk  r lk ,
r  0, 1, , K 1
Códigos de Huffmann Binários
1. Ordenar em uma coluna os símbolos do mais
provável ao menos provável.
2. Associar ‘0’ e ‘1’ aos dois símbolos menos
prováveis e combiná-los (soma das
probabilidades individuais).
3. Repetir 1 e 2 até a última coluna que terá apenas
dois símbolos; associa-se ‘0’ e ‘1’.
Códigos Ótimos r-ários
• Método de Huffmann: aplica-se o método com o
seguinte artifício:
• Adicionam-se ao alfabeto original símbolos
fictícios com probabilidade zero de ocorrência, até
o número de símbolos assim gerado ser
congruente a 1 mod (r – 1).
• Aplica-se o método de Huffmann agrupando-se r
símbolos de cada vez. O código gerado é um
código r-ário ótimo para o alfabeto original.
Fonte com Alfabeto Pequeno
Símbolo Código
a1
0
a2
11
a3
10
pa1   0,95
pa2   0,02
pa3   0,03
• L  1,05 bits/símbolo
• H(A) = 0,335 bits/simbolo
• Redundância = 0,715
bits/símbolo (213% da
entropia)
• São necessários duas vezes
mais bits do que o
prometido pela entropia!
Segunda Extensão da Fonte
Símb.
Prob.
Cod.
a1a1
0,9025
0
a1a2
0,0190
111
a1a3
0,0285
100
a2a1
0,0190
1101
a2a2
0,0004
110011
a2a3
0,0006
110001
a3a1
0.0285
101
a3a2
0,0006
110010
a3a3
0,0009
110000
• L2  1,222 bits/símbolo
• L2 2  0,611 bits/símbolo
(ainda 72% acima da
entropia!)
• Ln n  H A  extensão
de ordem n = 8  fonte
com 6561 símbolos!
• Huffman: precisa criar
todas as palavras-código!
Codificação Aritmética
• É mais eficiente designar uma palavra-código para
uma seqüência de tamanho m do que gerar as
palavras-código para todas as seqüências de
tamanho m.
• Um único identificador ou tag é gerado para toda
a seqüência a ser codificada. Esta tag corresponde
a uma fração binária que tornar-se-á num código
binário para a seqüência.
Codificação Aritmética
• Um conjunto possível de tags para representar
seqüências de símbolos são os números no
intervalo [0, 1).
• É necessário então uma função que mapeie
seqüências neste intervalo unitário. Utiliza-se a
função de distribuição acumulativa (cdf) das
variáveis aleatórias associadas com a fonte. Esta é
a função que será utilizada na codificação
aritmética.
Algoritmo para Decifrar o Identificador
1. Inicializar l(0) = 0 e u(0) = 1.
2. Para cada valor de k, determinar:
t* = (tag – l(k–1))/(u(k–1) – l(k–1)).
3. Determinar o valor de xk para o qual
FX(xk – 1) ≤ t* ≤ FX(xk).
4. Atualizar os valores de l(k) e u(k).
5. Continuar até o fim da seqüência.
Exemplo: Unicidade e Eficiência do Código Aritmético
Símbolo
FX
TX
1
2
3
4
0,5
0,75
0,875
1,0
0,25
0,625
0,8125
0,9375
Binário
.010
.101
.1101
.1111

1 
log
1


P x  

2
3
4
4
Código
01
101
1101
1111
Implementação com Inteiros
• Para a implementação com números inteiros, nas
equações para a atualização dos limites dos subintervalos, será necessário substituir FX(x).
• Seja nj o número de vezes que o símbolo j ocorre
em uma seqüência de tamanho Total_Count.
Então, FX(k) pode ser estimado por,
FX k  

k
i 1
ni
Total _ Count
Implementação com Inteiros
Se definirmos,
k
Cum _ Countk    ni
i 1
As equações de atualização podem ser re-escritas como,




 n 1
n 1

u

l
 1  Cum _ Countxn  1
n 
 n 1
l l


Total
_
Count


 n 1
 n 1

u

l
 1  Cum _ Countxn 
n 
 n 1
u l

 1
Total _ Count


Onde xn é o n-ésimo símbolo a ser codificado.
Implementação com Inteiros
Devemos mapear o intervalo da tag de forma que os limites inferior e
superior permaneçam na parte superior e inferior do intervalo.
Exemplo: Suponha m = 6, u(n) = 54 e l(n) = 33. A representação
binária é: u(n) = 110110 e l(n) = 100001. Note que ambos tem o MSB
igual a ‘1’. Seguindo o procedimento de shiftingt, deslocar o MSB (e
transmiti-lo ou armazená-lo) e adicionar ‘1’ no código binário de u(n)
e ‘0’ no código binário de l(n), obtendo-se u(n) = 101101 (ou 45) e l(n)
= 000010 (ou 2). Isto é equivalente a executar o mapeamento E2. O
mapeamento E1 pode ser feito de forma similar.
Para o procedimento E3 monitoramos o segundo MSB e se para u(n)
for ‘0’ e para l(n) for ‘1’ então (1) complementar o segundo MSB, (2)
deslocar para a esquerda e (3) incluir um ‘1’ em u(n) e um ‘0’ em
l(n). O número de mapeamentos E3 realizados será armazenado
(Scale3).
Algoritmo de Codificação com Inteiros
Inicializar l e u.
 u  l  1 Cum _ Count x  1 
l l

Total _ Count


 u  l  1 Cum _ Count x  
u l
 1
Total
_
Count


while (MSB de u e l sejam ambos iguais a b ou condição E3 mantida)
if (MSB de u e l são ambos iguais a b)
{
deslocar l à esquerda de um bit e incluir ‘0’ no LSB
deslocar u à esquerda de um bit e incluir ‘1’ no LSB
while (Scale3 > 0)
{
enviar o complemento de b
Scale3 = Scale3 – 1
}
}
Algoritmo de Codificação com Inteiros
if (condição E3 mantida)
{
deslocar l à esquerda de um bit e incluir ‘0’ no LSB
deslocar u à esquerda de um bit e incluir ‘1’ no LSB
complementar o (novo) MSB de l e u
Scale3 = Scale3 + 1
}
Algoritmo de Decodificação com Inteiros
Inicializar l e u.
Ler os primeiros m bits do identificador t.
k=0
  t  l  1 TotalCount 1



while  

Cum
_
Count
k


u  l 1



k←k+1
decodificar símbolo x.
 u  l  1 Cum _ Count x  1 
l l

Total _ Count


 u  l  1 Cum _ Count x  
u l
 1
Total
_
Count


Algoritmo de Decodificação com Inteiros
while (MSB de u e l sejam ambos iguais a b ou condição E3 mantida)
if (MSB de u e l são ambos iguais a b)
{
deslocar l à esquerda de um bit e incluir ‘0’ no LSB
deslocar u à esquerda de um bit e incluir ‘1’ no LSB
deslocar t à esquerda de um bit e incluir o próximo bit recebido no LSB
}
if (condição E3 mantida)
{
deslocar l à esquerda de um bit e incluir ‘0’ no LSB
deslocar u à esquerda de um bit e incluir ‘1’ no LSB
deslocar t à esquerda de um bit e incluir o próximo bit recebido no LSB
complementar o (novo) MSB de l, u e t
}
Códigos Baseados em Dicionários
• Seqüências de comprimento variável de símbolos
da fonte são codificadas em palavras-código de
comprimento fixo, obtidas de um dicionário.
• Utilizam técnicas adaptativas que permitem uma
utilização dinâmica do dicionário.
• São projetados independentemente da fonte de
informação  classe de algoritmos universais de
codificação de fonte.
Códigos Baseados em Dicionários
repita
palavra = leia_palavra (entrada);
index = busca (palavra,dicionário);
se index = 0 então
faça
escreva (palavra, saída);
inclua (palavra, dicionário);
fim
senão
escreva (index, saída);
até fim_da_mensagem
Algoritmo de Lempel-Ziv
Seqüência Binária:
10101101001001110101000011001110101100011011
Frases:
1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110,
101, 100001, 1011
Algoritmo de Lempel-Ziv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Posição no Dicionário
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Conteúdo
1
0
10
11
01
00
100
111
010
1000
011
001
110
101
10001
1011
Palavra-Código
00001
00000
00010
00011
00101
00100
00110
01001
01010
01110
01011
01101
01000
00111
10101
11101