Teoria da Informação:
o legado de Shannon
Carlos Salema
3/2/2005
Academia das Ciências
1
Índice









3/2/2005
Introdução
Definição e medida da informação
Informação do sinal analógico
O sistema de comunicação
Capacidade do canal binário
Transmissão digital
Capacidade do canal analógico
Codificação
Conclusões
Academia das Ciências
2
Introdução
Claude Shannon
• A mathematical theory of communication,
Bell System Technical Journal, Vol. 27,
1948, pp.379—423 e pp. 623—656
• Probability of error for optimal codes in a
gaussian channel, Bell System Technical
Journal, Vol 38 (1959), pp. 611—656.
3/2/2005
Academia das Ciências
3
Introdução
Harry Nyquist
Certain Topics in telegraph transmission theory,
Transactions of the AIEE, Vol. 47, Abril 1928, pp.
617-644
Ralph Hartley
Transmission of Information, Bell System
Technical Journal, Julho 1928, pp. 535—564
3/2/2005
Academia das Ciências
4
Introdução
Dolinar, S., Divsalar, D. e Pollara, F.
Code Performance as a Function of Block Size,
TMO Progress Report, Maio 1998.
3/2/2005
Academia das Ciências
5
Definição e medida da informação
Informação é qualquer mensagem enviada
pela fonte ao destinatário e que este só pode
conhecer recebendo-a ou “adivinhando-a”.
3/2/2005
Academia das Ciências
6
Definição e medida da informação
Se for p a probabilidade do destinatário
“adivinhar” a mensagem a informação I é:
1 
I  log2    log2 p
p 
bit
A informação mede-se em dígitos binários,
ou bits (do inglês binary digits, proposto por
J.W. Tukey)
3/2/2005
Academia das Ciências
7
Definição e medida da informação
Sejam i = 1, 2, …, n mensagens independentes,
com probabilidades associadas pi .
A informação I do conjunto de mensagens é:
 n

1

I  log2 


p
 i1 i 

3/2/2005
n
 1 
log2  
pi 

i1

Academia das Ciências
n
I
i
i1
8
Definição e medida da informação
Exemplo1:
Qual a informação associada a uma carta
retirada aleatoriamente de um baralho ?
1
p
52
3/2/2005
1 
I  log2   log2 52  5.7 bit
p 
Academia das Ciências
9
Definição e medida da informação
Exemplo 2:
Qual a informação num texto de 2000
caracteres, em língua desconhecida para o
receptor ?
1
I
p
256
3/2/2005
2000
1 
log2   2000log2 256  16 000bit
p 

i1

Academia das Ciências
10
Definição e medida da informação
Se os caracteres não forem equiprováveis, a
quantidade de informação da mensagem é dada
por:
n
I

i1

3/2/2005
n
 1 
pi log2    pi log2 pi 
pi  i1

Academia das Ciências
11
Informação do sinal analógico
Qual a informação de um sinal analógico ?
s(t)
t
3/2/2005
Academia das Ciências
12
Informação do sinal analógico
Se o sinal analógico tiver uma frequência limite
superior b pode ser reconstituído a partir de 2b
amostras por segundo.
Se cada amostra for quantificada em n níveis
(equiprováveis) a informação, por amostra, vale:
n

I amostra  
i1
3/2/2005
1 
1
log2   log2 n bit
n 
n
Academia das Ciências
13
Informação do sinal analógico
A informação do sinal analógico por unidade
de tempo vale:
I sinal  2b log2 n bit/s

3/2/2005
Academia das Ciências
14
Informação do sinal analógico
Exemplo 3:
Qual a informação do sinal de voz ?
Se o sinal de voz for limitado a 3400 Hz, a
amostragem for feita a 2x4 kHz e as amostras
quantificadas com 256 níveis, a informação é:
I voz  2 4  log2 256  64 kbit/s
3/2/2005
Academia das Ciências
15
Informação do sinal analógico
A voz não é um sinal contínuo, há pausas
entre palavras e entre-sílabas e nem todos os
níveis de discretização são equiprováveis.
A informação do sinal de voz tal qual foi
descrito, tem irrelevâncias e redundâncias.
Com um código apropriado consegue-se
transmitir o sinal de voz com qualidade
praticamente igual à conseguida com o
processo descrito com apenas 8 a 11 kbit/s
3/2/2005
Academia das Ciências
16
O sistema de comunicação
Fonte
Emissor
Canal
Ruído
3/2/2005
Receptor
Academia das Ciências
Destinatário
17
O sistema de comunicação
A fonte
Se a fonte usar um alfabeto com n símbolos
cada um com probabilidade pi , a informação
(ou entropia) por símbolo é:
n
 p log p 
