Cyklisk redundanskode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. januar 2021; checks kræver 10 redigeringer .

Cyklisk redundanskontrol _ _ , CRC [1] ) er en algoritme til at finde en kontrolsum designet til at kontrollere integriteten af data [2] . CRC er en praktisk anvendelse af fejlkorrigerende kodning baseret på visse matematiske egenskaber ved en cyklisk kode .

Introduktion

Begrebet cykliske koder er ret bredt [3] . I engelsk litteratur forstås CRC på to måder, afhængig af konteksten: Cyclic Redundancy Code eller Cyclic Redundancy Check [4] . Det første koncept betyder det matematiske fænomen af cykliske koder, det andet - den specifikke anvendelse af dette fænomen som en hash-funktion .

Cykliske koder er ikke kun nemme at implementere, men har også den fordel, at de er velegnede til at detektere burst-fejl: kontinuerlige sekvenser af fejlagtige datategn i meddelelser. Dette er vigtigt, fordi burst-fejl er almindelige transmissionsfejl i mange kommunikationskanaler, herunder magnetiske og optiske lagerenheder. Typisk detekterer en n-bit CRC, anvendt på en blok af data af vilkårlig længde, og med kontrolsummen umiddelbart efter dataene, enhver enkelt burst af fejl, der ikke er længere end n bit, og andelen af alle længere bursts af fejl, som den detekterer er (1 − 2 −n ).

Støjkorrigerende kodning

De første forsøg på at skabe koder med overflødig information begyndte længe før fremkomsten af moderne computere. For eksempel, tilbage i 1960'erne, udviklede Reed og Solomon en effektiv kodningsteknik - Reed-Solomon-koden . Det var ikke muligt at bruge det på det tidspunkt, da de første algoritmer ikke kunne udføre afkodningsoperationen inden for rimelig tid . Berlekamps grundlæggende værk , udgivet i 1968, satte en stopper for dette spørgsmål . Denne teknik , den praktiske anvendelse, som Massey påpegede et år senere , bruges stadig i digitale enheder, der modtager RS-kodede data den dag i dag. Desuden: dette system gør det ikke kun muligt at bestemme positioner, men også at rette forkerte kodesymboler (oftest oktetter ).

Men det er langt fra altid, at der kræves fejlretning fra koden . Mange moderne kommunikationskanaler har acceptable egenskaber, og ofte er det nok at kontrollere, om overførslen var vellykket, eller om der var nogen vanskeligheder; strukturen af fejlene og de specifikke placeringer af de forkerte symboler er overhovedet ikke af interesse for den modtagende part. Og under disse forhold viste algoritmer, der bruger kontrolsummer, sig at være en meget vellykket løsning. CRC er bedst egnet til sådanne opgaver: lave ressourceomkostninger, nem implementering og det allerede dannede matematiske apparat fra teorien om lineære cykliske koder sikrede dets enorme popularitet.

Selvom CRC-koden normalt kun bruges til fejldetektering, gør dens matematiske egenskaber det muligt at finde og rette en enkelt fejl i en blok af bit, hvis hver bit i den beskyttede blok (inklusive kontrolbittene) har sin egen unikke rest, når den er opdelt af generatorpolynomiet. For eksempel, hvis det genererende polynomium er irreducerbart, og længden af blokken ikke overstiger rækkefølgen af den genererede cykliske gruppe.

Kontrolsum

Generelt er kontrolsummen en værdi beregnet i henhold til et bestemt skema baseret på den kodede meddelelse. Kontroloplysningerne i systematisk kodning tildeles de overførte data. På den modtagende side kender abonnenten algoritmen til beregning af kontrolsummen: i overensstemmelse hermed har programmet mulighed for at kontrollere rigtigheden af de modtagne data.

Når pakker transmitteres over en netværkskanal, kan kildeinformationen blive forvrænget på grund af forskellige eksterne påvirkninger: elektrisk interferens, dårlige vejrforhold og mange andre. Essensen af teknikken er, at med gode egenskaber af kontrolsummen vil en fejl i meddelelsen i langt de fleste tilfælde føre til en ændring i dens kontrolsum. Hvis de oprindelige og beregnede beløb ikke er ens, tages der en beslutning om ugyldigheden af de modtagne data, og der kan anmodes om en gentransmission af pakken.

