codificacao de fonte

Prévia do material em texto

FONTES DISCRETAS DE INFORMAÇÃO 
 
Podemos caracterizar fontes discretas de informação por um conjunto finito 
de “M” símbolos, { }110 ,,, −Mxxx K , denominados de alfabeto da fonte. A probabilidade 
da fonte emitir cada símbolo é dada por { }110 ,,, −Mppp K . Os símbolos das fontes 
discretas não binárias são em geral representados por palavras binárias. A 
caracterização completa de uma fonte discreta de informação é dada pelo alfabeto 
da fonte, probabilidade de emissão de símbolos e a taxa de emissão de símbolos. 
As Figuras 1, 2 e 3 apresentam alguns exemplos de fontes discretas. 
 
Fonte de
Informação
Binária
..... 010011101001110
Rb bits/s
(Taxa de Transmissão)
P(0)=Prob. de Emitir bit 0
P(1)=Prob. de Emitir bit 1No. de Símbolos=2
 
Figura 1 – Fonte discreta binária 
 
Fonte de
Informação
q-ária
{0,1,2,3}
..... 03211003223103120
Rs símbolos/s
(Taxa de Transmissão)
P(2)=Prob. de Emitir Símbolo 2
P(3)=Prob. de Emitir Símbolo 3
No. de Símbolos=4
P(1)=Prob. de Emitir Símbolo 1
P(0)=Prob. de Emitir Símbolo 0
 
Figura 2 – Fonte discreta q-ária 
 
Fonte de
Informação
q-ária
{A,B,C,D,E}
..... AEDDCBBAEDB
Rs símbolos/s
(Taxa de Transmissão)
P(C)=Prob. de Emitir Símbolo C
P(D)=Prob. de Emitir Símbolo D
No. de Símbolos=5
P(B)=Prob. de Emitir Símbolo B
P(A)=Prob. de Emitir Símbolo A
P(E)=Prob. de Emitir Símbolo E
 
Figura 3 – Fonte discreta q-ária 
 
 
Os símbolos das fontes de informação discretas não binárias (q-árias) são em geral 
mapeados (codificados) para palavras binárias com o objetivo de armazenagem ou 
transmissão dos dados. Este processo é ilustrado na Figura 4. 
 
Fonte de
Informação
q-ária
{A,B,C,D}
..... DABBCAD
Rs símbolos/s
(Taxa de Transmissão)
Representação
Binária dos
Símbolos
da Fonte
Rb bits/s
..... 11 00 01 01 10 00 11
Tabela de Codificação
A - 00
B - 01
C - 10
D - 11
 
Figura 4 – Processo de codificação binária dos símbolos da fonte 
 
A fonte de informação possui uma taxa de emissão de símbolos, SR . Após o 
mapeamento binário teremos uma taxa média em bits/s, bR . Esta é uma taxa média 
de bits porque a fonte é um mecanismo probabilístico. Para calcularmos a taxa 
média em bits/s devemos calcular qual o tamanho médio das palavras binárias que 
estamos utilizando para representar cada símbolo da fonte. O tamanho médio das 
palavras binárias usadas para representar cada símbolo da fonte é dado por: 
 
 
 
 
 
 
 
 
 
 
 
A taxa média de transmissão em bits/s após a codificação binária é dada por: 
 
 
 
A taxa média em bits/s depende de L , ou seja, do tipo de código que estamos 
utilizando para fazer a representação binária dos símbolos da fonte. Se utilizarmos 
um código apropriado, podemos obter uma taxa média resultante menor, 
significando que estamos fazendo compressão (codificação fonte). 
 
 
 
lo bits/símbo ∑
−
=
⋅=
1
0
M
i
ii plL 
ii xl símbolo o representa que binária palavra da tamanho=
ii xp símbolo do ocorrência de adeprobabilid=
 
bits/s sb RLR ⋅= 
QUAL A REPRESENTAÇÃO BINÁRIA DE UMA FONTE DISCRETA QUE 
MINIMIZA A TAXA MÉDIA DE TRANSMISSÃO EM BITS/S ? 
CODIFICAÇÃO FONTE 
CODIFICAÇÃO PARA REDUÇÃO DE REDUNDÂNCIA 
 
 
 
