Introducao a Teoria da Informacao

Prévia do material em texto

INTRODUÇÃO À TEORIA DA 
INFORMAÇÃO
SISTEMA DE TRANSMISSÃO DIGITALSISTEMA DE TRANSMISSÃO DIGITALSISTEMA DE TRANSMISSÃO DIGITALSISTEMA DE TRANSMISSÃO DIGITAL
� Os codificadores de fonte possuem a finalidade de “casar” a fonte de dados com o
sistema levando em consideração a estatística de acontecimento dos símbolos da fonte. Ossistema levando em consideração a estatística de acontecimento dos símbolos da fonte. Os
códigos de fonte mais conhecidos são os que utilizam o algoritmo de Huffman e o de
Huffman modificado.
� O codificador de canal está projetado para, através da inclusão de símbolos de
redundância de forma inteligente, fazer com que a informação, após trafegar pelo canal,
possa ser recuperada de eventuais erros de acordo com o critério de qualidade exigido.
� O conjunto modulador-demodulador ( MODEM ) transforma o canal analógico
em canal discreto para possibilitar o funcionamento do conjunto codificador-decodificador
( CODEC ).
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
� Denomina-se alfabeto de uma fonte de informação discreta o
conjunto de elementos que a fonte pode selecionar. Por exemplo:
� Texto: {A, B, C ... X, Y, Z, 0, 1,2 ... 9,?, !, ... “}
� Sensor de nível ( h 2≥ hA ? ):{sim, não}
� Opção do cardápio: (1,2,3,4,5, 6)
� Considere-se uma fonte discreta com alfabeto de k elementos, {x1,
x ,..., x }. A relação entre o número de vezes n, em que um dadox2,..., xk }. A relação entre o número de vezes n, em que um dado
elemento xi, (com i = 1,2, ... , k) é selecionado pela fonte e o
número total N de seleções, para N tendendo a infinito, é a
probabilidade de ocorrência daquele elemento:





