Exame de Compressão e Codifica cão de Dados
Transcrição
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
Documentos relacionados
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
Leia mais6100278 - Universidade Federal do Paraná
trafego para um dado intervalo de observac~ao, e burtness (raz~ao entre a taxa de pico e a taxa media). Esses descritores, entretanto, n~ao fornecem informac~ao suciente sobre complexas correl...
Leia mais