Matematisk beskrivelse

CRC-algoritmen er baseret på egenskaberne ved division med en rest af binære polynomier, det vil sige polynomier over et begrænset felt . CRC-værdien er i det væsentlige resten af at dividere polynomiet svarende til inputtet med et eller andet fast generatorpolynomium . $GF(2)$

Hver endelig sekvens af bit er en-til-en forbundet med et binært polynomium , hvis koefficientsekvens er den oprindelige sekvens. For eksempel svarer bitsekvensen 1011010 til polynomiet: $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.

Antallet af distinkte polynomier af grad mindre end er lig med , hvilket er det samme som antallet af alle binære sekvenser af længde . $N$ $2^N$ $N$

Kontrolsumværdien i en algoritme med en genererende polynomiumgrad er defineret som en bitsekvens af længde , der repræsenterer polynomiet, hvilket resulterer i resten af at dividere polynomiet , der repræsenterer input-bitstrømmen, med polynomiet : $G(x)$ $N$ $N$ $R(x)$ $P(x)$ $G(x)$

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

hvor

R(x)

er et polynomium, der repræsenterer CRC-værdien;

P(x)

er et polynomium, hvis koefficienter repræsenterer inputdataene;

G(x)

er et genererende polynomium;

N

er graden af det genererende polynomium.

Multiplikation udføres ved at tildele nul bit til inputsekvensen, hvilket forbedrer kvaliteten af hashing for korte inputsekvenser. $x^N$ $N$

Når man dividerer med en rest af forskellige oprindelige polynomier med et genererende polynomium af grad , kan man opnå forskellige rester fra division. er ofte et irreducerbart polynomium . Det vælges normalt i overensstemmelse med kravene til en hash-funktion i forbindelse med hver enkelt applikation. $G(x)$ $N$ $2^{N}$ $G(x)$

Der er dog mange standardiserede polynomiegeneratorer, der har gode matematiske og korrelationsegenskaber (minimum antal kollisioner , nem beregning), hvoraf nogle er anført nedenfor.

CRC-beregning

Algoritmeparametre

En af hovedparametrene for CRC er det genererende polynomium.

En anden parameter forbundet med generatorpolynomiet er dens grad , som bestemmer antallet af bits , der bruges til at beregne CRC-værdien. I praksis er 8-, 16- og 32-bit ord de mest almindelige, hvilket er en konsekvens af de særlige kendetegn ved arkitekturen i moderne computerteknologi.

En anden parameter er ordets begyndelsesværdi (startværdi). Disse parametre definerer fuldstændigt den "traditionelle" CRC-beregningsalgoritme. Der er også modifikationer af algoritmen, for eksempel ved at bruge den omvendte rækkefølge af behandlingsbit.

Beskrivelse af proceduren

Det første ord er taget fra filen - det kan være en bit (CRC-1), byte (CRC-8) eller et hvilket som helst andet element. Hvis den mest signifikante bit i ordet er "1", så flyttes ordet til venstre med en bit, efterfulgt af en XOR -operation med et genererende polynomium. Følgelig, hvis den mest signifikante bit i ordet er "0", så udføres XOR-operationen ikke efter skiftet . Efter skiftet går den mest signifikante bit tabt, og den næste bit fra filen indlæses i stedet for den mindst signifikante bit, og operationen gentages, indtil den sidste bit af filen er indlæst. Efter at have gennemgået hele filen, forbliver resten i ordet, som er kontrolsummen.

Populære og standardiserede polynomier

Mens cykliske redundanskoder er en del af standarderne, har dette udtryk ikke en generelt accepteret definition - forskellige forfatteres fortolkninger modsiger ofte hinanden [1] [5] .

Dette paradoks gælder også for valget af et generatorpolynomium: ofte er standardiserede polynomier ikke de mest effektive med hensyn til de statistiske egenskaber af deres tilsvarende kontrolredundanskode .

