Exame de Compressão e Codifica cão de Dados

Exame de Compress~ao e Codicac~ao de Dados
Secc~ao de Telecomunicacco~es { DEEC
Instituto Superior Tecnico
25 de Fevereiro de 2000
1.
Considere uma fonte sem memoria que emite smbolos do alfabeto X = fA; B; C g, com probabilidades fp(A) = 0:9; p(B ) = 0:05; p(C ) = 0:05g. Desenhe um codigo optimo (por exemplo, de
Human) para esta fonte e calcule a sua eci^encia.
b) Qual a ordem da extens~
ao necessaria para que o comprimento medio de codicac~ao seja inferior a
0.7 bits/smbolo ?
c) Uma fonte S gera aleatoriamente smbolos do conjunto com 48 elementos, fA; B; C; :::; Z; a; b; :::; z g
(todas as letras, maiusculas e minusculas). Considere agora que a sada desta fonte e ligada a um
bloco que converte todas as letras em minusculas (por exemplo, \AeCxuDBaY" e transformado
em \aecxudbay"). A sada desse bloco de convers~ao constitui uma outra fonte X . Sabendo que a
entropia de S e log2 48 bits/smbolo, determine a entropia de X e a informac~ao mutua I (S ; X ).
Considere que a fonte S e ligada a um bloco diferente que converte todas as maiusculas em
minusculas e as minusculas em maiusculas (por exemplo, \AeCxuDBaY" e transformado em
\aEcXUdbAy"); designe a sada deste novo bloco por Y . Determine a entropia de Y e a informac~ao
mutua I (S ; X ).
d) Existe um procedimento de codicac~
ao (proposto por Tunstall, em 1968) que pode ser visto como
recproco do de Human. No codigo de Human procura-se codicar os smbolo da fonte com
sequ^encias de comprimento variavel por forma a que aos smbolos mais provaveis correspondam
sequ^encias mais curtas. Na codicac~ao de Tunstall, o objectivo e codicar sequ^encias (com comprimento variavel) de smbolos da fonte com palavras de codigo de comprimento xo. Ao desenhar
um codigo de Tunstall, o objectivo natural e maximizar o comprimento medio das sequ^encias de
entrada do codigo. Um codigo de Tunstall de comprimento n = 2 para uma fonte de smbolos
fA; B g com p(A) = 0:8 e
a)
AAA ! 00; AAB ! 01; AB ! 10; B ! 11
Calcule o eci^encia media deste codigo. Desenhe um codigo de Human para a extens~ao de ordem
2 da fonte (isto e, para fAA; AB; BA; BB g) e compare os resultados.
2. Um instrumento de medida produz valores inteiros no conjunto f0,1,...,511g; esta \fonte" e descrita
por um modelo de Markov de primeira ordem dado por
p(Xn = Xn;1 jXn;1 ) = 1=2
p(Xn = Xn;1 ; 1jXn;1) = 1=4
p(Xn = Xn;1 + 1jXn;1) = 1=4
(em que as operac~oes \+" e \-" s~ao tomadas modulo 512, isto e 511 + 1 = 0 e 0 ; 1 = 511).
a) Verique que a distribui
c~ao estacionaria desta fonte e
|
{z
}
= [1=512; 1=512; ::::; 1=512]:
512 elementos
1
(1)
b)
c)
3.
Calcule a taxa de entropia condicional, bem como a entropia da distribuic~ao estacionaria. Compare
e comente.
Desenhe um sistema de codicac~ao preditiva para esta fonte. Calcule o comprimento medio do
codigo obtido e compare com a taxa de entropia.
Considere um canal binario simetrico (CBS) cuja probabilidade de erro e . Qual a capacidade
deste canal?
b) Considere dois canais bin
arios simetricos iguais, ambos com probabilidade de erro , ligados em
serie. Qual capacidade do canal resultante?
c) Considere de novo o CBS com probabilidade de erro . Considere que se utiliza um c
odigo de
repetic~ao com palavras de 3 bits; isto e, para enviar 0 transmite-se 000, para enviar 1, transmite-se
111. O criterio de descodicac~ao e o de dist^ancia mnima; isto e, por exemplo, 001 e descodicado
como 000, e 110 como 111. Mostre que a probabilidade de errar e igual a 32 ; 23 .
d) Nas condic~
oes da alnea anterior, determine quais os valores de para o quais o codigo n~ao apresenta nenhuma vantagem (isto e, para os quais = 32 ; 23 ); calcule a capacidade de canal
correspondente e interprete o resultado.
a)
4. Considere um quantizador escalar uniforme, com 20 celulas, cuja gama de valores de entrada e [;1; 1[.
Assuma que a entrada e uma variavel aleatoria X cuja func~ao densidade de probabilidade e a que se
apresenta na gura seguinte:
b)
Considerando que A = 0, qual o valor da relac~ao sinal/rudo de quantizac~ao SNRQ (em dB)?
Recorde que SNRQ = 10 log10 (Ps2 =Pr2 ) dB , em que Ps2 e Pr2 s~ao, respectivamente, os valor medios
do quadrado do sinal e do erro de quantizac~ao (as pot^encias medias). Este quantizador e optimo
para este caso (com A = 0)?
Recorde que o valor medio do quadrado do erro de quantizac~ao, para quantizadores n~ao uniformes,
sob a aproximac~ao de alta resoluc~ao, e dado por
1
D = 12
pi 2i ;
i
c)
em que a soma varre todas as celulas, pi e a probabilidade da entrada cair na celula i, e i e a
largura da celula i. Com A 6= 0, o quantizador uniforme ainda e optimo? Justique.
Considere, nalmente, um quantizador ainda com 20 celulas, das quais 15 est~ao no intervalo [;1; 0]
(portanto cada uma com largura 1=15) e as restantes 5 no intervalo [0; 1] (portanto cada uma com
largura 1=5). Determine o valor de A a partir do qual este quantizador n~ao uniforme apresenta
menor erro de quantizac~ao quadratico medio do que o quantizador uniforme original.
a)
X
2