Teoria da Informação e Criacionismo: Teoria da Informação Clássica (Shannon)

Neste Artigo

• Claude Shannon e a Teoria da Informação Clássica
• Fontes de Informação
• Informação, Entropia e Incerteza
• Entropia Condicional e Conjunta
• Implicações para a Comunicação
• Informação e Ruído
• Entropia de Shannon vs. Entropia Termodinâmica
• Links

Claude Shannon e a Teoria Clássica da Informação[Topo]

A comunicação digital moderna depende da Teoria da Informação, que foi inventada na década de 1940 por Claude E. Shannon. Shannon publicou pela primeira vez A Teoria Matemática da Comunicação em 1947-1948, e publicou conjuntamente The Teoria Matemática da Comunicação com Warren Weaver em 1949. Esse texto ainda está em publicação pela University of Illinois Press. A Teoria da Informação, às vezes referida como Teoria da Informação Clássica em oposição à Teoria da Informação Algorítmica, fornece um modelo matemático para a comunicação. Embora Shannon estivesse principalmente preocupado com o problema das comunicações eletrônicas, a teoria tem uma aplicabilidade muito mais ampla. A comunicação ocorre sempre que coisas são copiadas ou movidas de um lugar e/ou tempo para outro.

Este artigo descreve brevemente os principais conceitos da teoria de Shannon. As demonstrações matemáticas estão prontamente disponíveis em muitas fontes, incluindo os links da Internet nesta página. Embora a teoria de Shannon abranja tanto a comunicação digital quanto a analógica, a comunicação analógica será ignorada por simplicidade. Por outro lado, a Teoria da Informação é um assunto bastante técnico, geralmente introduzido a estudantes universitários de engenharia do terceiro ano. Compreendê-la realmente requer conhecimento de estatística e cálculo.

Para aqueles que se perguntam como uma teoria sobre comunicação pode possivelmente se relacionar com a evolução biológica, uma visita ao site da web de Tom Schneider, Teoria da Informação Molecular e a Teoria das Máquinas Moleculares, pode ajudar. De qualquer forma, os criacionistas agora gostam de argumentar sobre informação, e este artigo fornece material de fundo útil sobre o assunto.

Fontes de Informação[Topo]

Uma fonte de informação é um sistema que emite, a partir de um conjunto fixo de M símbolos {a_1..a_M}, em uma sequência a uma certa taxa (veja Fig.1). No caso mais simples, cada símbolo que pode ser emitido pelo sistema é igualmente provável. A letra i representará algum símbolo de saída dado do conjunto {a_1..a_M}. Se todos os símbolos forem igualmente prováveis, então a probabilidade de que o símbolo i seja o produzido é p_i=P=¹/_M independente de qual símbolo temos em mente. Por exemplo, se a fonte de informação pode produzir quatro símbolos igualmente prováveis (A, B, C e D), então cada símbolo tem uma probabilidade de .25 (isto é, 25% ou 1/4).

Fig. 1. Fonte de Informação e Observador

Um observador está incerto quanto ao símbolo M que será emitido. Uma vez que um símbolo dado a_i é observado, o observador obteve informações da fonte. A incerteza do observador é reduzida. A quantidade de informação obtida pode ser medida porque o número de símbolos possíveis é conhecido. Por definição, a medida da informação I observada do sistema é dada por:

I = log₂ M=-log₂P,

e a unidade de medida é dígitos binários, ou bits. A unidade de medida depende da base do logaritmo. Na maioria das vezes, a Teoria da Informação usa o logaritmo de base 2 (log₂). Qualquer outra base de logaritmo funcionaria. Se usássemos a base 10, então a unidade de medida seria dígitos decimais.

Se um sistema pode produzir qualquer um dos 16 símbolos possíveis, para cada símbolo observado o observador recebe 4 bits de informação. Ou seja, isso reduz a incerteza do observador em 4 bits (veja Fig.2). O uso de logaritmo para medir a informação deve-se a Ralph V.L. Hartley, cujo artigo de 1928 é citado por Shannon.

Fig. 2. Observa-se um dos 16 Símbolos Possíveis

