CRC - Verificação de Redundância Cíclica

Verificação de redundância cíclica (CRC)

Introdução:

É uma técnica de detecção de erros usada amplamente nas redes de computadores de hoje e é baseada em códigos de verificação de redundância cíclica (cyclic redundancy check – CRC). É muito usada na prática (Ethernet, 802.11 WiFi, ATM).

Também conhecidos como códigos polinomiais, os códigos CRC consideram a cadeia de bits a ser enviada como um polinômio cujos coeficientes são os valores 0 e 1 na cadeia de bits e as operações nesta cadeia de bits são interpretadas como aritmética polinomial.

Funcionamento:

Consideramos a parcela de d bits de dados (D – número binário) que o nó remetente quer enviar para o nó receptor.

Primeiramente, o remetente e o receptor devem concordar com um padrão de r+1 bits, conhecido como um gerador, denominado por G.

É exigido, no exemplo, que o bit mais significativo (extrema esquerda) de G seja um 1. A ideia fundamental por trás dos códigos de CRC é mostrada na figura, a seguir:

Objetivo: escolher r bits de CRC, R, tal que:

Para uma dada parcela de dados D, o remetende escolherá r bits adicionais R e os anexará a D, de modo que o padrão d+r bits resultante (interpretado como um número binário) seja divisível exatamente por G (sem nenhum remanescente), usando a aritmética de módulo 2;

O receptor divide os d+r bits recebidos por G. Se o resto for diferente de zero, o receptor saberá que ocorreu um erro. Caso contrário, os dados são aceitos como corretos;

Desta forma, é possível detectar todos os erros em rajada menores que r+1 bits.

Exemplo:

Queremos: D . 2^r XOR R = nG, de modo equivalente a: D . 2^r = nG XOR R. Desta forma, se dividirmos D . 2^r por G, objetivamos o resto R:

R = resto [ D . 2^r/G]

Fonte: Kurose; Ross – Livro: Redes de Computadores e a Internet – Uma abordagem top-down. 5ª edição.