EN2612 Teoria da Informacao e Codigos - 1Q2015

Lista 1

1. Considere uma fonte X = {x1, x2, x3, x4, } tal que p(xi) =1

2i, i = 1, 2, . . ..

(a) Calcule a entropia de X. As seguintes expressoes podem ser uteis:

n=1

rn =r

1 r

n=1

nrn =r

(1 r)2.

(b) Um smbolo de X e gerado de acordo com esta distribuicao. Ache uma sequencia deperguntas do tipo sim ou n~ao que leve ao mnimo numero esperado de perguntas paraidentificar o resultado de X. Compare o numero esperado de perguntas com H(X).

2. Seja Y = 2X , onde X e uma variavel aleatoria que assume um numero finito de valores. Qualou quais das seguintes afirmacoes sao verdadeiras?

(a) H(Y ) H(X)(b) H(Y ) H(X)(c) H(Y ) > H(X)

(d) H(Y ) < H(X)

(e) H(Y ) = H(X)

3. Suponha uma fonte discreta sem memoria que produza N smbolos com probabilidadesp =

[p1 p2 pN

]. Qual o valor mnimo da entropia desta fonte? Ache todos os ve-

tores p que atingem esta entropia mnima.

4. A entropia relativa de p(x) em relacao a q(x) (ou distancia de Kullback-Leibler ou divergenciaentre p(x) e q(x)) e definida por

D (p (x) ||q (x)) =xX

p(x) logp(x)

q(x),

sendo p(x) e q(x) funcoes de probabilidade definidas para xX e X e o conjunto com todos ospossveis valores de x.

Uma das propriedades da entropia relativa e que ela sempre fornece um valor nao-negativo.Usando este fato, e lembrado que a entropia de uma fonte esta relacionada com a incertezasobre qual smbolo e gerado a cada instante, determine o limitante superior (na ausencia dequaisquer restricoes) para a entropia de uma fonte X, que produz smbolos de acordo comuma distribuicao p(x).

5. Classifique os codigos abaixo em relacao ao comprimento (fixo ou variavel) e classe (singu-lar/nao-singular, univocamente decodificavel, instantaneo/nao-instantaneo). Justifique cadaresposta.

1

X C1 C2 C3 C4A 0 0 10 0B 0 010 00 10C 0 01 11 110D 0 10 110 111

Referencias

[1] Cover, T. M. e Thomas, J. A., Elements of Information Theory, Wiley-Interscience, 2a Ed.,2006.

2