É fácil ver a utilidade nesta definição. Quando uma fonte de informação capaz de produzir qualquer um dos 128 símbolos básicos do ASCII, todos igualmente prováveis, produz um símbolo, o observador obtém 7 bits de informação, exatamente o número de bits usado para codificar o conjunto básico de símbolos do ASCII. (ASCII significa American Standard Code for Information Interchange, em uso há muitos anos em máquinas de teletipo e computadores. Claro que uma fonte de informação ASCII real não produz 128 símbolos igualmente prováveis, mas, por simplicidade, vamos fingir que ela o faz agora.)

Fig. 3. Sistema de Comunicação

Shannon descreve um sistema de comunicação como uma fonte de informação, transmissor, canal, receptor e destino (veja Fig. 3). O destino é nosso observador. Um requisito básico para um sistema de comunicação é que, com alta confiabilidade, o símbolo na fonte de informação e o símbolo no destino coincidam. Shannon teve uma percepção fundamental sobre isso: não importa se o símbolo significa algo. O que apenas importa é se o símbolo na fonte de informação e no destino são iguais. Foi essa percepção, o significado deve ser ignorado, que permitiu a Shannon criar um modelo matemático viável para a informação.

Em seguida, considere que os símbolos emitidos por uma fonte de informação podem não ser igualmente prováveis. Suponha que os símbolos {a_1..a_M} ocorram com probabilidades p₁..p_M. Como {a_1..a_M} são todos os símbolos possíveis, a soma das probabilidades p_i para todos os i é 1. Como o observador não sabe qual será o próximo símbolo na sequência de saída, a fonte de informação é tratada como um processo estocástico. Ou seja, assumimos que os símbolos emitidos são aleatórios, ocorrendo com as probabilidades dadas.

Um exemplo simples de um processo estocástico é uma pessoa lançando uma moeda repetidamente (ver Fig.4). Os resultados são às vezes cara e às vezes coroa, mas não podemos prever os resultados para qualquer lançamento específico da moeda. Assumimos, é claro, que a moeda é uma moeda justa, que tem uma chance de 50% de cara e uma chance de 50% de coroa quando lançada. Se registrássemos a sequência de lançamentos de moeda, ela poderia parecer HHTHTHHTHTTTTHTHHT...

Fig. 4. Um Processo Estocástico Simples

O próximo conceito necessário é uma máquina de estados finitos. Este é um tipo de máquina que possui um número finito de condições ou estados nos quais pode estar em qualquer ponto no tempo. Um interruptor de luz, por exemplo, tem dois estados - LIGADO e DES Ligado. Uma máquina de estados finitos não precisa existir fisicamente. Pode ser simplesmente um modelo matemático em papel ou em um computador. O estado da máquina pode ser registrado conforme o tempo passa, produzindo uma sequência semelhante à de uma moeda lançada. Se registrássemos a posição de um interruptor de luz no quarto de uma criança hiperativa a cada 15 minutos, poderia até parecer bastante aleatório, como LIGADO - LIGADO - DESLIGADO - LIGADO - DESLIGADO - LIGADO - LIGADO - DESLIGADO - LIGADO - DESLIGADO - DESLIGADO - DESLIGADO - DESLIGADO - LIGADO - DESLIGADO - LIGADO - LIGADO - DESLIGADO... exatamente como lançar uma moeda.

Agora podemos modelar uma fonte de informação como um tipo de máquina de estados aleatórios, pulando de estado para estado, com cada estado correspondendo ao próximo símbolo de saída. Ainda podemos dar a informação recebida observando o símbolo i em termos de sua probabilidade:

I_i=-log₂p_i

Pensando na fonte de informação dessa maneira, é razoável supor que a probabilidade de seu próximo estado dependerá de seu estado atual. Por exemplo, um interruptor de luz no quarto de um octogenário sedentário provavelmente não mudaria muito a cada 15 minutos: ON - ON - ON - ON - ON - ON - OFF - OFF - OFF - OFF...

Vamos considerar uma única mudança de estado. Nossa máquina de estados pode mudar do estado i para o estado j. Essa mudança de estado tem uma certa probabilidade. Podemos descrever a probabilidade de que j siga i como p(j|i). A notação p(j|i) é lida em voz alta como "a probabilidade de j dado i." Se você ler o artigo de Shannon, note que ele usa uma notação menos convencional p_i(j) em vez de p(j|i).

Para manter as coisas simples, não vamos fazer nossa máquina de estados lembrar qual era o seu estado anterior. Ela só sabe em qual estado ela está agora. Isso significa que a probabilidade do seu próximo estado pode depender apenas do estado atual. Não pode depender de como a máquina chegou ao estado atual. Se então olharmos para todas as possíveis transições de estado da máquina, podemos escrever o conjunto de probabilidades de transição de estado. Para cada símbolo i, a soma de todos os p(j|i) sobre j é 1. O conjunto de probabilidades de transição de estado para nosso interruptor de luz é:

{ p(ON|ON), p(ON |OFF), p(OFF|ON), p(OFF|OFF) }

É fácil ver que p(ON|ON) + p(OFF|ON) = 1, e também que p(ON|OFF) + p(OFF|OFF) = 1.

Um processo estocástico desse tipo, onde a distribuição de probabilidade do próximo estado depende do estado atual, mas de nada anterior, é chamado de processo de Markov discreto. Shannon representa fontes de informação como processos de Markov discretos. Ou seja, a fonte de informação é assumida como um processo aleatório, produzindo uma sequência de símbolos a partir de um conjunto fixo de símbolos, onde a probabilidade de cada novo símbolo depende apenas do símbolo anterior. A máquina de estados não pode lembrar nada anterior a isso.

Um processo ergódico é uma classe especial de processo de Markov. Para um processo ergódico, todas as sequências que ele pode produzir são iguais em propriedades estatísticas. Se a fonte de informação for ergódica, então a probabilidade de que o símbolo j ocorra após N símbolos, P_j(N), converge para um valor de equilíbrio com N cada vez maior. Shannon faz uma suposição geral de que as fontes de informação são processos ergódicos.

Informação, Entropia e Incerteza[Topo]

Lembre-se de que o observador começa completamente incerto quanto à sequência de símbolos que será emitida pela fonte de informação. À medida que cada símbolo é observado, a incerteza diminui. Podemos representar a fonte de informação como uma variável aleatória, já que seu estado pode corresponder a qualquer valor no conjunto de símbolos, e chamaremos ela de X, assim como Shannon faz. A variável aleatória X pode produzir qualquer um dos M símbolos {a_1..a_M}. Cada um desses símbolos tem uma probabilidade p₁ .. p_M, e essas probabilidades devem somar 1.

A informação recebida de X quando produz um símbolo i é

I_X=-log₂p_i

A entropia de X é definida pela sua informação média:

H(X) = E{I_X}=-∑ _i(p_ilog₂p _i)

A notação E{I_X} denota o valor esperado de I_X, que é um termo mais específico em estatística do que “média”. A entropia também pode ser chamada de incerteza média (estritamente falando, a redução média na incerteza para um receptor).

Por que a entropia da informação é definida como essa soma ponderada de probabilidades? Principalmente porque as probabilidades associadas aos símbolos não são, em geral, iguais. Considere as 26 letras do alfabeto inglês. Como Shannon observou, a letra "E" ocorre com mais frequência que "Q", a sequência "TH" mais que "XP", etc. Ao definir a entropia como a informação média, ela nos dirá algo sobre o quão plenamente um canal de comunicação está sendo utilizado.

A função de entropia H(X) é máxima quando p_i=¹/_M para todos os i. Isso faz sentido intuitivo, porque a incerteza é maior quando todos os resultados são igualmente prováveis. Por outro lado, se uma fonte de informação produz o símbolo a₁ com probabilidade .999 e dez outros símbolos a₂..a₁₁ cada um com probabilidade .0001, estamos quase certos de que o próximo símbolo será a₁.

Fig. 5. Entropia de uma Fonte Binária

