COMUNICAÇÕES DIGITAIS Livro Texto: “Communication Systems

COMUNICAÇÕES DIGITAIS
Livro Texto: “Communication Systems”, 4TH Edition Simon Haykin – John Wiley &
Sons, Inc.
1
1. Introdução
Exemplo:
Nível (Volts)
0
1
2
3
4
5
6
7
Codificação
000
001
010
011
100
101
110
111
2
Probabilidade
0,05
0,10
0,20
0,30
0,15
0,10
0,05
0,05
Probabilidade
0,30
0,20
0,15
0,10
0,10
0,05
0,05
0,05
Nível
3
2
4
1
5
0
6
7
Mapeamento realizado:
011
⇒
00
010
⇒
01
100
⇒
100
001
⇒
101
101
⇒
1100
000
⇒
1101
110
⇒
1110
111
⇒
1111
Codificador de fonte: n = 3 bits ⇒ n = 2,75 bits
Acrescentar bit de paridade: No codificador de canal
0 →
Modulador 
1 →
25 KHz
31 KHz
3
Codificação Fonte
00
01
100
101
1100
1101
1110
1111
4
9. Limites Fundamentais de Desempenho
9.1 – Incerteza, Informação e Entropia
Uma fonte produz K símbolos independentes uns dos outros
S = {s0, s1, s2, ..., sk-1}
Cada símbolo tem uma probabilidade de saída (aparecimento) igual a pk,
k = 0, ..., k = 1. Quando isso acontece chamamos a fonte de “fonte discreta sem memória”.
9.1.1 – Medida da Informação
Informação e incerteza estão relacionadas.
Exemplo:
X = “A lua gira em torno da terra”. Este tipo de informação não traz nenhuma incerteza.
Logo: P(x) → 1. Incerteza → 0
Y = “A lua se aproxima da terra”. Este tipo de informação traz grande incerteza. Logo:
P(y) → 0. Incerteza → ∞
Então
I(s k ) = log 2
define-se
a
quantidade
de
1
, bits
pk
Obs.: A unidade é bits porque se usa log na base 2.
Satisfazendo a:
5
informação
(I)
como
sendo:
1
pk = 1 → I(sk) = 0
2
0 ≤ pk ≤ 1 → I(sk) ≥ 0
Um evento ou traz alguma ou nenhuma informação, mas não traz perda (I < 0) de
informação.
> Is k
3
Se pi < pk então I s
j
4
se si e sj são independentes então a informação devida a Si Sj (Si seguida de Sj ou viceversa) é dada pela soma das informações: I(Si Sj) = I(Si) + I(Sj)
9.1.2 – Entropia da Fonte: H(S)
É a média de I(si), ou seja, é a informação média proveniente de uma fonte sem
memória
k -1
1
H(S) = E[I(s)] = ∑ p k log 2
= - ∑ p k log 2 p k
pk
k =0
k =0
k -1
Propriedade: 0 ≤ H(S) ≤ log2K onde K é o número de letras do alfabeto
1
H(S) = 0 se pi = 1 (um único evento)
2
H(S) = log2 K se pk =
1
K
para k = 0, 1, 2, ..., K-1 (igualmente prováveis)
9.1.3 – Exemplo Fonte Binária sem Memória
Dois símbolos a e b ou 0 e 1 com probabibilidades p e 1-p
6
H(s) = p log
1
1
+ (1 - p) log
p
1- p
9.1.4 – Entropia de Blocos de Símbolos de uma Fonte sem Memória
S = {S0, S1, …, SK-1} símbolos independentes. Formam-se n símbolos justapostos.
Entropia do agrupamento: H(Sn) = n H(s)
Exemplo:
S = {S0, S1, S2}
H(s) =
p(S0) = ¼
p(S1) = ¼
p(S2) = ½
1
 1  1
 1  1
 1  3
log 2   + log 2   + log 2   = bits
4
 1/4  4
 1/4  2
 1/2  2