Mange udbredte polynomier er dog ikke de mest effektive af alle mulige. I 1993-2004 var en gruppe videnskabsmænd engageret i undersøgelsen af at generere polynomier med kapacitet op til 16 [1] 24 og 32 bit [6] [7] og fandt polynomier, der giver bedre ydeevne end standardiserede polynomier med hensyn til kodeafstand [7] . Et af resultaterne af denne undersøgelse har allerede fundet vej til iSCSI -protokollen .

Det mest populære og anbefalede IEEE polynomium for CRC-32 bruges i Ethernet , FDDI ; også dette polynomium er en Hamming-kodegenerator [8] . Brug af et andet polynomium - CRC-32C - giver dig mulighed for at opnå den samme ydeevne med længden af den originale besked fra 58 bit til 131 kbps, og i nogle områder af længden af inputmeddelelsen kan den være endnu højere, så det er også populær i dag [7] . For eksempel bruger ITU-T G.hn-standarden CRC-32C til at opdage fejl i nyttelasten.

Tabellen nedenfor viser de mest almindelige polynomier - CRC-generatorer. I praksis kan beregningen af CRC inkludere præ- og post-inversion, såvel som den omvendte rækkefølge af bitbehandling. Proprietære implementeringer af CRC bruger ikke-nul initiale registerværdier for at gøre koden sværere at parse.

Navn	Polynomium	Repræsentationer: [9] normal / omvendt / omvendt fra omvendt
CRC-1	$x+1$ (bruges i hardwarefejlkontrol; også kendt som paritetsbit )	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 -token-pakker)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ ( ITU G.704 [13] )	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (telekommunikationssystemer, 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-leder bus )	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$ (telekommunikationssystemer [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] , mange andre; også kendt som CRC-16 og CRC-16-ANSI )	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$ ( X.25 , HDLC , XMODEM , Bluetooth , SD osv.)	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	Ikke CRC; se Fletchers kontrolsum	Brugt i 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	Ikke CRC; se Adler-32	Se 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 nyttelast)	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$ (luftfart; AIXM [23] )	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	$x^{64} + x^4 + x^3 + x + 1$ ( HDLC - ISO 3309 )	0x0000000000000001B / 0xD8000000000000000 / 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

Eksisterende standarder CRC-128 (IEEE) og CRC-256 (IEEE) i øjeblikket[ hvornår? ] er blevet afløst af kryptografiske hash-funktioner .

CRC-algoritmespecifikationer

En af de mest berømte er Ross N. Williams teknik [25] . Den bruger følgende muligheder:

Navnet på algoritmen ( navn );

Graden af den kontrolsum, der genererer polynomium ( bredde );

Selve det genererende polynomium ( poly ). For at skrive det som en værdi, skrives det først som en bitsekvens, mens den mest signifikante bit udelades - det er altid 1. For eksempel vil et polynomium i denne notation blive skrevet som et tal . For nemheds skyld er den resulterende binære repræsentation skrevet i hexadecimal form. For vores tilfælde vil det være lig med eller 0x11; $x^8+x^4+1$ $00010001_2$ $11_t$

Startdata ( init ), det vil sige værdierne af registrene på tidspunktet for starten af beregninger;

Flaget ( RefIn ), der angiver starten og retningen af beregningen, skal matche rækkefølgen af transmission i kanalen for at detektere udbrud af fejl. Der er to muligheder: Falsk - starter med den mest signifikante bit ( MSB -først) eller Sand - starter med den mindst signifikante bit ( LSB -først);

Flag ( RefOut ), der bestemmer, om rækkefølgen af registerbittene inverteres, når man indtaster XOR- elementet ;

Tallet ( XorOut ), hvormed resultatet tilføjes modulo 2 ;

CRC-værdien ( check ) for strengen "123456789" .

Eksempler [26]

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

Noter