Considere uma fonte binária de informação capaz de produzir símbolos 0 e 1. Sua entropia como função da probabilidade p₁ do símbolo 1 é mostrada em Fig.5. (Lembre-se de que p₀₌1-p₁ porque apenas dois símbolos são permitidos e suas probabilidades devem somar 1). Observe que a entropia atinge um máximo de 1 quando p₁=p₀=1/2. Quando ambos os símbolos são igualmente prováveis, o observador está mais incerto. A sequência de caras ou coroas de múltiplos lançamentos de uma moeda justa, por exemplo, tem entropia máxima. Por outro lado, se a fonte de informação sempre produzisse o símbolo 1 com probabilidade p₁=1, a entropia e a incerteza do observador seriam zero. Se a fonte de informação nunca produzisse o símbolo 1, mas sempre produzisse o símbolo 0, a entropia e a incerteza do observador também seriam zero. Nenhuma informação é ganha ao observar um evento conhecido por nunca mudar.

Entropia Condicional e Conjunta[Top]

Se X e Y são variáveis aleatórias representando, respectivamente, a entrada e a saída de um canal, então a entropia condicional (ou seja, a incerteza média do símbolo recebido dado que X foi transmitido) é:

H(Y|X)=-∑_i,j p(x_i,y_j)log₂ p(y_j|x_i),

a entropia conjunta (ou seja, a incerteza média do sistema de informação total) é:

H(X,Y)=-∑_i,j p(x_i,y_j)log₂ p(x_i,y_j),

e a entropia de ambiguidade (ou seja, a incerteza média do símbolo transmitido após a recepção de um símbolo) é:

H(X|Y)=-∑_i,j p(x_i,y_j)log₂ p(x_i|y_j).

A notação p(A,B) significa a probabilidade de A e B ocorrerem ambos, enquanto p(A|B) significa a probabilidade de A ocorrer dado que B já ocorreu.

Uma relação importante é:

H(X,Y)=H(X|Y)+ H(Y)=H(Y|X)+H( X).

Implicações para a Comunicação[Topo]

Shannon demonstrou que, para um canal com capacidade C e uma fonte de informação com entropia H, é possível transmitir a saída codificada da fonte de informação através do canal a uma taxa média de até (^C/_H) -e, onde e é um número arbitrariamente pequeno. Não é possível transmitir a uma taxa média superior a ^C/_H.

Shannon e R.M. Fano desenvolveram independentemente um método de codificação eficiente, conhecido como técnica de Shannon-Fano, no qual o comprimento do código aumenta com a diminuição da probabilidade do símbolo da fonte ou da palavra da fonte. A ideia básica é que os símbolos frequentemente utilizados (como a letra E) devem ser codificados com menos bits do que os símbolos pouco utilizados (como a letra Z) para aproveitar melhor o canal, ao contrário da codificação ASCII, onde tanto E quanto Z exigem os mesmos sete bits.

Se a comunicação ocorre com entrada X e saída Y, a capacidade de um canal é:

C = Max ( H(X) - H(X | Y) )

A função Max(H) significa o valor máximo de H. Para um canal sem ruído, H(X|Y)=0. Como H(X) é máximo quando todos os M símbolos possíveis para X são igualmente prováveis, C=log₂M, ou C=I(X).

Shannon também forneceu a base matemática para a transmissão em um canal com ruído (ver Fig.6). Um canal ruidoso pode ser visto como conectado a dois processos estocásticos: a fonte de informação e a fonte de ruído.

Fig. 6. Sistema de Comunicação com Ruído

Se X é a fonte de informação e Y é a informação recebida, então, ao utilizar um novo canal (um canal de correção) com capacidade igual à entropia condicional H(Y|X), é possível codificar os dados de correção de modo que todas as exceção de uma fração arbitrariamente pequena e dos erros possam ser corrigidas (ver Fig.7). Se a entropia da fonte de informação H ≤C, então a fonte de informação pode ser transmitida com uma taxa de erro arbitrariamente pequena. Se H>C, então nenhum método de codificação é possível de tal forma que a ambiguidade seja menor que H-C.

Fig. 7. Codificação para Reduzir Erros Devidos ao Ruído

Há muitos exemplos na literatura de códigos de correção de erros. Alguns dos mais conhecidos são os códigos de Hamming, Reed-Solomon, Viterbi e Fire.