I 
i
2
i
bit/símbolo
i1
3/2/2005
Academia das Ciências
18
O sistema de comunicação
A fonte binária
Seja uma fonte binária e sejam p e q as probabilidades dos símbolos (0 e 1).
A informação por símbolo da fonte é:
I fonte   p log2 (p)  q log2 (q)
3/2/2005
Academia das Ciências
bit/símbolo
19
O sistema de comunicação
Ifonte
p
I fonte   p log2 (p)  q log2 (q)
3/2/2005
Academia das Ciências
bit/símbolo
20
O sistema de comunicação
O canal binário
Um canal transmite à velocidade de v (bit/s)
mas alguns bits são recebidos com erro (taxa
de erros ber).
Qual a velocidade máxima c de transmissão
sem erros (capacidade do canal) ?
3/2/2005
Academia das Ciências
21
A capacidade do canal binário
A informação que chega ao receptor não é:
I destino  v (1  ber)
bit/s
Se fosse, para ber = 0.5

I destino  0.5 v
bit/s
Mas a informação que chega ao receptor é
nula, uma vez que a probabilidade de errar
é igual à probabilidade de acertar !
3/2/2005
Academia das Ciências
22
A capacidade do canal binário
A informação, por símbolo transmitido, que
chega ao receptor, é dada por:
I destino  I fonte  I erros canal
em que
I fonte   p log2 (p)  q log2 (q)  1 bit/símbolo

com q = 1—p
3/2/2005
Academia das Ciências
23
A capacidade do canal binário
Admitindo que ambos os símbolos são afectados de igual modo a informação perdida
devido aos erros, em bit/símbolo, é:
I erros canal  (1ber) log2 (1 ber) ber log2 (ber)
3/2/2005
Academia das Ciências
24
A capacidade do canal binário
A capacidade do canal (em bit/s) é
C  v  1 (1 ber) log2 (1 ber)  ber log2 (ber)
Agora para ber = 0.01 vem C ≈ 0.919v e
para ber = 0.5 vem, correctamente, C = 0.
3/2/2005
Academia das Ciências
25
A capacidade do canal binário
c/v
ber
3/2/2005
Academia das Ciências
26
A capacidade do canal binário
Qual a relação entre a largura de banda b e
a capacidade do canal ?
Se o canal tiver uma largura de banda b (em
Hz) pode transmitir 2b sinais binários, logo
a capacidade C, em bit/s, é:
C  2b 1 (1 ber) log2 (1 ber)  ber log2 (ber)
3/2/2005
Academia das Ciências
27
A capacidade do canal binário
Como é que um canal com uma taxa de erros
ber pode transmitir sem erros ?
Recorda-se que a capacidade do canal é a
velocidade máxima de transmissão sem erros
3/2/2005
Academia das Ciências
28
A capacidade do canal binário
Codificação
O emissor transforma o sinal da fonte noutro
sinal adicionando-lhe bits suplementares que
permitem detectar e corrigir os erros da
transmissão.
O receptor recebe o sinal do canal, corrige-o,
usando os bits suplementares, e entrega-o ao
destinatário
3/2/2005
Academia das Ciências
29
Transmissão digital
Considere-se um canal analógico, com
ruído aditivo branco e gaussiano, no qual
se pretende transmitir um sinal em código
polar, isto é um sinal que toma os valores
s = + a e s = – a.
3/2/2005
Academia das Ciências
30
Transmissão digital
À saída do canal, o ruído de amplitude x,
sobrepõe-se ao sinal. A reconstituição do sinal,
é feita com o seguinte algoritmo:
• Se s + x ≥ 0 admite-se que o sinal transmitido
foi +a
• Se s + x < 0 admite-se que o sinal transmitido
foi –a
3/2/2005
Academia das Ciências
31
Transmissão digital
Existe erro quando:
• se transmite s = + a e se recebe s + x < 0
• se transmite s = – a e se recebe s + x ≥ 0
3/2/2005
Academia das Ciências
32
Transmissão digital
Como x tem uma distribuição de amplitudes
gaussiana com média nula e desvio s
perro
x2

