Cyklické Retandancy Kódy: Príklad realizácie

[dkace]

Nazdar,
Nikdy som naprogramovaný kód v MC s CRC kód, takže potrebujem vašu pomoc.
Predstavte Mám μC ktorá kontroluje vypínačom a ak je prepínač na, potom to znie budík.Teraz tento μC komunikovať s inou, výmena adries a stastus kontrolný port.Ako môžem implementovať kód?Každý dobrý podnet na pochopenie funkcie, alebo dobré referencie na čítanie?
Ďakujeme vám

D.

 

[geok]

Nazdar,

Wikipedia bola vždy dobrým zdrojom.

Samozrejme, je to klasický "Plombující príručka pre algoritmy detekcie chýb"GeorgeEDIT: Zabavenie re-nahrán.
Ospravedlňujeme sa, ale musíte prihlásiť a prezerať túto prílohu

 

[dkace]

Prepáč, ale nemôžem stiahnuť.Tam je problém s odkazom
D.

 

[geok]

I am sorry, ale keď som si stiahnuť môj pripevnenia pri úpravách môj post,
ale nemôžem si ju stiahnuť neskôr.

Každopádně, tady je úplná dokumentu:

V Plombující príručka pre detekciu chýb algoritmy-Časť 1:
Kód:

A bezbolestne GUIDE TO CRC pre detekciu chýb algoritmy

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

"Všetko, čo ste chceli vedieť o CRC algoritmy, ale báli

sa opýtať v obave, že chyby v pochopenie by mohla byť zistená. "Verzia: 3.

Dátum: 19. augusta 1993.

Autor: Ross N. Williams.

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

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

Spoločnosť: Rocksoft ^ tm Pty Ltd

Šnek: 16 Lerwick Avenue, Hazelwood Park 5066, Austrália.

Fax: 61 8 373-4911 (c / - vnútorné systémy Pty Ltd).

Telefón: 61 8 379-9217 (10am to 10pm Adelaide Austrália času).

Poznámka: "Rocksoft" je ochrannou známkou Rocksoft Pty Ltd, Austrália.

Status: Copyright (C) Ross Williams, 1993.
Avšak, je povolenie

udelená značka a šíriť doslovné kópie tohto

dokumentu za predpokladu, že tieto informácie blok a autorské práva

Oznámenie je v cene.
Ďalej platí, že C kód modulu zahrnuté

V tomto dokumente sú plne verejnosti.

Poďakovanie: Ďakujeme Jean-loup Gailly (jloup (at) chorus.fr) a Mark Adler

(me (at) quest.jpl.nasa.gov), ktorí obaja dôkazom prečítajte tento dokument

a vybral hodně nits, rovnako ako niektoré veľké hrubé chyby.Obsah

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

Abstrakt

1.
Úvod: detekcia chýb

2.
Potrebu zloľitos »

3.
Základná myšlienka CRC algoritmy

4.
Polynomical Aritmetické

5.
Binárne Aritmetické bez prevádzkuje

6.
A Plne Pracoval Príklad

7.
Vyberáte Poly

8.
Přímočaré CRC Implementácia

9.
Tabuľka A-Driven Implementácia

10.
A Mírně rozdrvený Tabuľka-Driven Implementácia

11.
"Otázka" Tabuľka-Driven Implementácia

12.
"Obrácené" Polys

13.
Počiatočné a konečné hodnoty

14.
Definovanie algoritmov Absolutně

15.
A parametre Model Pre CRC algoritmy

16.
A Katalóg Parameter Sady pre normalizáciu

17.
Implementácia modelu Algoritmus

18.
Roll Your Own Tabuľka-Driven Implementácia

19.
Generovanie vyhľadávacie tabuľky

20.
Zhrnutie

21.
Opravy

A. Glosár

Odkazy

C. Odkazy I zistili ale zatiaľ zrakovo postihnutéAbstrakt

--------

Tento dokument vysvetľuje CRCs (cyklická redundantní kód) a ich

tabuľky-Driven implementáciu v plnom rozsahu, presne a podrobne.
Podstatná časť

literatúry o CRCs, a najmä na ich stôl-riadený

implementáciou, je trochu obskurní (alebo aspoň tak, zdá sa mi).

Tento dokument sa snaží poskytnúť jasný a jednoduchý ne-nezmysel

vysvetlenie CRCs a naprosto nechty každý detail z

fungovanie ich vysoký-rýchlosť implementácie.
Okrem toho,

tento dokument predstavuje model parametre CRC algoritmus nazývaný

"Rocksoft ^ tm Model CRC Algorithm".
Tento model možno algoritmus

