Cyclic redundancy check

Een cyclic redundancy check (CRC) is een foutdetectiecode die dikwijls gebruikt wordt in digitale netwerken en opslagmedia om bitfouten te detecteren. Blokken data die deze systemen binnenkomen, krijgen een korte controlewaarde of "checksum" gebaseerd op de rest bij een "deling met rest" op de data. Bij het binnenhalen of lezen van de data wordt de "deling met rest" wederom uitgevoerd, als daar dezelfde rest uitkomt zijn de data zeer waarschijnlijk correct. Blijken de data echter niet correct te zijn, dan kunnen via foutcorrectie de data hersteld worden.

CRC heeft haar naam te danken aan het feit dat het algoritme gebaseerd is op cyclische codes, dat de checksum redundant is (het vergroot het bericht zonder noodzakelijke informatie toe te voegen) en het de data controleert. CRC's worden zeer vaak toegepast omdat ze makkelijk te implementeren zijn in binaire hardware, gemakkelijk wiskundig te analyseren zijn, en goed zijn in het detecteren van veelvoorkomende fouten geproduceerd door ruis in een transmissiekanaal. CRC is uitgevonden door W. Wesley Peterson in 1961.

Werking

Het CRC-algoritme wordt steeds uitgevoerd op data die opgeslagen of verzonden worden. Elk deel van de data wordt beschouwd als een binair getal. Het CRC-algoritme zal dit binair getal delen door de CRC-polynoom. Dit is steeds een vaste binaire waarde die eigen is aan het algoritme. Als de binaire waarde van de data gedeeld wordt door de CRC-polynoom, ontstaat er een checksum. Deze checksum wordt achter de data geplaatst. De data en de checksum kunnen nu samen opgeslagen of verstuurd worden.

Als later de data gelezen of ontvangen worden, zal er weer een CRC-deling plaatsvinden. De deling deelt het binaire getal met daarachter de checksum door dezelfde CRC-polynoom. De deling zou geen rest mogen opleveren. Als er een fout plaatsgevonden heeft bij het opslaan of verzenden van de data, zal de rest meestal ongelijk zijn aan 0. De deling kan ook enkel op het binaire getal plaatsvinden; als de bekomen restwaarde gelijk is aan de checksum, is er geen fout gedetecteerd in de data.

De meeste toepassingen die (enkel) gebruikmaken van CRC, zullen niet trachten de fout te lokaliseren en te herstellen (foutcorrectie). Wel zullen ze ervoor zorgen dat de data opnieuw opgeslagen of verzonden worden tot er geen fouten meer gedetecteerd worden.

Data-integriteit

CRC's worden vooral gebruikt om vaak voorkomende fouten bij het verzenden van signalen te ontdekken. Ze vormen een snelle manier om de integriteit van verzonden data te verzekeren. Maar dit is enkel zo als ervan uitgegaan wordt dat data niet onderschept en veranderd worden.

Doordat er geen authenticatie aan te pas komt, kan een hacker de data veranderen en de CRC herberekenen, zodat de verandering niet gedetecteerd kan worden. Omdat CRC een gemakkelijk omkeerbare functie is, kan het niet gebruikt worden in digitale handtekeningen.

Grootte van CRC-checksum

Een CRC heet een n-bit CRC, als de checksum de grootte heeft van n bits. Voor een gegeven n zijn meerdere CRCs mogelijk, elk met een verschillend CRC-polynoom.

Langere CRC-polynomen zorgen voor een grotere zekerheid van de juistheid van de data, maar zorgen wel voor meer overhead.

Berekening

In dit voorbeeld worden binaire data met een lengte van 6 bits gecodeerd door een 2-bit CRC. Het CRC-polynoom is gelijk aan x²+1, dus met coëfficiënten 1, 0 en 1. Het resultaat, de checksum, is de rest van de deling en is 2 bits lang. Het quotiënt wordt niet gebruikt.

Genereren van de checksum

De data die verzonden of opgeslagen worden:

De CRC-polynoom:

De data worden modulo-2 (XOR) gedeeld door de polynoom en krijgen een toevoegsel van 2 bits (00) om ervoor te zorgen dat de uitkomst een quotiënt is met een restwaarde van 2 bits:

110101 00  / 101  =  111011 <-- Quotiënt
101
---
 111
 101
 ---
  100
  101
  ---
    11 0
    10 1
    -- -
     1 10
     1 01
     - --
       11 <-- restwaarde = CRC-checksum

Data samen met CRC-checksum = 11010111

Data controleren op een fout met CRC

De data kunnen op 2 manieren gecontroleerd worden:

1) De data 110101 worden teruggedeeld door de CRC-polynoom 101 en de rest vergeleken met checksum 11. Dit is exact dezelfde bewerking als bij het verzenden/opslaan van data.

2) De data 11010111 worden gedeeld door 101 en de restwaarde wordt vergeleken met 0.

Data met checksum:

11010111

Polynoom:

De data worden weer modulo-2 (XOR) gedeeld door de polynoom:

11010111  / 101  =  11101 <-- Quotiënt
101
---
 111
 101
 ---
  100
  101
  ---
    111
    101
    ---
     101
     101
      --
      00 <-- restwaarde is nul, dus geen fout ontdekt.

Zie ook

Coderingstheorie

Referenties

The Great CRC Mystery, Terry Ritter, Dr. Dobb's Journal of Software Tools, 1986
CRC Generating and Checking, Thomas Schmidt, 2000