Ir ao conteúdo principal

Seção 8.1 Códigos para Detectar e para Corrigir Erros

Consideremos um modelo simples de sistema de comunicações para o envio e recepção de mensagens codificadas (ver Figura 8.1.1).

\begin{tikzpicture}[scale=1] \draw [->] (0,8) node [above] {\emph{mensaje de $m$ dígitos}} -- (0,7.5); \node at (0,7) {Codificador}; \draw (-1.5,6.5) rectangle (1.5,7.5); \draw (0,6.5) -- (0,6.25); \draw [->] (0,5.75) -- (0,5.5); \node at (0,6) {\emph{palavra de $n$ dígitos no código}}; \node at (0,5) {Transmissor}; \draw (-1.5,4.5) rectangle (1.5,5.5); \draw (0,4.5) -- (0,4.25); \draw [->] (0,3.75) -- (0,3.5); \node at (0,4) {\emph{Ruído}}; \node at (0,3) {Receptor}; \draw (-1.5,2.5) rectangle (1.5,3.5); \draw (0,2.5) -- (0,2.25); \draw [->] (0,1.75) -- (0,1.5); \node at (0,2) {\emph{palavra recebida de $n$ dígitos}}; \node at (0,1) {Decodificador}; \draw (-1.5,0.5) rectangle (1.5,1.5); \draw [->] (0,0.5) -- (0,0) node [below] {\emph{mensagem de $m$ dígitos recibida ou erro}}; \end{tikzpicture}
Figura 8.1.1. Codificar e Decodificar Mensagens

Mensagens não codificadas podem ser compostas de letras ou caracteres, mas normalmente consistem de \(m\)-tuplas binárias. Essas mensagens se codificam em palavras de um código, que são \(n\)-tuplas binárias, por meio que um mecanismo chamado codificador. A mensagem é transmitida e logo decodificada. Consideraremos a aparição de erros durante a transmissão. Um erro ocorre se acontece uma troca em um ou mais bits da palavra do código. Um esquema decodificador é um método que tanto converte uma \(n\)-tupla arbitrátia recebida em uma mensagem decodificada coerente como retorna um erro para essa \(n\)-tupla. Se a mensagem recebida é uma palavra do código (um das \(n\)-tuplas permitidas), então a mensagem decodificada deve ser a mensagem única que foi codificada no código. Para tuplas recebidas que não estão no código, o esquema dará uma indicação de erro, ou, se formos mais espertos, tratará de corrigir o erro e reconstruir a mensagem original. Nosso objetivo é transmitir mensagens sem erros da forma mais barata e rápida possível.

Um possível mecanismo de codificação seria enviar a mensagem múltiplas vezes e comparar as cópias recebidas entre elas. Suponhamos que a mensagem a ser codificar é uma \(n\)-tupla binária \((x_{1}, x_{2}, \ldots, x_{n})\text{.}\) A mensagem se codifica em uma \(3n\)-tupla binária simplesmente repetindo a mensagem três vezes:

\begin{equation*} (x_{1}, x_{2}, \ldots, x_{n}) \mapsto (x_{1}, x_{2}, \ldots, x_{n}, x_{1}, x_{2}, \ldots, x_{n}, x_{1}, x_{2}, \ldots, x_{n}). \end{equation*}

Para decodificar a mensagem, escolhemos como o \(i\)-ésimo dígito, o que aparece na \(i\)-ésima posição, de ao menos duas das três transmissões. Por exemplo, se a mensagem original é \((0110)\text{,}\) então a mensagem transmitida será \((0110\; 0110\; 0110)\text{.}\) Se existe um erro de transmissão no quinto dígito, então a palavra recebida será \((0110\; 1110\; 0110)\text{,}\) a que será corretamente decodificada como \((0110)\text{.}\) 1  Este método de repetição tripla automaticamente detecta e corrige todos os erros individuais, mas é lento e ineficiente: para enviar uma mensagem que consista de \(n\) bits, precisamos \(2n\) bits adicionais, e só podemos detectar e corrigir erros individuais. Veremos que é possível encontrar esquema de codificação que codifique uma mensagem de \(n\) bits em uma mensagem de \(m\) bits com \(m\) muito menor que \(3n\text{.}\)

A paridade, um mecanismo de codificação usual, é muito mais eficiente que a simples repetição. O código ASCII (American Standard Code for Information Interchange) usa 8-tuplas binárias, dando lugar a \(2^{8} = 256\) 8-tuplas possíveis. Mas, só são necessários 7 bits pois só existem \(2^7 = 128\) caracteres ASCII. O que se pode ou deve fazer com o bit restante? Usando os oito dígitos, podemos detectar um erro individual de transmissão. Por exemplo, os códigos ASCII para A, B, e C são

