Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Provavelmente você já enfrentou problemas com erros de comunicação. É muito comum não entender alguma coisa que você ouve alguém dizer. Quantas vezes você já teve que repetir algo que acabou de falar? Há erros na comunicação sempre que a mensagem que você intenciona enviar acaba chegando com erros ao seu destino. Existem também erros que você comete na hora de enviar e na hora de receber e interpretar uma mensagem. O meio através do qual uma mensagem caminha é tipicamente chamado de canal de comunicação ou, simplesmente, canal. Quando acontecem erros aleatórios durante a transmissão de uma mensagem, dizemos que o canal é ruidoso. Supondo que o envio e a recepção de uma mensagem sejam sempre exatos, sem ocorrência alguma de erros, como corrigir os erros que ocorrem durante a transmissão através de um canal ruidoso?

Para começar a responder essa questão, vamos considerar um casal, Alice e Bob (ao invés de e ), e vamos supor que ela envia uma mensagem para ele. Para simplificar e tornar a discussão mais divertida, suponhamos que a Alice precisa dizer se vai ou não sair hoje e se quer ou não a companhia do Bob. Para ele, entender a mensagem sem ambiguidade é muito importante, pois, caso ela vá sair e queira sua companhia, ele terá que tomar um banho e se arrumar, talvez até fazer a barba, e ir apanhá-la (já que é um cavalheiro). Agora, caso ela não vá sair, mas queira a companhia dele, também é aconselhável que ele se apresente bem arrumadinho e cheiroso na casa dela. No entanto, caso ela não queira sua companhia, o Bob pode ficar barbudo e à vontade, cheirando mal, em sua casa. Nessas circunstâncias, ele pode, além de tudo, encher a cara, caso a Alice vá sair, ou pode tranquilizar-se e assistir a um filme, caso não vá sair, imaginando que talvez ela esteja apenas com dor de cabeça. Você pode imaginar o que aconteceria se ele recebesse uma mensagem errada? Por exemplo, se ela enviasse a mensagem, “Vou sair, quero sua companhia”, e ele entendesse, “Vou sair, não quero sua companhia”, quais poderiam ser as consequências? Bem, primeiro, ele não tomaria banho, não faria a barba, ficaria frustrado e com ciúmes dela, além, é claro, de se embebedar. Ela, esperando por ele, começaria a ficar preocupada e decidiria ir até sua casa para ver se está tudo bem. Imagine a cena do encontro!

Para matematizar o problema, vamos codificar as possíveis mensagens. A Alice pode ou não sair, o que pode ser representado por apenas um bit: no caso afirmativo, e no caso negativo. Além disso, ela pode, independentemente de sair ou não, querer ou não a companhia do Bob, o que também pode ser representando por apenas um bit: no caso afirmativo, e no caso negativo. Uma mensagem completa possui, portanto, dois bits e há um universo de quatro possibilidades: e Em uma tabela, que o Bob deve estar sempre carregando com ele, temos a codificação representada assim:

Mensagem	Código
“Não vou sair, não quero sua companhia.”
“Não vou sair, quero sua companhia.”
“Vou sair, não quero sua companhia.”
“Vou sair, quero sua companhia.”

 

Note que se o canal é ruidoso, sempre que um só bit for trocado, uma mensagem, ou palavra, do código torna-se outra palavra do mesmo código. Por exemplo, se a palavra durante a transmissão pelo canal, sofrer um erro no segundo bit, então o Bob receberá a palavra que é outra palavra, ou mensagem, do código; não há como ele saber que houve um erro de transmissão e, com isso, configurar-se-á a situação embaraçosa do exemplo acima. Se dois bits forem trocados durante a transmissão, novamente não há como o Bob saber que houve erros no canal.

A solução está em usar redundância na codificação de mensagens. Isso pode acabar custando mais caro. Veja você que a transmissão de mensagens tem um custo; basta você enviar um torpedo (SMS) pelo celular que a operadora cobrará uma tarifa. Se o número de caracteres passar de (GSM) ou (CDMA), você pagará mais do que uma só tarifa. Então, no mundo hipotético de Alice e Bob, vamos supor que ela não quer usar muitos bits redundantes, pois quer manter seus custos com mensagens curtas suficientemente baixos. No entanto, como vimos, com dois bits apenas não dá para o Bob saber se houve ou não um erro de transmissão. Para economizar, vamos ver o que dá para fazer com três bits. Como codificar palavras de dois bits usando palavras de três bits?

Note que as palavras e têm um número par de ‘s: a primeira tem e a segunda, Já as palavras e têm um só isto é, um número ímpar de ‘s. Vamos, então, introduzir um bit a mais para indicar a paridade da palavra e vamos posicioná-lo como o primeiro bit de palavras com três bits. Assim, quando a palavra original, de dois bits, for par, como e utilizaremos o primeiro bit par, isto é, nas palavras de três bits correspondentes, ou seja, e respectivamente. Já as palavras ímpares, e corresponderão a palavras de três bits cujo primeiro bit é isto é, e respectivamente. A tabela correspondente às mensagens agora fica assim:

