Syklinen redundanssikoodi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. tammikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Syklinen redundanssitarkistus _ _ , CRC [1] ) on algoritmi tarkistussumman löytämiseksi,suunniteltu tarkistamaan tietojen eheys [2] . CRC on käytännöllinen virheenkorjaavan koodauksen sovellus, joka perustuu syklisen koodin tiettyihin matemaattisiin ominaisuuksiin .

Johdanto

Syklisten koodien käsite on melko laaja [3] . Englanninkielisessä kirjallisuudessa CRC ymmärretään kahdella tavalla kontekstista riippuen: Cyclic Redundancy Code tai Cyclic Redundancy Check [4] . Ensimmäinen käsite tarkoittaa syklisten koodien matemaattista ilmiötä, toinen - tämän ilmiön erityistä soveltamista hash-funktiona .

Sykliset koodit eivät ole vain helppoja toteuttaa, vaan niillä on myös se etu, että ne sopivat purskevirheiden havaitsemiseen: jatkuvat virheellisten datamerkkien sekvenssit viesteissä. Tämä on tärkeää, koska purskevirheet ovat yleisiä lähetysvirheitä monissa viestintäkanavissa, mukaan lukien magneettiset ja optiset tallennuslaitteet. Tyypillisesti n-bittinen CRC, jota sovelletaan mielivaltaisen pituiseen datalohkoon ja jonka tarkistussumma välittömästi seuraa dataa, havaitsee minkä tahansa yksittäisen virhepurskeen, joka on enintään n bittiä, ja sen osuuden kaikista pidemmistä virhepurskeista. havaitsee on (1 − 2 −n ).

Kohinaa korjaava koodaus

Ensimmäiset yritykset luoda koodeja, joissa on ylimääräistä tietoa, alkoivat kauan ennen nykyaikaisten tietokoneiden tuloa. Esimerkiksi 1960-luvulla Reed ja Solomon kehittivät tehokkaan koodaustekniikan - Reed-Solomon Coden . Sen käyttö ei tuolloin ollut mahdollista, koska ensimmäiset algoritmit eivät pystyneet suorittamaan dekoodaustoimintoa kohtuullisessa ajassa . Berlekampin perusteos , joka julkaistiin vuonna 1968, päätti tämän ongelman . Tätä tekniikkaa , jonka käytännön soveltamiseen Massey huomautti vuotta myöhemmin , käytetään edelleen digitaalisissa laitteissa, jotka vastaanottavat RS-koodattua dataa tähän päivään asti. Lisäksi: tämä järjestelmä sallii paitsi paikkojen määrittämisen, myös virheellisten koodisymbolien (useimmiten oktettien ) korjaamisen.

Mutta ei ole läheskään aina, että virheen korjaus vaaditaan koodista . Monilla nykyaikaisilla viestintäkanavilla on hyväksyttävät ominaisuudet, ja usein riittää, että tarkistetaan, onnistuiko siirto tai oliko vaikeuksia; virheiden rakenne ja virheellisten symbolien erityiset paikat eivät kiinnosta vastaanottavaa osapuolta ollenkaan. Ja näissä olosuhteissa tarkistussummia käyttävät algoritmit osoittautuivat erittäin onnistuneiksi ratkaisuiksi. CRC soveltuu parhaiten tällaisiin tehtäviin: alhaiset resurssikustannukset, helppokäyttöisyys ja lineaaristen syklisten koodien teoriasta jo muodostunut matemaattinen laitteisto varmistivat sen valtavan suosion.

Vaikka CRC-koodia käytetään yleensä vain virheiden havaitsemiseen, sen matemaattiset ominaisuudet mahdollistavat yksittäisen virheen löytämisen ja korjaamisen bittilohkossa, jos jokaisella suojatun lohkon bitillä (mukaan lukien tarkistusbitit) on oma ainutlaatuinen jäännös jaettuna. generaattoripolynomin mukaan. Esimerkiksi, jos generoiva polynomi on redusoitumaton ja lohkon pituus ei ylitä generoidun syklisen ryhmän järjestystä.

