CRC

Imagem: MarcoDV11 · BY-SA · Openverse

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. 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 porque 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.

Imagem: sponki25 · BY · Openverse

Um dispositivo que suporta CRC calcula uma pequena sequência binária de tamanho fixo, conhecido como código de verificação ou CRC, para cada mensagem que será enviada ou recebida e a anexa aos dados, formando uma palavra-código (codeword). Quando uma palavra código é recebida ou lida, o dispositivo compara seu código de verificação anexado com um novo, calculado a partir da mensagem, ou aplica o CRC sobre toda a palavra-código e compara o resultado com uma constante residual pré-definida. Se os códigos CRC não são semelhantes a mensagem contém erros de dados. O dispositivo pode realizar ações corretivas como reler a mensagem ou requisitar um novo envio da mesma. Senão os dados podem ser tratados como corretos e sem erro. (Com uma pequena probabilidade o código pode conter erros não detectados; essa é a natureza fundamental da verificação de erros).

Imagem: S.A. Julio · BY-SA · Openverse

Os códigos de verificação cíclica de redundância são projetados para proteger contra erros típicos dos canais de comunicação, onde podem garantir a integridade de mensagens de forma rápida e confiável. Entretanto, eles não são aplicáveis para proteção contra alteração intencional de dados. Não há nenhum tipo de autenticação, um invasor pode editar a mensagem e recalcular seu código de verificação sem que a substituição seja detectada. Quando as funções criptográficas de hash e a CRC são armazenadas em conjunto com os dados, elas não podem proteger contra alterações intencionais dos dados. Aplicações que requerem tal proteção devem usar mecanismos de autenticação criptográficas como códigos de autenticação da mensagem ou assinaturas digitais. Diferente das funções hash criptográficas , um CRC pode ser revertido facilmente, o que o torna inaplicável para uso com assinaturas digitais. Finalmente, CRC são criados a partir de funções lineares, com a seguinte propriedade: c r c ( x ⊕ y ⊕ z ) = c r c ( x ) ⊕ c r c ( y ) ⊕ c r c ( z ) {\displaystyle crc(x\oplus y\oplus z)=crc(x)\oplus crc(y)\oplus crc(z)}

Imagem: David Camelo · BY-SA · Openverse

Para calcular um CRC de n bits, coloque os bits representando o dado em uma linha, e abaixo do MSB dessa linha posicione o padrão (n + 1)-bit que representa o divisor CRC, também chamado de "polinômio". Neste exemplo será utilizado uma mensagem de 14 bits, com um 3-bit CRC, e o polinômio gerador. O polinômio precisa ser escrito em binário, um polinômio de 3ª ordem possui 4 coeficientes (). Nesse caso, os coeficientes são: 1, 0, 1, 1. O resultado do cálculo tem 3 bits de tamanho. Primeiro, são adicionados zeros no fim da palavra correspondentes ao tamanho n do CRC. Então é feito o primeiro cálculo para se obter o 3-bit CRC: O algoritmo age sobre os bits diretamente acima do divisor em cada passo. O resultado para a iteração acima é a operação OU-exclusivo bit-a-bit para os bits acima do divisor polinomial. Os bits restantes são diretamente copiados para o resultado daquele passo. O Divisor é então deslocado para a direita em 1 bit e o processo é repetido até que divisor alcance o ultimo bit da mensagem. O cálculo completo pode ser visto a seguir:

Imagem: Borodun · BY · Openverse

A análise matemática desse processo de “divisão” demonstra como selecionar um divisor que garantirá boas propriedades de detecção de erro. Nessa análise, os dígitos da linha de bits são utilizados como coeficientes de um polinômio em uma variável qualquer x (coeficientes que são na verdade elementos do campo finito de GF(2), ao invés de números quaisquer propriamente). Esse conjunto binário polinomial é um anel matemático.

Imagem: S.A. Julio · BY-SA · Openverse

O conceito da verificação cíclica de redundância como um algoritmo de detecção de erros ganha complexidade à medida que implementações ou comitês de normas à aplicam em sistemas reais. Alguns exemplos de complicações são: Essas complicações demonstram que um polinômio pode ser expresso de 3 formas diferentes: as duas primeiras são as mais encontradas em algoritmos, sendo que uma é a negação logica da outra; e a terceira é a forma encontrada nos artigos escritos por Koopman. Em cada caso, um termo é omitido. E o polinômio x 4 + x + 1 {\displaystyle x^{4}+x+1} pode ser representado como: Na tabela abaixo eles são representados como:

Imagem: S.A. Julio · BY-SA · Openverse

Vários algoritmos de verificação cíclica de redundância são regidos por Normas Técnicas. Nenhum algoritmo, ou implementação de um polinômio de qualquer grau pode ser utilizado para todas as aplicações. Koopman e Chakravarty recomendam que a seleção de um polinômio seja feita de modo a atender as necessidades da aplicação e o tamanho esperado das mensagens enviadas. O número de algoritmos de CRC que podem ser usados gera certa confusão nos desenvolvedores, esse é o problema que a maioria de autores sobre o assunto busca resolver. Existem 3 polinômios utilizados para o CRC-12, 19 conflitos nas definições para o CRC-16, e 7 para o CRC-32. Os polinômios que são utilizados não são necessariamente os mais eficientes. Desde 1993, Koopman, Castagnoli e outros trabalharam com a abrangência de polinômios entre 3 e 64 bits de comprimento, buscando exemplos que possuíam uma melhora na performance (em termos da Distância de Hamming para determinado tamanho de mensagem) em comparação com os polinômios utilizados em padrões anteriores, publicando os que apresentavam melhores resultados com o intuito de otimizar a capacidade de detecção de erros de padrões futuros. Em particular, o iSCSI e SCTP utilizam um dos polinômios descobertos durante a pesquisa, o polinômio (Castagnoli) CRC-32C.