Syklisk Retandancy Koder: Eksempel på gjennomføring

[dkace]

Hei,
Jeg har aldri programmert en kode i MC med CRC-kode, så jeg trenger din hjelp.
Anta at jeg har en μC som sjekker en bryter og om bryteren er på, så det høres en alarm.Nå skal denne μC kommunisere med en annen, utveksle adresser og stastus kontroll port.Hvordan implementerer jeg koden?Noen gode forslag til å forstå funksjonalitet, eller en god referanse for å lese?
Takk

D.

 

[geok]

Hei,

Wikipedia har alltid vært en god kilde.

Selvfølgelig er det den klassiske "smertefri Guide to Error Detection algoritmer"GeorgeEDIT: Attachment lastes opp.
Beklager, men du må logge inn for å vise dette vedlegget

 

[dkace]

beklager men jeg kan ikke laste ned.Det er et problem med koblingen
D.

 

[geok]

Jeg beklager, men om jeg kan laste ned vedlegget når du redigerer mitt innlegg, jeg kan ikke laste den ned etterpå.

Allikevel, her er hele dokumentet:

Den smerteløse Guide to Error Detection algoritmer-Del 1:
Code:

En smertefri GUIDE TIL CRC FEIL Gjenkjenningsmerknad algoritmer

==================================================

"Alt du vil vite om CRC algoritmer, men var redd

å be om frykter at feil i din forståelse kan være oppdaget. "Versjon: 3.

Dato: 19. august 1993.

Forfatter: Ross N. Williams.

Net: Ross (at) guest.adelaide.edu.au.

FTP: ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt

Firma: Rocksoft ^ tm Inc.

Snegl: 16 Lerwick Avenue, Hazelwood Park 5066, Australia.

Fax: 61 8 373-4911 (c / - Internode Systems Pty Ltd).

Telefon: 61 8 379-9217 (10am til 10pm Adelaide Australia tid).

Merk: "Rocksoft" er et varemerke for Rocksoft Pty Ltd, Australia.

Status: Copyright (C) Ross Williams, 1993.
Men tillatelsen

tildeles lage og distribuere ordrett eksemplarer av denne

dokumentet, forutsatt at denne informasjonen blokk og opphavsrett

varsel er inkludert.
I tillegg har C-kode moduler inkludert

i dette dokumentet er fullstendig public domain.

Takk Takk til Jean-loup Gailly (jloup (at) chorus.fr) og Mark Adler

(meg (at) quest.jpl.nasa.gov) som både bevis lese dette dokumentet

og plukket ut mange nits samt enkelte store fett bugs.Innholdsfortegnelse

-----------------

Abstract

1.
Innledning: Error Detection

2.
Behovet for Complexity

3.
Den grunnleggende ideen bak CRC algoritmer

4.
Polynomical aritmetiske

5.
Binær aritmetikk med Nei bærer

6.
Et fullt Jobbet Eksempel

7.
Velge en Poly

8.
En grei CRC Gjennomføring

9.
En tabell-Driven Gjennomføring

10.
En litt Mangled Tabell-Driven Gjennomføring

11.
"Reflekterte" Table-Driven implementeringer

12.
"Reversed" Polys

13.
Innledende og Final Verdier

14.
Definere algoritmer Absolutely

15.
En parametrisk modell for CRC algoritmer

16.
A Catalog of Parameter Stiller for Standards

17.
Implementering av modellen algoritme

18.
Roll ditt eget Tabell-Driven Gjennomføring

19.
Generere et søketabellnavn

20.
Sammendrag

21.
Rettelser

A. Ordliste

B. Referanser

C. Referanser jeg har oppdaget, men ikke ennå SightedAbstract

--------

Dette dokumentet forklarer CRCs (Syklisk Redundancy Codes) og deres

tabell-drevet implementeringer i full, presise detaljer.
Mye av

litteratur om CRCs, og spesielt på deres bord-drevne

implementeringer, er litt uklar (eller i det minste synes det for meg).

Dette dokumentet er et forsøk på å gi en klar og enkel no-nonsense

forklaring av CRCs og absolutt spiker ned alle detaljer i

driften av sine høyhastighets implementeringer.
I tillegg til dette,

Dette dokumentet inneholder en parametrisk modell CRC algoritme kalt

"Rocksoft ^ tm Model CRC algoritmen".
Modellen algoritme kan

parametrisk å oppføre seg som de fleste av CRC implementeringene rundt,

og det 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

av høyhastighets tabellen drevet implementasjoner, og sørge for et program

som genererer CRC søketabeller.1.
Innledning: Error Detection

--------------------------------

Målet med en feilmelding gjenkjenningsverktøy teknikk er å aktivere mottakeren av en