Agrupamentos 2 a 2:
AR 32 = 32 = 9
S = {σ 0 σ 2 σ 3 L σ 8 }
7
σi
σ0
σ1
σ2
σ3
σ4
σ5
σ6
σ7
σ8
Sk Sj
S0S0
S0S1
S0 S2
S1S0
S1S1
S1S2
S2S0
S2S1
S2S2
p(σi)
1/16
1/16
1/8
1/16
1/16
1/8
1/8
1/8
1/4
8
H(S2 ) = ∑ p(σ i ) log
i=0
1
= 3 bits ⇒ H(s 2 ) = 2H(s)
p(σ i )
9.2 – Codificação da Fonte
•
Codificação eficiente depende de códigos de comprimento variável porque os pk’s são
diferentes
•
Códigos eficientes devem ser unicamente decodificáveis e de preferência, instantâneos
•
Comprimento médio de código L =
K-1
∑l
k =0
k
p k bits/símbolo.
onde lk é o comprimento do código da letra sk
•
Eficiência η:
η =
L min
L
9.3 – O Primeiro Teorema de Shannon
L min = H(S)
ou seja,
H(S) ≤ L
ainda:
η =
H(S)
L
Códigos não prefixos: Nenhum é prefixo de outro
8
Exemplo:
Símbolo da
Probabilidade de
Código I
Código II
Código III
fonte
ocorrência
s0
0,5
0
0
0
s1
0,25
1
01
10
s2
0,125
00
011
110
s3
0,125
11
0111
111
Não unicamente decodificável: Código I
Unicamente decodificáveis: Códigos II e III
Condição códigos não prefixo: Código III
Código não prefixo ⇒ Árvores de código
Código III:
Um código binário com condição de código não prefixo satisfaz à desigualdade de
Kraft-McMillan:
K -1
-l
∑ 2 k ≤1
k =0
onde lk são os comprimentos dos códigos de cada letra sk, k = 0, …, K-1.
Outros códigos não prefixo podem ou não satisfazer a essa condição.
9
Uma fonte discreta sem memória com entropia H(S) possui código com condição
de não prefixo cujo comprimento médio L satisfaz a:
H(S)
≤ L ≤ H(S) + 1
pk = 2-lk
Se
então
L = H(S) = Lmin
Para blocos de símbolos sn, tem-se: H(Sn) = n H(S) com comprimento médio por n
símbolos dado por Ln. Então:
H(Sn)
≤ Ln ≤ H(Sn) + 1
como H(Sn) = n H(S), tem-se:
n H(S) ≤ Ln ≤ n H(S) + 1
H(S)
≤
Ln
n
≤ H(S) + 1/n ,
lim L n /n → H(s)
n →∞
Ln/n é o comprimento médio por símbolo
(O código fica com rendimento igual a 100%).
9.4 – Método de Codificação sem perdas
9.4.1 – Método de Fano
Arrumam-se as letras em ordem decrescente de probabilidade.
Divide-se em subgrupos cujas probabilidades estejam próximas de 2-k
(k = 1, 2, …)
ou seja, inicialmente divide-se em dois subgupos de probabilidade 0,5 ;
depois em subgrupos de probabildade 0,25 e assim por diante.
Atribui-se a cada subgrupo o dígito 0 e 1.
10
Exemplo: S = (A,B,C,D,E,F) ⇒ P = {0.30, 0.10, 0.20, 0.25, 0.10, 0.05}
A
0,30
D
0,25
C
0,20
B
0,10
E
0,10
F
0,05
0
0
1
0
0
1
1
0
1
A
0.30
0
0
D
0.25
0
1
C
0.20
1
0
B
0.10
1
1
0
E
0.10
1
1
1
0
F
0.05
1
1
1
1
1
L = 2x0.3+2x0.25+2x0.20 + 3x0.10 + 4x0.10 + 4x0.5 = 2.4
k =5
H(S) = ∑ p k log
k =0
1
= 2,366
pk
H(S) < L
9.4.2 – Código de Huffman (Codificação Próxima da Ótima) para Códigos Binários
Arrumam-se as letras em ordem decrescente de probabilidade.
Combinam-se os dois últimos símbolos em um novo símbolo, somando-se suas
probabilidades. A estes símbolos atribui-se 0 e 1. O novo alfabeto (contendo os símbolos
combinados) é arrumado novamente em ordem decrescente de probabilidade e
sucessivamente o processo é repetido.
Exemplo:
11
0,30
0,25
0,20
0,10
0,10
0,05
00
01
11
101
1000
1001
L = 2,40
A idéia por trás do código de Huffman é a seguinte. Suponha que se obteve uma
árvore qualquer mais ou menos otimizada. Os dois símbolos menos prováveis podem ser
agrupados com um único símbolo, cuja probabilidade é a soma das probabilidades de cada
um e a distinção entre os dois é feita colocando-se ao final do código do novo símbolo, um
0 e um 1, resultando em dois códigos, um para cada um dos símbolos agrupados.
Repetindo-se esse procedimento, vai se chegar a dois únicos símbolos que reune o
agrupamento de diversos outros. A distinção entre esses dois únicos símbolos é feita por
um 0 e um 1, ou seja, chegou-se ao início da árvore de códigos.
9.4.3 – Códigos de Huffman com Códigos não Binários
Completa-se o alfabeto com símbolos de probabilidade zero até que se tenha um
alfabeto de tamanho D + m(D-1) símbolos, onde D = 2 (caso binário) ou D = 3 (caso
ternário), etc., e m é um inteiro qualquer, representando o número de vezes que se fará
agrupamentos de D em D símbolos. Depois procede-se idêntico como no caso de códigos
binários, combinando-se de D em D símbolos. Caso isso não seja feito, a árvore de códigos
poderá inicialmente conter menos do que D ramos, tornando-a não otimizada. O que se
está fazendo é na verdade, inicialmente não agrupar D símbolos mas sim um número
menor de símbolos.
12
Exemplo: Codificar em código de Huffman ternário, o alfabeto:
a1
a2
a3
a4
a5
a6
0,30
0,25
0,20
0,10
0,10
0,05
Número de símbolos do alfabeto a ser codificado = 6
Então: D + m (D-1) = 3 + 2m
Se m = 1 → total = 5
< 6
(Não OK)
Se m = 2 → total = 7
≥6
(OK)
A1
a2
a3
a4
a5
a6
1
2
00
02
010
011
13
9.4.4
Codificação Aritmética
A codificação aritmética, diferentemente da de Huffman, só é obtida tendo-se a
sequência de letras ou símbolos que se quer transmitir. Como exemplo, suponha-se que
tenhamos as letras abaixo com suas respectivas probabilidades.
Letras
Prob.
A
0,2
B
0,2
C
0,1
D
0,1
E
0,2
F
0,1
I
0,05
?
0,05
A função da letra ? na tabela é que necessitamos um término para a sequência a ser
transmitida (End of File).
A codificação aritmética é realizada através da função de distribuição de
probabilidades (função acumulada) das letras. Atribuindo-se números inteiros às letras na
ordem como aparecem na tabela (para facilitar a confecção da figura), teríamos, 1 = A,
2 = B, 3 = C, 4 = D, 5 = E, 6 = F, 7 = I e 8 = ? Fazendo-se isso, podemos colocar
num eixo horizontal as letras e na vertical a distribuição acumulada, conforme mostrado na
Figura 1.
1,0
0,95
0,90
0,80
0,60
0,50
0,40
0,20
0,00
0
1=A
2=B
3=C
4=D
5=E
6=F
7=I
8=?
Figura 1 - Função acumulada de probabilidade das letras
Na codificação aritmética não há necessidade de se colocar as letras em ordem decrescente
ou crescente de probabilidade.
14
Suponha-se que queiramos enviar a palavra BEBIDA. A codificação aritmética
dessa palavra é feita usando-se a função acumulada da Figura 1, conforme mostrado na
Figura 2.
1,00
0,40
0,360
0,3360
0,33560
0,335440
0,3354080
0,95
0,39
0,358
0,3356
0,33558
0,335438
0,3354076
0,90
0,38
0,356
0,3352
0,33556
0,335436
0,3354072
0,80
0,36
0,352
0,3344
0,33552
0,335432
0,3354064
0,60
0,32
0,344
0,3328
0,33544
0,335424
0,3354048
0,50
0,30
0,340
0,3320
0,33540
0,335420
0,3354040
0,40
0,28
0,336
0,3312
0,33536
0,335416
0,3354032
0,20
0,24
0,328
0,3296
0,33528
0,335408
0,3354016
0,00
0,20
0,320
0,3280
0,33520
0,335400
0,3354000
B
E
B
?
I
F
E
D
C
B
A
I
D
A
?
Figura 2 - Obtenção da codificação aritmética da palavra BEBIDA
Com a codificação obtida na Figura 2, obtemos o intervalo mostrado, ou seja, o
Número ∈ [ 0,3354076 , 0,3354080)
Qualquer número desse intervalo pode ser enviado e o receptor fará o
proceso inverso de decodificação.
0,3354076 x 2 = 0,6708152
0,6708152 x 2 = 1,3416304
1,3416304 - 1 = 0,3416304
0,3416304 x 2 = 0,6832608
0,6832608 x 2 = 1,3665216
1,3665216 - 1 = 0,3665216
0,3665216 x 2 = 0,7330432
0,7330432 x 2 = 1,4660864
→ → bit 0
→ → bit 1
→ → bit 0
→ → bit 1
→ → bit 0
→ → bit 1
e assim por diante. Até aqui temos: 0.010101
15
Continuando o processo para os números 0,3354076 e 0,3354080 chegamos a:
2
4
6
8 10 12
15
18
22
0,3354076 = .0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0
0,3354080 = .0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0
0,3354077339 = .0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 ... =
2-2 + 2-4 + 2-6 + 2-8 + 2-9 + 2-10 + 2-12 + 2-13 + 2-14 + 2-16 + 2-18 + 2-21
Pode-se transmitir a sequência binária: 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1
que tem 21 bits para representar a palavra BEBIDA + End of File (=?).
Para efeito de comparação, pode-se usar o processo da codificação de Huffman.
O algoritmo de Huffman resulta em:
A 0,20 11
0,20 11
0,20 10
0,20 01
0,40 00
0,40 1
0,60 0
B 0,20 000
0,20 000
0,20 11
0,20 10
0,20 01
0,40 00
0,40 1
E 0,20 001
0,20 001
0,20 000
0,20 11
0,20 10
0,20 01
C 0,10 011
0,10 010
0,20 001
0,20 000
0,20 11
D 0,10 100
0,10 011
0,10 010
0,20 001
F 0,10 101
0,10 100
0,10 011
I
0,05 0100
0,10 101
?
0,05 0101
Letras Prob. Código
obtido
A
0,2
11
B
0,2
000
E
0,2
001
C
0,1
011
D
0,1
100
F
0,1
101
I
0,05 0100
?
0,05 0101
1,00
A palavra BEBIDA? será transmitida como a sequência binária:
B
E
B
I
D
A ?
000 001 000 0100 100 11 0101
que terá 22 bits para transmissão
Então, por Huffman temos 22 bits e pela codificação aritmética temos 21 bits.
É claro que por Huffman, não haveria a necessidade de se colocar o símbolo ? para
indicar o fim de arquivo, já no método da codificação aritmética esse símbolo é
indispensável.
16
9.4.5 Lempel Ziv
O Algoritmo LZ77
A ideia por de trás do algoritmo LZ77 é a de substituir ocorrências de uma
determinada frase, ou grupo de bytes, numa sequência de dados com referência a uma
prévia ocorrência dessa frase.
Este algoritmo procura numa janela deslizante, definida sobre a sequência de caracteres
enviados, a maior sequência coincidente com inicio no buffer de look-ahead e devolve um
apontador para essa sequência. Ou seja, quando se processa o símbolo de entrada , procurase a maior sequência na janela, igual à que se está a processar.
Search buffer
símbolos já processados
Lookahead buffer posição
corrente e seguintes até ao final
da janela deslizante
Símbolo corrente símbolo que
irá ser processado (codificado)
Cada sequência é representada por um terno ordenado com a seguinte informação:
Offset
distância em relação à posição
corrente onde começa o match.
<Offset, comprimento, codificação_símbolo>
Comprimento
nº de símbolos da sequência de match.
Codificação_símbolo
primeiro símbolo do lookahead buffer
que não pertence aom match.
17
É possível que não seja verificada nenhuma coinsidência dentro da janela, nesse caso é
emitido um terno com o offset e comprimento zero e com o próximo símbolo.
Analise o seguinte exemplo de codificação, em que a janela deslizante tem uma
dimensão de 13 símbolos e o lookahead buffer de 6, onde temos a seguinte notação:
C( símbolo) é a codificação do símbolo.
c
a b r
a c
Exemplo:
a d a b r
a r
r
a r
r
a d
A condição inicial é a seguinte, onde dabrar deve ser codificada e cabraca já foi
codificada:
c
a b r
a c
a d a b r
a r
r
a r
r
a d
a r
r
a d
a r
r
a d
look-ahead buffer
search buffer
tamanho do buffer
Então a letra d é a única a ser codificada.
Código:
< 0, 0, C(d) >
A janela se move de 1 posição:
c
a b r
a c
a d a b r
search buffer
A código seguinte será:
a r
r
look-ahead buffer
< 7 , 4 , C(r ) >
A janela se move de 5 posições:
c
a b r
a c
a d a b r
a r
search buffer
A código seguinte será:
< 3, 5, C(d) >
18
r
look-ahead buffer
O LZ77 (Ziv and Lempel 1977) é um algoritmo fácil de implementar e a
decodificação pode ser feita de maneira extremamente rápida usando pouca
memória. Por estas razões é ajustável quando os recursos são mínimos. A melhor
maneira de explicar o funcionamento do LZ77 é em termos de sua decodificação.
A figura abaixo mostra uma saída do codificador LZ77, supondo para propósitos
de exemplo que o alfabeto consiste apenas de a’s e b’s. A saída consiste de uma
de triplas. O primeiro componente de uma tripla indica quanto voltar no texto já
decodificado para encontrar a próxima frase, o segundo componente armazena o
comprimento dessa frase, e o terceiro dá o próximo caracter da entrada.Os dois
primeiros itens constituem um ponteiro de volta no texto. Na figura os caracteres
abaabab já foram decodificados, e os próximos caracteres para ser decodificados
são representados pela tripla <5,3,b>.Portanto o decodificador volta cinco
caracteres no texto decodificado e copia três caracteres, produzindo a frase aab.
A próxima tripla, <1,10,a>, é uma referencia recursiva. Para decodifica-la, o
decodificador começa copiando um caracter anterior (b) e copia os próximos dez
caracteres. Isso produzirá 10 b’s consecutivos.
19
LZ78 - Codificação
•
•
•
Resultado da codificação expresso na forma:
(i, s)
– i: índice da última frase encontrada no dicionário;
– s: próximo carácter na sequência.
Se a frase tiver um único símbolo e este não existir no dicionário, é
codificado o próprio símbolo antecedido pelo índice 0 (índice da frase
vazia).
Quando o dicionário enche:
– Recolocar o dicionário no seu estado inicial (só com a string nula);
– Substituir frases presentes no dicionário por novas frases;
– Parar de inserir novas frases;
– Parar de inserir novas frases, mas monitorar, a partir deste momento,
a taxa de compressão. Se esta cair até um dado limiar, recolocar o
dicionário no estado inicial.
9
20
Exemplo: Som do monstro de “ Sesame Street “
w a b b a
a b b a
w a b b a
w o o
Dicionário Inicial
w o o
Índice
Entrada
1
w
2
a
3
b
w a b b a
w o o
Tabela resultado final da codificação com o LZ78 representando € por espaço em branco
Dicionário
Saída do codificador
Índice
Entrada
<0,C(w)>
1
w
< 0 , C ( a) >
2
a
< 0 , C ( b) >
3
b
< 3, C ( a ) >
4
ba
< 0 , C (€ ) >
5
€
<1,C(a)>
6
wa
<3,C(b)>
7
bb
< 2 , C (€ ) >
8
a€
<6,C(b)>
9
wab
< 4 , C (€ ) >
10
ba€
<9,C(b)>
11
wabb
<8,C(w)>
12
a€w
<0,C(o)>
13
o
< 13, C (€ ) >
14
o€
<1,C(o)>
15
wo
< 14, C ( w ) >
16
o€w
< 13, C ( o ) >
17
co
21
w
LZW
• Variante do LZ78, desenvolvida por Terry Welch em 1984.
• Introduz duas optimizações
– Inicialmente, os símbolos do alfabeto são inseridos no
dicionário;
– Apenas são enviados para o descodificador os índices das
frases.
• Os símbolos são lidos um a um a partir da sequência a
codificar;
• Estes símbolos (x) vão sendo adicionados a uma frase (W),
inicialmente nula, enquanto Wx for encontrada no dicionário;
• Quando já não for encontrada, é emitido o índice de W, Wx é
colocada no dicionário e, W é iniciada com o símbolo x.
10
22
Variantes dos Algoritmos LZ77 e
LZ78
Figura 1 – Algumas variantes dos algoritmos LZ77 e LZ78.
1
LZH – combina o LZ77 com Huffman
segurança (IPsec)
LZS – combina o LZ77 com um protocolo de
LZSS – variação do LZ77 criado por Storer e Szymanski
LZC - variação do LZ78 criado por Storer
LZT – variação do LZW criado por Ticher
23
Aplicações
•
•
•
•
•
•
•
UNIX Compression
– O algoritmo LZC é usado pelo utilitário “compress” do sistema
operativo UNIX.
GIF (Graphics Interchange Format)
– Muito similar ao “compress” do UNIX, também usa o
algoritmo LZC.
Protocolo V.42bis
– Usa uma variante do LZW (LZT).
O Zip e o gzip usam uma variante do LZ77 combinada com
Huffman estático.
O ARJ usa a codificação de Huffman e o algoritmo LZSS.
O WINRAR usa o LZ77 e Huffman.
O WINZIP entre outros algoritmos usa o LZW.
13
24
9.5 – Canais Discretos sem Memória
São conhecidas as probabilidades p(yi/xj)
Matriz de probabilidades:
x 0  y0
y1
...
y k -1 
x1  p(y 0 /x 0 ) p(y1 / x 0 )
p(y k -1/x 0 ) 


