Detecção e correção de erros

Em matemática, ciência da computação e telecomunicações detecção e correcção de erros é um assunto de grande importância e relevância na manutenção da integridade dos dados em canais com ruído ou em sistemas de armazenamento não imunes a falhas.

Em um sistema de comunicação pode se dizer que é normal a ocorrência de erros, pois funciona por troca de mensagens a todo instante de um local com outro. Os erros podem ser causados por interferências eletromagnéticas, envelhecimento de componentes, curto-circuito, que acabam afetando as mensagens, fazendo com que, por exemplo, um “0” seja enviado, e na transmissão acaba sendo transformado em “1”, ou seja, receptor recebe informação diferente daquela que foi enviada.

Abaixo, serão vistas formas de tratar os erros, que seria utilizar métodos que bits aos códigos, a fim de detectar e corrigir erros.

Definições

Detecção de erros é receber o aviso de erro e em seguida encontrar este erro, que pode ser causado por interferências, ruídos, entre outros fatores já citado, durante a passagem da mensagem do emissor para o receptor, a fim de que possa ser corrigido pela correção de erros.
Correção de erros é receber informações do erro e fazer sua correção.

Métodos de detecção de erros

Em detecção de erros, já definido, pode ser utilizado por diversos métodos como: Método de repetição, método de paridade, Checksum, método de redundância cíclica e códigos de Hamming. Estes métodos, seguindo seus próprios conceitos, irão de alguma maneira, detectar o erro para passar a correção de erros. O que tem em comum entre todos estes métodos é a utilização de inserção de bits extras, funcionando de uma maneira fácil de compreender: emissor enviar junto à informação original bits a mais, então o receptor calcula estes bits a mais, enviados, bits extras.

Método de repetição

Este método é considerado problemático, muito comum, sem muita eficiência, pois ao enviar uma mensagem, são enviados três repetições desta mensagem, ou seja, um método que apenas envia repetições da mensagem e, a partir da comparação destas mensagens se detecta se há ou não erro.

Vamos trabalhar em cima de um exemplo para melhor entender este método: se pretender enviar a mensagem “Hello World” será enviado “Hello World Hello World Hello World”. Então se caso chegasse ao receptor a mensagem “Hello World Hello World Hello Torld” este método observa que há uma discordância nas mensagens então detecta o erro.

A má eficiência deste método está no caso de enviar as três vezes uma mensagem e estas três estiverem erradas. Para melhor entender sua pouca eficiência, vamos pegar o mesmo exemplo da mensagem “Hello World”. O emissor pode enviar “Hello World”, pode ocorrer o erro sendo transformado em “Hello Torld” e então chegará ao receptor a seguinte mensagem: “Hello Torld Hello Torld Hello Torld”, ou seja, aqui está o problema deste método, pois a mensagem irá ser considerada como correta, não detectando erro algum.

Método de Paridade

O método de paridade também é considerado ineficiente, porém é o mais utilizado na detecção de erros.

Este método não tem segredo algum, é fácil de entender. Ele consiste em ser adicionado, pelo transmissor, um bit de redundância (bit de paridade) após ou antes da seqüência de bits que pertence à mensagem. Esse bit adicionado segue a seguinte regra:

caso apareça o bit “1” número ímpar de vezes é adicionado 1, exemplo: 0100101 paridade = 1;
caso apareça o bit “1” número par de vezes é adicionado 0, exemplo: 010101010010100, paridade = 0;

Vamos aqui dar um exemplo que dê certo. O caractere H na mensagem “Hello world” é dado em bits por: 1000001. Em seguida, o bit de paridade é calculado e depois enviado: 1000001x, ou seja, existem dois bit “1” então seu bit de paridade é par, adicionando bit de paridade “0”, sendo enviado: 10000010. No receptor, esse calcula a paridade da mensagem enviada com o bit de paridade x adicionado, observa que x = paridade então determina mensagem correta.

Em caso de erro, vamos citar um exemplo. Há o envio do bit “00101”, sendo primeiro “0” como o bit de paridade, porém o receptor recebe o seguinte código: “00001”, ou seja, o circuito de verificação de paridade percebe que há apenas um único “1”, isto é impar, então é detectado o erro.