↑ 1 2 3 4 5 Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks (2004). Dato for ansøgningen: ???. Arkiveret fra originalen den 22. august 2011. (ubestemt)
↑ Internet University of Information Technology. Foredrag: Organisering af trådløse netværk
↑ Internet University of Information Technology. Foredrag: Ethernet/Fast Ethernet Network Algoritmer
↑ Walma, M.; Pipelined Cyclic Redundancy Check (CRC) Beregning
↑ Greg Cook. Katalog over parametriserede CRC-algoritmer (29. april 2009). Dato for ansøgningen: ???. Arkiveret fra originalen den 22. august 2011. (ubestemt)
↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimering af cykliske redundans-checkkoder med 24 og 32 paritetsbits // IEEE-transaktioner på kommunikation. - juni 1993. - T. 41 , nr. 6 . - S. 883 . - doi : 10.1109/26.231911 .
↑ 1 2 3 4 5 6 P. Koopman. 32-bit cykliske redundanskoder til internetapplikationer // Den internationale konference om pålidelige systemer og netværk. - juni 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .
↑ Brayer, K; Hammond, JL Jr. (december 1975). "Evaluering af fejldetekteringspolynomiets ydeevne på AUTOVON-kanalen". konference rekord . National Telecommunications Conference, New Orleans, La. 1 . New York: Institute of Electrical and Electronics Engineers. pp. 8-21 til 8-25. Forældet parameter brugt |month=( hjælp )
↑ Den mest betydningsfulde bit udeladt i repræsentationer.
↑ G.704 , s. 12
↑ Klasse-1 Generation-2 UHF RFID-protokol version 1.2.0 . - 23. oktober 2008. - S. 35 . Arkiveret fra originalen den 20. november 2008.
↑ G.704 , s. 9
↑ G.704 , s. 3
↑ G.707: Netværksknudegrænseflade til det synkrone digitale hierarki (SDH)
↑ G.832: Transport af SDH-elementer på PDH-netværk — Ramme- og multiplekseringsstrukturer
↑ EN 302 307 Digital Video Broadcasting (DVB); Anden generations rammestruktur, kanalkodnings- og moduleringssystemer til broadcasting, interaktive tjenester, nyhedsindsamling og andre bredbåndssatellitapplikationer (DVB-S2)
↑ 1 2 FlexRay Protocol Specification version 2.1 Revision A. - 22. december 2005. - S. 93 .
↑ A. Perez, Wismer, Becker. Byte-Wise CRC-beregninger // IEEE Micro. - 1983. - V. 3 , nr. 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .
↑ TV Ramabadran, SS Gaitonde. En tutorial om CRC-beregninger // IEEE Micro. - 1988. - V. 8 , nr. 4 . - S. 62-75 . - doi : 10.1109/40.7773 .
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 16. oktober 2009. Arkiveret fra originalen 1. oktober 2009. (ubestemt)
↑ Pat Thaler. 16-bit CRC polynomium valg . INCITER T10 (28. august 2003). Dato for ansøgningen: ???. Arkiveret fra originalen den 22. august 2011. (ubestemt)
↑ Thomas Boutell, Glenn Randers-Pehrson et al. PNG (Portable Network Graphics) Specification, Version 1.2 (14. juli 1998). Dato for ansøgningen: ???. Arkiveret fra originalen den 22. august 2011. (ubestemt)
↑ AIXM Primer version 4.5 . Den Europæiske Organisation for Luftfartssikkerhed (20. marts 2006). Dato for ansøgningen: ???. Arkiveret fra originalen den 22. august 2011. (ubestemt)
↑ ECMA-182 s. 51
↑ Ross N. Williams. CRC Rocksoft (utilgængeligt link) (1993). Hentet 17. april 2012. Arkiveret fra originalen 3. september 2011. (ubestemt)
↑ Greg Cook. Katalog over parametriserede CRC-algoritmer (18. januar 2016). (ubestemt)

Litteratur

Henry S. Warren, Jr. Kapitel 5 At tælle bits // Algoritmiske tricks for programmører = Hacker's Delight. — M .: Williams , 2007. — 288 s. — ISBN 0-201-91465-4 .

Links

En elementær guide til CRC-fejldetektionsalgoritmer
CRC og hvordan man genopretter det
CRC Funktionsgenerator i VHDL og Verilog
Ross N. Williams/Anarchriz. Alt om CRC32 // Ross N. Williams. En elementær guide til CRC-fejldetektionsalgoritmer
Ross N. Williams. EN SMERTEFRI GUIDE TIL CRC FEJLDETEKTIONSALGORITHMER

CRC regnemaskiner

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE