Cyclic redundancy check

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een cyclic redundancy check (CRC) is een fout-detectie-code 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 van een deling op de data. Bij het binnen nemen of lezen van de data wordt de deling terug uitgevoerd, als dezelfde rest bekomen wordt is de data correct. Blijkt deze echter niet correct te zijn dan kan via error-correctie de data hersteld worden.


CRC heeft haar naam te danken aan het feit dat het algoritme gebaseerd is op cyclische codes, de checksum redundant is (het vergroot het bericht zonder noodzakelijke informatie toe te voegen), en het data nakijkt. CRCs 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 transmissie kanaal. CRC is uitgevonden door W. Wesley Peterson in 1961.

Werking[bewerken]

Het CRC algoritme wordt steeds uitgevoerd op data dat opgeslagen of verzonden wordt. Elk stuk data wordt beschouwd als een binair getal. Het CRC algoritme zal dit binair getal delen door het 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 het CRC polynoom ontstaat er een checksum. Deze checksum wordt achter de data geplaatst. De data en checksum kunnen nu samen opgeslagen of verstuurd worden.

Als later de data gelezen of ontvangen wordt zal er terug een CRC deling plaatsvinden. De deling deelt het binair getal met daarachter de checksum door hetzelfde CRC polynoom. De deling zou geen rest mogen opleveren. Als er een fout plaatsgevonden heeft bij het opslaan of verzenden van de data, dan zal de rest verschillend zijn van 0. De deling kan ook enkel op het binair getal plaatsvinden, als de bekomen restwaarde gelijk is aan de checksum is er geen fout gedetecteerd in de data.

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

Data Integriteit[bewerken]

CRCs worden vooral gebruikt om vaak voorkomende fouten bij het verzenden van signalen te signaleren. Ze vormen een snelle manier om de integriteit van verzonden data te verzekeren. Maar dit is enkel zo als er vanuit gegaan wordt dat data niet onderschept en veranderd wordt.

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

Grootte van CRC[bewerken]

Een CRC wordt een n-bit CRC genoemd omdat de checksum een 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[bewerken]

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


Genereren van de checksum

De data die verzonden of opgeslagen wordt:

110101

Het CRC polynoom:

101

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

110101 00  / 101  =  11101 <-- 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 kan op 2 manieren gecontroleerd worden:

1) De data 11010 wordt terug gedeeld door 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 1101011 wordt gedeeld door 101 en de restwaarde vergeleken met 0.


Data met checksum:

11010111

Polynoom:

101

De data wordt weer modulo-2 (XOR) gedeeld door het polynoom.

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


Zie ook[bewerken]

Referenties[bewerken]

  • [1]: Ritter, T. 1986. The Great CRC Mystery. Dr. Dobb's Journal of Software Tools.
  • [2]: Schmidt, T. 2000. CRC Generating and Checking.