Checksum

Este método é muito simples e fácil de compreender, consiste em transmitir todas as palavras junto com o resultado da soma dos bits delas. Vamos trabalhar em cima de um exemplo para compreender melhor:

Dado os dados iniciais de duas palavras de 8 bits: 00111101 00001101, estes valores são somados dando resultado ao checksum: 01001010.

00111101+00001101 = 01001010 -> Checksum
10110101 -> Checksum invertido

O emissor envia o checksum invertido ao receptor. Em seguida, como o próprio nome desse método já diz, no receptor as palavras são novamente somadas e comparadas com checksum que foi enviado, ou seja, checar a soma.

Para a detecção de algum erro, se em qualquer um dos dados transmitidos tiver algum erro este será descoberto, pois no receptor é recalculado e ocorre a soma do novo checksum com o checksum enviado que terá um resultado diferente de “1”.

Exemplo de uma transmissão sem algum erro:

01001010 MAIS 10110101 = 11111111

Onde 01001010 representa novo Checksum, que representa as palavras recebidas, 10110101 representa checksum enviado(Invertido) e 11111111 indica que não ocorreu erro.

Redundância cíclica (CRC)

Caracterizado por ser de boa eficiência, que funciona basicamente em cima de uma concordância polinomial gerador “G(x)”, que quanto maior o grau deste G, maior a eficiência desse método para detectar um erro. Deixamos claro aqui que o neste polinômio, o bit de maior e menor ordem devem obrigatoriamente ser iguais a 1.

Seguindo o exemplo: palavra inicial: 10110001, o polinômio p(x) é igual aos bits da palavra inicial somada com bits de paridade, além disso, deve ser divisível pelo polinômio gerador G(x), ou seja, deve ter resto “0”, caso contrário houve erro.

Ocorrendo erro, para detectar, este método faz com que o receptor receba T(x)+E(x) em vez de receber o polinômio T(x) apenas, destacando que cada bit “1” em E(x) corresponde um bit inverso e,pegando T(x) e dividir por G(x) o resultado será sempre “0”.

Observando o exemplo: tendo a mensagem com bits 10111011, é calculado o polinômio do gerador, utilizando a fórmula: G(x) = x4 + x + 1 resultando em 10011, conforme a mensagem já citada e, para enviar ao receptor é adicionado nessa mensagem ainda a quantidade de zeros determinado pela equivalência do grau do gerador G(x), ficando como: 10111011 0000. Logo em seguida é feita a divisão da mensagem original sem os zeros do gerador com o polinômio gerador utilizando a operação XOR, ou seja:

101110110000 / 10011

No fim desta divisão sobra resto 01111, que é adicionado à mensagem original ficando: 101110111111, e é aqui com este código a mais que se detecta se houver erro, pois no receptor é novamente calculado este mesmo resto e caso não de o mesmo resultado é detectado e avisado o erro.^[1]

Códigos de hamming

Nesse método basicamente funciona com o envio de uma mensagem em códigos de 7 posições de bits que são numerados da esquerda para a direita e começando com “1”. Porém tem suas regras e especificações como, os bits que são potência de 2 vão ser bits 2n, já os outros são preenchidos com bits com a mensagem que será transmitida.

É feito a conversão das posições que são diferentes de 2n e valor igual a “1”, ficando na posição 3 e 7 respectivamente, 011 e 111. Pegando estes valores e aplicando OR exclusivo ou conhecido também como XOR, dá origem às 3 primeiras posições da mensagem: “0 0 1”.

Em seguida é inserido os valores obtidos nas posições do bit de paridade, por fim sendo enviada a mensagem: “0011001”.

Para detectar se há erro ou não, é aplicado novamente o XOR aos valores obtidos e se o resultado for igual a 0 é que não houve erro na transmissão, mas se for diferente indica que há erro, e para descobrir a posição onde está o erro é converter o resultado obtido para decimal.

Exemplo sem erro: 0011001

Posição: 3- 011; 4-100, 7-111.
011 XOR 100 = 111
111 XOR 111 = 000

Exemplo com erro: 0001001

Posição: 4-100; 7-111				                    
100 XOR 111 = 011-> indica erro na posição 3

Métodos de correção de erros

Os métodos descritos acima são suficientes para determinar se houve ou não um erro na transmissão de uma mensagem. Mas nas maiorias das vezes isto não é suficiente. As mensagem têm que ser recebidas sem erros e o mero conhecimento de que existiu um erro não chega. É preciso determinar exatamente qual foi o erro e depois corrigi-lo. Veja o exemplo:

"Se faltarm algmas letrs consguims entndr a mensgm".

Apesar de alterada, é possível entender o que a mensagem está dizendo. Obviamente, se a alteração for maior, não iremos entendê-la. Por exemplo:

"S as rs sg tn mns".

Podemos aplicar estes dois exemplos para entender correções de erros em Sistemas Digitais. Se tratando de correção de erros em pacotes, temos duas alternativas:

Pedido automático de repetição (ARQ - Automatic repeat request)

Utiliza a repetição como método de correcção de erros em tramas. O receptor informa o emissor de que não ocorreram erros na transmissão no lama, enviando um aviso de recepção (ACK). Se depois de um tempo o emissor não tiver recebido essa ACK, significa que o bloco possuía erros. Então o bloco é enviado de novo até que exceda um certo número de repetições de envio, ou até que a ACK seja recebida.^[2]

Auto-Correctores (ECC - Error Correcting Code e FEC - Forward error correction)

A Correcção Adiantada de Erros ou FEC (Forward Error Correction) — uma aplicação de código de correção de erro - ECC (Error Correcting Code)^[3] — é um código no qual cada sinal de dados está em conformidade com regras específicas de construção. Os desvios dessas regras podem ser detectados e corrigidos. Esta técnica é normalmente usada em armazenamento de dados no computador (por exemplo: memória flash) e em transmissões de dados.^[4]

Ele faz uso de um aumento significativo da informação de controle para corrigir o erro. Por isso eles são usados somente em situações específicas em que não haja outra alternativa, por exemplo numa transmissão "Simplex" (unidirecional). Se houver erro este mecanismo irá recorrer a um ou mais esquemas de detecção referidos anteriormente para saber exatamente em que bit(que varia entre 1 ou 0) está o erro para inverter esse bit.

Alguns códigos podem detectar e corrigir um certo número de bits de erros. Se apenas corrigirem um erro, são chamados códigos de correcção de erro único, ou SEC - single error correcting, e os que conseguem detectar dois erros são chamados de detecção de erro duplo, ou DED - double error detecting.

Referências

↑ René J. Glaise. «A two-step computation of cyclic redundancy code CRC-32 for ATM networks». IBM Journal of Research and Development. doi:10.1147/rd.416.0705. Consultado em 18 de maio de 2020. Arquivado do original em 30 de janeiro de 2009
↑ «Advice to link designers on link Automatic Repeat reQuest (ARQ)». IETF. RFC 3366. Consultado em 18 de maio de 2020
↑ Carlos Eduardo Morimoto (26 de junho de 2005). «ECC». Guia do Hardware. Consultado em 18 de maio de 2020
↑ «Forward Error Correction (FEC) Building Block». IETF. RFC 3452. Consultado em 18 de maio de 2020

Bibliografia

Floyd, Thomas L. (2007). Sistemas Digitais - Fundamentos e Aplicações 9.ª ed. Brasil: Artmed Editora. ISBN 978-85-7780-107-7

Ligações externas

[1] René J. Glaise. «A two-step computation of cyclic redundancy code CRC-32 for ATM networks». IBM Journal of Research and Development. doi:10.1147/rd.416.0705. Consultado em 18 de maio de 2020. Arquivado do original em 30 de janeiro de 2009

[2] «Advice to link designers on link Automatic Repeat reQuest (ARQ)». IETF. RFC 3366. Consultado em 18 de maio de 2020

[3] Carlos Eduardo Morimoto (26 de junho de 2005). «ECC». Guia do Hardware. Consultado em 18 de maio de 2020

[4] «Forward Error Correction (FEC) Building Block». IETF. RFC 3452. Consultado em 18 de maio de 2020

[1]

[2]

[3]

[4]