- Johdatus CRC-laskelmissa
- Ilmainen CRC-laskenta rutiinit ladata
Johdanto CRC-laskelmissa
Kun digitaalinen data on tallennettu tai käyttöliittymät, tietojen korruptiota saattaa esiintyä. Tietojenkäsittelytieteen alusta lähtien ihmiset ovat miettineet tapoja käsitellä tämäntyyppisiä ongelmia., Sarjatiedoissa he keksivät ratkaisun liittää pariteettibitin jokaiseen lähetettyyn tavuun. Tämä yksinkertainen havaitseminen mekanismi toimii, jos pariton määrä bittiä tavu muutoksia, mutta parillinen määrä vääriä bittiä on yksi tavu ei voida havaita pariteetti tarkistaa. Tämän ongelman ratkaisemiseksi ihmiset ovat etsineet matemaattisia äänimekanismeja useiden väärien bittien havaitsemiseksi. CRC: n laskelma tai syklinen irtisanomistarkastus oli tämän tulos. Nykyään CRC-laskelmia käytetään kaikentyyppisissä viestinnässä. Kaikki verkkoyhteyden kautta lähetetyt paketit tarkistetaan CRC: llä., Myös jokaisella kiintolevyn datalohkolla on siihen liitetty CRC-arvo. Moderni tietokonemaailma ei pärjää ilman näitä CRC-laskelmia. Katsotaan, miksi niitä käytetään niin paljon. Vastaus on yksinkertainen, ne ovat tehokkaita, havaitsevat monenlaisia virheitä ja ovat erittäin nopeita laskea varsinkin kun omistettu laitteisto pelimerkkejä käytetään.
voisi ajatella, että tarkistussumman käyttäminen voi korvata asianmukaiset CRC-laskelmat. Tarkistussumman laskeminen on varmasti helpompaa, mutta tarkistussummat eivät löydä kaikkia virheitä. Otetaan esimerkki merkkijonosta ja lasketaan yksi tavu tarkistussumma., Esimerkkijono on” Lammert”, joka muuntuu ASCII-arvoiksi . Yksi tavu tarkistussumma tämä joukko voidaan laskea lisäämällä kaikki arvot, kuin jakamalla se 256 ja pitää loput. Tuloksena oleva tarkistussumma on 210. Voit käyttää yllä olevaa laskinta tämän tuloksen tarkistamiseen.
tässä esimerkissä on käytetty yhden tavun mittaista tarkistussummaa, joka antaa meille 256 erilaista arvoa. Käyttämällä kaksi tavu tarkistussumma johtaa 65,536 mahdollista eri tarkistussumma arvot ja kun neljän tavun arvoa käytetään on yli neljä miljardia mahdolliset arvot., Voimme päätellä, että neljän tavun tarkistussummalla todennäköisyys, että emme vahingossa havaitse virhettä, on alle 1-4 miljardia. Vaikuttaa hyvältä, mutta tämä on vain teoriaa. Käytännössä bitit eivät muutu puhtaasti sattumanvaraisesti viestinnän aikana. Ne pettävät usein purkauksissa tai sähköpiikkien takia. Oletetaan, että esimerkissämme array alin merkittävä osa merkki ” L ”on asetettu, ja pienin merkittävä osa merkki” a ” menetetään viestinnän aikana. Vastaanotin kuin nähdä array edustaa merkkijono ” M ’mmert”., Tämän uuden merkkijonon tarkistussumma on vielä 210, mutta tulos on ilmeisen väärä, vasta kahden bittien vaihduttua. Vaikka olisimme käyttäneet neljän tavun mittaista tarkistussummaa, emme olisi havainneet tätä siirtovirhettä. Tarkistussumman laskeminen voi siis olla yksinkertainen menetelmä virheiden havaitsemiseksi, mutta se ei anna paljon enemmän suojaa kuin tarkistussumman pituudesta riippumaton pariteettibitti.
tarkastusarvolaskennan idea on yksinkertainen. Käytä funktio F(bval,cval), joka syöttää tiedot yhden tavun ja tarkista arvo ja tuottaa uudelleen tarkista arvo., Itse asiassa tarkistussummalaskelmat edellä kuvatulla tavalla voidaan määritellä tällä tavalla. Meidän ainoa tavu tarkistussumma esimerkki voisi on laskettu seuraava toiminto (C-kielellä), että me kutsumme toistuvasti kunkin tavu tulo merkkijono. Cval: n alkuarvo on 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
ajatuksena CRC-laskenta on tarkastella tietoja, kuten yksi suuri binary numero. Tämä luku jaetaan tietyllä arvolla ja loppuosa laskutoimituksesta kutsutaan CRC: ksi., Jakamalla CRC laskennan aluksi näyttää maksaa paljon laskentatehoa, mutta se voidaan suorittaa erittäin nopeasti, jos käyttää samanlaista menetelmää kuin yksi oppinut koulussa. Voimme esimerkkinä laskea loput merkin ” m ” —joka on 1101101 binary merkintätapa—jakamalla se 19 tai 10011. Huomaa, että 19 on pariton numero. Tämä on välttämätöntä, kuten tulemme näkemään edelleen. Katso kirjat kuten binary laskentamenetelmä täällä ei ole kovin erilainen kuin desimaalin tapa olet oppinut, kun olit nuori. Se voi näyttää vain hieman oudolta., Myös merkinnät eroavat maiden välillä, mutta menetelmä on samanlainen.
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
desimaalin laskelmat voit nopeasti tarkistaa, että 109 jaettuna 19 esitetään osamäärä 5 14 jäljellä. Mutta mitä näemme myös järjestelmässä on, että jokainen vähän ylimääräistä tarkistaa vain maksaa yhden binary vertailu ja 50% tapauksista yksi binary vähennyslasku., Voit helposti lisätä useita bittiä testituloksia string—esimerkiksi 56 bittiä, jos käytämme esimerkiksi arvo ”Lammert”—ja seurauksena voi olla laskettu 56 binary vertailuja ja keskimäärin 28 binary vähennyslaskua. Tämä voidaan toteuttaa laitteisto suoraan vain hyvin vähän transistorit mukana. Myös ohjelmistoalgoritmit voivat olla erittäin tehokkaita.
CRC-laskelmissa ei käytetä normaalia vähennyslaskua, vaan kaikki laskelmat tehdään modulo 2. Siinä tilanteessa et välitä kuljettaa bittiä ja itse asiassa vähennys on yhtä suuri kuin yksinomainen tai toiminta., Tämä näyttää oudolta, tuloksena loppuosa on eri arvo, mutta algebraic näkökulmasta toiminnallisuus on sama. Keskustelu tästä tarvitsisi yliopistotason tietoa algebrallisesta kenttäteoriasta, ja luulen, että suurin osa lukijoista ei ole kiinnostunut tästä. Katsokaa tämän asiakirjan loppuun kirjoja, jotka keskustelevat tästä yksityiskohtaisesti.
Nyt meillä on CRC-laskenta menetelmä, joka on toteutettavissa sekä laitteistojen ja ohjelmistojen, ja on myös enemmän satunnaisia tunne kuin laskettaessa tavallinen tarkistussumma. Mutta miten se toimii käytännössä, kun yksi Malmi lisää bittiä on väärässä?, Jos valitsemme divisor-19 meidän esimerkki-on pariton määrä, et tarvitse korkean tason matematiikkaa nähdä, että jokainen bit virhe havaitaan. Tämä johtuu siitä, että jokainen bittivirhe antaa osingon muuttua teholla 2. Jos esimerkiksi bit n muutokset 0: sta 1, arvo osinko kasvaa 2n. Jos toisaalta vähän n muutokset 1 0, arvo osinko vähenee 2n. Koska et voi jakaa mitään valtaa kaksi pariton määrä, loput CRC-laskenta muuttuu ja virhe jää huomaamatta.,
toinen tilanne halutaan havaita on, kun kaksi yhden bitin muutos tiedot. Tämä edellyttää jonkin verran matematiikkaa, joka voidaan lukea Tanenbaum ’ s kirja mainittu alla. Sinun täytyy valita jakaja hyvin huolellisesti olla varma, että riippumaton etäisyys kahden väärän bittiä aina tunnistaa ne. Tiedetään, että CRC16-ja CRC-CCITT-laskelmien yleisesti käytetyt arvot 0x8005 ja 0x1021 toimivat tässä kysymyksessä erittäin hyvin., Huomaa, että muut arvot ehkä tai ehkä ei, ja et voi helposti laskea mikä jakaja-arvo on sopiva havaita kahden bitin virheitä ja joka ei ole. Luottaa laaja matemaattinen tutkimus tästä asiasta tehnyt joitakin vuosikymmeniä sitten erittäin ammattitaitoista matemaatikot ja käyttää arvoja nämä ihmiset saatu.
– Lisäksi meidän CRC-laskenta haluamme havaita kaikki virheet, jos pariton määrä hieman muutoksia. Tämä voidaan saavuttaa käyttämällä divisor kanssa parillinen määrä bittiä asetettu. Modulo 2-matematiikalla voit osoittaa, että kaikki virheet, joissa on pariton määrä bittejä, havaitaan., Kuten olen sanonut aiemmin, modulo 2 matematiikassa vähennyslaskutoiminto korvataan eksklusiivisella tai. Mahdollisia XOR-operaatioita on neljä.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
näemme, että kaikki yhdistelmät bittisiä arvoja, oddness ilme pysyy samana. Kun valitset tekijä, jolla on parillinen määrä bittejä asetettu, oddness jäljellä on yhtä suuri oddness osingon. Jos siis osingon hajuaisti muuttuu, koska pariton määrä bittejä muuttuu, myös loppuosa muuttuu., Joten kaikki virheet, jotka muuttavat pariton määrä bittiä havaitaan CRC laskelma, joka suoritetaan tällaisen jakaja. Olet saattanut nähdä, että yleisesti käytetty jakaja arvot 0x8005 ja 0x1021 todella on pariton määrä bittejä, ja ei edes kuten tässä on esitetty. Tämä johtuu siitä, että algoritmin sisällä on” piilotettu ” ylimääräinen bitti 216, joka tekee todellisen käytetyn divisorin arvon 0x18005 ja 0x11021 algoritmin sisällä.,
Viimeisenä mutta ei vähäisimpänä haluamme tunnistaa kaikki räjähtää virheitä meidän CRC-laskenta, joiden suurin pituus on havaittu, ja kaikki enää räjähtää virheet voidaan havaita suurella todennäköisyydellä. Murtovirhe on melko yleinen viestinnässä. Se on tyyppi virhe, joka tapahtuu, koska salama, rele kytkentä, jne. jossa pienen ajanjakson aikana kaikki bitit asetetaan yhteen., Todella ymmärtää tämän sinun täytyy myös olla jonkin verran tietoa modulo 2, algebra, niin hyväksy, että 16-bittinen jakaja voit tunnistaa kaikki murtuu, joiden suurin pituus on 16 bittiä, ja kaikki pidempiä sarjoja, joissa on vähintään 99.997% varmuudella.
puhtaassa matemaattisessa lähestymistavassa CRC-laskenta kirjoitetaan polynomilaskelmiksi. Jakajan arvoa ei useimmiten kuvata binäärilukuna, vaan tietyn kertaluvun polynomina. Normaalielämässä joitakin polynomeja käytetään muita useammin., Kolme käytetään on-line CRC laskennan tällä sivulla on 16 bittiä leveä CRC16 ja CRC-CCITT ja 32 bittiä leveä CRC32. Jälkimmäistä käytetään todennäköisesti eniten nyt, koska se on muun muassa CRC-generaattori kaikille verkkoliikenteen todentamiselle ja validoinnille.
kaikilla kolmella CRC-laskutyypillä minulla on ilmainen ohjelmistokirjasto saatavilla. Testiohjelmaa voidaan käyttää suoraan tiedostojen tai merkkijonojen testaamiseen. Voit myös tarkastella lähdekoodeja ja integroida nämä CRC-rutiinit omaan ohjelmaasi., Ole tietoinen CRC-laskennan alustusarvoista ja mahdollisista tarvittavista jälkikäsittelystä, kuten flipping-biteistä. Jos et tee tätä, saatat saada erilaisia tuloksia kuin muut CRC toteutuksia. Kaikki tämä esi-ja jälkikäsittely tehdään esimerkkiohjelmassa, joten ei pitäisi olla vaikeaa saada omaa toteutusta toimimaan. Yleinen käytetty testi on laskea ASCII-merkkijonon CRC-arvo ”123456789”., Jos rutiinisi tulos vastaa testiohjelman tulosta tai tämän verkkosivuston tulosta, toteutuksesi toimii ja on yhteensopiva useimpien muiden toteutusten kanssa.
juuri vertailukohtana yleisimpien CRC-laskelmien polynomifunktiot. Muista, että korkeimman asteen termi polynomilla (x16 tai x32) ei ole läsnä binary numero edustus, mutta epäsuorasti itse algoritmiin.,
| Kirjallisuus | ||
| 2002 | tietoverkkojen, jossa kuvataan yhteiset verkon järjestelmiä ja teoriaa ja algoritmeja takana niiden toteuttamista. | Andrew S. Tanenbaum |
| eri | The Art of Computer Programming on tärkein viittaus semi-numeerisia algoritmeja. Polynomilaskelmat on kuvattu perusteellisesti. Jonkin verran matematiikkaa on tarpeen täysin ymmärtää sitä kuitenkin. | Donald E. Knuth |
| – | DNP 3.,0, tai distributed network protocol on tiedonsiirtoprotokolla, joka on suunniteltu käytettäväksi välillä sähköasema tietokoneet, Rtu, remote terminal units, Ied intelligent electronic devices ja master asemia electric utility industry. Nykyisin sitä käytetään myös tutuilla toimialoilla, kuten jätevesien käsittelyssä, kuljetuksissa sekä öljy-ja kaasuteollisuudessa. | DNP User Group |
Vastaa