On-line CRC berekening en routines

Over de Auteur: Lammert Bies is een vader, echtgenoot en polyglot. Hij ontwikkelt embedded systemen sinds de jaren tachtig. Gebruikte machinaal leren voordat het een naam had. Specialiseert in het verbinden van computers, robots en mensen. Was een Google Mapmaker Advocaat en spreker op verscheidene internationale conferenties voordat in 2017 de stekker uit Mapmaker werd getrokken. Bughunter met Google. Verspreidt op dit moment kunstmatige intelligentie naar de wildste plekken in productieomgevingen. Hij stopt nooit met leren.

• Inleiding in CRC berekeningen
• Vrij te downloaden CRC routines

Inleiding in CRC berekeningen

Overal waar digitale data wordt opgeslagen of verzonden is de kans op datacorruptie aanwezig. Sinds het begin van computer wetenschap hebben mensen nagedacht hoe met dit type probleem om kan worden gegaan. Voor seriële data kwamen ze met de oplossing om een pariteit bit achter elke verzonden byte te plakken. Dit eenvoudige detectie mechanisme werkt alleen, wanneer een oneven aantal bits in een byte verandert, maar een even aantal foutieve bits zal niet worden gedetecteerd door de parity check. Om dit problemen de baas te worden hebben mensen gezocht naar wiskundig correcte mechanismen om meerdere foutieve bits te detecteren. De CRC of cyclic redundancy check is hiervan het resultaat. Tegenwoordig worden CRC berekeningen gebruikt bij alle vormen van communicatie. Alle pakketten die over een network verzonden worden, worden gecontroleerd met een CRC. Ook heeft elk datablok op een harde schijf een daarbij horende CRC waarde. De moderne computerwereld kan niet zonder deze CRC berekeningen. Laten we daarom kijken waarom ze zo breed in gebruik zijn. Het antwoord is eenvoudig, ze zijn krachtig, detecteren vele soorten fouten en ze zijn bijzonder snel te berekenen, met name wanneer daarvoor speciale hardware chips worden gebruikt.

Men zou kunnen denken, dat het gebruik van een normale checksum—het optellen van alle datawaarden—reguliere CRC berekeningen kan vervangen. Het is zeker eenvoudiger om een checksum uit te rekenen, maar checksums vinden niet alle soorten fouten. Laten we een voorbeeld string nemen en daar van de één byte checksum berekenen. De voorbeeld string is “Lammert” die converteert naar de ASCII waarden [ 76, 97, 109, 109, 101, 114, 116 ]. De één byte checksum van deze lijst kan worden berekend door alle waarden op te tellen, dan te delen door 256 en de rest te bewaren. De resulterende checksum is 210. Je kunt de calculator hierboven gebruiken om dit resultaat te controleren.

