Ciklički kodovi Retandancy: Primjer primjene

[dkace]

Bok,
Nikad nisam programirane šifra u MC s CRC koda, tako da mi treba vaša pomoć.
Recimo da imam μC koja je provjeravanje prebaciti jedan prekidač i ako je on, onda to zvuci alarma.Sada ovaj μC komuniciraju jedna s drugom, razmjena adresa i stastus kontrole porta.Kako implementirati kod?Bilo koji dobar prijedlog da razumije funkcionalnost ili dobra referenca za čitanje?
Hvala

D.

 

[geok]

Bok,

Wikipedia je uvijek bio dobar izvor.

Naravno, tu je klasični "Vodič za bezbolan Error Detection Algorithms"GeorgeEDIT: Attachment ponovno učitali.
Žao nam je, ali morate prijaviti da biste vidjeli u ovom prilogu

 

[dkace]

Žao nam je ali ne mogu skinuti.Postoji problem s vezom
D.

 

[geok]

Žao mi je, ali ipak ne mogu preuzeti moja privitak prilikom uređivanja moj post, ja ne mogu skinuti poslije.

U svakom slučaju, ovdje je kompletan dokument:

The Guide to bezbolan Error Detection Algorithms-Part 1:
Code:

A bezbolan VODIČ ZA CRC otkrivanje pogrešaka algoritmi

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

"Sve što ste htjeli znati o CRC algoritme, ali usudiše

tražiti pogreške u strahu da na razumijevanju može biti otkrivena ".Verzija: 3.

Datum: 19. kolovoza 1993.

Autor: Ross N. Williams.

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

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

Tvrtka: Rocksoft ^ tm Pty Ltd

Puž: 16 Lerwick Avenue, Hazelwood park 5066, Australia.

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

Telefon: 61 8 379-9217 (10-10 Adelaide Australija vrijeme).

Napomena: "Rocksoft" je zaštitni znak tvrtke Rocksoft Pty Ltd, Australia.

Status: Copyright (C) Ross Williams, 1993.
Međutim, odobrenje se

odobreno da doslovno i distribuirati kopije ovog

dokument pod uvjetom da je ova informacija i autorska prava blok

obavijest je uključen.
Također, C koda modula uključeni

u ovom dokumentu su potpuno iz javne domene.

Thanks: Hvala na Jean-loup Gailly (jloup (at) chorus.fr) i Mark Adler

(me (at) quest.jpl.nasa.gov) i dokaz koji pročitate ovaj dokument

i pokupljeno iz puno gnjida kao i neke velike masnoće bugova.Table of Contents

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

Sažetak

1.
Uvod: detekcija pogrešaka

2.
Potreba za Složenost

3.
Osnovna ideja CRC Algoritmi

4.
Polynomical aritmetika

5.
Binarna aritmetika s Ne nosi

6.
Potpuno Radila Primjer

7.
Odabir Poly

8.
CRC jednostavan za implementaciju

9.
Stol-Driven Implementacija

10.
Neznatno oštećenja Table-Driven Implementacija

11.
"Ogleda" Table-Driven implementacije

12.
"Preokrene" Polys

13.
Početne i završne vrijednosti

14.
Definiranje Algoritmi Apsolutno

15.
A Parameterized model za CRC Algoritmi

16.
A Shop of Parameter Kompleti za standarde

17.
Implementacija Modelu Algoritam

18.
Roll Your Own Table-Driven Implementacija

19.
Generiranje je pregledna tablica

20.
Summary

21.
Korekcije

A. Rječnik

B. Reference

C. Reference Imam otkrivena Ali još nisu slabovidnihSažetak

--------

Ovaj dokument objašnjava CRCs (cikličke zalihosti kodovi) i njihovo

stol-driven implementacijama u potpunosti, točan detalj.
Velik dio

literature na CRCs, a posebno na njihov stol-driven

implementacije, je malo opskurno (ili barem mi tako izgleda).

Ovaj dokument je pokušaj dati jasne i jednostavno bez gluposti

objašnjenje CRCs i zakovati apsolutno svaki detalj o

funkcioniranje njihove velike brzine implementacije.
Osim toga,

ovaj dokument predstavlja model parameterized CRC algoritam naziva

"^ Rocksoft tm Model CRC Algoritam".
Model algoritam može se

parameterized da se ponašaju kao i veći dio CRC oko implementacije,

