Telecomunicações – 2003/2004
3º ano Eng.ª Informática
Exercícios sobre Teoria da Informação – 5ª ficha de exercícios
Sumário:
- Resolução de exercícios sobre Teoria da Informação.
- Códigos de da Auto-Informação, Entropia, Entropia conjunta e
condicionada, Capacidade de canal.
1. Uma dada fonte de informação X produz símbolos ternários { A, B, C} com as
probabilidades de ocorrência {9/27, 16/27, 2/27}, respectivamente.
a) Determinar a auto informação de cada símbolo da fonte I(xi).
b) Determinar o valor da entropia H(X) da fonte.
c) Determinar o valor da entropia conjunta H(X,Y), supondo que o canal
cria uma relação entre os símbolos gerados pela fonte X e os
símbolos descodificados à saída do canal, uma segunda fonte Y
portanto. Essa relação é dada pelas probabilidades de transição
p(yj|xi) conforme o modelo do canal seguinte
2. Considere uma comunicação via satélite, onde se existem 3 canais
envolvidos, ascendente, bordo e descendente. Determine a capacidade do
sistema global tendo esses canais as seguinte probabilidades de erro.
Peasc=0,01
Pebordo=0
Pedesc=0,1
a) Desenhe o modelo do sistema global.
b) Determine a capacidade do sistema global tendo esses canais as
seguinte probabilidades de erro.
António Moura
1
Telecomunicações – 2003/2004
3º ano Eng.ª Informática
3. As probabilidades de geração dos símbolos de uma fonte binária são
p(x1)=p(x2)= 0,5. Os símbolos gerados por essa fonte binária atacam um
canal cuja matriz de transição de probabilidades é
a) Desenhe o modelo do canal.
b) Determine os valores das probabilidades p(y1) e p(y2) de cada um dos
símbolos binários à saída do canal de comunicação.
c) Determine os valores das probabilidades conjuntas p(xi,yj).
d) Determine o valor da informação mútua média I(X,Y).
e) Determine os valores da equivocação e da redundância do canal.
4. A figura abaixo representa um canal de informação. Determine a entropia
H(A) à entrada do canal e as entropias condicionais H(A|B) e H(B|A).
5. Para o modelo de canal de transmissão binário simétrico da figura (BSC),
abaixo apresentado, determine a taxa de transmissão de informação e o
débito médio de informação, quando p assume valores iguais a 0.9, 0.8 e 0.6.
António Moura
2
Telecomunicações – 2003/2004
3º ano Eng.ª Informática
6. O comportamento de uma fonte de informação X é definido através de uma
máquina de transição de estados, cujo comportamento é modelizado à custa
da seguinte cadeia de Markov. Quando a máquina se encontra no estado A,
B ou C, é enviado o símbolo de fonte xA, xB ou xC, respectivamente. As
probabilidades p(A), p(B) e p(C) quantificam a probabilidade de geração do
primeiro símbolo de fonte a ser transmitido pelo canal de comunicação (a
probabilidade do primeiro estado).
a)
b)
c)
d)
Calcular a entropia H(Xi) de cada um dos estados, com iЄ{1,2,3}.
Calcular a entropia H(X) da fonte.
Calcular a entropia H(2)(X) da extensão de ordem 2.
Verificar que H(2)(X) ≥ H(X).
7. Duas fontes de informação X e Y produzem símbolos quaternários {x0, x1, x2,
x3} e {y0, y1, y2, y3}, com probabilidades de ocorrência {1/2, 1/4, 1/8, 1/8} e
{1/4, 1/4, 1/4, 1/4}, respectivamente. Sabendo que as fontes produzem
símbolos a uma taxa de 1000 símbolos por segundo, deterime:
a)
b)
c)
d)
O débito binário das fontes R.
Uma codificação mais adequada para as fontes.
O comprimento médio das palavras de código N .
Conclua se a codificação que realizou é capaz de codificar sem erros
as duas fontes.
António Moura
3
Telecomunicações – 2003/2004
3º ano Eng.ª Informática
Formulário:
 1 
 = − log 2 ( p( xi )), ∀i
I ( xi ) = log 2 
 p ( xi ) 
M
M
M
 1 
 = −∑ p( xi ) ⋅ log 2 ( p( xi ))
H ( X ) = ∑ p ( xi ) ⋅ I ( xi ) = ∑ p ( xi ) ⋅ log 2 
i =1
i =1
i =1
 p ( xi ) 
R = r ⋅ H(X )
bis / seg
1
 1 
,
H ( X ) = Ω b ( p ) = p ⋅ log 2   + (1 − p ) ⋅ log 2 
 p
1− p 
p (0 ) = p
p (1) = 1 − p
R = r ⋅ H ( X ) = rb ⋅ Ω b ( p ) ≤ rb
N =
M
rb
= ∑ p(xi ) ⋅ N i
r
i =1
H (X ) ≤ N ≤ H (X ) + ε ,
ε =1
com
H ( n) ( X ) ≤ N ≤ n ⋅ H ( X )
n ⋅ H (X ) ≤ n ⋅ N ≤ n ⋅ H (X ) + 1
η=
⇒ H (X ) ≤ N ≤ H (X ) +
1
n
R H (X )
=
≤1
rb
N
M
K = ∑ 2 − Ni ≤ 1
i =1
 p (xi \ y j ) 

I ( xi , y j ) = log 2 
p
(
x
)
i


I ( X , Y ) = ∑∑ p (xi , y j ) ⋅ I (xi , y j )
M
N
i =1 j =1
I ( X , Y ) = H ( X ) − H ( X \ Y ) = H (Y ) − H (Y \ X ) = H ( X ) + H (Y ) − H ( X , Y )
H ( X , Y ) = H ( X ) + H ( X \ Y ) = H (Y ) + H (Y \ X )
António Moura
4
Telecomunicações – 2003/2004
3º ano Eng.ª Informática
M N


1

H ( X , Y ) = ∑∑ p (xi , y j ) ⋅ log
 p (x , y ) 
i =1 j =1
i
j


M N


1

H ( X \ Y ) = ∑ ∑ p(x i , y j )⋅ log
 p (x \ y ) 
i =1 j =1
i
j


M N


1

H (Y \ X ) = ∑∑ p ( y j , xi ) ⋅ log
 p(y \ x ) 
i =1 j =1
j
i 

redundância = 1 −
C s = max[I ( X , I )],
p ( xi )
C = rs ⋅ C s ,
António Moura
H (Y \ X )
H (X )
bits / símbolodefonte
bits / segundo
5