O teorema da codificação de canal

1.3.
Teorema da codificação de canal
•
Ritmo de informação
•
Teorema da codificação de canal
Teoria da Informação
Teorema da codificação de canal
1
Ritmo (ou taxa) de informação
• Se a fonte de entropia H(X) emitir uma sequência de n 1 símbolos a
informação total a ser transferida é de nH ( X ) bits.
• Se a fonte produzir r símbolos/s a duração da sequência de n símbolos é
n/r segundos.
• Portanto, a informação deve ser transferida à razão média de:
R=
informação total nH ( X )
=
= rH ( X ) bits/s
duração total
nr
Esta é a taxa de informação da fonte.
Se a fonte produzir símbolos com diferentes durações τ i (segundos) o ritmo,
ou taxa, de informação pode ser calculado alternativamente como
R=
H (X )
τ
bits/s
em que τ é a duração média de cada símbolo,
M
τ = P1τ1 + P2τ 2 + ... + PM τ M = ∑ Piτ i .
i =1
Teoria da Informação
Teorema da codificação de canal
2
O teorema da codificação de canal
(aplicado a canais discretos sem memória)
A entropia representa a informação esperada por cada símbolo de fonte.
• Se tivermos duas fontes com iguais entropias, aquela que produzir mais
símbolos por unidade de tempo vai colocar mais exigências no sistema de
comunicações.
(imagine duas pessoas a ler o mesmo texto escrito numa língua que domina mal.
Uma delas lê depressa. Qual é a que entende melhor?)
• O ritmo de informação mede a quantidade de informação produzida
num certo intervalo de tempo.
• Existem limitações físicas fundamentais à transferência de informação
(ruído, largura de banda, …), que se reflectem na capacidade do canal:
• A capacidade do canal (em bits/s) mede a quantidade de informação
que um canal pode transferir por unidade de tempo.
Shannon relacionou estes dois conceitos através do teorema da codificação
de canal, também chamado Teorema Fundamental da Teoria da
Informação:
Dado um canal de capacidade C e uma fonte com ritmo de
informação R, então se R ≤ C existe uma técnica de codificação
tal que a saída da fonte pode ser transmitida através do canal
com uma frequência arbitrariamente pequena de erros, apesar
da presença de ruído.
Se R > C, não é possível a transmissão sem erros.
Teoria da Informação
Teorema da codificação de canal
3
O teorema da codificação de canal
aplicado a canais discretos sem memória
(formulação alternativa)
Teorema:
“Uma fonte X de entropia H(X) produz símbolos à razão de um símbolo por
cada Ts segundos. Consideremos um canal discreto sem memória de
capacidade Cs (bits/símbolo!) e que seja usado uma vez em cada Tc
segundos. Então, se
H ( X ) Cs
≤
,
Ts
Tc
existe uma técnica de codificação dos símbolos da fonte que permite que os
símbolos transmitidos através do canal possam ser recuperados com uma
probabilidade de erro arbitrariamente pequena.
Se, pelo contrário,
H ( X ) Cs
, então não é possível transmitir os símbolos e
>
Ts
Tc
recuperá-los com uma probabilidade de erro arbitrariamente pequena.”
Conversão de Cs (bits/símbolo) em C (bits/s):
C=
Teoria da Informação
Cs
Tc
Teorema da codificação de canal
4
Aplicação do “Teorema da Codificação do
Canal” a um canal binário simétrico
Considere-se uma fonte binária a gerar símbolos equiprováveis de duração
Ts segundos, ou seja, a produzi-los à taxa de r = 1 Ts símbolos por segundo.
Sendo os símbolos binários equiprováveis, a entropia da fonte vale H ( X ) = 1
bit/símbolo e a taxa de informação da fonte é R = rH ( X ) = 1 Ts bits/s.
1 símbolo em
Ts segundos
1 dígito binário em
Tc segundos
capacidade por unidade
de tempo = Cs/Tc bits/s
(r=1/Ts)
Fonte
binária
Codificador de
canal binário
rH(X) bits/s
Canal binário
simétrico
Rc=k/n
O codificador (de canal!) produz um símbolo binário em cada Tc segundos, o
qual é transmitido através de um canal binário simétrico (BSC) – que,
portanto, é usado uma vez em cada Tc segundos. Assim, a capacidade do
canal por unidade de tempo é C = Cs Tc bits/s.
De acordo com o teorema da codificação do canal, terá de ser
H ( X ) Cs
⇒
≤
Ts
Tc
Mas
1 Cs
≤
Ts Tc
⇒
Tc
≤ Cs
Ts
Tc
= Rc (taxa do código, ver a seguir), pelo que
Ts
Rc ≤ Cs
Como a capacidade do canal BSC é Cs = 1 − Ω( p) :
Rc ≤ 1 − Ω( p)
Teoria da Informação
(canal BSC)
Teorema da codificação de canal
5
Aplicação do “Teorema da Codificação do
Canal” a um canal binário simétrico
(contin.)
Porque é que
Tc
= Rc ?
Ts
Antes da codificação
Ts
k=4
Duração do bloco: 4Ts
Tc
n=7
Duração do bloco: 7Tc
Depois da codificação
À razão
k
= Rc chama-se taxa do código.
n
Como a duração dos blocos é a mesma:
kTs = nTc
ou, neste caso,
4Ts = 7Tc ⇒ Tc Ts = 4 7 = Rc
Em resumo, temos duas maneiras de exprimir o teorema da codificação de
canal:
• Com a capacidade expressa em bits/símbolo, Cs:
Rc ≤ Cs
• Com a capacidade expressa em bits/s, C:
R = rH ( X ) ≤ C
bits/s
Teoria da Informação
bits/símbolo
C = Cs Tc
Teorema da codificação de canal
6