3/2/2005 Academia das Ciências 1
Teoria da Informação: o legado de Shannon
Carlos Salema
3/2/2005 Academia das Ciências 2
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
Índice
3/2/2005 Academia das Ciências 3
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 4
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 5
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 6
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 7
Definição e medida da informação
Se for p a probabilidade do destinatário “adivinhar” a mensagem a informação I é:
I log21
p
log2 p
A informação mede-se em dígitos binários, ou bits (do inglês binary digits, proposto por J. W. Tukey)
bit
3/2/2005 Academia das Ciências 8
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 é:
I log21
pii1
n
log2
1
pi
i1
n
I i
i1
n
3/2/2005 Academia das Ciências 9
Definição e medida da informação
Qual a informação associada a uma carta retirada aleatoriamente de um baralho ?
p 1
52
I log21
p
log2 52 5.7 bit
Exemplo1:
3/2/2005 Academia das Ciências 10
Definição e medida da informação
Qual a informação num texto de 2000 caracteres, em língua desconhecida para o receptor ?
p 1
256
I log21
p
i1
2000
2000 log2 256 16 000 bit
Exemplo 2:
3/2/2005 Academia das Ciências 11
Definição e medida da informação
Se os caracteres não forem equiprováveis, a quantidade de informação da mensagem é dada por:
I pi log21
pi
pi log2 pi
i1
n
i1
n
3/2/2005 Academia das Ciências 12
Informação do sinal analógico
Qual a informação de um sinal analógico ?
t
s(t)
3/2/2005 Academia das Ciências 13
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:
Iamostra 1
ni1
n
log21
n
log2 n bit
3/2/2005 Academia das Ciências 14
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 15
Informação do sinal analógico
Exemplo 3:
Qual a informação do sinal de voz ?
Ivoz 24 log2 256 64 kbit/s
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 é:
3/2/2005 Academia das Ciências 16
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 17
O sistema de comunicação
Fonte Emissor
ReceptorDestina-tário
Canal
Ruído
3/2/2005 Academia das Ciências 18
O sistema de comunicação
Se a fonte usar um alfabeto com n símbolos
cada um com probabilidade pi , a informação
(ou entropia) por símbolo é:
I pi
i1
n
log2 pi bit/símbolo
A fonte
3/2/2005 Academia das Ciências 19
O sistema de comunicação
Seja uma fonte binária e sejam p e q as probabi-
lidades dos símbolos (0 e 1).
A informação por símbolo da fonte é:
I fonte p log2 (p) q log2 (q) bit/símbolo
A fonte binária
3/2/2005 Academia das Ciências 20
O sistema de comunicação
I fonte p log2 (p) q log2 (q) bit/símbolo
Ifonte
p
3/2/2005 Academia das Ciências 21
O sistema de comunicação
Um canal transmite à velocidade de v (bit/s)
mas alguns bits são recebidos com erro (taxa
de erros ber).
O canal binário
Qual a velocidade máxima c de transmissão
sem erros (capacidade do canal) ?
3/2/2005 Academia das Ciências 22
A capacidade do canal binário
A informação que chega ao receptor não é:
Idestino v (1 ber) bit/s
Se fosse, para ber = 0.5
Idestino 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 23
A capacidade do canal binário
A informação, por símbolo transmitido, que chega ao receptor, é dada por:
Idestino I fonte Ierros canal
I fonte p log2 (p) q log2 (q) 1 bit/símbolo
em que
com q = 1—p
3/2/2005 Academia das Ciências 24
A capacidade do canal binário
Admitindo que ambos os símbolos são afec-tados de igual modo a informação perdida devido aos erros, em bit/símbolo, é:
Ierros canal (1 ber) log2 (1 ber) ber log2 (ber)
3/2/2005 Academia das Ciências 25
A capacidade do canal binário
C v 1 (1 ber) log2 (1 ber) ber log2 (ber)
A capacidade do canal (em bit/s) é
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 26
A capacidade do canal binário
ber
c/v
3/2/2005 Academia das Ciências 27
A capacidade do canal binário
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)
Qual a relação entre a largura de banda b e a capacidade do canal ?
3/2/2005 Academia das Ciências 28
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 29
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 30
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 31
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 32
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 33
Transmissão digital
Como x tem uma distribuição de amplitudes gaussiana com média nula e desvio
perro p1
2
a e
x 2
2 2dx q
1
2a
e
x 2
2 2dx
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 34
Transmissão digital
Tomando p = q = 1/2 vem:
perro 1
2Erfc
a
2
em que Erfc é a função complementar de erro.
3/2/2005 Academia das Ciências 35
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 rectan-gular, a energia média de bit é:
eb a2
3/2/2005 Academia das Ciências 36
Transmissão digital
a densidade de ruído por unidade de largura de banda é:
n0 2
2b
n p x x 2dx
2
Como a potência associada ao ruído é :
3/2/2005 Academia das Ciências 37
Transmissão digital
perro 1
2Erfc
eb
n0
pelo que a probabilidade de erro vem:
Eb
N 0 dB
10 log10eb
n0
Recordando que
3/2/2005 Academia das Ciências 38
Transmissão digital
perro
Eb/N0 [dB]
3/2/2005 Academia das Ciências 39
A capacidade do canal analógico
Para determinar a capacidade do canal analó-
gico, começa-se por calcular a entropia cor-
respondente à 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
3/2/2005 Academia das Ciências 40
O ruído pode ser descrito por 2b amostras, cada uma das quais tem uma distribuição de amplitude gaussiana.
Icontínua p x log2 p x dx
A capacidade do canal analógico
Como a informação associada a uma fonte contínua é:
3/2/2005 Academia das Ciências 41
Iamostra log2 2 e 2
1
2log2 2 e 2
Uma vez que o ruído é gaussiano:
p x 1
2e
x 2
2 2
a entropia por amostra de ruído vem:
A capacidade do canal analógico
3/2/2005 Academia das Ciências 42
n p x x 2dx
2
Atendendo a que a potência associada ao ruído é:
A capacidade do canal analógico
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 43
I sinal mais ruído b log2 2 e s n
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:
A capacidade do canal analógico
3/2/2005 Academia das Ciências 44
A capacidade do canal analógico é a
diferença entre a entropia do sinal mais
ruído e a entropia do ruído:
c b log2 1s
n
bit/s
A capacidade do canal analógico
3/2/2005 Academia das Ciências 45
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
A capacidade do canal analógico
3/2/2005 Academia das Ciências 46
A capacidade do canal analógico
Retomando a capacidade do canal analógico
c b log2 1s
n
bit/s
Como s = eb fb (em que fb é a frequência de bit) e n = n0 b a capacidade c vem:
c b log2 1eb
n0
fb
b
bit/s
3/2/2005 Academia das Ciências 47
A capacidade do canal analógico
c fb
loge 2
eb
n0
bit/s
eb
n0
fb
b1
eb
n0
loge 2
Eb
N 0
1.6 dBou
fb c
3/2/2005 Academia das Ciências 48
A capacidade do canal analógico
perro
Eb/N0 (dB)
?
3/2/2005 Academia das Ciências 49
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 50
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.
Designa-se por razão do código
Na prática 1/2 ≤ rc ≤ 1
rc k
n
3/2/2005 Academia das Ciências 51
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 52
Codificação
c b log2 1s
n
b log2 1
eb c
n0 b
c
2b
1
2log2 1
eb c
n0 b
O limite mínimo de eb/n0 pode ser escrito em
termos da razão do código.
3/2/2005 Academia das Ciências 53
Codificação
eb
n0
2
2rcmax 1
2rcmax
Eb
N 0
10 log102
2rcmax 1
2rcmax
2rcmaxlog2 1 2rcmax
eb
n0
Substituindo c em termos da razão de código
3/2/2005 Academia das Ciências 54
Codificação
rcmax
Eb/N0 [dB]
3/2/2005 Academia das Ciências 55
Codificação
Para a mesma razão de código, um código é tanto mais eficaz quanto maior for o compri-mento 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 é:
pbloco n
i
in
71
n
pbiti 1 pbit n i
3/2/2005 Academia das Ciências 56
Codificação
pbit
pbloco
n = 7
n = 70 n = 700
3/2/2005 Academia das Ciências 57
Codificação
Informação Código
u
u1
u2
uk
x
x1
x2
xn
x G u mod 2
Código de bloco
3/2/2005 Academia das Ciências 58
Codificação
Código de repetição (3,1)
G 1
1
1
Cada bit é repetido 3 vezes e, na recepção, a decisão é por maioria. A probabilidade de erro de bloco é:
pbloco 3
2
pbit
2 1 pbit
3/2/2005 Academia das Ciências 59
Codificação
Código de Hamming (7,4)
G
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 1 0
0 1 1 1
1 1 0 1
x G u mod 2
1
1
0
0
0
1
0
u
1
1
0
0
3/2/2005 Academia das Ciências 60
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 é
pbloco 7
i
i2
7
pbiti 1 pbit 7 i
3/2/2005 Academia das Ciências 61
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 62
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 63
Codificação
3/2/2005 Academia das Ciências 64
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 65
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 66
Conclusões
Muito obrigado pela vossa atenção