Detecção e correção de erros

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:

2pd + 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.

Anúncios
Esse post foi publicado em Eletrônica e marcado , , , , . Guardar link permanente.

Uma resposta para Detecção e correção de erros

  1. Manuel disse:

    Como pode detectar 2 erros?

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s