Informação e Ruído [Topo]

Um ponto importante a ter em mente é que tanto a fonte de informação quanto a fonte de ruído nas Fig. 6 e Fig. 7 são processos estocásticos. Ambos poderiam ser tratados como fontes de informação. A principal diferença entre eles é que o receptor está interessado na fonte de informação e deseja ignorar a fonte de ruído.

Em algumas situações, uma fonte de ruído é intencionalmente observada, neste caso, torna-se uma fonte de informação. Por outro lado, às vezes, a informação é copiada acidentalmente de um canal para outro. Isso é chamado de crosstalk, e seu resultado é que a fonte de informação sem interesse de outra pessoa é considerada ruído.

Quando os cientistas medem a radiação de fundo cósmico para estudá-la, ela é informação. A interferência em um sistema de comunicação proveniente da radiação de fundo cósmico é ruído. Os dados de elevação do terreno podem ser considerados aleatórios. Se você registrá-los para criar um mapa topográfico, eles são informação. Se você deseja medir o diâmetro de um planeta, eles são ruído. Este conceito, de que a informação de uma pessoa é o ruído de outra e vice-versa, é comumente mal compreendido em discussões leigas sobre a Teoria da Informação. Para reiterar, é o interesse do observador que transforma um processo estocástico em uma fonte de informação.

Alguns criacionistas argumentarão que o ruído degrada a informação da mesma forma que a Segunda Lei da Termodinâmica degrada a ordem, e implicarão que a Segunda Lei se aplica à informação. Mas, para a definição de informação de Shannon, como não nos importamos com o significado, e como a diferença entre informação e ruído depende apenas do nosso interesse, esse argumento não tem fundamento. Transformamos ruído em informação simplesmente decidindo nos importar com ele, e informação em ruído escolhendo ignorá-la. Além disso, a ordem termodinâmica diz respeito à disposição de moléculas e objetos similares, não a símbolos matemáticos, portanto, seu argumento é duplamente errado. Os símbolos de informação são abstrações matemáticas e não precisam se comportar como qualquer sistema físico particular (como uma coleção de moléculas), como será visto na próxima seção.

Alguns criacionistas também argumentam por uma Lei de Conservação da Informação, semelhante à Primeira Lei da Termodinâmica. Devemos lembrar que a Conservação de Energia é um princípio estabelecido por mais de 150 anos de coleta de dados rigorosa, e não há nenhum rigor por trás da noção de Conservação da Informação. De qualquer forma, sob a definição de Shannon de informação, esta lei proposta é sem sentido. Tudo o que você precisa para criar informação é um processo ergódico e um observador para observá-lo. O decaimento atômico fornece um exemplo físico simples. Um observador do decaimento atômico obtém nova informação (qual átomo, que hora, quais produtos) conforme cada átomo decai.

Entropia de Shannon vs. Entropia Termodinâmica[Topo]

A função de entropia informacional de Shannon tem exatamente a mesma forma que a equação do H-Teorema de Boltzmann:

H(t) = ∫f ln f dc

onde ∫ é o símbolo de integral do cálculo, ln significa logaritmo natural (base e), f é a função de distribuição para moléculas em um gás ideal, e c é o espaço de velocidades. O símbolo H é usado na Teoria da Informação devido a essa semelhança.

Curiosamente, o movimento browniano (o movimento térmico aleatório das moléculas) também é um processo de Markov. É a partir da fórmula H(t) que podemos derivar:

S = k ln w

onde S é a entropia termodinâmica de um sistema, k é a constante de Boltzmann e w é a desordem do sistema; isto é, a probabilidade de que um sistema exista no estado em que se encontra em relação a todos os estados possíveis em que poderia estar. O Teorema H de Boltzmann nos diz que, após muito tempo, f atingirá o equilíbrio. Isso é semelhante ao que Shannon nos diz sobre fontes de informação modeladas como processos ergódicos. Apesar das semelhanças, a entropia de Shannon e a entropia termodinâmica não são a mesma coisa. A entropia termodinâmica caracteriza um ensemble estatístico de estados moleculares, enquanto a entropia de Shannon caracteriza um ensemble estatístico de mensagens.