1
2
2
s
p
e
dx  q
 s 2

a


a
x2

1
2
2
s
e
dx
s 2
em que p é a probabilidade de transmitir
s = +a e q = 1– p a probabilidade de
transmitir s = – a.
3/2/2005
Academia das Ciências
33
Transmissão digital
Tomando p = q = 1/2 vem:
perro
 a 
1
 Erfc

2
s 2 
em que Erfc é a função complementar de erro.

3/2/2005
Academia das Ciências
34
Transmissão digital
É habitual representar a probabilidade de erro
em termos da energia média de bit eb e da
densidade de ruído por unidade de largura de
banda n0.
Se o sinal tiver a forma de um pulso rectangular, a energia média de bit é:
eb  a
3/2/2005
2
Academia das Ciências
35
Transmissão digital
Como a potência associada ao ruído é :
n



px x 2 dx  s 2
a densidade de ruído por unidade de largura
de 
banda é:
s2
n0 
3/2/2005
2b
Academia das Ciências
36
Transmissão digital
pelo que a probabilidade de erro vem:
perro
 e 
1
b
 Erfc



2
n
 0 
Recordando que

3/2/2005
e 
Eb
 10log10  b 
N 0 dB
n 0 
Academia das Ciências
37
Transmissão digital
perro
Eb/N0 [dB]
3/2/2005
Academia das Ciências
38
A capacidade do canal analógico
Para determinar a capacidade do canal analógico, começa-se por calcular a entropia correspondente à tensão de ruído, admitindo que
o seu espectro de potência é branco e limitado
superiormente a b, e que a estatística de
amplitudes é gaussiana, com média nula e
desvio padrão s.
3/2/2005
Academia das Ciências
39
A capacidade do canal analógico
O ruído pode ser descrito por 2b amostras,
cada uma das quais tem uma distribuição de
amplitude gaussiana.
Como a informação associada a uma fonte
contínua é:
I contínua  
3/2/2005



px log2 pxdx
Academia das Ciências
40
A capacidade do canal analógico
Uma vez que o ruído é gaussiano:
x2

1
2
px 
e 2s
s 2
a entropia por amostra de ruído vem:

I amostra
3/2/2005


2  1
2 
 log2  2 e s  log2  2 e s 

 2


Academia das Ciências
41
A capacidade do canal analógico
Atendendo a que a potência associada ao
ruído é:
n



px x 2 dx  s 2
Obtém-se a entropia associada às 2b
amostras
de
ruído:

I ruído  b log2 2 e n
3/2/2005
Academia das Ciências
42
A capacidade do canal analógico
A entropia de um sinal (analógico) com
potência s a que se adiciona ruído com
potência n, tem uma entropia dada por:
I sinal maisruído  b log2 2 e s  n

3/2/2005
Academia das Ciências
43
A capacidade do canal analógico
A capacidade do canal analógico é a
diferença entre a entropia do sinal mais
ruído e a entropia do ruído:
 s 
c  b log2 1  bit/s
 n 
3/2/2005
Academia das Ciências
44
A capacidade do canal analógico
A capacidade do canal telefónico, com
3.4 kHz com uma relação sinal-ruído de
S/N = 40 dB (boa qualidade), ou seja,
s/n= 104 é C = 45.2 kbit/s
3/2/2005
Academia das Ciências
45
A capacidade do canal analógico
Retomando a capacidade do canal analógico
 s 
c  b log2 1 bit/s
 n 
Como s = eb fb (em que fb é a frequência de
bit) e n = n0 b a capacidade c vem:

3/2/2005
 e f 
c  b log2 1 b  b bit/s
 n 0 b 
Academia das Ciências
46
A capacidade do canal analógico
fb
eb
c

bit/s
loge 2 n 0
eb f b

 1
n0 b
fb  c

eb
 loge 2
n0

3/2/2005
ou

Academia das Ciências
Eb
 1.6 dB
N0
47
A capacidade do canal analógico
perro
?
Eb/N0 (dB)
3/2/2005
Academia das Ciências
48
Codificação
A solução é a codificação: introdução de bits
adicionais na mensagem que permitem detectar
e corrigir erros.
Para manter a potência do sinal há que reduzir a
energia média por bit o que, por si só aumenta a
probabilidade de erro de bit.
A troca compensa como se irá demonstrar.
3/2/2005
Academia das Ciências
49
Codificação
Os códigos caracterizam-se por dois inteiros,
(n,k).
Para cada k símbolos de entrada o código
produz n símbolos de saída.
k
Designa-se por razão do código rc 
n
Na prática 1/2 ≤ rc ≤ 1
3/2/2005

