TEO INF 3

Prévia do material em texto

Teoria da informação. 
Professor Clauberto Vidal. 
 
Conceitos Fundamentais. 
 
1 – Introdução. 
 
O problema fundamental da comunicação é reproduzir no destino, ou exatamente ou 
aproximadamente a informação transmitida pela fonte geradora da informação. Como essa 
informação será codificada (comprimida) e a quais taxas essa informação poderá ser 
transmitida sobre o canal. 
A teoria da informação, a qual considera-se fundada em 1948 por Claude E. Shannon, 
está relacionada não apenas com tais questões, particulares a teoria da comunicação, como 
também a questões relativas a diversas áreas do conhecimento como: Criptografia e 
Criptoanálise, Teoria de Probabilidade, Inteligência Artificial, Economia, etc. 
Shannon estabelece que na média, o número de bits necessários para representar o 
resultado de um evento aleatório é dado pela entropia e que comunicação confiável é possível 
mesmo sobre canais com ruído, desde que a taxa de comunicação esteja abaixo de um certo 
limiar 
denominado capacidade do canal. 
 
2 - Sistemas de Comunicação. 
 
Um sistemas de comunicação, consiste de 5 partes: 
 
• Uma fonte de informação que produz uma mensagem ou seqüência de mensagens a serem 
transmitidas ao terminal receptor. Esta mensagem, figura abaixo, 
 
 
 
Figura 1 - Modelo esquemático de um sistema geral de comunicação. 
 
pode ser de vários tipos: 
 
(a) Uma seqüência de letras como em um sistema telegráfico; 
(b) Uma única função no tempo f(t), como o rádio ou uma função com mais de uma variável, 
f(x, y, t) como o sinal de uma transmissão de televisão em preto e branco; 
 
Teoria da Informação/Clauberto Vidal. Pág.1/7 
• Um transmissor (codificador) que opera na mensagem de modo que esta possa ser 
transmitido sobre o canal; 
 
• Um canal que é o meio pelo qual a informação será transmitida, este meio contem ruído (em 
casos ideais o ruído é desconsiderado) e irá alterar de alguma forma a mensagem original; 
 
• O receptor (decodificador) que apenas faz a função inversa do transmissor de modo a obter 
a mensagem original; 
 
• O destino, para quem a mensagem é encaminhada. 
 
3 - Medida de Informação. 
 
Sabendo como a informação por mensagem m é gerada, como podemos medir quanta 
informação é produzida? Com propósito de responder esta questão Shannon definiu a função: 
iP
mI 1log)( = 
Esta função é denominada auto-informação ou conteúdo da informação, e indica o total 
de conhecimento sobre o resultado de um certo evento. Pela função, assim como 
intuitivamente esperamos, um evento menos provável tem mais informação que outro mais 
provável. Se o logaritmo tiver base 2 o conteúdo da informação será expresso em bits. Se a 
base do logaritmo é e, então o conteúdo da informação é medido em nuts. Como exemplo 
considere o arremesso de uma moeda honesta. Como a probabilidade do resultado ser cara é 
igual a 1/2 a medida de auto-informação será: 
 
bitcaraI 12log)5,0/1(log)( 22 === 
 
4 – Entropia. 
 
 
Podemos agora mensurar a quantidade de informação média por mensagem emitida 
pela fonte : 
 
bitsPP
P
PIPmH i
n
i
i
i
n
i
ii
n
i
i 2
1
2
11
log1log)( ∑∑∑
==−
−===
 
Essa medida é denominada entropia ou incerteza da variável aleatória m. 
Podemos notar que a entropia de m é o valor médio do conteúdo da informação I(m). 
Podemos dizer que a entropia é o número médio de dígitos binários por mensagem 
necessário para codificação da fonte e é obtido através de H(m) (em bits), para determinada 
distribuição de probabilidades das mensagens. 
 
Exemplo. 
 
1 - Uma fonte gera uma mensagem (dentre quatro mensagens) a cada um 
microssegundo. As probabilidades de ocorrência dessas mensagens são: 0,4/0,3/0,2/0,1. Cada 
mensagem transmitida é independente das outras mensagens da seqüência. 
 
A)Qual é a entropia da fonte? 
B) Qual é a taxa de informação gerada por esta fonte (em bis /seg)? 
Teoria da Informação/Clauberto Vidal. Pág.2/7 
 