parametre správať sa rovnako ako väčšina z CRC implementácia okolo,

a tak pôsobí ako dobrá referencia pre opis konkrétne algoritmy.

A nízky-rýchlosť prevedenia modelu CRC algoritmus je uvedený v

C programovací jazyk.
Nakoniec je tu sekcia dáva dve formy

vysoko-rýchlostný tabuľkou riadený implementácia a poskytovanie program

ktorá generuje CRC lookup tabuliek.1.
Úvod: detekcia chýb

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

Cieľom chybu detekcie techniky je umožniť prijímače a

správy odovzdávať prostredníctvom hlučné (chyba-zavádzajú) kanál

zistiť, či správa bola poškodená.
To urobíte tak, že

vysielač konštrukcie hodnotu (tzv. kontrolný súčet), ktorá je funkciou

časti správy, a pripojí sa k správe.
Prijímač je potom

používať rovnaké funkcie pre výpočet kontrolného z prijatých

správy a porovnať ju s pripojeným kontrolné s cieľom zistiť, či sa

posolstvo bolo správne doručené.
Napríklad, keď sme sa rozhodli, kontrolné

funkcie, ktoré bolo jednoducho súčtom z bytov v správe mod 256

(tj modulo 256), potom by mohlo ísť niečo takto.
Všetky položky

v desiatkovej sústave.Oznámenie: 6 23 4

Správa s nastavením: 6 23 4 33

Vzkaz po odoslanie: 6 27 4 33Vo vyššie, druhý bajt správy bol poškodený z 23 na

27 o komunikačný kanál.
Avšak, prijímač je možné zistiť

tento porovnaním odovzdané kontrolné (33) s počítačom

kontrolný súčet 37 (6 27 4).
Ak kontrolný sám je poškodený, a

správne prenášať správy by mohli byť chybne označené ako

poškodený jeden.
Je to však bezpečný-bočné zlyhania.
Nebezpečná-bočné

výpadku, keď správa a / alebo kontrolný súčet je poškodený v

spôsobom, ktorý vedie k prenosu, ktorý je vnútorne konzistentný.

Bohužiaľ, táto možnosť je úplne nevyhnutné a najlepšie

že je možné urobiť, aby minimalizoval jeho pravdepodobnosť zvýšením

Množstvo informácií v kontrolnej (napr. rozšírenie z kontrolnej

jeden byte pre dva byty).Ostatné detekciu chýb existujú techniky, ktoré sa týkajú vykonávania zložitých

transformáciou na správu vstreknite jej prepusteným

informácie.
Avšak, tento dokument sa zaoberá iba CRC algoritmu

ktoré patria do triedy algoritmov na detekciu chýb, ktoré opúšťajú

data nepoškodená a kontrolné append na koniec.
tj:<original neporušené message> <checksum>2.
Potrebu zloľitos »

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

V kontrolné príklad v predchádzajúcej časti sme videli, ako

poąkodený správa bola objavená pomocou kontrolný algoritmus, ktorý prostě

súm byty v správe mod 256:Oznámenie: 6 23 4

Správa s nastavením: 6 23 4 33

Vzkaz po odoslanie: 6 27 4 33Problém s týmto algoritmom je, že je príliš jednoduchá.
Ak je počet

náhodný corruptions nastať, je 1 256 nádej, že budú

nie je možné zistiť.
Napríklad:Oznámenie: 6 23 4

Správa s nastavením: 6 23 4 33

Vzkaz po odoslanie: 8 20 5 33Na posilnenie kontroly, mohli by sme zmeniť z 8-bit registra

16-bitový register (tj súčet je 65536 bytes mod miesto mod 256), takže

ako to pravdepodobne zníži pravdepodobnosť zlyhania od 1 / 256 k

1 / 65536.
Zatiaľ čo v podstate dobrý nápad, to nepodarí, pretože v tomto prípade

vzorec používa, nie je dostatočne "náhodné", s jednoduchým sčítaním

vzorec, každý prichádzajúci byte postihuje približne len jeden bajt je

sčítaním registra bez ohľadu na to ako to celé je.
Napríklad v druhej

príklad vyššie, záverečná registri by mohlo byť megabyte široký a

chyba by naďalej zostať skryté.
Tento problém možno vyriešiť len

nahrádza jednoduché záverečná formule s dokonalejšími vzorca

, Ktorá spôsobuje každý prichádzajúci byte mať vplyv na celý

kontrolného zoznamu.Tak vidíme, že najmenej dva aspekty sú potrebné na vytvorenie silného

kontrolné funkcie:WIDTH: A dosť široký register šírka poskytnúť nízke a-priori