Academia das Ciências
50
Codificação
O ganho de codificação depende:
• da razão do código rc, aumentando quando
rc diminui;
• do valor de k, aumentando quando k
aumenta.
3/2/2005
Academia das Ciências
51
Codificação
O limite mínimo de eb/n0 pode ser escrito em
termos da razão do código.
 e c 
 s 
c  b log2 1  b log2 1 b 
 n 
 n 0 b 

3/2/2005
 e c 
c 1
 log2 1 b 
2b 2
 n 0 b 
Academia das Ciências
52
Codificação
Substituindo c em termos da razão de código
2rc max

eb 
 log2 1  2rc max

n 0 

2rcmax
eb 2
1

n0
2rc max


3/2/2005
2rcmax

Eb
2
1 

 10log10 
 2r

N0
c


max
Academia das Ciências
53
Codificação
Eb/N0 [dB]
rc
3/2/2005
Academia das Ciências
max
54
Codificação
Para a mesma razão de código, um código é
tanto mais eficaz quanto maior for o comprimento n do bloco de dados codificados.
Com códigos que detectem e corrijam todos
os erros até 1/7 do seu comprimento a
probabilidade de um bloco com erros é:
n
pbloco 

n
i 1
7
3/2/2005
n  i
ni
p
1
p
  bit 
bit 
i 
Academia das Ciências
55
Codificação
pbloco
n=7
pbit
n = 70
3/2/2005
n = 700
Academia das Ciências
56

Codificação
Código
Informação
u1 
 
u 2 

u
 
 
u k 

3/2/2005
Código de bloco
x  G  umod 2

Academia das Ciências
x1 
 
x 2 

x
 
 
x n 
57
Codificação
Código de repetição (3,1)
1
 
G  1

1

Cada bit é repetido 3 vezes e, na recepção, a
decisão é por maioria. A probabilidade
de erro

de bloco é:
3 2
pbloco   pbit 1 pbit 
2
3/2/2005
Academia das Ciências
58
 3/2/2005
Codificação
Código de Hamming (7,4)
1

0
0

G  0
1

0

1
0

0
0

1
0

1 1 1
1 0 1

0
1
0
0
1
0
0
1
0
1
1
 
1
0
 
x  G  umod 2  0
0
 
1

0

1
 
1

u
0
 
0


Academia das Ciências
59
Codificação
O código de Hamming (7,4) detecta e corrige
todos os erros simples (1 bit), pelo que a
probabilidade de erro de bloco é
7
pbloco 

i 2
3/2/2005

7 i
7i
 pbit 1 pbit 
i 
Academia das Ciências
60
Codificação
Com o código polar para eb/n0 = 7 tem-se
pbit ≈ 9.1·10-5 pelo que a probabilidade de um
bloco de 4 bits ter 1 ou mais bits errados é
pbloco = 3.7·10-4.
Com o código de Hamming (7,4) com eb/n0 =
4 vem pbit ≈ 2.3·10-3 e a probabilidade de um
bloco de 7 bits, com 4 de informação ter 1 ou
mais bits errados é pbloco = 1.1·10-4
3/2/2005
Academia das Ciências
61
Codificação
O código de Hamming (7,4) está longe do
limite de Shannon, o que não é de espantar
dado o baixo comprimento do bloco de código.
Em 1959 Shannon deduziu expressões para o
ganho de codificação máximo, em função do
comprimento do bloco de código.
Em 1998, Dolinar, S. et al., calcularam estes
limites para comprimentos de bloco curtos.
3/2/2005
Academia das Ciências
62
Codificação
3/2/2005
Academia das Ciências
63
Conclusões
Shannon:
• definiu e criou uma medida para informação
• estabeceu o limite para a velocidade de
transmissão da informação sem erros,
• estabeleceu limites para o ganho de codificação,
função da razão do código e do comprimento do
bloco.
3/2/2005
Academia das Ciências
64
Conclusões
A investigação actual procura criar códigos
que se aproximem tanto quanto possível do
limite de Shannon
3/2/2005
Academia das Ciências
65
Conclusões
Muito obrigado pela
vossa atenção
3/2/2005
Academia das Ciências
66