Na termodinâmica, a entropia tem a ver com todas as maneiras pelas quais as moléculas ou partículas podem estar dispostas, e maior entropia significa que menos trabalho físico pode ser extraído do sistema. No uso de Shannon, a entropia tem a ver com todas as maneiras pelas quais as mensagens podem ser transmitidas por uma fonte de informação, e maior entropia significa que as mensagens são mais igualmente prováveis. A entropia na teoria da informação não significa que a informação está se tornando mais inútil ou degradada; e porque é uma abstração matemática, ela não se relaciona diretamente com o trabalho físico salvo se você estiver tratando moléculas de forma informacional.

A entropia de Shannon foi relacionada pelo físico Léon Brillouin a um conceito às vezes chamado de negentropia. Este é um termo introduzido pelo físico e laureado com o Prêmio Nobel Erwin Schrödinger em seu texto de 1944 O que é a Vida para explicar como os sistemas vivos exportam entropia para o ambiente enquanto se mantêm em baixa entropia; em outras palavras, é o negativo da entropia. Em seu livro de 1962 Ciência e Teoria da Informação, Brillouin descreveu o Princípio da Negentropia da Informação ou NPI, o cerne do qual é que adquirir informações sobre os microestados de um sistema está associado a uma diminuição da entropia (é necessário trabalho para extrair informações, e a apagação leva a um aumento da entropia termodinâmica). Não há violação da Segunda Lei da Termodinâmica envolvida, já que uma redução na entropia termodinâmica de qualquer sistema local resulta em um aumento da entropia termodinâmica em outro lugar.

A relação entre a entropia da informação de Shannon H e a entropia S da mecânica estatística foi estabelecida com mais rigor por Edwin Jaynes em 1957. O resultado é que a entropia da informação e a entropia termodinâmica são métricas intimamente relacionadas, mas não são a mesma métrica. Para a maioria dos praticantes da Teoria da Informação até agora, isso não representa nenhum problema, pois seu campo é a comunicação e o cálculo usando circuitos eletrônicos convencionais, onde o significado termodinâmico da entropia não é discutido. A terminologia conflitante resulta, no entanto, em muita confusão em áreas como máquinas moleculares e física do cálculo, onde a entropia da informação e a entropia termodinâmica são tratadas lado a lado. Alguns autores, como Tom Schneider, argumentam pela eliminação da palavra entropia para a função H da Teoria da Informação e pelo uso do outro termo de Shannon, incerteza (surpresa média), em vez disso. Para mais sobre isso, veja A Informação Não é Entropia, a Informação Não é Incerteza!

Diferentemente da entropia molecular, a entropia de Shannon pode ser localmente reduzida sem inserir energia no sistema de informação. Simplesmente passar um canal através de um filtro passivo pode reduzir a entropia da informação transmitida (sem que o transmissor saiba, a capacidade do canal é reduzida e, portanto, também a entropia da informação no canal). A quantidade de potência necessária para transmitir é a mesma, independentemente de o filtro estar ou não instalado, e independentemente de a entropia da informação ser reduzida ou não. Outra maneira de pensar sobre isso é cortar um fio de um canal que possui múltiplos fios paralelos. A informação média que atravessa o canal, a entropia, diminui, sem relação com a quantidade de energia necessária para cortar o fio. Ou desligue a fonte de alimentação de uma fonte de informação e observe sua saída fixar-se em um único símbolo "off" com probabilidade 1 e entropia de informação 0.

Uma palavra de cautela sobre a notação: para aqueles familiarizados com a termodinâmica química, H na Teoria da Informação Clássica não é entalpia, e os dois assuntos não devem ser confundidos. Da mesma forma, o H na Teoria da Informação Clássica mede uma propriedade diferente do H na Teoria da Informação Algorítmica. Embora esses conflitos de notação possam ser lamentáveis, toda a literatura está escrita dessa forma e qualquer pessoa que queira entender a Teoria da Informação simplesmente terá que se acostumar com isso.

[Topo]