Olá leitores.
Desta vez um texto menos matemático, mas não menos técnico – sobre deteção e correção de erros. Os equipamento eletronicos, que de alguma forma, envolvem comunicação a executam de forma digital, ou seja, com sinais elétricos distretos, o Low (0) e o High (1). Entretanto, devido as limitações que os meios físicos apresentam, como por exemplo a resistência elétrica dos chips de computadores, os dados binários podem ser “perdidos”, id est, entrar em uma zona de tensão (normalmente entre 1V e 4V) que não pode ser reconhecida pelo processador dos dados como sendo um bit zero ou um. Quando isto ocorre diz-se que o bit ficou num estado “proibido”.
As limitações são conhecidas, entretanto não podemos ficar submetidos à incerteza sobre a informação recebida, ela deve ser clara e precisa. Para isso foram criados os códigos de detecção e correção de erros. Abaixo discorro sobre o método da paridade para a detecção e o método de Hamming para a detecção e correção – o segundo é uma melhora do primeiro. São algoritmos simples e permitem corrigir apenas um bit de cada série de dados. Existem outros métodos como o CRC (Código de Redundância Cíclica), Golay e Reed-Solomom, mas não serão por mim abordados.
Método da Paridade
O método da paridade consiste na adição de um bit verificador. Para paridade ímpar, a quantidade de bits “1” do código deve ser ímpar e para paridade par a quantidade deve ser par. É por meio da adição do bit de paridade que se faz o ajuste da quantidade, para atender ao requisito, de ter quantidade de “1” par, ou ímpar, dependendo da paridade adotada no sistema.
Por exemplo, para o código ‘11001’, no sistema de paridade par teria o bit verificador “1”, para que o código ficasse ‘111001’, e tendo, assim, portanto, uma quantidade par de “1”.
O código de correção de erro de Hamming
Foi criado em 1950 por Richard Hamming (1915-1998). Sua criação foi motivada pela imensa quantidade de erros de leitura dos cartões perfurados, nos computadores primitivos.
O código de Hamming prevê a correção de um único erro e se baseia no método da paridade, entretanto tem a vantagem de detectar a localização do erro.
Podem – e, em geral é o que ocorre – ser necessários mais de um bit de paridade para a verificação dos erros. O número de bits de paridade é dado pela seguinte fórmula:
2p ≥ d + p + 1
onde d é o número de bits do código e p é o número de bits de paridade necessários.
Os bits de paridade são inseridos nas posições 2n, onde n é um número natural; ou seja, nas posições 1,2,4,8 etc. Em um código de 8 bits, por exemplo, a posição 1 representa o bit mais significativo e a posição 8 o menos significativo (Tabela 1).
Tabela 1
| Designação | P1 | P2 | D1 | P3 | D2 | D3 | D4 |
| Posição | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Pos. em binário | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
A posição do bit em binário é um dado significativo para a determinação do bit de paridade. O bit P1 irá verificar os bits das posições binárias em que o algarismo menos significativo é 1. O bit P2 verificará os bits das posições binárias que possuem o bit 1, na posição central. E, finalmente, o bit P3 fará a verificação do conjunto de bits que possuem, na posição binária, o bit “1” na posição mais significativa. Os bits p1, P2 e P3 verificarão respectivamente os conjuntos {P1, D1, D2, D4}, {P2, D1, D3, D4} e {P3, D2, D3, D4}.
O processo foi descrito para o exemplo da tabela 1, de 7 bits, entretanto é bem genérico e, com processo análogo, se aplica a qualquer quantidade de bits.
A verificação de um código se dá da mesma forma que no método da paridade, com a diferença de terem que ser feitas uma verificação para cada um dos bits verificadores. Será encontrado, para cada bit verificador, a informação se o bit está correto ou não.
Feita a verificação do código, o próximo passo é determinar em qual posição está o bit com erro. Para os bits de paridade corretos atribui-se o bit 0 e para os incorretos atribui-se o bit 1. Representando o bit atribuído de cada bit de paridade por [P1] (bit atribuído à verificação feita por meio de P1), temos que a posição binária em que se encontra o bit com erro é – para o caso de um código de 7 bits – [P3][P2][P1].
Exemplo: Determine o erro no código recebido ‘0100011’.
Primeiramente, tabulam-se os dados para melhor visualização.
| Designação | P1 | P2 | D1 | P3 | D2 | D3 | D4 |
| Posição | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Pos. em binário | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| Código recebido | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
Fazendo a verificação para P1:
Consideram-se as posições 1, 3, 5, e 7, onde o código referente é 0001. A paridade está incorreta, portanto o bit a ser atribuído deve ser 1.
Fazendo a verificação para P2:
Consideram-se as posições 2, 3, 6 e 7, onde o código referente é 1011. A paridade está incorreta, portanto o bit a ser atribuído deve ser 1.
Fazendo a verificação para P3:
Consideram-se as posições 4, 5, 6 e 7, onde o código referente é 0011. A paridade está correta, portanto o bit a ser atribuído deve ser 0.
Finalização: O bit com erro está na posição binária 011, que corresponde à posição decimal 3. Onde o bit está como zero deve ser um.
Portanto o código correto é ‘0110011’.
Fonte:
Floyd, Thomas. Sistemas de numeração, operações e códigos. In:______.Sistemas Digitais: fundamentos e aplicações. Cap. 2.
Como pode detectar 2 erros?