Cyclische redundantiecontrole

A cyclische redundantiecontrole (CRC) is een Foutdetectiecode Vaak gebruikt in digitaal netwerk en opslagapparaten om accidentele wijzigingen in digitale gegevens te detecteren. Gegevensblokken die deze systemen invoeren, krijgen een korte Controleer waarde bijgevoegd, gebaseerd op de rest van een polynoomverdeling van hun inhoud. Bij het ophalen wordt de berekening herhaald en in het geval dat de controlewaarden niet overeenkomen, kunnen corrigerende maatregelen worden genomen tegen gegevenscorruptie. CRC's kunnen worden gebruikt foutcorrectie (zien bitfilters).^[1]

CRC's worden zo genoemd omdat de controleren (gegevensverificatie) Waarde is een ontslag (het breidt het bericht uit zonder toe te voegen informatie) en de algoritme is gebaseerd op cyclisch codes. CRC's zijn populair omdat ze eenvoudig te implementeren zijn in binair hardware, gemakkelijk om wiskundig te analyseren, en bijzonder goed in het detecteren van gemeenschappelijke fouten veroorzaakt door lawaai in transmissiekanalen. Omdat de cheque -waarde een vaste lengte heeft, de functie die het genereert, wordt af en toe gebruikt als een hash-functie.

Invoering

CRC's zijn gebaseerd op de theorie van cyclisch Foutcorrectiecodes. Het gebruik van systematisch Cyclische codes, die berichten coderen door een controlewaarde met een vaste lengte toe te voegen, voor het doel van foutdetectie in communicatienetwerken, werden eerst voorgesteld door W. Wesley Peterson in 1961.^[2] Cyclische codes zijn niet alleen eenvoudig te implementeren, maar hebben het voordeel dat ze bijzonder geschikt zijn voor de detectie van uitbarstfouten: aaneengesloten reeksen van foutieve gegevenssymbolen in berichten. Dit is belangrijk omdat burst -fouten in velen veel voorkomende transmissiefouten zijn communicatie kanalen, inclusief magnetische en optische opslagapparaten. Meestal een n-bit CRC toegepast op een gegevensblok met willekeurige lengte zal een enkele foutblokkeer niet langer detecteren dan n bits, en de fractie van alle langere foutuitbarstingen die het zal detecteren is (1 - 2⁻ⁿ).

Specificatie van een CRC-code vereist een definitie van een zogenaamde generator polynoom. Deze polynoom wordt de deler in een Polynomiale lange divisie, die de boodschap aanneemt als de dividend en waarin de quotiënt wordt weggegooid en de rest wordt het resultaat. Het belangrijke voorbehoud is dat het polynoom coëfficiënten worden berekend op basis van de rekenkunde van een eindige veld, dus de toevoegingsbewerking kan altijd bitgewijs parallel worden uitgevoerd (er is geen carry tussen cijfers).

In de praktijk gebruiken alle vaak gebruikte CRC's de Galois Field, of eenvoudiger een eindig veld, van twee elementen, GF (2). De twee elementen worden meestal 0 en 1 genoemd, comfortabel bijpassende computerarchitectuur.

Een CRC wordt een n-bit CRC wanneer de cheque -waarde is n bits lang. Voor een gegeven n, Meerdere CRC's zijn mogelijk, elk met een ander polynoom. Zo'n polynoom heeft de hoogste graad n, wat betekent dat het heeft n + 1 Voorwaarden. Met andere woorden, de polynoom heeft een lengte van n + 1; de codering ervan vereist n + 1 bits. Merk op dat de meeste polynoomspecificaties de MSB of LSB, omdat ze altijd zijn 1. De CRC en bijbehorende polynoom hebben meestal een naam van de vorm Crc-n-Xxx zoals in de tafel onderstaand.

Het eenvoudigste foutdetectiesysteem, het pariteitsbit, is in feite een 1-bit CRC: het gebruikt de generatorpolynoomx + 1 (twee termen),^[3] en heeft de naam CRC-1.

Sollicitatie

Een CRC-apparaat berekent een korte binaire volgorde van een korte lengte, bekend als de Controleer waarde of CRC, om elk blok van gegevens te verzonden of opgeslagen te worden en toe te voegen aan de gegevens, waardoor een codewoord.

Wanneer een codewoord wordt ontvangen of gelezen, vergelijkt het apparaat de controlewaarde met één vers berekend uit het gegevensblok, of gelijktijdig, voert een CRC uit op het hele codewoord en vergelijkt de resulterende controlewaarde met een verwacht residu constante.

Als de CRC -waarden niet overeenkomen, bevat het blok een gegevensfout.

Het apparaat kan corrigerende maatregelen ondernemen, zoals het herlezen van het blok of vragen dat het opnieuw wordt verzonden. Anders worden de gegevens verondersteld foutvrij te zijn (hoewel met enige kleine waarschijnlijkheid niet-gedetecteerde fouten kan bevatten; dit is inherent aan de aard van foutencontrole).^[4]

Data-integriteit

CRC's zijn specifiek ontworpen om te beschermen tegen veelvoorkomende soorten fouten op communicatiekanalen, waar ze een snelle en redelijke zekerheid kunnen bieden van de integriteit van geleverde berichten. Ze zijn echter niet geschikt voor het beschermen tegen opzettelijke wijziging van gegevens.