pravdepodobnosť zlyhania (napr. 32-bitová dáva 1 / 2 ^ 32 chance

zlyhania).CHAOS: Vzorec, ktorý dáva každému byte vstupné potenciál k zmene

ľubovoľný počet bitov v registri.Poznámka: Pojem "kontrolné" bol podľa všetkého používa na opis skorých

súhrnné vzorce, ale má teraz na všeobecnejšom zmysle

zahŕňajúce viac sofistikované algoritmy, ako sú tie, CRC.
V

CRC algoritmy boli popísané spĺňať druhú podmienku veľmi dobre,

a môže byť nakonfigurovaný tak, aby fungoval u rôznych šírkach kontrolné.3.
Základná myšlienka CRC algoritmy

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

Ak by sme mohli ísť v našom hľadanie na zložitejšie funkcie ako

sčítaním?
Najrôznejšie programy na jar na mysli.
Mohli by sme zostrojiť

tabuľky pomocou číslice pi, alebo hash každý prichádzajúci byte so všetkými

bytov v registri.
Dalo by sa dokonca aj veľký telefónny zoznam

on-line, a používať každý prichádzajúci byte v kombinácii s Registry bytov

na index nové telefónne číslo, ktoré bude budúci Registry hodnotu.

Možnosti sú neobmedzené.Avšak, nebudeme musieť ísť tak ďaleko, že ďalším krokom Aritmetická

postačuje.
Zatiaľ čo navyše zjavne nie je dostatočne silná, aby si zaujatie

účinné kontrolné, sa ukazuje, že rozdelenie je tak dlho, kým

divisor je približne rovnako široký ako kontrolný zaregistrovať.Základnou myšlienkou CRC algoritmu je jednoducho na liečbu správu ako

enormnú binárne číslo, rozdeliť ju do inej pevnej binárne číslo,

a na zostávajúcu časť z tejto divízie kontrolné.
Za

prijatí správy, príjemca môže vykonávať rovnaké divízie a

porovnať zvyšok sa "kontrolné" (odovzdané zostávajúce).Príklad: Predpokladajme, že správa sa skladala z dvoch bytov (6,23), ako

v predchádzajúcom príklade.
Tie môžu byť považované za hexadecimálny

číslo 0617, ktorá môže byť považovaná za binárne číslo

0000-0110-0001-0111.
Predpokladajme, že budeme používať kontrolné zaregistrovať jedno-byte

širokej a použitie konštantné divisor na 1001, potom je kontrolný

Zvyšok po 0000-0110-0001-0111 je rozdelená do 1001.
I keď v tomto

prípade tohto výpočtu by mohli byť samozrejme vykonáva prostredníctvom spoločnej

záhradný spektrum 32-bitových registrov, vo všeobecnom prípade je to chaotický.
Tak

miesto, budeme robiť rozdelenie pomocou osvedčených-'ol dlhú divízie, ktorá vás

naučili v škole (spomínate?).
Okrem tejto doby, je to v binárnou:... 0000010101101 = 00AD = 173 = kvocient

____-___-___-___ --

9 = 1001) 0000011000010111 = 0617 = 1559 = DIVIDEND

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 = zostávajúceV desiatkovej sústave je to "1559 rozdelený do 9 je 173 a zostávajúca časť 2".Hoci účinok každého trochu vstupné správy o kvociente

nie je všetko, že významný, 4-bit zvyšok dostane asi kopl

pomerne veľa, počas výpočtu, a ak je viac bytov boli pridané do

správy (dividendy) je to hodnota by mohla radikálne zmeniť opäť veľmi

rýchlo.
To je dôvod, prečo deľby práce, kde navyše nie je.V prípade, že ste přemýšlel, s použitím tejto 4-bit kontrolné prenášaných

Správa by vyzerať takto (v hexadecimálnej sústave): 06172 (kde 0617

je správa a 2 je kontrolná).
Prijímač by priepasti

0617 od 9 a pozrite sa, či bol zvyšok 2.4.
Polynomical Aritmetické

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

Kým divízie systém opísaný v predchádzajúcej časti je veľmi

veľmi podobný tomu, ktorý checksumming režimov názvom CRC režimy, CRC

systémy sú v skutočnosti trochu divnější, a musíme sa ponoriť do nejakej

podivný počet systémov porozumieť im.Slovo počujete po celú dobu, keď sa zaoberajú CRC algoritmy

je slovo "polynom".
A vzhľadom k tomu, CRC algoritmus sa hovorí, že je

použitia určitej polynómu a CRC algoritmy sú všeobecne povedať

byť operačný pomocou polynómu aritmetika.
Čo to znamená?Miesto toho sa divisor, dividenda (správa), podiel a zvyšok