\begin{align*} \text{A} & = 65_{10} = 01000001_{2},\\ \text{B} & = 66_{10} = 01000010_{2},\\ \text{C} & = 67_{10} = 01000011_{2}. \end{align*}

Note que o bit mais a esquerda é sempre 0, isto é, os 128 caracteres ASCII têm códigos

\begin{align*} 00000000_{2} & = 0_{10},\\ & \vdots\\ 01111111_{2} & = 127_{10}. \end{align*}

O bit pode ser usado para controlar erros nos outros sete bots. Colocamos como 0 ou 1 de maneira que o número total de bits 1 na representação do caractere seja par. Usando paridade, os códigos A, B e C são convertidos em

\begin{align*} \text{A} & = 01000001_{2},\\ \text{B} & = 01000010_{2},\\ \text{C} & = 11000011_{2}. \end{align*}

Suponhamos que é enviado A e ocorre um erro de transmissão no sexto bit de maneira que recebemos \((0100\; 0101)\text{.}\) Sabemos que foi produzido um erro, pois recebemos um número ímpar de uns, e podemos pedir que a palavra seja transmitida. Quando é usado para detectar erros, o bit mais a esquerda é chamado bit de controle de paridade.

Por muito o mecanismo mais comum de detecção de erros nos computadores é baseado na adição de um bit de paridade. Tipicamente, um computador guarda a informação em \(m\)-tuplas chamadas palavras. Comprimentos comuns de palavras são 8, 16 e 32 bits. Um bit na palavra é reservado para ser bit de controle de paridadee e não é usado para armazenar informação. Esse bit pode ser 0 ou 1, dependendo do número de uns na palavra.

Adicionar um controle de paridade permite a detecção de todos os erros únicos pois qualquer troca de um só bit já aumenta ou diminui em 1 o número de uns, e em qualquer caso, troca a paridade de par para ímpar, de maneira que a nova palavra não seja uma palavra do código.

O sistema de paridade é fácil de ser implementado, mas tem duas desvantagens. A primeira é que múltiplos erros não são detectados. Suponha que uma mensagem A é enviada e o primeiro e o sétimo dígito da transmissão são alterados. A palavra recebida resultará em uma mensagem do código, mas será decodificada como C no lugar de uma A. Em segundo lugar, não temos a habilidade de corrigir erros. Se a 8-tupla \((1001\; 1000)\) é recebida, sabemos que ocorreu um erro, mas não temos ideia qual foi o bit que foi trocado. Investigaremos agora um mecanismo de codificação que não só nos permitirá detectar erros de transmissão, mas nos permitirá corrigi-los.

Tabela 8.1.4.
Palavra Palavra Recebida
Transmitida 000 001 010 011 100 101 110 111
000 0 1 1 2 1 2 2 3
111 3 2 2 1 2 1 1 0

Suponhamos que nossa mensagem original é 0 ou 1, e que 0 se codifica em (000) e 1 se codifica em (111). Se ocorre só um erro durante a transmissão, então podemos detectar e corrigir este erro. Por exemplo, se recebemos um 101, então o segundo bit deve ter sido trocdo de 1 para 0. A palavra transmitida deve ter sido (111). Este método detectará e corrigirá todos os erros únicos.

Na Tabela 8.1.4, apresentamos todas as possíveis palavras que podem ser recebidas pelas palavras transmitidas (000) e (111).A Tabela 8.1.4 também mostra o número de bits em que cada 3-tupla difere da palavra original.

Subseção 8.1.1 Decodificação de Máxima Verossimilhança

O mecanismo de codificação apresentado no Exemplo  8.1.5 não é uma solução completa do problema, pois não leva em conta a possibilidade de múltiplos erros. Por exemplo, tanto (000) como (111) poderiam ser recebidos como (001). Não temos como, a partir da palavra recebida, ver se foi cometido só um erro no terceiro bit ou dois erros, um no primeiro bit e outro no segundo. Não importa o mecanismo de decodificação usado, uma mensagem incorreta pode ser recebida. Poderíamos transmitir um (000), ter erros nos três bits e receber a palavra (111) do código. É importante explicitar as suposições feitas sobre a probabilidade e destribuição dos erros de transmissão de maneira que, em uma aplicação particular, saibamos se um certo mecanismo de detecção de erros é apropriado. Suponha que os erros de transmissão são pouco frequentes e, quando ocorrem, ocorrem de forma independente de cada bit, isto é, se \(p\) é a probabilidade de um erro em um bit e \(q\) é a probabilidade de erro em outro bit, então a probabilidade de erros nos dois bits ao mesmo tempo é \(pq\text{.}\) Também suponha que uma \(n\)-tupla recebida se decodificará na palavra do código que está mais perto, suponha que o receptor usa decodificação de máxima verossimilhança. 2 

