Cyklisk redundanskod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 januari 2021; kontroller kräver 10 redigeringar .

Cyklisk redundanskontroll _ _ , CRC [1] ) är en algoritm för att hitta en kontrollsumma utformad för att kontrollera dataintegriteten [2] . CRC är en praktisk tillämpning av felkorrigerande kodning baserad på vissa matematiska egenskaper hos en cyklisk kod .

Introduktion

Begreppet cykliska koder är ganska brett [3] . I engelsk litteratur förstås CRC på två sätt, beroende på sammanhanget: Cyclic Redundancy Code eller Cyclic Redundancy Check [4] . Det första konceptet betyder det matematiska fenomenet med cykliska koder, det andra - den specifika tillämpningen av detta fenomen som en hashfunktion .

Cykliska koder är inte bara lätta att implementera, utan har också fördelen att de är lämpliga för att upptäcka skurfel: kontinuerliga sekvenser av felaktiga datatecken i meddelanden. Detta är viktigt eftersom skurfel är vanliga överföringsfel i många kommunikationskanaler, inklusive magnetiska och optiska lagringsenheter. Vanligtvis upptäcker en n-bitars CRC, applicerad på ett datablock av godtycklig längd, och med kontrollsumman omedelbart efter datan, varje enskild skur av fel som inte är längre än n bitar, och andelen av alla längre skurar av fel som den detekterar är (1 − 2 −n ).

Bruskorrigerande kodning

De första försöken att skapa koder med redundant information började långt innan moderna datorers tillkomst. Till exempel, på 1960-talet, utvecklade Reed och Solomon en effektiv kodningsteknik - Reed-Solomon-koden . Att använda det vid den tiden var inte möjligt, eftersom de första algoritmerna inte kunde utföra avkodningsoperationen inom rimlig tid . Berlekamps grundläggande arbete , publicerat 1968, satte stopp för denna fråga . Denna teknik , vars praktiska tillämpning Massey påpekade ett år senare , används fortfarande i digitala enheter som tar emot RS-kodad data än i dag. Dessutom: detta system tillåter inte bara att bestämma positioner, utan också att korrigera felaktiga kodsymboler (oftast oktetter ).

Men det är långt ifrån alltid som felkorrigering krävs från koden . Många moderna kommunikationskanaler har acceptabla egenskaper, och ofta räcker det med att kontrollera om överföringen lyckades eller om det fanns några svårigheter; strukturen på felen och de specifika positionerna för de felaktiga symbolerna är inte alls av intresse för den mottagande parten. Och under dessa förhållanden visade sig algoritmer som använder kontrollsummor vara en mycket framgångsrik lösning. CRC är bäst lämpad för sådana uppgifter: låga resurskostnader, enkel implementering och den redan bildade matematiska apparaten från teorin om linjära cykliska koder säkerställde dess enorma popularitet.

Även om CRC-koden vanligtvis endast används för feldetektering, gör dess matematiska egenskaper det möjligt att hitta och korrigera ett enstaka fel i ett block av bitar om varje bit i det skyddade blocket (inklusive kontrollbitarna) har sin egen unika rest när de delas av generatorpolynomet. Till exempel, om det genererande polynomet är irreducerbart och längden på blocket inte överstiger ordningen för den genererade cykliska gruppen.

Kontrollsumma

I allmänhet är kontrollsumman ett värde som beräknas enligt ett visst schema baserat på det kodade meddelandet. Kontrollinformationen i systematisk kodning tilldelas de överförda uppgifterna. På mottagningssidan känner abonnenten till algoritmen för att beräkna kontrollsumman: följaktligen har programmet förmågan att kontrollera riktigheten av mottagna data.

När paket sänds över en nätverkskanal kan källinformationen förvrängas på grund av olika yttre påverkan: elektriska störningar, dåliga väderförhållanden och många andra. Kärnan i tekniken är att med goda egenskaper hos kontrollsumman, i de allra flesta fall, kommer ett fel i meddelandet att leda till en förändring av dess kontrollsumma. Om de ursprungliga och beräknade summorna inte är lika, fattas ett beslut om ogiltigheten av den mottagna datan, och en omsändning av paketet kan begäras.