Meldingen formidles gjennom et støyende (feilfritt innføre) kanal til

avgjøre om meldingen er skadet.
For å gjøre dette,

transmitter konstruerer en verdi (kalles en kontrollsum) som en funksjon

i meldingen, og legger det til meldingen.
Mottakeren kan deretter

bruke samme funksjon for å beregne checksum av mottatt

melding, og sammenligne den med tilføyd kontrollsum for å se om

meldingen ble korrekt mottatt.
For eksempel, hvis vi velger en kontrollsum

funksjonen som var rett og slett summen av bytes i meldingen mod 256

(dvs. Módulo 256), så det kan gå noe som følger.
Alle tall

er i desimalformat.Melding: 6 23 4

Melding med checksum: 6 23 4 33

Melding etter overføringen: 6 27 4 33I ovenfor andre byte av meldingen ble ødelagt fra 23 til

27 av kommunikasjonskanal.
Men mottakeren kan oppdage

dette ved å sammenligne overført checksum (33) med datamaskinen

checksum av 37 (6 27 4).
Hvis checksum selv er korrupt, en

korrekt overført melding kan være feilaktig identifisert som et

ødelagt en.
Men dette er en trygg side fiasko.
En farlig side

svikt oppstår der meldingslageret og / eller checksum er skadet i en

måte som resulterer i en overføringshastighet som er internt konsistente.

Dessverre har denne muligheten er helt uunngåelig, og den beste

som kan gjøres er å redusere sin sannsynlighet ved å øke

mengden informasjon i checksum (f.eks utvide checksum fra

en byte til to bytes).Andre feil gjenkjenning teknikker eksisterer som innebærer å utføre komplekse

transformasjoner på meldingen for å injisere den med redundante

informasjon.
Men dette dokumentet adresser bare CRC algoritmer,

som faller inn i klassen av feil gjenkjenning algoritmer som forlater

data intakt og føyer en kontrollsum på slutten.
ie:<original intakt message> <checksum>2.
Behovet for Complexity

--------------------------

I checksum eksempel i forrige avsnitt, vi så hvordan en

ødelagt meldingen ble oppdaget ved hjelp av en checksum algoritme som bare

summer i byte i meldingen mod 256:Melding: 6 23 4

Melding med checksum: 6 23 4 33

Melding etter overføringen: 6 27 4 33Et problem med denne algoritmen er at det er for enkelt.
Hvis en rekke

tilfeldige corruptions oppstå, er det 1 i 256 sjanse for at de vil

ikke oppdages.
For eksempel:Melding: 6 23 4

Melding med checksum: 6 23 4 33

Melding etter overføringen: 8 20 5 33Å styrke checksum, vi kunne skifte fra en 8-bits register til

en 16-bits register (dvs. summen av bytes mod 65.536 istedenfor mod 256), slik

som tilsynelatende redusere sannsynligheten for svikt fra 1 / 256 til

1 / 65536.
Mens utgangspunktet en god idé, men ikke i dette tilfellet fordi

formelen brukes ikke er tilstrekkelig "tilfeldig", med en enkel summing

formel hver innkommende byte påvirker omtrent bare én byte av

summing register uansett hvor stort det er.
For eksempel, i den andre

eksemplet ovenfor er summing register kan være en megabyte stort, og

feil vil fortsatt gå undetected.
Dette problemet kan bare løses ved

erstatte enkle summing formel med en mer sofistikert formel

som forårsaker hver innkommende byte til å ha effekt på hele

checksum register.Således ser vi at minst to aspektene er nødvendige for å danne en sterk

checksum funksjon:WIDTH: Et register bredde stor nok til å gi en liten a-priori

Sannsynligheten for feil (for eksempel 32-bits gir en 1 / 2 ^ 32 sjanse

feilpunkter).Chaos: En formel som gir hver inngang byte potensial til å endre

et ubegrenset antall biter i register.Merk: Uttrykket "checksum" ble antakelig brukt for å beskrive tidlig

summing formler, men nå har tatt på en mer generell betydning

omfatter mer sofistikerte algoritmer som CRC seg.
Den, det

CRC algoritmer for å bli beskrevet tilfredsstille andre tilstand svært godt,

og kan konfigureres til å operere med en rekke checksum bredde.3.
Den grunnleggende ideen bak CRC algoritmer

---------------------------------------

Hvor kan vi gå på søk etter et mer sammensatt funksjon enn

summing?
Alle slags ordninger våren til sinnet.
Vi kan konstruere

tabeller ved hjelp av sifrene i pi eller hash hver innkommende byte med alle

bytes i register.
Vi kunne også ha en stor telefon bok

on-line, og bruker hver innkommende byte kombinert med register bytes

indeksere et nytt telefonnummer som ville bli den neste registrere verdi.

Mulighetene er ubegrensede.Men vi trenger ikke å gå så langt, neste aritmetiske trinn

tilstrekkelig.
Mens tillegg er åpenbart ikke sterk nok til å danne en

effektiv checksum, det viser seg at divisjon er, så lenge

divisor er omtrent like stort som checksum register.Den grunnleggende ideen om CRC algoritmer er ganske enkelt å behandle meldingen som en

enorme binære tall, for å dele den med en annen fast binære tall,

og å gjøre resten av denne divisjonen de kontrollsum.
Ved

mottak av meldingen, mottakeren kan utføre samme divisjon og

sammenligne resten med "checksum" (overført resten).Eksempel: Tenk at meldingen besto av to bytes (6,23) som

i forrige eksempel.
Disse kan betraktes som den heksadesimale

nummer 0617 som kan anses å være den binære tall

0000-0110-0001-0111.
Anta at vi bruker en kontrollsum registrere en byte

bred og bruke en konstant divisor av 1001, deretter checksum er

Resten etter 0000-0110-0001-0111 delt av 1001.
Selv i dette

tilfellet denne beregningen kan selvsagt utføres ved hjelp av felles

hage utvalg 32-bits registre, i det generelle tilfellet er rotete.
Så

stedet, vil vi gjøre divisjonen bruke god'ol lange divisjon som du

lært på skolen (husker du?).
Bortsett fra denne tiden er det i binær:... 0000010101101 = 00AD = 173 = QUOTIENT

____-___-___-___ -

9 = 1001) 0000011000010111 = 0617 = 1559 = UTBYTTE

Divisoren 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 = restenI desimalformat dette er "1559 fordelt på 9 173 med resten av 2».Selv om effekten av hver bit av inntastingslisten melding på quotient

er ikke alle som betydelig, den 4-bits resten blir kastet om

ganske mye i beregningen, og hvis flere bytes ble lagt til

meldingen (utbytte), er det verdien kan endres radikalt igjen meget

raskt.
Dette er grunnen divisjon arbeider der tillegg ikke.I tilfelle du lurer på, ved hjelp av denne 4-bits checksum det overført

meldingen vil se slik ut (i heksadesimal): 06172 (hvor 0617

er meldingen og 2 er checksum).
Mottakeren vil dele

0617 med 9 og se om resten var 2.4.
Polynomical aritmetiske

-------------------------

Mens divisjon ordningen beskrevet i forrige avsnitt er svært

ligner på checksumming ordninger kalles CRC ordninger, CRC

ordninger er faktisk litt sprøere, og vi må gå i dybden av noen

merkelig mange systemer for å forstå dem.Ordet du vil høre hele tiden når du arbeider med CRC algoritmer

er ordet "polynom.
En gitt CRC algoritmen skal sies å være

å bruke en bestemt polynom og CRC algoritmer generelt er sagt

skal operere ved hjelp polynom regning.
Hva betyr dette?I stedet for divisor, utbytte (melding), quotient, og resten

(som beskrevet i forrige avsnitt) som blir sett på som positivt

heltall, de blir sett på som polynomer med binære koeffisienter.

Dette gjøres ved å behandle hvert nummer som en bit-streng som biter er

den koeffisienter for et polynom.
For eksempel den ordinære nummer 23

(desimal) er 17 (hex) og 10111 binær og slik at den samsvarer med

polynom:1 * x ^ 4 0 * x ^ 3 1 * x ^ 2 1 * x ^ 1 1 * x ^ 0eller enklere:x ^ 4 x ^ 2 x ^ 1 x ^ 0Bruker denne teknikken, er meldingen, og divisor kan være representert

som polynomer og vi kan gjøre alle våre aritmetiske akkurat som før, bortsett

at nå er det all rotete opp med XS.
For eksempel at vi ønsket

å multiplisere 1101 av 1011.
Vi kan gjøre dette ved å multiplisere

polynomerx ^ 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 ^ 0På dette punktet for å få det rette svaret, må vi late som x 2

og spredd binærfilen bærer fra 3 * x ^ 3 girx ^ 7 x ^ 3 x ^ 2 x ^ 1 x ^ 0Det er akkurat som vanlige aritmetiske bortsett fra at basen er abstrahert

og kommer i alle beregningene eksplisitt stedet for å bli

det implisitt.
Så hva er vitsen?Poenget er at hvis vi late 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 koeffisienter er ukjent og at

koeffisienter for hver makt effektivt blitt sterkt skrevet;

koeffisientene til x ^ 2 er faktisk av en annen type til

koeffisientene til x ^ 3.Med koeffisienter for hver strøm pent isolert, matematikere

kom med alle slags forskjellige typer polynom arithmetics

bare ved å endre reglene om hvordan koeffisientene arbeid.
Av disse

ordninger, en særlig er relevant her, og det er et polynom

aritmetiske der koeffisientene beregnes MOD 2 og det er ingen

bære; alle koeffisientene må være enten 0 eller 1 og ingen bærer er

beregnes.
Dette kalles "polynom aritmetiske mod 2».
Derfor,

tilbake til den tidligere eksempelx ^ 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 ^ 0Under den andre aritmetikk, den 3 * x ^ 3 sikt ble propagated bruker

bære mekanisme bruke den kunnskapen som x = 2.
Under "polynom

aritmetiske mod 2 ", vi vet ikke hva x er, er det ingen bærer og

alle koeffisientene må beregnes mod 2.
Dermed blir resultatet

blir:= X ^ 6 x ^ 5 x ^ 4 x ^ 3 x ^ 2 x ^ 1 x ^ 0Som Knuth [Knuth81] sier (p.400):"The reader bør være oppmerksom på likheten mellom polynom

aritmetiske og flere presisjon aritmetikk (§ 4.3.1), der

den Radix b er substituert for x.
Sjefen Forskjellen er at

koeffisient u_k av x ^ k i polynom aritmetiske bjørner liten eller ingen

forhold til nabokommunene koeffisienter x ^ (k-1) [og x ^ (k 1)], så

ideen om å "bære" fra et sted til et annet er fraværende.
Faktisk

polynom aritmetiske Módulo b er i hovedsak identisk med flere

presisjon aritmetikk med Radix b, bortsett fra at alle bærer er

undertrykkes.Dermed polynomical aritmetiske mod 2 er bare binær aritmetikk mod 2 med

no bærer.
Mens polynomer gi nyttig matematiske maskineri i

mer analytiske tilnærminger til CRC og feil-korreksjon algoritmer for

I forbindelse med utstilling de gir ingen ekstra innsikt og noen

heftelse og har blitt forkastet i resten av dette dokumentet

i favør av direkte manipulasjon av arithmetical system som

de er isomorphic: binær regning uten bære.5.
Binær aritmetikk med Nei bærer

------------------------------------

Har dispensed med polynomer, kan vi fokusere på de virkelige aritmetiske

Problemet, som er at alle aritmetiske utført under CRC

Beregningene er utført i binær uten fører.
Ofte er dette

kalt polynom regning, men som jeg har erklært resten av denne

dokumentere et polynom fri sone, vil vi nødt til å kalle det CRC aritmetiske

i stedet.
Ettersom dette regning er en viktig del av CRC beregninger, vil vi

bedre blir vant til det.
Sånn:Legge to tall i CRC regning er det samme som å legge til tall i

ordinære binær aritmetikk unntatt det ikke er bære.
Dette betyr at

hvert par av tilsvarende biter bestemme tilsvarende output bit

uten referanse til andre bit stillinger.
For eksempel:10011011

11001010

--------

01010001

--------Det er bare fire saker for hver bit stilling:0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0 (ikke bære)Subtraksjon er identiske:10011011

-11001010

--------

01010001

--------med0-0 = 0

0-1 = 1 (wraparound)

1-0 = 1

1-1 = 0Faktisk, både addisjon og subtraksjon i CRC aritmetiske tilsvarer

til XOR operasjon, og XOR operasjonen sin egen invers.
Dette

effektivt reduserer driften av de første nivå av strøm

(addisjon, subtraksjon) til en operasjon som er sin egen invers.

Dette er en svært praktisk egenskap av aritmetikk.Ved skjuling av addisjon og subtraksjon, det aritmetiske forkaster alle

oppfatningen av omfanget utover kraft av sitt høyeste en bit.
Mens det

synes klart at 1010 er større enn 10, er det ikke lenger tilfelle

at 1010 kan anses å være større enn 1001.
For å se dette notatet

at du kan få fra 1010 til 1001 av både legge til og trekke fra

samme kvantum:1010 = 1010 0011

1010 = 1010 - 0011Dette gjør tull av noen forestilling om pålegg.Etter å ha definert tillegg kan vi gå til multiplikasjon og divisjon.

Multiplikasjon er helt grei, blir summen av

første tallet, flyttet i samsvar med andre tall.1101

x 1011

----

1101

1101.

0000 ..

1101 ...

-------

1111111 Merk: Summen bruker CRC tillegg

-------Divisjon er litt messier som vi trenger å vite når "et nummer går

til et annet nummer ". Dette gjør vi påberope seg svak definisjon av

størrelsesorden definert tidligere: at X er større enn eller lik Y IFF

plasseringen av de høyeste 1 bit av X er lik eller større enn

Plasseringen av den høyeste 1 bit av Y. Her er et fullt arbeidet divisjon

(nicked fra [Tanenbaum81]).1100001010

_______________

10011) 11010110110000

10011 ,,.,,....

-----,,.,,....

10011 ,.,,....

10011 ,.,,....

-----,.,,....

00001 .,,....

00000 .,,....

-----.,,....

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01.011 ....

00.000 ....

-----....

10.110 ...

10.011 ...

-----...

01.010 ..

00.000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = restenDet er virkelig det.
Før du fortsetter videre, men det er verdt vår

mens du spiller med denne aritmetiske litt å bli vant til det.Vi har allerede spilt med addisjon og subtraksjon, bemerker at de

er det samme.
Her, men vi bør være oppmerksom på at i denne

aritmetiske A 0 = A og A-0 = A.
Denne åpenbare egenskapen er svært nyttig

senere.I håndteringen av CRC multiplikasjon og divisjon, er det verdt å få et

føler for konsepter for flere og delelig.Hvis et tall A er et multiplum av B så hva dette betyr i CRC

aritmetiske er at det er mulig å lage en fra null ved XORing

i ulike skift av B. For eksempel, hvis A ble 0111010110 og B var 11,

vi kunne konstruere en fra B som følger:0111010110

= ....... 11.

.... 11 ....

... 11 .....

,11 .......Men hvis A er 0111010111, er det ikke mulig å bygge den ut av

forskjellige skift av B (kan du se hvorfor? - se senere), så det er sagt å være

ikke delelig med B i CRC regning.Således ser vi at CRC aritmetikk er primært om XORing bestemt

verdier i ulike skiftende forskyvninger.6.
Et fullt Jobbet Eksempel

-------------------------

Etter å ha definert CRC aritmetikk, kan vi nå ramme en CRC utregning som

bare en divisjon, fordi det er alt det er!
Denne delen fylles i

detaljer, og gir et eksempel.Å utføre en CRC beregning, må vi velge en divisor.
I matematikk

markedsføring snakker divisoren kalles "generator polynom" eller

bare den "polynom", og er en viktig parameter for enhver CRC algoritme.

Det ville trolig bli mer vennlig å ringe divisoren noe annet,

men poly snakk er så dypt inngrodd i feltet at det ville

nå være forvirrende å unngå det.
Som et kompromiss, vil vi henvise til

CRC polynom som "poly".
Bare tenk på dette tallet som en slags

papegøye.
"Hei poly!"Du kan velge et poly og komme opp med en CRC-algoritmen.
Uansett, imidlertid,

noen polys er bedre enn andre, og derfor er det lurt å holde fast ved

prøvde en testet seg.
En nyere delen løser dette problemet.Bredden (plassering av høyeste 1 bit) av poly er svært

viktig som den dominerer hele regnestykket.
Vanligvis bredder av

16 eller 32, er valgt slik forenkle implementeringen på moderne

datamaskiner.
Bredden på en poly er faktisk litt plassering av

Største bit.
For eksempel er bredden av 10.011 er 4, ikke 5.
For

Ifølge eksempel, vil vi valgte en poly av 10011 (av bredden W 4).Etter å ha valgt en poly, kan vi fortsette med regnestykket.
Dette er

bare en divisjon (i CRC aritmetikk) av meldingen av poly.
Den, det

bare lure er at W null bitene legges til meldingen før

CRC beregnes.
Dermed har vi:Opprinnelig melding: 1101011011

Poly: 10011

Melding etter at du har lagt W nuller: 11010110110000Nå er vi bare dele utvidet melding av poly bruker CRC

regning.
Dette er samme inndeling som før:1100001010 = Quotient (ingen bryr seg om quotient)

_______________

10011) 11010110110000 = Augmented melding (1101011011 0000)

= Poly 10.011 ,,.,,....

-----,,.,,....

10011 ,.,,....

10011 ,.,,....

-----,.,,....

00001 .,,....

00000 .,,....

-----.,,....

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01.011 ....

00.000 ....

-----....

10.110 ...

10.011 ...

-----...

01.010 ..

00.000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = resten = THE checksum!Avdelingen gir en quotient, som vi kaster bort, og resten,

som er beregnet kontrollsum.
Dette ender regnestykket.Vanligvis er det checksum deretter legges til meldingen, og resultatet

overført.
I dette tilfellet overføring ville være: 11010110111110.I den andre enden, mottakeren kan gjøre én av to ting:a.
Skill meldingen og kontrollsum.
Beregne sjekksummen for

meldingen (etter at du har lagt W nuller), og sammenlign de to

kontrollsummer.b.
Checksum hele mye (uten å legge nuller) og se om det

kommer ut som null!Disse to alternativene er likeverdige.
Men i neste avsnitt, vi

vil bli forutsatt alternativ b fordi det er marginalt matematisk

støvsugeren.En oppsummering av driften av klassen av CRC algoritmer:1.
Velg en bredde W, og en poly G (av bredden W).

2.
Føyer W null biter til meldingen.
Kall dette M '.

3.
Dividere M "av G bruker CRC regning.
Resten er kontrollsum.Det er alt som skal til.7.
Velge en Poly

------------------

Velge en poly er litt av en svart kunst og leseren er henvist

til [Tanenbaum81] (p.130-132) som har en veldig klar diskusjon av denne

utgave.
Denne delen bare som mål å sette frykten for døden i noen

som så mye som leker med tanken om å gjøre opp sin egen poly.
Hvis du

ikke bryr seg om hvorfor en poly kan være bedre enn en annen og like

vil finne ut om høyhastighets implementeringer, velge ett av

arithmetically lyd polys oppført på slutten av denne delen, og hopper

til neste avsnitt.Først oppmerksom på at overført melding T er flere av poly.

For å se dette oppmerksom på at 1) den siste W biter av T er resten etter

dele utvidet (av nuller husker) melding av poly, og 2)

Dessuten er det samme som å trekke så legge resten skyver den

verdi opp til neste flere.
Nå oppmerksom på at hvis overført

meldingen er skadet i overføring at vi får T E der E

er en feil vektor (og er CRC tillegg (dvs. XOR)).
Ved mottakelse av

denne meldingen, mottakeren dividerer T E av G. Som T mod G 0, (T E)

mod G = E mod G. altså kapasiteten på poly vi velger å ta

bestemte typer feil vil være bestemt av antall Combi

av G, for korrupsjon E som er et multiplum av G vil undetected.

Vår oppgave da er å finne klasser G som Combi ser så lite

liker den slags linje støy (som skal skape corruptions) som

mulig.
Så la oss undersøke slags linje støy vi kan forvente.ENKELT BIT FEIL: En enkelt bit feil betyr E = 1000 ... 0000.
Vi kan

sikre at denne type feil er alltid oppdages av at

G har minst to bits satt til 1.
Noen flere av G vil bli

konstrueres ved hjelp av skiftende og legge til, og det er umulig å

konstruere en verdi med en enkelt bit av skiftende en legge en enkelt

verdi med mer enn én bit satt, ettersom to biter vil alltid

vedvarer.To BIT FEIL: Hvis du vil oppdage alle feil på formen 100 ... 000100 ... 000

(dvs. E inneholder to 1 bits) velger en G som ikke har Combi

som er 11, 101, 1001, 10001, 100001, etc. Det er ikke klart for meg hvordan

en går om å gjøre dette (jeg har ikke den rene matematikk bakgrunnen)

men Tanenbaum sikrer oss at slike G finnes, og trekker G med 1 bit

(15,14,1) slått på som et eksempel på en G som ikke vil dele noe

mindre enn 1 ... 1 der ...
er 32.767 nuller.Feil med et odde antall BITS: Vi kan fange alle corruptions der

E har et odde antall biter med å velge en G som har et likt antall

biter.
For å se dette oppmerksom på at 1) CRC multiplikasjon er bare XORing en

konstant verdi i et register ved ulike forskyvninger, 2) XORing er ganske enkelt

en bit-flip operasjon, og 3) hvis du XOR verdien med et likt antall

biter i et register, vil oddness antall 1 biter i

register forblir invariant.
Eksempel: Starter med E = 111, forsøk å

snu alle tre biter til null ved gjentatt bruk av XORing i

11 på ett av de to forskyvninger (dvs. "E = E XOR 011" og "E = E XOR 110")

Dette er nesten isomorphic til "glass tumblers" party puslespillet der

du utfordre noen til å snu tre tumblers ved gjentatt

anvendelsen av driften av bla to.
De fleste av de populære

CRC polys inneholde et likt antall 1 biter.
(Merk: Tanenbaum stater

mer spesifikt at alle feil med et odde antall biter kan

fanget ved å gjøre G et multiplum av 11).Burst FEIL: A burst feilen ligner E = 000 ... 000111 ... 11110000 ... 00.

Det er E består av alle nuller unntatt for kjøring av 1s sted

innsiden.
Dette kan være recast som E = (10000 ... 00) (1111111 ... 111) der

det er z nuller i venstre del og n seg i høyre del.
Til

catch feil av denne typen, vi bare sett den laveste bit av G til 1.

Gjøre dette sikrer at LEFT kan ikke være en faktor på G. Så, så lenge

G er større enn høyre feilen blir oppdaget.
Se Tanenbaum for en

tydeligere beskrivelse av dette, jeg er litt uklar på dette.
Merk:

Tanenbaum hevder at sannsynligheten for en serie av lengden større

enn W komme gjennom (0,5) ^ W.Det konkluderer seksjonen på den fine kunsten å velge polys.Enkelte populære polys er:

16 biter: (16,12,5,0) [x25 standard]

(16,15,2,0) [ "CRC-16"]

32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]8.
En grei CRC Gjennomføring

---------------------------------------

Dette er slutten av teorien; nå vi slå til implementeringer.
Hvis du vil starte

med, kan vi undersøke et absolutt rett-ned-det-midt kjedelig

ukomplisert lav hastighet implementering som bruker ikke fart

triks i det hele tatt.
Vi vil deretter transformere det programmet progessively til vi

ende opp med den kompakte tabell-drevet vi alle kjenner og elsker og

som noen av oss ønsker å forstå.Å implementere en CRC algoritmen alt vi trenger å gjøre er å iverksette CRC

divisjon.
Det er to grunner til at vi kan ikke bare bruke dividere

instruksjon av hva maskinen er på.
Den første er at vi har

til å gjøre skillet i CRC regning.
Det andre er at utbytte

kanskje ti megabyte lang, og dagens prosessorer ikke har

registrerer at store.Så å implementere CRC divisjon, må vi feed meldingen gjennom en

divisjon register.
På dette punktet, må vi være helt presis

om meldingen data.
I alle disse eksemplene meldingen

anses å være en strøm av bytes (hver på 8 biter) med litt 7 av

hver byte som vurderes å være den mest betydningsfulle bit (MSB).
Den, det

bit stream dannet fra disse bytes blir det litt strøm med MSB

(bit 7) av første byte først, går ned til bits 0 av første

byte, og deretter MSB av andre byte og så videre.Med dette i bakhodet, kan vi skissere en implementering av CRC

divisjon.
For å eksempel vurdere en poly med W = 4 og

de poly = 10111.
Deretter kan de utføre divisjon, må vi bruke en 4-bits

register:3 2 1 0 Bits

--- --- --- ---

Pop!
<- | | | | | <----- Augmented melding

--- --- --- --- 1 0 1 1 1 = Den Poly(Påminnelse: The Augmented melding meldingen fulgt av W null biter.)Å utføre divisjon utføre følgende:Legg register uten biter.

Utfylle meldingen ved å legge W null biter til slutten av det.

Mens (mer melding bits)

Begynne

Skift registeret etter en bit, lese neste bit av

Augmented melding til register bit posisjon 0.

Hvis (a 1 bit popped ut av register i trinn 3)

Registrer = Registrer XOR Poly.

Slutt

Registeret inneholder nå resten.(Merk: I praksis er IF tilstand kan testes ved å teste toppen

bit av R før utfører skift.)Vi vil kalle denne algoritmen "kortidsleie.Dette kan se litt rotete, men alle er vi egentlig gjør er

"trekke" ulike maktene (dvs. shiftings) av poly fra

melding før det er ingenting igjen, men resten.
Studer

manuell eksempler på lang divisjon hvis du ikke forstår dette.Det burde være klart at over algoritmen vil fungere for alle width W.9.
En tabell-Driven Gjennomføring

--------------------------------

Den enkle algoritmen ovenfor er et godt utgangspunkt, fordi det

svarer direkte til teorien presentert så langt, og fordi det er

Så enkelt.
Men fordi det opererer på bit-nivå, er det heller

klosset til koden (selv i C), og ineffektivt å kjøre (det må

loop gang for hver bit).
Å øke den opp, må vi finne en måte å

aktivere algoritme til å behandle meldingen i enheter som er større enn en

bit.
Kandidat mengdene er nibbles (4 biter), byte (8 bit), ord

(16 bits) og longwords (32 bits) og høyere hvis vi kan få det til.
Av

these, 4 bits is best avoided because it does not correspond to a byte
boundary. At the very least, any speedup should allow us to operate at
byte boundaries, and in fact most of the table driven algorithms
operate a byte at a time.

For the purposes of discussion, let us switch from a 4-bit poly to a
32-bit one. Our register looks much the same, except the boxes
represent bytes instead of bits, and the Poly is 33 bits (one implicit
1 bit at the top and 32 "active" bits) (W=32).