- A codificação fonte é utilizada para se eliminar (reduzir) a redundância natural 
presente na fonte de informação. A codificação para se reduzir a redundância da 
fonte é feita pela seleção eficiente de uma representação binária. 
 
 
 
Exemplo – Considere uma fonte discreta que emite 4 possíveis símbolos a uma 
 taxa de 200 símbolos/s 
 
SÍMBOLO DA FONTE PROBABILIDADE DE 
OCORRÊNCIA 
REPRESENTAÇÃO 
BINÁRIA USUAL 
REPRESENTAÇÃO BINÁRIA 
ALTERNATIVA 
A 50% 00 0 
B 25% 01 10 
C 15% 10 110 
D 10% 11 111 
 
 
 
 
 
 
 
- A substituição é usualmente temporária e é feita para se obter uma economia na 
armazenagem ou transmissão dos símbolos da fonte 
 
 
 
 
 
 
 
 
FAZER CODIFICAÇÃO FONTE IMPLICA NA SUBSTITUIÇÃO DE UMA REPRESENTAÇÃO 
BINÁRIA DOS SÍMBOLOS DA FONTE POR OUTRA REPRESENTAÇÃO ALTERNATIVA 
lo bits/símbo 2=L bits/s 400=bR
lobits/símbo 75,1=L bits/s 350=bR
COMO OBTER O CÓDIGO MAIS EFICIENTE PARA UMA DADA 
FONTE DE INFORMAÇÃO ? 
CÓDIGO MAIS 
 EFICIENTE 
CODIFICAÇÃO FONTE 
CODIFICAÇÃO PARA REDUÇÃO DE REDUNDÂNCIA 
 
 
Exemplo – Considere a seguinte fonte de informação discreta: 
SÍMBOLO DA 
FONTE 
PROBABILIDADE DE OCORRÊNCIA 
A 0,73 
B 0,25 
C 0,02 
 
Analise a utilização dos seguintes códigos para a representação binária da fonte 
discreta: 
SÍMBOLO DA 
FONTE CÓDIGO 1 CÓDIGO 2 CÓDIGO 3 CÓDIGO 4 CÓDIGO 5 CÓDIGO 6 
A 00 00 0 1 1 1 
B 00 01 1 10 00 01 
C 11 10 11 100 01 11 
 
Códigos Unicamente Decodificáveis: 
Os códigos devem ser unicamente decodificáveis para permitir o mapeamento 
inverso para o símbolo original do alfabeto no receptor. Os códigos 1, 3, e 6 não são 
unicamente decodificáveis portanto não podem ser utilizados. 
 
 
 
 
Códigos Livres de Prefixo: 
Uma condição suficiente (mas não necessária) para que um código seja unicamente 
decodificável é que nenhuma palavra código seja prefixo de outra palavra código. O 
código 4 não é um código livre de prefixo e é unicamente decodificável. Os códigos 
livre de prefixo possuem decodificação instantânea. 
 
 
 
 
TENTANDO DECODIFICAR A SEQÜÊNCIA 1 0 1 1 1 CODIFICADA COM O CÓDIGO 3: 
 
OPÇÃO 1: B A B B B OPÇÃO 2: B A B C OPÇÃO 3: B A C B 
 
NA TRANSMISSÃO DO SÍMBOLO B COM A REPRESENTAÇÃO BINÁRIA 1 0 DO CÓDIGO 4, O 
RECEPTOR NÃO PODE DETERMINAR SE É A PALAVRA INTEIRA DO SÍMBOLO B OU A 
PALAVRA PARCIAL DO SÍMBOLO C. É NECESSÁRIO ESPERAR OUTROS BITS PARA FAZER A 
DECODIFICAÇÃO 
CODIFICAÇÃO FONTE 
MEDIDA DE INFORMAÇÃO E ENTROPIA 
 
Para cada símbolo da fonte de informação podemos associar uma medida de 
informação que depende da probabilidade de ocorrência do símbolo. A medida de 
informação está associada ao princípio da incerteza (surpresa). Quando a 
probabilidade de um símbolo tende a um, o seu conteúdo de informação tende a 
zero. A medida de informação de cada símbolo é dada por: 
 
 
 
 
A medida de informação representa o número de bits necessário para representar o 
símbolo da fonte. A informação média da fonte, denominada de entropia, é dada por 
 
 
 
 
 
A unidade da entropia é bits/símbolo e representa o número médio de bits 
necessário para representar cada símbolo da fonte de informação. Dada a taxa de 
emissão da fonte em símbolos por segundo, podemos calcular a taxa de 
transmissão média teórica em bits por segundo após a codificação da fonte: 
 
 
 
 
A taxa de transmissão média teórica utiliza H ao invés de L para calcular bR , pois 
pressupõe que é possível construir um código prático onde HL = . 
 
 
 
 
 
10 lo,bits/símbo 
1
log2 −≤≤





= Mi
i
i
p
I
 
lobits/símbo ∑∑
−
=
−
=






⋅=⋅=
1
0
2
1
0
1
log
M
i i
i
M
i
ii
p
pIpH
 
símbolos/s em fonte da taxa==
s
s
T
R
1
bits/ss) (símbolos/olos)(bits/símb =⋅=
s
b
T
HR
1
EXEMPLO – Uma fonte digital emite 200 símbolos/s. Os possíveis símbolos com a 
respectiva probabilidade de ocorrência são mostrados na tabela abaixo: 
 
SÍMBOLO DA FONTE PROBABILIDADE DE OCORRÊNCIA 
A 0,2 
B 0,2 
C 0,3 
D 0,3 
 
A medida de informação de cada símbolo é: 
 
 
 
 
A entropia da fonte é: 
 
 
 
 
Se pudermos encontrar um código que atinja a entropia da fonte para codificar os 
símbolos, a taxa média em bits por segundo após a codificação será: 
 
 
 
 
Fonte de
Informação
{A,B,C,D}
..... DABBCAD
R=200 símbolos/s
Codificação
Binária dos
Símbolos da
Fonte
R=394 bits/s
(Taxa Média)
 
 
bits 2,32=





==
2,0
1
log2BA II bits ,731
3,0
1
log2 =





== DC II 
lobits/símbo 97,1
1
0
=⋅= ∑
−
=
M
i
ii IpH 
bits/s 39420097,1 =⋅=bR 
CODIFICAÇÃO FONTE 
EFICIÊNCIA DOS CÓDIGOS 
 
Dado um código prático específico, podemos calcular o comprimento médio das 
palavras código, 
 
 
 
onde il é o tamanho da palavra bináriausada para codificar o símbolo ix . 
 
A eficiência do código é dada pela relação da entropia com o comprimento médio do 
código utilizado: 
 
 
 
Se estamos utilizando um código com uma dado LLLL , A taxa de transmissão média 
em bits/s será dada por: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
lobits/símbo ∑
−
=
⋅=
1
0
M
i
ii lpL 
1≤=
L
H
η 
bits/ss) (símbolos/olos)(bits/símb =⋅=
s
b
T
LR
1
PRINCÍPIO DA CODIFICAÇÃO FONTE: 
 
“PARA SÍMBOLOS QUE OCORREM COM MAIOR PROBABILIDADE DEVEMOS ASSOCIAR 
PALAVRAS CÓDIGO MAIS CURTAS DO QUE PARA SÍMBOLOS QUE OCORREM COM 
MENOR PROBABILIDADE” 
EXERCÍCIOS DE CODIFICAÇÃO FONTE 
 
 
Exercício 1 – Uma fonte de informação emite 2000 símbolos/s, selecionados de um alfabeto 
de M=4 possíveis símbolos. As probabilidades de ocorrência de cada símbolo são 
mostradas na tabela abaixo: 
 
Símbolo da Fonte Probabilidade de Ocorrência 
A 1/2 
B 1/4 
C 1/8 
D 1/8 
 
a) Calcule a entropia da fonte 
b) Calcule a taxa média de transmissão em bits/s após a codificação 
 
 
Exercício 2 – Para a fonte de informação do exercício anterior, analise a utilização dos 
códigos propostos na tabela abaixo. Determine quais códigos podem ser utilizados 
(justifique) e sua eficiência, LH=η . 
 
Símbolo Código 1 Código 2 Código 3 Código 4 
A 00 0 0 0 
B 01 1 01 10 
C 10 10 011 110 
D 11 11 0111 111 
 
 
Exercício 3 - Um sistema remoto de aquisição e transmissão de dados coleta informação na 
forma de palavras binárias de 3 bits (símbolos), a uma taxa de 10000 bps (bits por 
segundo). Após a coleta estes dados são transmitidos. Para reduzir a taxa de transmissão e 
utilizar meios de transmissão mais econômicos, é feita uma codificação das palavras 
binárias de 3 bits utilizando um código de prefixo de tamanho variável. O conjunto de 
palavras-código é: 
 
{1, 01, 001, 0001, 00001, 000001, 0000001, 0000000} 
 
Através de medidas, obteve-se a freqüência de ocorrência das palavras binárias (símbolos), 
conforme mostra a tabela. 
 
 
0m 1m 2m 3m 4m 5m 6m 7m 
000 001 010 011 100 101 110 111 
1% 2% 6% 25% 50% 12% 3% 1% 
 
 
a) Calcule a entropia da fonte, H 
b) Determine o código mostrando o mapeamento entre as palavras binárias de 3 bits 
(símbolos de informação) e as palavras-código de forma a conseguir a menor taxa de 
transmissão 
c) Determine o comprimento médio das palavras códigos, L 
d) Determine a eficiência deste código, LH=η 
e) Com que taxa as informações são coletadas (símbolos/s) 
f) Calcule a taxa de transmissão resultante na linha após a codificação (bits/s) 
 
 
Exercício 4 – Em um dado sistema, um processador recebe um dentre quatro comandos (A, 
B, C e D) a uma taxa de 10000 comandos por segundo. Cada comando está codificado com 
dois bits. A seqüência de comandos codificada é transmitida através de um cabo com banda 
passante de 8,75 kHz. 
 
a) Determine a taxa de sinalização, em bits por segundo, na saída do processador. 
 
b) Explique, considerando a banda passante do cabo, o fato de haver, na prática, uma 
grande incidência de erros na execução dos comandos. 
 
c) Observando a freqüência relativa com que os comandos A, B, C e D são apresentados ao 
processador, percebe-se que tais comandos ocorrem, respectivamente, com freqüências 
50%, 25%, 12,5% e 12,5%. Com o objetivo de reduzir a taxa de bits na transmissão dos 
dados, é empregado o código apresentado na tabela a seguir. 
 
A B C D 
0 10 110 111 
 
Determine o comprimento médio do código em bits por comando e a nova taxa de 
sinalização. 
 
d) Responda se seria possível, com os resultados obtidos no item c), esperar uma melhoria 
no desempenho do sistema. Justifique. 
 
Exercício 5 – Um antigo aparelho de fax transmite uma média diária de 20 páginas tamanho 
carta (8,5 polegadas x 11 polegadas), ao custo de R$ 0,10 por minuto de utilização. Para se 
obter uma boa resolução são utilizados 1000 elementos de imagem em cada linha horizontal 
e 1294 elementos de imagem em cada linha vertical, com 8 níveis de brilho (ou níveis de 
cinza) para cada elemento. Os elementos de imagem têm a mesma probabilidade de 
ocorrência. As páginas são transmitidas, via modem, segundo a recomendação V.22-bis da 
UIT, cuja taxa de sinalização é de 1200 baud. O modem utiliza a técnica dibit (4 níveis, com 
2 bits para cada nível). 
 
a) Determine, sem considerar outras despesas, a economia média diária obtida se o 
modem fosse substituído pelo acesso básico à Rede Digital de Serviços Integrados (RDSI), 
trabalhando com 128 kbps, ao custo de R$0,20 por minuto de utilização, e se fosse também 
empregado para a digitalização um scanner de 300 dpi (dots per inch) de resolução, com 
codificação de 8 bits por pixel. 
 
b) Verifique se a RDSI seria capaz de transmitir, em tempo real, imagens de TV com 
resolução de 640 pixels x 350 pixels, com codificação de 8 bits por pixel. Justifique. 
 
Dados / Informações Técnicas 
• Sistema de TV: transmite 30 quadros por segundo. 
 
 
 
 
 
 
CODIFICAÇÃO FONTE 
ALGORITMO DE HUFFMAN 
 
O algoritmo de Huffman permite a construção de códigos cujo comprimento médio 
atinge ou se aproxima da entropia da fonte. 
 
O algoritmo de Huffman é ótimo no sentido que nenhum outro código unicamente 
decodificável tem comprimento médio menor das palavras código. 
 
O procedimento para construção de códigos usando o algoritmo de Huffman é dado 
a seguir: 
 
a) listar os símbolos da fonte em ordem decrescente de probabilidade 
b) associar um bit distinto com cada uma dos símbolos de menor probabilidade 
c) formar uma nova probabilidade dada pela soma das duas menores 
d) reordenar o conjunto de probabilidades, caso necessário 
f) repetir o procedimento até restarem apenas duas probabilidades 
g) obter as palavras códigos fazendo o caminho inverso na árvore binária 
 
 
Símbolo
A
B
C
D
Probabilidade
0,5
0,25
0,125
0,125
0,5
0,25
0,25
0,5
0,5
0
1
0
1
0
1
Probabilidade Probabilidade
 
 
SÍMBOLO PROBABILIDADE (PI) PALAVRA CÓDIGO COMPRIMENTO DA PALAVRA CÓDIGO (LI) (PI*LI) 
A 0,5 0 1 0,5 
B 0,25 10 2 0,5 
C 0,125 110 3 0,375 
D 0,125 111 3 0,375 
 COMPRIMENTO MÉDIO DAS PALAVRAS CÓDIGO 1,75 
 
CODIFICAÇÃO FONTE 
ALGORITMO DE HUFFMAN 
 
Uma mudança na ordenação das probabilidades ou no mapeamento binário de cada 
ramo gera códigos diferentes, mas com o mesmo comprimento médio das palavras 
código. 
 
Símbolo
A
B
C
D
Probabilidade
0,5
0,25
0,125
0,125
0,5
0,25
0,25
0,5
0,5
0
1
0
1
0
1
Probabilidade Probabilidade
 
 
SÍMBOLO PROBABILIDADE (PI) PALAVRA CÓDIGO COMPRIMENTO DA PALAVRA CÓDIGO (LI) (PI*LI) 
A 0,5 1 1 0,5 
B 0,25 01 2 0,5 
C 0,125 000 3 0,375 
D 0,125 001 3 0,375 
 COMPRIMENTO MÉDIO DAS PALAVRAS CÓDIGO 1,75 
 
EXEMPLO – O exemplo abaixo ilustra a aplicação do código para compactação de um 
arquivo. 
 
 
 
 
 
 
 
Utilizando o código de comprimento variável obtido com o algoritmo de Huffman, 
obtemos a seguinte codificação: 
 
 
Arquivo Texto: 
AABCBAABBDCAABCAADAA 
 
Codificação usual: 
A=00 B=01 C=10 D=11 
 
Arquivo Binário: 
 A A B C B A A B B D C A A B C A A D A A 
00 00 01 10 01 00 00 01 01 11 10 00 00 01 10 00 00 11 00 00 = 40 bits 
Arquivo Binário: 
 A A B C B A A B B D C A A B C A A D A A 
 1 1 01 000 01 1 1 01 01 001 000 1 1 01 000 1 1 001 1 1 = 35 bits 
Exercício – Uma fonte de informação emite 1000 símbolos/s, selecionados de um 
alfabeto de 5 possíveis símbolos. As probabilidades de ocorrência de cada símbolo 
são mostradas na tabela abaixo: 
 
Símbolo da 
Fonte 
Probabilidade de 
Ocorrência 
A 0,4 
B 0,2 
C 0,2 
D 0,1 
E 0,1 
 
a) Calcule a entropia da fonte 
b) Construir um código fonte usando o algoritmo de Huffman 
c) Calcular o comprimento médio das palavras código, L 
d) Calcular a eficiência do código 
e) Calcule a taxa média de transmissãoem bits/s após a codificação fonte