Tarkistussumma

Yleensä tarkistussumma on arvo, joka lasketaan tietyn kaavion mukaan koodatun viestin perusteella. Tarkastustiedot systemaattisessa koodauksessa osoitetaan lähetetylle datalle. Vastaanottavalla puolella tilaaja tietää tarkistussumman laskemisalgoritmin: vastaavasti ohjelma pystyy tarkistamaan vastaanotettujen tietojen oikeellisuuden.

Kun paketteja lähetetään verkkokanavan kautta, lähdetiedot voivat vääristyä useiden ulkoisten vaikutusten vuoksi: sähköhäiriöt, huonot sääolosuhteet ja monet muut. Tekniikan ydin on, että tarkistussumman hyvillä ominaisuuksilla suurimmassa osassa tapauksista virhe viestissä johtaa sen tarkistussumman muutokseen. Jos alkuperäinen ja laskettu summa eivät ole samat, päätetään vastaanotetun tiedon pätemättömyydestä ja voidaan pyytää paketin uudelleenlähetystä.

Matemaattinen kuvaus

CRC-algoritmi perustuu jaon ominaisuuksiin binääripolynomien jäännöksellä, eli äärellisen kentän polynomeilla . CRC - arvo on olennaisesti tuloa vastaavan polynomin jakamisen jäännös jollakin kiinteällä generaattoripolynomilla . $GF(2)$

Jokainen äärellinen bittisekvenssi on yksi yhteen liitetty binääripolynomiin, jonka kerroinsekvenssi on alkuperäinen sekvenssi. Esimerkiksi bittisekvenssi 1011010 vastaa polynomia: $a_0, a_1, \pisteet, a_{N-1}$ $\textstyle\sum_{n=0}^{N-1} a_n x^n$

P(x) = 1\cpiste x^6 + 0\cpiste x^5 + 1\cpiste x^4 + 1\cpiste x^3 + 0\cpiste x^2 + 1\cpiste x^1 + 0\cpiste x^0 = x^6 + x^4 + x^3 + x^1.

Erillisten polynomien lukumäärä, joiden aste on pienempi kuin on yhtä suuri kuin , mikä on sama kuin kaikkien pituisten binäärisekvenssien lukumäärä . $N$ $2^N$ $N$

Algoritmin tarkistussumman arvo, jolla on generoiva polynomiaste, määritellään pituudeksi bittisekvenssiksi , joka edustaa polynomia , joka johtaa tulobittivirtaa edustavan polynomin jakamiseen polynomilla : $G(x)$ $N$ $N$ $R(x)$ $P(x)$ $G(x)$

R(x) = P(x)\cdot x^N\, \bmod\, G(x)

missä

R(x)

on polynomi, joka edustaa CRC-arvoa;

P(x)

on polynomi, jonka kertoimet edustavat syöttödataa;

G(x)

on generoiva polynomi;

N

on generoivan polynomin aste.

Kertominen suoritetaan antamalla syöttösekvenssille nolla bittiä, mikä parantaa lyhyiden syöttösekvenssien hajautuslaatua. $x^N$ $N$

Kun jaetaan erilaisten alkuperäisten polynomien jäännöksellä generoivalla astepolynomilla , jaosta voidaan saada erilaisia jäännöksiä. on usein redusoitumaton polynomi . Se valitaan yleensä tiivistefunktiolle asetettujen vaatimusten mukaisesti kunkin tietyn sovelluksen yhteydessä. $G(x)$ $N$ $2^{N}$ $G(x)$

On kuitenkin monia standardoituja polynomigeneraattoreita, joilla on hyvät matemaattiset ja korrelaatioominaisuudet (vähimmäismäärä törmäyksiä , laskennan helppous), joista osa on lueteltu alla.