Ten eerste, omdat er geen authenticatie is, kan een aanvaller een bericht bewerken en de CRC opnieuw berekenen zonder dat de vervanging wordt gedetecteerd. Wanneer ze naast de gegevens worden opgeslagen, beschermen CRC's en cryptografische hash zelf niet tegen opzettelijk Wijziging van gegevens. Elke toepassing die bescherming vereist tegen dergelijke aanvallen moet cryptografische authenticatiemechanismen gebruiken, zoals Berichtverificatiecodes of Digitale handtekeningen (die gewoonlijk zijn gebaseerd op Cryptografische hash functies).

Ten tweede is CRC, in tegenstelling tot cryptografische hashfuncties, een gemakkelijk omkeerbare functie, waardoor het ongeschikt is voor gebruik in digitale handtekeningen.^[5]

Ten derde voldoet CRC aan een relatie vergelijkbaar met die van een lineaire functie (of meer nauwkeurig, een affiene functie):^[6]

${\ DisplayStyle \ OperatorName {Crc} (X \ OPLUS Y) = \ OperatorName {Crc} (X) \ OPLUS \ OperatorName {Crc} (Y) \ OPLUS C}$

waar ${\ displaystyle c}$ hangt af van de lengte van ${\ displaystyle x}$ en ${\ displaystyle y}$. Dit kan ook als volgt worden vermeld, waar ${\ displaystyle x}$, ${\ displaystyle y}$ en ${\ DisplayStyle Z}$ hebben dezelfde lengte

${\ DisplayStyle \ OperatorName {Crc} (X \ OPLUS Y \ OPLUS Z) = \ OperatorName {Crc} (X) \ OPLUS \ OperatorName {Crc} (Y) \ OPLUS \ OperatorName {Crc} (Z);};};$

Als gevolg hiervan, zelfs als de CRC is gecodeerd met een Stream cijfer dat gebruikt XOR als zijn combinerende operatie (of modus van Blokcijfer die het effectief verandert in een stroomcijfer, zoals OFB of CFB), kunnen zowel de boodschap als de bijbehorende CRC worden gemanipuleerd zonder kennis van de coderingssleutel; Dit was een van de bekende ontwerpfouten van de Wired Equivalent Privacy (WEP) protocol.^[7]

Berekening

