- Úvod na CRC výpočtů
- Zdarma CRC výpočtu rutiny pro stažení
Úvod na CRC výpočtů
vždy, když digitální data jsou uložena nebo rozhraním, poškození dat může dojít. Od začátku informatiky lidé přemýšlejí o způsobech, jak se s tímto typem problému vypořádat., Pro sériová data přišli s řešením připojit paritní bit ke každému odeslanému bajtu. Tento jednoduchý detekční mechanismus funguje, pokud se změní lichý počet bitů v bajtu, ale sudý počet falešných bitů v jednom bajtu nebude detekován kontrolou parity. K překonání tohoto problému lidé hledali matematické zvukové mechanismy pro detekci více falešných bitů. Výsledkem byl výpočet CRC nebo kontrola cyklické redundance. V současné době se výpočty CRC používají ve všech typech komunikací. Všechny pakety odeslané přes síťové připojení jsou kontrolovány pomocí CRC., Také každý datový blok na pevném disku má k němu připojenou hodnotu CRC. Moderní počítačový svět se bez těchto výpočtů CRC neobejde. Podívejme se tedy, proč jsou tak široce používány. Odpověď je jednoduchá, jsou výkonná, detekují mnoho typů chyb a jsou extrémně rychlé pro výpočet, zejména při použití vyhrazených hardwarových čipů.
člověk by si mohl myslet, že použití kontrolního součtu může nahradit správné výpočty CRC. Je jistě snazší vypočítat kontrolní součet, ale kontrolní součty nenajdou všechny chyby. Umožňuje vzít příklad řetězec a vypočítat jeden byte kontrolní součet., Příklad řetězec je“ Lammert“, který převádí na hodnoty ASCII . Kontrolní součet jednoho byte tohoto pole lze vypočítat přidáním všech hodnot, než vydělením 256 a ponecháním zbytku. Výsledný kontrolní součet je 210. Ke kontrole tohoto výsledku můžete použít kalkulačku výše.
v tomto příkladu jsme použili jeden byte dlouhý kontrolní součet, který nám dává 256 různých hodnot. Použití dvoubajtového kontrolního součtu bude mít za následek 65,536 možných různých hodnot kontrolního součtu a při použití hodnoty čtyř bajtů existuje více než čtyři miliardy možných hodnot., Můžeme dojít k závěru, že s kontrolním součtem čtyř bajtů je šance, že náhodně nezjistíme chybu, menší než 1 až 4 miliardy. Vypadá to docela dobře, ale je to jen teorie. V praxi se bity během komunikace nemění čistě náhodně. Často selhávají v dávkách nebo v důsledku elektrických hrotů. Předpokládejme, že v našem příkladovém poli je nastaven nejnižší významný bit znaku “ L „a během komunikace se ztratí nejnižší významný bit znaku „a“. Přijímač bude více než vidět pole představující řetězec “ M ‚mmert“., Kontrolní součet pro tento nový řetězec je stále 210, ale výsledek je zjevně špatný, až po změně dvou bitů. I kdybychom použili čtyři byte dlouhý kontrolní součet, nezjistili bychom tuto chybu přenosu. Výpočet kontrolního součtu tedy může být jednoduchou metodou pro detekci chyb, ale neposkytuje mnohem větší ochranu než paritní bit, nezávisle na délce kontrolního součtu.
myšlenka výpočtu hodnoty kontroly je jednoduchá. Použití funkce F(bval,cval) vstupů, jeden datový byte a zkontrolujte hodnotu a výstupy přepočítána hodnota., Ve skutečnosti výpočty kontrolního součtu, jak je popsáno výše, lze definovat tímto způsobem. Náš příklad kontrolního součtu jednoho bytu mohl být vypočítán s následující funkcí (v jazyce C), kterou opakovaně voláme pro každý bajt ve vstupním řetězci. Počáteční hodnota pro cval je 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
myšlenka výpočet CRC, je podívat se na data jako jeden velký binární číslo. Toto číslo je děleno určitou hodnotou a zbytek výpočtu se nazývá CRC., Dělení ve výpočtu CRC zpočátku vypadá, že stojí hodně výpočetního výkonu, ale může být provedeno velmi rychle, pokud použijeme metodu podobnou té, která se naučila ve škole. Budeme jako příklad vypočítat zbytek za znak “ m “ —což je 1101101 v binární notaci—vydělením 19 nebo 10011. Vezměte prosím na vědomí, že 19 je liché číslo. To je nezbytné, jak uvidíme dále. Podívejte se prosím na vaše učebnice, protože metoda binárního výpočtu se zde příliš neliší od desítkové metody, kterou jste se naučili, když jste byli mladí. Mohlo by to vypadat trochu divně., Také notace se liší mezi zeměmi, ale metoda je podobná.
1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder
S desetinná výpočty, můžete rychle zkontrolovat, že 109 děleno 19 dává kvocient 5 s 14 jako zbytek. V schématu však také vidíme, že každý kousek navíc ke kontrole stojí pouze jedno binární srovnání a v 50% případů jedno binární odčítání., Můžete snadno zvýšit počet bitů testovací data řetězec—například na 56 bitů, pokud použijeme náš příklad hodnota „Lammert“—a výsledek může být vypočtena s 56 binární porovnávání a průměru 28 binární odčítání. To může být implementováno v hardwaru přímo s jen velmi málo tranzistorů zapojených. Také softwarové algoritmy mohou být velmi efektivní.
pro výpočty CRC se nepoužívá žádné normální odčítání, ale všechny výpočty se provádějí modulo 2. V této situaci budete ignorovat nést bity a ve skutečnosti odčítání se bude rovnat exkluzivní nebo operace., To vypadá divně, výsledný zbytek má jinou hodnotu, ale z algebraického hlediska je funkčnost stejná. Diskuse o tom by vyžadovala vysokoškolské znalosti algebraické teorie pole a myslím, že většina čtenářů o to nemá zájem. Podívejte se prosím na konec tohoto dokumentu pro knihy, které o tom podrobně diskutují.
nyní máme metodu výpočtu CRC, která je implementovatelná v hardwaru i softwaru a má také náhodnější pocit než výpočet běžného kontrolního součtu. Ale jak to bude fungovat v praxi, když jedna ruda více bitů jsou špatné?, Pokud zvolíme dělitel-19 v našem příkladu – jako liché číslo, nepotřebujete matematiku na vysoké úrovni, abyste viděli, že bude detekována každá chyba bitů. Je to proto, že každá chyba bitů umožní změnu dividendy s výkonem 2. Pokud například bit n mění od 0 do 1, hodnota dividendy se bude zvyšovat s 2n. Pokud na druhou stranu trochu se n mění od 1 do 0, hodnota dividendy se bude snižovat s 2n. Protože nemůžete dělit žádnou mocí dvě liché číslo, zbytek CRC výpočet bude měnit a chyba nebude bez povšimnutí.,
druhá situace, kterou chceme zjistit, je, když se v datech změní dva jednotlivé bity. To vyžaduje nějakou matematiku, kterou lze přečíst v Tanenbaumově knize uvedené níže. Musíte si velmi pečlivě vybrat dělitele, abyste se ujistili, že nezávisle na vzdálenosti mezi dvěma chybnými bity je vždy zjistíte. Je známo, že běžně používané hodnoty 0x8005 a 0x1021 výpočtů CRC16 a CRC-CCITT jsou v tomto problému velmi dobré., Vezměte prosím na vědomí, že jiné hodnoty, mohou nebo nemusí, a nelze snadno vypočítat, které dělitel hodnota je vhodná pro detekci dvou bitové chyby a který není. Spoléhat na rozsáhlý matematický výzkum na toto téma provedeno několik desetiletí před tím, že vysoce kvalifikovaní matematici a použít hodnoty tyto lidi získat.
navíc s naším výpočtem CRC chceme detekovat všechny chyby, kde se změní lichý počet bitů. Toho lze dosáhnout použitím dělitele se sudým počtem bitů. Pomocí matematiky modulo 2 můžete ukázat, že jsou detekovány všechny chyby s lichým počtem bitů., Jak jsem již řekl, v matematice modulo 2 je funkce odčítání nahrazena exkluzivní nebo. Existují čtyři možné operace XOR.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
vidíme, že pro všechny kombinace bitové hodnoty, zvláštnost výraz zůstává stejný. Při výběru dělitele se sudým počtem nastavených bitů se zvláštnost zbytku rovná zvláštnosti dividendy. Pokud se tedy změní podivnost dividendy, protože se změní lichý počet bitů, zbytek se také změní., Takže všechny chyby, které mění lichý počet bitů, budou detekovány výpočtem CRC, který se provádí s takovým dělitelem. Možná jste viděli, že běžně používané hodnoty dělitele 0x8005 a 0x1021 mají ve skutečnosti lichý počet bitů, a to ani tak, jak je uvedeno zde. Je to proto, že uvnitř algoritmu je „skrytý“ navíc trochu 216, který dělá skutečné použit dělitel hodnota 0x18005 a 0x11021 uvnitř algoritmu.,
v neposlední řadě chceme zjistit všechny roztržení chyby s naší CRC výpočtu s maximální délkou má být detekován, a všechny delší praskla chyb zjištěných s vysokou pravděpodobností. Chyba výbuchu je v komunikaci poměrně častá. Jedná se o typ chyby, ke které dochází kvůli blesku, spínání relé atd. kde během malého období jsou všechny bity nastaveny na jeden., Opravdu pochopit, to také musíte mít nějaké znalosti o modulo 2 algebry, tak prosím přijměte, že s 16-bitový dělitel, budete moci zjistit všechny výbuchy s maximální délkou 16 bitů, a všechny delší praskne s alespoň 99.997% jistotou.
v čistě matematickém přístupu je výpočet CRC zapsán jako polynomiální výpočty. Hodnota dělitele není nejčastěji popsána jako binární číslo, ale polynom určitého pořadí. V normálním životě se některé polynomy používají častěji než jiné., Tři použité v on-line výpočtu CRC na této stránce jsou 16 bit široký CRC16 a CRC-CCITT a 32 bitů široký CRC32. Ten je nyní pravděpodobně nejpoužívanější, protože mimo jiné je generátorem CRC pro veškeré ověřování a ověřování síťového provozu.
pro všechny tři typy výpočtů CRC mám k dispozici knihovnu svobodného softwaru. Testovací program lze použít přímo k testování souborů nebo řetězců. Můžete se také podívat na zdrojové kódy a integrovat tyto rutiny CRC do vlastního programu., Mějte prosím na paměti Inicializační hodnoty výpočtu CRC a možné nezbytné následné zpracování, jako je převrácení bitů. Pokud tak neučiníte, můžete získat jiné výsledky než jiné implementace CRC. To vše před a po zpracování se provádí v příkladu programu, takže by nemělo být obtížné, aby vaše vlastní implementace fungovala. Běžně používaným testem je výpočet hodnoty CRC pro řetězec ASCII „123456789“., Pokud výsledek vaší rutiny odpovídá výsledku testovacího programu nebo výsledku na tomto webu, vaše implementace funguje a je kompatibilní s většinou ostatních implementací.
stejně jako odkaz na polynomiální funkce pro nejběžnější výpočty CRC. Nezapomeňte, že termín nejvyššího řádu polynomu (x16 nebo x32) není přítomen v reprezentaci binárních čísel, ale implikovaný samotným algoritmem.,
| Literatuře | ||
| 2002 | Počítačové Sítě, popisující běžné síťové systémy a teorie a algoritmy za jejich provádění. | Andrew s. Tanenbaum |
| různé | umění počítačového programování je hlavním odkazem na semimerické algoritmy. Polynomiální výpočty jsou popsány do hloubky. Určitá úroveň matematiky je však nezbytná k tomu, aby ji plně pochopila. | Donald E. Knuth |
| – | DNP 3.,0, nebo distribuované sítě protokol je komunikační protokol navržený pro použití mezi rozvodny počítače, RTUs remote terminal units, Ied inteligentní elektronické zařízení a master stanice pro electric utility průmyslu. Nyní se také používá ve známých průmyslových odvětvích, jako je čištění odpadních vod, doprava a ropný a plynárenský průmysl. | DNP Skupiny Uživatelů |
Napsat komentář