Aula 25 - Álgebra II

Aplicações: Teoria Algébrica dos Códigos Consideremos o seguinte código binário, a que chamaremos C_{1}, que permite dar as instruções de comando a um leitor de DVD, através de um comando à distância:

                      PLAY  REW  FORWARD  STOP 00 01  10  11

Suponhamos que carregamos na tecla PLAY do comando, a que corresponde a palavra 00 do código; o comando transmite esta palavra ao leitor de DVD mas se, porventura, nessa comunicação ocorrer o erro

00  10 −−→^{erro}

o leitor receberá a palavra 10, e como esta faz parte de C_{1} (corresponde à instrução FORWARD), aquele não terá nenhuma maneira de detectar o erro e executará a instrução FORWARD!

O código C_{1} é um exemplo de código binário, ou seja, um código definido sobre o alfabeto (corpo) 𝔽_{2}, constituído por todas as palavras de comprimento 2 nesse alfabeto. Trata-se de um código muito pobre, pois nem sequer detecta erros simples (singulares) como o do exemplo acima.

O que fazemos habitualmente quando não entendemos o que outra pessoa nos quer dizer? Pedimos que repita a mensagem. Façamos isso no código C_{1}, isto é, pensemos no código C_{2} que se obtem de C_{1} repetindo a informação em cada palavra uma vez:

                     PLAY  REW  FORWARD  STOP 0000 0101 1010 1111

Agora, ao ser transmitida a instrução PLAY (ou seja, a palavra 0000), se ocorrer o mesmo erro singular de há pouco,

0000  1000 −−→^{erro}

como a palavra recebida não faz parte de C_{2}, o leitor de DVD pode concluir imediatamente que ocorreu algum erro na transmissão. Neste caso, o código C_{2} já detecta este erro singular (e é fácil de ver que detecta qualquer outro erro singular). Terá maneira de corrigir esse erro, isto é, de identificar a palavra original (assumindo que na transmissão só poderão ocorrer, quando muito, erros singulares)? Não; de facto, há duas palavras em C_{2} que poderiam ser as originais:

