Correção de erros
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
A
e
B ),
e vamos supor que ela envia uma mensagem para ele.
Para simplicar 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 car 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 lme, 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, caria frustrado e com
ciúmes dela, além, é claro, de se embebedar. Ela, esperando por ele, começaria
a car preocupada e decidiria ir até sua casa para ver se está tudo bem. Imagine
a cena do encontro!
Para matematizar o problema, vamos codicar as possíveis mensagens. A
Alice pode ou não sair, o que pode ser representado por apenas um bit:
caso armativo, e
0, no caso negativo.
1,
no
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:
1,
no caso armativo, e
0,
no caso negativo.
Uma mensagem completa possui, portanto, dois bits e há um universo de quatro
possibilidades:
00, 01, 10
e
11.
Em uma tabela, que o Bob deve estar sempre
carregando com ele, temos a codicação representada assim:
1
Mensagem
Código
Não vou sair, não quero sua companhia.
00
01
10
11
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.
exemplo, se a palavra
11,
Por
durante a transmissão pelo canal, sofrer um erro no
segundo bit, então o Bob receberá a palavra
10,
que é outra palavra, ou men-
sagem, do código; não há como ele saber que houve um erro de transmissão e,
com isso, congurar-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 codicaçã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
255
(GSM) ou
160
(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 sucientemente 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 codicar palavras de dois bits usando palavras de três bits?
Note que as palavras
a segunda,
1's.
2.
00
e
Já as palavras
11 têm um número par de 1's: a primeira tem 0 e
01 e 10 têm um só 1, isto é, um número ímpar de
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.
quando a palavra original, de dois bits, for par, como
primeiro bit par, isto é,
000
e
011,
0,
00
e
11,
Assim,
utilizaremos o
nas palavras de três bits correspondentes, ou seja,
respectivamente. Já as palavras ímpares,
palavras de três bits cujo primeiro bit é
1,
101
isto é,
01 e 10, corresponderão a
110, respectivamente. A
e
tabela correspondente às mensagens agora ca assim:
Palavra de dois bits
Palavra de três bits
00
01
10
11
000
101
110
011
.
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
011.
Se ocorrer o erro do exemplo, ou seja,
se o terceiro bit for trocado durante a transmissão, o Bob receberá a palavra
010.
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
2
de, no máximo, um erro, sem permitir correção. Não dá, com esse código, para
011, sofrer um
110, que está no
detectar dois ou três erros. Por exemplo, se a palavra enviada,
erro no primeiro e no terceiro bits, o Bob receberá a palavra
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 cando, 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 codicamos palavras de dois bits usando
palavras de três bits, dizemos que esse é um código
dizemos que temos um código
ando palavras de
código
n
[n, k]
[3, 2] .
De maneira geral,
quando codicamos palavras de
bits, sempre com
n > k.
k
bits, us-
Então, como podemos obter um
[4, 2]?
Uma maneira possível de obter redundância é repetir os bits. Assim, podemos codicar 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 codicada
00
01
10
11
0000
0011
1100
1111
.
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
1100
e ocorrer apenas um erro,
1000 e ele detectará
1000 não pertence ao código, mas não saberá se a palavra correta
0000, mesmo que tenha certeza que apenas um erro tenha ocorrido.
digamos, no segundo bit, então o Bob receberá a palavra
um erro, pois
é
1100,
ou
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 codicação mais ecaz,
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 trans-
formaçã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
00
como
3
0
0
,
01
0
1
1
0
1
1
como
10
como
,
e
11
como
.
Note que as componentes desses vetores são sempre
0 ou 1, já que os signicados
desses números são não e sim, respectivamente; não haveria como interpretar
uma componente igual a
2
em um desses vetores represntando palavras. Com
esse tipo de notação, podemos ver que a tabela acima com um particular código
[4, 2]
é uma transformação representada por uma matriz
4 × 2,
matriz geratriz, dada por

G =
1
 1

 0
0

0
0 
.
1 
1
Veja só como é verdade:

G
0
0
que representa a palavra
1
 1
= 
 0
0
G
que representa


0 0
 0
0 
0

=
 1
1  1
1
1



0 1
 1
0 
1

=
 0
1  0
1
0



0 1
 1
0 
1

=
 1
1  1
1
1


,

0
1
1
0
1
1
1
 1
= 
 0
0

,

0011

G
representando

0000,



0
0  0
0 
0

=
 0
1  0
0
1
1100,
1
 1
= 
 0
0

,

e

G
1
 1
= 
 0
0
4

,

chamada de
1111. Vemos que a matriz G gera a codicação da tabela
[4, 2] , basta trocarmos os
elementos da matriz G. Mas agora temos um probleminha: vamos supor que
queiramos modicar somente a primeira linha da matriz G e escrever


1 1
 1 0 

G1 = 
 0 1 .
0 1
que equivale à palavra
acima.
Logo, para obter outros códigos, do tipo
Veja o que acontece se aplicamos a transformação

1
1
G1
Se somarmos
1
com
1

1
 1
= 
 0
0
e obtivermos
G1

na palavra
11 :

1 1+1
 1 
0 
1


=
 1 .
1  1
1
1
2,
sentar uma palavra, já que o número
obteremos um vetor que não pode repre-
2
não signica sim, nem não. Temos
que eliminar a possibilidade de outros números aparecerem, que não sejam apenas
0
e
1.
2. Para as componentes
2, que é assim:
A saída para isso é usar somas módulo
palavras, vamos sempre usar a aritmética módulo
0+0
=
0,
0+1
=
1,
1+0
=
1
1+1
=
0.
de
e
Agora estamos equipados para modicar a matriz geratriz e gerar outros códigos
[4, 2] .
No exemplo acima, portanto, obtemos

G1
1
1
1
 1
= 
 0
0


0
1  1
0 
1

=
 1
1  1
1
1


.

Veja uma coisa interessante sobre uma matriz geratriz com as duas colunas
iguais:

G2
1
1
=


1 0
 0
0 
1

=
 0
1  1
1
0
1
 0

 1
1
5




e

G2
0
0
1
 0
= 
 1
1


0
1  0
0 
0

=
 0
1  0
0
1


,

isto é, a matriz

G2
1
 0
= 
 1
1

1
0 

1 
1
transforma duas palavras de dois bits diferentes em duas palavras de quatro bits
iguais!
Isso causa muita confusão, pois não dá para decodicar uma palavra
dessas, já que nunca saberemos se
0000 quer dizer 11 ou 00. 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
2
das duas colunas originais não altera o código. Por
exemplo, tomemos a matriz
G
e troquemos sua primeira coluna pela soma de
G3 ,

1
  1
=
  1
1
suas colunas originais, obtendo a nova geratriz

G3
1+0
 1+0
= 
 0+1
0+1
0
0
0
1
1
0
1
1
0
0
1
1

dada por

0
0 
.
1 
1
Com isso, obtemos

G3
1
 1

= 
1
1

G3
1
 1
= 
 1
1

G3
1
 1
= 
 1
1


0 0

0 
 0 = 0
 0
1  0
1
0



0
0  0
0 
0

=
 1
1  1
1
1



0 1
 1
0 
1

=
 1
1  0
1
1



0 1
 1
0 
1

=
 0
1  1
1
0


,


,


,

e

G3
1
 1
= 
 1
1
6

,

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
0000, 0011, 1100
1111
e
G3 .
[4, 2] , pode-
continuam sendo geradas pela geratriz
Com as propriedades que aprendemos sobre geratrizes de códigos
mos 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
0
componentes
módulo
2
e
1
e utilizando aritmética módulo
2.
Note também que a soma
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 denir 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
2
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
2,
pois só há multiplicações entre os números do conjunto
essa denição, é fácil ver que a palavra
1100,
{0, 1} .
Com
por exemplo, é ortogonal a ela
mesma, já que o produto escalar de seu vetor coluna por ele mesmo é nulo.
Agora sabemos gerar códigos
uma matriz geratriz
n×k
[n, k] quaisquer, já que só precisamos construir
k colunas linear-
e tomar o cuidado para escolher
mente independentes, isto é, nenhuma dessas colunas pode ser igual à soma de
qualquer número das outras
k−2
colunas, onde, entre as colunas, não estamos
considerando o vetor nulo (por isso escrevi k − 2 outras colunas e não k − 1.)
Com esse formalismo, agora queremos descobrir uma maneira de testar se uma
determinada palavra pertence ou não a um dado código
C.
É evidente que uma
palavra do código não pode ter componente alguma em um subespaço ortogonal
C, que é
C e denotado por C ⊥ . Seja C o código original das
quatro palavras, 0000, 0011, 1100 e 1111. Vamos agora considerar o conjunto
de todas as palavras de quatro bits simultaneamente ortogonais (módulo 2) às
quatro palavras de C. Então, queremos encontrar todos os vetores coluna do
àquele de
C.
Então, vamos gerar um subespaço ortogonal ao do código
chamado de código dual de
tipo


a1
 a2 


 a3  ,
a4
com
a1 , a2 , a3
e
a4
pertencentes ao conjunto
t 
a1
0
 a2   0

 
 a3   1
a4
1

7
{0, 1} ,




=
0,
tais que
t 
1
a1
 a2   1

 
 a3   0
0
a4

t 
a1
1
 a2   1

 
 a3   1
a4
1





=
0
=
0,
e

onde o sobrescrito
qualquer.
t



signica que estamos tomando a transposta de uma matriz
a1 , a2 , a3
Então, devemos encontrar
e
a4
simultaneamente satis-
fazendo
a3 + a4
=
0
a1 + a2
=
0.
e
Com essas duas equações satisfeitas, também teremos a equação
a1 + a2 + a3 + a4
=
automaticamente satisfeita. Em aritmética módulo
a3
=
a3
= a4 = 1,
a1
=
a1
= a2 = 1.
0
2, podemos ter, como solução,
a4 = 0
ou
além de também ter
a2 = 0
ou
As palavras formadas com essas possíveis soluções para suas componentes cam:
0000, 0011, 1100 e 1111, isto é, obtemos o mesmo código C como sendo ortogonal
C ⊥ = C. Como esses dois
códigos são o mesmo, têm a mesma geratriz G. Como as colunas de G geram o
subespaço ortogonal a C, que no presente caso é o próprio C, essas colunas são
ortogonais a todas as palavras de C. Logo, para testar se uma dada palavra é
do código, basta calcularmos o produto da transposta de G pelo vetor coluna
a si próprio e, portanto, é dito auto-dual, ou seja,
representando a palavra em questão; se o resultado não for nulo, segue que a
8
palavra não está no código e, portanto, um erro é detectado. Por exemplo, caso
o Bob receba a palavra
1000, ele pode ver que essa palavra não é do código pelo
produto matricial seguinte:


1
 0 

Gt 
 0  =
0

1
0
1
0
0
1
0
1

1
 0 

= 1 ,
 0 
0
0
que é diferente do vetor nulo de duas dimensões.
No caso de um código geral, do tipo
[n, k] ,
a matriz transposta da geratriz
do código dual é chamada de matriz de vericação de paridade e, normalmente,
é denotada por
H. 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 suciente para deixar comentários.
aguardando!
9
Estarei