\begin{tikzpicture}[scale=1] \node at (1.5,0) [below] {$p$}; \draw [->] (0,0) node [left] {1} -- (3,0) node [right] {1}; \node at (1.5,2) [above] {$p$}; \draw [->] (0,2) node [left] {0} -- (3,2) node [right] {0}; \draw [->] (0,0.2) -- (3,1.8); \draw [->] (0,1.8) -- (3,0.2); \node at (1.8,1.15) [above] {$q$}; \node at (1.8,0.85) [below] {$q$}; \end{tikzpicture}
Figura 8.1.6. Canal binário simétrico

Um canal binário simétrico é um modelo que consiste em um transmissor capaz de enviar um sinal binário, um 0 ou um 1, junto com um receptor. Seja \(p\) a probabilidade de que o sinal seja recebido corretamente. Então \(q = 1 - p\) é a probabilidae de recepção incorreta. Se é enviado um 1, então a probabilidade de receber um 1 é \(p\) e a probabilidade de receber um 0 é \(q\) (Figura 8.1.6). A probabilidade de que não ocorra nenhum erro durante a transmissão de uma palavra binária do código de tamanho \(n\) é \(p^{n}\text{.}\) Por exemplo, se \(p=0.999\) e é enviada uma mensagem que consiste de 10.000 bits, então a probabilidade de uma transmissão perfeita é

\begin{equation*} (0,999)^{10.000} \approx 0,00005. \end{equation*}

Fixemos \(k\) coordenadas diferentes. Calculemos primeiro a probabilidade de que um erro tenha ocorrido neste conjunto fixo de coordenadas. A probabilidade que tenha ocorrido um erro em uma \(k\) coordenadas particular é \(q\text{;}\) a probabilidade que nenhum erro tenha ocorrido em uma das restantes \(n-k\) coordenadas é \(p\text{.}\) A probabilidade de cada um desses \(n\) eventos independentes é \(q^{k}p^{n-k}\text{.}\) O número de sequências de erros possíveis com exatamente \(k\) erros é igual a

\begin{equation*} \binom{n}{k} = \frac{n!}{k!(n - k)!}, \end{equation*}

o número de combinações de \(k\) coisas escolhidas de um total de \(n\text{.}\) Cada uma dessas sequências de erros tem probabilidade \(q^{k}p^{n-k}\) de ocorrer; logo, a probabilidade de todas essas sequências de erros é

\begin{equation*} \binom{n}{k} q^{k}p^{n - k}. \end{equation*}

Suponha que \(p = 0.995\) e que é enviada uma mensagem de 500-bits. A probabilidade de que a mensagem tenha sido enviada sem erros é

\begin{equation*} p^{n} = (0.995)^{500} \approx 0.082. \end{equation*}

A probabilidade que tenha ocorrido exatamente um erro é

\begin{equation*} \binom{n}{1} qp^{n - 1}= 500(0.005)(0.995)^{499} \approx 0.204. \end{equation*}

A probabilidade de exatamente dois erros é

\begin{equation*} \binom{n}{2} q^{2}p^{n - 2}= \frac{500 \cdot 499}{2}(0.005)^{2}(0.995)^{498} \approx 0.257. \end{equation*}

A probabilidade de mais de dois erros é

\begin{equation*} 1 - 0.082 - 0.204 - 0.257 = 0.457. \end{equation*}

Subseção 8.1.2 Códigos de Blocos

Se vamos desenvolver códigos eficientes para detectar e corrigir erros, precisaremos de ferramentas matemáticas mais sofisticadas. A teoria de grupos permitirá métodos mais rápidos e eficientes para codificar e decodificar mensagens. Um código é um código de blocos \((n, m)\) se a informação que será codificada puder ser dividida em blocos de \(m\) dígitos binários, cada um dos quais pode ser codificado em \(n\) dígitos binários. Mais especificamente, um código de blocos \((n, m)\) consiste de uma função codificadora

\begin{equation*} E:{\mathbb Z}^{m}_{2} \rightarrow {\mathbb Z}^{n}_{2} \end{equation*}

e uma função decodificadora

\begin{equation*} D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{m}_{2}. \end{equation*}

Uma palavra do código é qualquer elemento na imagem de \(E\text{.}\) Também precisamos que \(E\) seja 1-1 de maneira que dois blocos de informação não sejam codificados para mesma palavra do código.

