CRC

 Nota: Se procura a moeda cujo código é CRC, veja Colón costa-riquenho.

CRC, do inglês Cyclic redundancy check, ou verificação de redundância cíclica é um código detector de erros, um tipo de função hash que gera um valor expresso em poucos bits em função de um bloco maior de dados, como um pacote de dados, ou um ficheiro, por forma a detectar erros de transmissão ou armazenamento.

O CRC é calculado e anexado à informação a transmitir (ou armazenar) e verificada após a recepção ou acesso, para confirmar se não ocorreram alterações. O CRC é popular por ser simples de implementar em hardware binário, simples de ser analisado matematicamente, e pela eficiência em detectar erros típicos causados por ruído em canais de transmissão.

Propriedades

A utilidade do CRC advém das seguintes propriedades:

1. Como todos os bits são usados no cálculo do CRC, a mudança em apenas um bit provoca uma mudança no CRC.
2. Mesmo mudanças pequenas nos dados levam a CRCs muito diferentes. Experiências com o CRC-32 (usando polinômios de 32 bits) mostram que é muito raro que a introdução de erros nos dados não seja detectado pelo CRC.
3. A probabilidade de qualquer dos 2³² valores possíveis para o CRC é praticamente uniforme.

Cálculo

O CRC é calculado através das operações da aritmética módulo 2. Com efeito, é o resto da divisão polinomial entre os dados a enviar, e um polinômio gerador adequadamente escolhido. Para efetuar esta divisão , cada posição dos bits no bloco de dados ou arquivo é considerado como uma potência de x no polinômio, e o valor do bit é o coeficiente correspondente (0 ou 1). Por exemplo, a seqüencia de bits 1001101100110100 deve ser considerada como sendo o polinômio:

$P(x) = 1x^{15} + 0x^{14} + 0x^{13} + 1x^{12} + 1x^{11} + 0x^{10} + 1x^9 + 1x^8 + 0x^7 + 0x^6 + 1x^5 + 1x^4 + 0x^3 + 1x^2 + 0x^1 + 0x^0$

ou seja:

$P(x) = x^{15} + x^{12} + x^{11} + x^9 + x^8 + x^5 + x^4 + x^2$

O polinômio composto por todos os bits do arquivo é dividido usando-se aritmética módulo 2 pelo polinômio gerador. O resto da divisão dos polinômios gera sempre um polinômio cujo grau é sempre menor que o grau do polinômio gerador, então se usamos um polinômio de grau 32, temos como resto um polinômio de grau 31 ou menos que podemos representar com 32 bits, um para cada coeficiente (o primeiro coeficiente é o de x⁰, por isso temos um coeficiente a mais que o grau).

Existem alguns polinômios geradores padronizados para serem usados no cálculo de CRC que foram testados para garantir as propriedades listadas acima. Os mais comuns são:

• CRC-32 que usa o polinômio gerador $CRC_{32}(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x^{1} + x^{0}$ ou 100000100110000010001110110110111 em notação binária.
• CRC-16 que usa o polinômio gerador $CRC_{16}(x) = x^{16} + x^{15} + x^{2} + x^{0}$ ou 11000000000000101 em notação binária.
• CRC-12 que usa o polinômio gerador $CRC_{12}(x) = x^{12} + x^{3} + x^{1} + x^{0}$ ou 1000000001011 em notação binária.
• CRC-8 que usa o polinômio gerador $CRC_{8}(x) = x^{8} + x^{2} + x^{1} + x^{0}$ ou 100000111 em notação binária.
• CRC-1 que usa o polinômio gerador $CRC_{1}(x) = 1$ ou 1 em notação binária. Este tipo de códificação é usualmente designada por código de paridade, a qual adiciona um bit 1 ou 0 á direita do conjunto de digitos binários a codificar.

É de salientar que o CRC é, contudo, inútil para validar a integridade dos dados - pelas suas características, é possível alterar os dados sem que o CRC reflita a alteração. Nestes casos pode-se utilizar as funções de hash criptográficas.

Bibliografia

• (em inglês) SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1

Ver também

• Tolerância a Falhas
• Falha (computação)
• TMR