[figure: 1010; 0000; 1000; erro singular; erro singular; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Consideremos, finalmente, o código C_{3}, definido pela tabela

PLAY REW FORWARD STOP 000000 010101 101010 111111

Agora, além de qualquer erro singular ser detectável, também pode ser corrigido automaticamente (assumindo novamente que na transmissão só poderão ocorrer, quando muito, erros singulares). Por exemplo, o erro singular

000000  100000 −−→^{erro}

é evidentemente detectado e corrigido; a única palavra de C_{3} que poderia ter dado origem à palavra 100000, na assumpção que só ocorreram erros singulares, é a palavra 000000:

Palavra de C_{3} 000000 010101 101010 111111
Palavra recebida 100000 100000 100000 100000
Número de erros  1  4  2  5

É claro que se puderem ocorrer erros duplos no canal de comunicação, C_{3} já não corrige o erro singular acima: a palavra original poderia muito bem ser a palavra 101010.

Assim, esta ideia de construir códigos correctores de erros só funciona se conhecermos a priori um limite para o número de erros que pode ocorrer no respectivo canal de comunicação. Ou, então, se adoptarmos o seguinte princípio de bom senso (o chamado princípio do vizinho mais próximo):

A palavra original correspondente a uma palavra recebida com erros deve ser a palavra do código “mais próxima” da palavra recebida

(isto é, assumimos que é mais provável que o menor número de erros possível tenha ocorrido na transmissão).

Daqui em diante, assumimos sempre este princípio. (mais adiante, tornaremos precisa a noção de proximidade implícita no termo “mais próxima”.)

Os códigos C_{1}, C_{2} e C_{3} são exemplos do tipo de códigos que vamos estudar, e que podem ser formalizados do seguinte modo:

CÓDIGOS SOBRE UM CORPO FINITO 𝔽_{q}. CÓDIGOS LINEARES Um código de comprimento n sobre o corpo 𝔽_{q} é um subconjunto C de (𝔽_{q})^{n}. Portanto, C é formado por palavras de comprimento n, a_{1}a_{2} … a_{n}, formadas com o alfabeto 𝔽_{q} (isto é, cada a_{i} ∈ 𝔽_{q}). Note que 𝔽_{q}^{n} é um espaço vectorial sobre 𝔽_{q}, de dimensão n. Assim, as palavras de C são simplesmente vectores deste espaço. Quando C é um subespaço linear de 𝔽_{q}^{n}, de dimensão k, diz-se que C é um código linear ou (n, k)-código sobre 𝔽_{q}.

Exemplos: C_{1} = 𝔽_{2}^{2}, pelo que C_{1} é um (2, 2)-código sobre 𝔽_{2}. Os códigos C_{2} e C_{3} também são códigos lineares sobre 𝔽_{2} (binários), como é fácil de ver: C_{2} é um (4, 2)-código enquanto C_{3} é um (6, 2)-código.

Os (n, k)-códigos sobre o corpo 𝔽_{2} foram o tipo de códigos utilizados pelas sondas que viajaram até Marte, na transmissão das fotografias para a Terra. No caso dos CDs de música, utiliza-se o corpo 𝔽_{256} = 𝔽_{2^{8}}.

Precisemos agora a noção de distância entre duas palavras de 𝔽_{q}^{n}.

DISTÂNCIA DE HAMMING A distância de Hamming entre duas palavras a⃗ = a_{1}a_{2} … a_{n} e b⃗ = b_{1}b_{2} … b_{n} é o número de índices i ∈ {1, 2, …, n} tais que a_{i} ≠ b_{i}. Note que d(a⃗, b⃗) indica o número de erros ocorridos se a⃗ é a palavra transmitida e b⃗ é a palavra recebida.

Por exemplo, d(1101, 0111) = 2. É muito fácil de ver que a distância de Hamming é uma métrica em 𝔽_{q}^{n}, isto é, para quaisquer a⃗, b⃗, c⃗ ∈ 𝔽_{q}^{n}, tem-se:

(1) d(a⃗, b⃗) ≥ 0; d(a⃗, b⃗) = 0 se e só se a⃗ = b⃗.

(2) d(a⃗, b⃗) = d(b⃗, a⃗).

(3) d(a⃗, b⃗) ≤ d(a⃗, c⃗) + d(c⃗, b⃗).

DISTÂNCIA MÍNIMA Chama-se distância mínima de um código C, que se denota por δ(C), ao número

min_{a⃗,b⃗∈C,a⃗≠b⃗} d(a⃗, b⃗).

Este número mede o grau de vizinhança das palavras em C. Por exemplo, δ(C_{1}) = 1, δ(C_{2}) = 2 e δ(C_{3}) = 3.

Quanto maior é o valor de δ(C), mais eficiente é o código. Portanto, um dos objectivos na construção de um código é que tenha as palavras o mais afastadas entre si. Por outro lado, isto limita o número de palavras do código, logo limita a sua capacidade de armazenar e transmitir informação. Reconciliar estes dois objectivos (isto é, procurar o ponto de equilíbrio entre eles) é um dos problemas da teoria dos códigos.

CÓDIGOS t-DETECTORES E t-CORRECTORES DE ERROS Seja t ∈ ℕ. Diz-se que um código C é t-detector de erros se detecta qualquer combinação de t erros em qualquer palavra. Diz-se que C é t-corrector de erros se corrige qualquer combinação de t erros em qualquer palavra.

Teorema. Seja C um código com distância mínima δ(C).

(a) Se t ≤ δ(C) − 1, então C é t-detector de erros.

(b) Se t ≤ \frac{δ(C)−1}{2}, então C é t-corrector de erros.

Demonstração. (a) Suponhamos que na transmissão de uma palavra a⃗ ∈ C ocorreram t erros, resultando na palavra recebida b⃗:

a⃗  b⃗ −−→^{t}_{erros}

(portanto, d(a⃗, b⃗) = t). Para provarmos que o código terá a capacidade de detectar o erro, teremos que garantir que b⃗ ∉ C, o que é fácil: como d(a⃗, b⃗) = t < δ(C) e a⃗ ∈ C então b⃗ ∉ C.

(b) Suponhamos que na transmissão de uma palavra a⃗ ∈ C ocorreram t erros, resultando na palavra recebida b⃗ (portanto, d(a⃗, b⃗) = t). Agora, para provarmos que o código terá a capacidade de corrigir o erro, bastará garantir que mais nenhuma palavra em C além de a⃗ pode ter dado origem à palavra errada b⃗, ou seja, que qualquer outra palavra c⃗ ∈ C está a uma distância de b⃗ maior do que t, o que também é fácil: pela desigualdade triangular da distância,

d(b⃗, c⃗) ≥ d(a⃗, c⃗) − d(a⃗, b⃗) ≥ δ(C) − t ≥ 2t + 1 − t = t + 1.

Portanto, um código consegue detectar t erros se quaisquer duas palavras do código estiverem a uma distância de Hamming pelo menos t + 1:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; t; a⃗; b⃗]

Por sua vez, um código consegue corrigir t erros se quaisquer duas palavras do código estiverem a uma distância de Hamming pelo menos 2t + 1:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; t; t; a⃗; b⃗]

Nos exemplos que vimos anteriormente, tem-se:

Código δ(C) No. erros que detecta No. erros que corrige
C_{1}  1  0  0
C_{2}  2  1  0
C_{3}  3  2  1

Portanto C_{2} é 1-detector de erros e C_{3} é 1-corrector de erros e 2-detector de erros.

A definição de código t-corrector implica que quaisquer bolas de raio t, centradas em palavras distintas, sejam disjuntas. Se, além disso, estas bolas cobrirem a totalidade do espaço (uma propriedade rara mas interessante), o código diz-se perfeito. Assim, um código t-corrector C sobre 𝔽_{q} diz-se perfeito se

⋃_{a⃗∈C} B(a⃗, t) = 𝔽_{q}^{n}.