CRC-laskenta

Algoritmin parametrit

Yksi CRC:n pääparametreista on generoiva polynomi.

Toinen generaattoripolynomiin liittyvä parametri on sen aste , joka määrittää CRC-arvon laskemiseen käytettyjen bittien lukumäärän. Käytännössä yleisimpiä ovat 8-, 16- ja 32-bittiset sanat, mikä on seurausta modernin tietotekniikan arkkitehtuurin erityispiirteistä.

Toinen parametri on sanan aloitusarvo. Nämä parametrit määrittelevät täysin "perinteisen" CRC-laskentaalgoritmin. Algoritmiin on myös muunnelmia, esimerkiksi käyttämällä käänteistä käsittelybittien järjestystä.

Toimenpiteen kuvaus

Ensimmäinen sana on otettu tiedostosta - se voi olla bitti (CRC-1), tavu (CRC-8) tai mikä tahansa muu elementti. Jos sanan merkittävin bitti on "1", sanaa siirretään yhden bitin verran vasemmalle, minkä jälkeen suoritetaan XOR -operaatio generoivalla polynomilla. Vastaavasti, jos sanan merkittävin bitti on "0", XOR-toimintoa ei suoriteta siirron jälkeen. Siirron jälkeen merkittävin bitti katoaa ja seuraava bitti tiedostosta ladataan vähiten merkitsevän bitin tilalle, ja toimintoa toistetaan, kunnes tiedoston viimeinen bitti on ladattu. Kun koko tiedosto on käyty läpi, loppuosa jää sanaan, joka on tarkistussumma.

Suositut ja standardoidut polynomit

Vaikka sykliset redundanssikoodit ovat osa standardeja, tällä termillä ei ole yleisesti hyväksyttyä määritelmää - eri kirjoittajien tulkinnat ovat usein ristiriidassa keskenään [1] [5] .

Tämä paradoksi koskee myös generaattoripolynomin valintaa: usein standardoidut polynomit eivät ole tehokkaimpia niiden vastaavan tarkistusredundanssikoodin tilastollisten ominaisuuksien kannalta .

Monet laajalti käytetyt polynomit eivät kuitenkaan ole tehokkaimpia kaikista mahdollisista. Vuosina 1993-2004 ryhmä tutkijoita tutki polynomien generoimista, joiden kapasiteetti on enintään 16 [1] 24 ja 32 bittiä [6] [7] ja löysi polynomeja, jotka antavat paremman suorituskyvyn kuin standardoidut polynomit koodietäisyyden suhteen . [7] . Yksi tämän tutkimuksen tuloksista on jo löytänyt tiensä iSCSI - protokollaan .

Suosituinta ja suositeltua IEEE -polynomia CRC-32:lle käytetään Ethernetissä , FDDI :ssä ; myös tämä polynomi on Hamming -koodigeneraattori [8] . Toisen polynomin - CRC-32C - avulla voit saavuttaa saman suorituskyvyn alkuperäisen viestin pituudella 58 bitistä 131 kbps:iin, ja joillain syöttöviestin pituusalueilla se voi olla jopa suurempi, joten se on myös suosittu nykyään [7] . Esimerkiksi ITU-T G.hn -standardi käyttää CRC-32C:tä havaitsemaan virheet hyötykuormassa.

Alla olevassa taulukossa on lueteltu yleisimmät polynomit - CRC-generaattorit. Käytännössä CRC:n laskenta voi sisältää esi- ja jälkiinversion sekä käänteisen bittikäsittelyn järjestyksen. CRC:n omat toteutukset käyttävät nollasta poikkeavia alkurekisteriarvoja, mikä tekee koodista vaikeampaa jäsentää .

