Jule-hack: CRC optimering
Jeg har et trivielt lille problem med en microcontroller: Jeg skal gemme nogle semi-statiske data i flash-hukommelsen, men denne er kun specificeret til 1000 skrivninger.
Ergo må der lidt CRC og reallokering til, ren rutine.
Bortset fra, at jeg et sted i baghovedet havde Philip Koopmans historiske paper, hvor han viste at de fleste og mest udbredte CRC polynomier er elendige.
Hvis du nogensinde har haft lejlighed til at vælge et CRC polynomie, har du sandsynligvis gjort det forkert, hvis du ikke har læst ovenstående paper.
Hvis du har forladt dig på allerede existerende CRC polynomier, som f.eks CCITT's eller andre, har du helt sikkert en elendig performance, for mange af de helt tidlige CRC polynomier var valgt efter at have så få "taps" som muligt, af hensyn til hardware implementeringerne.
Der findes således 16 bits CRC polynomier der kan fange næsten dobbelt så mange fejl som CCITT's CRC16.
Problemet er bare, at der er ikke er nogen god måde at vælge et CRC polynomium på, bortset fra at prøve dem alle, med de(n) længder data man har brug for at holde styr på.
Der er en lille detalje om CRC polynomier som de fleste ikke er klar over:
I hardware tester man ofte CRC ved at køre datablokken + dens CRC sum igennem CRC funktionen og derefter checke at man får rene nul-bits i hele registeret.
Faktisk er det den måde mange ethernetcontrollere plejede at detektere hvor lang en ethernet pakke var: Når CRC registeret var nul var pakken komplet.
Mange polynomier er særligt blinde for bitfejl i den appendede CRC sum, hvis man bruger denne metode. Ikke noget vildt og voldsomt, men en anelse mere følsomme end i resten af datablokken.
Hvis man derimod tester på "software måden", udregner CRC over datablokken og sammenligner med dens tidligere udregnede CRC sum, kan man godt bruge disse polynomier, der i visse tilfælde er en smule stærkere for andre fejl.
I mit tilfælde er der altid tale om 62 bytes og et 16 bit CRC, så nu er et par af mine computere igang med at tygge sig vej igennem alle 16 bits polynomier, for at finde det der har den bedste performance.
Alle polynomier bortset fra 0x0000 kan finde enkeltbitfejl, så det tester jeg ikke.
Jeg prøver med brute force om der er nogen to eller tre bits fejl der ikke detekteres og hvis der er, opgiver jeg dette polynomium, for Hamming Distancen for en 496 bit pakke er over 3 bit.
Derefter tester jeg ca. 10% af alle fire bits fejl og ser på antallet af misses. Hvis polynomiet kan møve sig ind på min top-100 liste og er bedre end CCITT's CRC16, udregner jeg det totale antal af fire-bits-fejl, dette polynomium ikke fanger.
Efter jul engang, vil jeg lave en monte-carlo test på min top-100 liste og se hvordan de klarer sig med 5, 6, 7 og særligt 8 bit fejl.
God Jul,
phk
...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.
Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.
Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.
Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.