P=
p(y k -1/x1 ) 
 p(y 0 /x1 ) p(y1/x1 )


x j-1 p(y 0 /x j-1 ) p(y1/x j-1 )
p(y k -1/x j-1 )
O somatório nas linhas = 1, ou seja
∑ p(y k /x j ) = 1
K -1
k =0
25
x j fixo
9.5.1 – Canal BSC (Binary Symmetric Channel)
Em casos práticos p deve tender a 0, por exemplo
p = 10-6 ;
p = 10-8
Pode-se calcular a entropia da fonte H(X) e a entropia da saída H(Y):
K -1
H(X) = ∑ P(x k ) log 2 [1/p(x k )]
k =0
[
J -1
H(Y) = ∑ P(y j ) log 2 1/p(y j )
j= 0
]
Podemos calcular também:
[
K -1
H(Y x k ) = ∑ p(y j x k ) log 2 1/p(y j x k )
j= 0
[
]
]
J -1
K -1

H(Y X) = ∑ p(x k )  ∑ p(y j x k ) log 2 1/p(y j x k ) 
k =0
 j= 0

26
Sabe-se que:
p(xkyj) = p(xk) p(yjxk)/p(yj)
p(x,y) = p(y) p(xy) = p(x) p(yx)
logo
H(Y X ) =
H(Y X ) =
J-1
K-1
k =0
j= 0
J-1
K-1
k =0
j= 0
∑ ∑ p(x
∑ ∑ p(x
k
) p(y j x k ) log 2 1/p(y j x k )   =
k
, y j ) log 2 1/p(y j x k )  
[
K -1
Então podemos calcular:
H(X/y j ) = ∑ p(x k y j ) log 2 1/p(x k y j )
k =0
[
K -1
]
]

 J -1