Om een n-bit binaire CRC, lijn de bits in die de invoer op een rij vertegenwoordigen en plaats de (n + 1) -bitpatroon dat de deler van de CRC vertegenwoordigt (een "genoemd"polynoom") Onder het linkeruiteinde van de rij.

In dit voorbeeld zullen we 14 bits berichten coderen met een 3-bit CRC, met een polynoom x³ + x + 1. De polynoom is in binair geschreven als de coëfficiënten; Een 3e graad polynoom heeft 4 coëfficiënten (1x³ + 0x² + 1x + 1). In dit geval zijn de coëfficiënten 1, 0, 1 en 1. Het resultaat van de berekening is 3 bits lang, daarom wordt het een 3-bit CRC genoemd. U hebt echter 4 bits nodig om de polynoom expliciet te vermelden.

Begin met het te coderen bericht:

11010011101100 

Dit wordt eerst opgevuld met nullen die overeenkomen met de bitlengte n van de CRC. Dit wordt gedaan zodat het resulterende codewoord binnen is systematisch het formulier. Hier is de eerste berekening voor het berekenen van een 3-bit CRC:

11010011101100 000 <--- Input rechts opgevuld met 3 bits 1011 <--- deler (4 bits) = x³ + x + 1 ------------------ 01100011101100 000 <- -- resultaat

Het algoritme werkt op de bits direct boven de deler in elke stap. Het resultaat voor die iteratie is de bitgewijze XOR van de polynoomdeler met de bits erboven. De bits niet boven de deler worden eenvoudig hieronder direct hieronder gekopieerd voor die stap. De deler wordt vervolgens naar rechts verschoven om aan te passen aan de hoogst resterende 1 bit in de invoer, en het proces wordt herhaald totdat de deler het rechteruiteinde van de ingangsrij bereikt. Hier is de volledige berekening:

11010011101100 000 <--- Input rechts opgevuld met 3 bits 1011 <--- Deler 01100011101100 000 <--- Resultaat (Opmerking De eerste vier bits zijn de XOR met de divisie eronder, de rest van de bits zijn ongewijzigd) 1011 <- -Divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- Merk op dat de deler zich beweegt om af te stemmen op de volgende 1 in het dividend (omdat quotiënt voor die stap nul was) 1011 (met andere woorden, het doet het 'T noodzakelijkerwijs een bit per iteratie verplaatsen) 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <-Rest (3 bits) . Divisie -algoritme stopt hier omdat het dividend gelijk is aan nul.

Aangezien de meest linkse deler elke invoerbit die het heeft aangeraakt, is het aangeraakt, wanneer dit proces eindigt, zijn de enige bits in de inputrij die niet-nul kunnen zijn de n bits aan de rechterkant van de rij. Deze n Bits zijn de rest van de divisiestap en zullen ook de waarde van de CRC -functie zijn (tenzij de gekozen CRC -specificatie om enkele nabewerking vereist).

De geldigheid van een ontvangen bericht kan eenvoudig worden geverifieerd door de bovenstaande berekening opnieuw uit te voeren, dit keer met de toegevoegde controle in plaats van nullen. De rest moet nul gelijk zijn als er geen detecteerbare fouten zijn.

11010011101100 100 <--- Input met controlewaarde 1011 <--- Deler 01100011101100 100 <--- Resultaat 1011 <--- Deler ... 0011101111100 100 ...... 00000000001110 100 1011 0000000000010101 100 101 1 --- --------------- 0000000000000000 000 <--- RESTER

Het volgende Python Code schetst een functie die de initiële CRC -rest voor een gekozen invoer en polynoom zal retourneren, met 1 of 0 als de initiële vulling. Merk op dat deze code werkt met stringingangen in plaats van ruwe nummers:

def CRC_REMAINDER(input_bitstring, polynomial_bitstring, initial_filler):  "" "Bereken de CRC -rest van een reeks bits met behulp van een gekozen polynoom.     Initial_filler moet '1' of '0' zijn.     "" "  polynomial_bitstring = polynomial_bitstring.lstrip('0')  len_input = Len(input_bitstring)  initial_padding = (Len(polynomial_bitstring) - 1) * initial_filler  input_padded_array = lijst(input_bitstring + initial_padding)  terwijl '1' in input_padded_array[:len_input]:  cur_shift = input_padded_array.inhoudsopgave('1')  voor i in bereik(Len(polynomial_bitstring)):  input_padded_array[cur_shift + i] \  = STR(inteken(polynomial_bitstring[i] ! = input_padded_array[cur_shift + i]))  opbrengst ''.meedoen(input_padded_array) [len_input:] def CRC_CHECK(input_bitstring, polynomial_bitstring, check_value):  "" "Bereken de CRC -controle van een reeks bits met behulp van een gekozen polynoom." ""  polynomial_bitstring = polynomial_bitstring.lstrip('0')  len_input = Len(input_bitstring)  initial_padding = check_value  input_padded_array = lijst(input_bitstring + initial_padding)  terwijl '1' in input_padded_array[:len_input]:  cur_shift = input_padded_array.inhoudsopgave('1')  voor i in bereik(Len(polynomial_bitstring)):  input_padded_array[cur_shift + i] \  = STR(inteken(polynomial_bitstring[i] ! = input_padded_array[cur_shift + i]))  opbrengst ('1' niet in ''.meedoen(input_padded_array) [len_input:]) 

>>> CRC_REMAINDER('11010011101100', '1011', '0') '100' >>> CRC_CHECK('11010011101100', '1011', '100') WAAR 

CRC-32-algoritme

Dit is een praktisch algoritme voor de CRC-32-variant van CRC.^[8] De crctable is een memoisering van een berekening die zou moeten worden herhaald voor elke byte van de boodschap (Berekening van cyclische redundantiecontroles § Multi-bit berekening).

Functie CRC32 Invoer:       Gegevens: bytes // reeks bytes  Uitvoer:       CRC32: UINT32 // 32-bit niet-ondertekende CRC-32-waarde
 // Initialiseer CRC-32 in startwaarde CRC32 ← 0xffffffff
 Voor elk byte in gegevens doen    nLookupIndex ← (CRC32 XOR BYTE) en 0xFF CRC32 ← (CRC32 SHR 8) XOR CRCTABLE [NLOOKUPINDEX] // crctable is een reeks van 256 32-bit constanten
 // voltooi de CRC-32-waarde door alle bits om te keren CRC32 ← CRC32 XOR 0XFFFFFFFopbrengst CRC32

In C ziet het algoritme als zodanig uit:

#erbij betrekken  // uint32_t, uint8_t uint32_t CRC32(const uint8_t gegevens[], size_t Data_length) { 	uint32_t CRC32 = 0xffffffffu; 	 	voor (size_t i = 0; i < Data_length; i++) { 		const uint32_t lookupIndex = (CRC32 ^ gegevens[i])) & 0xff; 		CRC32 = (CRC32 >> 8) ^ Beschadigd[lookupIndex];  // crctable is een reeks van 256 32-bit constanten 	} 	 	// voltooi de CRC-32-waarde door alle bits om te keren 	CRC32 ^= 0xffffffffu; 	opbrengst CRC32; } 

Wiskunde

Wiskundige analyse van dit divisie-achtige proces laat zien hoe een deler te selecteren die goede foutdetectie-eigenschappen garandeert. In deze analyse worden de cijfers van de bitreeksen in een of andere variabele als de coëfficiënten van een polynoom genomen x—Coëfficiënten die elementen van het eindige veld zijn GF (2) (De Modulo 2 van de gehele getallen, d.w.z. een nul of een), in plaats van meer bekende getallen. De set binaire polynomen is een wiskundige ring.

Polynomen ontwerpen

De selectie van de generatorpolynoom is het belangrijkste onderdeel van de implementatie van het CRC -algoritme. De polynoom moet worden gekozen om de foutdetecterende mogelijkheden te maximaliseren en tegelijkertijd de algehele botsingskansen te minimaliseren.

Het belangrijkste kenmerk van de polynoom is de lengte (grootste graad (exponent) +1 van een term in de polynoom), vanwege de directe invloed op de lengte van de berekende controlewaarde.

De meest gebruikte polynoomlengtes zijn 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32) en 65 bits (CRC-64).^[3]

Een CRC wordt een n-bit CRC wanneer de cheque -waarde is n-Bits. Voor een gegeven n, Meerdere CRC's zijn mogelijk, elk met een ander polynoom. Zo'n polynoom heeft de hoogste graad n, en daarom n + 1 termen (de polynoom heeft een lengte van n + 1). De rest heeft lengte n. De CRC heeft een naam van het formulier Crc-n-Xxx.

Het ontwerp van het CRC -polynoom hangt af van de maximale totale lengte van het te beschermen blok (data + CRC -bits), de gewenste foutbeschermingsfuncties en het type bronnen voor het implementeren van de CRC, evenals de gewenste prestaties. Een veel voorkomende misvatting is dat de "beste" CRC -polynomen van beide zijn afgeleid onherleidbare polynomen of onherleidbare polynomen maal de factor1 + x, die aan de code bijdraagt, de mogelijkheid om alle fouten te detecteren die een oneven aantal bits beïnvloeden.^[9] In werkelijkheid moeten alle hierboven beschreven factoren de selectie van de polynoom aangaan en kunnen leiden tot een herleidbare polynoom. Het kiezen van een reduceerbaar polynoom zal echter resulteren in een bepaald deel van de gemiste fouten, omdat de quotiëntring heeft nul divisors.

Het voordeel van het kiezen van een primitief polynoom Aangezien de generator voor een CRC-code is dat de resulterende code een maximale totale bloklengte heeft in de zin dat alle 1-bits fouten binnen die bloklengte verschillende resten hebben (ook wel genoemd syndromen) en daarom, omdat de rest een lineaire functie van het blok is, kan de code alle 2-bits fouten binnen die bloklengte detecteren. Als ${\ displaystyle r}$ is de mate van de primitieve generatorpolynoom, dan is de maximale totale bloklengte ${\ DisplayStyle 2^{r} -1}$, en de bijbehorende code kan eventuele fouten met één bit of dubbel bits detecteren.^[10] We kunnen deze situatie verbeteren. Als we de generatorpolynoom gebruiken ${\ displaystyle g (x) = p (x) (1+x)}$, waar ${\ displaystyle p}$ is een primitieve polynoom van graad ${\ displaystyle r-1}$, dan is de maximale totale bloklengte ${\ DisplayStyle 2^{r-1} -1}$, en de code kan single, dubbel, drievoudig en oneven aantal fouten detecteren.

Een polynoom ${\ displaystyle g (x)}$ Dat toegeeft dat andere factorisaties kunnen worden gekozen om de maximale totale bloklengte in evenwicht te brengen met een gewenste foutdetectievermogen. De BCH -codes zijn een krachtige klasse van dergelijke polynomen. Ze ondervinden de twee bovenstaande voorbeelden. Ongeacht de reduceerbaarheidseigenschappen van een generatorpolynoom van graadr, als het de term "+1" omvat, kan de code foutpatronen detecteren die beperkt zijn tot een venster van r aaneengesloten bits. Deze patronen worden "foutbursts" genoemd.

Specificatie

Het concept van de CRC als een foutdetecterende code wordt ingewikkeld wanneer een implementator of normencommissie het gebruikt om een ​​praktisch systeem te ontwerpen. Hier zijn enkele complicaties:

• Soms een implementatie Voorvoegt een vast bitpatroon naar de bitstream die moet worden gecontroleerd. Dit is handig wanneer klokfouten 0-bits voor een bericht kunnen invoegen, een wijziging die anders de controlewaarde ongewijzigd zou laten.
• Meestal, maar niet altijd, een implementatie toevoegen n 0-bits (n De grootte van de CRC) naar de bitstream die moet worden gecontroleerd voordat de polynoomverdeling optreedt. Dergelijk toevoegen wordt expliciet aangetoond in de Berekening van CRC artikel. Dit heeft het gemak dat de rest van de originele bitstream met de toegevoegde cheque -waarde precies nul is, dus de CRC kan eenvoudig worden gecontroleerd door de polynomiale divisie op de ontvangen bitstream uit te voeren en de rest te vergelijken met nul. Vanwege de associatieve en commutatieve eigenschappen van de exclusieve-of-operatie kunnen praktische tabelgestuurde implementaties een resultaat verkrijgen dat numeriek equivalent is aan nul-uitzending zonder expliciet toe te voegen aan nullen, door een equivalent te gebruiken,^[9] sneller algoritme dat het bericht bitstream combineert met de stroom die uit het CRC -register wordt verschoven.
• Soms een implementatie exclusief-ors een vast bit patroon in de rest van de polynoomverdeling.
• Bit bestelling: Sommige schema's beschouwen het lage-orde bit van elke byte als "eerste", wat vervolgens tijdens polynoomverdeling "linkmost" betekent, wat in strijd is met ons gebruikelijke begrip van "lage orde". Deze conventie is logisch wanneer seriepoort Transmissies zijn CRC-gecontroleerd in hardware, omdat sommige wijdverspreide seriële port transmissie-conventies eerst bytes die het minst significante bit overbrengen.
• Byte -bestelling: Met multi-byte CRC's kan er verwarring zijn over de vraag of de byte die eerst wordt uitgezonden (of opgeslagen in de laagst geadresseerde byte van geheugen) de minst significante byte (LSB) of de meest significante byte (MSB) is. Sommige 16-bit CRC-schema's verwisselen bijvoorbeeld de bytes van de controlewaarde.
• Weglating van het bit van hoge orde van de divisor polynomiaal: omdat het bit van hoge orde altijd 1 is, en omdat een n-bit CRC moet worden gedefinieerd door een (n + 1) -bit deler die overstromen een n-beetje register, sommige schrijvers gaan ervan uit dat het onnodig is om het bit van de deler te vermelden.
• Weglating van het lage-orde bit van de divisor polynomiaal: omdat het bit met lage orde altijd 1 is, vertegenwoordigen auteurs zoals Philip Koopman polynomen met hun bit intact, maar zonder het lage-orde bit (de lage orde (de lage orde (de lage orde ${\ displaystyle x^{0}}$ of 1 term). Deze conventie codeert voor de polynoom compleet met zijn graad in één geheel getal.

Deze complicaties betekenen dat er drie gemeenschappelijke manieren zijn om een ​​polynoom als een geheel getal uit te drukken: de eerste twee, die spiegelbeelden in binair zijn, zijn de constanten die in code worden gevonden; De derde is het nummer dat wordt gevonden in de papieren van Koopman. In elk geval wordt één term weggelaten. Dus het polynoom ${\ displaystyle x^{4}+x+1}$ Kan worden getranscribeerd als:

• 0x3 = 0b0011, vertegenwoordigt ${\ displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}}$ (MSB-FIRST-code)
• 0xc = 0b1100, vertegenwoordigt ${\ displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}}$ (LSB-FIRST-code)
• 0x9 = 0b1001, vertegenwoordigt ${\ displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}}$ (Koopman Notation)