=
∞→ N
n
xp i
N
i lim)(
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
� A soma das probabilidades de ocorrência de todos os elementos do
alfabeto da fonte é, evidentemente, , pois a fonte só
seleciona elementos contidos em seu alfabeto (a probabilidade de
selecionar elemento não-contido no alfabeto é nula).
� A quantidade de informação associada à ocorrência de um elemento xi
∑
=
=
k
i
ixp
1
1)(
� A quantidade de informação associada à ocorrência de um elemento xi
mede o grau de surpresa quando
aquele elemento é selecionado pela fonte. Elementos selecionados
com maior freqüência causam menos
surpresa, ao passo que elementos de ocorrência mais rara causam
mais surpresa. Define-se a quantidade
de informação I(xi), associada à seleção do elemento xi ; usando a
função logaritmo de base 2:








=
)(
1
log)( 2
i
i xp
xI
� Quantidade de informação, assim definida, tem como características: 
� Quantidade de informação varia com o inverso da probabilidade de
ocorrência - elementos menos freqüentes têm quantidade de
informação maior que elementos mais freqüentes.
� Se o alfabeto da fonte tem um único elemento, a quantidade de
informação associada à seleção desse elemento (evento certo) é nula:
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA








=
)(
1
log)( 2
i
i xp
xI
informação associada à seleção desse elemento (evento certo) é nula:
I(xi)= O para p(xi) = 1.
� Se a fonte seleciona um elemento não-contido em seu alfabeto (evento
impossível), a quantidade de informação associada a essa seleção é
infinita: I(xi)= ∞ para p(xi) = 0.
� Se a seleção de cada elemento não afeta a probabilidade de ocorrência de
outros nas seleções seguintes, a quantidade total de informação de uma
seqüência de elementos é a soma das quantida-
des de informação individuais
� A quantidade de informação - medida em bit (acrônimo de binary unit
= unidade binária, devido ao uso logaritmo de base 2) - é um número
real não-negativo adimensional.
� Quantidade de informação é importante para a criação de códigos
(representações de elementos da fonte discreta) para transmissão
eficiente de informação. Ao criar um código para representar letras,
algarismos e sinais de pontuação no telégrafo elétrico, Morse
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
algarismos e sinais de pontuação no telégrafo elétrico, Morse
intuitivamente associou representação mais curta para
caracteres mais freqüentes (com menor quantidade de informação) e
mais longa para caracteres menos freqüentes (com maior quantidade
de informação).
� Define-se como entropia de uma fonte discreta a quantidade média de
informação por ocorrência (seleção de um elemento pela fonte).
� Considere-se que a fonte discreta seleciona, num dado intervalo, um total
de N = nl + n2 + ... + nk , elementos, com n1 ocorrências do elemento x1 ,
n2 ocorrências do elemento x2, ...., nk ocorrências do elemento xk . Com
ocorrências estatisticamente independentes, a quantidade total de
informação total dessas N seleções é IT = nl I(x1) + n2 I(x2) + ... + nk I(xk) : A
relação entre a quantidade total de informação e o número de ocorrência
no intervalo é:
→∞
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
)(...)()( 2
2
1
1
k
kT xI
N
n
xI
N
n
xI
N
n
N
I +++=
� Para N→∞, tem-se a entropia, definida pela expressão:
� Entropia é uma característica da fonte de informação discreta que depende
da probabilidade de Ocorrência de cada um dos elementos de seu alfabeto.
Quanto maior a entropia da fonte maior será a incerteza
sobre qual elemento a ser selecionado (menor previsibilidade da fonte).
∑∑
==
∞→






===
k
i i
i
k
i
ii
T
N
bit
xp
xpxIxp
N
I
H
1
2
1
)(
)(
1
log)()()(lim
� Exemplo: Considere-se que, no restaurante, observando-se pedidos
feitos durante um período de tempo suficientemente longo, foram
determinadas as probabilidades de ocorrência de cada uma das
opções, conforme Tabela 9B. Observe-se que a soma das
probabilidades de todos os elementos do alfabeto da
fonte deve ser igual a l:
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
Opção Prato Probabilidade de ocorrência Opção Prato Probabilidade de ocorrência 
1 Moqueca capixaba 1/2 
2 Filé com fritas 1/4 
3 Mocotó no feijão 1/8 
4 Rabada à moda 1/16 
5 Buchada de bode 3/64 
6 Jabá com jerimum 1/64 
� A quantidade de informação de cada uma das opções é:
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
Opção Prato Probabilidade de ocorrência 
1 Moqueca capixaba 1/2 
2 Filé com fritas 1/4 
3 Mocotó no feijão 1/8 
4 Rabada à moda 1/16 
5 Buchada de bode 3/64 
6 Jabá com jerimum 1/64 
� A entropia dessa fonte discreta é: 
� H = (1/2) . 1 + (1/4) . 2 + (1/8) . 3 + (1/16) . 4 + (3/64) . 4,415 + (1/64).6= 1,926 bit.
� Tem-se, em média, a quantidade de informação de 1,926 bit por elemento selecionado. 
� Considere-se uma fonte discreta com alfabeto de apenas dois
elementos como, por exemplo, um sensor chave: {sim, não} - uma
fonte binária. Sejam p(sim) = x e p(não) = 1 - x as respectivas probabili-
dades de ocorrência desses elementos (com x real, adimensional e 0 <
x < 1).
� A entropia da fonte binária é função da probabilidade x: 
� H(x) = x log(1/x) + (l - x) . log2[ l / (l - x)] = - x . log2 (x) - (l - x) . log2 (l - x) (1)
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
� H(x) = x log(1/x)+ (l - x) . log2[ l / (l - x)] = - x . log2 (x) - (l - x) . log2 (l - x) (1)
� A entropia é máxima para x tal que a derivada primeira é nula, , 
e a derivada segunda é negativa, . Derivando (1) em 
relação a x: 
� Essa derivada é nula para 1 - x = x, ou seja, x = 1/2. 
0=
dx
dH
0
2
2
<
dx
Hd





 −=
x
x
dx
dH 1
log2
� Para
� A entropia máxima ( para x = ½ ) é: 
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
( ) entropia máxima de Ponto 0log4 e 0 se-obtém ,
2
1
22
2
→<−=== e
dx
Hd
dx
dH
x
)1(
)(log1).1()1(
)(log.
1
1
)(log
1
2
2222
2
xx
e
x
xx
e
x
x
x
x
dx
d
e
x
x
dx
Hd
−
−=−−−
−
=




 −
−
=
� A entropia máxima ( para x = ½ ) é: 
( ) ( ) bit 12log
2
1
12log
2
1
22 =




 −+= Hmáx
� Com dois elementos equiprováveis (x = 1 - x = ½ ), a entropia é máxima (a
fonte é menos previsível).
� Observe-se que, à medida que um dos elementos se torna mais provável
que o outro, a entropia da fonte decresce.
� Se a probabilidade de ocorrência de um dos elementos é igual a 1 (evento
certo), a do outro é 0 (evento impossível) e a entropia da fonte é zero.
� Esse resultado pode ser generalizado - a entropia de uma fonte discreta
com alfabeto de k elementos é máxima para p( x ) = 1/k, i = 1,2, ... , k
QUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIAQUANTIDADE DE INFORMAÇÃO E ENTROPIA
com alfabeto de k elementos é máxima para p( xi ) = 1/k, i = 1,2, ... , k
(elementos equiprováveis). O valor máximo de entropia de uma fonte discreta
com alfabeto de k elementos é, portanto:
� Por exemplo, para a fonte de opções de cardápio (Tabela 9B), a quantidade
de informação de cada opção varia entre 1 bit para a preferida do público e
6 bits para a menos procurada e a entropia da fonte é H = 1,926 bit. Se
todas as seis opções ocorressem com a mesma probabilidade (= 1/6), a
entropia da fonte teria o valor máximo:
)(log2max kH =
bits 58,2)6(log2max ≅=H
CODIFICAÇÃO DE FONTE
� Codificação de fonte consiste em associar, a cada elemento do alfabeto da
fonte, um caractere – uma combinação de elementos de código. Se todos os
caracteres têm o mesmo número de elementos de código, diz-se que o
código é de comprimento constante. Se o número de elementos de código
não é o mesmo para todos os caracteres, o código é de comprimento variável.
� A codificação com elementos binários (que podem assumir apenas dois
valores) é particularmente interessante para transmissão elétrica. Cada
elemento do conjunto binário, representado por {0, 1}, é denominado
dígito binário - ou bit (acrônimo de binary digit - não confundir comdígito binário - ou bit (acrônimo de binary digit - não confundir com
unidade binária, embora seja usado o mesmo acrônimo).
� Com n elementos binários de código obtêm-se 2n combinações de bits
(caracteres) que podem representar elementos do alfabeto da fonte de
informação discreta.
� No exemplo do restaurante, com código binário com comprimento
variável, duas das opções podem ser representadas com caracteres de 1
bit, e as quatro opções restantes com caracteres de 2 bits. De preferência,
devem ser associados caracteres mais curtos aos elementos mais
freqüentes.
CODIFICAÇÃO DE FONTE
� Para representar as seis opções, com código de comprimento
constante n, deve-se ter:
� Como n ( número de dígitos binários ) deve ser inteiro, o número
mínimo de bits para o código de comprimento constante é n = 3.
)(log 58,2)6(log
)2log(
)6log(
62 2max2 kHnn
n =≥→≅=≥→≥
� No código binário de comprimento variável, o número médio de bits
(dígitos binários) por caractere, considerando as probabilidades de
ocorrência indicadas na Tabela 9B, é inferior ao número de bits por
caractere do código de comprimento constante:
25,1
4
1
2
4
3
64
1
64
3
16
1
8
1
2
4
1
2
1
1 =+=




 ++++




 +=n
CODIFICAÇÃO DE FONTE
Opção Prato 
Probabilidade 
de ocorrência 
Código Binário
Comprimento
Variável
Comprimento
Constante
1 
Moqueca 
capixaba 
1/2 0 000
2 Filé com fritas 1/4 1 0012 Filé com fritas 1/4 1 001
3 
Mocotó no 
feijão 
1/8 00 010
4 
Rabada à 
moda 
1/16 01 011
5 
Buchada de 
bode 
3/64 10 100
6 
Jabá com 
jerimum 
1/64 11 101
Algoritmo de Huffman
� Algoritmo para a compressão de arquivos, principalmente arquivos
textos.
� Atribui códigos menores para símbolos mais freqüentes e códigos
maiores para símbolos menos freqüentes.
� Código é um conjunto de bits.
� Representação dos dados é feita com códigos de tamanho variável� Representação dos dados é feita com códigos de tamanho variável
Código ASCII
A=01000001
B=01000010
.
.
.
a=01100001
b=01100010
Código de Huffman
A=? (0)
B=? (110)
.
.
.
a=? (1111110)
b=? (11111111110)
Algoritmo de Huffman
� Supondo A e C mais freqüentes que C e D no conjunto de valores
possíveis.
ABACDA= 0 110 0 10 111 0
A B A C D A
Símbolo
A
B
C
D
Código
0
110
10
111
Algoritmo de Huffman
� Dado:Tabela de freqüências dos N símbolos de um alfabeto
� Objetivo: Atribuir códigos aos símbolos de modo que os mais
freqüentes tenham códigos menores (menos bits).
A-0.2
B-0.1
a-0.1
.
.
.
A-0
B-10
a-110
.
.
.
Huffman
Algoritmo de Huffman
Fdjoiasdjfoidsjfoisofnsdo
Sdjfoisdjfoisdfoisdfoid
Oidsfoisdnfosdf
Sdoifsjfsdfskodnfsdknf Arquivo
comprimido