Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
COMUNICAÇÃO DIGITAL
INTRODUÇÃO À TEORIA DE INFORMAÇÃOÇ Ç
Evelio M G Fernández 2011Evelio M. G. Fernández - 2011
Introdução à Teoria de Informação
E 1948 Cl d Sh bli b lh “A• Em 1948, Claude Shannon publicou o trabalho “A Mathematical Theory of Communications”. A
i d i d i õ d Shpartir do conceito de comunicações de Shannon, podem ser identificadas três partes:
• Codificação de fonte: Shannon mostrou que em ç qprincípio sempre é possível transmitir a informação gerada por uma fonte a uma taxa igual ç g p gà sua entropia.
Introdução à Teoria de InformaçãoIntrodução à Teoria de Informação
• Codificação de Canal: Shannon descobriu um parâmetro calculável que chamou de Capacidade de Canal e provou que, para um determinado canal, comunicação livre de erros é possível desde que a taxa de transmissão não seja maior que a capacidade do canal.
• Teoria da Taxa de Distorção (Rate Distortion Theory): A ser utilizada em compressão com y) pperdas
C ã d D dCompressão de Dados
• Arte ou ciência de representar informação de uma f E õ ã i dforma compacta. Essas representações são criadas identificando e utilizando estruturas que existem
d d li i d dâ inos dados para eliminar redundância.• Dados:
– Caracteres num arquivo de texto– Números que representam amostras de sinais de áudio,
voz, imagens, etc.
Algoritmos de Compressão
1. MODELAGEM – Extrair informação sobre a redundância da fonte e expressar essaredundância da fonte e expressar essa redundância na forma de um modelo.
2 CODIFICAÇÃO Uma descrição do modelo e2. CODIFICAÇÃO – Uma descrição do modelo e uma descrição de como os dados diferem do modelo são codificados possivelmentemodelo são codificados possivelmente utilizando símbolos binários.
Diferença: dados – modelo = resíduo
E l 1Exemplo 1
Exemplo 2p
Medidas de Desempenho
1. Taxa de Compressão– Ex: 4:1 ou 75 %
2. Fidelidade– Distorção (Rate Distortion Theory)s o ção ( ate isto tion heo y)
E lExemplo
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 011C 1/8 10 00 110 011
D 1/8 11 01 1110 0111
Entropia de uma Fonte Binária sem Memória
Códi P fiCódigos Prefixos
N h l ódi é fi d l• Nenhuma palavra código é prefixo de qualquer outra palavra-código
• Todo código prefixo é instantâneo (o final das palavras• 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 é• Um código prefixo é sempre U.D. (a recíproca não é sempre verdadeira)
• Existe um código prefixo binário se e somente seExiste um código prefixo binário se e somente se
Desigualdade de Kraft-McMillan121
≤∑−
−K
lk Desigualdade de Kraft McMillan120
≤∑=k
Códi P fiCódigos Prefixos
• Dado um conjunto de códigos que satisfaz a d i ld d d K f M Mill SEMPRE ádesigualdade de Kraft-McMillan, SEMPRE será possível encontrar um código prefixo com esses
i l ódi Ocomprimentos para as suas palavras-código. O comprimento médio das palavras do código estará li i d l i d f d i f ã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) i édi d ódi U DLH(S), o comprimento médio de um código U.D. para a codificação desta fonte é limitado por:
L
( )SHL ≥
com igualdade se e somente se:
1,,1,0, −== − Krrp klk K
Códigos de Huffmann Binários
1. Ordenar em uma coluna os símbolos do mais á l á lprová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ódi Óti á iCódigos Ótimos r-ários
• Método de Huffmann: aplica-se o método com o seguinte artifício:seguinte artifício:
• Adicionam-se ao alfabeto original símbolos fictícios com probabilidade zero de ocorrência atéfictícios com probabilidade zero de ocorrência, até o número de símbolos assim gerado ser congruente a 1 mod (r 1)congruente a 1 mod (r – 1).
• Aplica-se o método de Huffmann agrupando-se rí b l d d O ódi d ésímbolos de cada vez. O código gerado é um
código r-ário ótimo para o alfabeto original.
F t Alf b t PFonte com Alfabeto Pequeno
Símbolo Código • bits/símbolo05,1=Lga1 0a 11
• H(A) = 0,335 bits/simbolo• Redundância = 0,715 a2 11
a3 10
,bits/símbolo (213% da entropia)p )
• São necessários duas vezes mais bits do que o
( ) 95,01 =ap( ) 02,02 =ap mais bits do que o
prometido pela entropia!( ) 02,02ap( ) 03,03 =ap
Segunda Extensão da Fonte
Símb. Prob. Cod.0 9025 0
• bits/símbolobi / í b l
222,12 =La1a1 0,9025 0a1a2 0,0190 111a a 0 0285 100
• bits/símbolo (ainda 72% acima da entropia!)
611,022 =L
a1a3 0,0285 100a2a1 0,0190 1101a2a2 0 0004 110011
entropia!)• extensão
de ordem n = 8 ⇒ fonte( )⇒→ AHnLn
a2a2 0,0004 110011a2a3 0,0006 110001a3a1 0.0285 101
de ordem n = 8 ⇒ fonte com 6561 símbolos!
• Huffman: precisa criar3 1
a3a2 0,0006 110010a3a3 0,0009 110000
• Huffman: precisa criar todas as palavras-código!
C difi ã A it étiCodificação Aritmética
• É mais eficiente designar uma palavra-código para üê i d h duma seqüência de tamanho m do que gerar as
palavras-código para todas as seqüências de htamanho 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.
C difi ã A it étiCodificação Aritmética
• Um conjunto possível de tags para representar üê i d í b l ã ú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.
Al it D if Id tifi dAlgoritmo 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)).( g ) ( )3. Determinar o valor de xk para o qual
F (x 1) ≤ t* ≤ F (x )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éticoExemplo: Unicidade e Eficiência do Código Aritmético
1 ⎤⎡Símbolo FX XT Binário ( ) 11log +⎥
⎥
⎤⎢⎢
⎡xP
Código
1 0 5 0 25 010 2 011 0,5 0,25 .010 2 012 0,75 0,625 .101 3 101 3 0,875 0,8125 .1101 4 1101, ,4 1,0 0,9375 .1111 4 1111
Códi B d Di i á iCódigos Baseados em Dicionários
• Seqüências de comprimento variável de símbolos d f ã difi d l ódi dda 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 ç gcodificação de fonte.
Códigos Baseados em DicionáriosCódigos Baseados em Dicionários
itrepitapalavra = leia_palavra (entrada);index = busca (palavra dicionário);index = busca (palavra,dicionário);se index = 0 entãofaçafaça
escreva (palavra, saída);inclua (palavra, dicionário);
fimsenão
(i d íd )escreva (index, saída);até fim_da_mensagem
Al it d L l ZiAlgoritmo de Lempel-Ziv
Seqüência Binária:
10101101001001110101000011001110101100011011
Frases:Frases:
1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 100001, 1011
Algoritmo de Lempel-ZivAlgoritmo de Lempel Ziv
Posição no Dicionário Conteúdo Palavra-Código Posição no Dicionário Conteúdo Palavra Código1 0001 1 00001 2 0010 0 00000 3 0011 10 000104 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 0111010 1010 1000 0111011 1011 011 01011 12 1100 001 01101 13 1101 110 0100013 1101 110 0100014 1110 101 00111 15 1111 10001 10101 16 1011 1110116 1011 11101
Transformada Discreta de Cossenos
Transformada Discreta de Cossenos
( ) ( ) ( ) ( ) ( ) ( )∑∑− − ++1 1 12122 N N vyuxfCCF ππ
8x8 Pixels( ) ( ) ( ) ( ) ( ) ( )∑∑
= =
=0 0 2
cos2
cos,,x y N
yN
yxfvCuCN
vuF
Primitivas da Transformada Discreta de Cossenos
“Zi Z S i ”“Zig-Zag Scanning”
E l d C difi ã E t i MPEG 2Exemplo de Codificação por Entropia em MPEG-2
Tamanho do “run” Valor do coeficiente Palavra-código de do run de zeros diferente de zero comprimento variável
0 12 0000 0000 1101 000 12 0000 0000 1101 00
0 6 0010 0001 0
1 4 0000 0011 000
0 3 0010 10
EOB - 10
Codificador MPEGConversão de Formatos
BLOCOS
24 / 30 / 60Quadros / s
deDeteção QUADRO
RECONSTRUIDO
ERRO DE PREDIÇÃOMovimento
T f ã E i lDCTPreditor
Reconstrução
Transformação EspacialDCT
COEFICIENTES
QDCT-1 Fator de Escala
Truncamento
COEFICIENTES QUANTIZADOS
QDCT
Compactação
VETORES DEMOVIMENTO DADOS
RLEHuffman
SAÍDAMUX Buffer
Compensação de MovimentoCompensação de Movimento
Canal Discreto sem Memória
Matriz de Canal ou Transição
( ) ( ) ( )( ) ( ) ( ) ⎥
⎤⎢⎡ − 010100
|||||| K xypxypxyp L
( ) ( ) ( )
( ) ( ) ( )⎥⎥⎥⎥
⎢⎢⎢⎢
= − 111110 |||P K xypxypxyp
MMM
L
( ) ( ) ( )⎥⎦⎢⎣ −−−− 111110 ||| JKJJ xypxypxyp L
Canal Binário Simétrico
Relações entre Várias Entropias de Canal
Capacidade do Canal BSC
C id d d C lCapacidade de Canal
• A capacidade de canal não é somente uma propriedade de um canal físico particular.
• Um canal não significa apenas o meio físico de propagação das mensagens, mas também:
A ifi ã d i d i i (bi á i á i– A especificação do tipo de sinais (binário, r-ário, ortogonal, etc)
– O tipo de receptor usado (determinante da probabilidade– O tipo de receptor usado (determinante da probabilidade de erro do sistema).
• Todas estas informações estão incluídas na matrizTodas estas informações estão incluídas na matriz de transição do canal. Esta matriz especifica completamente o canal.
Teorema da Codificação de Canal
T d C difi ã d C lTeorema da Codificação de Canal
i. Seja uma fonte discreta sem memória com alfabeto S e entropia H(S) que produz símbolos a cada Ts segundos. Seja um canal DMC com capacidade C que é usado umaSeja um canal DMC com capacidade C que é usado uma vez a cada Tc segundos.Então seEntão, se
( )cs T
CT
SH≤
existe um esquema de codificação para o qual a saída da fonte pode ser transmitida pelo canal e reconstruída comfonte pode ser transmitida pelo canal e reconstruída com
0, →= εεeP
T d C difi ã d C lTeorema da Codificação de Canal
ii. Pelo contrário, se
( )TC
TSH
>
não é possível o anterior.
cs TT
p
Resultado mais importante da Teoria de Informaçãop ç
Código de Repetição