In de onderstaande tabel worden ze weergegeven als:

Verduistering

CRC's in eigen protocollen kunnen zijn verdoezeld Door een niet-triviale beginwaarde en een laatste XOR te gebruiken, maar deze technieken voegen geen cryptografische sterkte toe aan het algoritme en kunnen dat zijn omgekeerd ontworpen met behulp van eenvoudige methoden.^[11]

Normen en gemeenschappelijk gebruik

Er zijn talloze soorten cyclische redundantiecontroles opgenomen in Technische normen. In geen geval past één algoritme, of een van elke graad, bij elk doel; Koopman en Chakravarty bevelen aan om een ​​polynoom te selecteren volgens de toepassingsvereisten en de verwachte verdeling van berichtlengtes.^[12] Het aantal verschillende CRC's in gebruik heeft ontwikkelaars verward, een situatie die auteurs hebben geprobeerd aan te pakken.^[9] Er zijn drie polynomen gerapporteerd voor CRC-12,^[12] Tweeëntwintig tegenstrijdige definities van CRC-16 en zeven van CRC-32.^[13]

De algemeen toegepaste polynomen zijn niet de meest efficiënte mogelijke mogelijk. Sinds 1993 hebben Koopman, Castagnoli en anderen de ruimte van polynomen onderzocht tussen 3 en 64 bits in grootte,^{[12][14][15][16]} voorbeelden vinden die veel betere prestaties hebben (in termen van Hamming -afstand voor een gegeven berichtgrootte) dan de polynomen van eerdere protocollen, en het publiceren van het beste hiervan met als doel de foutendetectievermogen van toekomstige normen te verbeteren.^[15] Vooral, iSCSI en SCTP hebben een van de bevindingen van dit onderzoek aangenomen, de CRC-32C (Castagnoli) polynoom.