(ako je opísané v predchádzajúcej časti) je vnímaný ako pozitívny

celé čísla, sú vnímané ako polynómu s binárnym koeficienty.

To sa vykonáva úpravou každého čísla ako bit-string ktorého bity sú

koeficienty z polynómu.
Napríklad, obyčajné číslo 23

(desiatkovom) je 17 (hex) a 10111 binárnou a tak zodpovedá na

polynóm:1 * x ^ 4 0 * x ^ 3 1 * x ^ 2 1 * x ^ 1 1 * x ^ 0alebo jednoduchšie:x ^ 4 x ^ 2 x ^ 1 x ^ 0Pomocou tejto techniky, správy a divisor môže byť zastúpený

ako polynómu a čo môžeme urobiť všetky naše aritmetickými rovnako ako predtým, s výnimkou

že teraz je to všetko zaplněný až s Xs.
Povedzme, že sme chceli

množiť 1101 do 1011.
Môžeme to urobiť jednoducho vynásobením

polynómux ^ 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 ^ 0V tomto momente sa dostať správnu odpoveď, musíme sa tváriť, že je x 2

a propagovať binárnou prevádzkuje od 3 * x ^ 3 získavaniex ^ 7 x ^ 3 x ^ 2 x ^ 1 x ^ 0Je to rovnako ako obyčajné aritmetické okrem toho, že základom je roztržitý

a vniesol do všetkých výpočtov výslovne namiesto

tam implicitne.
Tak čo to má zmysel?Pointa je v tom, že ak budeme tváriť, že nevieme, čo je x, nemôžeme

vykonávať prevádzkuje.
Nevieme, že 3 * x ^ 3 je rovnaký ako x ^ 4 x ^ 3

pretože nevieme, že je x 2.
V tejto pravda polynóm Aritmetická

vzťah medzi koeficientmi je neznámy, a tak sa

Koeficienty jednotlivých moc efektívny štát pevne zadanej;

koeficienty x ^ 2, sú skutočne o iný typ

koeficienty x ^ 3.S koeficienty každého moc pekne izolované, matematici

prišiel s najrôznejšími rôzne druhy polynóm aritmetika

jednoducho zmenou pravidiel o tom, ako kurzoch práce.
Z týchto

programy, jedným je obzvlášť relevantný, a to je polynóm

Aritmetická kde koeficienty sú vypočítané MOD 2 a neexistuje

sebou, všetky koeficienty musia byť buď 0 alebo 1, a nie sa vykonáva

vypočítať.
Tomu sa hovorí "polynóm aritmetika mod 2".
Teda,

návrate do predchádzajúcej príkladx ^ 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ľa inej aritmetického, 3 * x ^ 3 obdobie bolo vypestované s použitím

carry mechanizmus využívať vedomosti, že x = 2.
Pod názvom "polynóm

aritmetika mod 2 ", nevieme, čo je x neexistujú vykonáva, a

všetky koeficienty musia byť vypočítaná mod 2.
To znamená, že výsledok

sa stáva:= X ^ 6 x ^ 5 x ^ 4 x ^ 3 x ^ 2 x ^ 1 x ^ 0Ako Knuth [Knuth81] hovorí (p.400):"Čítacie zariadenie by malo upozorniť na podobnosť medzi polynóm

aritmetická a viac-presnosť aritmetických (oddiel 4.3.1), kde

radix b je nahradené x.
Medzi hlavný rozdiel je v tom, že

koeficient u_k x ^ k polynóm aritmetickými medvede v malé alebo žiadne

vzťahu k jeho susedným koeficienty x ^ (k-1) [a x ^ (k 1)], takže

myšlienku "výkon" z jedného miesta na druhé chýba.
V skutočnosti

polynóm aritmetika modulo b je v podstate zhodný s viac

presnosť aritmetických s radix b, s výnimkou toho, že všetci sa vykonáva

potlačené. "Tak polynomical aritmetika mod 2 je len binárne aritmetika mod 2 s

ne prevádzkuje.
Kým polynómu poskytnúť užitočné matematických strojov v

viac analytických prístupov k CRC a chyba-oprava algoritmu pre

účely expozície budú poskytovať žiadne ďalšie poznatky a niektoré

obtiaž a boli vyraďované vo zvyšku tohto dokumentu

v prospech priamej manipulácie aritmetický systém, s ktorým

sú izomorfní: binárne aritmetické so sebou.5.
Binárne Aritmetické bez prevádzkuje

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

S upustiť polynómu môžeme sústrediť na skutočné Aritmetická

problém, ktorý spočíva v tom, že všetky aritmetické vykonaná počas CRC

