O teorema da codificação de canal
Transcrição
O teorema da codificação de canal
1.3. Teorema da codificação de canal • Ritmo de informação • Teorema da codificação de canal Teoria da Informação Teorema da codificação de canal 1 Ritmo (ou taxa) de informação • Se a fonte de entropia H(X) emitir uma sequência de n 1 símbolos a informação total a ser transferida é de nH ( X ) bits. • Se a fonte produzir r símbolos/s a duração da sequência de n símbolos é n/r segundos. • Portanto, a informação deve ser transferida à razão média de: R= informação total nH ( X ) = = rH ( X ) bits/s duração total nr Esta é a taxa de informação da fonte. Se a fonte produzir símbolos com diferentes durações τ i (segundos) o ritmo, ou taxa, de informação pode ser calculado alternativamente como R= H (X ) τ bits/s em que τ é a duração média de cada símbolo, M τ = P1τ1 + P2τ 2 + ... + PM τ M = ∑ Piτ i . i =1 Teoria da Informação Teorema da codificação de canal 2 O teorema da codificação de canal (aplicado a canais discretos sem memória) A entropia representa a informação esperada por cada símbolo de fonte. • Se tivermos duas fontes com iguais entropias, aquela que produzir mais símbolos por unidade de tempo vai colocar mais exigências no sistema de comunicações. (imagine duas pessoas a ler o mesmo texto escrito numa língua que domina mal. Uma delas lê depressa. Qual é a que entende melhor?) • O ritmo de informação mede a quantidade de informação produzida num certo intervalo de tempo. • Existem limitações físicas fundamentais à transferência de informação (ruído, largura de banda, …), que se reflectem na capacidade do canal: • A capacidade do canal (em bits/s) mede a quantidade de informação que um canal pode transferir por unidade de tempo. Shannon relacionou estes dois conceitos através do teorema da codificação de canal, também chamado Teorema Fundamental da Teoria da Informação: Dado um canal de capacidade C e uma fonte com ritmo de informação R, então se R ≤ C existe uma técnica de codificação tal que a saída da fonte pode ser transmitida através do canal com uma frequência arbitrariamente pequena de erros, apesar da presença de ruído. Se R > C, não é possível a transmissão sem erros. Teoria da Informação Teorema da codificação de canal 3 O teorema da codificação de canal aplicado a canais discretos sem memória (formulação alternativa) Teorema: “Uma fonte X de entropia H(X) produz símbolos à razão de um símbolo por cada Ts segundos. Consideremos um canal discreto sem memória de capacidade Cs (bits/símbolo!) e que seja usado uma vez em cada Tc segundos. Então, se H ( X ) Cs ≤ , Ts Tc existe uma técnica de codificação dos símbolos da fonte que permite que os símbolos transmitidos através do canal possam ser recuperados com uma probabilidade de erro arbitrariamente pequena. Se, pelo contrário, H ( X ) Cs , então não é possível transmitir os símbolos e > Ts Tc recuperá-los com uma probabilidade de erro arbitrariamente pequena.” Conversão de Cs (bits/símbolo) em C (bits/s): C= Teoria da Informação Cs Tc Teorema da codificação de canal 4 Aplicação do “Teorema da Codificação do Canal” a um canal binário simétrico Considere-se uma fonte binária a gerar símbolos equiprováveis de duração Ts segundos, ou seja, a produzi-los à taxa de r = 1 Ts símbolos por segundo. Sendo os símbolos binários equiprováveis, a entropia da fonte vale H ( X ) = 1 bit/símbolo e a taxa de informação da fonte é R = rH ( X ) = 1 Ts bits/s. 1 símbolo em Ts segundos 1 dígito binário em Tc segundos capacidade por unidade de tempo = Cs/Tc bits/s (r=1/Ts) Fonte binária Codificador de canal binário rH(X) bits/s Canal binário simétrico Rc=k/n O codificador (de canal!) produz um símbolo binário em cada Tc segundos, o qual é transmitido através de um canal binário simétrico (BSC) – que, portanto, é usado uma vez em cada Tc segundos. Assim, a capacidade do canal por unidade de tempo é C = Cs Tc bits/s. De acordo com o teorema da codificação do canal, terá de ser H ( X ) Cs ⇒ ≤ Ts Tc Mas 1 Cs ≤ Ts Tc ⇒ Tc ≤ Cs Ts Tc = Rc (taxa do código, ver a seguir), pelo que Ts Rc ≤ Cs Como a capacidade do canal BSC é Cs = 1 − Ω( p) : Rc ≤ 1 − Ω( p) Teoria da Informação (canal BSC) Teorema da codificação de canal 5 Aplicação do “Teorema da Codificação do Canal” a um canal binário simétrico (contin.) Porque é que Tc = Rc ? Ts Antes da codificação Ts k=4 Duração do bloco: 4Ts Tc n=7 Duração do bloco: 7Tc Depois da codificação À razão k = Rc chama-se taxa do código. n Como a duração dos blocos é a mesma: kTs = nTc ou, neste caso, 4Ts = 7Tc ⇒ Tc Ts = 4 7 = Rc Em resumo, temos duas maneiras de exprimir o teorema da codificação de canal: • Com a capacidade expressa em bits/símbolo, Cs: Rc ≤ Cs • Com a capacidade expressa em bits/s, C: R = rH ( X ) ≤ C bits/s Teoria da Informação bits/símbolo C = Cs Tc Teorema da codificação de canal 6