i tako djeluje kao dobra referenca za opisivanje određenom algoritama.

A low-speed provedbe modela CRC algoritma je predviđeno u

C programski jezik.
Na kraju se nalazi i poglavlje daje dva oblika

of high-speed stol driven implementacije i pružanje program

koji generira CRC lookup tablicama.1.
Uvod: detekcija pogrešaka

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

Cilj je do pogreške detekcija tehnika je omogućiti prijemnik od

poruke prenosi kroz glasan (error-uvodeći) kanal

utvrdili je li poruka je oštećen.
Da biste to učinili, u

odašiljač konstrukata vrijednost (naziva se provjerava) da je funkcija

u poruku, a to pridodat na poruku.
Prijamnik tada mogu

koristite istu funkciju izračunati zbroj za provjeru primljenih od

poruke i usporedite s prilogu provjerava da vidi je li

Poruka je ispravno primljena.
Na primjer, ako smo odabrali jedan ispitni zbroj

funkciju koja je jednostavno suma od bajtova u poruci mod 256

(tj. modulo 256), onda bi to moglo ići nešto što slijedi.
Svi brojevi

su u dekadski.Poruka: 6 23 4

Poruka s provjerava: 6 23 4 33

Poruka nakon prijenosa: 6 27 4 33U gore, drugi bajt u poruci oštećen je od 23. do

27 od komunikacijskih kanala.
Međutim, prijemnik može otkriti

ovo se usporedbom s prenosivih provjerava (33) s računalom

ispitni zbroj od 37 (6 27 4).
Ako se provjerava je oštećena, a

korektno prenosi poruka može biti pogrešno identificiran kao

oštećen jedan.
Međutim, to je sigurno na strani neuspjeh.
A opasno-side

pogreške na kojoj se poruka i / ili provjerava je oštećena u

način koji dovodi do prijenosa koji se interno konzistentni.

Nažalost, ova mogućnost je potpuno neizbježna i najbolje

koji se može učiniti je da se minimizira vjerojatnost njegove povećanjem

količina informacija u provjerava (npr. širenja provjerava od

jedan bajt dva bytes).Ostali otkrivanje pogrešaka postoje tehnike koje uključuju performing complex

transformacija na poruku kako bi se uvelo ga blagoglagoljiv

informacije.
Međutim, ovaj dokument bavi samo CRC algoritme,

koja spadaju u klasi otkrivanje pogrešaka algoritama da napuste

podaci netaknuti i dodajte jedan provjerava na kraju.
tj.:<original netaknut message> <checksum>2.
Potreba za Složenost

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

Na primjer provjerava u prethodnom odjeljku, vidjeli smo kako se

ošteti poruka je otkrivena provjerava pomoću algoritma da jednostavno

sume su bajtova u poruci mod 256oruka: 6 23 4

Poruka s provjerava: 6 23 4 33

Poruka nakon prijenosa: 6 27 4 33Problem s ovom algoritma je da je to previše jednostavna.
Ako je broj

slučajni corruptions dogodi, ima 1 u 256 šansa da će

ne može otkriti.
Na primjeroruka: 6 23 4

Poruka s provjerava: 6 23 4 33

Nakon prijenosa Poruka: 8 20 5 33Ojačati provjerava, mogli bismo se promijeniti iz 8-bitni registar

16-bitni registar (tj. suma je mod 65536 bytes umjesto mod 256), tako

kao prividno smanjuju vjerojatnost pogreške od 1 / 256 za

1 / 65536.
Iako je u osnovi dobra ideja, to ne uspije, u ovom slučaju, jer

formula koja se nije dovoljno "slučajnih"; s jednostavnim rezime

formula, svaki bajt dolazni utječe grubo samo jedan bajt od

rezime registrirati bez obzira koliko je širok.
Na primjer, u drugoj

primjer gore navedeno, rezime registrirati moglo biti megabyte širok, a

pogreška bi ići dalje neotkriven.
Ovaj problem se može riješiti

rezime zamjenjujući jednostavne formule s više sofisticirana formula

koji uzrokuje svaki dolazni bajt imati učinak na cijelu

provjerava registrirate.Dakle, vidimo da najmanje dva aspekta su potrebni da se formira snažna

provjerava funkcija:Širina: A registrirati širina dovoljno širok kako bi pružio nisku a-priori