Výpočty sa vykonáva v binárnou so sebou nesie.
Často je to

nazývajú polynomiální aritmetika, ale jak jsem vyhlásil zvyšok tohto

potvrdzujú polynóm voľné zóny, budeme musieť hovoriť CRC Aritmetická

miesto.
Keďže táto aritmetika je kľúčovou súčasťou CRC výpočtov by sme

lepšie si zvyknúť na to.
Ideme na toridanie dvoch čísiel v CRC aritmetika je rovnaký ako pridanie čísla do

bežné binárne aritmetické výnimkou nie je sebou.
To znamená, že

každú dvojicu zodpovedajúcich bitov určiť zodpovedajúce výstupné bit

bez ohľadu na akékoľvek iné bit pozícií.
Napríklad:10011011

11001010

--------

01010001

--------Existujú iba štyri prípady za každý bit pozícia:0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0 (žiadny carry)Odčítania je rovnaká:10011011

-11001010

--------

01010001

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

0-1 = 1 (ovinovací)

1-0 = 1

1-1 = 0V skutočnosti, ako vedľa a odčítanie v CRC aritmetika je ekvivalentný

na XOR operáciu a XOR operácii je jeho vlastné inverznou.
Tento

účinne znižuje prevádzku prvého stupňa sily

(sčítanie, odčítanie) na jediný úkon, ktorý je jeho vlastné inverznou.

To je veľmi výhodné majetku aritmetický.Do zasúvacej pridanie a odčítanie, aritmetický zbavuje akejkoľvek

pojem veľkosti presahuje výkon jeho najvyšší bit.
I keď

zrejmé, že 1010 je vyšší ako 10, je už v prípade

1010, ktoré možno považovať za viac ako 1001.
Ak chcete vidieť, poznámka

, Ktoré môžete získať od 1010 do 1001 obe pridávanie a odpočítaním

rovnaké množstvo:1010 = 1010 0011

1010 = 1010 - 0011Tým nezmysel akéhokoľvek pojmu poradí.Okrem toho majú definovaný, môžeme prejsť k násobenie a delenie.

Násobenie je úplne jednoduché, čo je súčet všetkých

Prvé číslo, presunula v súlade s druhým číslom.1101

x 1011

----

1101

1101.

0000 ..

1101 ...

-------

1111111 Poznámka: súčet CRC používa navyše

-------Divízia je trochu nepořádnější ako by sme mali vedieť, keď "a číslo prekračuje

na iné číslo. "Aby to bolo možné, sme sa odvolávať na slabú definície

rozsah definovaný skôr: X, ktorý je väčší ako alebo rovný Y MFF

postavenie najvyššej 1 bit z X je rovnaké alebo väčšie ako

pozíciu najvyššie 1 bit Y. Tu 'je plne pracoval divízie

(vrúbkovanie z [Tanenbaum81]).1100001010

_______________

10011) 11010110110000

10011 ,,.,,....

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

10011 ,.,,....

10011 ,.,,....

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

00001 .,,....

00000 .,,....

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

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01011 ....

00000 ....

-----....

10110 ...

10011 ...

-----...

01010 ..

00000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = ZostávajúciTo je naozaj to.
Pred tým, ako ďalšie, ale stojí to za naše

pri hraní s touto aritmetický trochu zvyknúť si na to.Sme už hrali s prídavkom a odčítanie, pozorujem, že sa

sú to samé.
Tu však musíme upozorniť, že v tomto

Aritmetická A 0 = A a A-0 = A.
Táto zjavná vlastnosť je veľmi užitočná

neskôr.Pri zaobchádzaní s CRC násobenie a delenie, stojí to za získanie

pocit pre pojmov viacnásobných a rozdeľovať.Ak číslo A je násobkom B potom, čo to znamená v CRC

Aritmetická sa, že je možné postaviť od nuly do XORing

v rôznych posunie B. Napríklad, ak bol 0111010110 A a B bolo 11,

by sme mohli postaviť z B takto:0111010110

= ....... 11.

11 .... ....

... 11 .....

, 11 .......Avšak, ak je A 0111010111, že nie je možné vyrábať z

rôznych posunie B (môžete vidieť prečo? - pozri ďalej), takže sa hovorí, že je

nie je deliteľné B CRC aritmetika.Tak vidíme, že aritmetický CRC je primárne o XORing najmä

Hodnoty v rôznych presúva offsety.6.
A Plne Pracoval Príklad

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

S CRC definované aritmetické, môžeme teraz vytvorenie CRC výpočtu ako

prostě divízie, pretože to všetko je!
Tento oddiel sa vypĺňa

