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