Palavra de dois bits	Palavra de três bits

.

Usando essa tabela, dá para o Bob determinar se a mensagem que recebe está correta ou errada? Vejamos um exemplo: suponha que a Alice manda a mensagem do exemplo acima, usando três bits, de acordo com o código da tabela acima, isto é, ela envia a palavra Se ocorrer o erro do exemplo, ou seja, se o terceiro bit for trocado durante a transmissão, o Bob receberá a palavra Veja que essa palavra não corresponde ao código exposto na tabela acima! Nesse caso o Bob saberá que houve algum erro no canal. Note, porém, que ele não saberá qual bit está errado. Dizemos que o código acima permite a detecção de, no máximo, um erro, sem permitir correção. Não dá, com esse código, para detectar dois ou três erros. Por exemplo, se a palavra enviada, sofrer um erro no primeiro e no terceiro bits, o Bob receberá a palavra que está no código e, assim, ele vai se colocar em uma situação complicada novamente. O que normalmente acontece é que um canal pode ser ruidoso com a probabilidade de ocorrer um erro maior do que a probabilidade de dois erros. Então, o Bob pode, até um certo ponto, apostar que uma determinada mensagem esteja correta, já que está no código, sempre ficando, porém, com a pulga atrás da orelha… Talvez fosse interessante ver o que é possível fazer com mais um bit de redundância. Mas antes, deixe-me apresentar a nomenclatura que usaremos para códigos. Como na tabela acima codificamos palavras de dois bits usando palavras de três bits, dizemos que esse é um código De maneira geral, dizemos que temos um código quando codificamos palavras de bits, usando palavras de bits, sempre com Então, como podemos obter um código

Uma maneira possível de obter redundância é repetir os bits. Assim, podemos codificar as palavras originais, de dois bits, em palavras de quatro bits tais que os dois primeiros bits sejam iguais ao primeiro bit da palavra original e os dois últimos bits sejam iguais ao segundo bit da palavra original. Usando uma tabela, temos

Palavra original	Palavra codificada

.

Será que o Bob pode usar essa redundância de dois bits extras para detectar e corrigir erros? Infelizmente, usando esse código ele só consegue detectar, com certeza, apenas um erro no máximo e não consegue corrigir, com certeza, erro algum. Por exemplo, se a palavra enviada for e ocorrer apenas um erro, digamos, no segundo bit, então o Bob receberá a palavra e ele detectará um erro, pois não pertence ao código, mas não saberá se a palavra correta é ou mesmo que tenha certeza que apenas um erro tenha ocorrido. Se ocorrerem dois erros, de novo a palavra voltará a ser igual a uma outra da tabela e o Bob não detectará erro algum. A tabela acima representa apenas um possível código com quatro bits. Não há uma outra codificação mais eficaz, permitindo detectar mais erros e talvez até corrigi-los?

Para procurar por códigos possíveis, é interessante formular matematicamente o problema. Veja que o código acima nada mais é do que uma transformação de palavras de dois bits em palavras de quatro bits. Para tratar transformações desse tipo, podemos tentar pensar em vetorizar as palavras, isto é, podemos tentar a representação de cada palavra por um vetor coluna. Assim, por exemplo, podemos escrever

e

Note que as componentes desses vetores são sempre ou já que os significados desses números são “não” e “sim”, respectivamente; não haveria como interpretar uma componente igual a em um desses vetores represntando palavras. Com esse tipo de notação, podemos ver que a tabela acima com um particular código é uma transformação representada por uma matriz chamada de matriz geratriz, dada por

Veja só como é verdade:

que representa a palavra

que representa

representando e

que equivale à palavra Vemos que a matriz gera a codificação da tabela acima. Logo, para obter outros códigos, do tipo basta trocarmos os elementos da matriz Mas agora temos um probleminha: vamos supor que queiramos modificar somente a primeira linha da matriz e escrever

Veja o que acontece se aplicamos a transformação na palavra

Se somarmos com e obtivermos obteremos um vetor que não pode representar uma palavra, já que o número não significa “sim”, nem “não”. Temos que eliminar a possibilidade de outros números aparecerem, que não sejam apenas e A saída para isso é usar somas módulo Para as componentes de palavras, vamos sempre usar a aritmética módulo que é assim:

e

Agora estamos equipados para modificar a matriz geratriz e gerar outros códigos No exemplo acima, portanto, obtemos

Veja uma coisa interessante sobre uma matriz geratriz com as duas colunas iguais:

e

isto é, a matriz

transforma duas palavras de dois bits diferentes em duas palavras de quatro bits iguais! Isso causa muita confusão, pois não dá para decodificar uma palavra dessas, já que nunca saberemos se quer dizer ou Logo, não podemos ter duas colunas iguais para nossas geratrizes.

Outra propriedade interessante de geratrizes é que trocar uma de suas colunas pela soma módulo das duas colunas originais não altera o código. Por exemplo, tomemos a matriz e troquemos sua primeira coluna pela soma de suas colunas originais, obtendo a nova geratriz dada por

Com isso, obtemos

e

que, embora tenha alterado a regra de correspondência biunívoca entre as palavras, não muda as palavras do código de quatro bits, isto é, as mesmas palavras e continuam sendo geradas pela geratriz

Com as propriedades que aprendemos sobre geratrizes de códigos podemos dizer que essas matrizes, para serem úteis, devem ter duas colunas que sejam linearmente independentes, isto é, uma não pode ser igual à outra, nesse tipo particular de código. Então, essas duas colunas servem como uma base para um subespaço de duas dimensões de um espaço vetorial de quatro dimensões. Note que esses espaços vetoriais são espaços de vetores coluna construídos apenas com componentes e e utilizando aritmética módulo Note também que a soma módulo de dois vetores coluna quaisquer do código resulta em outro vetor do código, ilustrando que o conjunto é mesmo um subespaço vetorial.

Vamos definir o produto escalar entre dois vetores de um mesmo espaço vetorial de palavras de código de forma análoga à usual, em que tomamos a soma módulo dos produtos das componentes dos vetores. O produto entre duas componentes é como o usual, não havendo mudança no caso de aritmética módulo pois só há multiplicações entre os números do conjunto Com essa definição, é fácil ver que a palavra por exemplo, é ortogonal a ela mesma, já que o produto escalar de seu vetor coluna por ele mesmo é nulo.

Agora sabemos gerar códigos quaisquer, já que só precisamos construir uma matriz geratriz e tomar o cuidado para escolher colunas linearmente independentes, isto é, nenhuma dessas colunas pode ser igual à soma de qualquer número das outras colunas, onde, entre as colunas, não estamos considerando o vetor nulo (por isso escrevi “ outras colunas” e não “”.) Com esse formalismo, agora queremos descobrir uma maneira de testar se uma determinada palavra pertence ou não a um dado código É evidente que uma palavra do código não pode ter componente alguma em um subespaço ortogonal àquele de Então, vamos gerar um subespaço ortogonal ao do código que é chamado de código dual de e denotado por Seja o código original das quatro palavras, e Vamos agora considerar o conjunto de todas as palavras de quatro bits simultaneamente ortogonais (módulo ) às quatro palavras de Então, queremos encontrar todos os vetores coluna do tipo

com e pertencentes ao conjunto tais que

e

onde o sobrescrito significa que estamos tomando a transposta de uma matriz qualquer. Então, devemos encontrar e simultaneamente satisfazendo

e

Com essas duas equações satisfeitas, também teremos a equação

automaticamente satisfeita. Em aritmética módulo podemos ter, como solução,

ou

além de também ter

ou

As palavras formadas com essas possíveis soluções para suas componentes ficam: e isto é, obtemos o mesmo código como sendo ortogonal a si próprio e, portanto, é dito auto-dual, ou seja, Como esses dois códigos são o mesmo, têm a mesma geratriz Como as colunas de geram o subespaço ortogonal a que no presente caso é o próprio essas colunas são ortogonais a todas as palavras de Logo, para testar se uma dada palavra é do código, basta calcularmos o produto da transposta de pelo vetor coluna representando a palavra em questão; se o resultado não for nulo, segue que a palavra não está no código e, portanto, um erro é detectado. Por exemplo, caso o Bob receba a palavra ele pode ver que essa palavra não é do código pelo produto matricial seguinte:

que é diferente do vetor nulo de duas dimensões.

No caso de um código geral, do tipo a matriz transposta da geratriz do código dual é chamada de matriz de verificação de paridade e, normalmente, é denotada por Creio que esta postagem está comprida o bastante para fazer uma pausa. Minha intenção é continuar a desenvolver este assunto apenas se você realmente tiver curiosidade suficiente para deixar comentários. Estarei aguardando!

Música desta postagem: January (At the Fireside) de Pyotr Ilich Tchaikovsky, por Alfonso Bertazzi

Recomendo também a leitura da postagem a seguir:

• Potências em Base Decimal, Base Binária e o byte

Uma versão em PDF

Gostou desta postagem? Então clique no botão abaixo e siga o Nerdyard no Twitter! Toda vez que houver uma nova postagem aqui, você saberá imediatamente!

Melhor ainda: inscreva-se em Nerdyard e receba, por e-mail, o aviso com links para cada nova postagem ou novidade.

Inscreva-se em Nerdyard

Melhor email:

Visite este grupo

NOTE QUE EU ODEIO SPAM COM TODA CONVICÇÃO!

Dessa forma, não se preocupe: eu juro que jamais fornecerei seu endereço de e-mail ou qualquer outra informação sobre você para ninguém!

Acesse o Wiki de Nerdyard