Podrobnosti a dáva príklad.Ak chcete vykonať výpočet CRC, budeme musieť zvoliť divisor.
V matematike

marketing hovoriť divisor sa nazýva "generátor polynóm" alebo

jednoducho "polynóm" a je kľúčovým parametrom akéhokoľvek CRC algoritmus.

Bolo by asi byť viac priateľské k volania divisor niečo iné,

ale poly hovoriť, je tak hlboko zakorenený v oblasti, že by

Teraz je to mätúce, aby nedošlo.
Ako kompromis, ktorý bude odkazovať na

CRC polynómu ako "poly".
Skúsme si na toto číslo ako akési

papagáj.
"Ahoj poly!"Môžete si vybrať akékoľvek poly a prísť s CRC algoritmus.
Avšak,

POLYS niektorí sú lepšie ako ostatné, a tak je dobré sa držať sa

vyskúšali jeden z nich skúša.
A neskôr sekcii tejto problematike.Šírka (pozícia najvyššej 1 bit) z poly je veľmi

dôležité, ako je dominantou celého výpočtu.
Typicky šírok

16 alebo 32 sa volí tak, aby zjednodušili implementácie na moderný

počítačov.
Šírka a polyoxyetylén je skutočná bit stanovisko

najvyšší bit.
Napríklad, šírka 10011 je 4, nie 5.
Pre

účely, napríklad, budeme si vybral jeden z poly 10011 (šírka W zo 4).S zvolila poly, môžeme pristúpiť k výpočtu.
To je

prostě divízie (v CRC aritmetika) správy, ktoré poly.
V

len trik je v tom, že Z nulovej bity sú pripojené k správy pred

CRC je vypočítaný.
Preto sme saôvodná správa: 1101011011

Poly: 10011

Vzkaz po pridaní Z nuly: 11010110110000Teraz jednoducho rozdeliť doplnená správa o poly pomocou CRC

aritmetika.
To je rovnaké ako pred rozdelením:1100001010 = Podiel (nikto sa zaujíma o podiel)

_______________

10011) 11010110110000 = augmented správy (1101011011 0000)

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

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

10011 ,.,,....

10011 ,.,,....

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

00001 .,,....

00000 .,,....

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

00010 ,,....

00000 ,,....

-----,,....

00101 ,....

00000 ,....

-----,....

01011 ....

00000 ....

-----....

10110 ...

10011 ...

-----...

01010 ..

00000 ..

-----..

10.100.

10.011.

-----.

01110

00000

-----

1110 = Zostávajúci = NA Checksum!Toto rozdelenie vznikne kvocient, ktorý sme zahodiť, a zvyšok,

ktorá je vypočítaná kontrolné.
Tento výpočet končí.Zvyčajne je kontrolný súčet sa potom pripojí na základe správy a výsledok

odovzdané.
V tomto prípade sa prenos by: 11010110111110.Na druhej strane príjemcu môže urobiť jednu z dvoch vecí:a.
Samostatné správy a kontrolný súčet.
Vypočítajte kontrolné

správa (po pridaní Z nuly) a porovnať dve

kontrolné.b.
Kontrolný celú partiu (bez pridania nuly) a zistite, či je

vychádza ako nula!Tieto dve možnosti sú rovnocenné.
Avšak, v ďalšej časti sme sa

sa predpokladá možnosť b, pretože je takmer matematicky

čistejšie.Súhrn prevádzku na triede CRC algoritmy:1.
Vyberte šírku W, a polyoxyetylén G (šírka W).

2.
Append Z nulovej bity na správu.
Zavolej M '.

3.
Dělit M 'G pomocou CRC aritmetika.
Zvyšok je kontrolná.To všetko je k nej.7.
Vyberáte Poly

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

Výber poly je niečo ako čierna mágia a čitateľ sa odkazuje

na [Tanenbaum81] (p.130-132), ktorý má veľmi jasnú diskusiu o tomto

problém.
Táto sekcia si kladie za cieľ dať len strach zo smrti do nikoho

ktorí toľko ako hračky s myšlienkou, ktoré tvoria vlastné poly.
Ak ste

Nestarám sa o tom, prečo jeden poly mohlo byť lepšie, než iné, a práve

chcú dozvedieť o high-rýchlosť implementácie, vyberte jeden z

aritmeticky zvuk POLYS uvedené na konci tohto bodu a preskočte

na ďalšie časti.Po prvé, že vysiela správu T je násobkom tohto poly.

Ak chcete vidieť, že 1) Z posledného bitu T je zvyšok po

dělením umocněno (od nuly pamatovat) správu o poly, a 2)

