Cod de redundanță ciclică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 ianuarie 2021; verificările necesită 10 modificări .

Verificarea redundanței ciclice _ , CRC [1] ) este un algoritm pentru găsirea unei sume de control conceput pentru a verifica integritatea datelor [2] . CRC este o aplicație practică a codificării de corectare a erorilor bazată pe anumite proprietăți matematice ale unui cod ciclic .

Introducere

Conceptul de coduri ciclice este destul de larg [3] . În literatura engleză, CRC este înțeles în două moduri, în funcție de context: Cyclic Redundancy Code sau Cyclic Redundancy Check [4] . Primul concept înseamnă fenomenul matematic al codurilor ciclice, al doilea - aplicarea specifică a acestui fenomen ca funcție hash .

Codurile ciclice nu sunt doar ușor de implementat, dar au și avantajul de a fi potrivite pentru detectarea erorilor de explozie: secvențe continue de caractere de date eronate în mesaje. Acest lucru este important deoarece erorile de rafală sunt erori comune de transmisie în multe canale de comunicație, inclusiv dispozitivele de stocare magnetice și optice. În mod obișnuit, un CRC de n biți, aplicat unui bloc de date de lungime arbitrară și cu suma de control imediat după date, detectează orice explozie unică de erori care nu depășește n biți și proporția tuturor exploziilor mai lungi de erori pe care le detectează este (1 − 2 −n ).

Codare de corectare a zgomotului

Primele încercări de a crea coduri cu informații redundante au început cu mult înainte de apariția computerelor moderne. De exemplu, în anii 1960, Reed și Solomon au dezvoltat o tehnică de codificare eficientă - Codul Reed-Solomon . Utilizarea acestuia la acel moment nu era posibilă, deoarece primii algoritmi nu puteau efectua operația de decodare într-un timp rezonabil . Lucrarea fundamentală a lui Berlekamp , publicată în 1968, a pus capăt acestei probleme . Această tehnică , a cărei aplicare practică a subliniat Massey un an mai târziu , este încă folosită în dispozitivele digitale care primesc date codificate RS până în prezent. Mai mult: acest sistem permite nu numai determinarea pozițiilor, ci și corectarea simbolurilor codurilor incorecte (cel mai adesea octeți ).

Dar este departe de a fi întotdeauna necesară corectarea erorilor din cod . Multe canale de comunicare moderne au caracteristici acceptabile și de multe ori este suficient să se verifice dacă transferul a avut succes sau dacă au existat dificultăți ; structura erorilor și pozițiile specifice ale simbolurilor incorecte nu prezintă deloc interes pentru partea care primește. Și în aceste condiții, algoritmii care utilizează sume de control s-au dovedit a fi o soluție de mare succes. CRC este cel mai potrivit pentru astfel de sarcini: costurile reduse ale resurselor, ușurința de implementare și aparatul matematic deja format din teoria codurilor ciclice liniare i-au asigurat popularitatea imensă.

Deși codul CRC este utilizat de obicei doar pentru detectarea erorilor, proprietățile sale matematice fac posibilă găsirea și corectarea unei singure erori într-un bloc de biți dacă fiecare bit al blocului protejat (inclusiv biții de verificare) are propriul său rest unic atunci când este împărțit. prin polinomul generator. De exemplu, dacă polinomul generator este ireductibil și lungimea blocului nu depășește ordinul grupului ciclic generat.

Sumă de control

În general, suma de control este o valoare calculată după o anumită schemă bazată pe mesajul codificat. Informațiile de verificare în codificare sistematică sunt atribuite datelor transmise. Pe partea de recepție, abonatul cunoaște algoritmul pentru calcularea sumei de control: în consecință, programul are capacitatea de a verifica corectitudinea datelor primite.

Când pachetele sunt transmise pe un canal de rețea, informațiile sursă pot fi distorsionate din cauza diferitelor influențe externe: interferențe electrice, condiții meteorologice nefavorabile și multe altele. Esența tehnicii este că, cu caracteristici bune ale sumei de control, în marea majoritate a cazurilor, o eroare în mesaj va duce la o modificare a sumei de control. Dacă sumele inițiale și cele calculate nu sunt egale, se ia o decizie cu privire la invaliditatea datelor primite și se poate solicita o retransmitere a pachetului.