In dit voorbeeld hebben we een één byte lange checksum gebruikt die 256 verschillende waarden kan aannemen. Bij het gebruik van een twee byte checksum zal dit resulteren in 65.536 verschillende checksum waarden en als een vier byte waarde wordt gebruikt zijn er meer dan vier miljard mogelijke waarden. We zouden hieruit kunnen concluderen dat met een vier byte checksum de kans dat we per ongeluk een fout niet detecteren kleiner is dan 1 op vier miljard. Dat klinkt aardig, maar is slechts theorie. In de praktijk vallen bits niet puur willekeurig om tijdens communicatie. Ze vallen vaak in rijen achter elkaar, of ten gevolge van elektrische pieken. Laten we aannemen dat in onze voorbeeld lijst het minst significante bit van het karakter ‘L‘ wordt gezet, en dat het minst significante bit van karakter ‘a‘ verloren raakt tijdens de communicatie. De ontvanger ziet dan de waarden [ 77, 96, 109, 109, 101, 114, 116 ] wat staat voor de string “M`mmert“. De checksum van deze nieuwe string is nog steeds 210, maar het resultaat is duidelijk foutief, slechts nadat twee bits zijn gewijzigd. Zelfs als we een vier byte lange checksum hadden gebruikt zouden we deze transmissie fout niet ontdekt hebben. Dus het berekenen van een checksum mag dan een simpele methode zijn om fouten te detecteren, maar het geeft niet veel meer bescherming dan het pariteitsbit, onafhankelijk van de lengte van de checksum.

Het idee van controlewaarde berekening is eenvoudig. Gebruik een functie F(bval,cval) dat één data byte accepteert en een controle waarde en geef vervolgens de herberekende controlewaarde terug. In feite kunnen checksum berekeningen op deze manier worden beschreven. Ons één byte checksum voorbeeld zou berekend hebben kunnen worden met de volgende functie (in de taal C) die we herhaaldelijk voor elk karakter in de invoerstring aanroepen. De initiële waarde voor cval is 0.

int F_chk_8( int bval, int cval ) {

    retun ( bval + cval ) % 256;

}

Het idee achter CRC berekening is om te kijken naar de data als één groot binair nummer. Dit nummer wordt gedeeld door een bepaalde waarde en de rest van de berekening wordt de CRC genoemd. Delen lijkt op het eerste zicht heel veel rekenkracht te kosten, maar het kan zeer snel worden uitgevoerd wanneer we een methode gebruiken die vergelijkbaar is met die we op school hebben geleerd. We zullen als voorbeeld de rest berekenen van het karakter ‘m‘—dat 1101101 is in binaire notatie—door het de delen door 19 of 10011. Let op, dat 19 een oneven getal is. Dit is nodig zoals we later zullen zien. Voor referentie kunnen de oude schoolboeken gebruikt worden want de hier getoonde binaire berekeningsmethode verschilt niet veel van de decimale methode die we geleerd hebben toen we jong waren. Het lijkt alleen misschien een beetje vreemd. Ook notaties verschillen tussen verschillende landen, maar de methode is vergelijkbaar.

                    1 0 1 = 5
            -------------
1 0 0 1 1 / 1 1 0 1 1 0 1
            1 0 0 1 1 | |
            --------- | |
              1 0 0 0 0 |
              0 0 0 0 0 |
              --------- |
              1 0 0 0 0 1
                1 0 0 1 1
                ---------
                  1 1 1 0 = 14 = remainder

Met een decimale berekening kan snel worden gecontroleerd dat 109 gedeeld door 19 een quotient geeft van 5 met een rest van 14. Maar wat we ook zien in dit schema dat elk bit extra dat we willen checken slechts één binaire vergelijking en in 50% van de gevallen een binaire aftrekking kost. Je kunt eenvoudig het aantal bits in de test data string verhogen—bijvoorbeeld naar 56 bits als we onze voorbeeld string “Lammert” gebruiken—en het resultaat kan worden berekend met 56 binaire vergelijkingen en een gemiddelde van 28 binaire aftrekkingen. Dit kan direct in hardware worden geïmplementeerd, waarbij slechts zeer weinig transistors noodzakelijk zijn. Ook software algoritmes kunnen heel efficiënt zijn.

Voor CRC berekeningen wordt geen normale aftrekking gebruikt, maar alle berekeningen worden modulo 2 uitgevoerd. In die situatie wordt het overloopbit gemakshalve vergeten en in de praktijk is een aftrekking dan gelijk aan een exclusive or operatie. Dit lijkt vreemd, de resulterende rest heeft een andere waarde, maar vanuit een algebraïsch gezichtspunt is de functionaliteit gelijkwaardig. Een discussie hierover zij een universitair kennisniveau van algebraïsche veld theorie noodzakelijk maken en ik denk dat de meeste lezers hierin niet geïnteresseerd zijn. Kijk aan het eind van dit document voor boeken die hier in detail op in gaan.

Nu hebben we een rekenmethode die implementeerbaar is in zowel hardware als software en daarbij ook een meer random gevoel uitstraalt dan een ordinaire checksum. Maar hoe gedraagd het zich in de praktijk als één of meer bits fout zijn? Als we de deler—19 in ons voorbeeld—als oneven getal kiezen, dan is er weinig hoge school wiskunde voor nodig om te zien dat elke enkelvoudig bit fout zal worden gedetecteerd. Dit is omdat elke enkelevoudige bit fout het deeltal laat veranderen met een macht van 2. Als bijvoorbeeld bit n verandert van 0 naar 1, dan zal de waarde van het deeltal toenemen met 2ⁿ. Als aan de andere kant bit n verandert van 1 naar 0, zal de waarde van het deeltal afnemen met 2ⁿ. Omdat het niet mogelijk is een macht van twee door een oneven getal te delen zal de rest van de CRC berekening veranderen en zo de fout niet onopgemerkt blijven.

De tweede situatie die we willen detecteren is wanneer twee losse bits wijzigen in de data. Hiervoor is enige wiskunde benodigd die kan worden gevonden in Tanenbaum’s boek dat hieronder genoemd is. Het is nodig de deler heel zorgvuldig te kiezen om er zeker van de zijn dat onafhankelijk van de afstand tussen de twee foute bits een dergelijke fout altijd gedetecteerd worden. Het is bekend dat veel gebruikte waarden 0x8005 en 0x1021 van de CRC16 en CRC-CCITT berekeningen het heel goed doen op dit punt. Let op dat andere getallen wel of niet deze eigenschap hebben en dat het niet eenvoudig te berekenen is welke deler waarde geschikt is voor het detecteren van twee bits fouten en welke niet. Vertrouw daarom op het uitvoerige wiskundige onderzoek op dit punt enkele decennia terug door hoog gekwalificeerde wiskundigen en gebruik de waarden die door deze mensen zijn vastgesteld.

Bovendien willen we alle fouten detecteren waarbij een oneven aantal bits wijzigt. Dit kan worden bereikt door een deler te nemen waarbij een even aantal bits gezet is. Wanneer we modulo 2 wiskunde gebruiken valt aan te tonen dat alle fouten met een oneven aantal bits gedetecteerd worden. Zoals ik hiervoor al heb gezegd wordt in modulo 2 berekeningen de aftrekfunctie vervangen door de exclusive or. Er zijn vier mogelijke XOR operaties.

0 XOR 0 => 0     even => even
0 XOR 1 => 1     odd  => odd
1 XOR 0 => 1     odd  => odd
1 XOR 1 => 0     even => even

We zien dat voor alle combinaties van bitwaarden de onevenheid van de expressie gelijk blijft. Door een deler te kiezen waarin een even aantal bits is gezet, zal de onevenheid van de rest gelijk zijn aan de onevenheid van het deeltal. Daarom zal, als de onevenheid van het deeltal verandert omdat een oneven aantal bits verandert, de rest ook wijzigen. Dus alle fouten die een oneven aantal bits veranderen zullen worden gedetecteerd door een CRC die met zo een deler is berekend. Je hebt mogelijk gezien dat de vaak gebruikte deler waarden 0x8005 en 0x1021 feitelijk een oneven aantal bits hebben, en niet even zoals hier is aangegeven. Dit is omdat er intern in het algoritme een “verborgen”extra bit 2¹⁶ is waardoor de werkelijke deler 0x18005 of 0x11021 wordt in het algoritme.

Tenslotte willen we alle zogenaamde burst errors van een bepaalde lengte detecteren en voor burst errors met grotere lengte willen we dat die kans zo groot mogelijk is. Burst errors zijn rijen van bits die door een storing allemaal hoog of laag geworden zijn. Burst errors komen veelvuldig voor in communicatie. Het is het type fout dat het gevolg is van onweer, schakelende relais en dergelijke waarbij gedurende een korte periode alle bits gezet worden. Om dit volledig te begrijpen is ook hier kennis nodig van modulo 2 algebra, dus accepteer alsjeblieft dat met een 16 bits deler het mogelijk is alle burst met een maximale lengte te detecteren van 16 bits, en alle langere bursts met een waarschijnlijkheid van tenminste 99.997%.

In een puur mathematische benadering wordt een CRC berekening opgeschreven als polynoom berekeningen. Het deeltal is meestal niet beschreven als een binair getal, maar als een polynoom van een bepaalde orde. In de dagelijkse situatie worden sommige polynomen vaker gebruikt dan anderen. De drie gebruikt in de on-line berekening op deze pagina zijn de 16 bit brede CRC16 en CRCCCITT en de 32 bits brede CRC32. De laatst wordt op dit moment waarschijnlijk het meest gebruikt omdat het ondermeer de CRC generator is voor alle netwerk verkeer verificatie en validatie.

Voor alle drie types CRC berekeningen heb ik een vrije software bibliotheek beschikbaar gemaakt. Het testprogramma bij de bibliotheek kan direct gebruikt worden om files of strings te testen. Je kunt ook kijken naar de broncodes en deze routines in je eigen programma integreren. Let op de initialisatie waarden van de CRC berekening en mogelijk nodige nabewerking zoals het omgooien van bits. Wanneer je dit niet doet kun je mogelijk andere resultaten krijgen dan andere implementaties. Al dit voor- en nabewerken is gedaan in het voorbeeldprogramma, dus zou het niet de moeilijk moeten zijn om je eigen implementatie werkend te krijgen. Een veel gebruikte test is om de CRC te berekenen van de ASCII string “123456789”. Als de uitvoer van je routine overeenkomt met de uitkomst van het testprogramma op deze website, dan werkt je implementatie en ben je uitwisselbaar met de meeste andere applicaties.

Als naslag zijn hier de polynoom functies voor de meest voorkomende CRC berekeningen. Houd in het achterhoofd dat de term met de hoogste orde van de polynoom (x¹⁶ of x³²) niet aanwezig is in de binaire nummer representatie, maar door het algoritme zelf geïmpliceerd wordt.