Navyše je rovnaké ako odpočítaní tak pridajte zvyšok sa posúva

hodnoty až do budúceho viac.
Teraz na vedomie, že ak sa odovzdávajú

Správa je poškodený pri prenose, že budeme dostávať T E, kde E

je chybou, vektor (a je CRC navyše (tj XOR)).
Po obdržaní

túto správu, prijímač bariér T E G. Pretože T mod G je 0, (T E)

mod G = E mod G. To znamená, že kapacita je poly volíme chytit

určité druhy chýb bude určená množina násobkov

G, za akúkoľvek korupcii E, ktorá je násobkom G bude odhalené.

Našou úlohou je teda nájsť triedy G, ktorého násobky pozrite sa, ako málo

ako druh linky hluku (ktorý bude vytvorenie corruptions) as

je to možné.
Tak nech to posúdi druhy línie hluk môžeme očakávať.JEDNOTNOM BIT CHYBY: A jediný bit chyba znamená, E = 1000 ... 0000.
Môžeme

zabezpečiť, že táto trieda je vždy odhalené chyby sa presvedčí, že

G má aspoň dva bity nastavené na 1.
Akékoľvek násobok G bude

vyrobený pomocou presúvania a pridávanie a je nemožné

konštruovať hodnotu s jedinou bitovou posunem pridáva jeden jediný

s hodnotou viac ako jeden bit nastaviť ako dva konca bity budú vždy

pretrvávať.DVA-BIT CHYBY: Ak chcete zistiť všetky chyby v podobe 100 ... 000 ... 000100

(tj E obsahuje dva bity 1) vyberte si G že nemá násobky

, Ktoré sú 11, 101, 1001, 10001, 100001 atd Nie je mi jasné, ako

jedna sa o tom (nemám čistej matematike na pozadí),

Tanenbaum ale uisťuje nás, že táto G existujú, a cituje G s 1 bitov

(15,14,1) zapnutý ako príklad jedného G, že nebude nič deliť

menej ako 1 ... 1, kde ...
je 32767 nul.CHÝB SE nepárny bitov: Môžeme chytiť všetky corruptions kde

E má nepárny počet bitov výberom G, ktorá má párny počet

bitov.
Ak chcete vidieť, že 1) CRC násobenie je jednoducho jedna XORing

konštantnú hodnotu do registra na rôznych kompenzáciou, 2) XORing je prostě

trochu flip-operácie, a 3), ak si XOR hodnoty sa aj počet

bity do registra, podivínství na počet bitov v 1

registra zostáva invariantní.
Príklad: Počnúc E = 111, pokus o

flip všetkých troch bitov na nulu opakované použitie v XORing

11 v jednom z dvoch kompenzácia (tj "E = E XOR 011" a "E = E XOR 110")

To je takmer izomorfní na "sklo skleničky" party, kde puzzle

vás napadnúť niekoho flip tri skleničky v opakovanom

Žiadosť o premávke obracející dvoma.
Väčšina populárnej

CRC POLYS obsahovať párny počet 1 bity.
(Poznámka: Tanenbaum štátov

konkrétnejšie, že všetky chyby s nepárnym počtom bitov môže byť

ulovených tým G násobkom 11).Pretrhnutý CHYBY: A praskla chyba vyzerá E = 000 ... 000.111 ... 11110000 ... 00.

To znamená, že E sa skladá zo všetkých nuly až na spustenie 1s někde

vevnitř.
To môže byť prepracované ako E = (10000 ... 00) (1111111 ... 111), kde

sa z nuly v ľavej časti a n sú v pravej časti.
Do

úlovok chybách tohto druhu, sme jednoducho nastaviť najnižšej bit G: 1.

Zabezpečuje, že robíš ľavého nemožno faktor G. Teda, ak

G je širší ako práva, bude chyba zistená.
Pozri Tanenbaum pre

jasnejšie vysvetlenie tohto, jsem trochu fuzzy na tohle.
Poznámka:

Tanenbaum tvrdí, že pravdepodobnosť, že praskla o dĺžke viac

Z ako dostať cez je (0,5) ^ W.Dospeje k záveru, že časť o výtvarné umenie výberu POLYS.Niektoré populárne POLYS sú:

16 bitov: (16,12,5,0) [X25 štandard]

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

32 bitov: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]8.
Přímočaré CRC Implementácia

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

To je koniec teórie, teraz zase na implementáciu.
Ak chcete začať

s sme skúmať úplne rovno-down-the-middle nuda

přímočaré nízky-rýchlosť prevedení, ktorá nepoužíva žiadne rýchlosti

triky na všetkých.
My potom transformácie, že program progessively kým sme