Matematisk beskrivning

CRC-algoritmen är baserad på egenskaperna för division med en återstod av binära polynom, det vill säga polynom över ett ändligt fält . CRC-värdet är i huvudsak resten av att dividera polynomet som motsvarar inmatningen med något fast generatorpolynom . $GF(2)$

Varje ändlig sekvens av bitar är en-till-en associerad med ett binärt polynom vars koefficientsekvens är den ursprungliga sekvensen. Till exempel motsvarar bitsekvensen 1011010 polynomet: $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.

Antalet distinkta polynom av grad mindre än är lika med , vilket är samma som antalet av alla binära längdsekvenser . $N$ $2^N$ $N$

Kontrollsummans värde i en algoritm med en genererande polynomgrad definieras som en bitsekvens av längd , som representerar polynomet vilket resulterar i att resten av polynomet , som representerar den ingående bitströmmen, divideras med polynomet : $G(x)$ $N$ $N$ $R(x)$ $P(x)$ $G(x)$

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

var

R(x)

är ett polynom som representerar CRC-värdet;

P(x)

är ett polynom vars koefficienter representerar indata;

G(x)

är ett genererande polynom;

N

är graden av det genererande polynomet.

Multiplikation utförs genom att tilldela noll bitar till ingångssekvensen, vilket förbättrar kvaliteten på hashning för korta ingångssekvenser. $x^N$ $N$

När man dividerar med en rest av olika ursprungliga polynom med ett genererande polynom av grad , kan man få olika rester från division. är ofta ett irreducerbart polynom . Den väljs vanligtvis i enlighet med kraven för en hashfunktion i sammanhanget för varje enskild applikation. $G(x)$ $N$ $2^{N}$ $G(x)$

Det finns dock många standardiserade polynomgeneratorer som har goda matematiska egenskaper och korrelationsegenskaper (minsta antal kollisioner , enkel beräkning), av vilka några listas nedan.

CRC-beräkning

Algoritmparametrar

En av huvudparametrarna för CRC är det genererande polynomet.

En annan parameter associerad med generatorpolynomet är dess grad , som bestämmer antalet bitar som används för att beräkna CRC-värdet. I praktiken är 8-, 16- och 32-bitars ord de vanligaste, vilket är en konsekvens av särdragen i arkitekturen för modern datorteknik.

En annan parameter är ordets initiala (start)värde. Dessa parametrar definierar helt den "traditionella" CRC-beräkningsalgoritmen. Det finns också modifieringar av algoritmen, till exempel genom att använda omvänd ordning av bearbetningsbitar.

Beskrivning av proceduren

Det första ordet är hämtat från filen - det kan vara en bit (CRC-1), byte (CRC-8) eller något annat element. Om den mest signifikanta biten i ordet är "1", så flyttas ordet åt vänster med en bit, följt av en XOR- operation med ett genererande polynom. Följaktligen, om den mest signifikanta biten i ordet är "0", utförs inte XOR-operationen efter skiftet . Efter skiftet förloras den mest signifikanta biten, och nästa bit från filen laddas i stället för den minst signifikanta biten, och operationen upprepas tills den sista biten i filen laddas. Efter att ha gått igenom hela filen finns resten kvar i ordet, vilket är kontrollsumman.

Populära och standardiserade polynom

Medan cykliska redundanskoder är en del av standarderna, har denna term inte en allmänt accepterad definition - tolkningarna av olika författare motsäger ofta varandra [1] [5] .

Denna paradox gäller även för valet av ett generatorpolynom: ofta är standardiserade polynom inte de mest effektiva när det gäller de statistiska egenskaperna för deras motsvarande kontrollredundanskod .