Het ontwerp van de 32-bit polynoom die het meest wordt gebruikt door standaardenlichamen, CRC-32-ieee, was het resultaat van een gezamenlijke inspanning voor de Rome Laboratorium en de Air Force Electronic Systems Division door Joseph Hammond, James Brown en Shyan-Shiang Liu van de Georgia Instituut van Technologie en Kenneth Brayer van de Mitre Corporation. De vroegst bekende optredens van de 32-bit polynomiale waren in hun publicaties van 1975: Technical Report 2956 door Brayer voor MITER, gepubliceerd in januari en vrijgegeven voor openbare verspreiding tot door openbare verspreiding DTIC in augustus,^[17] en Hammond, Brown en Liu's rapport voor het Rome Laboratory, gepubliceerd in mei.^[18] Beide rapporten bevatten bijdragen van het andere team. In december 1975 presenteerden Brayer en Hammond hun werk in een krant op de IEEE National Telecommunications Conference: de IEEE CRC-32 Polynomial is het genererende polynoom van een Hamming Code en werd geselecteerd voor zijn foutdetectieprestaties.^[19] Toch komt de Castagnoli CRC-32C-polynoom die wordt gebruikt in ISCSI of SCTP overeen met zijn prestaties op berichten van 58 bits tot 131 kbits, en overtreft het in verschillende groottes, waaronder de twee meest voorkomende afmetingen van internetpakket.^[15] De Itu-t G.HN Standaard maakt ook gebruik van CRC-32C om fouten in de payload te detecteren (hoewel het CRC-16-CCITT gebruikt voor Phy headers).

CRC-32C-berekening wordt als operatie in hardware geïmplementeerd (CRC32) van SSE4.2 instructieset, voor het eerst geïntroduceerd in Intel processors Nehalem Microarchitectuur. ARM AARCH64 Architectuur biedt ook hardware-versnelling voor zowel CRC-32- als CRC-32C-bewerkingen.

Polynoomrepresentaties van cyclische redundantiecontroles

De onderstaande tabel geeft alleen een overzicht van de polynomen van de verschillende algoritmen die worden gebruikt. Variaties van een bepaald protocol kunnen pre-inversie, post-inversie en omgekeerde bitbestelling opleggen zoals hierboven beschreven. De CRC32 die in GZIP en BZIP2 worden gebruikt, gebruikt bijvoorbeeld dezelfde polynoom, maar GZIP maakt gebruik van omgekeerde bit -bestelling, terwijl BZIP2 dat niet doet.^[13] Merk op dat zelfs pariteitspolynomen in GF (2) met graad groter dan 1 zijn nooit primitief. Zelfs pariteitspolynoom gemarkeerd als primitief in deze tabel vertegenwoordigen een primitief polynoom vermenigvuldigd met ${\ displaystyle \ links (x+1 \ rechts)}$. Het belangrijkste stukje polynoom is altijd 1 en wordt niet getoond in de hex -representaties.

Naam	Toepassingen	Polynomiale representaties				Pariteit[20]	Primitief[21]	Maximale stukjes lading door Hamming -afstand[22][15][21]
		Normaal	Teruggedraaid	Wederkerig	Omgekeerde wederzijds			≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2[23]
CRC-1	de meeste hardware; ook gekend als pariteitsbit	0x1	0x1	0x1	0x1	ook al
		${\ DisplayStyle x+1}$
CRC-3-GSM	mobiele netwerken[24]	0x3	0x6	0x5	0x5	oneven	ja [25]	–	–	–	–	–	–	–	–	–	–	–	–	–	4	∞
		${\ displaystyle x^{3}+x+1}$
CRC-4-UTU	Itu-t G.704, p. 12	0x3	0xc	0x9	0x9	oneven
		${\ displaystyle x^{4}+x+1}$
CRC-5-EPC	Gen 2 RFID[26]	0x09	0x12	0x05	0x14	oneven
		${\ displaystyle x^{5}+x^{3} +1}$
CRC-5-UTU	Itu-t G.704, p. 9	0x15	0x15	0x0b	0x1a	ook al
		${\ displaystyle x^{5}+x^{4}+x^{2} +1}$
CRC-5-USB	USB tokenpakketten	0x05	0x14	0x09	0x12	oneven
		${\ displaystyle x^{5}+x^{2} +1}$
CRC-6-CDMA2000-EEN	mobiele netwerken[27]	0x27	0x39	0x33	0x33	oneven
CRC-6-CDMA2000-B	mobiele netwerken[27]	0x07	0x38	0x31	0x23	ook al
CRC-6-DARC	Gegevensradiokanaal[28]	0x19	0x26	0x0d	0x2c	ook al
CRC-6-GSM	mobiele netwerken[24]	0x2f	0x3d	0x3b	0x37	ook al	ja [29]	–	–	–	–	–	–	–	–	–	–	1	1	25	25	∞
		${\ displaystyle x^{6}+x^{5}+x^{3}+x^{2}+x+1}$
CRC-6-ETU	Itu-t G.704, p. 3	0x03	0x30	0x21	0x21	oneven
		${\ displaystyle x^{6}+x+1}$
CRC-7	Telecomsystemen, ITU-T G.707, Itu-t G.832, MMC, SD	0x09	0x48	0x11	0x44	oneven
		${\ displaystyle x^{7}+x^{3} +1}$
CRC-7-MVB	Treincommunicatienetwerk, IEC 60870-5[30]	0x65	0x53	0x27	0x72	oneven
CRC-8	DVB-S2[31]	0xd5	0xab	0x57	0xea[12]	ook al	nee [32]	–	–	–	–	–	–	–	–	–	–	2	2	85	85	∞
		${\ displaystyle x^{8}+x^{7}+x^{6}+x^{4}+x^{2} +1}$
CRC-8-Autosar	Auto -integratie,[33] Openingsveiligheid[34]	0x2f	0xf4	0xe9	0x97[12]	ook al	ja [32]	–	–	–	–	–	–	–	–	–	–	3	3	119	119	∞
		${\ displaystyle x^{8}+x^{5}+x^{3}+x^{2}+x+1}$
CRC-8-Bluetooth	draadloze connectie[35]	0xa7	0xe5	0xcb	0xd3	ook al
		${\ displaystyle x^{8}+x^{7}+x^{5}+x^{2}+x+1}$
CRC-8-CCITT	Itu-t I.432.1 (02/99); Geldautomaat Hec, Isdn HEC en celafbakening, SMBUS PEC	0x07	0xe0	0xc1	0x83	ook al
		${\ displaystyle x^{8}+x^{2}+x+1}$