Nimi	Polynomi	Esitykset: [9] normaali / käänteinen / käänteinen käänteisestä
CRC-1	$x+1$ (käytetään laitteistovirheiden tarkistuksessa; tunnetaan myös pariteettibittinä )	0x1 / 0x1 / 0x1
CRC-4-ITU	$x^{4}+x+1$ ( ITU G.704 [10] )	0x3 / 0xC / 0x9
CRC-5-EPC	$x^5 + x^3 + 1$ ( Gen 2 RFID [11] )	0x09 / 0x12 / 0x14
CRC-5-ITU	$x^5 + x^4 + x^2 + 1$ ( ITU G.704 [12] )	0x15 / 0x15 / 0x1A
CRC-5-USB	$x^5 + x^2 + 1$ ( USB -tunnuspaketit)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ ( ITU G.704 [13] )	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (tietoliikennejärjestelmät, ITU-T G.707 [14] , ITU-T G.832 [15] , MMC , SD )	0x09 / 0x48 / 0x44
CRC-8- CCITT	$x^8 + x^2 + x + 1$ ( ATM HEC ), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8- Dallas / Maxim	$x^8 + x^5 + x^4 + 1$ ( 1-johtiminen väylä )	0x31 / 0x8C / 0x98
CRC-8	$x^8 + x^7 + x^6 + x^4 + x^2 + 1$ ( ETSI EN 302 307 [16] , 5.1.4)	0xD5 / 0xAB / 0xEA [1]
CRC-8-SAE J1850	$x^8 + x^4 + x^3 + x^2 + 1$	0x1D / 0xB8 / 0x8E
CRC-10	$x^{10} + x^9 + x^5 + x^4 + x + 1$	0x233 / 0x331 / 0x319
CRC-11	$x^{11} + x^9 + x^8 + x^7 + x^2 + 1$ ( FlexRay [17] )	0x385 / 0x50E / 0x5C2
CRC-12	$x^{12} + x^{11} + x^3 + x^2 + x + 1$ (televiestintäjärjestelmät [18] [19] )	0x80F / 0xF01 / 0xC07
CRC-15- CAN	$x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1$	0x4599 / 0x4CD1 / 0x62CC
CRC-16- IBM	$x^{16} + x^{15} + x^2 + 1$ ( Bisync , Modbus , USB , ANSI X3.28 [20] , monet muut; tunnetaan myös nimellä CRC-16 ja CRC-16-ANSI )	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$ ( X.25 , HDLC , XMODEM , Bluetooth , SD jne.)	0x1021 / 0x8408 / 0x8810 [1]
CRC-16- T10 - DIF	$x^{16} + x^{15} + x^{11} + x^{9} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ ( SCSI DIF)	0x8BB7 [21] / 0xEDD1 / 0xC5DB
CRC-16- DNP	$x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1$ (DNP, IEC 870 , M-Bus )	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher	Ei CRC; katso Fletcherin tarkistussumma	Käytetty Adler-32 A&B CRC: ssä
CRC-24	$x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^ {11} + x^{10} + x^8 + x^7 + x^6 + x^3 + x + 1$ ( FlexRay [17] )	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24 Radix-64	$x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1$ ( OpenPGP )	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	$x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^ {8} + x^{7} + x^{6} + x^{2} + x + 1$ ( CDMA )	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler	Ei CRC; katso Adler-32	Katso Adler-32
CRC-32 - IEEE 802.3	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^ 8 + x^7 + x^5 + x^4 + x^2 + x + 1$ ( V.42 , MPEG-2 , PNG [22] , POSIX cksum )	0x04C11DB7 / 0xEDB88320 / 0x82608EDB [7]
CRC-32C (Castagnoli)	$x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^ {19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1$ ( iSCSI , G.hn hyötykuorma)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0 [7]
CRC-32K (Koopman)	$x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^ {16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1$	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B [7]
CRC-32Q	$x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^ {5} + x^{3} + x + 1$ (ilmailu; AIXM [23] )	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	$x^{64} + x^4 + x^3 + x + 1$ ( HDLC - ISO 3309 )	0x000000000000001B / 0xD800000000000000 / 0x8000000000000000D
CRC-64- ECMA	$x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^ {46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} +$ $x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^ {19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1$ [24]	0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

Nykyiset standardit CRC-128 (IEEE) ja CRC-256 (IEEE) tällä hetkellä[ milloin? ] on korvattu kryptografisilla hash-funktioilla .

CRC-algoritmin tekniset tiedot

Yksi tunnetuimmista on Ross N. Williamsin tekniikka [25] . Se käyttää seuraavia vaihtoehtoja:

Algoritmin nimi ( nimi );

Polynomin muodostavan tarkistussumman aste ( leveys );

Itse generoiva polynomi ( poly ). Jotta se voidaan kirjoittaa arvoksi, se kirjoitetaan ensin bittijonona, kun taas merkitsevin bitti jätetään pois - se on aina 1. Esimerkiksi polynomi tässä merkinnässä kirjoitetaan numerona . Mukavuuden vuoksi tuloksena oleva binääriesitys kirjoitetaan heksadesimaalimuodossa . Meidän tapauksessamme se on yhtä suuri tai 0x11; $x^8+x^4+1$ $00010001_2$ $11_h$

Aloitustiedot ( init ), eli rekisterien arvot laskennan alkamishetkellä;

Laskennan alkamista ja suuntaa ilmaisevan lipun ( RefIn ) on vastattava kanavan lähetysjärjestystä virhepurskeiden havaitsemiseksi. Vaihtoehtoja on kaksi: False - alkaa merkittävimmällä bitillä ( MSB -first) tai True - alkaa vähiten merkitsevästä bitistä ( LSB -first);

Lippu ( RefOut ), joka määrittää, onko rekisteribittien järjestys käänteinen, kun XOR -elementtiä syötetään ;

Numero ( XorOut ) , johon tulos lisätään modulo 2 ;

CRC-arvo ( check ) merkkijonolle "123456789" .

Esimerkkejä [26]

Nimi	Leveys	Poly	Sen sisällä	RefIn	Ref Out	XorOut	Tarkistaa
CRC-3/ROHC	3	0x3	0x7	totta	totta	0x0	0x6
CRC-4/ITU	neljä	0x3	0x0	totta	totta	0x0	0x7
CRC-5/EPC	5	0x9	0x9	väärä	väärä	0x0	0x0
CRC-5/ITU	5	0x15	0x0	totta	totta	0x0	0x7
CRC-5/USB	5	0x5	0x1F	totta	totta	0x1F	0x19
CRC-6/CDMA2000-A	6	0x27	0x3F	väärä	väärä	0x0	0xD
CRC-6/CDMA2000-B	6	0x7	0x3F	väärä	väärä	0x0	0x3B
CRC-6/DARC	6	0x19	0x0	totta	totta	0x0	0x26
CRC-6/ITU	6	0x3	0x0	totta	totta	0x0	0x6
CRC-7	7	0x9	0x0	väärä	väärä	0x0	0x75
CRC-7/ROHC	7	0x4F	0x7F	totta	totta	0x0	0x53
CRC-8	kahdeksan	0x7	0x0	väärä	väärä	0x0	0xF4
CRC-8/CDMA2000	kahdeksan	0x9B	0xFF	väärä	väärä	0x0	0xDA
CRC-8/DARC	kahdeksan	0x39	0x0	totta	totta	0x0	0x15
CRC-8/DVB-S2	kahdeksan	0xD5	0x0	väärä	väärä	0x0	0xBC
CRC-8/EBU	kahdeksan	0x1D	0xFF	totta	totta	0x0	0x97
CRC-8/I-KOODI	kahdeksan	0x1D	0xFD	väärä	väärä	0x0	0x7E
CRC-8/ITU	kahdeksan	0x7	0x0	väärä	väärä	0x55	0xA1
CRC-8/MAXIM	kahdeksan	0x31	0x0	totta	totta	0x0	0xA1
CRC-8/ROHC	kahdeksan	0x7	0xFF	totta	totta	0x0	0xD0
CRC-8/WCDMA	kahdeksan	0x9B	0x0	totta	totta	0x0	0x25
CRC-10	kymmenen	0x233	0x0	väärä	väärä	0x0	0x199
CRC-10/CDMA2000	kymmenen	0x3D9	0x3FF	väärä	väärä	0x0	0x233
CRC-11	yksitoista	0x385	0x1A	väärä	väärä	0x0	0x5A3
CRC-12/3GPP	12	0x80F	0x0	väärä	totta	0x0	0xDAF
CRC-12/CDMA2000	12	0xF13	0xFFF	väärä	väärä	0x0	0xD4D
CRC-12/DECT	12	0x80F	0x0	väärä	väärä	0x0	0xF5B
CRC-13/BBC	13	0x1CF5	0x0	väärä	väärä	0x0	0x4FA
CRC-14/DARC	neljätoista	0x805	0x0	totta	totta	0x0	0x82D
CRC-15	viisitoista	0x4599	0x0	väärä	väärä	0x0	0x59E
CRC-15/MPT1327	viisitoista	0x6815	0x0	väärä	väärä	0x1	0x2566
CRC-16/ARC	16	0x8005	0x0	totta	totta	0x0	0xBB3D
CRC-16/AUG-CCITT	16	0x1021	0x1D0F	väärä	väärä	0x0	0xE5CC
CRC-16/BUYPASS	16	0x8005	0x0	väärä	väärä	0x0	0xFEE8
CRC-16/CCITT-EPÄTOSI	16	0x1021	0xFFFF	väärä	väärä	0x0	0x29B1
CRC-16/CDMA2000	16	0xC867	0xFFFF	väärä	väärä	0x0	0x4C06
CRC-16/DDS-110	16	0x8005	0x800D	väärä	väärä	0x0	0x9ECF
CRC-16/DECT-R	16	0x589	0x0	väärä	väärä	0x1	0x7E
CRC-16/DECT-X	16	0x589	0x0	väärä	väärä	0x0	0x7F
CRC-16/DNP	16	0x3D65	0x0	totta	totta	0xFFFF	0xEA82
CRC-16/FI-13757	16	0x3D65	0x0	väärä	väärä	0xFFFF	0xC2B7
CRC-16/GENIBUS	16	0x1021	0xFFFF	väärä	väärä	0xFFFF	0xD64E
CRC-16/MAXIM	16	0x8005	0x0	totta	totta	0xFFFF	0x44C2
CRC-16/MCRF4XX	16	0x1021	0xFFFF	totta	totta	0x0	0x6F91
CRC-16/RIELLO	16	0x1021	0xB2AA	totta	totta	0x0	0x63D0
CRC-16/T10-DIF	16	0x8BB7	0x0	väärä	väärä	0x0	0xD0DB
CRC-16/TELEDISK	16	0xA097	0x0	väärä	väärä	0x0	0xFB3
CRC-16/TMS37157	16	0x1021	0x89EC	totta	totta	0x0	0x26B1
CRC-16/USB	16	0x8005	0xFFFF	totta	totta	0xFFFF	0xB4C8
CRC-A	16	0x1021	0xC6C6	totta	totta	0x0	0xBF05
CRC-16/KERMIT	16	0x1021	0x0	totta	totta	0x0	0x2189
CRC-16/MODBUS	16	0x8005	0xFFFF	totta	totta	0x0	0x4B37
CRC-16/X-25	16	0x1021	0xFFFF	totta	totta	0xFFFF	0x906E
CRC-16/XMODEM	16	0x1021	0x0	väärä	väärä	0x0	0x31C3
CRC-24	24	0x864CFB	0xB704CE	väärä	väärä	0x0	0x21CF02
CRC-24/FLEXRAY-A	24	0x5D6DCB	0xFEDCBA	väärä	väärä	0x0	0x7979BD
CRC-24/FLEXRAY-B	24	0x5D6DCB	0xABCDEF	väärä	väärä	0x0	0x1F23B8
CRC-31/PHILIPS	31	0x4C11DB7	0x7FFFFFFF	väärä	väärä	0x7FFFFFFF	0xCE9E46C
CRC-32/ zlib	32	0x4C11DB7	0xFFFFFFFF	totta	totta	0xFFFFFFFF	0xCBF43926
CRC-32/BZIP2	32	0x4C11DB7	0xFFFFFFFF	väärä	väärä	0xFFFFFFFF	0xFC891918
CRC-32C	32	0x1EDC6F41	0xFFFFFFFF	totta	totta	0xFFFFFFFF	0xE3069283
CRC-32D	32	0xA833982B	0xFFFFFFFF	totta	totta	0xFFFFFFFF	0x87315576
CRC-32/MPEG-2	32	0x4C11DB7	0xFFFFFFFF	väärä	väärä	0x0	0x376E6E7
CRC-32/POSIX	32	0x4C11DB7	0x0	väärä	väärä	0xFFFFFFFF	0x765E7680
CRC-32Q	32	0x814141AB	0x0	väärä	väärä	0x0	0x3010BF7F
CRC-32/JAMCRC	32	0x4C11DB7	0xFFFFFFFF	totta	totta	0x0	0x340BC6D9
CRC-32/XFER	32	0xAF	0x0	väärä	väärä	0x0	0xBD0BE338
CRC-40/GSM	40	0x4820009	0x0	väärä	väärä	0xFFFFFFFFFF	0xD4164FC646
CRC-64	64	0x42F0E1EBA9EA3693	0x0	väärä	väärä	0x0	0x6C40DF5F0B497347
CRC-64/WE	64	0x42F0E1EBA9EA3693	0xFFFFFFFFFFFFFFFF	väärä	väärä	0xFFFFFFFFFFFFFFFF	0x62EC59E3F1A4F00A
CRC-64/XZ	64	0x42F0E1EBA9EA3693	0xFFFFFFFFFFFFFFFF	totta	totta	0xFFFFFFFFFFFFFFFF	0x995DC9BBDF1939FA

Muistiinpanot

↑ 1 2 3 4 5 Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) polynomivalinta sulautetuille verkoille (2004). Hakemuksen päivämäärä: ???. Arkistoitu alkuperäisestä 22. elokuuta 2011. (määrätön)
↑ Tietotekniikan Internet-yliopisto. Luento: Langattomien verkkojen organisointi
↑ Tietotekniikan Internet-yliopisto. Luento: Ethernet/Fast Ethernet Network Algorithms
↑ Walma, M.; Liukutettu syklinen redundanssitarkistus (CRC) -laskenta
↑ Greg Cook. Parametrisoitujen CRC-algoritmien luettelo (29. huhtikuuta 2009). Hakemuksen päivämäärä: ???. Arkistoitu alkuperäisestä 22. elokuuta 2011. (määrätön)
↑ G. Castagnoli, S. Braeuer, M. Herrman. Syklisen redundanssin tarkistuskoodien optimointi 24 ja 32 pariteettibitillä // IEEE Transactions on Communications. - Kesäkuu 1993. - T. 41 , nro 6 . - S. 883 . - doi : 10.1109/26.231911 .
↑ 1 2 3 4 5 6 P. Koopman. 32-bittiset sykliset redundanssikoodit Internet-sovelluksille // Kansainvälinen luotettavien järjestelmien ja verkkojen konferenssi. - Kesäkuu 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .
↑ Brayer, K; Hammond, JL Jr. (joulukuu 1975). "Virheentunnistuspolynomin suorituskyvyn arviointi AUTOVON-kanavalla". konferenssin ennätys . National Telecommunications Conference, New Orleans, La. 1 . New York: Institute of Electrical and Electronics Engineers. s. 8-21-8-25. Käytöstä poistettu parametri |month=( ohje )
↑ Merkittävin bitti jätetty pois esityksistä.
↑ G.704 , s. 12
↑ Luokka-1 Generation-2 UHF RFID -protokollan versio 1.2.0 . - 23. lokakuuta 2008. - S. 35 . Arkistoitu alkuperäisestä 20. marraskuuta 2008.
↑ G.704 , s. 9
↑ G.704 , s. 3
↑ G.707: Verkkosolmuliitäntä synkroniselle digitaaliselle hierarkialle (SDH)
↑ G.832: SDH-elementtien siirto PDH-verkoissa — Kehys- ja multipleksointirakenteet
↑ EN 302 307 Digital Video Broadcasting (DVB); Toisen sukupolven kehysrakenne, kanavakoodaus- ja modulaatiojärjestelmät yleislähetyksiin, interaktiivisiin palveluihin, uutisten keräämiseen ja muihin laajakaistaisiin satelliittisovelluksiin (DVB-S2)
↑ 1 2 FlexRay-protokollaspesifikaatioversio 2.1 Versio A. - 22. joulukuuta 2005. - S. 93 .
↑ A. Perez, Wismer, Becker. Byte-Wise CRC-laskelmat // IEEE Micro. - 1983. - V. 3 , nro 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .
↑ TV Ramabadran, SS Gaitonde. CRC-laskennan opetusohjelma // IEEE Micro. - 1988. - V. 8 , nro 4 . - S. 62-75 . - doi : 10.1109/40.7773 .
↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 16. lokakuuta 2009. Arkistoitu alkuperäisestä 1. lokakuuta 2009. (määrätön)
↑ Pat Thaler. 16-bittinen CRC-polynomin valinta . INCITS T10 (28. elokuuta 2003). Hakemuksen päivämäärä: ???. Arkistoitu alkuperäisestä 22. elokuuta 2011. (määrätön)
↑ Thomas Boutell, Glenn Randers-Pehrson et ai., PNG (Portable Network Graphics) -spesifikaatio, versio 1.2 (14. heinäkuuta 1998). Hakemuksen päivämäärä: ???. Arkistoitu alkuperäisestä 22. elokuuta 2011. (määrätön)
↑ AIXM Primer -versio 4.5 . Euroopan lennonvarmistusjärjestö (20. maaliskuuta 2006). Hakemuksen päivämäärä: ???. Arkistoitu alkuperäisestä 22. elokuuta 2011. (määrätön)
↑ ECMA-182 s. 51
↑ Ross N. Williams. CRC Rocksoft (linkki ei saatavilla) (1993). Haettu 17. huhtikuuta 2012. Arkistoitu alkuperäisestä 3. syyskuuta 2011. (määrätön)
↑ Greg Cook. Parametrisoitujen CRC-algoritmien luettelo (18. tammikuuta 2016). (määrätön)

Kirjallisuus

Henry S. Warren, Jr. Luku 5 Bittien laskeminen // Algoritmisia temppuja ohjelmoijille = Hacker's Delight. — M .: Williams , 2007. — 288 s. — ISBN 0-201-91465-4 .

Linkit

Perusopas CRC-virheentunnistusalgoritmeihin
CRC ja kuinka se palautetaan
CRC-funktiogeneraattori VHDL :ssä ja Verilogissa
Ross N. Williams/Anarchriz. Kaikki CRC32 :sta // Ross N. Williams. Perusopas CRC-virheentunnistusalgoritmeihin
Ross N. Williams. KIPUTON OPAS CRC-VIRHEIDEN TUNNISTUSALGORITMIIN

CRC-laskimet

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA