View
107
Download
0
Category
Preview:
Citation preview
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 palavras-có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
Desigualdade de Kraft-McMillan121
0
K
k
lk
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 de um código U.D. para a codificação desta fonte é limitado por:
com igualdade se e somente se:
L
SHL
1,,1,0, Krrp klk
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ódigoa1 0a2 11a3 10
• 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!
05,1L
95,01 ap 02,02 ap
03,03 ap
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
• bits/símbolo• bits/símbolo
(ainda 72% acima da entropia!)
• extensão de ordem n = 8 fonte com 6561 símbolos!
• Huffman: precisa criar todas as palavras-código!
222,12 L
611,022 L
AHnLn
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.
• 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.
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).
• Atualizar os valores de l(k) e u(k).• Continuar até o fim da seqüência.
Exemplo: Unicidade e Eficiência do Código Aritmético
Símbolo FX XT Binário 11
log
xP
Código
1 0,5 0,25 .010 2 01 2 0,75 0,625 .101 3 101 3 0,875 0,8125 .1101 4 1101 4 1,0 0,9375 .1111 4 1111
Implementação com Inteiros
• Para a implementação com números inteiros, nas equações para a atualização dos limites dos sub-intervalos, 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,
CountTotal
nkF
k
i iX _
1
Implementação com Inteiros
Se definirmos,
As equações de atualização podem ser re-escritas como,
Onde xn é o n-ésimo símbolo a ser codificado.
k
iinkCountCum
1
_
1_
_1
_
1_1
111
111
CountTotal
xCountCumlulu
CountTotal
xCountCumlull
nnn
nn
nnn
nn
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.
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 LSBwhile (Scale3 > 0)
{enviar o complemento de bScale3 = Scale3 – 1}
}
1
_
_1
_
1_1
CountTotal
xCountCumlulu
CountTotal
xCountCumlull
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 LSBcomplementar o (novo) MSB de l e u Scale3 = Scale3 + 1 }
Algoritmo de Decodificação com Inteiros
1
_
_1
_
1_1
CountTotal
xCountCumlulu
CountTotal
xCountCumlull
Inicializar l e u.Ler os primeiros m bits do identificador t.k = 0
k ← k + 1decodificar símbolo x.
kCountCumlu
CountTotallt_
1
11while
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 LSBdeslocar 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
repitapalavra = leia_palavra (entrada);index = busca (palavra,dicionário);se index = 0 entãofaça
escreva (palavra, saída);inclua (palavra, dicionário);
fimsenão
escreva (index, saída);até fim_da_mensagem
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
Algoritmo de Lempel-Ziv
Posição no Dicionário Conteúdo Palavra-Código 1 0001 1 00001 2 0010 0 00000 3 0011 10 00010 4 0100 11 00011 5 0101 01 00101 6 0110 00 00100 7 0111 100 00110 8 1000 111 01001 9 1001 010 01010
10 1010 1000 01110 11 1011 011 01011 12 1100 001 01101 13 1101 110 01000 14 1110 101 00111 15 1111 10001 10101 16 1011 11101
Recommended