CRC-8-Dallas/Maxim	1-draads bus[36]	0x31	0x8c	0x19	0x98	ook al
		${\ displaystyle x^{8}+x^{5}+x^{4} +1}$
CRC-8-DARC	Gegevensradiokanaal[28]	0x39	0x9c	0x39	0x9c	oneven
		${\ displaystyle x^{8}+x^{5}+x^{4}+x^{3} +1}$
CRC-8-GSM-B	mobiele netwerken[24]	0x49	0x92	0x25	0xa4	ook al
		${\ DisplayStyle x^{8}+x^{6}+x^{3} +1}$
CRC-8-SAE J1850	AES3; OBD	0x1d	0xb8	0x71	0x8e	oneven
		${\ displaystyle x^{8}+x^{4}+x^{3}+x^{2} +1}$
CRC-8-WCDMA	mobiele netwerken[27][37]	0x9b	0xd9	0xb3	0xcd[12]	ook al
		${\ displaystyle x^{8}+x^{7}+x^{4}+x^{3}+x+1}$
CRC-10	GELDAUTOMAAT; Itu-t I.610	0x233	0x331	0x263	0x319	ook al
		${\ displaystyle x^{10}+x^{9}+x^{5}+x^{4}+x+1}$
CRC-10-CDMA2000	mobiele netwerken[27]	0x3d9	0x26f	0x0df	0x3ec	ook al
CRC-10-GSM	mobiele netwerken[24]	0x175	0x2ba	0x175	0x2ba	oneven
CRC-11	Flexray[38]	0x385	0x50e	0x21d	0x5c2	ook al
		${\ displaystyle x^{11}+x^{9}+x^{8}+x^{7}+x^{2} +1}$
CRC-12	telecomsystemen[39][40]	0x80f	0xf01	0xe03	0xc07[12]	ook al
		${\ displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-12-CDMA2000	mobiele netwerken[27]	0xf13	0xc8f	0x91f	0xf89	ook al
CRC-12-GSM	mobiele netwerken[24]	0xd31	0x8cb	0x197	0xe98	oneven
CRC-13-BBC	Tijdsignaal, Radio Teleswitch[41][42]	0x1cf5	0x15e7	0x0bcf	0x1e7a	ook al
		${\ displaystyle x^{13}+x^{12}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4} +x^{2} +1}$
CRC-14-DARC	Gegevensradiokanaal[28]	0x0805	0x2804	0x1009	0x2402	ook al
CRC-14-GSM	mobiele netwerken[24]	0x202d	0x2d01	0x1a03	0x3016	ook al
CRC-15-KAN		0xc599[43][44]	0x4cd1	0x19a3	0x62cc	ook al
		${\ displaystyle x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3} +1}$
CRC-15-MPT1327	[45]	0x6815	0x540b	0x2817	0x740a	oneven
CRC-16-Chakravarty	Optimaal voor ladingen ≤64 bits[30]	0x2f15	0xa8f4	0x51e9	0x978a	oneven
CRC-16-Arinc	Acars toepassingen[46]	0xa02b	0xd405	0xa80b	0xd015	oneven
CRC-16-CCITT	X.25, V.41, HDLC FCS, Xmodem, Bluetooth, Pactor, SD, Digrf, vele anderen; bekend als CRC-CCITT	0x1021	0x8408	0x811	0x8810[12]	ook al
		${\ DisplayStyle x^{16}+x^{12}+x^{5} +1}$
CRC-16-CDMA2000	mobiele netwerken[27]	0xc867	0xe613	0xcc27	0xe433	oneven
CRC-16-Desk	draadloze telefoons[47]	0x0589	0x91a0	0x2341	0x82c4	ook al
		${\ displaystyle x^{16}+x^{10}+x^{8}+x^{7}+x^{3} +1}$
CRC-16-T10-Dif	SCSI Dif	0x8bb7[48]	0xedd1	0xdba3	0xc5db	oneven
		${\ displaystyle x^{16}+x^{15}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{4} +x^{2}+x+1}$
CRC-16-DNP	DNP, IEC 870, M-bus	0x3d65	0xa6bc	0x4d79	0x9eb2	ook al
		${\ displaystyle x^{16}+x^{13}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5} +x^{2} +1}$
CRC-16-IBM	Bisync, Modbus, USB, Ansi X3.28, SIA DC-07, vele anderen; ook gekend als CRC-16 en CRC-16-ANTSI	0x8005	0xa001	0x4003	0xc002	ook al
		${\ DisplayStyle x^{16}+x^{15}+x^{2} +1}$
CRC-16-Openingsveiligheid-EEN	Veiligheidsveldbus[34]	0x5935	0xac9a	0x5935	0xac9a[12]	oneven
CRC-16-Openingsveiligheid-B	Veiligheidsveldbus[34]	0x755b	0xdaae	0xb55d	0xbaad[12]	oneven
CRC-16-Profibus	Fieldbus -netwerken[49]	0x1dcf	0xf3b8	0xe771	0x8ee7	oneven
Fletcher-16	Gebruikt in Adler-32 A&B Checksums	Vaak verward om een ​​CRC te zijn, maar eigenlijk een controlesom; zien Fletcher's checksum
CRC-17-CAN	Kan FD[50]	0x1685b	0x1b42d	0x1685b	0x1b42d	ook al
CRC-21-CAN	Kan FD[50]	0x102899	0x132281	0x064503	0x18144c	ook al
CRC-24	Flexray[38]	0x5d6dcb	0xd3b6ba	0xa76d75	0xaeb6e5	ook al
		${\ DisplayStyle 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}$
