Sejam duas sentenças pertencentes a uma dada linguagem. Admitimos que a sua concatenação também pertencerá a esta linguagem (por exemplo: “Hoje o dia está desagradável” e “Você já viu aquele filme” são duas sentenças do português. Sua concatenação, “Hoje o dia está desagradável. Você já viu aquele filme?” também será, num sentido lato, uma “sentença” do português. O “ponto” entre as duas sentenças originais é o operador da concatenação) . A estrutura de um sistema concatenável é a seguinte: se a e b pertencem a L então ab também pertencerá a L. Estruturas deste tipo são chamadas monóides. Um processo de codificação é, rigorosamente, uma aplicação biunívoca de um monóide sobre outro. Que quer dizer isso? Para nossa finalidade de compreender um processo de codificação, consideraremos que toda linguagem tem a estrutura de um monóide. Num processo simplificado de codificação, substituímos as letras do alfabeto por sinais especiais. Então, a cada sinal corresponde uma letra, e apenas uma. Quando eu codificar um texto, obterei uma única versão codificada (não posso codificar de duas maneiras diferentes o mesmo texto), e quando alguém traduzir a versão codificada, obterá de volta e texto inicial. Diz-se unívoco todo processo que, a partir de um objeto inicial, obtém um único objeto transformado. Quando há univocidade nos dois sentidos, diz-se que o processo é biunívoco. O diagrama esclarece.
mensagem original → codificação (unívoca) → mensagem cifrada
mensagem original ← decodificação (unívoca) ← mensagem cifrada
É evidente que, como desejamos que nossa mensagem, descodificada, se mantenha intacta, o nosso processo de codificação devera ser biunívoco.
Suponhamos agora que à transmissão de cada mensagem associamos um certo custo. Nosso interesse estaria em reduzir este custo. A mensagem é uma sequência de letras num certo alfabeto e cada mensagem tem a si associada uma probabilidade de ser transmitida. Uma medida do “custo” seria, por exemplo, o número de letras numa dada mensagem (uma mensagem mais longa custaria mais que uma curta porque levaria mais tempo a ser transmitida). O custo médio de todas as mensagens seria a média ponderada dos custos individuais, sendo o fator de ponderação a probabilidade de transmissão de cada uma das mensagens. A pergunta espontânea neste ponto é: haverá alguma codificação que reduza o custo médio de transmissão de um dado conjunto de mensagens? A resposta é afirmativa.
Pode-se também mostrar que, em certas circunstâncias, há um método de codificação mais eficiente que todos os outros possíveis. “Eficiência” será (formalmente) definida como o quociente entre o comprimento médio das mensagens transmitidas no processo de codificação de menor custo possível, e o comprimento médio das mensagens em qualquer outro processo de codificação. A redundância associada a um dado código é igual a 1 menos a eficiência correspondente. Quando a eficiência for de 100%, a redundância é nula. Para uma discussão completa ainda é melhor o artigo original sobre teoria da comunicação. (Francisco Doria – DCC)