CRC


A verificação cíclica de redundância (do inglês, CRC - Cyclic Redundancy Check) é um método de detecção de erros normalmente usada em redes digitais e dispositivos de armazenamento para detectar mudança acidental em cadeias de dados. Mensagens de dados entrando nesses sistemas recebem um pequeno anexo com um valor de verificação baseado no resto de divisão polinomial do seu conteúdo. No ato da recuperação do dado o cálculo é refeito e comparado com o valor gerado anteriormente. Se os valores não se mostrarem semelhantes podem ser aplicadas ações para correção de dados, evitando assim a corrupção de dados. CRC pode ser usada para correção de erros a partir de alguns métodos.[1]

O nome CRC vem da redundância do valor de verificação atrelado ao dado (A mensagem recebe um aumento em seu tamanho sem adicionar uma informação) e o algoritmo de validação é construído com laços de repetição cíclicos.

A verificação cíclica de redundância é amplamente utilizada em dispositivos binários por ser de simples implementação, é matematicamente fácil de ser analisada e apresenta bons resultados na detecção de erros comuns em canais de transmissão causados por ruído. A função utilizada para gerar o valor de verificação possui tamanho fixo, e é utilizada igualmente como uma função hash.

O primeiro a propor a CRC foi W. Wesley Peterson em 1961. Hoje, a 32-bit CRC function of Ethernet e vários outros padrões são trabalhos de vários pesquisadores e foi publicada em 1975.

Introdução

Verificação cíclica de redundância é baseada na teoria de códigos de correção de erros cíclicos. O uso de códigos cíclicos sistemáticos, que alteram a mensagem adicionando um valor de verificação de tamanho fixo, com o propósito de detecção de erros em redes de comunicação foi proposta por W. Wesley Peterson em 1961.[2] Códigos cíclicos são simples de implementar e possuem o benefício apresentar ótimas respostas na detecção de erros causados pela “Rajada” de bits: sequencias continuas de símbolos de dados errados ( Burst Errors).

Eles são importantes por que Burst Errors são ocorrências comuns em canais de comunicação, incluindo canais óticos ou magnéticos. Geralmente, um n-bit CRC aplicado sobre uma mensagem de tamanho qualquer irá detectar cada um desses erros que forem menores que n bits e uma fração de 1/(1- 2^(-n)) de bits em mensagens maiores.

A determinação de um valor para o código de validação requer a definição de um Gerador Polinomial.

Esse polinomial será o divisor em uma divisão polinomial em que a mensagem de dados será o dividendo e o quociente é descartado, porém o resto será o código de verificação. É importante mencionar que os coeficientes do gerador são calculados de acordo com a aritmética de campo finito, para que a operação de adição possa sempre ocorrer paralelamente bit-a-bit(sem carry entre dígitos).O tamanho do resto será sempre menor que o do gerador polinomial, com isso pode-se determinar o tamanho do código de verificação.

Na prática, a maioria dos códigos utilizam um campo Galois de 2 elementos, GF(2).Os elementos são geralmente chamados de 0 e 1 coincidentemente utilizados na arquitetura binária.

Um CRC é chamado de n-bit CRC quando seu código de verificação possui tamanho de n bits. Para um dado n, múltiplos códigos de verificação são possíveis de serem construídos, cada um com um polinômio diferente. Tal polinômio possui o maior grau de valor n, além de n +1 termos. Ou seja, ele possui tamanho n + 1 bits.

Várias especificações descartam o MSB ou o LSB, pois eles sempre serão iguais a 1. Essas especificações serão encontradas mais a frente na forma de CRC-n-XXX.

O sistema de detecção ode erro mais simples, o bit de paridade, é na verdade um 1-bit CRC, de polinômio x + 1 (dois termos), de nome CRC-1.

En otros idiomas