bits
PPPPPPPP
PPPPPPPP
PPmH
A
i
n
i
i
846,1
)loglogloglog(
2log
1
)loglogloglog(
)log()(
)
4104310321021101
10
424323222121
2
1
=
=+++−=
=+++−=
=−= ∑
=
 
B) Cada mensagem é transmitida em 0,000001 segundo. Em um segundo são transmitidas 
1.000.000 de mensagens que equivalem a 1.846.000 bit/seg. 
 
2 – Qual é a entropia de uma fonte de 4 símbolos com distribuição de probabilidade 
P={0,5;0,3;0,15;0,05}? 
 
bits
mH
647596,1216,04105,0521,05,0
)05,0/1(log05,0)15,0/1(log15,0)3,0/1(log3,0)5,0/1(log5,0)( 2222
=++++=
=+++=
 
 
5 – Codificação da fonte. 
 
 
 
 Figura 2 – Modelo para codificação de fonte. 
 
 Se alguns símbolos-fonte forem conhecidos como mais prováveis do que outros, então 
poderemos explorar essa característica na geração de um código da fonte atribuindo palavras-
código breves a símbolos freqüentes e palavras-código longas a símbolos-fonte raros. Como 
exemplo, citamos o código Morse onde à letra E, de ocorrência mais freqüente, é atribuído a 
palavra-código ( . ) e à letra Q, de ocorrência menos freqüente, é atribuído a palavra-código 
(--. --). 
 Admitindo que a palavra-código atribuída ao símbolo mi pelo codificador tenha um 
tamanho Li , medido em bits. Definimos o tamanho médio da palavra-código, L, do codificador 
da fonte como: 
 
 i
n
i
i LPL ∑
=
=
1
 
Teoria da Informação/Clauberto Vidal. Pág.3/7 
 Que representa o número médio de bits por símbolo-fonte no processo de codificação da 
fonte. 
A informação média por mensagem é a entropia bitsPPmH i
n
i
i 2
1
log)( ∑
=
−=
Para uma transmissão de N mensagens a partir da fonte teremos : )(mNHLN =
 
Dada uma fonte discreta sem memória (uma fonte sem memória implica que cada 
mensagem emitida é independente das mensagens anteriores), com entropia H(m), o tamanho 
médio da palavra-código L corresponde a: 
)(mHL ≥ 
De acordo com o teorema da codificação da fonte, a entropia H(m) representa um limite 
fundamental ao número médio de bits por símbolo da fonte necessário para representar uma 
fonte discreta sem memória no sentido de que ele pode se tornar tão pequeno quanto à 
entropia H(m), mas não menor do que ela. 
A eficiência de um codificador de fonte pode ser descrita como: 
 
 L
mH )(=η 
 
Exemplo. 
 Seja uma fonte de quatro símbolos A={a,b,c,d} que possuem probabilidades 
P={0,5;0,3;0,15;0,05}. Seja C um codificador que mapeia os símbolos de A em cadeias de 
dígitos binários {0,10,110,111} respectivamente. Qual é o número médio de dígitos binários por 
símbolo? Qual é a eficiência do codificador? 
O número médio de bits por símbolo é dado por, =i
n
i
i LPL ∑
=
=
1
 == 
 = 0,5X1+0,3X2+0,15X3+0,05X3=1,7 bits 
 
A entropia da fonte é dada por, 
 
bits
bitsPPmH i
n
i
i
6477,1)05,0log05,015,0log15,03,0log3,05,0log5,0(
log)(
2222
2
1
=+++−=
=−= ∑
=
 
A eficiência é dada por %977,1
6477,1)( ===
L
mHη 
 
 
 
 
 
 
Teoria da Informação/Clauberto Vidal. Pág.4/7 
 
Exemplo. 
 
 Repetir o exemplo anterior para a cadeia de dígitos binários {00, 01, 10,11}. 
 
 
bitsLPL i
n
i
i 2
1
== ∑
=
 
 %4,822
6477,1)( ===
LmHη 
 
6 – Codificação de Huffman. 
 Se desejarmos codificar cada mensagem da fonte diretamente sem usar seqüências 
longas, então, em geral, o tamanho médio da palavra-código por mensagem será maior do que 
a entropia H(m). Na prática, não é desejável usar seqüências longas, porque causam atraso na 
transmissão. 
 
 O código de Huffman é ótimo no sentido de que o número médio de dígitos binários 
necessário para representar o símbolo da fonte é mínimo. 
 
 Vamos usar o código de Huffman com uma fonte que produz oito símbolos: 
P(m1) = 0,50 ;P(m2) = 0,02 ;P(m3) = 0,03; P(m4) = 0,04 ;P(m5) = 0,10 ;P(m6) = 0,04 ;P(m7) 
= 0,12; P(m8) = 0,15. 
 
 Passos a seguir para construir a árvore do código Huffman: 
 
 1 - Ordenar as mensagens por ordem decrescente de probabilidades. 
 
m1 m8 m7 m5 m4 m6 m3 m2 
 
3 - Agrupar as duas mensagens com as probabilidades mais baixas e somar estas 
 probabilidades. 
Agrupamos m2 e m3 no nó a, cuja soma de probabilidades dá 0,05. De um conjunto de 
oito probabilidades passamos a ter um conjunto de 6+1=7 probabilidades. 
 
 3 - Repetir o passo anterior para o novo conjunto de probabilidades, até chegar à raiz da 
árvore. 
 
 3.1 - Agrupamos m4 e m6 no nó b, cuja soma de probabilidades dá 0,08. De um 
conjunto de sete probabilidades passamos a ter um conjunto de seis probabilidades: 0,50; 0,15; 
0,12; 0,10; 0,08 (nó b) e 0,05 (nó a). 
 
 3.2 - Agora agrupamos os nós a e b, produzindo o nó c. Depois agrupamos m5 e m7, 
produzindo o nó d, e assim por diante, gerando os nós e e f e chegando finalmente à raiz. 
 
Teoria da Informação/Clauberto Vidal. Pág.5/7 
4 - Da copa para a raiz arbitrar o bit 1 (ou 0) para os ramos que partem do nó de menor 
probabilidade e o bit 0 (ou 1) para os que partem do outro nó. 
 
Por exemplo, ao ramo que vai do nó a para o nó c atribuamos-lhe o bit 1. 
 
5 - Determinar as palavras de código percorrendo a árvore da raiz para a copa. 
 
Por exemplo, ao símbolo m7 corresponde a palavra de código binária 110. 
 
 
A entropia da fonte vale H(m) = 2,21 bits/símbolo e L=2,26. Se tomássemos palavras de 
código de igual comprimento necessitaríamos de 3 bits/símbolo. Assim bastou tomar 2,26 
bits/símbolo. 
 
 Æ Eficiência = 2,21/2,26=97,3% 
 
Árvore do exemplo de código de Huffman binário. 
 
 
 
 
 
 
 
Teoria da Informação/Clauberto Vidal. Pág.6/7 
Exercícios. 
 
1 - Uma fonte emite sete mensagens com probabilidades 1/2,1/4,1/8,1/16,1/32,1/64 e 1/64 
respectivamente. 
A) Encontre a entropia da fonte; 
B) Obtenha o código binário de Huffman; 
C) Encontre o tamanho médio da palavra-código; 
D) Determine a eficiência. 
 
Resposta: 
A) H(m)=63/32 bits 
B) 
mensagens probabilidades Palavras-código 
m1 1/2 0 
m2 1/4 10 
m3 1/8 110 
m4 1/16 1110 
m5 1/32 11110 
m6 1/64 111110 
m7 1/64 111111 
 
C) L=63/32 bits 
 
D) Eficiência = 100 % 
 
2 – Uma fonte emite quatro mensagens com probabilidades 0,5;0,3;0,1; e 0,1, 
respectivamente. 
 
A) Encontre a entropia da fonte; 
B) Obtenha o código binário de Huffman; 
C) Encontre o tamanho médio da palavra-código; 
D) Determine a eficiência. 
 
Respostas: 
 
A) H(m)= 1,69 bits. 
 
B) 
 
mensagens probabilidades Palavras-código 
m1 0,5 0 
m2 0,3 10 
m3 0,1 110 
m4 0,1 111 
 
C) L= 1,7 bits. 
D) Eficiência = 1,69/1,7 = 99,2 % 
 
 
 
Teoria da Informação/Clauberto Vidal. Pág.7/7