skončiť s kompaktné stolové-riadený kód všetci vieme, a lásku a

ktoré niektorí z nás by chcel rozumieť.Ak chcete vykonať CRC algoritmus všetko musíme urobiť, je urobiť CRC

divízie.
Existujú dva dôvody, prečo nemôžeme jednoducho použiť priepasti

výučba akéhokoľvek stroje sme on.
Prvá je, že sme

robiť rozdiely v CRC aritmetika.
Druhá je, že dividendy

by mohla byť desať MB dlho, a dnešné spracovatelia nemajú

registrov, ktoré veľká.Takže na vykonanie CRC divízie, musíme kŕmiť správ prostredníctvom

Divízie zaregistrovať.
V tejto chvíli máme za úplne presný

o dátumy správ.
Vo všetkých nasledujúcich príkladoch je správa

byť považovaná za prúd bajtov (každý z 8 bitov) s bit 7

každý byte je považovaný za najvýznamnejší bit (MSB).
V

bit stream vytvorený z týchto bytov bude bit stream s MSB

(bit 7) v prvom byte prvej, šel na bit 0 z prvých

byte, a potom MSB na druhý byte a tak ďalej.V tomto duchu môžeme skica implementácia CRC

divízie.
Na účely napríklad zvážiť poly s W = 4 a

na poly = 10111.
Potom sa vykoná rozdelenie, musíme použiť 4-bit

registra:3 2 1 0 Bits

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

Pop!
<- | | | | | <----- Augmented správy

--- --- --- --- 1 0 1 1 1 = V Poly(Upozornenie: Táto správa bude rozšírená správa nasleduje Z nulovej bity.)Ak chcete vykonať rozdelenie urobiť nasledovné:Založte registra s nulovými bity.

Zvýšil správu pridáte Z nulovej bity na koniec.

While (viac správ bitov)

Začať

Shift register vľavo o jeden bit, čítanie ďalšie bit zo

rozšírenej správy do registra bitové pozíciu 0.

If (a 1 bit bouchnutý z registra počas kroku 3)

Registrovať Registrovať = XOR vícepodlaž.

Koniec

Register teraz obsahuje zvyšok.(Poznámka: V praxi to znamená, IF podmienka môže byť testovaný pri testovaní na začiatok

bit R pred vykonaním zmeny.)Zavoláme algoritmus tejto "jednoduché".To môže vyzerať trochu chaotický, ale všetci sme sa naozaj robí

"odpočíta" rôznych mocností (tj shiftings) z poly z

správ, kým sa nič, ale zvyšok.
Študovať

manuálna príklady dlho divízie ak nechcete pochopiť.Malo by byť jasné, že vyššie uvedený algoritmus bude pracovať pre akúkoľvek šírku W.9.
Tabuľka A-Driven Implementácia

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

V JEDNODUCHÝCH algoritmu vyššie je dobrý východiskový bod, pretože

zodpovedá priamo do teórie prezentované tak ďaleko, a pretože je

tak jednoduché.
Avšak, pretože to funguje na bitovej úrovni, je skôr

nepříjemná pre kód (ani v C) a neefektívny vykonávať (má na

slučky raz za každý bit).
Chcete urýchli, musíme nájsť spôsob, ako sa

umožniť algoritmus pre spracovanie správy v jednotkách väčší ako jedna

kúsok.
Kandidátske množstvo křupky (4 bity), bytov (8 bitov), slov

(16 bitov) a longwords (32 bitov) a vyššia, ak sme schopní dosiahnuť.
Z

tieto 4 bity sa najlepšie vyhnúť, pretože to nezodpovedá byte

hranice.
Prinajmenšom žiadne zrýchlenie by nám umožňujú pracovať pri

byte hranice, a v skutočnosti väčšina z tabuľky riadeného algoritmy

prevádzkovať byte naraz.Na účely diskusie, dajte nám switch od 4-bit poly na

32-bit jedna.
Náš register vyzerá rovnaký, s výnimkou priestoru

predstavujú byty namiesto bitov a vícepodlaž je 33 bitov (jeden konkludentného

1 bit v hornej a 32 "aktívny" bitov) (Z = 32).3 2 1 0 Bytes

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

Pop!
<- | | | | | <----- Augmented správy

---- ---- ---- ---- 1 <------ 32 bitov ------>V JEDNODUCHÝCH algoritmus je stále platný.
Poďme preskúmať, čo to robí.

Predstavte si, že JEDNODUCHÉ algoritmus je v plnom prúde a zváži

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.

 

[Michel]

Hi geok,

Thanks for part one, can I have part two? If it is possible can you send it also in my mail box?

Thanks again,
D.