O código de paridade desenvolvido para detectar erros individuais em caracteres ASCII é um código de blocos \((8,7)\text{.}\) A função codificadora é

\begin{equation*} E(x_7, x_6, \ldots, x_1) = (x_8, x_7, \ldots, x_1), \end{equation*}

donde \(x_8 = x_7 + x_6 + \cdots + x_1\) com a soma em \({\mathbb Z}_2\text{.}\)

Sejam \({\mathbf x} = (x_1, \ldots, x_n)\) e \({\mathbf y} = (y_1, \ldots, y_n)\) \(n\)-tuplas binárias. A distância de Hamming ou distância, \(d({\mathbf x}, {\mathbf y})\text{,}\) entre \({\mathbf x}\) e \({\mathbf y}\) é o número de bits em que \({\mathbf x}\) e \({\mathbf y}\) diferem. A distância entre duas palavras do código é o número mínimo de erros de transmissão necessário para transformar uma das palavras na outra. A distância mínima para um código, \(d_{\min}\text{,}\) é o mínimo de todas as distâncias \(d({\mathbf x}, {\mathbf y})\text{,}\) donde \({\mathbf x}\) e \({\mathbf y}\) são palavras distintas do código. O peso, \(w({\mathbf x})\text{,}\) de uma palavra de um código binário \({\mathbf x}\) é o número de uns em \({\mathbf x}\text{.}\) Claramente, \(w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\text{,}\) donde \({\mathbf 0} = (00 \cdots 0)\text{.}\)

Sejam \({\mathbf x} = (10101)\text{,}\) \({\mathbf y} = (11010)\text{,}\) e \({\mathbf z} = (00011)\) todas as palavras em um código \(C\text{.}\) Então temos as seguintes distâncias de Hamming:

\begin{equation*} d({\mathbf x},{\mathbf y}) = 4, \qquad d({\mathbf x},{\mathbf z}) = 3, \qquad d({\mathbf y},{\mathbf z}) = 3. \end{equation*}

A distância mínima para este código é 3 e os pesos são:

\begin{equation*} w({\mathbf x}) = 3, \qquad w({\mathbf y}) = 3, \qquad w({\mathbf z}) = 2. \end{equation*}

A seguinte proposição lista algumas propriedades básicas sobre o peso de uma palavra do código e a distância entre duas palavras do código. A demonstração é deixada como exercício.

Os pesos em um código particular são usualmente muitos mais fáceis de calcular que as distâncias de Hamming entre todas as palavras do código. Se um código é construído cuidadosamente, podemos tirar proveito deste fato.

Suponhamos que \({\mathbf x} = (1101)\) e \({\mathbf y} = (1100)\) são palavras em algum código. Se transmitimos (1101) e um erro ocorre no bit mais a direita, então receberemos (1100). Como (1100) é uma palavra do código o decodificador decodificará (1100) como a mensagem transmitida. Este código claramente não é muito apropriado para a detecção de erros. O problema é que \(d({\mathbf x}, {\mathbf y}) = 1\text{.}\) Se \({\mathbf x} = (1100)\) e \({\mathbf y} = (1010)\) são palavras do código, então \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Se \({\mathbf x}\) é transmitido e ocorre um erro, então \({\mathbf y}\) nunca pode ser recebido. A Tabela 8.1.12 mostra as distâncias entre todas as palavras do código de 4-bits em que os primeiros três bits são de informação e o quarto é um bit de controle de paridade. Podemos ver que a distância mínima neste caso é 2, logo, o código se encaixa como código de detecção de um erro.

Tabela 8.1.12.
0000 0011 0101 0110 1001 1010 1100 1111
0000 0 2 2 2 2 2 2 4
0011 2 0 2 2 2 2 4 2
0101 2 2 0 2 2 4 2 2
0110 2 2 2 0 4 2 2 2
1001 2 2 2 4 0 2 2 2
1010 2 2 4 2 2 0 2 2
1100 2 4 2 2 2 2 0 2
1111 4 2 2 2 2 2 2 0

Para determinar exatamente quais são as capacidades de detecção e correção de erros de um código, devemos analisar a distância mínima para o código. Sejam \({\mathbf x}\) e \({\mathbf y}\) palavras do código. Se \(d({\mathbf x}, {\mathbf y}) = 1\) e ocorre um erro donde \({\mathbf x}\) e \({\mathbf y}\) diferem, então \({\mathbf x}\) se transforma em \({\mathbf y}\text{.}\) A palavra recebida é \({\mathbf y}\) e não é produzido nenhuma mensagem de erro. Agora suponhamos que \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Então um único erro não pode transformar \({\mathbf x}\) em \({\mathbf y}\text{.}\) Portanto, se \(d_{\min} = 2\text{,}\) temos a habilidade de detectar erros únicos. Todavia, suponhamos que \(d({\mathbf x}, {\mathbf y}) = 2\text{,}\) \({\mathbf y}\) é enviado, e se recebe uma palavra \({\mathbf z}\) que não está no código tal que