Descriere matematică

Algoritmul CRC se bazează pe proprietățile divizării cu un rest de polinoame binare, adică polinoame peste un câmp finit . Valoarea CRC este în esență restul împărțirii polinomului corespunzător intrării la un polinom fix generator . $GF(2)$

Fiecare secvență finită de biți este unu-la-unu asociată cu un polinom binar a cărui secvență de coeficienți este secvența originală. De exemplu, secvența de biți 1011010 corespunde polinomului: $a_0, a_1, \dots, a_{N-1}$ $\textstyle\sum_{n=0}^{N-1} a_n x^n$

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

Numărul de polinoame distincte de grad mai mic decât este egal cu , care este același cu numărul tuturor secvențelor binare de lungime . $N$ $2^N$ $N$

Valoarea sumei de control dintr-un algoritm cu un grad de polinom generator este definită ca o secvență de biți de lungime , reprezentând polinomul care rezultă în restul împărțirii polinomului , reprezentând fluxul de biți de intrare, la polinomul : $G(x)$ $N$ $N$ $R(x)$ $P(x)$ $G(x)$

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

Unde

R(x)

este un polinom reprezentând valoarea CRC;

P(x)

este un polinom ai cărui coeficienți reprezintă datele de intrare;

G(x)

este un polinom generator;

N

este gradul polinomului generator.

Înmulțirea se realizează prin alocarea de biți zero secvenței de intrare, ceea ce îmbunătățește calitatea hashingului pentru secvențele scurte de intrare. $x^N$ $N$

Când împărțim cu un rest de diverse polinoame originale cu un polinom generator de grad , se pot obține diverse resturi din diviziune. este adesea un polinom ireductibil . De obicei, este selectat în conformitate cu cerințele pentru o funcție hash în contextul fiecărei aplicații particulare. $G(x)$ $N$ $2^{N}$ $G(x)$

Cu toate acestea, există multe generatoare de polinoame standardizate care au proprietăți matematice și de corelare bune (număr minim de coliziuni , ușurință de calcul), dintre care unele sunt enumerate mai jos.

Calcul CRC

Parametrii algoritmului

Unul dintre principalii parametri ai CRC este polinomul generator.

Un alt parametru asociat cu polinomul generator este gradul acestuia , care determină numărul de biți utilizați pentru a calcula valoarea CRC. În practică, cuvintele de 8, 16 și 32 de biți sunt cele mai comune, ceea ce este o consecință a particularităților arhitecturii tehnologiei computerizate moderne.

Un alt parametru este valoarea inițială (de pornire) a cuvântului. Acești parametri definesc complet algoritmul de calcul „tradițional” CRC. Există, de asemenea, modificări ale algoritmului, de exemplu, folosind ordinea inversă a biților de procesare.

Descrierea procedurii

Primul cuvânt este preluat din fișier - poate fi un bit (CRC-1), octet (CRC-8) sau orice alt element. Dacă bitul cel mai semnificativ din cuvânt este „1”, atunci cuvântul este deplasat la stânga cu un bit, urmat de o operație XOR cu un polinom generator. În consecință, dacă bitul cel mai semnificativ din cuvânt este „0”, atunci operația XOR nu este efectuată după schimbarea . După schimbare, bitul cel mai semnificativ este pierdut, iar următorul bit din fișier este încărcat în locul celui mai puțin semnificativ, iar operația se repetă până când ultimul bit al fișierului este încărcat. După ce parcurgeți întregul fișier, restul rămâne în cuvânt, care este suma de control.

Polinoame populare și standardizate

În timp ce codurile de redundanță ciclică fac parte din standarde, acest termen nu are o definiție general acceptată - interpretările diverșilor autori se contrazic deseori [1] [5] .

Acest paradox se aplică și alegerii unui polinom generator: adesea polinoamele standardizate nu sunt cele mai eficiente în ceea ce privește proprietățile statistice ale codului de redundanță de verificare corespunzător .

Cu toate acestea, multe polinoame utilizate pe scară largă nu sunt cele mai eficiente dintre toate posibilele. În 1993-2004, un grup de oameni de știință s-a angajat în studiul generării de polinoame cu capacitate de până la 16 [1] 24 și 32 de biți [6] [7] și au găsit polinoame care oferă performanțe mai bune decât polinoamele standardizate în ceea ce privește distanța de cod. [7] . Unul dintre rezultatele acestui studiu și-a găsit deja drumul în protocolul iSCSI .