H(X Y) = ∑ p(y j )  ∑ p(x k y j ) log 2 1/p(x k y j ) 

k = 0
j= 0
H(X) representa a incerteza média da entrada
H(Y) representa a incerteza média da saída
H(XY) representa a incerteza média da entrada conhecida a saída (chamado de equívoco)
A quantidade H(X) – H(XY) é a informação sobre a entrada que pode ser
“resolvida” sabendo-se o que aconteceu com a saída. É chamada de informação mútua.
9.6
– Informação Mútua I(X; Y)
I(X; Y) = H(X) – H(XY)
ou
I(X; Y) =
K-1
J-1
k =0
j= 0
∑∑
p(y j x k )
p(x k ) p(y j x k ) log 2
144244
3
p(y j )
p(x k , y j )
144244
3
I(x k ; y j )
27
Exemplo:
3
1 1
1
+ log 2
= 0,811 bits/símbolo
H(X) = log 2
4
3/4 4
1/4
p(y0 = A) = (3/4) . (1-10-2) + (1/4) . (10-2) = 0,745
p(y1 = B) = 1 – p(y0) = 0,255
5
1 3
1
H(Y) = log 2
+ log 2
= 0,81919 bits/símbolo
8
5/8 8
3/8
H(Y) > H(X) → mais bits chegando no receptor do que bits enviados, devido aos
erros introduzidos pelo canal. Cálculo de I(X; Y):
1 - 10- 2
I(X A ; YA ) = log 2
= 0,41023 bits
0,745
10- 2
I(A; B) = log 2
= - 4,67289 bits
0,255
28
10- 2
I(B; A) = log 2
= - 6,21979 bits
0,745
I(B; B) = log 2
1
1 - 1e - 2
= 1,95713 bit
0,255
1
I(X; Y) = ∑ ∑ p(x k ) p(y j /x k ) I(x k ; y j )
k = 0 j= 0
I(X; Y) = 0,73839 bits/símbolo.
Equívoco H(XY) = H(X) – I(X;Y) = 0,811 – 0,73839 = 0,07261 bits/símbolo
H(XY) = 0,07261 bits/símbolo → em média precisamos de 0,07261 bits para corrigir o
erro que o canal introduz sobre X.
I(X;Y) = 0,73839 bits/símbolo→ quantidade média (73,839%) de bits de informação que Y
leva (carrega) sobre X (entrada).
9.5.2.1 – Propriedades de I(X; Y)
1
I(X; Y) = I(Y; X)
2
I(X; Y) ≥ 0
3
I(X; Y) = H(Y) – H(Y/X) = H(X) – H(XY)
4
I(X; Y) = H(X) + H(Y) – H(X,Y)
onde
H(X, Y) = ∑ ∑ p(x k , y j ) log 2
k
j
29
1
p(x k , y j )
Representação por diagrama de Venn:
9.7 – Capacidade do Canal
Num canal discreto sem memória, as probabilidades p(yj, xk) são bem definidas e
dependem só do canal. Se variarmos as p(xk) de entrada, I(X; Y) variará de acordo com
essas probabilidades.
Define-se, então, a capacidade C de um canal como sendo o valor máximo de
I(X; Y) quando se varia p(xk).
C = max I(X; Y)
{p(xk)}
30
Quando
o
canal
é
simétrico,
a
capacidade
C
é
obtida
fazendo-se
p(x0) = p(x1) = p(x2) = …, isto é, equiprobabilidade. Para um canal BSC, a capacidade é
obtida quando p(x0) = p(x1) = ½.
Neste caso:
C = 1 + p log2 p + (1-p) log2(1-p)
C = 1 – H(p)
31
Capacidade máxima (duas possibilidades)
9.8 – Teorema da Codificação do Canal (Teorema de Shannon)
O ruído causa erros (diferenças) entre a sequência de transmissão e a de recepção.
Num canal BSC com p = 10-6, significa que em média haverá um bit com erro em
1 000 000 bits transmitidos.
Para se diminuir os erros introduzidos pelo canal, pode-se codificar os bits que
serão enviados pelo canal (codificação de canal).
Essa codificação é feita introduzindo-se bits redundantes. Enquanto na fonte,
retirou-se os bits redundantes através de uma codificação com códigos de comprimento
variável, aqui, introduz-se bits redundantes de forma controlada.
32
Se a fonte produz k bits e o codificador de canal contém n bits (n > k); o número de
bits redundantes será n-k. A razão r = k/n é chamada de “code rate”. O ideal é se ter um
“code rate” alto (≈ 1).
Pergunta: Existe algum esquema de codificação (no transmissor) de modo que a
probabilidade (de uma mensagem apareça com erros no receptor) seja tão pequena
quanto se queira ?
Resposta: Sim, desde que satisfaça ao teorema da codificação do canal.
Teorema de Shannon
Suponha que a fonte sem memória tenha uma entropia H(S) bits/símbolo e produza
símbolos a cada Ts segundos. Suponha que o canal sem memória tenha uma capacidade C
bits/símbolo e possa ser usado a cada Tc segundos. Então, se
H(S)
C
bits/seg ≤ bits/seg
TS
Tc
é possível fazer um esquema de codificação no qual símbolos da fonte podem ser
transmitidos num canal ruidoso e reconstruídos com uma probabilidade de erro
arbitrariamente pequena. Caso a relação acima não seja satisfeita, não existirá nenhum
modo de se diminuir essa probabilidade de erro. Da mesma forma, isso acontece de um
canal para outro.
Exemplo:
33
com p = 10-2
→
C = 1 + p.log2 p + (1-p) log2(1-p) = 0,9192 bits/símbolo.
Seja o esquema de codificação seguinte: para cada bit da fonte, repete-se n vezes
esse bit, onde n = 2m + 1, m ≥ 1.
Exemplo: n = 3 faz-se:
0 → 000
1 → 111 
→ Regra de codificação arbitrada, sendo que para
cada bit a ser transmitido, transmite-se repetidamente 3 bits iguais
Regra de Decodificação:
000
001
Se chegar
 decodifica-se como sendo o 0