CRC-24-Radix-64	Openpgp, RTCM104v3	0x864cfb	0xdf3261	0xbe64c3	0xc3267d	ook al
		${\ displaystyle 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}$
CRC-24-WCDMA	Gebruikt in OS-9 RTOS. Residu = 0x800fe3.[51]	0x800063	0xc60001	0x8c0003	0xc00031	ook al	ja[52]	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	∞
		${\ displaystyle x^{24}+x^{23}+x^{6}+x^{5}+x+1}$
CRC-30	CDMA	0x2030b9c7	0x38e74301	0x31ce8603	0x30185ce3	ook al
		${\ displaystyle 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}$
CRC-32	ISO 3309 (HDLC), Ansi X3.66 (ADCCP), FIPS Pub 71, Fed-STD-1003, ITU-T V.42, ISO/IEC/IEEE 802-3 (Ethernet), Sata, MPEG-2, Pkzip, Gzip, BZIP2, Posix CKSUM,[53] PNG,[54] Zmodem, vele anderen	0x04c11db7	0xedb88320	0xDB710641	0x82608edb[15]	oneven	ja	–	10	–	–	12	21	34	57	91	171	268	2974	91607	4294967263	∞
		${\ displaystyle 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}$
CRC-32C (Castagnoli)	iSCSI, SCTP, G.HN lading, SSE4.2, BTRFS, ext4, Ceph	0x1edc6f41	0x82f63b78	0x05EC76F1	0x8f6e37a0[15]	ook al	ja	6	–	8	–	20	–	47	–	177	–	5243	–	2147483615	–	∞
		${\ displaystyle 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}$
CRC-32K (Koopman {1,3,28}))	Uitstekend in Ethernet -framlengte, slechte prestaties met lange bestanden	0x741b8cd7	0xeb31d82e	0xd663b05d	0xba0dc66b[15]	ook al	nee	2	–	4	–	16	–	18	–	152	–	16360	–	114663	–	∞
		${\ displaystyle 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}$
CRC-32K2 (Koopman {1,1,30}))	Uitstekend in Ethernet -framlengte, slechte prestaties met lange bestanden	0x32583499	0x992c1a4c	0x32583499	0x992c1a4c[15]	ook al	nee	–	–	3	–	16	–	26	–	134	–	32738	–	65506	–	∞
CRC-32Q	luchtvaart; Aixm[55]	0x814141AB	0xd5828281	0xab050503	0xc0a0a0d5	ook al
		${\ displaystyle x^{32}+x^{31}+x^{24}+x^{22}+x^{16}+x^{14}+x^{8}+x^{7} +x^{5}+x^{3}+x+1}$
Adler-32		Vaak verward om een ​​CRC te zijn, maar eigenlijk een controlesom; zien Adler-32
CRC-40-GSM	GSM -besturingskanaal[56][57][58]	0x0004820009	0x9000412000	0x2000824001	0x8002410004	ook al
		${\ displaystyle x^{40}+x^{26}+x^{23}+x^{17}+x^{3}+1 = (x^{23} +1) (x^{17} +x^{3} +1)}$
CRC-64-ECMA	ECMA-182 p. 51, XZ Utils	0x42f0e1eba9ea3693	0xc96c5795d7870f42	0x92d8af2baf0e1e85	0xa17870f5d4f51b49	ook al
		${\ DisplayStyle 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}+}$ ${\ displaystyle 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}$
CRC-64-ISO	ISO 3309 (HDLC), Zwitserse prot/Trembl; beschouwd als zwak voor hashing[59]	0x000000000000001B	0xD800000000000000000000	0xb000000000000001	0x800000000000000D	oneven
		${\ DisplayStyle x^{64}+x^{4}+x^{3}+x+1}$

Implementaties

• Implementatie van CRC32 in GNU -radio tot 3.6.1 (ca. 2012)
• C -klasse code voor CRC CheckSum -berekening met veel verschillende CRC's om uit te kiezen

CRC -catalogi

• Catalogus van geparametriseerde CRC -algoritmen
• CRC Polynomial Zoo

Zie ook

• Wiskunde van cyclische redundantiecontroles
• Berekening van cyclische redundantiecontroles
• Lijst met hash -functies
• Lijst met checksum -algoritmen
• Informatiebeveiliging
• Eenvoudige bestandsverificatie
• LRC

Referenties

Verder lezen

• Warren Jr., Henry S. (2013). Hackers genot (2 ed.). Addison Wesley. ISBN 978-0-321-84268-8.

Externe links

• ISO/IEC 13239: 2002: Informatietechnologie-Telecommunicatie- en informatieuitwisseling tussen systemen-Procedures op hoog niveau datalinkcontrole (HDLC)
• CRC32-Castagnoli Linux-bibliotheek