Men många ofta använda polynom är inte de mest effektiva av alla möjliga. 1993-2004 var en grupp forskare engagerade i studien av att generera polynom med kapacitet upp till 16 [1] 24 och 32 bitar [6] [7] och fann polynom som ger bättre prestanda än standardiserade polynom när det gäller kodavstånd [7] . Ett av resultaten av denna studie har redan hittat sin väg in i iSCSI- protokollet .

Det mest populära och rekommenderade IEEE -polynomet för CRC-32 används i Ethernet , FDDI ; även detta polynom är en Hamming-kodgenerator [8] . Genom att använda ett annat polynom - CRC-32C - kan du uppnå samma prestanda med längden på det ursprungliga meddelandet från 58 bitar till 131 kbps, och i vissa områden av längden på inmatningsmeddelandet kan det vara ännu högre, så det är också populär idag [7] . Till exempel använder ITU-T G.hn-standarden CRC-32C för att upptäcka fel i nyttolasten.

Tabellen nedan listar de vanligaste polynomen - CRC-generatorer. I praktiken kan beräkningen av CRC innefatta pre- och post-inversion, såväl som den omvända ordningen för bitbehandling. Proprietära implementeringar av CRC använder initiala registervärden som inte är noll för att göra koden svårare att tolka.

namn	Polynom	Representationer: [9] normal / omvänd / omvänd från omvänd
CRC-1	$x+1$ (används i maskinvarufelkontroll; även känd 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- tokenpaket)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ ( ITU G.704 [13] )	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (telekommunikationssystem, 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- trådsbuss )	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$ (telekommunikationssystem [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] , många andra; även känd som CRC-16 och 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	Inte CRC; se Fletchers kontrollsumma	Används 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	Inte 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 nyttolast)	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$ (flyg; 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

Befintliga standarder CRC-128 (IEEE) och CRC-256 (IEEE) för närvarande[ när? ] har ersatts av kryptografiska hashfunktioner .

CRC Algoritm Specifikationer

En av de mest kända är Ross N. Williams teknik [25] . Den använder följande alternativ:

Namnet på algoritmen ( namn );

Graden av den kontrollsumma som genererar polynom ( width );

Själva det genererande polynomet ( poly ). För att skriva det som ett värde skrivs det först som en bitsekvens, medan den mest signifikanta biten utelämnas - det är alltid 1. Till exempel kommer ett polynom i denna notation att skrivas som ett tal . För enkelhetens skull skrivs den resulterande binära representationen i hexadecimal form. För vårt fall kommer det att vara lika med eller 0x11; $x^8+x^4+1$ $00010001_2$ $11_h$

Startdata ( init ), det vill säga registrens värden vid tidpunkten för starten av beräkningar;

Flaggan ( RefIn ), som indikerar starten och riktningen för beräkningen, måste matcha sändningsordningen i kanalen för att detektera felskurar. Det finns två alternativ: False - börjar med den mest signifikanta biten ( MSB -först) eller True - börjar med den minst signifikanta biten ( LSB -först);

Flagga ( RefOut ) som bestämmer om ordningen på registerbitarna inverteras när XOR- elementet går in ;

Antalet ( XorOut ) med vilket resultatet adderas modulo 2 ;

CRC-värdet ( check ) för strängen "123456789" .

Exempel [26]

namn	Bredd	Poly	I det	RefIn	Ref Out	XorOut	Kolla upp
CRC-3/ROHC	3	0x3	0x7	Sann	Sann	0x0	0x6
CRC-4/ITU	fyra	0x3	0x0	Sann	Sann	0x0	0x7
CRC-5/EPC	5	0x9	0x9	falsk	falsk	0x0	0x0
CRC-5/ITU	5	0x15	0x0	Sann	Sann	0x0	0x7
CRC-5/USB	5	0x5	0x1F	Sann	Sann	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	Sann	Sann	0x0	0x26
CRC-6/ITU	6	0x3	0x0	Sann	Sann	0x0	0x6
CRC-7	7	0x9	0x0	falsk	falsk	0x0	0x75
CRC-7/ROHC	7	0x4F	0x7F	Sann	Sann	0x0	0x53
CRC-8	åtta	0x7	0x0	falsk	falsk	0x0	0xF4
CRC-8/CDMA2000	åtta	0x9B	0xFF	falsk	falsk	0x0	0xDA
CRC-8/DARC	åtta	0x39	0x0	Sann	Sann	0x0	0x15
CRC-8/DVB-S2	åtta	0xD5	0x0	falsk	falsk	0x0	0xBC
CRC-8/EBU	åtta	0x1D	0xFF	Sann	Sann	0x0	0x97
CRC-8/I-CODE	åtta	0x1D	0xFD	falsk	falsk	0x0	0x7E
CRC-8/ITU	åtta	0x7	0x0	falsk	falsk	0x55	0xA1
CRC-8/MAXIM	åtta	0x31	0x0	Sann	Sann	0x0	0xA1
CRC-8/ROHC	åtta	0x7	0xFF	Sann	Sann	0x0	0xD0
CRC-8/WCDMA	åtta	0x9B	0x0	Sann	Sann	0x0	0x25
CRC-10	tio	0x233	0x0	falsk	falsk	0x0	0x199
CRC-10/CDMA2000	tio	0x3D9	0x3FF	falsk	falsk	0x0	0x233
CRC-11	elva	0x385	0x1A	falsk	falsk	0x0	0x5A3
CRC-12/3GPP	12	0x80F	0x0	falsk	Sann	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	fjorton	0x805	0x0	Sann	Sann	0x0	0x82D
CRC-15	femton	0x4599	0x0	falsk	falsk	0x0	0x59E
CRC-15/MPT1327	femton	0x6815	0x0	falsk	falsk	0x1	0x2566
CRC-16/ARC	16	0x8005	0x0	Sann	Sann	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	Sann	Sann	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	Sann	Sann	0xFFFF	0x44C2
CRC-16/MCRF4XX	16	0x1021	0xFFFF	Sann	Sann	0x0	0x6F91
CRC-16/RIELLO	16	0x1021	0xB2AA	Sann	Sann	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	Sann	Sann	0x0	0x26B1
CRC-16/USB	16	0x8005	0xFFFF	Sann	Sann	0xFFFF	0xB4C8
CRC-A	16	0x1021	0xC6C6	Sann	Sann	0x0	0xBF05
CRC-16/KERMIT	16	0x1021	0x0	Sann	Sann	0x0	0x2189
CRC-16/MODBUS	16	0x8005	0xFFFF	Sann	Sann	0x0	0x4B37
CRC-16/X-25	16	0x1021	0xFFFF	Sann	Sann	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	Sann	Sann	0xFFFFFFFF	0xCBF43926
CRC-32/BZIP2	32	0x4C11DB7	0xFFFFFFFF	falsk	falsk	0xFFFFFFFF	0xFC891918
CRC-32C	32	0x1EDC6F41	0xFFFFFFFF	Sann	Sann	0xFFFFFFFF	0xE3069283
CRC-32D	32	0xA833982B	0xFFFFFFFF	Sann	Sann	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	Sann	Sann	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	Sann	Sann	0xFFFFFFFFFFFFFF	0x995DC9BBDF1939FA

Anteckningar

↑ 1 2 3 4 5 Philip Koopman, Tridib Chakravarty. Cyklisk redundanskod (CRC) Polynomval för inbyggda nätverk (2004). Datum för ansökan: ???. Arkiverad från originalet den 22 augusti 2011. (obestämd)
↑ Internetuniversitet av informationsteknologi. Föreläsning: Organisation av trådlösa nätverk
↑ Internetuniversitet av informationsteknologi. Föreläsning: Ethernet/Fast Ethernet Network Algorithms
↑ Walma, M.; Pipelined Cyclic Redundancy Check (CRC) Beräkning
↑ Greg Cook. Katalog över parametriserade CRC-algoritmer (29 april 2009). Datum för ansökan: ???. Arkiverad från originalet den 22 augusti 2011. (obestämd)
↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimering av cykliska redundanskontrollkoder med 24 och 32 paritetsbitar // 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-bitars cykliska redundanskoder för internetapplikationer // Den internationella konferensen om pålitliga system och nätverk. - Juni 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .
↑ Brayer, K; Hammond, JL Jr. (december 1975). "Utvärdering av feldetekteringspolynomprestanda på AUTOVON-kanalen". konferensrekord . National Telecommunications Conference, New Orleans, La. 1 . New York: Institute of Electrical and Electronics Engineers. pp. 8-21 till 8-25. Utfasad parameter används |month=( hjälp )
↑ Den mest signifikanta biten utelämnad i representationer.
↑ G.704 , sid. 12
↑ Klass-1 Generation-2 UHF RFID-protokoll version 1.2.0 . - 23 oktober 2008. - S. 35 . Arkiverad från originalet den 20 november 2008.
↑ G.704 , sid. 9
↑ G.704 , sid. 3
↑ G.707: Nätverksnodgränssnitt för den synkrona digitala hierarkin (SDH)
↑ G.832: Transport av SDH-element på PDH-nätverk — Ram- och multiplexeringsstrukturer
↑ EN 302 307 Digital Video Broadcasting (DVB); Andra generationens ramstruktur, kanalkodning och moduleringssystem för broadcasting, interaktiva tjänster, nyhetsinsamling och andra bredbandsatellittillämpningar (DVB-S2)
↑ 1 2 FlexRay Protocol Specification version 2.1 Revision A. - 22 december 2005. - P. 93 .
↑ A. Perez, Wismer, Becker. Byte-Wise CRC-beräkningar // IEEE Micro. - 1983. - V. 3 , nr 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .
↑ TV Ramabadran, SS Gaitonde. En handledning om CRC-beräkningar // IEEE Micro. - 1988. - V. 8 , nr 4 . - S. 62-75 . - doi : 10.1109/40.7773 .
↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 16 oktober 2009. Arkiverad från originalet 1 oktober 2009. (obestämd)
↑ Pat Thaler. 16-bitars CRC-polynomval . INCITS T10 (28 augusti 2003). Datum för ansökan: ???. Arkiverad från originalet den 22 augusti 2011. (obestämd)
↑ Thomas Boutell, Glenn Randers-Pehrson et al. PNG-specifikation (Portable Network Graphics), version 1.2 (14 juli 1998). Datum för ansökan: ???. Arkiverad från originalet den 22 augusti 2011. (obestämd)
↑ AIXM Primer version 4.5 . Europeiska organisationen för säkerhet inom flygtrafiken (20 mars 2006). Datum för ansökan: ???. Arkiverad från originalet den 22 augusti 2011. (obestämd)
↑ ECMA-182 sid. 51
↑ Ross N. Williams. CRC Rocksoft (inte tillgänglig länk) (1993). Hämtad 17 april 2012. Arkiverad från originalet 3 september 2011. (obestämd)
↑ Greg Cook. Katalog över parametriserade CRC-algoritmer (18 januari 2016). (obestämd)

Litteratur

Henry S. Warren, Jr. Kapitel 5 Räkna bitar // Algoritmiska knep för programmerare = Hacker's Delight. — M .: Williams , 2007. — 288 sid. — ISBN 0-201-91465-4 .

Länkar

En grundläggande guide till CRC-feldetekteringsalgoritmer
CRC och hur man återställer det
CRC Function Generator i VHDL och Verilog
Ross N. Williams/Anarchriz. Allt om CRC32 // Ross N. Williams. En grundläggande guide till CRC-feldetekteringsalgoritmer
Ross N. Williams. EN SMARTFRI GUIDE TILL CRC FELDETEKTIONSALGORITMER

CRC-kalkylatorer

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA