TE111 { Comunica˘c~ao Digital - eletrica.ufpr.br · k log 2 p k bits/s mbolo da fonte ... 2 0;5 0;25log 2 0;25 2 0;125log 2 0;125 = 1; ... = 0;25log 2 0;25 0;75log 2 0;75 = 0;81

TE111 – Comunicacao DigitalIntroducao a Teoria de Informacao e Codificacao de Fonte

Evelio M. G. Fernandez

25 de outubro de 2016

Evelio M. G. Fernandez TE111 – Teoria de Informacao e Codificacao de Fonte

Introducao a Teoria de Informacao

Em 1948, Claude Shannon publicou o trabalho “A MathematicalTheory of Communications”. A partir do conceito decomunicacoes de Shannon, podem ser identificadas tres partes:

1 Codificacao de Fonte: Shannon mostrou que em princıpiosempre e possıvel transmitir a informacao gerada por umafonte a uma taxa igual a sua entropia.

2 Codificacao de Canal: Shannon descobriu um parametrocalculavel que chamou de Capacidade de Canal e provou que,para um determinado canal, comunicacao livre de erros epossıvel desde que a taxa de transmissao nao seja maior que acapacidade do canal.

3 Teoria Taxa-Distorcao: A ser utilizada em compressao comperdas.


Notes

Notes

Sistema de Comunicacao Digital


Compressao de Dados

Arte ou ciencia de representar informacao de uma formacompacta. Essas representacoes sao criadas identificando eutilizando estruturas que existem nos dados para eliminarredundancia.

Dados:

Caracteres num arquivo de texto;Numeros que representam amostras de sinais de audio, voz,imagens, etc.


Notes

Notes

Algoritmos de Compressao

1 MODELAGEM – Extrair informacao sobre a redundancia dafonte e expressar essa redundancia na forma de um modelo;

2 CODIFICACAO – Uma descricao do modelo e umadescricao de como os dados diferem do modelo saocodificados possivelmente utilizando sımbolos binarios.

Diferenca: dados – modelo = resıduo


Exemplo 1

Resıduo: en = xn − xn ∈ {−1,0,1} ⇒ 2 bits para representa-lo


Notes

Notes

Exemplo 2

Resıduo: en = xn − xn−1


Medidas de Desempenho

1 Taxa de Compressao

Ex: 4:1 ou 75 %

2 Fidelidade

Distorcao (Rate-Distortion Theory)


Notes

Notes

Exemplo 3

Sımbolo (sk) Prob. (pk) 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

Taxa de compressao:

L =

K−1∑k=0

lk · pk =⇒

LI = 2 bits/sımbolo

LII = 1,25 bits/sımbolo

LIII = LIV = 1,875 bits/sımbolo

Fidelidade: Decodificacao da sequencia: . . . 0011 . . . pelo ’codigo’ II?


Codigos Prefixos

Nenhuma palavra codigo e prefixo de qualquer outrapalavra-codigo;

Todo codigo prefixo e instantaneo (o final das palavras-codigoe bem definido);

Um codigo prefixo e sempre U.D. (a recıproca nao e sempreverdadeira);

Existe um codigo prefixo binario se e somente se

K−1∑k=0

2lk ≤ 1→ Desigualdade de Kraft-McMillan.

Com relacao aos codigos da tabela:

I → 4× 2−2 = 1II → 2−1 + 3× 2−2 = 1,25 > 1III e IV → 2−1 + 2−2 + 2−3 + 2−4 = 0,9375 < 1


Notes

Notes

Codigos Prefixos

Dado um conjunto de comprimentos de palavras codigo quesatisfaz a desigualdade de Kraft-McMillan, SEMPRE serapossıvel encontrar um codigo prefixo com esses comprimentospara as suas palavras-codigo. O comprimento medio daspalavras do codigo estara limitado pela entropia da fonte deinformacao.


Medida da Informacao

- Modelo da fonte: S , V.A. discreta com Prob(S = sk) = pk, k = 0,1, . . . ,K − 1

- Informacao obtida com a revelacao do evento: S = sk → I(sk) = − log2 pk bits

- Propriedades de I(·)Se pk = 1⇒ I(sk) = 0

0 ≤ pk ≤ 1⇒ I(sk) ≥ 0

pk < pi ⇒ I(sk) > I(si)

Se sk e si sao estatisticamente independentes ⇒ I(sksi) = I(sk) + I(si)


Notes

Notes

Medida da Informacao – Entropia

Entropia da Fonte, H(S)

Valor medio de I(sk) sobre o alfabeto S. E uma medida do numero medio desımbolos necessarios para codificar a fonte.

H(S) , E[I(sk)]

= −K−1∑k=0

pk log2 pk bits/sımbolo da fonte

Propriedades de H(S)

H(S) ≥ 0;

H(S) = 0 se e somente se pk = 1 para algum k;

H(S) ≤ log2 K com igualdade se e somente se pk = 1k

para todo k.

Exemplo: Entropia da fonte da tabela?

→ H(S) = −0,5 log2 0,5−0,25 log2 0,25−2×0,125 log2 0,125 = 1,75 bits/sımbolo


Entropia de uma Fonte Binaria sem Memoria

Fonte binaria com Prob(S = 0) = p e Prob(S = 1) = 1− p

⇒ H(S) = −p log2 p− (1− p) log2(1− p)


Notes

Notes

Teorema da Codificacao de Fonte

Dada uma fonte discreta sem memoria com entropia H(S), ocomprimento medio L de um codigo U.D. para a codificacaodesta fonte e limitado por:

L ≥ H(S)

com igualdade se e somente se:

pk = r−lk , r = 0,1, . . . ,K−1⇒ codigos absolutamente otimos

Codigos (quase) absolutamente otimos:

⇒ − logr pk ≤ lk ≤ − logr pk + 1

⇒ H(S)

log2 r≤ L ≤ H(S)

log2 r+ 1


Extensao de uma Fonte Discreta sem Memoria

Fonte extendida → sımbolos tratados em blocos de n sımbolos da fonte original;

Alfabeto (Sn) com Kn blocos (mensagens) distintos de comprimento n.

Exemplo: Fonte binaria, S = {0,1} com Prob(S = 0) = 0,25 e Prob(S = 1) = 0,75

⇒ H(S) = −0,25 log2 0,25− 0,75 log2 0,75 = 0,81 bits/sımbolo

Considerar agora mensagens ou palavras de comprimento n = 3

Mensagem (sk) Probabilidade

000 1/64001 3/64010 3/64011 9/64100 3/64101 9/64110 9/64111 27/64

H(S3) = 2,45 bits/mensagem;

Notar que H(S3) = 3H(S);

Em geral, H(Sn) = nH(S).


Notes

Notes

Extensao de uma Fonte Discreta sem Memoria

Sejam:

L→ comprimento medio em caracteres do codigo por sımbolo da fonte S;

Ln → comprimento medio em caracteres do codigo por sımbolo da fonteextendida Sn;Lnn→ comprimento medio em caracteres do codigo por sımbolo da fonte

S;

=⇒ H(S)

log2 r≤ Ln

n<

H(S)

log2 r+

1

n

limn→∞

Ln

n=

H(S)

log2 r

Exercıcio: Seja uma fonte com S = {s0,s1} e probabilidades {3/4, 1/4}. Sejaa fonte extendida de ordem n = 2. Para codifica-las considere os codigos {0,1}e {0,10, 110,111}, respectivamente. Determine L, Ln e Ln

n.


Codigos de Huffmann Binarios

1 Ordenar em uma coluna os sımbolos do mais provavel aomenos provavel;

2 Associar ‘0’ e ‘1’ aos dois sımbolos menos provaveis ecombina-los (soma das probabilidades individuais);

3 Repetir 1 e 2 ate a ultima coluna que tera apenas doissımbolos; associa-se ‘0’ e ‘1’.


Notes

Notes

Exercıcio

Obter um codigo um codigo otimo binario pelo metodo deHuffmann para a seguinte fonte discreta de informacao:

Sımbolo Prob.

s0 0,4

s1 0,2

s2 0,2

s3 0,1

s4 0,1

a) Verifique se e codigo prefixo;

b) Determine L;

c) Satisfaz o teorema da codificacao de fonte?

d) E codigo absolutamente otimo ou quase absolutamente otimo?


Codigos Otimos r-arios

Metodo de Huffmann: aplica-se o metodo com o seguinteartifıcio:

Adicionam-se ao alfabeto original sımbolos fictıcios comprobabilidade zero de ocorrencia, ate o numero de sımbolosassim gerado ser congruente a 1 mod (r − 1);

Aplica-se o metodo de Huffmann agrupando-se r sımbolos decada vez. O codigo gerado e um codigo r-ario otimo para oalfabeto original.


Notes

Notes

Exercıcio

Obter um codigo otimo ternario pelo metodo de Huffmann para aseguinte fonte discreta de informacao:

Sımbolo Prob.

s0 1/3

s1 1/6

s2 1/6

s3 1/9

s4 1/9

s5 1/9

a) Verifique se e codigo prefixo;

b) Determine L;

c) Satisfaz o teorema da codificacao de fonte?

d) E codigo absolutamente otimo ou quase absolutamente otimo?


Fonte com Alfabeto Pequeno

Sımbolo Codigo

a1 0

a2 11

a3 10

P(a1) = 0,95P(a2) = 0,02P(a3) = 0,03

L = 1,05 bits/sımbolo

