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
Om Poul-Henning KampKommentarer (3)
Vil du gøre Koopmans arbejde en gang til?
Eller har du et særligt ærinde?
-Jens
-
0 -
0
Nej, egentlig ikke, men fejl i flash-hukommelse har ikke samme (statistiske) natur som transmissionsfejl, så jeg vil gerne lige have simuleret mig igennem spørgsmålet, inden jeg skruer en microcontroller fast et sted hvor den skal sidde i 20år.
Mit brute-force survey er forresten lige blevet færdigt og har interessant nok fundet et andet resultat end Koopmans tabeller angiver: Han angiver bedste CRC for 496 bit payload til at være:
(x^3 + x + 1)(x^13 + x^11 + x^10 + x^9 + x^8 + x^6 + x^4 + x^3 + x^2 + x + 1)
der kun skulle misse 36800 fir-bit fejl.
I min simulation er det dog kun 32076 den misser, sandsynligvis fordi jeg bruger 'software-måden' at checke CRC, frem for 'hardware-måden' som Koopman bruger[1].
Men min simulation kom også frem til at:
(x^3 + x + 1)(x^13 + x^12 + x^11 + x^9 + x^8 + x^5 + x^3 + x^2 + 1)
Klarer sig marginalt bedre, nemlig kun 31955 4-bit-fejl misset.
Jeg skal have fundet ud af hvorfor der er den forskel...
Poul-Henning
[1] Software-måden er når du udregner CRC på payload og sammenligner med den gemte/fremsendte CRC. Hardware-måden er når du kører CRC på payload med gemt/fremsendt CRC appended og checker for nul-værdi i CRC registeret.
-
0
-
0
Hej Henning,
Hvad med din brute force kode - er den tilgængelig, eller skal folk med slige interesse selv hacke den deres foretrukne programmeringssprog ?
Mvh,
Martin.
-
0
-
0
