en smertefri GUIDE TIL CRC FEIL algoritmer
==================================== =============================== Denne artikkelen har blitt plassert på nettet ved feilindikator Controls, skaperne av sprut rekke microPLCs for OEM bruk. Splat er verdens mest kostnadseffektive microPLC. Fra off-the-sokkel produkter som sparer du mer enn de koster, til tilpassede bruker programmerbare kontrollere, er Splat en oppsiktsvekkende ny måte å gjøre elektroniske kontroller for maskiner i mengder på 1 til 50 000 pa
Hvis du vil sjekke ut Splat kopi og lim inn følgende URL til nettleseren sted eller adresse vinduet: http://splatco.com =============================== ==================================== Artikkel gjengitt med tillatelse fra eieren av opphavsretten. Nyte! ================================================== =================
en smertefri GUIDE TIL CRC FEIL algoritmer ====================== ============================ " Alt du ønsket å vite om CRC algoritmer, men var redd for å spørre i frykt for at feil i forståelse kan bli oppdaget "
versjon:. 3. Dato: 19 august 1993. Forfatter: Ross N. Williams. Netto: [email protected]. FTP: ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt Company: Rocksoft ^ tm Pty Ltd Snail: 16 Lerwick Avenue, Hazelwood Park 5066, Australia. Fax: +61 8 373-4911 (c /- inter Systems Pty Ltd). Telefon: +61 8 379-9217 (kl 10 til 22:00 Adelaide Australia tid). Merk: " Rocksoft " er et varemerke for Rocksoft Pty Ltd, Australia. Status: Copyright (C) Ross Williams, 1993. Imidlertid er det tillatt å lage og distribuere ordrette kopier av dette dokumentet, forutsatt at denne informasjonen blokken og opphavsrett er inkludert. Også C kode moduler som inngår i dette dokumentet er fullt ut offentlig domene. Takk. Takk til Jean-loup Gailly ([email protected]) og Mark Adler ([email protected]) som begge bevis lese dette dokumentet og plukket ut masse nits samt noen store fete bugs
Innhold ----------------- Abstract 1. Innledning: Feil Detection 2. Behovet for Complexity 3. Grunntanken bak CRC Algoritmer 4. Polynomical aritmetiske 5. Binary aritmetikk med Ingen Bærer 6. Fullt Jobbet Eksempel 7. Velge en Poly 8. Enkel CRC Gjennomføring 9. Tabell-Driven Gjennomføring 10. Litt lemlestede Table-Driven Implementering 11. " Reflektert " Tabell-Driven implementeringer 12. " Tilbake " Polys 13. Initial og sluttverdier 14. Definere Algoritmer Absolutt 15. parametriert modell for CRC Algoritmer 16. Katalog av parametersett for Standards 17. En implementering av modellen Algoritme 18. Roll din egen tabell-Driven Gjennomføring 19. generere A oppslag tabell 20. oppsummering 21. Korreksjoner A. Ordliste B. Referanser C. referanser jeg har oppdaget, men som ikke Blinde
Abstrakt -------- Dette dokumentet forklarer CRC (Cyclic Redundancy Codes) og deres bord -driven implementeringer i sin helhet, presise detaljer. Mye av litteraturen på CRC, og spesielt på deres bord-drevet implementeringer, er litt uklar (eller i det minste virker så for meg). Dette dokumentet er et forsøk på å gi en klar og enkel no-nonsense forklaring på CRC og absolutt spiker ned alle detaljer i driften av deres høy hastighet implementeringer. I tillegg til dette, presenterer dette dokumentet en parametrisk modell CRC algoritme kalt " Rocksoft ^ tm Model CRC algoritme ". Modellen algoritmen kan parametriseres til å oppføre seg som de fleste av CRC implementeringer rundt, og så fungerer som en god referanse for å beskrive spesielle algoritmer. En lav hastighet implementering av modellen CRC algoritmen er gitt i C programmeringsspråk. Endelig er det en del som gir to former for høyhastighets bord drevet implementeringer, og gir et program som genererer CRC oppslagstabeller
1. Introduksjon. Error Detection --------------- ----------------- Formålet med en feildeteksjon teknikk er å gjøre det mulig for mottakeren av en melding som sendes gjennom en støyende (feil-innføring) kanal for å bestemme om meldingen er blitt ødelagt . For å gjøre dette, konstruerer senderen en verdi (kalt en checksum) som er en funksjon av meldingen, og legger det i meldingen. Mottakeren kan deretter bruke den samme funksjonen for å beregne sjekksummen av den mottatte meldingen og sammenligne den med vedlagte sjekksummen for å se om meldingen ble mottatt korrekt. For eksempel, hvis vi velger en kontrollsum funksjon som var ganske enkelt summen av byte i meldingen mod 256 (dvs. modulo 256), så kan det gå noe som følger. Alle tall er i desimal
Melding:. 6 23 4 Meldings med sjekksum: 6 23 4 33 Message etter sending: 6 27 4 33
Ovenfor den andre byte av meldingen ble ødelagt 23-27 av kommunikasjonskanalen. Imidlertid kan mottakeren registrere dette ved å sammenligne den utsendte kontrollsummen (33) med datamaskin-kontrollsummen av 37 (6 + 27 + 4). Hvis sjekksummen selv er skadet, kan en korrekt overført melding bli feilaktig identifisert som en ødelagt en. Dette er imidlertid en sikker-side svikt. En farlig-sidesvikt opptrer der meldingen og /eller kontrollsum er ødelagt på en måte som resulterer i en overføring som er internt konsistent. Dessverre er denne muligheten helt uunngåelig, og det beste som kan gjøres er å minimere sannsynligheten ved å øke mengden av informasjon i sjekksum (f.eks utvide sjekksum fra en byte til to bytes).
Andre feildeteksjonsteknikker finnes som involvere utføre komplekse transformasjoner på meldingen for å injisere den med overflødig informasjon. Men løser dette dokumentet kun CRC algoritmer, som faller inn i klassen av feildeteksjon algoritmer som forlater data intakt og legge en sjekksum på slutten. dvs:
2. Behovet for Complexity -------------------------- I checksum eksempel i forrige avsnitt, vi så hvordan en skadet meldingen ble oppdaget ved hjelp av en sjekksum algoritme som bare summerer byte i meldingen mod 256:
melding: 6 23 4 meldings~~POS=TRUNC med sjekksum: 6 23 4 33 Message etter sending: 6 27 4 33
A problemet med denne algoritmen er at den er også enkel. Hvis et antall tilfeldige forfalskninger forekommer, er det en 1 i 256 sjanse for at de ikke vil bli registrert. For eksempel:
Melding: 6 23 4 Meldings med sjekksum: 6 23 4 33 Message etter sending: 8 20 5 33
å styrke kontrollsummen, vi kunne endre fra en 8-bits register til en 16-bits register (dvs. summen byte mod 65536 stedet for mod 256) for å tilsynelatende redusere sannsynligheten for svikt fra 1/256 til 1/65536. Mens utgangspunktet en god idé, svikter det i dette tilfellet fordi formelen som brukes ikke er tilstrekkelig " tilfeldig "; med en enkel summering formel, påvirker hver innkommende byte omtrent bare én byte til summeringsregisteret uansett hvor stort det er. For eksempel, i det andre eksemplet ovenfor, kan summeringsregisteret være en megabyte bred, og feilen vil fortsatt gå ubemerket. Dette problem kan bare løses ved å erstatte den enkle summerings formel med et mer sofistikert formel som bevirker at hver innkommende byte for å ha en virkning på hele kontrollsum registeret.
Således ser vi at i det minste to sider er nødvendig for å danne en sterk sjekksum funksjon:
bREDDE:. et register bredde bredt nok til å gi en lav a-priori sannsynlighet for svikt (f.eks 32-bits gir et 1/2 ^ 32 sjanse for feil)
CHAOS: en formel som gir hver innspill byte potensial til å endre antall bits i registeret
Merk: begrepet " checksum ". ble antagelig brukt for å beskrive tidlige summeringsformler, men har nå tatt på en mer generell betydning som omfatter mer avanserte algoritmer som CRC seg. CRC algoritmer for å beskrives tilfredsstille den andre betingelsen veldig godt, og kan konfigureres til å operere med en rekke checksum bredder.
3. Grunntanken bak CRC Algoritmer ------------- -------------------------- Hvor kan vi gå i vår søken etter en mer kompleks funksjon enn å summere? Alle slags ordninger våren til sinnet. Vi kunne konstruere tabeller ved hjelp av sifrene i pi, eller hasj hver innkommende byte med alle bytes i registeret. Vi kunne selv holde en stor telefonkatalogen på nett, og bruke hver innkommende byte kombinert med register bytes å indeksere et nytt telefonnummer som ville bli den neste registerverdien. Mulighetene er ubegrensede
Men vi trenger ikke å gå så langt.; neste aritmetiske skritt tilstrekkelig. Mens tilsetningen er helt klart ikke er sterk nok til å danne en effektiv sjekksum, viser det seg at divisjonen er, så lenge divisor er omtrent like bred som kontrollsummen register.
Grunnleggende ideen av CRC-algoritmer er ganske enkelt å behandle meldingen som et enormt binært tall, for å dele det ved en annen fast binært tall, og for å gjøre resten fra denne divisjon sjekksummen. Ved mottak av melding, kan mottakeren utfører samme divisjon og sammenligne resten med " checksum " (Overført rest)
. Eksempel: Anta at melding besto av de to bytes (6,23) som i det foregående eksempel. Disse kan anses å være det heksadesimale tall 0617, som kan anses å være det binære tall 0000-0110-0001-0111. Anta at vi bruker en checksum registrere en byte bred og bruke en konstant divisor av 1001, deretter sjekksummen er resten etter 0000-0110-0001-0111 er delt av 1001. Mens i dette tilfellet, kan denne beregningen åpenbart utføres ved hjelp felles hage rekke 32-bits registre, i det generelle tilfellet dette er rotete. Så i stedet, vil vi gjøre delingen ved hjelp av god-'ol lange divisjon som du lærte på skolen (husker du?). Bortsett fra denne gangen, er det i binær.
... 0000010101101 = 00AD = 173 = QUOTIENT ____-___-___-___- 9 = 1001) 0000011000010111 = 0617 = 1559 = UTBYTTE DIVISOR 0000 ,, ...., . ,,, ----. ,, ....,. ,,, 0000 ,, ....,. ,,, 0000 ,, ....,. ,,, ---- ,, ....,. ,,, 0001, ....,. ,,, 0000, ....,. ,,, ----, ....,. ,,, 0011 .... ,. ,,, 0000 ....,. ,,, ----....,. ,,, 0110 ...,. ,,, 0000 ...,. ,,, ---- ..., ,,, 1100 .., ,,, 1001 .., ,,, ==== .., ,,, 0110, ,,, 0000, ,,,........ - ---.,. ,,, 1100,. ,,, 1001,. ,,, ====,. ,,, 0111. ,,, 0000. ,,, ----. ,,, 1110, ,, 1001 ,,, ==== ,,, 1011 ,, 1001 ,, ==== ,, 0101, 0000, ---- 1011 1001 ==== 0010 = 02 = 2 = RESTEN
In desimal dette er " 1559 delt på 9 er 173 med en rest på 2 ".
Selv om effekten av hver bit av input melding på kvotienten er ikke alle som signifikant, blir det fire-bits resten sparket om ganske mye i løpet av beregningen, og hvis flere byte ble lagt til meldingen (utbytte) det er verdi kan endre seg radikalt igjen svært raskt. Dette er grunnen Avdelingen arbeider hvor tillegg ikke
I tilfelle du lurer på, ved hjelp av denne 4-bit sjekksum den sendte meldingen vil se slik ut (i heksadesimal). 06172 (der 0617 er budskapet og 2 er sjekksummen). Mottakeren ville dele 0617 med 9 og se om resten var 2.
4. Polynomical aritmetiske ------------------------- Mens divisjon ordningen er beskrevet i forrige avsnitt er svært lik den checksumming ordninger som kalles CRC ordninger, CRC ordninger er faktisk litt sprøere, og vi trenger å gå i dybden av noen merkelige tallsystemer for å forstå dem.
ordet du vil høre hele tiden når du arbeider med CRC algoritmer er ordet " polynom ". En gitt CRC algoritme vil bli sagt å være å bruke en bestemt polynom, og CRC algoritmer generelt sies å være i drift ved hjelp av polynom aritmetikk. Hva betyr dette?
Stedet for divisor, utbytte (melding), kvotient, og resten (som beskrevet i forrige avsnitt) blir sett på som positive heltall, blir de sett på som polynomer med binære koeffisienter. Dette gjøres ved å behandle hvert nummer som en bit-streng hvis bit er koeffisientene til et polynom. For eksempel, den ordinære nummer 23 (desimal) er 17 (hex) og 10111 binær og så det tilsvarer polynomet:
1 * x ^ 4 + 0 * x ^ 3 + 1 * x ^ 2 + 1 * x ^ 1 + 1 * x ^ 0
eller ganske enkelt:
x ^ 4 + x ^ 2 + x ^ 1 + x ^ 0
Ved hjelp av denne teknikken, meldingen og divisor kan representeres som polynomer og vi kan gjøre all vår regning like før, bortsett fra at nå er det alt fylt opp med Xs. For eksempel at vi ønsket å multiplisere 1101 av 1011. Vi kan gjøre dette ganske enkelt ved å multiplisere polynomer: product: (x ^ 3 + x ^ 2 + x ^ 0) (x ^ 3 + x ^ 1 + x ^ 0 ) = (x ^ 6 + x ^ 4 + x ^ 3 + x ^ 5 + x ^ 3 + x ^ 2 + x ^ 3 + x ^ 1 + x ^ 0) = x ^ 6 + x ^ 5 + x ^ 4 + 3 * x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0
på dette punktet, for å få det rette svaret, må vi late som om x er 2 og forplante binære bærer fra 3 * x ^ 3 givende
x ^ 7 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0
det er akkurat som vanlig aritmetikk, bortsett fra at basen er abstrahert og brakt inn i alle beregningene eksplisitt i stedet for å være der implisitt . Så hva er poenget?
Poenget er at hvis vi later som vi ikke vet hva x er, kan vi ikke utføre bærer. Vi vet ikke at 3 * x ^ 3 er det samme som x ^ 4 + x ^ 3, fordi vi ikke vet at x er 2. I dette sant polynom aritmetiske forholdet mellom alle koeffisientene er ukjent og så koeffisientene av hver makt effektivt blitt sterkt skrevet; koeffisientene til x ^ 2 er effektivt av en annen type til koeffisientene til x ^ 3.
Med koeffisientene hver makt pent isolerte, matematikere kom opp med alle slags forskjellige typer polynom aritmetikk bare ved å endre reglene om hvordan koeffisientene arbeid. Av disse ordningene, er en særlig relevant her, og det er et polynom aritmetikk der koeffisientene er beregnet MOD to og det er ingen bære; alle koeffisientene må være enten 0 eller 1, og ingen bærer beregnes. Dette kalles " polynom aritmetikk mod 2 ". Dermed går tilbake til tidligere eksempel: product: (x ^ 3 + x ^ 2 + x ^ 0) (x ^ 3 + x ^ 1 + x ^ 0) = (x ^ 6 + x ^ 4 + x ^ 3 + x ^ 5 + x ^ 3 + x ^ 2 + x ^ 3 + x ^ 1 + x ^ 0) = x ^ 6 + x ^ 5 + x ^ 4 + 3 * x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0
Under den andre aritmetikk, ble 3 * x ^ 3 sikt spredd ved hjelp av bæremekanismen ved hjelp av kunnskap at x = 2. Under " polynom aritmetikk mod 2 ", vet vi ikke hva x er, er det ingen bærer, og alle koeffisientene må beregnes mod 2. Dermed blir resultatet:
= x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0
Som Knuth [Knuth81] sier (p.400):
" leseren bør merke seg likheten mellom polynom aritmetikk og flere presisjon aritmetikk (avsnitt 4.3.1), hvor den radix b er substituert for x. Den viktigste forskjellen er at koeffisienten u_k av x ^ k i polynom aritmetikk bærer lite eller ingen relasjon til sine naboland koeffisienter x ^ {k-1} [og x ^ {k + 1}], så ideen om " frakte " fra ett sted til et annet er fraværende. Faktisk polynom aritmetikk modulo b er i hovedsak identisk med flere presisjon aritmetikk med Radix b, bortsett fra at alle bærer undertrykkes ".
Dermed polynomical aritmetikk mod 2 er bare binære aritmetiske mod 2 uten bærer. Mens polynomer gi nyttig matematisk maskiner i flere analytiske tilnærminger til CRC og feilkorrigering algoritmer, i forbindelse med utstillingen gir de ingen ekstra innsikt og noen heftelser og har blitt forkastet i resten av dette dokumentet til fordel for direkte manipulasjon av aritmetisk system som de er isomorfe: binær aritmetikk uten carry
5. Binary Arithmetic med Ingen bærer ----------------------------. -------- Etter å ha avviklet polynomer, kan vi fokusere på den virkelige aritmetiske problemet, som er at alle aritmetiske utført i løpet av CRC beregninger er utført i binær uten bærer. Ofte kalles polynom aritmetikk, men som jeg har erklært resten av dette dokumentet et polynom fri sone, må vi kalle det CRC aritmetiske stedet. Ettersom dette aritmetikk er en viktig del av CRC beregninger, vil vi bedre blir vant til det. Here we go:
Legge to tall i CRC aritmetiske er det samme som å legge til numre i vanlig binær aritmetikk bortsett fra det er ingen bære. Dette betyr at hvert par av tilsvarende biter bestemme den tilsvarende utgangs bit uten henvisning til andre bitposisjoner. For eksempel:
10011011 +11001010 -------- 01010001 --------
Det er bare fire tilfeller for hver bit posisjoner:
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 (ingen carry)
subtraksjon er identisk:
10011011 -11001010 -------- 01010001 --------
med
0-0 = 0 0-1 = 1 (buede) 1-0 = 1 1-1 = 0
faktisk både addisjon og subtraksjon i CRC aritmetikk er ekvivalent med eksklusiv eller-operasjonen, og XOR-operasjon er sin egen invers. Dette reduserer effektivt driften av det første nivået av strøm (addisjon, subtraksjon) til en enkel operasjon som er sin egen invers. Dette er en veldig praktisk egenskap ved aritmetikk.
Ved skjuling av addisjon og subtraksjon, forkaster den aritmetiske noen forestilling om omfanget utover kraften i sitt høyeste en bit. Selv om det synes klart at 1010 er større enn 10, er det ikke lenger slik at 1010 kan anses å være større enn 1001. For å se dette, merk at du kan få 1010-1001 av både legge til og trekke den samme mengde:
1010 = 1010 + 0011 1010 = 1010 -. 0011
Dette gjør tull av noen forestilling om pålegg
ha definert tillegg kan vi flytte til multiplikasjon og divisjon. Multiplikasjon er helt grei, blir summen av det første tallet, flyttet i samsvar med det andre tallet.
1101 x 1011 ---- 1101 1101. 0000 .. 1101 ... ------- 1.111.111 Note : summen bruker CRC tillegg -------
Division er litt Messier som vi trenger å vite når " en rekke går inn i et annet nummer ". For å gjøre dette, påkalle vi den svake definisjonen av omfanget definert tidligere: at X er større enn eller lik Y iff posisjonen til det høyeste en bit av X er den samme eller større enn posisjonen til det høyeste en bit av Y. tur et fullt jobbet divisjon (bretter fra [Tanenbaum81]).
1100001010 _______________ 10011) 11010110110000 10011 ,,. ,, .... ----- ,,. ,, .... 10011,. ,,. ... 10 011,. ,, .... -----,. ,, .... 00001. ,, .... 00000. ,, .... -----. ,,. ... 00010 ,, .... 00000 ,, .... ----- ,, .... 00101 .... 00000, .... -----, .... 01011 .... 00000 .... -----.... 10110 ... 10011 ... -----... 01010 .. 00000 .. ----- .. 10100. 10011. -----. 01110 00000 ----- 1110 = Rest
Det er egentlig det. Før du fortsetter videre, men det er verdt vår mens du spiller med denne aritmetikk litt å bli vant til det.
Vi har allerede spilt med addisjon og subtraksjon, merker at de er de samme. Her, skjønt, bør vi være oppmerksom på at i dette regne A + 0 = A og A-0 = A. Denne åpenbare egenskapen er veldig nyttig senere.
I håndteringen av CRC multiplikasjon og divisjon, er det verdt å få en følelse for begrepene FLERE og delelig.
Hvis et nummer A er et multiplum av B da hva dette betyr i CRC aritmetikk er at det er mulig å konstruere en fra null ved XORing i ulike skift av B. for eksempel, hvis A var 0111010110 og B var 11, kan vi konstruere A fra B som følger:
0111010110 = ..... ..11. + .... 11 .... + ... 11 ..... ....... 0,11
Imidlertid, hvis A er 0111010111, er det ikke mulig å konstruere den ut av forskjellige forskyvninger av B (kan du se hvorfor - se senere) så det er sagt å være ikke delelig med B i CRC aritmetiske
Dermed ser vi at CRC aritmetiske er først og fremst om XORing bestemte verdier på ulike skiftende forskyvninger
6.. . en Fullt Jobbet Eksempel ------------------------- ha definert CRC aritmetikk, kan vi nå ramme en CRC beregning som rett og slett en divisjon, fordi det er alt Det er! Denne delen fyller i detaljene, og gir et eksempel.
Å utføre en CRC beregning, må vi velge en divisor. I matematikk markedsføring snakke divisor kalles " generatorpolynom " eller bare " polynom ", og er en viktig parameter for ethvert CRC algoritme. Det ville trolig være mer vennlig å ringe divisor noe annet, men poly talk er så dypt inngrodd i feltet at det nå ville være forvirrende å unngå det. Som et kompromiss, vil vi referere til CRC polynom som " poly ". Bare tenk på dette tallet som en slags papegøye. &Quot; Hei poly "
Du kan velge hvilken som helst poly og komme opp med en CRC algoritme. Men noen polys er bedre enn andre, og så det er lurt å holde fast med de prøvde seg med en testet seg. En senere avsnitt løser dette problemet.
Bredde (posisjon på det høyeste en bit) av poly er svært viktig fordi det dominerer hele beregningen. Typisk blir en bredde på 16 eller 32 valgt slik at for å forenkle implementeringen på moderne datamaskiner. Bredden av en poly er den aktuelle bit posisjonen til største bit. For eksempel er bredden av 10 011 4, ikke 5. Ved anvendelse av eksempel, vil vi velge en poly av 10011 (av bredde W på 4).
Etter å ha valgt en poly, kan vi fortsette med beregningen. Dette er bare en avdeling (i CRC aritmetisk) av meldingen ved poly. Det eneste trikset er at W null biter er vedlagt meldingen før CRC beregnes. Dermed har vi:
Original melding: 1101011011 Poly: 10011 Message etter føye W nuller: 11010110110000
Nå er vi rett og slett dele den utvidede meldingen av poly hjelp CRC aritmetikk. Dette er den samme divisjon som før.
1100001010 = Quotient (ingen bryr seg om kvotienten) _______________ 10011) 11010110110000 = Augmented melding (1101011011 + 0000) = Poly 10011 ,, ,, .... ----- ,,. ,, .... 10011,. ,, .... 10011,. ,, .... -----,. ,, .... 00001. ,, .... 00000. ,, .... -----. ,, .... 00010 ,, .... 00000 ,, .... ----- ,, .... 00101 .... 00000 , .... -----, .... 01011 .... 00000 .... -----.... 10110 ... 10011 ... -----... 01010 .. 00000 .. ----- .. 10100. 10011. -----. 01110 00000 ----- 1110 = Rest = sjekksum !!!!
divisjon gir en kvotient, som vi kaster, og en rest, som er beregnet sjekksum. Dette avslutter beregningen.
Vanligvis er checksum deretter legges til meldingen, og resultatet overføres. I dette tilfellet overføringen vil være: 11010110111110.
I den andre enden, kan mottakeren gjøre en av to ting:
en. Skill meldingen og sjekksummen. Beregn sjekksummen for meldingen (etter føye W nuller) og sammenligne de to kontrollsummer.
B. Checksum hele mye (uten å føye til nuller) og se om det kommer ut som null!
Disse to alternativene er likeverdige. Men i neste avsnitt, vil vi være forutsatt alternativ b fordi det er marginalt matematisk renere, En oppsummering av driften av klassen av CRC algoritmer.
1. Velg en bredde W, og en poly G ( av bredde W). 2. Tilføy W null biter til meldingen. Kall dette M '. 3. Divide M 'av G hjelp CRC aritmetikk. Resten er sjekksummen.
Det er alt som skal til.
7. Velge en Poly ------------------ Velge en poly er litt av en svart kunst og leseren blir referert til [Tanenbaum81] (p.130-132) som har en veldig klar diskusjon om dette problemet. Denne delen bare har som mål å sette frykten for døden til alle som så mye som leker med ideen om å gjøre opp sin egen poly. Hvis du ikke bryr seg om hvorfor en poly kan være bedre enn en annen, og bare ønsker å finne ut om høyhastighets-implementeringer, velg en av de arithmetically lyd polys oppført på slutten av denne delen og hoppe til neste avsnitt.
Først oppmerksom på at den sendte meldingen T er et multiplum av poly. For å se dette, være oppmerksom på at 1) de siste W biter av T er resten etter å dividere forsterket (ved nuller husker) melding av poly, og 2) tilsetningen er den samme som subtraksjon så tilsetning av resten skyver verdi opp til neste multiplum. Nå oppmerksom på at dersom den overførte meldingen er ødelagt i overførings at vi vil motta T + E hvor E er en feil vektor (og + er CRC tillegg (dvs. XOR)). Ved mottak av denne meldingen, deler mottakeren T + E av G. Som T mod G er 0, (T + E) mod G = E mod G. således kapasiteten av poly vi velger å fange visse typer feil vil bestemmes av settet med multipler av G, til en hvilken som helst korrupsjon E som er et multiplum av G vil være ubemerket. Vår oppgave er da å finne klasser av G hvis multipler ser så lite som en slags linjestøy (som skal lage forfalskninger) som mulig. Så la oss undersøke hva slags linjestøy vi kan forvente
eneste bit FEIL. En enkelt bitfeil betyr E = 1000 ... 0000. Vi kan sikre at denne klasse av feil blir alltid oppdaget at ved å sørge for at G har minst to bits satt til 1. Alle multiplum av G blir konstruert ved hjelp av forskyvning, og å tilsette, og det er umulig å konstruere en verdi med en enkelt bit av skiftende en legger til en enkelt verdi med mer enn én bit sett, som de to kantskjær vil alltid vedvare
tO-bIT fEIL:. for å oppdage alle feil på formen 100 ... 000 100 ... 000 (dvs. E inneholder to 1 bit) velger en G som ikke har multipler som er 11, 101, 1001, 10001, 100001, etc. det er ikke klart for meg hvordan man går om du gjør dette (jeg har ikke den rene matematikk bakgrunnen), men Tanenbaum forsikrer oss om at en slik G eksisterer, og siterer G med 1 bits (15,14,1) slått på som et eksempel på en G som ikke vil dele noe mindre enn en ... en der ... er 32767 nuller .
FEIL med et ulikt antall bits: Vi kan ta alle forfalskninger hvor E har et ulikt antall bits ved å velge en G som har et likt antall bits. For å se dette, merk at 1) CRC multiplikasjon er rett og slett XORing en konstant verdi i et register på ulike forskyvninger, 2) XORing er rett og slett en bit-flip drift, og 3) hvis du XOR en verdi med et likt antall bits i en registrere, oddness av antall 1 biter i registeret forblir invariant. Eksempel: Fra og med E = 111, forsøk på å snu alle tre biter til null ved gjentatt bruk av XORing i 11 på en av de to forskyvninger (dvs. " E = E XOR 011 " og " E = E XOR 110 ") dette er nesten isomorf med " glass tumblers " fest puslespill der du utfordre noen til å snu tre tumblers ved gjentatt bruk av driften av bla noen to. De fleste av de populære CRC polys inneholde et like antall 1 bits. (Merk: Tanenbaum sier mer spesifikt at alle feil med et ulikt antall bits kan bli fanget ved å lage G et multiplum av 11)
Burst Feil:. En burst error ser ut E = 000 ... 000 111 ... 11110000 ... 00. Det er, E består av nuller bortsett fra en kjøring av 1s sted inne. Dette kan omarbeides som E = (10000 ... 00) (1111111 ... 111) der det er z nuller i venstre del og n de i høyre del. Å fange feil av denne typen, vi bare sette den laveste bit av G til 1. Å gjøre dette sikrer at VENSTRE ikke kan være en faktor av G. Deretter så lenge G er bredere enn rett, vil feilen bli oppdaget. Se Tanenbaum for en klarere forklaring på dette; Jeg er litt uklar på dette. Merk: Tanenbaum hevder at sannsynligheten for et utbrudd av lengde større enn W komme gjennom er (0,5) ^ W
Det konkluderer avsnittet om den fine kunsten å velge polys
Enkelte populære polys er:.. 16 bits: | | | | | | | | | | | | | | 0xFF; | | | | | | | | | | | | | | | | | gå i stykker; gå i stykker;