O controlo de erros

Setembro 2015

O controlo de erros

A codificação binária é muito prática para uma utilização em aparelhos electrónicos como um computador, nos quais a informação pode ser codificada graças à presença ou não de um sinal eléctrico.

Contudo, o sinal eléctrico pode sofrer perturbações (distorção, presença de barulho), nomeadamente aquando do transporte dos dados num longo trajecto. Assim, o controlo da validade dos dados é necessário para certas aplicações (profissionais, bancárias, industriais, confidenciais, relativas à segurança,…).

É por isso que existem mecanismos que permitem garantir um certo nível de integridade dos dados, quer dizer, de fornecer ao destinatário um seguro de que os dados recebidos são bem similares aos dados emitidos. A protecção contra os erros pode fazer-se de duas maneiras:

  • ou fiabilizando o apoio de transmissão, quer dizer baseando-se numa proteção física. Uma ligação convencional tem geralmente uma taxa de erro compreendida entre 10-5 e 10-7.
  • ou instalando mecanismos lógicos de detecção e correcção dos erros.



A maior parte dos sistemas de controlo de erro ao nível lógico baseia-se numa adição de informação (fala-se de “redundância”) que permite verificar a validade dos dados. Chama-se soma de controlo (em inglês checksum) a esta informação suplementar.

A correcção de erros

É assim que sistemas de detecção de erro mais sofisticados foram criados, estes códigos são chamados:

  • códigos autocorrectores
  • códigos autoverificadores

O controlo de paridade

O controlo de paridade (chamado às vezes VRC, para Vertical Redundancy Check ou Vertical Redundancy Checking) é um dos sistemas de controlo mais simples. Consiste em acrescentar um bit suplementar (chamado bit de paridade) a um certo número de bits de dados chamado palavra de código (geralmente 7 bits, para formar um byte com o bit de paridade) cujo valor (0 ou 1) é tal que o número total de bits a 1 seja par. Para ser mais explícito, consiste em acrescentar um 1 se o número de bits da palavra de código for ímpar, 0 no caso contrário.

Tomemos o exemplo seguinte:




Neste exemplo, o número de bits de dados a 1 é igual, o bit de paridade por conseguinte é posicionado a 0. No exemplo seguinte, em contrapartida, os bits de dados sendo em número ímpar, o bit de paridade é de 1:




Imaginemos agora que após transmissão o bit de peso fraco (o bit situado à direita) do byte precedente é vítima de uma interferência:




O bit de paridade já não corresponde então à paridade do byte: um erro é detectado.

Contudo, se dois bits (ou um número igual de bits) viessem alterar simultaneamente aquando do transporte de dados, então nenhum erro seria detectado…




O sistema de controlo de paridade que só detecta os erros em número ímpar, permite por conseguinte detectar unicamente 50% dos erros. Este sistema de detecção de erros possui igualmente o grande inconveniente de não permitir corrigir os erros detectados (o único meio é exigir a retransmissão do byte errado…).

O controlo de paridade cruzado


O controlo de paridade cruzado (também chamado controlo de redundância longitudinal ou Longitudinal Redundancy Check, notado LRC) consiste não em controlar a integridade dos dados de um caracter, mas em controlar a integridade dos bits de paridade de um bloco de caracteres.


Imaginemos que “HELLO” é a mensagem a transmitir, utilizando o código ASCII standard. Eis os dados tal como serão transmitidos com os códigos de controlo de paridade cruzado:


LettreCódigo ASCII(das 7 bits)bit de paridade(LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

O controlo de redundância cíclico

O controlo de redundância cíclico (notado CRC, ou em inglês Cyclic Redundancy Check) é um meio de controlo de integridade dos dados potente e fácil de aplicar. Representa o principal método de detecção de erros utilizado nas telecomunicações.

Princípio

O controlo de redundância cíclico consiste em proteger blocos de dados, chamados tramas (frames em inglês). A cada trama é associado um bloco de dados, chamado código de controlo (às vezes CRC por abuso de linguagem ou FCS para Frame Check Sequência no caso de um código de 32 bits). O código CRC contém elementos redundantes no que diz respeito à trama, permitindo detectar os erros, mas também repará-los.

Contrôle de redondance cyclique (CRC)


O princípio do CRC consiste em tratar as sequências binárias como polinómios binários, quer dizer polinómios cujos coeficientes correspondem à sequência binária. Assim, a sequência binária 0110101001 pode ser representada sob a forma polinominal seguinte:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
soit  
X8 + X7 + X5 + X3 + X0
ou encore  
X8 + X7 + X5 + X3 + 1



Desta maneira, o bit de peso fraco da sequência (o bit mais à direita) representa o grau 0 polinómio (X0 = 1), o 4º bit partindo da direita representa o grau 3 polinómio (X3)… Uma sequência de n bits constitui por conseguinte um polinómio de grau máximo n-1. Todas as expressões polinominais são manipuladas seguidamente com uma aritmética módulo 2.

Neste mecanismo de detecção de erro, um polynómio predefinido (chamado polynómio gerador e notado G (X)) é conhecido do emissor e o receptor. A detecção de erro consiste, para o emissor, em efectuar um algoritmo sobre os bits da trama a fim de gerar um CRC, e transmitir estes dois elementos ao receptor. Basta então ao receptor que efectue o mesmo cálculo a fim de verificar que o CRC é válido.

Aplicação prática


Seja M a mensagem correspondente aos bits da trama a enviar e M (X) o polynómio associado. Chamemos Me à mensagem transmitida, quer dizer a mensagem inicial à qual terá sido concatenado o CRC de n bits. O CRC está como Me (X)/G (X) =0. O código CRC é assim igual ao resto da divisão polinominal de M (X) (ao qual de antemão concatenámos n bits nulos que correspondem ao comprimento do CRC) por G (X).


Mais simples ainda é tomar um exemplo: tomemos a mensagem M de 16 bits seguinte: 1011 0001 0010 1010 (notado B1 hexadecimal). Tomaemos G (X) = X3 + 1 (representado binário por 1001). Já que G (X) é de grau 3, trata-se de acrescentar 4 bits nulos a M: 10110001001010100000. O CRC é igual ao resto da divisão de M por G:

10110001001010100000  
1001...,..,.,.,.....  
----...,..,.,.,.....  
 0100..,..,.,.,.....  
 0000..,..,.,.,.....  
 ----..,..,.,.,.....  
  1000.,..,.,.,.....  
  0000.,..,.,.,.....  
  ----.,..,.,.,.....  
  1000.,..,.,.,.....  
   1001,..,.,.,.....  
   ----,..,.,.,.....  
 1111..,.,.,.....  
 1001..,.,.,.....  
 ----..,.,.,.....  
  1100.,.,.,.....  
  1001.,.,.,.....  
  ----.,.,.,.....  
   1101,.,.,.....  
   1001,.,.,.....  
   ----,.,.,.....  
    1000.,.,.....  
    0000.,.,.....  
    ----.,.,.....  
    10001,.....  
  1001,.,.....  
  ----,.,.....  
  10000.,.....  
   1001.,.....  
   ----  
    1111,.....  
    1001,.....  
    ----,.....  
     1100.....  
     1001.....  
     ----.....  
   1100....  
   1001....  
   ----....  
    1010...  
    1001...  
    ----...  
     0110..  
     0000..  
     ----..  
      1100.  
      1001.  
      ----.  
    1010  
    1001  
    ----  
    0011



Para criar Me basta concatenar o CRC assim obtido aos bits da trama a transmitir:

M' = 1011000100101010 + 0011  
M' = 10110001001010100011



Assim, se o destinatário da mensagem efectuar a divisão de Me por G, obterá um resto nulo se a transmissão se efectuar sem erro:

10110001001010100011  
1001...,..,.,.,...,,  
----...,..,.,.,...,,  
 0100..,..,.,.,...,,  
 0000..,..,.,.,...,,  
 ----..,..,.,.,...,,  
  1000.,..,.,.,.....  
  1001.,..,.,.,.....  
  ----.,..,.,.,.....  
   0010,..,.,.,.....  
   0000,..,.,.,.....  
   ----,..,.,.,.....  
 0101..,.,.,.....  
 0000..,.,.,.....  
 ----..,.,.,.....  
  1010.,.,.,.....  
  1001.,.,.,.....  
  ----.,.,.,.....  
   0110,.,.,.....  
   0000,.,.,.....  
   ----,.,.,.....  
    1101.,.,.....  
    1001.,.,.....  
    ----.,.,.....  
  1010,.,.....  
  1001,.,.....  
  ----,.,.....  
   0111.,.....  
   0000.,.....  
   ----  
    1110,.....  
    1001,.....  
    ----,.....  
     1111.....  
     1001.....  
     ----.....  
   1100....  
   1001....  
   ----....  
    1010...  
    1001...  
    ----...  
     0110..  
     0000..  
     ----,,  
      1101,  
      1001,  
      ----,  
    1001  
    1001  
    ----  
       0

Polinómios geradores


Os polinómios geradores o mais correntemente empregados são:

  • CRC-12 : X12 + X11 + X3 + X2 + X + 1
  • CRC-16 : X16 + X15 + X2 + 1
  • CRC CCITT V41 : X16 + X12 + X5 + 1

(Este código é utilizado nomeadamente no procedimento HDLC.)
  • CRC-32 (Ethernet) : = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1
  • CRC ARPA : X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1
Para uma leitura offline, é possível baixar gratuitamente este artigo no formato PDF:
O-controlo-de-erros .pdf

Veja também


Error checking
Error checking
Verificación de errores
Verificación de errores
Die Fehlerkontrolle
Die Fehlerkontrolle
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
Il controllo degli errori
Il controllo degli errori
Este documento, intitulado « O controlo de erros »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.