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.

Definições

Detecção de erros

• Detecção de erros é a capacidade de detectar erros causados por ruído ou outras causas durante a transmissão de um emissor para um receptor.

Correcção de erros

• Correcção de erros, para além da detecção do erro, permite a sua correcção.

Implementação

Há duas formas de implementar um sistema de correcção de erros:

• Pedido Automático de Repetição ou ARQ (Automatic repeat request): o transmissor envia os dados e um código de detecção de erros, que permite que o receptor detecte a existência de erros. Se não encontrar erros, envia uma mensagem (um ACK, ou seja, aviso de recepção) ao emissor. Se o emissor não receber o ACK, então é porque a mensagem continha erros e é automaticamente re-transmitida.

• Correcção Adiantada de erros ou FEC (Forward error correction): O emissor codifica os dados com um código de correcção de erros e envia a mensagem. O receptor descodifica a mensagem que recebe para a forma "mais provável" ou seja, os códigos são implementados de forma a que a quantidade fosse necessária uma quantidade de ruído "improvável" para que a mensagem chegasse errada ao receptor.

Esquemas de detecção de erros

Existem diversos esquemas para se conseguir a detecção de erros de transmissão, e estes esquemas são, na sua maioria, muito simples. Todos os códigos de detecção de erros (incluindo detecção e correcção) transmitem mais informação do que a mensagem original. Na maioria dos esquemas, para além da mensagem, são transmitidos dados de "confirmação" - dados extra (também conhecidos como dados redundantes) que servem para a detecção de erros.

Esquemas de repetição

Existem algumas variantes deste esquema, mas basicamente consiste em enviar repetição da informação. Por exemplo, se fosse pretendido enviar a mensagem "olá", seria enviada "olá olá olá". Se fosse recebida a mensagem "olá olá olb", como uma das repetições não coincidia, sabia-se que tinha havido um erro. Este esquema é pouco eficiente (transmite 3 vezes os mesmos dados) e pode ser problemático em situações em que o erro ocorre no mesmo sítio - no nosso exemplo "olb olb olb". Neste caso, a mensagem "olb" era detectada como correcta.

Esquemas de paridade

As mensagens são partidas em vários blocos de bits (uns e zeros numa transmissão digital). O número de ocorrências do "1" é contado. Depois é activado um bit de paridade definido conforme o seguinte critério:

• 1 se o bit "1" aparece uma quantidade ímpar de vezes
• 0 se o bit "1" aparece uma quantidade par de vezes

Quando a mensagem chega, é testado o bit de paridade para verificar se está de acordo com o número de "1" da mensagem. Este esquema tem o problema de falhar quando o número de erros na transmissão é par. Por exemplo:

• Mensagem enviada: 10010100, em que há 3 ocorrências do bit "1", e como 3 é impar o bit de paridade é 1;
• Mensagem recebida: 10010111, com 5 ocorrências do bit "1", que também é ímpar e portanto gera um bit de paridade igual a 1;
• Resultado: a mensagem recebida está errada mas o erro não é detectado.

Redundância cíclica (CRC)

Uma forma mais complexa de detecção e correção de erros é a utilização de propriedades matemáticas da mensagem a ser transmitida.

Este método considera cada bloco de dados da mensagem como um coeficiente polinomial, dividindo-o depois por um outro polinômio predeterminado. O resto resultante da divisão é enviados pelo emissor como dados redundantes, para detecção de erros no receptor. No receptor, são novamente calculados o mesmo resto e comparado com o que foi enviados pelo emissor. Se não forem coincidentes, indica que houve um erro na transmissão.

Checksum

O checksum de uma mensagem é uma soma aritmética de certos componentes da mensagem - por exemplo a soma de todos os bytes que a compoem. Esta soma é enviada pelo emissor e recalculada no receptor, para ser comparada com a soma enviada. Se não forem coincidentes, indica que houve um erro na transmissão.

Correcçã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. Haveria uma grande vantagem se o receptor pudesse determinar qual foi o erro e corrigi-lo. Isto é possível. Vejamos o seguinte exemplo:

• "Se faltarm algmas letrs consguims entndr a mensgm".

Este conceito pode ser aplicado à correcção de erros nas transmissões digitais.

Pedido automático de repetição

O Pedido automático de repetição ou ARQ Automatic Repeat-reQuest é um método de controle de erros para transmissões de dados que usa os códigos de detecção de erros para conseguir transmissões confiáveis. Usa também as mensagens de acknowledgment e/ou não acknowledgement e os timeouts (tempos limites). Um acknowledgment (ACK) é uma mensagem enviada pelo receptor para o transmissor e que indica que um bloco de dados foi correctamente recepcionado.

Normalmente, quando o emissor não recebe o ACK antes de se esgotar o tempo limite, isto significa que o bloco de dados não foi recepcionado correctamente e retransmite-o.

Código de correção de erros (ECC - error-correcting code)

O ECC é 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.

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.