probability of failure (npr. 32-bita daje 1 / 2 ^ 32 šansu

neuspjeha).Chaos: A formula koja daje svaki ulazni bajt potencijal za promjenu

bilo koji broj bitova u registru.Napomena: pojam "provjerava" je vjerojatno koristi za opisivanje rano

rezime formule, ali je sada na općenitije značenje

obuhvaća više sofisticirane algoritme poput onih CRC.
Taj

CRC algoritmi biti opisane zadovoljiti drugom stanju vrlo dobro,

i može biti konfiguriran za rad s različitim provjerava widths.3.
Osnovna ideja CRC Algoritmi

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

Gdje bismo mogli ići u našoj potrazi za složenije funkcije od

rezime?
Sve vrste shema proljeća do uma.
Možemo konstrukt

tablica pomoću znamenki pi, ili smjesa svaki dolazni bajt sa svim

bajtova u registar.
Mogli bismo čak i držati veliki telefonski imenik

on-line, i koristiti svaki dolazni bajt u kombinaciji sa registrirati bytes

indeksirati novi telefonski broj koji će biti sljedeći registrirati vrijednost.

Mogućnosti su neograničene.Međutim, mi ne treba ići tako daleko, a sljedeći korak aritmetika

dovoljno.
Dok je jasno osim ne dovoljno jak da se formira jedna

provjerava na snazi, to ispada da je podjela, tako dugo dok se

djelitelj je kao širok kao zbroj za provjeru registrirate.Osnovna ideja je jednostavno CRC algoritmi za liječenje poruku kao

ogroman binarni broj, razdijelite ga na drugom fiksnom binarni broj,

i da se ostatak od ove podjele se provjerava.
Nakon

primitka poruke, prijemnik može izvesti iste podjele i

ostatak usporediti s "provjerava" (prenose ostatku).Primjer: Pretpostavimo na poruku sastojalo od dva bytes (6,23), kao

u prethodnom primjeru.
To se može smatrati da se u heksadecimalni

broj 0617, koji se može smatrati da je binarni broj

0000-0110-0001-0111.
Pretpostavimo da smo koristili provjerava registrirati jedan-byte

širok i koristiti stalan djelitelj od 1001, tada je zbroj za provjeru

Ostatak nakon 0000-0110-0001-0111 je podijeljen 1001.
Dok je u ovom

slučaju, ovo bi moglo Izračun očito se izvode korištenjem zajedničkih

vrt raznolikost 32-bit registre, u općem slučaju je to u neredu.
Tako

Umjesto toga, mi ćemo napraviti podjela pomoću dobre-'ol dugo podjele koju

naučeno u školi (sjećate?).
Osim ovog puta, to je u binarni:... 00AD = 0000010101101 = 173 = kvocijent

____-___-___-___ -

9 = 1001) 0000011000010111 = 0617 = 1559 = djeljenik

Djelitelj 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 = ostatakU ovom je decimalni "1559 podeljen 9 je 173 s ostatka 2".Iako je utjecaj svakog bita za unos poruke na kvocijent

nije sve što je značajan, 4-bitni ostatak dobiva nogama o

jako puno tijekom izračun, a ako više bytes dodao da su

poruke (dividenda) je vrijednost mogla radikalno promijeniti opet vrlo

brzo.
To je razlog zašto podjelu radi Osim gdje ne.U slučaju da ste pitate, koristeći ovaj 4-bitni provjerava se prenosi

poruka bi izgledati ovako (u heksadecimalni): 06172 (gdje je 0617

je poruka, a 2 je zbroj za provjeru).
Prijamnik će podijeliti

0617 9 i vidjeti hoće li se ostatak je 2.4.
Polynomical aritmetika

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

Iako je podjela sheme opisane u prethodnom odjeljku je vrlo

vrlo sličan na checksumming šema nazvana CRC sheme, u CRC

Sheme su zapravo malo weirder, i mi treba da prekapati u neke

čudno broj sustavi razumjeti ih.Riječ ćete čuti sve vrijeme kada se bave CRC algoritmi

je riječ "polinom".
A s obzirom CRC algoritam će se reći da se

koristeći određenu polinom, CRC i algoritmi su u cjelini, rekao je

da se pomoću operacijskog polinom aritmetika.
Što to znači?Umjesto da je djelitelj, dividendu (poruke), kvocijent i ostatak

(kao što je opisano u prethodnom poglavlju) se posmatrati kao pozitivan

integers, oni su kao polinomi s binarnim koeficijentima.

To je učinio po liječniku svaki broj kao string-bitne čije su bitovi

su koeficijenti a polinom.
Na primjer, obični broj 23

(dekadski) je 17 (šest) i 10.111 dvojčana tako da odgovara na

polinom:1 * x ^ 4 0 * x ^ 3 1 * x ^ 2 1 * x ^ 1 1 * x ^ 0ili, jednostavnije rečeno:x ^ 4 x ^ 2 x 1 x ^ ^ 0Korištenjem ove tehnike, poruka, i djelitelj može biti zastupljeni

kao polinomi i možemo učiniti sve naše računsko jednako kao i prije, osim

da sad je sve zatrpan sa XS.
Na primjer, pretpostavimo htjeli smo

do 1101 by mnošenja 1011.
Možemo to učinili, jednostavno se množenjem

polinomix ^ 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 ^ ^ 0U ovom trenutku, da bi dobili pravi odgovor, mi smo se pretvarati da je 2 x

i propagirati dvojčana nosi sa 3 * x ^ 3 popustljivx ^ 7 x ^ 3 x ^ 2 x 1 x ^ ^ 0To je isto kao obična aritmetička osim da je baza je zamišljen

i doveo u svim proračunima umjesto da se eksplicitno

postoji implicitno.
Pa šta je svrha?Stvar je u tome da ako mi pretvarati da ne znam šta je x, ne možemo

obavljati nosi.
Mi ne znamo da je 3 * x ^ 3 je isto kao x ^ 4 x ^ 3

jer mi ne znamo da je x 2.
U ovom true polinom aritmetika

odnos između svih koeficijenata je nepoznat, i tako je

koeficijenti za svaku vlast efektivno postati jako kucanog;

koeficijenti x ^ 2 efikasno nekog drugog tipa na

koeficijenti x ^ 3.S koeficijentima za svaku vlast lijepo izolirani, matematičare

je došao gore sa svim vrstama različitih polinom arithmetics

jednostavno mijenjanje pravila o tome kako koeficijenti rada.
Od tih

Sheme, jedno posebno ovdje je relevantna i da je polinom

aritmetička gdje se računaju koeficijenti MOD 2 i nema

nositi sve koeficijenti moraju biti ili 0 ili 1 i ne provodi se

izračunati.
To se zove "polinom aritmetička mod 2".
Stoga,

Povratkom u ranijim primjerx ^ 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 ^ ^ 0Pod drugim aritmetika, 3 * x ^ 3 pojam bio propagated korištenja

nositi mehanizam pomoću spoznaje da je x = 2.
Pod "polinom

aritmetička mod 2 ", ne znam što je x, nema nosi, i

svi koeficijenti moraju biti izračunat mod 2.
Dakle, rezultat

postaje:= X ^ 6 x ^ 5 x ^ 4 x ^ 3 x ^ 2 x 1 x ^ ^ 0Kao Knuth [Knuth81] kaže (p.400):"Čitatelju trebali primjetite sličnost između polinom

aritmetički i više precizno aritmetički (Poglavlje 4.3.1), gdje

je baza b je zamijenjen za x.
SSef razlika je u tome što se

koeficijent u_k od x ^ k polinom aritmetička medvjeda u malim ili nikakvim

odnosu na susjednih koeficijenti x ^ (k-1) [a x K ^ (1)], tako da

ideju "nošenje" s jednog mjesta na drugo je odsutan.
U stvari

polinom aritmetika po modulu b je u suštini istovjetna više

aritmetika s preciznošću radix b, osim što nosi sve su

potisnut. "Ovako polynomical aritmetička mod 2 je samo binarni aritmetički mod 2 sa

ne nosi.
Dok polinomi pružiti koristan u matematičkim Strojevi

više analitički pristupi i CRC error-correction algoritmi za

potrebe izlaganja ne daju dodatni uvid i neke

teret, te su odbačene u ostatku ovog dokumenta

u korist direktne manipulacije u kojoj aritmetički sustav s

oni su isomorphic: binarna aritmetika bez nositi.5.
Binarna aritmetika s Ne nosi

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

Imajući dispensed s polinomi, možemo se fokusirati na stvarne aritmetičke

tema, koje je da su sve aritmetičke izvodi tijekom CRC

računanje izvodi u binarnom bez nosi.
Često je to

