Introdução ao Estudo de Sistemas de Comunicações Digitais

Comecemos por recordar a introducéo ao capitulo 1 0 estudo de um sistema de comunicacoes digitais envolve dois aspectos cruciais 1 a eficiéncia da representagao da informacao gerada pela fonte 2 a taxa de transmissao a qual é possivel enviar a informagao com fiabilidade através de um canal ruidoso A teoria da informagao estabelece os limites fundamentais associados as quest6es acima referidas A saber I numero minimo de unidades de informagao binaria bit por simbolo necessario para representar completamente a fonte II o valor maximo da taxa de transmissao que garante fiabilidade da comunicacao através de um canal ruidoso No capitulo 1 fizemos o estudo do primeiro problema no contexto do modelo de fonte discreta sem memoria Aqui iremos abordar a segunda questao estabelecendo o resultado referido em II usando 0 modelo de canal discreto sem memoria que iremos introduzir na seccao seguinte 81 Canais Discretos sem Memoria Um canal discreto um modelo estatistico que a um alfabeto de entrada representado por uma varidvel aleatéria discreta X faz corresponder de acordo com uma qualquer lei de transigao uma varidvel aleatéria discreta Y A variavel aleatéria discreta X modela 0 alfabeto de entrada do canal e Y modela o alfabeto de saida O modelo descrito esta ilustrado na Figura 81 Notese que em geral a cardinalidade do alfabeto de saida pode ser diferente da do alfabeto de entrada s Y Figura 81 Modelo de um canal discreto Def 81 Canal discreto sem memoria um canal discreto sem memoria é determinado pelo mecanismo estatistico que descreve o transporte de informacao entre a fonte e o destinatério e que se define pelo conjunto de probabilidades condicionais ply x m12M k12K 81 81 Notese que cada simbolo de saida s6 depende de um simbolo de entrada e nao de uma sequéncia Dai a designacao de canal sem meméria Em geral Vm 12M ply x0 k4m ou seja O processo de transmissdo esta sujeito a erros A ocorréncia de erros de transmissao decorre do facto de o canal ser ruidoso Assim 4 emissao do simbolo particular x pode corresponder a recepao de qualquer um dos simbolos do alfabeto de saida e portanto K Y ply Xm 1 m12M 82 kI A medida de fiabilidade da transmissAo através de um canal discreto é dada pela probabilidade média de erro por simbolo Seja px PXx m12M 83 a probabilidade de o simbolo x ser transmitido Naturalmente ocorre um erro de transmissdo se o simbolo recebido for um qualquer y km isto é K P YyPYy 84 kam Sendo conhecidas as distribuigdes de probabilidade apriori 83 e de transiao 81 entao a partir da distribuigao conjunta ply xJply x px m12Mk12K 85 podemos calcular a distribuigdo de probabilidade marginal da saida M ply JPY y ply Xm 86 m1 Usando 85 e 86 em 84 obtémse K M Po YY Ply Xm PR n 87 a Verificamos assim que no caso de um canal discreto sem mem6ria a probabilidade média de erro de transmissao por simbolo é completamente determinada pela distribuicao apriori e pelas probabilidades de transicdo 83 e 81 respectivamente Exemplo 81 Canal binario simétrico Consideremos o caso do canal bindrio simétrico de grande interesse te6rico e importancia pratica Neste caso KM2 0 alfabeto de entrada x 0 e x1 e o de saida y 0 e y 1 O canal é designado como simétrico porque a probabilidade p de receber 1 supondo ter sido transmitido O é igual a probabilidade de receber 0 supondo ter sido transmitido 1 como se ilustra no diagrama da Figura 82 Independentemente da distribuido apriori P p 82 83 Figura 82 Canal binário simétrico 82 Informação Mútua e Informação Condicional O conceito de entropia introduzido no capítulo 1 pode ser estendido a alfabetos conjuntos Def 82 Entropia conjunta Sejam X e Y os alfabetos de entrada e de saída de um canal discreto sem memória cuja distribuição de probabilidade conjunta é dada por 85 Então a entropia conjunta dos alfabetos X e Y é k m 2 M 1 m K k 1 k m log p x y p x y XY H 88 Recordemos que m 2 log p x mede a incerteza inicial apriori associada à transmissão do símbolo xm Por outro lado k m 2 y log p x mede a incerteza final sobre a transmissão do símbolo xm após ter sido recebido o símbolo k y O ganho de informação sobre o símbolo de entrada xm após observação do símbolo de saída k y é então dado pela diferença entre a incerteza inicial e a incerteza final ou seja m 2 k m 2 k m log p x y log p x I x y 89 A relação anterior pode escreverse na forma m k m 2 k m p x y p x log I x y 810 como é sabido k m k m k m p y p y x p x y p x 811 e portanto k m k 2 m k p y p y x log I y x 812 e m k k m I y x I x y 813 0 0 1 1 p p 1p 1p 84 É devido a esta relação de simetria que a quantidade m k k m ou I y x I x y é designada por informação mútua entre os acontecimentos X x m e Y yk A informação mútua média entre os alfabetos X e Y será então dada por M 1 m K k 1 k m k m p x y I x y I XY 814 Usando 810 e a identidade equivalente a 811 k m k m m k m p y p x p x y p x y p x em 814 obtemos M m 1 k m k m 2 K k 1 k m p y p x p x y log p x y I XY 815 Para interpretar o conceito de informação mútua média comecemos por recordar que k m 2 y log p x determina a incerteza final sobre a transmissão do símbolo xm uma vez observado o símbolo de saída k y isto é representa a informação própria de m x condicionada pela observação de k y k m 2 k m y log p x y I x 816 Def 83 Entropia condicional A entropia condicional mede em termos médios o acréscimo de informação sobre o símbolo de entrada do canal ganho pela observação do símbolo de saída M 1 m k m 2 K 1 k k m y log p x p x y H X Y 817 Rescrevendo 815 p x log p x y log p x x y p p x y log p x y log p x x y p log p x y log p x p x y XY I M m 1 m m 2 M m 1 k m 2 K k 1 k m M 1 m K k 1 k m m 2 M m 1 k m 2 K k 1 k m M m 1 m 2 k m 2 K k 1 k m e comparando com 817 verificamos que a primeira parcela do lado direito é exactamente H X Y enquanto que a segunda é a entropia do alfabeto de entrada Temos então I YX Y X Y X Y X XY I H H H H 818 A informagao miitua média mede portanto a incerteza média existente apriori sobre o simbolo de entrada do canal que é resolvida também em média pela observaao da saida do canal A relagao anterior pode ainda escreverse noutra forma Com efeito a expressdo 88 da entropia conjunta pode rescreverse como HYPE Fly vows Ht fb mJk 2 m k m1 kl PK ply ou ainda como cy XnVu HO F fay gs aed de Pl BG K M EHoleas fo ply k1 m1 UN ply M K Epler foes na m1 k1 UN plx Identificando as parcelas uma a uma concluimos que 108 HOX HY HXY 619 A Figura 83 ilustra de modo simbélico as relagdes entre as diversas quantidades introduzidas e que caracterizam a fonte 0 canal e a respectiva saida HX Y Hx Hix Hy IX Y Figura 83 Relagdes entre as quantidades que caracterizam a fonte o canal e a saida do canal 83 Capacidade de um Canal Discreto sem Memoria Ja anteriormente se fez notar que um canal discreto sem meméria é caracterizado pelas probabilidades de transicao definidas em 81 No entanto a informacgaéo mutua média entre os alfabetos de entrada fonte e de safda do canal depende também da distribuigao apriori definida em 83 Sendo o canal independente da fonte e sendo a informaao mutua média o ganho de informagao sobre a entrada do canal apds observagao da correspondente saida é natural pensarse em optimizar a eficiéncia de utilizagao do canal maximizando o ganho de informagao atras referido Uma vez que as probabilidades de transiao caracterizam o canal e 85 estao fora do contolo de quem pretende desenhar 0 sistema de comunicag6es 0 processo de optimizacao referido tera de assentar sobre a distribuigao de probabilidade apriori Def 84 Capacidade do canal discreto sem memoria A capacidade de um canal discreto sem memoria é 0 maximo da informacgéo mtitua média por cada utilizagdo do canal e relativamente a todas as possiveis distribuigdes de probabilidade apriori isto é C max 1X Y 820 PX m m12M A capacidade de canal medese em unidades binarias de informagao bit por intervalo de sinalizagao tempo de transmissao de um simbolo ou duragao de cada utilizagdo do canal Exemplo 82 Canal binario simétrico Consideremos o canal binario simétrico ja introduzido no Exemplo 81 Figura 82 e completamente especificado pelo parametro p probabilidade de erro Seja py PrX Xq obviamente p PrX X 1p Usando estes dados em 818 e maximizando em ordem a py concluise que C XY y p 1 2 821 isto é a informagdo muitua média é maxima quando os simbolos de entrada s4o equiprovaveis e a capacidade deste canal vale C1plog p1plog Ip 822 Notese que 822 se pode escrever como C1H onde Hpp log p1plog Ip é a funcdo 115 representada na Figura 11 do capitulo 1 Recordando essa figura podemos concluir que 1 quando nao existe rufdo de canal p0 e a capacidade atinge o seu valor maximo de um bit por cada intervalo de transmissao 2 quando o canal é ruidoso p0 ea capacidade atinge o valor minimo de 0 bit por intervalo de transmissfo quando p12 84 Teorema da Codificacao de Canal O teorema da codificagao de canal é um dos resultados mais importantes derivados por Shannon no contexto da Teoria da Informacao Este teorema estabelece um limite fundamental sobre o valor da taxa média de transmissao fidvel de informacfo através de um canal ruidoso 86 87 Teorema da Codificação de Canal Considerese uma fonte discreta sem memória com alfabeto X entropia H X e que gera um símbolo em cada s T segundos Consideremos também um canal discreto sem memória com capacidade C e que é usado uma vez em cada c T segundos Então se Tc C Ts H X 823 existe um código segundo o qual a saída da fonte pode ser transmitida através do canal e reconstruída com probabilidade de erro arbitrariamente pequena Ao contrário se Tc C Ts X H não é possível garantir a reconstrução fiável da informação transmitida A demonstração deste teorema que não faremos aqui não é construtiva1 Isto é apenas se garante a existência do código não o definindo Embora o problema da codificação de canal venha a ser discutido mais tarde em maior detalhe faz sentido introduzir as ideias fundamentais O objectico da codificação de canal é aumentar a resistência do sistema de comunicações digital face aos efeitos do ruído de canal No caso particular dos códigos de bloco a cada bloco de k bits da sequência binária gerada pela fonte fazse corresponder um bloco de n bits palavra de código com n k Este processo de codificação deve ser concebido de modo que a descodificação tenha solução única Notese que do universo de n 2 blocos binários de comprimento n apenas k 2 são palavras de código as que correspondem numa relação de um para um aos blocos binários de comprimento k gerados pela fonte Este esquema está representado simbolicamente na Figura 84 No caso de a transmissão se efectivar sem erros o processo de descodificação conduz ao bloco de comprimento k que havia sido gerado pela fonte Quando ocorrem erros de transmissão a palavra de comprimento n recebida pode não ser uma palavra de código e o erro é detectado eou corrigido Daqui resulta naturalmente uma probabilidade de erro por bit inferior à que existiria se não fosse usada a codificação de canal A codificação de canal pode ser encarada como o processo dual da codificação de fonte Enquanto neste caso se elimina redundância para melhorar a eficiência na codificação de canal controlase a redundância introduzida para melhorar a fiabilidade Figura 84 Codificação de canal 1 Referência indicada no fim do capítulo 1 k 2 k 2 k 2 k 2 2n n 2 transmissão sem erros transmissão com erros codificação descodificação detecção de erros 88 Exemplo 83 Canal binário simétrico Consideremos uma fonte binária sem memória que gera bits equiprováveis a uma taxa de um bit em cada s T segundos ou seja 1 Ts bps Neste caso a entropia da fonte é 1 pelo que a taxa de geração de informação é de 1 Ts bitsegundo2 A sequência fonte é codificada com base num codificador de razão r k n e que produz um símbolo em cada c T segundos À saída do codificador a taxa de transmissão de dados é 1 Tc baud O canal binário simétrico é assim usado uma vez em cada Tc segundos Portanto a capacidade do canal por unidade de tempo é C Tc bitsegundo onde C é dada por 822 De acordo com o teorema da codificação de canal se c s T C T 1 824 então pode forçarse a probabilidade de erro por bit a tomar um valor arbitrariamente pequeno através de uma codificação adequada Como Tc Ts k n r a condição 824 pode ser modificada para a forma equivalente r C 825 Deste modo podemos afirmar que existe um código com razão r que verificando 825 garante uma probabilidade de erro por bit tão pequena quanto queiramos Suponhamos que o parâmetro que caracteriza o canal binário simétrico vale 10 2 p e que queremos construir um código para o qual 8 e 10 P Usando aquele valor de p em 822 obtemos C 0 9192 bitsegundo Consideremos agora um código de repetição que para cada bit gerado pela fonte transmite 1 2m n bits iguais ou seja r 1 n Por exemplo para 1 m as palavras do código são 000 e 111 Suponhamos ainda que o descodificador funciona por maioria escolhe 0 se a palavra recebida tiver mais 0s do que 1s e viceversa Se for gerado um 0 transmitese 000 e o descodificador erra se receber 2 1s e um 0 ou 3 1s Portanto para o caso geral a probabilidade de erro por bit vem dada por n m 1 i n i i e p i p 1 n P 826 Calculando o valor de e P para diversos valores de r 1 n podemos construir a Tabela 81 r 1 1 3 1 5 1 7 1 9 11 1 Pe 102 10 4 3 106 10 7 4 108 10 10 5 Tabela 81 Probabilidade de erro média nos códigos de repetição Verificamos assim que e P decresce à medida que r diminui e que se atinge o valor máximo especificado de 8 e 10 P quando r 1 9 Reparese que neste caso transmitimos 9 bits em representação de um único bit da fonte o que se traduz no facto de C 0 9192 0 1111 r Ao contrário o que o teorema da codificação de fonte diz é que basta que r C igual no limite Portanto os códigos de repetição não são deste ponto de vista os mais eficientes existindo como veremos mais tarde métodos de codificação mais adequados 2 A distinção entre taxa de geração de dados binários e taxa de geração de informação é muito importante no contexto aqui considerado Notese que aqui ambas têm o mesmo valor pois os símbolos são equiprováveis 85 Entropia Diferencial O conceito de entropia introduzido no contexto das variaveis aleat6rias discretas pode ser de algum modo generalizado para o caso das variaveis aleatorias continuas desde que se tenham em conta alguns detalhes técnicos que discutiremos adiante Def 85 Entropia diferencial Consideremos uma fonte analégica modelada pelo processo Xt Seja X a varidvel aleatéria continua que descreve estatisticamente a amplitude Xt do referido processo em qualquer instante f e fx x a respectiva densidade de probabilidade A entropia diferencial de xXé rx aa Cie ee O termo entropia diferencial é usado para marcar as diferencas relativamente ao conceito de entropia de fontes discretas Suponhamos que X tem uma distribuicéo uniforme l a Oxa fy x De 0 caso contrario substituindo em 827 obterseia hx log a a qual toma valores negativos quando a 1 e tornase singular quando a oo Recordese que a entropia de uma fonte discreta é sempre positiva e limitada Portanto ao contrario da entropia de fontes discretas a entropia diferencial definida para fontes analdgicas nao pode ser interpretada como uma medida de aleatoriedade ou de incerteza Suponhamos que a varidvel aleatéria X constitui a forma limite de uma varidvel aleatéria discreta que toma os valores x kA k101 e onde A 0 éarbitrariamente pequeno Assim sendo podemos assumir que Prx X x A fy x JA e no limite quando A 0 a entropia da fonte continua seria 00 HX lim yf x JA log fx x JA A0 k00 foo too Ay yt x log fF x NA yt x log A JA x kco kco ou atendendo a 827 too HxhX lim logA fx x A 828 A0 kco Consideremos a segunda parcela do lado direito de 828 e notemos que para valores de A suficientemente pequenos se tem 89 810 x 2 x k X x k X log x f x f quando x 0 o termo à direita nesta desiguladade tornase infinitamente maior do que o termo da esquerda pelo que embora k X x k X x 1 x dx f x f 0 lim k x k X x 2 x x f log 0 lim não existe Daqui se conclui que a entropia 828 de uma fonte contínua é infinitamente grande Esta conclusão deriva do facto de ser infinita a quantidade de informação associada ao acontecimento 0 0 x x X quando X é uma variável aleatória contínua No entanto e voltando a 828 a entropia diferencial pode ser interpretada como a entropia da fonte contínua medida relativamente à referência k x k X x 2 x x f log 0 lim Neste contexto supondo que X e Y são respectivamente a entrada e a saída de um canal sem memória podemos generalizar o conceito de informação mútua entre X e Y Em particular dudv v u f f u v f u v log f XY I Y X XY 2 XY 829 Entre outros factos pode mostrarse que sendo a entropia diferencia condicional dada por v dudv u Y f u v log f X Y XY 2 XY h 830 então Y X Y X Y X I XY h h h h 831 Como em 831 o termo de referência no cálculo da entropia é o mesmo a informação mútua pode continuar a ser interpretada tal como no caso de fontes e canais discretos 851 Máxima Entropia Neste parágrafo vamos resolver um problema cujos resultados serão necessários mais adiante e cuja formulação se apresenta de seguida 811 Calcular a função densidade de probabilidade fX que maximiza x dx f x log f X X 2 X h 827 sob as restrições 1 f X u du 832 e 2 X X 2 u du f m u σ 833 onde u du f u m X X 834 Para resolver este problema vamos novamente recorrer à técnica dos multiplicadores de Lagrange começando por determinar os pontos de estacionariedade da Lagrangeana σ λ λ 2 X 2 X 2 X 1 X 2 X X u du f m u 1 u du f u du f u log f L f 835 No entanto é necessário ter em conta que o problema em causa exige a maximização de 835 relativamente a uma função definida sobre o conjunto dos números reais e não relativamente a um parâmetro Suponhamos que fX é a função que maximiza 827 cumprindo as restrições 832 e 833 Então podemos definir f f f X X ε ε 836 onde f ε ε representa uma perturbação relativamente à função maximizante f X Sublinhe se que ε é um parâmetro real arbitrário tal como f ε Os pontos de estacionariedade de 835 são aqueles que verificam a condição necessária de existência do máximo 0 0 L ε ε 837 Se em 835 substituirmos f X por f X definido em 836 e em seguida usarmos 837 obteremos 0 du m u log e u log e ln f u f 2 X 2 1 2 X 2 λ λ ε 0 que atendendo ao facto de f ser uma fungdo arbitraria s6 se verifica se o factor entre da integranda for nulo ou seja x x Inf u14 2 um VueR 838 loge loge Usando esta relagao podemos impor as restrigdes 832 e 833 e apds resolver o sistema de equacées resultante obtemos os multiplicadores de Lagrange 1 e log 2 210 loge r 52 20 os quais uma vez subsitufdos em 838 permitem obter 0 resultado final x My y 1 20 f xe 0Xoo Vv 210 Concluso a entropia diferencial da variavel aleatoria X cuja variancia é o é maxima se X for gaussiana Por outras palavras se X e Y forem varidveis aleatérias continuas ambas com a mesma variancia e se X for gaussiana entao hxhY 86 Teorema da Capacidade de Canal Consideremos 0 processo X t estacionario de média nula e com largura de banda B Suponhamos que X t é amostrado uniformemente com periodo T Sejam X XkT as varidveis aleatérias que modelam estatisticamente as amostras xt do processo X t nos instantes tkT Admitamos que as amostras x sao transmitidas através de um canal perturbado por rufdo aditivo branco e gaussiano com espectro de poténcia constante e igual a n2 Se o canal de transmissfo tiver largura de banda B entdo a respectiva safda é modelada pela variavel aleatéria Y X N k01K1 839 onde N é uma varidvel aleatéria gaussiana independente de X com média nula e variancia o nB 840 Admitamos ainda que P EX k01K1 841 812 813 Supondo que a amostragem é feita ao ritmo de Nyquist então o número K de amostras transmitidas num intervalo de tempo com duração T é K 2BT 842 Por analogia com 820 a capacidade do canal gaussiano será k k X I X Y u f max C k 843 onde k Yk I X é a informação mútua entre k X e k Y definida em 829 e que verifica 831 isto é k k k k k Y X Y I X Y h h 844 Notese que de acordo com 839 e 840 a variável aleatória k k k x Y X é gaussiana com média k x e variância B 2 σ η Por outro lado usando a definição de entropia diferencial 827 verificase facilmente que a entropia diferencial de uma gaussiana com variância 2 σ não depende do respectivo valor médio e vale 2 2 e log 2 2 π σ Portanto podemos escrever k k k k N Y I X Y h h 845 Como k N é independente de k X então o cálculo da capacidade do canal 843 envolve apenas a maximização de h Yk onde k Y tem variância PX ηB Este problema foi resolvido no parágrafo 851 h Yk é máxima com k Y gaussiana Temos então B 2 e 2 log 1 Y 2 k η π PX h 846 e 2 e B 2 log 1 N 2 k π η h 847 O valor máximo da informação mútua 845 resulta de 846 e 847 pelo que tendo em conta 843 obtémse a capacidade do canal gaussiano η B 1 2 log 1 C 2 PX bitutilização Finalmente como o canal é usado K vezes em T segundos usando 842 vem η B 1 Blog C 2 PX bitsegundo 848 De acordo com o teorema da codificação de canal sabemos que desde que se use o código adequado é possível transmitir através do canal gaussiano com largura de banda B à taxa máxima C dada por 848 com probabilidade de erro arbitrariamente pequena Para uma largura de banda B fixa a taxa de transmissão de informação exequível aumenta com a razão PX η No entanto se estes parâmetros se mantiverem fixos aquela taxa de transmissão aumenta com a largura de banda B aproximandose de um valor limite quando 814 B SNR η PX se anula De facto usando a aproximação 0 x x log e x 1 log 1 2 2 concluímos que quando B 0 B SNR η PX e η log2 e 1 PX C Portanto mesmo que a largura de banda do canal cresça indefinidamente a respectiva capacidade e portanto a taxa máxima de transmissão fiável de informação permanece limitada 87 Sistema Ideal de Comunicações Por hipótese assumiremos que no sistema ideal a transmissão de informação é feita à taxa máxima isto é igual à capacidade C do canal gaussiano Assim se E for a energia dispendida na transmissão de cada unidade de informação podemos dizer que a potência transmitida vale PX CE Assim sendo 848 escrevese na forma η B E C 1 log B C 2 s 1 Hz 1 bit 849 Notese que CB mede a eficiência espectral máxima do canal isto é dá o número máximo de unidades de informação transmitidas por unidade de tempo e por unidade de largura de banda do canal A Figura 85 mostra o andamento da eficiência espectral em função de E η Figura 85 Eficiência espectral A zona sombreada do plano abaixo da curva R C constitui a região útil de utilização do canal gaussiano Para o caso do sistema ideal o limiar dB 61 E η obtémse invertendo 849 com R C Neste sistema a probabilidade de erro é Pe 0 se o canal for usado abaixo daquele limiar isto é se dB 61 E η Ao contrário se dB 61 E η então 1 Pe E η dB RB R C R C R C 16