010
100 
porque supõe-se que houve apenas 1 troca
011
101
Se chegar
 decodifica-se como sendo o 1 porque supõe-se que houve apenas 1 troca
110
111
Ou seja, é mais provável um erro do que dois erros na transmissão binária.
Logo, a probabilidade de erro será:
n
Pe = ∑ Cin p i (1 - p) n -i
m=1
i = m +1
34
m+1 significa da metade em diante
com n = 3 tem-se
3
Pe = ∑ Ci3 (10- 2 )i (1 - 10- 2 )3-i
i=2
r=
No exemplo temos
k
n
r = 1/3 = 0,333
e
Pe = 2,98 x 10-4
Para n = 5, tem-se
5
Pe = ∑ Ci5 (10- 2 )i (1 - 10- 2 )5 -i
i =3
35
e r = 1/5
Code Rate r = 1/n
Prob. média de erro, Pe
1
1e-2
1/3
3e-4
1/5
1e-6
1/7
4e-7
1/9
1e-8
1/11
5e-10
9.9 – Entropia e Informação Mútua para Variáveis Contínuas
 1 
+∞
H(X) = ∫- ∞ f s (x) log 2 
 dx
f
(x)
 x 
fs(x) – função densidade de probabilidade
 f (y x ) 
+∞ +∞
I(X; Y) = ∫- ∞ ∫− ∞ f X, Y (x, y) log 2  x

 f x ( y) 
9.10 – Teorema da Capacidade do Canal
Suponha que estejamos transmitindo um sinal x(t) e recebendo y(t), onde
y(t) = x(t) + n(t), onde n(t) é um ruído branco aditivo com função densidade de
probabilidade N(0, σ2). A potência de x(t) é P Watts e a banda passante de transmissão
é igual a B Hertz.
igual a B Hertz.
O ruído tem densidade espectral N0/2 Watts/Hertz e banda passante
A potência do ruído é σ2 = N0 B Watts
A capacidade C do canal é dada por:

P 
 P 
 bits/seg
C = B log 2 1+ 2  = B log 2 1 +
N
B
 σ 

0 
36
onde
P
σ2
é a relação sinal/ruído
σ 2 = N 0 B → potência de ruído
9.11 Rate-Distortion Theory
In lossy data compression, the decompressed data need not be exactly the same as the
original data. Often, it suffices to have a reasonably close approximation. A distortion
measure is a mathematical entity which specifies exactly how close the approximation is.
Generally, it is a function which assigns to any two letters
non-negative number denoted as
Here,
is the original data,
between and
measure:
is the approximation, and
and
in the alphabet
a
is the amount of distortion
. The most common distortion measures are the Hamming distortion
and the squared-error distortion measure (which is only applicable when
numbers):
is a set of
Rate-distortion theory says that for a given source and a given distortion measure, there
exists a function, R(D), called the rate-distortion function. The typical shape of R(D) looks
like this:
Para D=0 tem-se R = H (entropia da fonte )
R é dado em bits (bits/símbolo)
D é dado normalmente em dB.
37
9.11 Referencias
1. C. E. Shannon, A Mathematical Theory of Communication (free pdf version)
2. C. E. Shannon and W. Weaver, The Mathematical Theory of Communication. ($13
paper version)
3. C. E. Shannon, N. J. Sloane, and A. D. Wyner, Claude Elwood Shannon: Collected
Papers.
4. C. E. Shannon, ``Prediction and Entropy of Printed English," available in Shannon:
Collected Papers.
5. C. E. Shannon, ``Coding Theorems for a Discrete Source with a Fidelity Criterion,"
available in Shannon: Collected Papers.
6. T. M. Cover and J. A. Thomas, Elements of Information Theory.
7. R. Gallager, Information Theory and Reliable Communication.
8. A. Gersho and R. M. Gray, Vector Quantization and Signal Compression.
9. K. Sayood, Introduction to Data Compression.
10. M. Nelson and J.-L. Gailly, The Data Compression Book.
11. A. Leon-Garcia, Probability and Random Processes for Electrical Engineering.
(Student Solution Manual).
12. A. Papoulis, Probability, Random Variables, and Stochastic Processes.
13. M. R. Schroeder, Computer Speech: Recognition, Compression, Synthesis.
14. G. Held and T. R. Marshall, Data and Image Compression: Tools and Techniques.
15. D. Hankerson, P. D. Johnson, and G. A. Harris, Introduction to Information Theory
and Data Compression .
38