zove polinom aritmetika, ali kao što sam proglašen ostatak ove

jedan dokument polinom free zone, mi ćemo morati nazvati CRC aritmetika

umjesto.
Kao što je ovaj aritmetička ključni je dio CRC izračuni, mi bismo

bolje da se na njega.
Idemoodavanje brojeva u dva CRC aritmetička je ista kao i dodavanja brojeva u

običan binarni aritmetički osim nema nositi.
To znači da

svaki par odgovarajući bitovi odrediti odgovarajuće izlazna bita

bez pozivanje na bilo koji drugi bitni pozicijama.
Na primjer:10011011

11001010

--------

01010001

--------Postoje samo četiri slučaja za svaki zalogaj položaj:0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0 (nema nositi)Oduzimanje je identična:10011011

-11001010

--------

01010001

--------s0-0 = 0

0-1 = 1 (wraparound)

1-0 = 1

1-1 = 0U stvari, oba u dodatku i oduzimanje CRC aritmetička je ekvivalentan

na XOR operacije, i XOR operaciju vlastite inverzna.
Ovo

učinkovito smanjuje operacija prvog nivoa vlasti

(Uz to, oduzimanje) na jednu operaciju koja je vlastitim inverzna.

Ovo je veoma zgodan nekretninu od aritmetika.By collapsing o dodatku i oduzimanje, u bilo kojoj aritmetički odbacuje

Pojam magnitude izvan snage svoju najvišu jedan zalogaj.
Iako je

čini se jasno da je 1010 veću od 10, to više nije slučaj

1010 da se može smatrati da bude veća od 1001.
Da biste vidjeli ovaj, bilješke

koji možete dobiti od 1010 do 1001 by dodajući kako je i subtracting

ista količina:1010 = 1010 0011

1010 = 1010 - 0011To čini gluposti bilo pojam poretka.Nakon što su definirana Nadalje, možemo premjestiti na razmnožavanje i podijeljenosti.

Množenje je potpuno jasan, budući da je zbroj u

prvi broj, u skladu s pomaknutom drugi broj.1101

x 1011

----

1101

1101.

0000 ..

1101 ...

-------

1111111 Napomena: Zbroj koristi CRC Dodatno

-------Zavod je malo Messier što nam je potrebno da znate kada je "broj ide

u neki drugi broj. Da biste to učinili, mi dozivati slabe definicije

Magnituda definirano ranije: X koja je veća od ili jednaka Y iff

položaju najviše 1 malo X je jednak ili veći od

položaj najviše 1 malo Y. Ovdje mi je u potpunosti izrađen podjela

(nicked od [Tanenbaum81]).1100001010

_______________

10011) 11010110110000

10011 ,,.,,....

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

10011 ,.,,....

10011 ,.,,....

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

00001 .,,....

00000 .,,....

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

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01.011 ....

00.000 ....

-----....

10110 ...

10011 ...

-----...

01010 ..

00000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = ostatakTo je stvarno ona.
Prije daljnjeg postupka, međutim, to je vrijedno naše

dok igrate s ovim aritmetička malo da bi se na njega.Mi smo već igrali uz dodatak i oduzimanje, primjećujući da su

su ista stvar.
Ovdje, međutim, mi treba da imajte na umu da u ovom

aritmetička A 0 = A i A-0 = A.
Ova očigledna vlasništvo je vrlo korisno

kasnije.U koje se bave CRC množenje i podjela, to je vrijedno uzimajući

osjećaj o konceptima i višestruke djeljiv.A ako je jedan broj je više od B onda što to znači u CRC

aritmetička se da je moguće konstruirati od nula po XORing

u različite smjene B. Na primjer, ako je 0111010110 A i B bila je 11,

bismo mogli konstruirati iz B, kako slijedi:0111010110

= ....... 11.

.... .... 11

... 11 .....

,11 .......Međutim, ako je 0111010111, nije moguće konstruirati ga iz

razne smjene B (možete vidjeti zašto? - vidi kasnije) pa je rekao da se

nije djeljiv by B u CRC aritmetika.Tako ćemo vidjeti da CRC aritmetička XORing je prije svega o određenoj

vrijednosti u različitim namještajući offsets.6.
Potpuno Radila Primjer

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

Nakon što su definirana CRC aritmetika, možemo sada okviru jedne CRC Izračun kao

Jednostavno dijeljenje, jer to je sve je to!
Ovaj dio popunjava u