\begin{equation*} d({\mathbf x}, {\mathbf z}) = d({\mathbf y}, {\mathbf z}) = 1. \end{equation*}

Então o decodificador não pode decidir entre \({\mathbf x}\) e \({\mathbf y}\text{.}\) No entanto, estamos conscientes de que foi cometido um erro, não sabemos qual foi esse erro.

Suponhamos que \(d_{\min} \geq 3\text{.}\) Então o algoritmo de decodificação de máxima verossimilhança corrige todos os erros únicos. Começando com uma palavra \({\mathbf x}\) do código, um erro de um único bit na transmissão da \({\mathbf y}\) com \(d({\mathbf x}, {\mathbf y}) = 1\text{,}\) mas \(d({\mathbf z}, {\mathbf y}) \geq 2\) para qualquer outra palavra \({\mathbf z} \neq {\mathbf x}\) do código. Se não precisamos corrigir erros, então podemos detectar quando um código tem distância mínima maior ou igaul a 3.

Suponhamos que é enviada uma palavra \({\mathbf x}\) do código e que é recebida a palavra \({\mathbf y}\) com, no máximo, \(n\) errores. Então \(d( {\mathbf x}, {\mathbf y}) \leq n\text{.}\) Se \({\mathbf z}\) é qualquer palavra do código distinta de \({\mathbf x}\text{,}\) então

\begin{equation*} 2n+1 \leq d( {\mathbf x}, {\mathbf z}) \leq d( {\mathbf x}, {\mathbf y}) + d( {\mathbf y}, {\mathbf z}) \leq n + d( {\mathbf y}, {\mathbf z}). \end{equation*}

Logo, \(d({\mathbf y}, {\mathbf z} ) \geq n+1\) e \({\mathbf y}\) será decodificada corretamente como \({\mathbf x}\text{.}\) Agora suponhamos que \({\mathbf x}\) é transmitido e \({\mathbf y}\) é recebido e que ao menos um erro ocorreu, mas não mais que \(2n\) erros. Então \(1 \leq d( {\mathbf x}, {\mathbf y} ) \leq 2n\text{.}\) Como a distância mínima entre palavras do código é \(2n +1\text{,}\) \({\mathbf y}\) não pode ser uma palabra do código. Assim, o código pode detectar entre 1 até \(2n\) erros.

Na Tabela 8.1.15, as palavras \({\mathbf c}_1 = (00000)\text{,}\) \({\mathbf c}_2 = (00111)\text{,}\) \({\mathbf c}_3 = (11100)\text{,}\) e \({\mathbf c}_4 = (11011)\) determinam um código corretor de um erro.

Tabela 8.1.15.
00000 00111 11100 11011
00000 0 3 3 4
00111 3 0 4 3
11100 3 4 0 3
11011 4 3 3 0

Subseção 8.1.3 Nota Histórica

A teoria moderna de códigos começou em 1948 com a publicação de C. Shannon, titulada “A Mathematical Theory of Information” [7]. Em seu artigo, Shannon ofereceu um exemplo de um código algébrico e o Teorema de Shannon estabeleceu precisamente o quão bom códigos poderiam ser. Richard Hamming começou a trabalhar com códigos lineares em Bell Labs no final dos anos 1940s e princípios dos anos 1950s depois de sofrer a frustação de que os programas que compilava não eram capazaes de se recuperar de simples erros gerados por ruídos. A teoria de códigos cresceu tremendamente nas décadas seguintes. The Theory of Error-Correcting Codes, de MacWilliams e Sloane [5], publicado em 1977, já possuía mais de 1500 referências. Códigos lineares (códigos de blocos \((32, 6)\) de Reed-Muller) foram usados nas sondas espaciais Mariner da NASA. Sondas espaciais posteriores como Voyager usaram os chamados códigos de convolução. Atualmente, existem investigações ativas com respeito ao código Goppa, que dependem fortemente de geometria algébrica.

Adotaremos a convenção de numerar os dígitos da esquerda para direita nas \(n\)-tuplas binárias.
Esta seção requer conhecimentos de probabilidade, mas pode ser pulada, sem perda de continuidade.