H(A) = 0,335 bits/sımbolo

Redundancia = 0,715 bits/sımbolo (213%da entropia)

Sao necessarios duas vezes mais bits doque o prometido pela entropia!


Notes

Notes

Segunda Extensao da Fonte

Sımbolo Prob. Codigo

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)⇒ extensao deordem n = 8⇒ fonte com 6561sımbolos!

Huffman: precisa criar todas aspalavras-codigo!

⇒ Codificacao artimetica,codigos baseados emdicionarios, etc.


Canal Discreto sem Memoria


Notes

Notes

Matriz de Canal ou Matriz de Transicao

P =

p(y0|x0) p(y1|x0) · · · p(yK−1|x0)p(y0|x1) p(y1|x1) · · · p(yK−1|x1)

......

. . ....

p(y0|xJ−1) p(y1|xJ−1) · · · p(yK−1|xJ−1)


Canal Binario Simetrico


Notes

Notes

Relacoes entre Varias Entropias de Canal


Capacidade do Canal BSC


Notes

Notes

Capacidade de Canal

A capacidade de canal nao e somente uma propriedade de umcanal fısico particular;

Um canal nao significa apenas o meio fısico de propagacaodas mensagens, mas tambem:

A especificacao do tipo de sinais (binario, r-ario, ortogonal,etc);O tipo de receptor usado (determinante da probabilidade deerro do sistema);

Todas estas informacoes estao incluıdas na matriz de transicaodo canal. Esta matriz especifica completamente o canal.


Sistema de Comunicacao com Codificacao de Canal


Notes

Notes

Teorema da Codificacao de Canal

i. Seja uma fonte discreta sem memoria com alfabeto S eentropia H(S) que produz sımbolos a cada Ts segundos. Sejaum canal DMC com capacidade C que e usado uma vez acada Tc segundos.Entao, se

H(S)

Ts≤ C

Tc

existe um esquema de codificacao para o qual a saıda da fontepode ser transmitida pelo canal e reconstruıda com

Pe → ε, ε→ 0


Teorema da Codificacao de Canal (Cont.)

ii. Pelo contrario, seH(S)

Ts>

C

Tc

nao e possıvel o anterior.

⇒ Resultado mais importante da Teoria de Informacao.


Notes

Notes

Codigo de Repeticao


Medida de Informacao para Sinais ContınuosCaso Discreto:

X → V.A. discreta;

x ∈ alfabeto finito.

Caso Contınuo:

X → V.A. contınua;

x ∈ alfabeto infinito.

Pelo teorema do valor medio, existe um xi dentro de cada bin tal que:

fX(xi)∆ =

∫ (i+1)∆

i∆fX(x)dx.

Notes

Notes

Limite de Shannon


Limite de Shannon


Notes

Notes

Documents

TE111 { Comunica˘c~ao Digital - eletrica.ufpr.br · k log 2 p k bits/s mbolo da fonte ... 2 0;5 0;25log 2 0;25 2 0;125log 2 0;125 = 1; ... = 0;25log 2 0;25 0;75log 2 0;75 = 0;81