detalje, te daje primjer.Da biste napravili izračun CRC, moramo izabrati djelitelj.
U matematika

marketing govore djelitelj zove se "generator polinom" ili

jednostavno "polinom", a predstavlja ključni parametar bilo CRC algoritam.

To će vjerojatno biti više prijateljski nazovite djelitelj nešto drugo,

ali poli razgovor je tako duboko ukorijenjen u polje da bi to

sada biti zbunjujuća da se izbjegne njega.
Kao kompromis, mi ćemo se odnose na

CRC polinom kao "poli".
Pravedan misliti na taj broj, kao svojevrsno

papagaj.
"Poli Hello!"Možete odabrati bilo koji poli i iskrsavati sa CRC algoritam.
Međutim,

polys neke su bolje od drugih, i tako je mudar da budu sa

testirane jednom pokušao sam sebe.
A kasnije poglavlje bavi ovom pitanju.Širina (najviši položaj bita 1) of the poly je vrlo

važno jer dominira cijelom izračuna.
Tipično, widths of

16 ili 32 su odabrali kako bi se pojednostavio provedbu na modernim

računala.
Širina od poli je stvarni položaj bita u

najviša bita.
Na primjer, 10011 širina je 4, a ne 5.
Za

svrhe Primjerice, mi ćemo je izabrao jednog od poli 10011 (od širine W 4).Imajući odabrao poly, možemo nastaviti s izračuna.
To je

jednostavno dijeljenje (u CRC aritmetički) u poruci koju je poli.
Taj

samo trik je u tome što W nulti bitovi su u prilogu na poruku prije

CRC izračunava.
Tako imamo:Originalna poruka: 1101011011

Poly: 10011

Poruka nakon dodavanjem nula W: 11010110110000Sada jednostavno podijeliti proširen na poli poruku koristeći CRC

aritmetika.
To je ista podjela kao i prije:1100001010 = kvocijent (nitko ne brine o kvocijent)

_______________

10011) 11010110110000 = proširena poruka (1101011011 0000)

Poly ,,.,,.... = 10011

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

10011 ,.,,....

10011 ,.,,....

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

00001 .,,....

00000 .,,....

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

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01.011 ....

00.000 ....

-----....

10110 ...

10011 ...

-----...

01010 ..

00000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = = ostatak THE CheckSum!Podjela daje količnik, koji mi bacaju, a ostatak,

koji je izračunat provjerava.
Ova aukcije izračun.Obično se tada provjerava se u prilogu na poruku i rezultat

prenose.
U ovom slučaju prijenos bio bi: 11010110111110.Na drugom kraju, prijemnik može učiniti jednu od dvije stvari:a.
Razdvojite poruci i provjerava.
Izračunajte zbroj za provjeru za

poruke (nakon W dodavanjem nula) i usporediti dva

checksums.b.
Program cijelog zemljišta (bez dodavanjem nula) i ako ga vidim

izlazi kao nula!Ove dvije opcije su ekvivalentne.
Međutim, u sljedećem odjeljku, mi

će biti pretpostavljiv b opciju jer je periferno matematički

čistije.Sažetak na rad klasi CRC algoritmi:1.
Izaberite širina W, a poly G (od širine W).

2.
Priložena W nulti bitovi na poruku.
Nazovite odmah ovaj M '.

3.
Podijeli M 'by G koristi CRC aritmetika.
Ostatak se provjerava.To je sve što je na njega.7.
Odabir Poly

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

Odabir poli je nešto od crne umjetnosti i čitatelj je navedeno

do [Tanenbaum81] (p.130-132) koji ima vrlo jasne raspravu o ovom

problem.
Ovo poglavlje ima za cilj samo da se strah od smrti u bilo ko

koji su toliko kao igračke s idejom sačinjava vlastitu poli.
Ako

ne brinuti se o jednoj poli zašto bi moglo biti bolje nego neki drugi i samo

žele saznati o velikoj brzini implementacije, izaberite jedan od

arithmetically zvuka polys navedene na kraju ovog odjeljka i preskočiti

na sljedeći odjeljak.Najprije primite na znanje da prenesu poruku T je više od poli.

Da biste vidjeli ovaj, uzmite u obzir da 1) zadnjeg bita W T je od ostatka nakon

razdioba prošireni (po nula sjetiti) poruku koju je poli, i 2)

