- Bevezetés a CRC számítások
- Ingyenes CRC számítás rutinok letölthető
Bevezetés a CRC számítások
Ha a digitális adatok tárolása vagy interfészes, adatvesztés következhet be. A számítástechnika kezdete óta az emberek gondolkodnak az ilyen típusú problémák kezelésének módjairól., A soros adatok jöttek fel a megoldást, hogy csatolja a paritás bit minden egyes küldött bájt. Ez az egyszerű észlelési mechanizmus akkor működik, ha egy bájtban páratlan számú bit megváltozik, de egy bájtban páros számú hamis bitet nem észlel a paritásellenőrzés. A probléma leküzdése érdekében az emberek matematikai hangmechanizmusokat kerestek több hamis bit észlelésére. Ennek eredménye volt a CRC-számítás vagy a ciklikus redundancia-ellenőrzés. Manapság a CRC számításokat minden típusú kommunikációban használják. A hálózati kapcsolaton keresztül küldött összes csomagot egy CRC ellenőrzi., A merevlemez minden egyes adatblokkjának CRC értéke is hozzá van csatolva. A modern számítógépes világ nem nélkülözheti ezeket a CRC számításokat. Tehát lássuk, miért olyan széles körben használják őket. A válasz egyszerű, erős, sokféle hibát észlel, rendkívül gyorsan kiszámítható, különösen akkor, ha dedikált hardveres chipeket használnak.
azt gondolhatnánk, hogy egy ellenőrző összeg helyettesítheti a megfelelő CRC számításokat. Minden bizonnyal könnyebb kiszámítani az ellenőrző összeget, de az ellenőrző összegek nem találnak minden hibát. Vegyünk egy példa karakterláncot, és számítsuk ki az egy bájtos ellenőrző összeget., A példa karakterlánc “Lammert”, amely átalakítja az ASCII értékeket . Ennek a tömbnek az egy bájtos ellenőrző összege az összes érték hozzáadásával kiszámítható, mint a 256-os osztással, a fennmaradó rész megtartásával. A kapott ellenőrző összeg 210. A fenti számológép segítségével ellenőrizheti ezt az eredményt.
ebben a példában egy byte hosszú ellenőrző összeget használtunk, amely 256 különböző értéket ad nekünk. Két bájtos ellenőrző összeg használatával 65,536 lehetséges különböző ellenőrző összegértékeket eredményez, és ha négy byte értéket használunk, akkor több mint négy milliárd lehetséges érték van., Arra a következtetésre juthatunk, hogy egy négy bájtos ellenőrző összegnél az esélye, hogy véletlenül nem észlelünk hibát, kevesebb, mint 1-4 milliárd. Elég jónak tűnik, de ez csak elmélet. A gyakorlatban a bitek nem változnak tisztán véletlenszerűen a kommunikáció során. Gyakran meghibásodnak, vagy elektromos tüskék miatt. Tegyük fel, hogy a példasorozatunkban az ” L “karakter legkisebb jelentős része van beállítva, a kommunikáció során pedig az” a ” karakter legkisebb jelentős része elvész. A vevő lesz, mint látni a tömb képviselő húr ” M ‘mert”., Az új karakterlánc ellenőrző összege továbbra is 210, de az eredmény nyilvánvalóan rossz, csak két bit megváltoztatása után. Még akkor is, ha négy byte hosszú ellenőrző összeget használtunk volna, nem észleltük volna ezt az átviteli hibát. Tehát az ellenőrző összeg kiszámítása egyszerű módszer lehet a hibák észlelésére, de nem nyújt sokkal több védelmet, mint a paritás bit, függetlenül az ellenőrző összeg hosszától.
az ötlet mögött egy ellenőrző érték kiszámítása egyszerű. Használjon olyan f(bval,cval) függvényt, amely egy adat bájtot, egy ellenőrző értéket ad be, és egy újraszámított ellenőrző értéket ad ki., Valójában a fent leírt ellenőrző összeg számításokat így lehet meghatározni. Az egy bájtos ellenőrző példa a következő funkcióval (C nyelven) számítható ki, amelyet a bemeneti karakterlánc minden egyes bájtjára ismételten hívunk. A cval kezdeti értéke 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
az ötlet mögött CRC számítás, hogy nézd meg az adatokat, mint egy nagy bináris szám. Ezt a számot egy bizonyos értékkel osztják el, a számítás fennmaradó részét CRC-nek nevezik., A CRC-számítás elosztása először úgy néz ki, hogy sok számítási teljesítménybe kerül, de nagyon gyorsan elvégezhető, ha az iskolában tanult módszerhez hasonló módszert használunk. Példaként kiszámítjuk az ” m ” karakter fennmaradó részét—amely 1101101 bináris jelölésben—úgy, hogy 19-re vagy 10011-re osztjuk. Felhívjuk figyelmét, hogy a 19 páratlan szám. Erre azért van szükség, mert látni fogjuk tovább. Kérjük, olvassa el a tankönyvek, mint a bináris számítási módszer itt nem nagyon különbözik a decimális módszer tanult, amikor fiatal volt. Lehet, hogy csak egy kicsit furcsának tűnik., A jelölések is különböznek az országok között, de a módszer hasonló.
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
decimális számításokkal gyorsan ellenőrizheti, hogy 109 osztva 19 ad hányadosa 5 a 14, mint a többi. De azt is látjuk, a rendszer, hogy minden kicsit extra, hogy ellenőrizze csak a költségek egy bináris összehasonlítás, 50% – ában egy bináris kivonás., Könnyen növelheti a teszt adatsor bitjeinek számát-például 56 bitre, ha a “Lammert”példaértéket használjuk—, az eredmény pedig 56 bináris összehasonlítással és átlagosan 28 bináris kivonással számítható ki. Ez a hardver közvetlenül csak nagyon kevés tranzisztorral valósítható meg. A szoftver algoritmusok is nagyon hatékonyak lehetnek.
a CRC számításokhoz normál kivonást nem használnak,de minden számítás modulo 2. Ebben a helyzetben figyelmen kívül hagyja a carry biteket, és valójában a kivonás egyenlő lesz egy exkluzív vagy művelettel., Ez furcsanak tűnik, a kapott maradéknak más értéke van, de algebrai szempontból a funkcionalitás egyenlő. Ennek megvitatásához egyetemi szintű ismeretekre lenne szükség az algebrai mezőelméletről, és azt hiszem, az olvasók nagy részét ez nem érdekli. Kérjük, nézze meg a dokumentum végét olyan könyvekhez, amelyek részletesen megvitatják ezt.
most már van egy CRC számítási módszerünk, amely mind hardverben, mind szoftverben megvalósítható, és randomabb érzés is van, mint egy közönséges ellenőrző összeg kiszámítása. De hogyan fog működni a gyakorlatban, ha egy vagy több Bit hibás?, Ha úgy döntünk, hogy az osztó—19 a példánkban—páratlan szám, akkor nincs szükség magas szintű matematikára, hogy minden egyes bithiba észlelhető legyen. Ez azért van, mert minden egyes bit hiba hagyja, hogy az osztalék változás a hatalom 2. Ha például kicsit n változásokat a 0, 1, értéke az osztalék növeli a 2n. Ha viszont kicsit n változásokat 1-től 0, értéke az osztalék csökken a 2n. Mert nem tudsz osztani minden hatalom a két páratlan szám, a többi a CRC számítás fog változni, de a hiba nem marad észrevétlen.,
a második helyzet, amelyet észlelni akarunk, amikor két egyetlen bit megváltozik az adatokban. Ehhez szükség van néhány matematika, amely olvasható Tanenbaum könyvében alább említett. Nagyon óvatosan kell kiválasztania az osztót, hogy megbizonyosodjon arról, hogy a két rossz Bit közötti távolságtól függetlenül mindig észleli őket. Ismeretes, hogy a CRC16 és CRC-CCITT számítások általánosan használt 0x8005 és 0x1021 értékei nagyon jól teljesítenek ebben a kérdésben., Kérjük, vegye figyelembe, hogy más értékeket lehet, vagy lehet, hogy nem, illetve nem könnyen számítani, amely osztó értéke megfelelő kimutatására két kis hibák, amelyek nem. Támaszkodnak kiterjedt matematikai kutatás ezt a kérdést tettem néhány évtizeddel ezelőtt a magasan képzett matematikus, majd az értékek ezek az emberek kapott.
továbbá a CRC számításunkkal minden olyan hibát szeretnénk észlelni, ahol páratlan számú bit változik. Ezt úgy lehet elérni, hogy egy osztó páros számú bitet állít be. A modulo 2 matematika segítségével megmutathatja, hogy minden hibát páratlan számú bittel észlelnek., Mint már mondtam, a modulo 2 matematikában a kivonási függvény helyébe az exkluzív vagy. Négy lehetséges XOR művelet létezik.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
látjuk, hogy a bitértékek minden kombinációjánál a kifejezés furcsasága változatlan marad. A páros bitszámú osztó kiválasztásakor a fennmaradó rész furcsasága megegyezik az osztalék furcsaságával. Ezért, ha az osztalék furcsasága megváltozik, mert páratlan számú bit változik, a fennmaradó rész is megváltozik., Tehát minden olyan hiba, amely páratlan számú bitet változtat meg, egy CRC számítással észlelhető, amelyet egy ilyen osztóval hajtanak végre. Lehet, hogy látta, hogy az általánosan használt 0x8005 és 0x1021 osztóértékek valójában páratlan számú bitet tartalmaznak, még az itt leírtak szerint sem. Ez azért van, mert az algoritmuson belül van egy “rejtett” extra bit 216, ami a ténylegesen használt osztó értékét 0x18005 és 0x11021 az algoritmuson belül.,
végül, de nem utolsósorban az összes tört hibát szeretnénk észlelni a CRC-számítással, amelynek maximális hossza észlelhető, és minden hosszabb tört hibát nagy valószínűséggel kell észlelni. A robbantási hiba meglehetősen gyakori a kommunikációban. Ez a hiba típusa a villámlás, a relé kapcsolása stb. ahol egy kis idő alatt az összes Bit egyre van állítva., Igazán értem, hogy ez neked is kell egy kis tudás a modulo 2 algebra, ezért kérem, fogadja el, hogy egy 16 bites osztója lesz képes felismerni minden borul a maximális hossza 16 bit, valamint minden hosszabb sorozatokat legalább 99.997% – os biztonsággal.
tiszta matematikai megközelítésben a CRC-számítást polinomszámításként írják le. Az osztó értékét leggyakrabban nem bináris számként írják le, hanem egy bizonyos rendű polinomként. A normális életben néhány polinomot gyakrabban használnak, mint mások., Ezen az oldalon az on-line CRC számításnál használt három a 16 bites széles CRC16 és CRC-CCIT, valamint a 32 bites széles CRC32. Ez utóbbit valószínűleg most használják leginkább, mert többek között ez a CRC generátor az összes hálózati forgalom ellenőrzéséhez és érvényesítéséhez.
mindhárom típusú CRC számítások van egy szabad szoftver könyvtár áll rendelkezésre. A tesztprogram közvetlenül használható fájlok vagy karakterláncok tesztelésére. Megnézheti a forráskódokat is, és integrálhatja ezeket a CRC rutinokat a saját programjába., Kérjük, vegye figyelembe a CRC számítás inicializálási értékeit, valamint az esetleges szükséges utófeldolgozást, például a forgácsolási biteket. Ha ezt nem teszi meg, előfordulhat, hogy más eredményeket kap, mint a többi CRC implementáció. Mindez elő-és utófeldolgozás történik a példaprogramban, így nem lehet nehéz, hogy a saját végrehajtása működik. Egy általánosan használt teszt az ASCII “123456789”karakterlánc CRC értékének kiszámítása., Ha a rutin eredménye megegyezik a tesztprogram eredményével vagy a weboldal eredményével, akkor az implementációja működik, és kompatibilis a legtöbb más implementációval.
csak referenciaként a polinom függvények a leggyakoribb CRC számítások. Kérjük, ne feledje, hogy a polinom legmagasabb rendű kifejezése (x16 vagy x32) nincs jelen a bináris szám ábrázolásában, hanem maga az algoritmus.,
| Irodalom | ||
| 2002 | számítógépes hálózatok, amelyek leírják a közös hálózati rendszereket és a megvalósításuk mögötti elméletet és algoritmusokat. | Andrew S. Tanenbaum |
| various | a számítógépes programozás művészete a fél numerikus algoritmusok fő referenciája. A polinomszámításokat részletesen ismertetjük. A matematika bizonyos szintje szükséges ahhoz, hogy teljes mértékben megértsük. | Donald E. Knuth |
| – | DNP 3.,0, vagy elosztott hálózati protokoll egy kommunikációs protokoll használatra tervezett között alállomás számítógépek, RTUs távoli terminál egységek, Ied intelligens elektronikus eszközök, mester állomások a közüzemi elektromos ipar. Ma már olyan ismert iparágakban is használják, mint a szennyvízkezelés, a szállítás, valamint az olaj-és gázipar. | DNP felhasználói csoport |
Vélemény, hozzászólás?