Cel mai popular și recomandat polinom IEEE pentru CRC-32 este utilizat în Ethernet , FDDI ; de asemenea, acest polinom este un generator de cod Hamming [8] . Folosirea unui alt polinom - CRC-32C - vă permite să obțineți aceeași performanță cu lungimea mesajului original de la 58 de biți la 131 kbps, iar în unele intervale de lungime a mesajului de intrare poate fi și mai mare, deci este, de asemenea, popular astăzi [7] . De exemplu, standardul ITU-T G.hn folosește CRC-32C pentru a detecta erorile în sarcina utilă.

Tabelul de mai jos enumeră cele mai comune polinoame - generatoare CRC. În practică, calculul CRC poate include pre- și post-inversie, precum și ordinea inversă a procesării biților. Implementările proprietare ale CRC folosesc valori inițiale diferite de zero pentru a face codul mai dificil de analizat.

Nume	Polinom	Reprezentări: [9] normal / inversat / inversat de la invers
CRC-1	$x+1$ (utilizat în verificarea erorilor hardware; cunoscut și ca bit de paritate )	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$ ( RFID Gen 2 [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$ ( pachete de jetoane USB )	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ ( ITU G.704 [13] )	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (sisteme de telecomunicații, 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 ), Controlul erorilor antet ISDN și delimitarea celulei ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8- Dallas / Maxim	$x^8 + x^5 + x^4 + 1$ ( autobuz cu 1 fir )	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$ (sisteme de telecomunicații [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] , multe altele; cunoscute și ca CRC-16 și CRC-16-ANSI )	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$ ( X.25 , HDLC , XMODEM , Bluetooth , SD etc.)	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	Nu CRC; vezi suma de control a lui Fletcher	Folosit în Adler-32 A&B CRC
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	Nu CRC; vezi Adler-32	Vezi 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] , CKsum POSIX )	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 , sarcină utilă G.hn )	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$ (aviație; 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

Standardele existente CRC-128 (IEEE) și CRC-256 (IEEE) în prezent[ când? ] au fost înlocuite de funcțiile hash criptografice .

Specificații algoritmului CRC

Una dintre cele mai cunoscute este tehnica Ross N. Williams [25] . Utilizează următoarele opțiuni:

Numele algoritmului ( nume );

Gradul polinomului generator al sumei de control ( lățime );

Polinomul generator însuși ( poli ). Pentru a o scrie ca valoare, se scrie mai întâi ca o secvență de biți, în timp ce bitul cel mai semnificativ este omis - este întotdeauna 1. De exemplu, un polinom din această notație va fi scris ca un număr . Pentru comoditate, reprezentarea binară rezultată este scrisă în formă hexazecimală . Pentru cazul nostru, acesta va fi egal cu sau 0x11; $x^8+x^4+1$ $00010001_2$ $11_h$

Date de început ( init ), adică valorile registrelor la momentul începerii calculelor;

Indicatorul ( RefIn ), care indică începutul și direcția calculului, trebuie să se potrivească cu ordinea de transmisie pe canal pentru a detecta exploziile de erori. Există două opțiuni: False - începând cu bitul cel mai semnificativ ( MSB - primul) sau Adevărat - începând cu bitul cel mai puțin semnificativ ( LSB - primul);

Flag ( RefOut ) care determină dacă ordinea biților de registru este inversată la introducerea elementului XOR ;

Numărul ( XorOut ) cu care rezultatul este adăugat modulo 2 ;

Valoarea CRC ( verifica ) pentru șirul „123456789” .

Exemple [26]

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

Note

↑ 1 2 3 4 5 Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) Polynom Selection For Embedded Networks (2004). Data cererii: ???. Arhivat din original pe 22 august 2011. (nedefinit)
↑ Universitatea de Tehnologia Informației pe Internet. Curs: Organizarea rețelelor wireless
↑ Universitatea de Tehnologia Informației pe Internet. Prelegere: Algoritmi de rețea Ethernet/Fast Ethernet
↑ Walma, M.; Calcul de verificare a redundanței ciclice în conducte (CRC).
↑ Greg Cook. Catalogul algoritmilor CRC parametrizați (29 aprilie 2009). Data cererii: ???. Arhivat din original pe 22 august 2011. (nedefinit)
↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimizarea codurilor de verificare a redundanței ciclice cu 24 și 32 de biți de paritate // Tranzacții IEEE pe comunicații. - iunie 1993. - T. 41 , nr 6 . - S. 883 . - doi : 10.1109/26.231911 .
↑ 1 2 3 4 5 6 P. Koopman. Coduri de redundanță ciclică pe 32 de biți pentru aplicații de internet // Conferința internațională privind sistemele și rețelele de încredere. - iunie 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .
↑ Brayer, K; Hammond, JL Jr. (decembrie 1975). „Evaluarea performanței polinomului de detectare a erorilor pe canalul AUTOVON”. înregistrarea conferinței . Conferința Națională de Telecomunicații, New Orleans, La. 1 . New York: Institutul de Ingineri Electrici și Electronici. pp. 8-21 până la 8-25. Parametrul depreciat folosit |month=( ajutor )
↑ Cel mai semnificativ bit a fost omis în reprezentări.
↑ G.704 , p. 12
↑ Protocolul UHF RFID clasa 1 generația 2 versiunea 1.2.0 . - 23 octombrie 2008. - S. 35 . Arhivat din original pe 20 noiembrie 2008.
↑ G.704 , p. 9
↑ G.704 , p. 3
↑ G.707: Interfață nod de rețea pentru ierarhia digitală sincronă (SDH)
↑ G.832: Transportul elementelor SDH pe rețele PDH — Structuri de cadru și multiplexare
↑ EN 302 307 Digital Video Broadcasting (DVB); Structură de încadrare de a doua generație, sisteme de codificare și modulare a canalelor pentru difuzare, servicii interactive, colectare de știri și alte aplicații prin satelit în bandă largă (DVB-S2)
↑ 1 2 FlexRay Protocol Specification versiunea 2.1 Revizia A. - 22 decembrie 2005. - P. 93 .
↑ A. Perez, Wismer, Becker. Calcule CRC în funcție de octeți // IEEE Micro. - 1983. - V. 3 , Nr. 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .
↑ TV Ramabadran, SS Gaitonde. Un tutorial despre calculele CRC // IEEE Micro. - 1988. - V. 8 , nr 4 . - S. 62-75 . - doi : 10.1109/40.7773 .
↑ Copie arhivată (link nu este disponibil) . Consultat la 16 octombrie 2009. Arhivat din original la 1 octombrie 2009. (nedefinit)
↑ Pat Thaler. Selectare polinom CRC pe 16 biți . INCITS T10 (28 august 2003). Data cererii: ???. Arhivat din original pe 22 august 2011. (nedefinit)
^ Thomas Boutell , Glenn Randers-Pehrson și alții PNG (Portable Network Graphics) Specification, Versiunea 1.2 (14 iulie 1998). Data cererii: ???. Arhivat din original pe 22 august 2011. (nedefinit)
↑ AIXM Primer versiunea 4.5 . Organizația Europeană pentru Siguranța Navigației Aeriene (20 martie 2006). Data cererii: ???. Arhivat din original pe 22 august 2011. (nedefinit)
↑ ECMA-182 p. 51
↑ Ross N. Williams. CRC Rocksoft (link indisponibil) (1993). Consultat la 17 aprilie 2012. Arhivat din original pe 3 septembrie 2011. (nedefinit)
↑ Greg Cook. Catalog de algoritmi CRC parametrizați (18 ianuarie 2016). (nedefinit)

Literatură

Henry S. Warren, Jr. Capitolul 5 Numărarea biților // Trucuri algoritmice pentru programatori = Hacker's Delight. — M .: Williams , 2007. — 288 p. — ISBN 0-201-91465-4 .

Link -uri

Un ghid elementar pentru algoritmii de detectare a erorilor CRC
CRC și cum să-l recuperezi
Generator de funcții CRC în VHDL și Verilog
Ross N. Williams/Anarchriz. Totul despre CRC32 // Ross N. Williams. Un ghid elementar pentru algoritmii de detectare a erorilor CRC
Ross N. Williams. UN GHID INDUROR PENTRU ALGORITMI DE DETECȚIE A ERORILOR CRC

Calculatoare CRC

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 Centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă 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 Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