Uz to je isto kao oduzimanje dodajući kako se ostatak gura se

vrijednosti do sljedećeg više.
Sad uzmite u obzir da ako se prenosi

Poruka je oštećen u prijenosu da ćemo primiti T E gdje je E

is an error vektor (i je dodatak CRC (npr. XOR)).
Po primitku

ovu poruku, prijemnik dijeli T E G. Kao T mod je G 0, (T E)

mod G = E mod G. Dakle, kapaciteta od poli smo odabrati ulov

pojedine vrste greške će biti određena je skup multiples

G, za bilo koju korupcija E da je više od G će biti neotkriven.

Naš zadatak je da onda pronaći klase G čiji multiples izgledaju kao mali

kao što je rod od buke liniju (koja će biti stvaranje corruptions) kao

moguće.
Tako ćemo razmotriti vrste linija šum možemo očekivati.SINGLE BIT pogreške: Jedna pogreška bita znači E = 1000 ... 0000.
Možemo

bi se osiguralo da ova klasa greška je uvijek otkriven pobrinete da

G ima najmanje dva bita postavljeno na 1.
Bilo koja višestruko G će biti

konstruirani pomoću pomicanja i dodavanjem i nemoguće je

Konstruiramo vrijednost s jednom bitnom gura jednog po jednog dodajuchi

vrijednost s više od jednog bita postavili, kao dva bita kraju će se uvijek

ustrajati.Mizeran POGREŠKE: Za detektirati sve pogreške u obliku 100 ... 000100 ... 000

(tj. E sadrži dva bita 1) odabrati G koja nema multiples

koji su 11, 101, 1001, 10001, 100001, itd. Nije mi jasno kako se

jedan ide čineći ovo (nemam čiste matematike pozadini),

ali Tanenbaum osigurava nam da se takve G postoje i navodi G s 1 bita

(15,14,1) uključeno kao primjer jednog G koji neće ništa Razdijelit

manje od 1 ... 1 ... gdje
32767 je nula.POGREŠKE S Odd BROJ BITS: Možemo uhvatiti sve corruptions gdje

E ima neparan broj bita po izboru G koji je još broj

bitova.
Da biste vidjeli ovaj, uzmite u obzir da 1) CRC multiplikacija je jednostavno jedan XORing

konstantna vrijednost u registru na raznim offsets, 2) XORing je jednostavno

malo-flip operacije, i 3) ako XOR vrijednost s još broja

bitova u registru, čudnost se na broj od 1 bita u

registrirati ostaje invarijantne.
Primjer: Od E = 111, pokušaj

flip sva tri bita na nulu od ponovljenih primjena u XORing

11 na jedan od dva offsets (tj. "E = E XOR 011" i "E = E XOR 110")

To je gotovo isomorphic na "staklenim tumblers" party gdje puzzle

izazov nekome da vam flip tri tumblers po ponovio

primjena na rad bilo koje flipping dva.
Većina od popularnih

CRC polys sadržavati još broj od 1 bita.
(Napomena: Tanenbaum države

točnije da su sve pogreške s neparan broj bita može biti

G uloviste donošenjem više od 11).Praskava POGREŠKE: A praskava pogreška izgleda kao E = 000 ... 000111 ... 11110000 ... 00.

To jest, E se sastoji od svih nula, osim u vožnji 1s negdje

unutar.
To se može pretopiti kao E = (10000 ... 00) (1111111 ... 111), gdje

postoje z nula u lijevom dijelu i n one u desnom dijelu.
Za

ulov greške ove vrste, mi jednostavno postaviti najnižu zalogaj od G do 1.

To osigurava da LIJEVO ne moze biti faktor G. Tada, tako dugo dok

G je šira od desne greška će biti otkrivena.
Pogledajte Tanenbaum za

jasnije objašnjenje ovoga; sam malo fuzzy na ovoj.
Napomena:

Tanenbaum, tvrdi da je vjerojatnost nekog praska dužine veće

nego što je kroz dobivanje W (0.5) ^ W.To zaključuje poglavlje o umjetnina odabira polys.Neki popularni polys su:

16 bita: (16,12,5,0) [X25 standard]

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

32 bita: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]8.
CRC jednostavan za implementaciju

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

To je kraj teorije; sada skrećemo na implementacijama.
Za početak

s, ispitali smo apsolutno ravno-down-the-middle dosadno

