Codificação de Fonte e Teorema da Amostragem de Nyquist

Codificação de Fonte Conversão AD teorema da amostragem de Nyquist DPCM differential pulse code modulation DM delta modulation e ADM adaptive delta modulation codificação por entropia código de Huffman Centro de Tecnologia Departamento de Eletrônica e Computação UFSM00261 SISTEMAS DE COMUNICAÇÃO DIGITAL I Prof Fernando DeCastro Codificação de Fonte Conforme já brevemente discutido nos slides 3 5 6 e 7 do Cap I o Codificador de Fonte source encoder efetua a digitalização ADC e a compressão da informação original p efeito de minimizar a banda ocupada no canal de transmissão Especificamente a Codificação de Fonte é o processo que visa reduzir o máximo possível a informação redundante da sequência de Informação em sua saída sequência esta obtida a partir do processamento do sinal de entrada Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 2 Conversão AD I Amostragem Processo através do qual o sinal contínuo no tempo 𝑥𝑡 é transformado em um sinal discreto no tempo representado por 𝑥𝑝𝑡 ou 𝑥𝑝𝑛 onde 𝑛 é interpretado como o instante de tempo no qual o valor do sinal 𝑥𝑡 é levado à saída do processo de amostragem Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 3 O processo de digitalização de um sinal analógico efetuado em um ADC analog to digital converter compreende 3 etapas que ocorrem em sequência I Amostragem no tempo do sinal analógico II Quantização das amplitudes do sinal amostrado III Codificação ie mapeamento de cada amostra do sinal quantizado em uma respectiva palavra binária O processo de digitalização de um sinal analógico já foi estudado na disciplina de Sinais e Sistemas ver httpswwwfccdecastrocombrpdfSSAula316032020pdf Faremos aqui uma breve revisão 𝑥𝑡 𝑥𝑝𝑡 Nota Nos próximos slides faremos uso do conceito de espectro de um sinal e do conceito de função de transferência de um sistema no caso um filtro passabaixa Para aqueles que ainda não cursaram a disciplina Sinais e Sistemas é aconselhável estudarem com atenção o capítulo introdutório da referida disciplina disponível em httpswwwfccdecastrocombrpdfSSAula212032020pdf como também assistir as videoaulas relativas a este capítulo introdutório disponíveis em httpswwwfccdecastrocombrA2SSUFSMhtml A amostragem no domínio do tempo de um sinal analógico 𝑥 𝑡 pode ser modelada pela multiplicação entre sinal 𝑥 𝑡 e uma sequência de impulsos periódicos 𝑝 𝑡 de período 𝑇𝑠 Τ 1 𝑓𝑠 s sendo 𝑓𝑠 Hz ou Sas samples per second a frequência de amostragem conforme mostrado abaixo Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 4 Conversão AD e representação no domínio frequência da operação de amostragem 𝑥𝑝 𝑡 𝑥𝑡 𝑝 𝑡 onde ℱ é o operador Transformada de Fourier O operador na equação 1 denota a operação de convolução ver propriedade multiplication na tabela no slide 27 de httpswwwfccdecastrocombrpdfSSAulas9a1227042020pdf a b c d e ℱ a sinal analógico 𝑥𝑡 a ser amostrado b função de amostragem 𝑝𝑡 c operação de amostragem resultando no sinal amostrado 𝑥𝑝 𝑡 𝑝 𝑡 𝑥𝑡 d representação da operação de amostragem 𝑥𝑝 𝑡 𝑝 𝑡 𝑥𝑡 através de um grafo de fluxo de sinal 1 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 5 Conversão AD O espectro 𝑃 𝜔 no domínio frequência 𝜔 2𝜋𝑓 do sinal 𝑝 𝑡 formado por impulsos periódicos de período 𝑇𝑠 é dado por 𝑃 𝜔 ℱ𝑝 𝑡 onde ℱ é o operador que retorna a Transformada de Fourier do argumento e resulta conforme equação 2 e figura abaixo ver última linha da tabela no slide 29 de httpswwwfccdecastrocombrpdfSSAulas9a1227042020pdf 2 ℱ Da equação 1 no slide anterior note que o produto 𝑥𝑡𝑝 𝑡 𝑥𝑝 𝑡 no domínio tempo resulta na convolução 1 2𝜋𝑋 𝜔 𝑃 𝜔 𝑋𝑝 𝜔 no domínio frequência convolução que é efetuada entre o espectro 𝑋 𝜔 ℱ𝑥 𝑡 do sinal analógico 𝑥𝑡 e o espectro 𝑃 𝜔 ℱ𝑝 𝑡 da função de amostragem 𝑝𝑡 conforme mostra a figura abaixo sendo 𝜔𝑠 2𝜋𝑓𝑠 e 𝑓𝑠 Τ 1 𝑇𝑠 𝑋 𝜔 operador indica a convolução entre 𝑋 𝜔 e 𝑃 𝜔 𝜔𝑀 2𝜋𝑓𝑀 𝑃 𝜔 ℱ𝑝 𝑡 𝑋 𝜔 ℱ𝑥 𝑡 𝑃 𝜔 ℱ𝑝 𝑡 𝜔 𝑓𝑀 Hz é a máxima frequência no espectro 𝑋 𝜔 do sinal analógico 𝑥 𝑡 O resultado da convolução entre 𝑋 𝜔 e 𝑃 𝜔 ie o resultado de 𝑋𝑝 𝜔 1 2𝜋𝑋 𝜔 𝑃 𝜔 referido no slide anterior é mostrado na figura abaixo p a situação em que 𝑓𝑠 2𝑓𝑀 onde 𝑓𝑀 é a máxima frequência no espectro do sinal 𝑥𝑡 Note que o espectro 𝑋𝑝 𝜔 do sinal amostrado 𝑥𝑝 𝑡 é formado por múltiplos espectros transladados em frequência que são réplicas do espectro original 𝑋 𝜔 ℱ𝑥 𝑡 do sinal analógico 𝑥𝑡 Cada translação em frequência do espectro 𝑋 𝜔 ocorre em uma frequência central 𝑘𝑓𝑠 onde 𝑘 1 2 3 Observe também que o espectro 𝑋 𝜔 do sinal analógico original 𝑥𝑡 pode ser recuperado a partir do espectro 𝑋𝑝 𝜔 do sinal amostrado 𝑥𝑝 𝑡 aplicandose um filtro passabaixa cuja magnitude da função de transferência 𝐻𝐿𝑃 𝜔 é indicada pela caixa quadrada formada pela linha tracejada vermelha na figura abaixo A função de transferência 𝐻𝐿𝑃 𝜔 atenua todos os espectros transladados para as frequências centrais 𝑘𝑓𝑠 𝑘 1 2 3 mas deixa passar o espectro original 𝑋 𝜔 sem atenuação Portanto submetendo o sinal amostrado 𝑥𝑝 𝑡 a um filtro passabaixa com função de transferência 𝐻𝐿𝑃 𝜔 o sinal analógico original 𝑥𝑡 pode ser recuperado Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 6 𝑋𝑝 𝜔 1 2𝜋𝑋 𝜔 𝑃 𝜔 Conversão AD 𝐻𝐿𝑃 𝜔 𝑋 𝜔 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 2𝑓𝑀 2ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 2𝑓𝑠 4𝑓𝑀 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 7 Conversão AD A figura abaixo mostra o resultado da convolução 𝑋𝑝 𝜔 1 2𝜋𝑋 𝜔 𝑃 𝜔 p a situação em que 𝑓𝑠 2𝑓𝑀 onde 𝑓𝑀 é a máxima frequência no espectro do sinal 𝑥𝑡 Note que como 𝑓𝑠 2𝑓𝑀 ocorre a formação de uma banda de guarda que separa a maior frequência 𝑓𝑀 do espectro 𝑋 𝜔 original e a menor frequência 𝑓𝑠 𝑓𝑀 da 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 Observe que para fins de recuperação do sinal analógico original 𝑥𝑡 através de se um filtro passabaixa com função de transferência 𝐻𝐿𝑃 𝜔 referida no slide anterior a existência de uma banda de guarda elimina a necessidade de que a curva da magnitude da função de transferência 𝐻𝐿𝑃 𝜔 seja uma caixa quadrada facilitando a implementação do filtro que nesta situação pode ter uma curva de magnitude suave entre a faixa de passagem e a faixa de rejeição filtros com curva de magnitude de 𝐻𝐿𝑃 𝜔 na forma de uma caixa quadrada são difíceis de serem implementados demandando muitos coeficientes 𝑋𝑝 𝜔 1 2𝜋𝑋 𝜔 𝑃 𝜔 𝐻𝐿𝑃 𝜔 𝑋 𝜔 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 8 Conversão AD 𝑋𝑝 𝜔 1 2𝜋𝑋 𝜔 𝑃 𝜔 𝑋 𝜔 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 Vamos analisar agora a situação em que 𝑓𝑠 2𝑓𝑀 conforme mostrado na figura abaixo Note que para 𝑓𝑠 2𝑓𝑀 o espectro 𝑋 𝜔 original é superposto pela 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 Portanto para esta situação tornase impossível recuperar o sinal original através de um filtro passa baixa porque o espectro 𝑋 𝜔 original é interferido pela superposição da 1ª réplica de 𝑋 𝜔 transladada em frequência e centrada em 𝑓𝑠 o que causaria distorção no sinal recuperado pelo filtro passabaixa Esta distorção é denominada aliasing alias pseudônimo em inglês porque o espectro original 𝑋 𝜔 sofre interferência de uma réplica dele mesmo com outro nome isto é sofre interferência dele mesmo só que transladado em frequência Teorema da Amostragem de Nyquist Seja 𝑥𝑡 um sinal limitado em banda tal que 𝑓𝑀 seja a frequência mais alta de seu espectro frequência a partir da qual as componentes espectrais de 𝑥𝑡 podem ser consideradas de magnitude desprezível Sejam os valores de 𝑥𝑡 determinados a intervalos constantes de 𝑇𝑠 segundos tais que 𝑇𝑠 1 2𝑓𝑀 isto é 𝑥𝑡 é periodicamente amostrado a cada 𝑇𝑠 1 2𝑓𝑀 segundos Desta forma sendo 𝑇𝑠 1 2𝑓𝑀 então a frequência de amostragem será maior ou igual a 2𝑓𝑀 𝑓𝑠 1𝑇𝑠 2𝑓𝑀 Uma vez obedecidas as condições acima as amostras 𝑥𝑛𝑇𝑠 𝑥 𝑛 de 𝑥𝑡 univocamente determinam 𝑥𝑡 sendo 𝑛 01 o índice das amostras Nesta situação o sinal 𝑥𝑡 pode ser reconstruído a partir do sinal amostrado 𝑥 𝑛 através de um filtro adequado Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 9 A frequência de amostragem mínima 𝑓𝑠 2𝑓𝑀 para que não haja ocorrência de aliasing é denominada de Nyquist Rate httpsenwikipediaorgwikiNyquistrate Não confundir Nyquist Rate com frequência de Nyquist ver httpsenwikipediaorgwikiNyquistfrequency 𝑥𝑡 𝑥𝑡 𝑥𝑡 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 10 Conversão AD II Quantização Processo através do qual o sinal amostrado 𝑥 𝑛 contínuo em amplitude é transformado em um sinal 𝑥𝑞 𝑛 discreto em amplitude viabilizando que o posterior processo III Codificação mapeie uma palavra binária de 𝑁 bits a cada um dos 𝑀 2𝑁 respectivos valores de amplitudes quantizados Por exemplo a figura abaixo mostra um sinal 𝑥𝑞 𝑛 quantizado em um conjunto de 𝑀 11 possíveis amplitudes dadas por 𝑚𝑘 6 5 4 3 2 1 0 1 2 3 4 Volts com 𝑘 01 𝑀 1 O sinal 𝑥𝑞 𝑛 quantizado é originado a partir da quantização de um sinal amostrado 𝑥 𝑛 contínuo em amplitude que por sua vez é originado da amostragem no domínio tempo de um sinal analógico 𝑥𝑡 A excursão de amplitude do sinal 𝑥 𝑛 varia entre os limites 𝑉𝐿 e 𝑉𝐻 Especificamente note na figura abaixo que para cada instante discreto 𝑛 o processo de quantização calcula 𝑀 erros instantâneos de quantização dados por 𝑒𝑞𝑛 𝑥𝑛 𝑚𝑘 com 𝑘 assumindo os valores 01 𝑀 1 O valor de 𝑚𝑘 que resultar no menor 𝑒𝑞𝑛 é então atribuído a 𝑥𝑞𝑛 𝑥𝑡 𝑥 𝑛 𝑥𝑞 𝑛 𝑡 𝑛 𝑒𝑞𝑛 𝑥𝑛 𝑥𝑞𝑛 𝑒𝑞 𝑛 𝑥 𝑛 𝑥𝑞 𝑛 0 𝑉𝐻 𝑉𝐿 𝑆 𝑉𝐻 𝑉𝐿𝑀 é denominado passo de quantização O valor absoluto 𝑒𝑞𝑛 do erro de quantização 𝑒𝑞𝑛 é sempre menor do que Τ 𝑆 2 ie 𝑒𝑞𝑛 Τ 𝑆 2 p qualquer amostra de índice 𝑛 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 11 Conversão AD Portanto o processo de quantização pode ser representado pelo bloco funcional mostrado na figura abaixo 𝑄 𝑥 𝑛 𝑥𝑞 𝑛 𝑄 arg min 𝑚𝑘 𝑚𝑘 onde 𝑥𝑞 𝑛 𝑄𝑥 𝑛 sendo 𝑄 o operador definido por 3 Desta maneira lendo matematicamente a equação 3 o operador de quantização 𝑄 executa o procedimento Dado um valor do argumento do operador 𝑄 o operador determina os 𝑀 valores resultantes da operação 𝑚𝑘 para cada argumento 𝑚𝑘 da operação 𝑚𝑘 e então retorna o valor de 𝑚𝑘 que resultou no menor 𝑚𝑘 Note que quanto maior for o número 𝑀 de níveis de quantização menor será o passo de quantização 𝑆 𝑉𝐻 𝑉𝐿𝑀 e portanto menor será o erro de quantização 𝑒𝑞𝑛 𝑥𝑛 𝑥𝑞𝑛 ver slide anterior Consequentemente menor será o valor médio quadrático de 𝑒𝑞𝑛 identificado por eq2 e denominado de potência do ruído de quantização dada por ver dedução na seção 221 de httpwwwfccdecastrocombrpdfcd2pdf e onde 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 é o conjunto de 𝑀 amplitudes quantizadas níveis de quantização c 𝑘 01 𝑀 1 Os valores do erro de quantização 𝑒𝑞𝑛 são aleatórios porque as amplitudes do sinal analógico 𝑥𝑡 são também aleatórias um sinal de voz ou de vídeo por exemplo Portanto em razão da aleatoriedade o erro de quantização 𝑒𝑞𝑛 pode ser interpretado como um ruído de quantização Consequentemente quanto maior for o número 𝑀 de níveis de quantização menor será o passo de quantização 𝑆 e mais 𝑥𝑞𝑛 se assemelhará à 𝑥𝑛 porque 𝑥𝑞𝑛 será menos degradado pelo ruído aditivo de quantização A relação sinalruído de quantização 𝑆𝑁𝑅𝑄dB é dada por ver dedução na seção 221 de httpwwwfccdecastrocombrpdfcd2pdf eq2 𝑆2 12 4 Watts 𝑆𝑁𝑅𝑄 6𝑁 dB sendo 𝑁 log2𝑀 o número de bits da palavra binária respectivamente mapeada pelo posterior processo III Codificação a cada um dos 𝑀 2𝑁 respectivos valores 𝑚𝑘 de amplitudes quantizadas sendo 𝑘 01 𝑀 1 5 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 12 𝑥𝑡 𝑥𝑞𝑡 𝑥𝑛𝑇𝑠 𝑥 𝑛 𝑥𝑞 𝑛𝑇𝑠 𝑥𝑞 𝑛 𝑇𝑠 Por exemplo a figura abaixo ilustra o processo de quantização de um conversor AD ADC que utiliza palavras binárias de 𝑁 3 bitsamostra 𝑀 2𝑁 8 respectivos valores 𝑚𝑘 de amplitudes quantizadas 𝑘 01 𝑀 1 A relação sinal ruído de quantização dada por 5 resulta 𝑆𝑁𝑅𝑄 6𝑁 18 dB Se o ADC utilizasse palavras binárias de 𝑁 4 bitsamostra 𝑀 2𝑁 16 respectivos valores 𝑚𝑘 de amplitudes quantizadas obteríamos 𝑆𝑁𝑅𝑄 6𝑁 24 dB indicando que um ADC de 𝑁 4 bits digitaliza com mais fidelidade o sinal analógico do que um ADC de 𝑁 3 bits Conversão AD Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 13 Conversão AD 𝑚7 111 𝑚6 110 𝑚5 101 𝑚4 100 𝑚3 011 𝑚2 010 𝑚1 001 𝑚0 000 𝑥𝑞𝑡 O processo de codificação 𝒎𝒌 𝐩𝐚𝐥𝐚𝐯𝐫𝐚 𝐛𝐢𝐧á𝐫𝐢𝐚 é muitas vezes referido como PCM Pulse Code Modulation Uma possível implementação em hardware do mapeamento mostrado na figura abaixo é discutida no slide 18 de httpswwwfccdecastrocombrpdfSSAula316032020pdf 𝑥𝑞𝑡 III Codificação PCM Pulse Code Modulation Processo através do qual cada 𝑛ésima amostra no sinal quantizado 𝑥𝑞 𝑛 é codificada mapeada em uma respectiva palavra binária de 𝑁 log2𝑀 bits sendo 𝑀 2𝑁 o número de valores 𝑚𝑘 de amplitudes quantizadas utilizadas no processo de quantização com 𝑘 01 𝑀 1 Por exemplo a figura abaixo mostra uma possível codificação adotada no mapeamento 𝒎𝒌 𝐩𝐚𝐥𝐚𝐯𝐫𝐚 𝐛𝐢𝐧á𝐫𝐢𝐚 em um ADC hipotético que gera uma sequência de palavras binárias de 𝑁 3 bitsamostra 𝑀 2𝑁 8 respectivos valores 𝑚𝑘 de amplitudes quantizadas 𝑘 01 𝑀 1 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 14 Pulse Code Modulation PCM seguida de compressão de dados Após o processo de codificação PCM na grande maioria das situações práticas alguma forma de compressão é aplicada na sequência de palavras binárias gerada A compressão por entropia que estudaremos adiante neste capítulo mostrada abaixo em um exemplo para um sinal de áudio é uma das possíveis formas de compressão de dados utilizada Note abaixo na coluna Codificação original que as palavras binárias de 4 bits com maior frequência de ocorrência são remapeadas em palavras binárias na coluna Compressão Código com menor número de bits Este processo reduz portanto o número de bits necessários na sequência de bits que representa o sinal Quando um sinal analógico 𝑚𝑡 de áudio ou vídeo é amostrado a uma frequência de amostragem 𝑓𝑠 muito maior do que o 𝑁𝑦𝑞𝑢𝑖𝑠𝑡 𝑅𝑎𝑡𝑒 2𝑓𝑀 ver slide 9 o sinal amostrado 𝑚 𝑛 resultante exibe uma alta correlação entre amostras adjacentes O significado desta alta correlação é que na média o sinal não varia rapidamente de uma amostra para a outra A consequência disto é que quando amostras altamente correlacionadas são codificadas em um codificador PCM padrão a sequência resultante de bits apresentará informação redundante desnecessária Portanto mensagens que não são absolutamente essenciais à transmissão de informação são geradas como resultado do processo de codificação Remover esta redundância resulta em um aumento da eficiência do sinal codificado em transportar informação no sentido de que serão necessários menos bits para transportar a informação Pulse Code Modulation com compressão diferencial de dados DPCM Differential PCM Se conhecemos uma parcela suficiente do sinal redundante 𝑚 𝑛 podemos inferir o resto do sinal ou pelo menos tentar fazer uma estimativa provável Em particular se conhecemos o comportamento passado de um sinal até um determinado ponto no tempo então é possível fazer alguma inferência sobre seus valores futuros Tal processo de inferência é conhecido como predição Embora existam inúmeros métodos de predição no contexto de codificação DPCM nos limitaremos à denominada Predição Linear Em um codificador DPCM situado no TX digital o bloco Preditor Linear efetua a predição de uma amostra futura que é obtida como uma combinação linear de um conjunto de amostras passadas conforme indicado abaixo no diagrama funcional de um codificador DPCM 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 15 Consideremos a situação em que o sinal analógico 𝑚𝑡 seja amostrado a uma frequência de amostragem 𝑓𝑠 Τ 1 𝑇𝑠 muito maior do que o 𝑁𝑦𝑞𝑢𝑖𝑠𝑡 𝑅𝑎𝑡𝑒 2𝑓𝑀 ver slide 9 Esta superamostragem produz uma sequência de amostras 𝑚𝑛 altamente correlacionadas e espaçadas no tempo de um intervalo 𝑇𝑠 Esta alta correlação entre as amostras da sequência 𝑚𝑛 na entrada do codificador DPCM mostrado em a ao lado permite que o decodificador DPCM mostrado em b efetue a predição de valores futuros de 𝑚𝑛 a partir da sequência de bits 𝑦 𝑛 recebida do codificador DPCM e gerada no codificador através da diferença entre o sinal original 𝑚𝑛 e sua predição 𝑚 𝑛 Note em a que o a entrada do quantizador 𝑄 não é o sinal a ser codificado mas sim o sinal de erro 𝑒n 𝑚n 𝑚n que é a diferença entre o sinal super amostrado 𝑚n na entrada do codificador e a predição 𝑚n do sinal 𝑚n Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 16 Pulse Code Modulation com compressão diferencial de dados DPCM Differential PCM 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 ෩𝑚 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DPCM no TX Decodificador DPCM no RX No codificador DPCM em a o sinal 𝑚n é o resultado do processo de predição linear aplicado sobre um conjunto de amostras passadas do sinal 𝑚𝑞 𝑛 este último sendo uma versão quantizada do sinal 𝑚n O sinal de erro 𝑒𝑛 é denominado de erro de predição visto que seu valor representa a incapacidade do Preditor Linear em predizer 𝑚n com exatidão 𝑄 efetua o processo de quantização do erro de predição 𝑒𝑛 gerando o erro de predição quantizado 𝑒𝑞 𝑛 Como ocorre em todo e qualquer processo de quantização um erro de quantização na forma de um ruído aleatório 𝑞𝑒𝑛 é superposto ao sinal de saída do quantizador 𝑄 de modo que a saída do quantizador 𝑄 pode ser descrita como 𝑒𝑞𝑛 𝑄 𝑒 𝑛 𝑒𝑛 𝑞𝑒𝑛 6 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 17 Pulse Code Modulation com compressão diferencial de dados DPCM Differential PCM 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 ෩𝑚 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DPCM no TX Decodificador DPCM no RX O sinal de entrada do Preditor Linear do codificador DPCM mostrado em a é formado pela soma do sinal predito 𝑚𝑛 e da saída do quantizador 𝑒𝑞𝑛 ie 𝑚𝑞𝑛 𝑚𝑛 𝑒𝑞𝑛 7 Substituindo 6 em 7 𝑚𝑞𝑛 𝑚𝑛 𝑒𝑛 𝑞𝑒𝑛 8 E do somador à esquerda em a temos que 𝑒 𝑛 𝑚 𝑛 𝑚𝑛 logo substituindo em 8 obtemos 𝑚𝑞𝑛 𝑚𝑛 𝑒𝑛 𝑒𝑛 𝑞𝑒𝑛 𝑚𝑞𝑛 𝑚𝑛 𝑞𝑒𝑛 9 Portanto de 9 inferese que não importa a capacidade de predição do Preditor Linear no codificador mostrado em a o sinal 𝑚𝑞𝑛 aplicado na sua entrada difere do sinal 𝑚𝑛 original apenas do valor do erro de quantização 𝑞𝑒𝑛 Note que ao aplicar a saída do quantizador 𝑒𝑞 𝑛 𝑄 𝑒 𝑛 ao conversor AD do codificador DPCM mostrado em a obtemos sequência 𝑦𝑛 de bits correspondentes às mensagens codificadas em DPCM Após ser submetida aos processos dos demais blocos funcionais mostrados no slide 2 codificador de canal modulador amplificador de potência canal de transmissão amplificador de sinal demodulador e decodificador de canal a sequência de bits 𝑦 𝑛 na saída do codificador DPCM mostrado em a é recebida na entrada 𝑦 𝑛 do decodificador DPCM mostrado em b Quando o canal de transmissão não gera degradação na onda EM EM eletromagnética que nele se propaga e que transporta a informação a ser transmitida da origem TX ao destino RX a sequência de bits 𝑦 𝑛 recebida na entrada do decodificador DPCM no RX corresponde à sequência de bits 𝑦 𝑛 na saída do codificador DPCM no TX ie 𝑦 𝑛 𝑦 𝑛 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 18 Pulse Code Modulation com compressão diferencial de dados DPCM Differential PCM 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 ෩𝑚 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DPCM no TX Decodificador DPCM no RX A seguir o conversor DA do decodificador DPCM mostrado em b converte a sequência de bits 𝑦 𝑛 recebida na entrada do decodificador DPCM em uma aproximação ෦ 𝑒𝑞 𝑛 do erro de predição quantizado 𝑒𝑞 𝑛 É uma aproximação porque o canal de transmissão pode degradar a informação transportada pela onda EM que nele se propaga ao ponto de o demodulador e o decodificador de canal não conseguirem recuperar o sinal original O processo de predição efetuado no decodificador DPCM é idêntico ao processo de predição realizado no codificador A saída 𝑚𝑞𝑛 do decodificador em b é uma aproximação quantizada de 𝑚 𝑛 na entrada do codificador em a e é dada pela soma do sinal predito ෩𝑚𝑛 com o erro de predição quantizado ෦ 𝑒𝑞 𝑛 𝑚𝑞𝑛 ෦ 𝑒𝑞 𝑛 ෩𝑚 𝑛 Se o canal de transmissão não introduz nenhuma degradação então 𝑚𝑞𝑛 𝑚𝑞𝑛 No âmbito da implementação em hardware de um codificador DPCM uma possível abordagem é o sinal original 𝑚𝑛 resultar da digitalização de um sinal analógico 𝑚 𝑡 através de um AD de 16 bits prévio ao codificador DPCM mostrado em a de modo que o ruído de quantização em 𝑚𝑛 resulte mínimo ie resulte em uma alta relação sinal ruído p 𝑚𝑛 𝑆𝑁𝑅𝑄 96 dB ver equação 5 slide 11 Nesta situação o sinal 𝑚 𝑛 pode ser representado por uma variável em ponto flutuante e o quantizador 𝑄 e o preditor linear podem ser implementados em um microprocessador ARM por exemplo com todas as demais variáveis de sinal 𝑒 𝑛 𝑚𝑞 𝑛 𝑚 𝑛 e 𝑒𝑞 𝑛 também sendo representadas em ponto flutuante Dado que todos os sinais já são digitais o bloco AD do codificador passa a ser um bloco que converte a variável 𝑒𝑞 𝑛 em ponto flutuante para uma variável inteira com um reduzido número de bits número apenas o necessário para acomodar a faixa de excursão de amplitudes de 𝑒𝑞 𝑛 Mesma abordagem é aplicável ao decodificador DPCM mostrado em b 9A Consideremos um codificador PCM ver slide 13 que adota um quantizador 𝑄 com 𝑀 2𝑁 níveis de quantização e passo de quantização 𝑆 𝑉𝐻 𝑉𝐿𝑀 sendo 𝑉𝐻 𝑉𝐿 a faixa dinâmica do sinal na entrada de 𝑄 e 𝑁 o número de bits da palavra binária que representa cada amostra quantizada ver discussão nos slides 10 e 11 Consideremos agora o quantizador 𝑄 de um codificador DPCM conforme a ao lado Se o Preditor Linear prediz 𝑚𝑛 com alguma exatidão então a faixa de excursão de amplitude 𝑽𝑯 𝑽𝑳 do sinal 𝒆𝒏 na entrada de 𝑸 será muito menor do que a faixa de excursão de amplitude do sinal 𝒎𝒏 na entrada do quantizador 𝑸 do codificador PCM Portanto para um mesmo número 𝑀 de níveis de quantização o passo de quantização 𝑆 𝑉𝐻 𝑉𝐿𝑀 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 19 A redução de bits obtida com DPCM em comparação ao PCM 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 ෩𝑚 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DPCM no TX Decodificador DPCM no RX A consequência da asserção no parágrafo anterior é que se um codificador DPCM apresenta a mesma relação sinalruído de quantização 𝑆𝑁𝑅𝑄 de um codificador PCM então certamente o número de bits 𝑁DPCM da palavra binária que representa cada amostra quantizada no codificador DPCM será menor do que o número de bits 𝑁PCM da palavra binária que representa cada amostra quantizada no codificador PCM O quanto 𝑁DPCM será menor do que 𝑁PCM depende das características estatísticas do sinal 𝑚 𝑛 e principalmente da ordem de predição do preditor linear O quão precisa é a predição determina portanto o grau de compressão de bits obtido com um codificador DPCM Para um sinal de voz digitalizado c 𝑓𝑠 8𝐾𝐻𝑧 um preditor linear de ordem 5 em um codificador DPCM necessita de 2 bits a menos por amostra do que um codificador PCM Deste modo um sistema DPCM economiza 8𝐾𝐻𝑧 2bits 16Kbps na taxa de transmissão resultando em menor banda passante que o sistema PCM Nos próximos slides passaremos a analisar o processo de predição linear será menor para o codificador DPCM do que para o codificador PCM o que implica da equação 4 do slide 11 que a potência do ruído de quantização eq2 𝑆2 12 é menor no codificador DPCM do que no codificador PCM Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 20 Predição Linear 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 a Codificador DPCM no TX 𝑢𝑛 b Preditor linear do Codificador DPCM 𝑚 𝑛 𝐿 8 𝑊 𝑤0 𝑤1 𝑤2 𝑤3 𝑤4 𝑤5 𝑤6 𝑤7 𝑇 Em a abaixo é mostrado um codificador DPCM e em b é mostrada a arquitetura do bloco Preditor Linear adotado no codificador No exemplo em questão o preditor linear é um filtro FIR httpsptwikipediaorgwikiFiltroFIR de ordem 𝐿 8 ie o seu buffer que armazena as amostras passadas de 𝑚𝑞 𝑛 representado pelo vetor 𝑢 e o vetor de coeficientes 𝑊 do filtro FIR são ambos de tamanho 𝐿 8 Nota Vamos usar a representação 𝑢𝑛 para expressar a 𝑛ésima amostra da sequência 𝑢 porque no âmbito de predição linear há descrição de sinais através de vetores e matrizes e a representação 𝑢𝑛 para a sequência de amostras 𝑢 poderia gerar confusão com a representação vetorialmatricial 𝑢 𝑢𝑛 𝑢𝑛 1 𝑢𝑛 2 𝑢𝑛 3 𝑢𝑛 4 𝑢𝑛 5 𝑢𝑛 6 𝑢𝑛 7 𝑇 𝑢 𝑛 1 𝑊𝑇𝑢 𝑘0 𝐿1 𝑤𝑘𝑢𝑛 𝑘 A saída 𝑢 𝑛 1 do preditor linear é o valor da amostra predita e é dada por 10 Os coeficientes 𝑊 do preditor são definidos de forma a minimizar de uma função de custo 𝐽 ver discussão sobre o conceito de função de custo no slide 122 de httpswwwfccdecastrocombrpdfCEAula16a1815122020p df e demais orientações no link lá indicado No caso de predição linear conforme mostra a figura ao lado a função de custo 𝐽 mede o erro médio quadrático 𝐸 𝑒2 entre a o valor 𝑢 𝑛 1 estimado p a predição da amostra que ocorre no instante 𝑛 1 e o valor 𝑢 𝑛 1 𝑑𝑛 da amostra que efetivamente ocorre no instante 𝑛 1 onde 𝑑 𝑛 𝑢 𝑛 1 é a saída desejada do preditor 𝑒 𝑛 𝑑 𝑛 𝑢 𝑛 1 𝑢 𝑛 1 𝑢 𝑛 1 é o erro de predição no instante discreto 𝑛 e 𝐸 é o operador que retorna a esperança estatística de seu argumento ver httpsenwikipediaorgwikiExpectedvalue De maneira semelhante ao teorema do cálculo em que os valores de 𝑥 que fazem 𝑑𝑓𝑥 𝑑𝑥 0 correspondem à pontos de mínimo de uma função quadrática 𝑓𝑥 no caso vetorial o operador gradiente é aplicado à função de custo 𝐽 com o intuito de obter os coeficientes 𝑤𝑘 do filtro FIR que minimizam 𝐽 Isto é obtido da solução da equação 𝐽 0 onde 𝐽 𝐽 𝑊 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 21 Predição Linear 𝑚𝑞 𝑛 𝑢𝑛 𝑚 𝑛 𝐿 8 𝑊 𝑤0 𝑤1 𝑤2 𝑤3 𝑤4 𝑤5 𝑤6 𝑤7 𝑇 𝑢 𝑢𝑛 𝑢𝑛 1 𝑢𝑛 2 𝑢𝑛 3 𝑢𝑛 4 𝑢𝑛 5 𝑢𝑛 6 𝑢𝑛 7 𝑇 𝑊 𝑹1𝑃 11 onde 𝑹 é uma matriz 𝐿 𝐿 denominada de matriz de autocorrelação da sequência de amostras representada no vetor 𝑢 e 𝑃 é um vetor 𝐿 1 denominado de vetor de correlação cruzada entre a sequência de amostras representada no vetor 𝑢 e o valor 𝑢 𝑛 1 da amostra que efetivamente ocorre no instante 𝑛 1 Veremos nos próximo slides como determinar 𝑹 e 𝑃 para um preditor linear de ordem 𝐿 A solução de 𝐽 𝑊 0 é dada pela denominada Equação de WienerHopf ver httpsenwikipediaorgwikiWienerfilter Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 22 Predição Linear 𝑚𝑞 𝑛 𝑢𝑛 𝑚 𝑛 𝐿 8 𝑊 𝑤0 𝑤1 𝑤2 𝑤3 𝑤4 𝑤5 𝑤6 𝑤7 𝑇 𝑢 𝑢𝑛 𝑢𝑛 1 𝑢𝑛 2 𝑢𝑛 3 𝑢𝑛 4 𝑢𝑛 5 𝑢𝑛 6 𝑢𝑛 7 𝑇 𝑊 𝑹1𝑃 11 Para determinar a matriz de autocorrelação 𝑹 de dimensão 𝐿 𝐿 e o vetor de correlação cruzada 𝑃 de dimensão 𝐿 1 utiliza se um conjunto de 𝑁𝑆𝑎𝑚𝑝 amostras passadas mais recentes da sequência de amostras 𝑢 𝑛 𝑚𝑞 𝑛 sendo 𝑁𝑆𝑎𝑚𝑝 suficientemente grande para que 𝑹 capte a autocorrelação da sequência de amostras 𝑢 𝑛 𝑚𝑞 𝑛 As 𝑁𝑆𝑎𝑚𝑝 amostras da sequência 𝑢 𝑛 são transformadas em um conjunto de 𝑁𝑉𝑒𝑡 𝑁𝑆𝑎𝑚𝑝 1 vetores 𝑢𝑛 𝑘 de dimensão 𝐿 1 obtendose a matriz 𝑹 e o vetor 𝑃 através de 𝑹 e 𝑃 são reavaliados a cada 𝑁𝑝 predições sendo 𝑁𝑝 determinado experimentalmente com base em um compromisso entre minimização da complexidade computacional e precisão da predição A cada reavaliação de 𝑹 e 𝑃 os novos coeficientes do filtro 𝑊 são obtidos e enviados ao receptor através do canal de comunicação Note que a partir da inicialização de um sistema DPCM devido à saída do preditor ser realimentada para a sua entrada tanto o preditor do TX quanto o preditor do RX necessitam de um razoável número de amostras até que consigam reduzir o erro de predição a níveis aceitáveis 𝑹 1 𝑁𝑉𝑒𝑡 𝑘0 𝑁𝑉𝑒𝑡1 𝑢𝑛 𝑘 𝑢𝑇𝑛 𝑘 12 𝑃 1 𝑁𝑉𝑒𝑡 1 𝑘0 𝑁𝑉𝑒𝑡2 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 𝑢𝑛 𝑘 é a saída desejada 𝑑 𝑛 do preditor p o vetor 𝑢𝑛 𝑘 1 13 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 23 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 Codificador DPCM no TX Exemplo 1 Consideremos o codificador DPCM mostrado em a ao lado A sequência de amostras na entrada do bloco Preditor Linear é dada por 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 Pedese a Determine o valor de 𝑚 𝑛 𝑢 𝑛 1 que é a estimativa da predição da amostra que ocorre no instante 𝑛 1 b Determine o erro de predição 𝑒 𝑛 para 𝑚 𝑛 obtido em a sabendo que o valor da amostra que efetivamente ocorre no instante 𝑛 1 é 𝑢 𝑛 1 1414 O preditor linear é de ordem 𝐿 2 e utiliza 𝑁𝑆𝑎𝑚𝑝 11 amostras consecutivas de 𝑚𝑞 𝑛 para a definição da matriz de correlação 𝑹 Dica Dado 𝑹 2 2 temos que 𝑹 𝑟00 𝑟01 𝑟10 𝑟11 𝑹1 1 𝑟00𝑟11𝑟01𝑟10 𝑟11 𝑟01 𝑟10 𝑟00 Predição Linear Solução a A estrutura de dados para a predição é composta por 𝑁𝑉𝑒𝑡 𝑁𝑆𝑎𝑚𝑝 1 10 vetores 𝑢𝑛 𝑘 cada vetor 𝑢𝑛 𝑘 possui 𝐿 2 componentes sendo 𝐿 a ordem do preditor Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 24 Predição Linear 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 Em conformidade com a equação 12 os 𝑁𝑉𝑒𝑡 𝑁𝑆𝑎𝑚𝑝 1 10 vetores 𝑢𝑛 𝑘 resultam Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 25 Predição Linear 𝑘 0 𝑘 1 𝑘 2 𝑘 3 𝑘 4 Determinando as 𝑁𝑉𝑒𝑡 𝑁𝑆𝑎𝑚𝑝 1 10 matrizes 𝑢𝑛 𝑘 𝑢𝑇𝑛 𝑘 usadas na formação de matriz de autocorrelação 𝑹 de dimensão 𝐿 𝐿 em conformidade com a equação 12 Reproduzindo 𝑢 𝑛 para efeito de facilitar a visualização da sequência de amostras 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 26 Predição Linear 𝑘 5 𝑘 6 𝑘 7 𝑘 8 𝑘 9 𝑹 1 10 𝑘0 9 𝑢 𝑛 𝑘 𝑢𝑇 𝑛 𝑘 1 10 179970 141400 141400 219970 17997 14140 14140 21997 Substituindo na equação 12 as 𝑁𝑉𝑒𝑡 𝑁𝑆𝑎𝑚𝑝 1 10 matrizes 𝑢𝑛 𝑘 𝑢𝑇𝑛 𝑘 acima determinadas obtemos a matriz de autocorrelação 𝑹 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 27 Determinando os 𝑁𝑉𝑒𝑡 1 9 vetores 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 usados na formação do vetor de correlação cruzada 𝑃 de dimensão 𝐿 1 em conformidade com a equação 13 reproduzida abaixo por facilidade de visualização 𝑃 1 𝑁𝑉𝑒𝑡 1 𝑘0 𝑁𝑉𝑒𝑡2 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 1 9 𝑘0 8 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 𝑘 0 Predição Linear 𝑢𝑛 𝑘 é a saída desejada 𝑑 𝑛 do preditor p o vetor 𝑢𝑛 𝑘 1 𝑘 1 𝑘 2 𝑘 3 𝑘 4 Reproduzindo 𝑢 𝑛 para efeito de facilitar a visualização da sequência de amostras 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 28 Predição Linear 𝑘 5 𝑘 6 𝑘 7 𝑘 8 Substituindo na equação 13 os 𝑁𝑉𝑒𝑡 1 9 vetores 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 acima determinados obtemos do vetor de correlação cruzada 𝑃 𝑃 1 𝑁𝑉𝑒𝑡 1 𝑘0 𝑁𝑉𝑒𝑡2 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 1 9 𝑘0 8 𝑢𝑛 𝑘𝑢𝑛 𝑘 1 1 9 113120 0 12569 0 𝑊 𝑹1𝑃 17997 14140 14140 21997 1 12569 0 11226 07216 07216 09185 12569 0 14110 09070 Substituindo na equação 11 do slide 21 o valor obtido para 𝑹 slide 26 e substituindo na equação 11 o valor obtido para 𝑃 acima obtemos o vetor 𝑊 cujos componentes são os coeficientes do filtro FIR do preditor Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 29 Predição Linear O valor estimado 𝑢 𝑛 1 para a 1ª amostra subsequente à sequencia de amostras 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 é dado pela equação 10 do slide 20 𝑢 𝑛 1 𝑊𝑇𝑢 𝑘0 𝐿1 𝑤𝑘𝑢𝑛 𝑘 𝑘0 1 𝑤𝑘𝑢𝑛 𝑘 𝑤𝑜𝑢 𝑛 𝑤1𝑢 𝑛 1 14110 0 09070 1414 12825 b A sequencia de amostras 𝑢 𝑛 incluindo o valor da amostra 𝑢 𝑛 1 1414 que efetivamente ocorre no instante 𝑛 1 é 𝑢 𝑛 𝑚𝑞 𝑛 2 1414 0 1414 2 1414 0 1414 2 1414 0 1414 Portanto o erro de predição no instante discreto 𝑛 1 é 𝑒 𝑛 𝑑 𝑛 𝑢 𝑛 1 𝑢 𝑛 1 𝑢 𝑛 1 1414 12825 01315 Alternativamente no link Videoaula DPCM Profa Cristina De Castro encontrase disponível uma videoaula com a revisão passo a passo da solução do Exemplo 1 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 30 Quando o sinal analógico 𝑚𝑡 é amostrado a uma frequência de amostragem 𝑓𝑠 muitíssimo maior do que o 𝑁𝑦𝑞𝑢𝑖𝑠𝑡 𝑅𝑎𝑡𝑒 2𝑓𝑀 ver slide 9 caracterizando uma superamostragem o sinal superamostrado 𝑚 𝑛 resultante exibe uma altíssima correlação entre amostras adjacentes Esta altíssima correlação entre as amostras reduz drasticamente o erro de predição do bloco Preditor Linear ao ponto de a faixa de excursão de amplitude 𝑉𝐻 𝑉𝐿 do sinal 𝑒𝑛 na entrada do quantizador 𝑄 tender a zero permitindo reduzir o número de níveis de quantização 𝑀 2𝑁 para 𝑀 2 e portanto as palavras binárias na saída 𝑦 𝑛 do codificador DM são palavras binárias de tamanho 𝑁 1 bit Uma aplicação clássica de DM é o link de voz do space shuttle da NASA ver httpswwwfccdecastrocombrpdfSSGTDMpdf Modulação Delta DM Delta Modulation 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DM no TX Decodificador DM no RX 𝑚𝑞 𝑛 1 𝑧1 𝑧1 𝑒𝑞𝑛 𝑄𝑒𝑛 𝑒𝑛 d O sistema DM provê uma aproximação 𝑚𝑞𝑛 em forma de escada com tamanho de degrau 𝛿 para o sinal superamostrado 𝑚 𝑡 𝑚𝑞𝑛 𝑚𝑡 c Transmitância do quantizador acumulador integrador acumulador integrador ෩𝑚 𝑛 ෦ 𝑚𝑞 𝑛 1 AD 1 bit DA 1 bit Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 31 Modulação Delta DM Delta Modulation 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DM no TX Decodificador DM no RX 𝑚𝑞 𝑛 1 𝑧1 𝑧1 𝑒𝑞𝑛 𝑄𝑒𝑛 𝑒𝑛 d O sistema DM provê uma aproximação 𝑚𝑞𝑛 em forma de escada com tamanho de degrau 𝛿 para o sinal superamostrado 𝑚 𝑡 𝑚𝑞𝑛 𝑚𝑡 c Transmitância do quantizador acumulador integrador acumulador integrador ෩𝑚 𝑛 ෦ 𝑚𝑞 𝑛 1 AD 1 bit DA 1 bit O erro de predição 𝑒n na entrada do quantizador 𝑄 do codificador DM é 𝑒𝑛 𝑚𝑛 𝑚𝑞𝑛 1 14 A saída 𝑒𝑞𝑛 do quantizador é dada por 𝑒𝑞𝑛 𝛿sgn𝑒𝑛 15 sgn 𝑥 ቊ1 𝑥 0 1 𝑥 0 onde sendo 𝛿 o tamanho do degrau da escada do sinal 𝑚𝑞𝑛 que aproxima o sinal superamostrado 𝑚 𝑡 ver d abaixo Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 32 Modulação Delta DM Delta Modulation 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DM no TX Decodificador DM no RX 𝑚𝑞 𝑛 1 𝑧1 𝑧1 𝑒𝑞𝑛 𝑄𝑒𝑛 𝑒𝑛 d O sistema DM provê uma aproximação 𝑚𝑞𝑛 em forma de escada com tamanho de degrau 𝛿 para o sinal superamostrado 𝑚 𝑡 𝑚𝑞𝑛 𝑚𝑡 c Transmitância do quantizador acumulador integrador acumulador integrador ෩𝑚 𝑛 ෦ 𝑚𝑞 𝑛 1 AD 1 bit DA 1 bit O bloco preditor 𝑧1 é um preditor pela última amostra que no instante 𝑛 copia para a sua saída 𝑚 𝑛 a amostra anterior 𝑚𝑞 𝑛 1 presente em sua entrada no instante 𝑛 1 significado de 𝑧1 ver transformada Z em A entrada do preditor 𝑧1 é dada por 𝑚𝑞 𝑛 𝑚𝑞 𝑛 1 𝑒𝑞 𝑛 16 A realimentação da saída 𝑚 𝑛 do preditor 𝑧1 à sua entrada através do somador Σ forma um acumulador httpswwwfccdecastrocombrpdfSSaula23a2625062020pdf 𝑚𝑞𝑛 𝑖0 𝑛 𝑒𝑞 𝑛 𝑚𝑞 𝑛 1 𝑖0 𝑛 𝑒𝑞 𝑛 𝑖0 𝑛 𝑚𝑞 𝑛 1 𝑖0 𝑛 𝑚𝑞 𝑛 1 0 17 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 33 Modulação Delta DM Delta Modulation 𝑚 𝑛 𝑒 𝑛 𝑒𝑞 𝑛 𝑚 𝑛 𝑚𝑞 𝑛 𝑦 𝑛 𝑦 𝑛 ෦ 𝑒𝑞 𝑛 ෦ 𝑚𝑞 𝑛 Codificador DM no TX Decodificador DM no RX 𝑚𝑞 𝑛 1 𝑧1 𝑧1 𝑒𝑞𝑛 𝑄𝑒𝑛 𝑒𝑛 d O sistema DM provê uma aproximação 𝑚𝑞𝑛 em forma de escada com tamanho de degrau 𝛿 para o sinal superamostrado 𝑚 𝑡 𝑚𝑞𝑛 𝑚𝑡 c Transmitância do quantizador acumulador integrador acumulador integrador ෩𝑚 𝑛 ෦ 𝑚𝑞 𝑛 1 AD 1 bit DA 1 bit No decodificador DM em b cada bit é transformado pelo DA em um pulso 𝛿𝛿 que representa o sinal ෦ 𝑒𝑞 𝑛 O acumulador gera então o sinal ෦ 𝑚𝑞 𝑛 em sua saída que é uma aproximação quantizada de 𝑚 𝑛 na entrada do codificador DM em a ෦ 𝑚𝑞 𝑛 ෦ 𝑒𝑞 𝑛 ෩𝑚 𝑛 18 Sistemas DM são sujeitos a dois tipos de erro de quantização ver figura abaixo I Distorção por declividade excessiva em 𝑚𝑡 slopeoverload distortion No intervalo de tempo 𝑡1 a 𝑡2 o valor de 𝛿 é muito pequeno para que 𝑚𝑞𝑛 consiga acompanhar a alta razão de variação de 𝑚𝑡 II Ruído granular No intervalo de tempo 𝑡3 a 𝑡4 a razão de variação de 𝑚𝑡 é pequena e o valor de 𝛿 é desnecessariamente grande gerando variações 𝛿 em torno do valor de 𝑚𝑡 que representa um ruído de amplitude 𝛿 sobreposto ao sinal 𝑚𝑡 Percebese portanto que existe a necessidade de um valor maior para 𝛿 objetivando acomodar um sinal 𝑚𝑡 com alta razão de variação enquanto que um menor valor de 𝛿 é necessário para representar com precisão um sinal 𝑚𝑡 aproximadamente invariável no tempo Neste contexto o valor de 𝛿 adequado resulta em um compromisso entre distorção slopeoverload e ruído granular Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 34 Distorção de sinal na Modulação Delta DM Delta Modulation 𝑚𝑡 𝑚𝑞𝑛 distorção slope overload ruído granular 𝑡1 𝑡𝑠 𝑡2 𝑡3 𝑡4 𝛿 O sistema ADM objetiva otimizar 𝛿 para que o mesmo se adapte à dinâmica do sinal 𝑚𝑡 minimizando o compromisso entre distorção slopeoverload e ruído granular referido no slide anterior Um sistema ADM tipicamente utiliza a seguinte regra de adaptação para 𝛿 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 35 Modulação Delta Adaptativa ADM Adaptive Delta Modulation 𝑚𝑡 𝑚𝑞𝑛 distorção slope overload ruído granular 𝑡1 𝑡𝑠 𝑡2 𝑡3 𝑡4 𝛿 𝛿𝑛 𝛿𝑛1𝛾𝜌𝑏𝑛𝜌𝑏𝑛1 19 onde 𝛾 1 é uma constante determinada experimentalmente objetivando a redução do erro de quantização 𝜌 𝑏 2𝑏 1 com 𝑏𝑛 e 𝑏𝑛1 sendo respectivamente o último e o penúltimo bit gerados na saída 𝑦n do AD do codificador de um sistema DM Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 36 Modulação Delta Adaptativa ADM Adaptive Delta Modulation 𝑚𝑡 𝑚𝑞𝑛 distorção slope overload ruído granular 𝑡1 𝑡𝑠 𝑡2 𝑡3 𝑡4 𝛿 𝛿𝑛 𝛿𝑛1𝛾𝜌𝑏𝑛𝜌𝑏𝑛1 19 com 𝜌 𝑏 2𝑏 1 Assim se em um determinado instante 𝑛 começa a ocorrer distorção slopeoverload então forçosamente 𝑏𝑛 𝑏𝑛1 𝜌 𝑏𝑛 𝜌 𝑏𝑛1 1 de 19 𝛿𝑛 𝛿𝑛1𝛾 Portanto 𝛿𝑛 é multiplicado por 𝛾 aumentando 𝛿 e reduzindo a distorção slopeoverload Por outro lado se em um determinado instante 𝑛 começa a ocorrer ruído granular então forçosamente 𝑏𝑛 𝑏𝑛1 𝜌 𝑏𝑛 𝜌 𝑏𝑛1 1 de 19 𝛿𝑛 𝛿𝑛1 Τ 1 𝛾 Portanto 𝛿𝑛 é dividido por 𝛾 diminuindo 𝛿 e reduzindo o ruído granular Entropia uma possível medida de informação Postulado II Eventos que ocorrem raramente no espaço amostral de uma variável aleatória contêm mais informação do que eventos que ocorrem frequentemente Por exemplo O sol nasceu à leste hoje pela manhã evento frequente pouca informação Porto Alegre foi atingida por um terremoto hoje pela manhã evento raro maior conteúdo de informação Amostragem Quantização Codificação Fonte de Informação Variável Aleatória X A Entropia proposta por Hartley em 1928 é uma medida logarítmica de informação que reflete este raciocínio intuitivo Postulado I A observação da ocorrência de um evento do espaço amostral de uma variável aleatória nos dá informação Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 37 Conforme discutimos nos slides 56 e 7 do Cap I é necessário que o Codificador de Fonte efetue a compressão da informação a ser transmitida de modo a minimizar a largura do espectro BW da onda EM que se propaga no canal de transmissão Neste contexto é necessário definir o que se entende por informação Consideremos o sinal de uma fonte de informação áudio vídeo submetida ao processo de amostragem quantização e codificação do Codificador de Fonte conforme figura abaixo A sequência de amostras quantizadas em amplitude e portanto a sequência de palavras binárias na saída do Codificador de Fonte pode ser interpretada como uma variável aleatória 𝑋 Neste contexto dois postulados nos auxiliam a definir informação Ao registrarmos a sequência de amostras quantizadas em amplitude e portanto ao registrarmos a sequência de palavras binárias de 𝑁 bits correspondentes em um Codificador de Fonte que opera com 𝑀 níveis de quantização após o registro de um número suficiente de amostras podemos fazer um estudo estatístico da probabilidade de ocorrência de cada uma das 𝑀 possíveis amostras mensagens de 𝑁 log2𝑀 bits A saída do quantizador pode ser considerada uma variável aleatória discreta 𝑋 com espaço de amostras definido pelo conjunto 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 de 𝑀 mensagens 𝑀 palavras binárias 𝑚𝑘 com probabilidade de ocorrência 𝑝𝑘 𝑘 01 𝑀 1 conforme exemplo na tabela abaixo para um Codificador de Fonte que adota um ADC de 𝑁 3 bits 𝑀 8 níveis de quantização Segundo Hartley a autoinformação ℎ𝑚𝑘 implícita na ocorrência de uma mensagem palavra binária 𝑚𝑘 com probabilidade de ocorrência 𝑝𝑘 é definida por Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 38 Amostragem Quantização Codificação Fonte de Informação Variável Aleatória X ℎ 𝑚𝑘 log2𝑝𝑘 bits 20 onde log2 𝑥 ln𝑥 ln2 Analisando a equação 20 inferese que I Como 0 𝑝𝑘 1 ℎ𝑚𝑘 é sempre um número positivo II ℎ𝑚𝑘 é medida em bits devido a função logarítmica de base 2 III Como log2𝑢 é uma função monotonicamente crescente com 𝑢 a autoinformação ℎ 𝑚𝑘 log2𝑝𝑘 de uma mensagem palavra binária rara é maior do que a de uma mensagem palavra binária frequente conforme exemplo abaixo para um Codificador de Fonte que adota um ADC de 𝑁 3 bits 𝑀 8 níveis de quantização 𝒑𝒌 005 01 015 02 025 015 0075 0025 palavra binária mensagem 𝑚𝑘 000 001 010 011 100 101 110 111 ℎ 𝑚𝑘 log2 𝑝𝑘 4322 3322 2737 2322 2000 2737 3737 5322 mensagem palavra binária frequente menor autoinformação ℎ𝑚𝑘 mensagem palavra binária rara maior autoinformação ℎ𝑚𝑘 Entropia uma possível medida de informação A média da autoinformação ℎ 𝑚𝑘 log2𝑝𝑘 transportada por cada uma das 𝑀 mensagens 𝑚𝑘 do conjunto 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 é denominada entropia da variável aleatória 𝑋 ou equivalentemente entropia do conjunto 𝑿 de mensagens Assim a entropia 𝐻𝑋 da variável aleatória 𝑋 cujo espaço de amostras é o conjunto 𝑋 de 𝑀 mensagens é dada por Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 39 Entropia uma possível medida de informação 𝐻 𝑋 𝐸 ℎ 𝑚𝑘 𝐸 log2 𝑝𝑘 𝑘0 𝑀1 𝑝𝑘log2 𝑝𝑘 bitsmensagem onde 𝐸 é o operador estatístico que retorna o valor esperado do argumento ver httpsptwikipediaorgwikiValoresperado Note que se as 𝑀 mensagens apresentam probabilidade de ocorrência iguais mensagens equiprováveis então 𝑝𝑘 1𝑀 para 𝑘 01 𝑀 1 e daí 21 simplifica para 𝐻 𝑋 𝑘0 𝑀1 1 𝑀 log2 1 𝑀 1 𝑀 𝑘0 𝑀1 log2 𝑀 21 22 Por exemplo para um Codificador de Fonte que adota um ADC de 𝑁 2 bits 𝑀 4 níveis de quantização em que o sinal digitalizado apresenta níveis de amplitude equiprováveis temos que 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚2 𝑚3 𝑝0 𝑝1 𝑝2 𝑝3 025 e a entropia 𝐻 𝑋 𝐸 ℎ 𝑚𝑘 de cada mensagem do conjunto 𝑋 de 𝑀 4 mensagens de 𝑁 2 bits resulta de 22 como sendo 𝐻 𝑋 log2 4 2 bitsmensagem bitsmensagem 1 𝑀 𝑘0 𝑀1 log2 𝑀 1 𝑀 𝑀log2 𝑀 log2𝑀 Exemplo 1 Seja um sistema para transmissão digital que utiliza no Codificador de Fonte um conjunto 𝑋 𝑚0 𝑚1 com 𝑀 2 possíveis mensagens palavras binárias de 𝑁 1 bit ou 𝑀 2 possíveis níveis de quantização Seja 𝑞 a probabilidade de ocorrência que a saída 𝑋 do quantizador assuma valor 𝑚0 isto é 𝑞 𝑃𝑋 𝑚0 Pedese Determine o gráfico da Entropia de 𝑋 em função de q Solução Para determinar o gráfico da Entropia de 𝑋 em função de q consideremos que 𝑞 𝑃 𝑋 𝑚0 𝑃 𝑋 𝑚1 1 𝑞 Portanto Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 40 Entropia uma possível medida de informação 𝐻 𝑋 𝑘0 𝑀1 𝑝𝑘log2 𝑝𝑘 𝑝0log2 𝑝0 𝑝1log2 𝑝1 𝑞log2 𝑞 1 𝑞 log2 1 𝑞 bitsmensagem 23 Plotando 𝐻𝑋 𝑞 a partir de 23 obtemos o gráfico 𝐻 𝑋 𝑞 Note no gráfico que a entropia ie a média da auto informação ℎ 𝑚𝑘 log2𝑝𝑘 transportada por cada uma das 𝑀 2 mensagens 𝑚𝑘 do conjunto 𝑋 𝑚𝑘 𝑚0 𝑚1 é máxima e de valor max 𝐻 𝑋 quando as mensagens são equiprováveis ie quando 𝑞 𝑃 𝑋 𝑚0 𝑃 𝑋 𝑚1 05 Embora este resultado tenha sido obtido para 𝑀 2 mensagens o resultado é geral e válido para qualquer valor de 𝑀 ie a média 𝑯 𝑿 da autoinformação transportada por cada uma das 𝑴 mensagens 𝒎𝒌 do conjunto de mensagens 𝑿 𝒎𝒌 de um sistema de transporte de informação é máxima e dada por 𝐦𝐚𝐱 𝑯 𝑿 𝐥𝐨𝐠𝟐 𝑴 quando a probabilidade de ocorrência das 𝑴 mensagens são iguais max 𝐻 𝑋 Taxa de transporte da informação Consideremos uma fonte de informação conectada à entrada do Codificador de Fonte de um sistema digital que transporta informação através de um conjunto 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 com 𝑀 possíveis mensagens palavras binárias conforme mostra a figura abaixo Suponhamos que estamos registrando em disco a saída 𝑋 do Codificador de Fonte contando a frequência de ocorrência probabilidade 𝑝𝑘 𝑘 01 𝑀 1 das 𝑀 possíveis palavras binárias e determinando através de 21 a média da autoinformação transportada por cada uma das 𝑀 palavras binárias 𝑚𝑘 do conjunto 𝑋 ie determinando a entropia 𝐻𝑋 Se a fonte de informação é amostrada a uma frequência de amostragem 𝑓𝑠 Sas samples per second então na saída 𝑋 do Codificador de Fonte são geradas 𝑓𝑠 𝑚𝑒𝑛𝑠𝑎𝑔𝑒𝑛𝑠𝑠𝑒𝑔𝑢𝑛𝑑𝑜 com uma entropia 𝐻𝑏𝑖𝑡𝑠𝑚𝑒𝑛𝑠𝑎𝑔𝑒𝑚 Portanto a Taxa de Informação 𝑅 que meda o número médio de bits por segundo transportados pelo Codificador de Fonte é dada por Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 41 Amostragem Quantização Codificação Fonte de Informação 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 𝑋 𝑅 bits s 𝑓𝑠 mensagens s 𝐻 bits mensagem 24 Exemplo 2 Seja um sistema para transmissão digital cujo Codificador de Fonte digitaliza um sinal analógico 𝑚𝑡 através de um conjunto 𝑋 𝑚0 𝑚1 𝑚2 𝑚3 com 𝑀 4 possíveis mensagens conforme mostra a figura abaixo Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 42 Taxa de transporte da informação As palavras binárias na saída 𝑋 do Codificador são tais que a ocorrência de uma não altera a probabilidade de ocorrência da outra i é as mensagens são estatisticamente independentes As probabilidades de ocorrência são 𝑃 𝑋 𝑚0 𝑃 𝑋 𝑚3 18 e 𝑃 𝑋 𝑚1 𝑃 𝑋 𝑚2 38 O intervalo de amostragem adotado no ADC do Codificador de Fonte é 𝑇𝑠 1 𝑓𝑠 50𝜇𝑠 Pedese Determine a taxa de informação 𝑅 bits s gerada pelo sinal 𝑚𝑡 na saida 𝑋 do Codificador de Fonte Amostragem Quantização Codificação 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚2 𝑚3 𝑋 𝑚𝑡 Solução A entropia ie a média da autoinformação transportada por cada uma das 𝑀 4 mensagens 𝑚𝑘 do conjunto 𝑋 𝑚0 𝑚1 𝑚2 𝑚3 é dada pela equação 21 𝐻 𝑋 𝑘0 𝑀1 𝑝𝑘log2 𝑝𝑘 1 8 log2 1 8 3 8 log2 3 8 3 8 log2 3 8 1 8 log2 1 8 18 bitsmensagem 𝑓𝑠 1 𝑇𝑠 1 50𝜇𝑠 20 KSas 20000 mensagenssegundo 𝑅 bits s 𝑓𝑠 mensagens s 𝐻 bits mensagem 20000 mensagenssegundo 18 bitsmensagem 36 Kbps Da equação 24 Codificação por entropia Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 43 Consideremos o Codificador de Fonte de um sistema digital que digitaliza a informação através de um conjunto 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 com 𝑀 possíveis mensagens palavras binárias 𝑁 log2 𝑀 bits seguido pelo bloco Codificador por Entropia conforme mostra a figura abaixo Amostragem Quantização Codificação 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 𝑋 𝑚𝑡 Codificador por Entropia 𝜃 𝑆 𝑠𝑘 𝑠0 𝑠1 𝑠𝑀1 O Codificador por Entropia processa cada uma das 𝑀 possíveis palavras binárias 𝑋 𝑚𝑘 𝑚0 𝑚1 𝑚𝑀1 de 𝑁 log2 𝑀 bits em sua entrada e associa a cada uma delas uma respectiva palavracódigo símbolo 𝑆 𝑠𝑘 𝑠0 𝑠1 𝑠𝑀1 cujo número de bits é controlado por uma função 𝛽𝑝𝑘 da probabilidade de ocorrência 𝑝𝑘 da mensagem 𝑚𝑘 em sua entrada A função 𝜷𝒑𝒌 é tal que quanto maior a probabilidade de ocorrência 𝒑𝒌 da mensagem 𝒎𝒌 menor será o número de bits atribuídos à respectiva palavracódigo 𝒔𝒌 associada O efeito da função 𝛽𝑝𝑘 resulta que mensagens que ocorrem frequentemente necessitem de menos bits para serem transmitidas e portanto o efeito global é o de reduzir a quantidade de bits transmitidos Podemos considerar o bloco Codificador por Entropia na figura acima como um operador 𝜽 tal que 𝑠𝑘 𝜃𝑚𝑘 onde a associação da mensagem 𝑚𝑘 à palavracódigo 𝑠𝑘 através do codebook definido por 𝑠𝑘 𝜃𝑚𝑘 obedece à função 𝛽𝑝𝑘 referida no parágrafo anterior Existem várias possíveis definições para a função 𝛽𝑝𝑘 Veremos adiante neste capítulo que a função 𝛽𝑝𝑘 ótima é implementada pelo Código de Huffman Quando um sistema digital é projetado é feito um estudo estatístico da frequência de ocorrência 𝑝𝑘 de cada uma das 𝑀 possíveis mensagens 𝑚𝑘 para que o mapeamento 𝑠𝑘 𝜃𝑚𝑘 efetuado pelo código compressor possa ser especificado ie de modo que a função 𝛽𝑝𝑘 possa ser determinada O conjunto de 𝑀 valores obtidos para 𝑝𝑘 pode ser considerado uma boa aproximação das probabilidades de ocorrência de cada uma das 𝑀 possíveis mensagens desde que seja utilizado um número suficientemente grande de amostras Por exemplo o Código Morse brevemente discutido nos slides 6 e 7 do Cap I teve a sua função 𝛽𝑝𝑘 determinada experimentalmente a partir de um estudo estatístico que determinou a frequência de ocorrência 𝑝𝑘 dos caracteres alfabéticos utilizados na escrita de textos em língua inglesa Codificação por entropia Um código p compressão por entropia é portanto um operador 𝜃 tal que 𝑠𝑖 𝜃𝑥𝑖 onde a associação da mensagem 𝑥𝑖 à palavracódigo 𝑠𝑖 através do codebook definido por 𝑠𝑖 𝜃𝑥𝑖 obedece à uma função 𝛽𝑝𝑖 onde 𝑖 01 𝑀 1 sendo 𝑀 o número de possíveis mensagens 𝑥𝑖 palavras binárias de 𝑁 log2 𝑀 bits que constam no conjunto 𝑋 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 A função 𝛽𝑝𝑖 é tal que quanto maior a probabilidade de ocorrência 𝑝𝑖 da mensagem 𝑥𝑖 menor será o número de bits atribuídos à respectiva palavracódigo 𝑠𝑘 associada Os dados de entrada e saída do operador 𝜃 são respectivamente 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 é o conjunto de 𝑀 possíveis mensagens a serem codificadas através de 𝑠𝑖 𝜃𝑥𝑖 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 é o conjunto de 𝑀 possíveis palavrascódigo ou símbolos resultantes da codificação 𝑠𝑖 𝜃𝑥𝑖 É imperativo que o mapeamento 𝑠𝑖 𝜃𝑥𝑖 efetuado pelo operador 𝜃 seja um mapeamento unívoco de modo que as palavrascódigo 𝑠𝑖 recebidas no decodificador por entropia do RX sejam univocamente decodificáveis através de 𝑥𝑖 𝜃1𝑠𝑖 caso contrário o decodificador do RX encontrará ambiguidades no conjunto de palavrascódigo 𝑠𝑖 recebidas incorrendo em erros de decodificação na recuperação das mensagens 𝑥𝑖 Veremos adiante neste capítulo como definir códigos univocamente decodificáveis códigos UD O conjunto de caracteres do código ou alfabeto do código é o conjunto 𝐴 𝑎0 𝑎1 𝑎𝐷1 composto por 𝐷 elementos de cuja composição são formadas cada uma das palavracódigo Neste estudo o escopo enfocará códigos binários em que o alfabeto é 𝐴 01 O tamanho ℓ𝒊 de uma palavracódigo ou símbolo 𝑠𝑖 é definido pelo número de caracteres do alfabeto 𝐴 utilizado na construção da palavracódigo Por exemplo no codebook abaixo é mostrado o tamanho ℓ𝒊 de cada símbolo 𝑠𝑖 p um código binário Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 44 Mensagem 𝒙𝒊 Palavra bin PalavraCódigo 𝒔𝒊 associada a 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 ℓ𝒊 𝑥0 00 0 1 𝑥1 01 010 3 𝑥2 10 01 2 𝑥3 11 10 2 Codificação por entropia O objetivo de um codificador por entropia é através de um código 𝑠𝑖 𝜃𝑥𝑖 minimizar o tamanho médio ത𝐿 dos símbolos 𝑠𝑖 do conjunto de 𝑀 possíveis símbolos 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 na saída do codificador respectivamente correspondentes às mensagens no conjunto 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 aplicadas à sua entrada sendo o tamanho médio ത𝐿 dos símbolos no conjunto dos 𝑀 possíveis símbolos 𝑆 𝑠𝑖 dado por Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 45 onde 𝑝𝑖 é a probabilidade de ocorrência da mensagem 𝑥𝑖 e onde ℓ𝒊 é o tamanho do símbolo 𝑠𝑖 associado à mensagem 𝑥𝑖 através do código 𝑠𝑖 𝜃𝑥𝑖 ത𝐿 𝑖0 𝑀1 𝑝𝑖ℓ𝒊 25 A Codificação por Entropia assume que a fonte de informação é sem memória Uma fonte é considerada sem memória quando as mensagens emitidas pela fonte são estatisticamente independentes ie a ocorrência de uma determinada mensagem 𝑥𝑖 não afeta a probabilidade de ocorrência da mensagem 𝑥𝑗 com 𝑖 𝑗 01 𝑀 1 Esta condição de a fonte de informação ser sem memória é necessária pois caso contrário a função 𝐿 𝑓𝑝𝑖 ℓ𝒊 a ser minimizada dependeria do desenrolar temporal da sequência de mensagens emitidas pela fonte o que resultaria em um codebook 𝜽 variável no tempo Embora poucas fontes físicas sigam exatamente o modelo de uma fonte sem memória códigos 𝜃 constantes no tempo resultantes da suposição de que as mensagens emitidas pela fonte são estatisticamente independentes são amplamente utilizados como códigos compressores mesmo quando a dependência estatística da fonte resulta na impossibilidade de minimização de ഥ𝐿 durante a totalidade do tempo de codificação Em alguns sistemas que operam com sinais altamente dinâmicos a probabilidade de ocorrência 𝑝𝑖 da mensagem 𝑥𝑖 é avaliada periodicamente para cada uma das 𝑀 mensagens e um novo codebook 𝑠𝑖 𝜃𝑥𝑖 é então definido após cada período de avaliação Esta redefinição adaptativa e periódica do codebook 𝑠𝑖 𝜃𝑥𝑖 obviamente aumenta o custo computacional do processo de compressão Um exemplo de técnica de compressão que utiliza um codebook adaptativo é o CELP Code Excited Linear Prediction ver httpsenwikipediaorgwikiCodeexcitedlinearprediction técnica que é largamente utilizada na compressão de voz em tempo real em telefones celulares Codificação por entropia Exemplo 3 Seja um sistema para transmissão digital que utilize no Codificador de Fonte um conjunto 𝑥0 𝑥1 𝑥2 𝑥3 00011011 com 𝑀 4 possíveis mensagens As mensagens são tais que a ocorrência de uma não altera a probabilidade de ocorrência da outra ie as mensagens são estatisticamente independentes As probabilidades 𝑝𝑖 de ocorrência de cada mensagem são 𝑃 𝑋 𝑥0 1 2 𝑃 𝑋 𝑥1 1 4 𝑃 𝑋 𝑥2 𝑃 𝑋 𝑥3 1 8 0 codebook do código 𝜃 é conforme tabela ao lado Mensagem 𝒙𝒊 Palavra bin PalavraCódigo 𝒔𝒊 associada a 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 𝑥0 00 0 𝑥1 01 10 𝑥2 10 110 𝑥3 11 111 Pedese a Determine a entropia da fonte 𝐻 𝑋 b Determine o comprimento médio ത𝐿 𝜃 do código 𝜃 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 46 Solução Da tabela do codebook dado no enunciado temos que as probabilidades de ocorrência 𝑝𝑖 e o tamanho ℓ𝒊 de cada palavracódigosímbolo 𝑠𝑖 são conforme tabela abaixo 𝒙𝒊 𝒑𝒊 Símbolo 𝒔𝒊 associado a 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 ℓ𝒊 𝑥0 12 0 1 𝑥1 14 10 2 𝑥2 18 110 3 𝑥3 18 111 3 𝐻 𝑋 1 2 log2 1 2 1 4 log2 1 4 1 8 log2 1 8 1 8 log2 1 8 175 bitsmensagem a Da equação 21 no slide 39 e das probabilidades 𝑝𝑖 na tabela ao lado temos que a entropia da fonte 𝐻 𝑋 resulta em b Da equação 25 no slide anterior e das probabilidades 𝑝𝑖 e tamanhos ℓ𝒊 na tabela acima temos que o comprimento médio ത𝐿 𝜃 do código 𝜃 resulta em 𝐿 𝜃 1 2 1 1 4 2 1 8 3 1 8 3 175 bitssímbolo Note por exemplo que se transmitíssemos as palavras binárias de 2 bits sem compressão para 10000 mensagens a serem enviadas do TX ao RX teríamos que enviar 20000 bits através o canal de transmissão mas o uso do codebook 𝜃 reduz este número para 17500 bits Exemplo 4 Seja o código compressor 𝜃 conforme definido no codebook na tabela abaixo 𝐻 𝑋 1 3 log2 1 3 1 3 log2 1 3 1 3 log2 1 3 158 bitsmensagem 𝐿 𝜃 1 3 1 1 3 2 1 3 2 167 bitssímbolo 𝒙𝒊 𝒑𝒊 Símbolo 𝒔𝒊 associado a 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 ℓ𝒊 𝑥0 13 0 1 𝑥1 13 10 2 𝑥2 13 11 2 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 47 Codificação por entropia Pedese a Determine a entropia da fonte 𝐻 𝑋 b Determine o comprimento médio ത𝐿 𝜃 do código 𝜃 Solução a Da equação 21 no slide 39 e das probabilidades 𝑝𝑖 na tabela acima temos que a entropia da fonte 𝐻 𝑋 resulta em b Da equação 25 no slide 45 e das probabilidades 𝑝𝑖 e tamanhos ℓ𝒊 na tabela acima temos que o comprimento médio ത𝐿 𝜃 do código 𝜃 resulta em Note no Exemplo 3 no slide anterior que o comprimento médio ത𝑳 𝜽 𝟏 𝟕𝟓 𝐛𝐢𝐭𝐬𝐬í𝐦𝐛𝐨𝐥𝐨 das palavrascódigo 𝑠𝑖 geradas pelo codebook do código 𝜃 resultou igual à média da autoinformação 𝑯 𝑿 𝟏 𝟕𝟓 𝐛𝐢𝐭𝐬𝐦𝐞𝐧𝐬𝐚𝐠𝐞𝐦 transportada pelas 𝑀 mensagens 𝑥𝑖 do conjunto Esta situação em que ത𝑳 𝜽 𝑯 𝑿 maximiza a compressão porque indica que toda a informação redundante nas 𝑀 mensagens 𝑥𝑖 do conjunto foi eliminada através do mapeamento 𝑠𝑖 𝜃𝑥𝑖 efetuado pelo codebook do código 𝜃 Já com o codebook do código 𝜃 do presente Exemplo 4 esta condição ótima não consegue ser atingida porque ത𝐿 𝜃 167 bitssímbolo é maior que 𝐻 𝑋 158 bitsmensagem indicando que nem toda a informação redundante nas 𝑀 mensagens 𝑥𝑖 do conjunto foi eliminada através do mapeamento 𝑠𝑖 𝜃𝑥𝑖 efetuado pelo codebook do código 𝜃 Códigos univocamente decodificáveis Códigos UD Um código é Univocamente Decodificável UD quando o seu codebook for tal que qualquer sequência de caracteres do alfabeto 𝐴 passível de ser formada a partir da justaposição de um número qualquer de símbolos pertencentes ao conjunto 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 puder ser associada ao ser decodificada no RX a uma única mensagem em 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 Conceito de justaposição A justaposição de 𝑁 símbolos ou palavrascódigo é a sequência 𝛼 𝑠𝑖 𝑠𝑖1 𝑠𝑖𝑁1 formada pela transmissão do símbolo 𝑠𝑖 seguido da transmissão do símbolo 𝑠𝑖1 e assim sucessivamente até a transmissão do símbolo 𝑠𝑖𝑁1 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 48 Conforme brevemente discutido no slide 44 é imperativo que o mapeamento 𝑠𝑖 𝜃𝑥𝑖 efetuado pelo codebook do código 𝜃 seja um mapeamento unívoco de modo que as palavrascódigo 𝑠𝑖 recebidas no decodificador por entropia do RX sejam univocamente decodificáveis através de 𝑥𝑖 𝜃1𝑠𝑖 caso contrário o decodificador do RX encontrará ambiguidades no conjunto de palavrascódigo 𝑠𝑖 recebidas incorrendo em erros de decodificação na recuperação das mensagens 𝑥𝑖 Um código 𝜃 cujo codebook defina um mapeamento 𝑠𝑖 𝜃𝑥𝑖 unívoco é denominado de código univocamente decodificável código UD Exemplo 5 Seja o código 𝜃 conforme definido no codebook na tabela abaixo Pedese Determine se 𝜃 é UD Mensagem Palavracódigo 𝒔𝒊 𝐚𝐬𝐬𝐨𝐜𝐢𝐚𝐝𝐚 𝐚 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 𝑥0 0 𝑥1 010 𝑥2 01 𝑥3 10 Solução Vamos partir da palavracódigo com maior numero de bits 𝑠1 010 e verificar se ela ao ser transmitida pelo TX é passível de ser decomposta em uma justaposição das demais palavrascódigo Especificamente a pergunta que temos que responder é Como decodificar 𝑠1 010 no RX As possíveis inferências que o decodificador do RX faria são 𝑠1 010 𝑥𝑖 𝜃1 𝑠𝑖 𝑥1 correto 𝑠2𝑠0 010 𝑥𝑖 𝜃1 𝑠𝑖 𝑥1 incorreto 𝑠0𝑠3 010 𝑥𝑖 𝜃1 𝑠𝑖 𝑥1 incorreto Dado que ocorrem as ambiguidades 𝑠2𝑠0 e 𝑠0𝑠3 no decodificador do RX quando o TX transmite 𝑠1 então o código 𝜽 não é UD Códigos instantâneos As ambiguidades do codebook do código 𝜃 do Exemplo 5 no slide anterior talvez pudessem ser resolvidas se aguardássemos a recepção de bits adicionais para resolver a incerteza mas tal tempo de espera é indesejável dada a constante busca por velocidade de decodificação é desejável que o RX seja capaz de decodificar instantaneamente as palavrascódigo 𝑠𝑖 à medida que as mesmas são recebidas no decodificador do RX Uma maneira de assegurar que um código seja UD e que nenhum tempo de espera seja necessário para a correta decodificação é utilizar códigos prefixos ou instantâneos A denominação instantâneo para tais códigos decorre de não haver necessidade de aguardar a recepção de bits adicionais para que se resolva ambiguidades Um código instantâneo ou prefixo pode ser decodificado sem referência a palavrascódigo futuras porque o final de uma palavracódigo é imediatamente reconhecido no decodificador Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 49 Todos os códigos instantâneos são UD mas nem todos os códigos UD são instantâneos Ou seja o conjunto dos códigos instantâneos é um subconjunto do conjunto dos códigos UD conforme mostra a figura ao lado Um código é instantâneo se nenhuma palavracódigo é prefixo de nenhuma outra palavracódigo pertencente ao código códigos instantâneos códigos UD Conceito de sequência prefixo Sejam as sequências 𝛼𝑎 𝛼𝑏 e 𝛼𝑐 formadas pela justaposição de respectivamente 𝑁𝑎 𝑁𝑏 e 𝑁𝑐 palavrascódigo 𝑠𝑖 pertencentes ao codebook do código 𝜃 sendo 𝑁𝑎 𝑁𝑏 𝑁𝑐 um número qualquer de palavras código Dizemos que a sequência 𝛼𝑏 é prefixo da sequência 𝛼𝑎 se 𝛼𝑎 puder ser representada por 𝛼𝑏𝛼𝑐 para alguma sequência 𝛼𝑐 denominada sufixo Mensagem PalavraCódigo 𝒔𝒊 𝐚𝐬𝐬𝐨𝐜𝐢𝐚𝐝𝐚 𝐚 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 𝑥0 10 𝑥1 00 𝑥2 11 𝑥3 110 Como 11 é prefixo de 110 𝜃 não é instantâneo No entanto não podemos afirmar que não seja UD pelo fato de não ser instantâneo Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 50 Códigos instantâneos Exemplo 6 Seja o código 𝜃 conforme definido no codebook na tabela abaixo Pedese Determine se 𝜃 é instantâneo Solução códigos instantâneos códigos UD Seja um código 𝜃 com alfabeto 𝐴 𝛼0 𝛼1 𝛼𝐷1 e conjunto imagem 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 definido pelo seu codebook Para testar se 𝜃 é UD constróise uma sequência de conjuntos de símbolos 𝑆0 𝑆1 obedecendo ao seguinte critério de formação 1 𝑆0 é o próprio conjunto imagem do codebook ie 𝑆0 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 2 Para definir 𝑆1 formase a partir de 𝑆0 o conjunto P de todos os pares 𝑠𝑖𝑠𝑗 de palavrascódigo 𝑠𝑖 𝑠𝑗 possíveis de serem formados por justaposição de duas palavrascódigo distintas pertencentes ao conjunto 𝑆0 Teste para verificar se um código é UD Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 51 𝑠0 𝑠1 𝑠𝑀1 𝑠0 𝑠0𝑠1 𝑠0𝑠𝑀1 𝑠1 𝑠1𝑠0 𝑠1𝑠𝑀1 𝑠𝑀1 𝑠𝑀1𝑠0 𝑠𝑀1𝑠1 3 Se a palavracódigo 𝑠𝑖 𝑆0 é prefixo da palavracódigo 𝑠𝑗 𝑆0 ie 𝑠𝑗 𝑠𝑖𝜎 então o sufixo 𝜎 é um elemento do conjunto 𝑆1 ie σ 𝑆1 Executase a verificação 𝑠𝑗 𝑠𝑖𝜎 para todos os elementos de P até que todos os sufixos sejam atribuídos ao conjunto 𝑆1 𝛼0 𝛼1 onde cada sequência 𝛼𝑘 de caracteres de 𝐴 é um sufixo originado pelo resultado positivo do teste 𝑠𝑗 𝑠𝑖𝜎 4 Para definir 𝑆𝑛 𝑛 1 comparase 𝑆0 e 𝑆𝑛1 de modo bidirecional I Se uma palavracódigo 𝑠𝑖 𝑆0 é prefixo de uma sequência 𝛼𝑗 𝑆𝑛1 tal que 𝛼𝑗 𝑠𝑖𝜎 então o sufixo 𝜎 𝑆𝑛 II Se uma sequência 𝛼𝑗 𝑆𝑛1 é prefixo de uma palavracódigo 𝑠𝑖 𝑆0 tal que 𝑠𝑖 𝛼𝑗𝜎 então o sufixo 𝜎 𝑆𝑛 5 Definese tantos conjuntos 𝑆𝑛 até um valor de 𝑛 tal que 𝑆𝑛 ou até um valor de 𝑛 tal que 𝑆𝑛 𝑆𝑛1 6 O código 𝜃 é UD se e somente se nenhum dos conjuntos da sequência de conjuntos 𝑆1 𝑆2 contenha uma palavracódigo que pertença ao conjunto 𝑆₀ Exemplo 7 Usando o algoritmo descrito no slide anterior verifique se o código 𝜃 abaixo com alfabeto 𝐴 𝑎 𝑏 𝑐 𝑑 𝑒 é instantâneo eou UD Mensagem PalavraCódigo 𝒔𝒊 𝐚𝐬𝐬𝐨𝐜𝐢𝐚𝐝𝐚 𝐚 𝒎𝒊 por 𝒔𝒊 𝜽𝒙𝒊 𝑥0 𝑎 𝑥1 𝑐 𝑥2 𝑎𝑑 𝑥3 𝑎𝑏𝑏 𝑥4 𝑏𝑎𝑑 𝑥5 𝑑𝑒𝑏 𝑥6 𝑏𝑏𝑐𝑑𝑒 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 52 Teste para verificar se um código é UD 𝑺𝟎 𝑺𝟏 𝑎 𝑑 𝑐 𝑏𝑏 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆1 𝑆1 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de outras palavras de 𝑆0 Alguma palavra de 𝑆1 𝑆0 Se sim 𝜃 não é UD Se não construir 𝑆2 a partir de 𝑆0 𝑒 𝑆1 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 53 Teste para verificar se um código é UD Solução 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑎 𝑑 𝑒𝑏 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆2 𝑆2 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de palavras de 𝑆1 e 𝑆2 contém todos os sufixos encontrados ao mapear palavras de 𝑆1 que são prefixo de palavras de 𝑆0 Alguma palavra de 𝑆2 𝑆0 Se sim 𝜃 não é UD Se não construir 𝑆3 a partir de 𝑆0 e 𝑆2 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 54 Teste para verificar se um código é UD 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑎 𝑑 𝑒𝑏 𝑑𝑒 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆3 𝑆3 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de palavras de 𝑆2 e 𝑆3 contém todos os sufixos encontrados ao mapear palavras de 𝑆2 que são prefixo de palavras de 𝑆0 Alguma palavra de 𝑆3 𝑆0 Se sim 𝜃 não é UD Se não construir 𝑆4 a partir de 𝑆0 e 𝑆3 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 55 Teste para verificar se um código é UD 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 𝑎 𝑑 𝑒𝑏 𝑑𝑒 𝑏 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆4 𝑆4 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de palavras de 𝑆3 e 𝑆4 contém todos os sufixos encontrados ao mapear palavras de 𝑆3 que são prefixo de palavras de 𝑆0 Alguma palavra de 𝑆4 𝑆0 Se sim 𝜃 não é UD Se não construir 𝑆5 a partir de 𝑆0 e 𝑆4 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 56 Teste para verificar se um código é UD 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 𝑺𝟓 𝑎 𝑑 𝑒𝑏 𝑑𝑒 𝑏 𝑎𝑑 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑏𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆5 𝑆5 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de palavras de 𝑆4 e 𝑆5 contém todos os sufixos encontrados ao mapear palavras de 𝑆4 que são prefixo de palavras de 𝑆0 Alguma palavra de 𝑆5 𝑆0 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 57 Teste para verificar se um código é UD 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 𝑺𝟓 𝑎 𝑑 𝑒𝑏 𝑑𝑒 𝑏 𝑎𝑑 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑏𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Construir 𝑆5 𝑆5 contém todos os sufixos encontrados ao mapear palavras de 𝑆0 que são prefixo de palavras de 𝑆4 e 𝑆5 contém todos os sufixos encontrados ao mapear palavras de 𝑆4 que são prefixo de palavras de 𝑆0 Alguma palavra de 𝑆5 𝑆0 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 58 Teste para verificar se um código é UD Visto que 𝑎𝑑 𝑆5 e 𝑎𝑑 𝑆0 logo 𝜃 não é UD 𝑺𝟎 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑺𝟒 𝑺𝟓 𝑺𝟔 𝑺𝟕 𝑺𝟖 𝑎 𝑑 𝑒𝑏 𝑑𝑒 𝑏 𝑎𝑑 𝑑 𝑒𝑏 𝑐 𝑏𝑏 𝑐𝑑𝑒 𝑏𝑐𝑑𝑒 𝑎𝑑 𝑎𝑏𝑏 𝑏𝑎𝑑 𝑑𝑒𝑏 𝑏𝑏𝑐𝑑𝑒 Note que poderíamos ter encerrado o procedimento ao obter 𝑆5 no slide anterior quando então já tínhamos elementos suficientes para decidir que 𝜃 não é UD No entanto neste slide o procedimento foi continuado até não encontrarmos mais elementos na coluna 𝑆 construída Este é o procedimento que deve obrigatoriamente ser seguido caso não se encontre uma palavra pertencente a 𝑆0 em alguma das colunas construídas Somente ao encontrar é possível afirmar que o código é UD Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 59 Teste para verificar se um código é UD 𝜃𝐼𝐼𝐼 𝜃𝐼 𝑺𝟎 𝑺𝟏 𝑺𝟐 1 0 0 00 1 01 10 𝑺𝟎 𝑺𝟏 0 10 110 111 𝑺𝟎 𝑺𝟏 𝑺𝟐 0 1 11 01 11 1 011 111 Resposta Não é instantâneo nem UD Resposta Não é instantâneo mas é UD Resposta É Instantâneo e portanto é UD Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 60 Teste para verificar se um código é UD Exemplo 8 Usando o algoritmo descrito nos slide 51 verifique se os códigos 𝜃𝐼 𝜃𝐼𝐼 e 𝜃𝐼𝐼𝐼 abaixo com alfabeto 𝐴 01 são instantâneos eou UD 𝜃𝐼𝐼 No link Videoaula Códigos Instantâneos e UD Profa Cristina De Castro encontrase disponível uma videoaula com a solução passo a passo do Exemplo 8 Seja uma variável aleatória discreta X com espaço de amostras definido pelo conjunto 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 de 𝑀 eventos estatisticamente independentes 𝑥𝑖 com probabilidade de ocorrência 𝑝𝑖 𝑖 01 𝑀 1 Então é possível construir um código Instantâneo 𝜃 através de um codebook de palavrascódigo 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 formadas a partir do alfabeto 𝐴 01 tal que o conjunto 𝐿 ℓ𝒊 ℓ𝟎 ℓ𝟏 ℓ𝑴𝟏 dos tamanhos das palavrascódigo respectivas em 𝑆 satisfaça à desigualdade Teorema da Codificação de Fonte TCF de Shannon Noiseless Coding Theorem Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 61 𝐻 𝑋 ത𝐿 𝐻𝑋 1 onde 𝐻 𝑋 é a entropia da fonte 𝑋 dada pela equação 21 do slide 39 ത𝐿 é o tamanho médio das palavrascódigos dado pela equação 25 do slide 45 ver httpsenwikipediaorgwikiShannon27ssourcecodingtheorem 26 O TCF garante a viabilidade teórica de implementação de códigos instantâneos cujo tamanho médio ത𝐿 dos símbolos pode ser reduzido a um valor tão pequeno quanto o valor da Entropia 𝐻𝑋 da fonte ou se impossível pelo menos a um valor menor que 𝐻 𝑋 1 Uma decorrência do TCF é a definição da Eficiência de Codificação 𝜼 dada por ver discussão na solução do Exemplo 4 no slide 47 𝜂 𝐻𝑋 ത𝐿 27 Um código 𝜃 é Absolutamente Ótimo matched to the source casado com a fonte quando 𝜂 10 isto é quando ത𝐿 𝐻𝑋 Ver por exemplo o código do Exemplo 3 no slide 46 Um código 𝜃 é Quase Absolutamente Ótimo quando 𝐻 𝑋 ത𝐿 𝐻𝑋 1 Embora o TCF nos garanta que é possível obter códigos instantâneos com ത𝐿 tão pequeno quanto a própria entropia 𝐻𝑋 da fonte nenhuma informação é dada sobre como construir tais códigos A construção de códigos ótimos baseiase na minimização do tamanho médio ത𝐿 das palavrascódigos do codebook sendo ത𝐿 dado pela equação 25 do slide 45 Um código instantâneo que minimize ത𝐿 é denominado de Código Ótimo Há um teorema que prova que se um código ótimo 𝜃 resulta em ഥ𝐿 então é impossível existir um outro código instantâneo 𝜃 com tamanho médio ത𝐿 tal que ത𝐿 ഥ𝐿 Um Código Ótimo binário cujas palavrascódigo 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 são formadas a partir do alfabeto 𝐴 01 satisfaz as seguintes propriedades I Palavrascódigo com maior probabilidade possuem menor tamanho menor número de bits II As 2 palavrascódigo menos prováveis possuem o mesmo tamanho mesmo número de bits III As 2 palavrascódigo menos prováveis diferem somente no valor do último bit Códigos Ótimos Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 62 Exemplo 9 Verifique se o código 𝜃 definido no codebook abaixo é um Código Ótimo Mensagem 𝒑𝒊 PalavraCódigo 𝒔𝒊 𝐚𝐬𝐬𝐨𝐜𝐢𝐚𝐝𝐚 𝐚 𝒙𝒊 por 𝒔𝒊 𝜽𝒙𝒊 𝑥0 06 0 𝑥1 02 100 𝑥2 01 101 𝑥3 004 1101 𝑥4 006 1110 Note no codebook acima que As propriedades I e II são satisfeitas A propriedade III não é satisfeita 𝑠3 e 𝑠4 não diferem somente no último bit Portanto o código 𝜽 definido no codebook acima não é um Código Ótimo Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 63 Códigos Ótimos Solução Do slide anterior temos que um Código Ótimo binário cujas palavrascódigo 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 são formadas a partir do alfabeto 𝐴 01 satisfaz as seguintes propriedades I Palavrascódigo com maior probabilidade possuem menor tamanho menor número de bits II As 2 palavrascódigo menos prováveis possuem o mesmo tamanho mesmo número de bits III As 2 palavrascódigo menos prováveis diferem somente no valor do último bit Para a construção de um código ótimo binário 𝜃 a partir do algoritmo de Huffman efetuase o seguinte procedimento Seja inicialmente 𝑘 𝑗 0 1 Organizar as probabilidades 𝑝𝑖 de alto a baixo em uma coluna em ordem decrescente de valor denominada Coluna 𝑘 2 Somar as 2 menores probabilidades 𝑝𝑖 na Coluna 𝑘 e transferilas para a próxima coluna à direita denominada Coluna 𝑘 1 obedecendo a ordem decrescente As demais probabilidades da Coluna 𝑘 são transferidas inalteradas para a Coluna 𝑘 1 3 Incrementar 𝑘 de 1 e repetir 1 a 3 até restarem somente 2 probabilidades na Coluna 𝑘 1 então denominada Coluna 𝑗 4 Na Coluna 𝑗 atribuir a palavracódigo representada pelo bit 0 à maior probabilidade e atribuir a palavracódigo representada pelo bit 1 à menor probabilidade 5 Localizar na Coluna 𝑗 1 imediatamente à esquerda da Coluna 𝑗 quais as 2 probabilidades geradoras que ao serem somadas resultaram na probabilidade gerada na Coluna 𝑗 Atribuir às 2 probabilidades geradoras na Coluna 𝑗 1 a palavracódigo já atribuída à probabilidade gerada na Coluna 𝑗 Às probabilidades nãogeradoras na Coluna 𝑗 1 são atribuídas as palavrascódigo já atribuídas às respectivas probabilidades nãogeradas por soma na Coluna 𝑗 6 Na Coluna 𝑗 1 nas palavrascódigos já atribuídas em 5 às 2 probabilidades geradoras justapor o bit 0 à palavra código geradora de maior probabilidade e justapor o bit 1 à palavracódigo geradora de menor probabilidade 7 Incrementar 𝑗 de 1 e repetir 5 a 7 até que todas as colunas tenham palavrascódigo associadas às probabilidades nelas contidas 8 Após a execução de 7 o codebook p o Código de Huffman estará definido na coluna mais a esquerda Algoritmo para construção de códigos ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 64 Exemplo 10 Seja uma fonte de informação representada pela variável aleatória discreta 𝑋 com espaço de amostras definido pelo conjunto 𝑥𝑖 𝑥0 𝑥1 𝑥𝑀1 de 𝑀 6 eventos estatisticamente independentes 𝑥𝑖 com probabilidades de ocorrência 𝑝𝑖 𝑖 01 𝑀 1 conforme tabela abaixo Pedese a Utilizando o algoritmo de Huffman descrito no slide anterior determine um código ótimo 𝜃 cujo conjunto de palavrascódigo 𝑆 𝑠𝑖 𝑠0 𝑠1 𝑠𝑀1 é formado a partir do alfabeto 𝐴 01 b Determine a eficiência de 𝜃 c Determine se 𝜃 é absolutamente ótimo ou quase absolutamente ótimo Solução a Utilizando o algoritmo de Huffman descrito no slide anterior Mensagem 𝒑𝒊 𝑥0 04 𝑥1 03 𝑥2 01 𝑥3 01 𝑥4 006 𝑥5 004 Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 65 Códigos ótimos Códigos de Huffman Mensagem 𝒑𝒊 𝒔𝒊 𝑥0 04 1 𝑥1 03 00 𝑥2 01 011 𝑥3 01 0100 𝑥4 006 01010 𝑥5 004 01011 04 03 01 01 006 004 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 66 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 67 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 68 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 69 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 70 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 71 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 72 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 0 0 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 73 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 74 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 75 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 76 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 77 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 78 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 79 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 1 00 011 0100 0101 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 80 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 1 00 011 0100 0101 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 81 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 1 00 011 0100 0101 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 82 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 1 00 011 0100 0101 1 00 011 0100 01010 01011 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 83 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 04 03 01 01 006 004 04 03 01 01 01 04 03 02 01 04 03 03 06 04 0 1 1 00 01 1 00 010 011 1 00 011 0100 0101 1 00 011 0100 01010 01011 Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 84 Detalhamento passo a passo do algoritmo de Huffman descrito no slide 64 ത𝐿 𝑖0 𝑀1 𝑝𝑖ℓ𝒊 220 bitssímbolo 𝐻 𝑋 𝑖0 𝑀1 𝑝𝑖log2 𝑝𝑖 214 bitsmensagem 𝜂 𝐻𝑋 ത𝐿 214 220 0973 973 c Visto que 𝐻 𝑋 ത𝐿 𝐻𝑋 1 então 𝜃 é quase absolutamente ótimo Códigos Ótimos Códigos de Huffman Sistemas de Comunicação Digital I Cap II Codificação de Fonte Prof Fernando DeCastro 85 No link Videoaula Códigos de Huffman Profa Cristina De Castro encontrase disponível uma videoaula com a revisão passo a passo de códigos de Huffman Mensagem 𝒑𝒊 𝒔𝒊 𝑥0 04 1 𝑥1 03 00 𝑥2 01 011 𝑥3 01 0100 𝑥4 006 01010 𝑥5 004 01011 b A entropia 𝐻 𝑋 da fonte 𝑋 é dada pela equação 21 do slide 39 O tamanho médio ത𝐿 das palavrascódigos é dado pela equação 25 do slide 45 A eficiência 𝜂 do código é dada pela equação 27 do slide 61