COMUNICAÇÃO DIGITAL
INTRODUÇÃO À TEORIA DE INFORMAÇÃO
Evelio M. G. Fernández - 2010
Introdução à Teoria de Informação
• Em 1948, Claude Shannon publicou o trabalho “A
Mathematical Theory of Communications”. A
partir do conceito de comunicações de Shannon,
podem ser identificadas três partes:
• Codificação de fonte: Shannon mostrou que em
princípio sempre é possível transmitir a
informação gerada por uma fonte a uma taxa igual
à sua entropia.
Introduçã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
perdas
Compressão de Dados
• Arte ou ciência de representar informação de uma
forma compacta. Essas representações são criadas
identificando e utilizando estruturas que existem
nos 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 essa
redundância na forma de um modelo.
2. CODIFICAÇÃO – Uma descrição do modelo e
uma descrição de como os dados diferem do
modelo são codificados possivelmente
utilizando símbolos binários.
Diferença: dados – modelo = resíduo
Exemplo 1
Exemplo 2
Medidas de Desempenho
1. Taxa de Compressão
–
Ex: 4:1 ou 75 %
2. Fidelidade
–
Distorção (Rate Distortion Theory)
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 palavrascó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
K 1
lk
2
  1 Desigualdade de Kraft-McMillan
k 0
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 L de um código U.D.
para a codificação desta fonte é limitado por:
L  H S 
com igualdade se e somente se:
pk  r lk ,
r  0, 1, , K 1
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ódigo
a1
0
a2
11
a3
10
pa1   0,95
pa2   0,02
pa3   0,03
• L  1,05 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!
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
• L2  1,222 bits/símbolo
• L2 2  0,611 bits/símbolo
(ainda 72% acima da
entropia!)
• Ln n  H A  extensão
de ordem n = 8  fonte
com 6561 símbolos!
• Huffman: precisa criar
todas as palavras-código!
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.
Codificação Aritmética
• 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.
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).
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ético
Símbolo
FX
TX
1
2
3
4
0,5
0,75
0,875
1,0
0,25
0,625
0,8125
0,9375
Binário
.010
.101
.1101
.1111

1 
log
1


P x  

2
3
4
4
Código
01
101
1101
1111
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
repita
palavra = leia_palavra (entrada);
index = busca (palavra,dicionário);
se index = 0 então
faça
escreva (palavra, saída);
inclua (palavra, dicionário);
fim
senão
escreva (index, saída);
até fim_da_mensagem
Algoritmo de Lempel-Ziv
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Posição no Dicionário
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Conteúdo
1
0
10
11
01
00
100
111
010
1000
011
001
110
101
10001
1011
Palavra-Código
00001
00000
00010
00011
00101
00100
00110
01001
01010
01110
01011
01101
01000
00111
10101
11101
Transformada
Discreta de
Cossenos
Transformada Discreta de Cossenos
N 1 N 1
2 x  1u cos 2 y  1v
2
F u, v   C u C v  f x, y  cos
N
2N
2N
x 0 y 0
8x8 Pixels
Primitivas da Transformada Discreta de Cossenos
“Zig-Zag Scanning”
Exemplo de Codificação por Entropia em MPEG-2
Tamanho
do “run”
de zeros
Valor do coeficiente
diferente de zero
0
12
0000 0000 1101 00
0
6
0010 0001 0
1
4
0000 0011 000
0
3
0010 10
EOB
-
10
Palavra-código de
comprimento variável
Codificador MPEG
24 / 30 / 60
Conversão de Formatos
Quadros / s
BLOCOS
QUADRO
RECONSTRUIDO
Deteção
de
Movimento
ERRO DE PREDIÇÃO
Preditor
DCT
Reconstrução
Transformação Espacial
COEFICIENTES
DCT
-1
Fator de Escala
Q
Truncamento
COEFICIENTES QUANTIZADOS
Compactação
VETORES DE
MOVIMENTO
RLE
Huffman
DADOS
SAÍDA
MUX
Buffer
Compensação de Movimento
Canal Discreto sem Memória
Matriz de Canal ou Transição
p y1 | x0  
 p y0 | x0 
 p y | x 
p y1 | x1  
0
1

P




 p y0 | x J 1  p y1 | x J 1  
p y K 1 | x0  
p y K 1 | x1  



p y K 1 | x J 1 
Canal Binário Simétrico
Relações entre Várias Entropias de Canal
Capacidade do Canal BSC
Capacidade 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 especificação do tipo de sinais (binário, r-ário,
ortogonal, etc)
– O tipo de receptor usado (determinante da probabilidade
de erro do sistema).
• Todas 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
Teorema 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 uma
vez a cada Tc segundos.
Então, se
H S  C

Ts
Tc
existe um esquema de codificação para o qual a saída da
fonte pode ser transmitida pelo canal e reconstruída com
Pe   ,   0
Teorema da Codificação de Canal
ii.
Pelo contrário, se
H S  C

Ts
Tc
não é possível o anterior.
Resultado mais importante da Teoria de Informação
Código de Repetição