neposredan niske brzine implementacija koja ne koristi brzinu

varalica at svi.
Zatim ćemo transformirati da progessively program sve dok ne

kraj gore sa kompaktnim stol-driven code smo svi znali i ljubavi i

kojih neki od nas htjeli razumjeti.Primijeniti CRC algoritam sve što morate učiniti je implementirati CRC

podijeljenosti.
Postoje dva razloga zašto se ne možemo jednostavno koristiti Razdijelit

instrukcije od bilo što smo na stroju.
Prvi je da imamo

da učine podijeliti u CRC aritmetika.
Druga je da se dividende

može biti deset megabajta dugo, a današnji procesori nemaju

registrira da je velika.Tako je za provedbu CRC podjela, mi smo to feed poruku putem

podjela registrirate.
U ovom trenutku, mi moramo biti apsolutno precizan

o poruci podataka.
U svim sljedećim primjerima poruka će

se smatrati da je tok bajtova (svaka 8 bitova), s bitnim 7

svaki bajt koji smatraju da su najznačajniji bit (MSB).
Taj

bitova formirana od tih bytes će bitova s MSB

(bitni 7) prvi bajt prvi, idući dolje na bitni 0 od prve

bajt, a onda u drugoj MSB bajt i tako dalje.Imajući ovo na umu, možemo skicirati implementacija u CRC

podijeljenosti.
Za potrebe primjer, razmotriti poli s W = 4 i

na poli = 10.111.
Zatim je obaviti podjelu, trebamo koristiti 4-bitni

Registracija:3 2 1 0 Bitova

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

Pop!
<- | | | | | <----- Prošireni poruku

--- --- --- --- 1 0 1 1 1 = The Poly(Napomena: U prošireni poruka je poruka slijedi W nula bitova.)Izvršiti podjelu obavljati sljedeće:Opterećenje registar s nula bitova.

Uvećati poruku W po dodavanjem nula bitova na kraj nje.

Iako je (više poruka bita)

Započeti

Shift registar lijevo po jedan zalogaj, čitanja sljedeći zalogaj od

prošireni poruku registrirati položaj bita 0.

If (a 1 bita popped out of registar tijekom korak 3)

Registracija Registracija = XOR Poly.

Kraj

Registar sada sadrži ostatak.(Napomena: U praksi, IF uvjet može biti ispitan testiranjem na vrh

malo prije R izvedbu pomak.)Mi ćemo pozvati ovaj algoritam "JEDNOSTAVNA".Ovo može izgledati malo zbrkan, ali svi smo mi zapravo radiš je

"subtracting" različitih ovlasti (tj. shiftings) of the poly od

poruka dok nema ništa, ali se ostatak lijevo.
Studija je

priručnik primjeri dugo podjele i ako ne razumijete ove.To bi trebalo biti jasno da je iznad algoritam će raditi za bilo koju širinu W.9.
Stol-Driven Implementacija

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

Jednostavan algoritam gore je dobra polazna točka, jer

odgovara izravno na teorije do sada, i zato što je

tako jednostavna.
Međutim, budući da djeluje na razini bita, to je prilično

neokretan na broj (čak u C), te izvršavanje neučinkovita (to je to

loop jednom za svaki zalogaj).
Da bi ga ubrzati, moramo pronaći način da se

omogućiti algoritma za obradu poruka u veće jedinice od jednog

djelić.
Kandidat količine su grickalice (4 bita), byte (8 bita), riječi

(16 bita) i longwords (32 bita) i viša ako to možemo postići.
Od

tim, 4 bita je najbolje izbjegavati jer se ne odgovara na bajt

međa.
U najmanju ruku, bilo koji speedup trebali bi nam omogućiti da rade na

bajt granice, i zapravo većina tablice driven algoritmi

poslovati jedan bajt u isto vrijeme.Za potrebe diskusije, neka nam se prebaciti s 4-bitnim za poli

32-bitni jedan.
Naš registrirati izgleda puno istih, osim kutije

predstavljaju bytes umjesto bitova, a Poly je 33 bitova (jedan implicitan

1 bita na vrhu i 32 "aktivna" bita) (Z = 32).3 2 1 0 Bytes

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

Pop!
<- | | | | | <----- Prošireni poruku

---- ---- ---- ---- 1 <------ 32 bita ------>Jednostavan algoritam je još uvijek moguće.
Neka nas ispitati o čemu se radi.

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.