3    2    1    0   Bytes
---- ---- ---- ----
Pop! <-- |    |    |    |    | <----- Augmented message
---- ---- ---- ----

1<------32 bits------>

The SIMPLE algorithm is still applicable. Let us examine what it does.
Imagine that the SIMPLE algorithm is in full swing and consider the
top 8 bits of the 32-bit register (byte 3) to have the values:

t7 t6 t5 t4 t3 t2 t1 t0

In the next iteration of SIMPLE, t7 will determine whether the Poly
will be XORed into the entire register. If t7=1, this will happen,
otherwise it will not. Suppose that the top 8 bits of the poly are g7
g6.. g0, then after the next iteration, the top byte will be:

t6 t5 t4 t3 t2 t1 t0 ??
t7 * (g7 g6 g5 g4 g3 g2 g1 g0)    [Reminder: is XOR]

The NEW top bit (that will control what happens in the next iteration)
now has the value t6 t7*g7. The important thing to notice here is
that from an informational point of view, all the information required
to calculate the NEW top bit was present in the top TWO bits of the
original top byte. Similarly, the NEXT top bit can be calculated in
advance SOLELY from the top THREE bits t7, t6, and t5. In fact, in
general, the value of the top bit in the register in k iterations can
be calculated from the top k bits of the register. Let us take this
for granted for a moment.

Consider for a moment that we use the top 8 bits of the register to
calculate the value of the top bit of the register during the next 8
iterations. Suppose that we drive the next 8 iterations using the
calculated values (which we could perhaps store in a single byte
register and shift out to pick off each bit). Then we note three
things:

* The top byte of the register now doesn't matter. No matter how
many times and at what offset the poly is XORed to the top 8
bits, they will all be shifted out the right hand side during the
next 8 iterations anyway. * The remaining bits will be shifted left one position and the
rightmost byte of the register will be shifted in the next byte

AND

* While all this is going on, the register will be subjected to a
series of XOR's in accordance with the bits of the pre-calculated
control byte.

Now consider the effect of XORing in a constant value at various
offsets to a register. For example:

0100010  Register
...0110  XOR this
..0110.  XOR this
0110...  XOR this
-------
0011000
-------

The point of this is that you can XOR constant values into a register
to your heart's delight, and in the end, there will exist a value
which when XORed in with the original register will have the same
effect as all the other XORs.

Perhaps you can see the solution now. Putting all the pieces together
we have an algorithm that goes like this:

While (augmented message is not exhausted)
Begin
Examine the top byte of the register
Calculate the control byte from the top byte of the register
Sum all the Polys at various offsets that are to be XORed into
the register in accordance with the control byte
Shift the register left by one byte, reading a new message byte
into the rightmost byte of the register
XOR the summed polys to the register
End

As it stands this is not much better than the SIMPLE algorithm.
However, it turns out that most of the calculation can be precomputed
and assembled into a table. As a result, the above algorithm can be
reduced to:

While (augmented message is not exhaused)
Begin
Top = top_byte(Register);
Register = (Register << 24) | next_augmessage_byte;
Register = Register XOR precomputed_table[Top];
End

There! If you understand this, you've grasped the main idea of
table-driven CRC algorithms. The above is a very efficient algorithm
requiring just a shift, and OR, an XOR, and a table lookup per byte.
Graphically, it looks like this:

3    2    1    0   Bytes
---- ---- ---- ----
-----<|    |    |    |    | <----- Augmented message
|      ---- ---- ---- ----
|                ^
|                |
|               XOR
|                |
|     0 ---- ---- ---- ----        Algorithm
v      ---- ---- ---- ----        ---------
|      ---- ---- ---- ----        1. Shift the register left by
|      ---- ---- ---- ----           one byte, reading in a new
|      ---- ---- ---- ----           message byte.
|      ---- ---- ---- ----        2. Use the top byte just rotated
|      ---- ---- ---- ----           out of the register to index
-----> ---- ---- ---- ----           the table of 256 32-bit values.
---- ---- ---- ----        3. XOR the table value into the
---- ---- ---- ----           register.
---- ---- ---- ----        4. Goto 1 iff more augmented
---- ---- ---- ----           message bytes.
255 ---- ---- ---- ---- In C, the algorithm main loop looks like this:

r=0;
while (len--)
{
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *p ;
r^=table[t];
}

where len is the length of the augmented message in bytes, p points to
the augmented message, r is the register, t is a temporary, and table
is the computed table. This code can be made even more unreadable as
follows:

r=0; while (len--) r = ((r << 8) | *p ) ^ t[(r >> 24) & 0xFF];

This is a very clean, efficient loop, although not a very obvious one
to the casual observer not versed in CRC theory. We will call this the
TABLE algorithm.