Kontrola cyklické redundance - Cyclic redundancy check

A kontrola cyklické redundance (CRC) je kód pro detekci chyb běžně používané v digitálním formátu sítí a úložná zařízení k detekci náhodných změn nezpracovaných dat. Bloky dat vstupujících do těchto systémů jsou krátké zkontrolujte hodnotu připojeno, na základě zbývající části a polynomiální dělení jejich obsahu. Při načítání se výpočet opakuje a v případě, že se kontrolní hodnoty neshodují, lze podniknout nápravná opatření proti poškození dat. CRC lze použít pro oprava chyb (vidět bitové filtry ).^[1]

CRC se nazývají proto, že šek Hodnota (ověření dat) je a nadbytek (rozšíří zprávu bez přidání informace ) a algoritmus je založeno na cyklický kódy. CRC jsou populární, protože se dají snadno implementovat v binárním formátu Hardware, snadno matematicky analyzovatelný a zvláště dobrý při detekci běžných chyb způsobených hluk v přenosových kanálech. Protože kontrolní hodnota má pevnou délku, funkce který jej generuje, se občas používá jako a hashovací funkce.

CRC vynalezl W. Wesley Peterson v roce 1961; 32bitová funkce CRC, používaná v Ethernetu a mnoha dalších standardech, je dílem několika výzkumníků a byla zveřejněna v roce 1975.

Úvod

CRC jsou založeny na teorii cyklický kódy opravující chyby. Použití systematický cyklické kódy, které kódují zprávy přidáním hodnoty kontroly pevné délky, pro účely detekce chyb v komunikačních sítích, navrhl nejprve W. Wesley Peterson v roce 1961.^[2]Cyklické kódy se nejen snadno implementují, ale mají tu výhodu, že jsou zvláště vhodné pro detekci chyby série: souvislé sekvence chybných datových symbolů ve zprávách. To je důležité, protože chyby shluku jsou u mnoha běžnými chybami přenosu komunikační kanály, včetně magnetických a optických paměťových zařízení. Typicky n-bitový CRC aplikovaný na datový blok libovolné délky detekuje každou jednotlivou chybovou dávku ne delší než n bitů a zlomek všech delších výpadků chyb, které detekuje, je (1 − 2⁻ⁿ).

Specifikace kódu CRC vyžaduje definici tzv polynom generátoru. Tento polynom se stává dělitel v polynomiální dlouhé dělení, který bere zprávu jako dividenda a ve kterém kvocient je vyřazen a zbytek se stane výsledkem. Důležitou výhradou je, že polynom koeficienty se počítají podle aritmetiky a konečné pole, takže operaci přidání lze vždy provést bitově-paralelně (mezi číslicemi není žádný přenos).

V praxi všechny běžně používané CRC používají Galoisovo pole ze dvou prvků, GF (2). Tyto dva prvky se obvykle nazývají 0 a 1 a pohodlně se shodují s architekturou počítače.

CRC se nazývá n-bit CRC, pokud je jeho kontrolní hodnota n bity dlouhé. Za dané n, je možné více CRC, každý s jiným polynomem. Takový polynom má nejvyšší stupeň n, což znamená, že má n + 1 podmínky. Jinými slovy má polynom délku n + 1; jeho kódování vyžaduje n + 1 bity. Všimněte si, že většina polynomiálních specifikací buď upustí MSB nebo LSB, protože jsou vždy 1. CRC a přidružený polynom mají obvykle název ve tvaru CRC-n-XXX jako v stůl níže.

Nejjednodušší systém detekce chyb, paritní bit, je ve skutečnosti 1bitový CRC: používá polynom generátoruX + 1 (dva výrazy) a má název CRC-1.

aplikace

Zařízení s povoleným CRC vypočítá krátkou binární sekvenci s pevnou délkou, známou jako zkontrolujte hodnotu nebo CRC, pro každý blok dat, který má být odeslán nebo uložen, a připojí jej k datům, čímž vytvoří a kódové slovo.

Když je kódové slovo přijato nebo přečteno, zařízení buď porovná svou kontrolní hodnotu s jednou čerstvě vypočítanou z datového bloku, nebo ekvivalentně provede CRC na celém kódovém slovu a porovná výslednou kontrolní hodnotu s očekávanou zbytek konstantní.

Pokud se hodnoty CRC neshodují, obsahuje blok datovou chybu.

Zařízení může přijmout nápravná opatření, například znovu načíst blok nebo požádat o jeho opětovné odeslání. V opačném případě se předpokládá, že data jsou bezchybná (i když s malou pravděpodobností mohou obsahovat nezjištěné chyby; to je vlastní povaze kontroly chyb).^[3]

Integrita dat

CRC jsou speciálně navrženy k ochraně před běžnými typy chyb na komunikačních kanálech, kde mohou poskytnout rychlou a přiměřenou záruku integrita doručených zpráv. Nejsou však vhodné k ochraně proti úmyslné změně údajů.

Za prvé, protože neexistuje žádné ověřování, může útočník upravit zprávu a přepočítat CRC bez detekce náhrady. Pokud jsou uloženy společně s daty, CRC a kryptografické hashovací funkce samy o sobě nechrání úmyslné úprava údajů. Jakákoli aplikace, která vyžaduje ochranu před takovými útoky, musí používat mechanismy kryptografického ověřování, například ověřovací kódy zpráv nebo digitální podpisy (které jsou obvykle založeny na kryptografický hash funkce).

Zadruhé, na rozdíl od kryptografických hashovacích funkcí je CRC snadno reverzibilní funkcí, což ji činí nevhodnou pro použití v digitálních podpisech.^[4]

Za třetí, CRC je lineární funkce s vlastností, která^[5]

${displaystyle operatorname {crc} (xoplus yoplus z) = operatorname {crc} (x) oplus operatorname {crc} (y) oplus operatorname {crc} (z);}$

ve výsledku, i když je CRC šifrováno pomocí a proudová šifra který používá XOR jako jeho kombinující operace (nebo režimu z bloková šifra který ji efektivně promění v proudovou šifru, jako je OFB nebo CFB), se zprávou i přidruženým CRC lze manipulovat bez znalosti šifrovacího klíče; to byla jedna ze známých konstrukčních vad Drátové ekvivalentní soukromí (WEP) protokol.^[6]

Výpočet

Vypočítat n-bitový binární CRC, zalomte bity představující vstup v řadě a umístěte (n + 1) -bitový vzor představující dělitele CRC (nazývaný „polynomiální ") pod levým koncem řádku.

V tomto příkladu zakódujeme 14 bitů zprávy pomocí 3bitového CRC s polynomem X³ + X + 1. Polynom je zapsán binárně jako koeficienty; polynom 3. stupně má 4 koeficienty (1X³ + 0X² + 1X + 1). V tomto případě jsou koeficienty 1, 0, 1 a 1. Výsledek výpočtu je dlouhý 3 bity.

Začněte zprávou, kterou chcete kódovat:

11010011101100

To je nejprve vyplněno nulami odpovídajícími délce bitu n CRC. To se provádí tak, aby výsledné kódové slovo bylo v systematický formulář. Zde je první výpočet pro výpočet 3bitového CRC:

11010011101100 000 <--- vstup vpravo vyplněný 3 bity 1011 <--- dělitel (4 bity) = x³ + x + 1 ------------------ 01100011101100 000 <- - výsledek

Algoritmus v každém kroku působí na bity přímo nad dělitelem. Výsledkem této iterace je bitový XOR polynomiálního dělitele s bity nad ním. Bity, které nejsou nad dělitelem, se pro tento krok jednoduše zkopírují přímo níže. Dělitel se poté posune doprava, aby se zarovnal s nejvyšším zbývajícím 1 bitem na vstupu, a proces se opakuje, dokud dělitel nedosáhne pravého konce vstupního řádku. Zde je celý výpočet:

11010011101100 000 <--- vstup vpravo vyplněný 3 bity 1011 <--- dělitel 01100011101100 000 <--- výsledek (všimněte si, že první čtyři bity jsou XOR s dělitelem pod, zbytek bitů se nezmění) 1011 <--- dělitel ... 00111011101100 000 101100010111101100 000 101100000001101100 000 <--- všimněte si, že dělitel se přesune, aby se vyrovnal s další 1 v dividendě (protože podíl pro tento krok byl nula) 1011 (jinými slovy, nemusí se nutně jeden bit na iteraci) 00000000110100 000 101100000000011000 000 101100000000001110 000 101100000000000101 000 101 1 ----------------- 00000000000000 100 <--- zbytek (3 bity). Algoritmus dělení se zde zastaví, protože dividenda se rovná nule.

Vzhledem k tomu, že bit vlevo oddělovače vynuloval každý vstupní bit, kterého se dotkl, když tento proces končí, jedinými bity ve vstupním řádku, které mohou být nenulové, jsou n bity na pravém konci řádku. Tyto n bity jsou zbytkem kroku dělení a budou také hodnotou funkce CRC (pokud zvolená specifikace CRC nevyžaduje nějaké následné zpracování).

Platnost přijaté zprávy lze snadno ověřit provedením výše uvedeného výpočtu znovu, tentokrát s přidanou kontrolní hodnotou namísto nul. Zbytek by se měl rovnat nule, pokud neexistují žádné zjistitelné chyby.

11010011101100 100 <--- vstup s kontrolní hodnotou 1011 <--- dělitel01100011101100 100 <--- výsledek 1011 <--- dělitel ... 00111011101100 100 ...... 00000000001110 100 101100000000000101 100 101 1 ------ ------------ 00000000000000 000 <--- zbytek

Následující Krajta code outlines a function which will return the initial CRC remainder for a selected input and polynomial, with either 1 or 0 as the initial padding. Všimněte si, že tento kód funguje spíše s řetězcovými vstupy než se surovými čísly:

def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):    "" "Vypočítejte zbytek CRC řetězce bitů pomocí vybraného polynomu.    initial_filler by měl být '1' nebo '0'.    """    polynomial_bitstring = polynomial_bitstring.pás('0')    len_input = len(input_bitstring)    initial_padding = initial_filler * (len(polynomial_bitstring) - 1)    input_padded_array = seznam(input_bitstring + initial_padding)    zatímco '1' v input_padded_array[:len_input]:        cur_shift = input_padded_array.index('1')        pro i v rozsah(len(polynomial_bitstring)):            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))    vrátit se ''.připojit se(input_padded_array)[len_input:]def crc_check(input_bitstring, polynomial_bitstring, kontrolní_hodnota):    "" "Vypočítejte CRC kontrolu řetězce bitů pomocí vybraného polynomu." ""    polynomial_bitstring = polynomial_bitstring.pás('0')    len_input = len(input_bitstring)    initial_padding = kontrolní_hodnota    input_padded_array = seznam(input_bitstring + initial_padding)    zatímco '1' v input_padded_array[:len_input]:        cur_shift = input_padded_array.index('1')        pro i v rozsah(len(polynomial_bitstring)):            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))    vrátit se ('1' ne v ''.připojit se(input_padded_array)[len_input:])

>>> crc_check('11010011101100','1011','100')Skutečný>>> crc_remainder('11010011101100','1011','0')'100'

Algoritmus CRC-32

Toto je praktický algoritmus pro CRC-32 variantu CRC.^[7] CRCTable je a memorování výpočtu, který by se musel opakovat pro každý bajt zprávy (Výpočet kontrol cyklické redundance § Vícebitový výpočet ).

Funkce CRC32 Vstup:      data: Bajty // Pole bajtů   Výstup:      crc32: UInt32 // 32bitová nepodepsaná hodnota crc-32
// Inicializujte crc-32 na počáteční hodnotucrc32 ← 0xFFFFFFFF
pro každého byte v data dělat   nLookupIndex ← (crc32 xor byte) a 0xFF; crc32 ← (crc32 shr 8) xor CRCTable [nLookupIndex] // CRCTable je pole 256 32bitových konstant
// Dokončete hodnotu CRC-32 převrácením všech bitůcrc32 ← crc32 xor 0xFFFFFFFFvrátit se crc32

Matematika

Matematická analýza tohoto dělení podobného procesu odhaluje, jak vybrat dělitele, který zaručuje dobré vlastnosti detekce chyb. V této analýze se číslice bitových řetězců berou jako koeficienty polynomu v nějaké proměnné X— Koeficienty, které jsou prvky konečného pole GF (2) místo známějších čísel. Sada binárních polynomů je matematická prsten.

Navrhování polynomů

Výběr polynomu generátoru je nejdůležitější součástí implementace algoritmu CRC. Polynom musí být zvolen tak, aby maximalizoval schopnosti detekce chyb a zároveň minimalizoval celkovou pravděpodobnost kolize.

Nejdůležitějším atributem polynomu je jeho délka (největší stupeň (exponent) +1 libovolného termínu v polynomu) kvůli jeho přímému vlivu na délku vypočítané kontrolní hodnoty.

Nejčastěji používané délky polynomů jsou:

• 9 bitů (CRC-8)
• 17 bitů (CRC-16)
• 33 bitů (CRC-32)
• 65 bitů (CRC-64)

CRC se nazývá n-bit CRC, pokud je jeho kontrolní hodnota n-bity. Za dané n, je možné více CRC, každý s jiným polynomem. Takový polynom má nejvyšší stupeň n, a tedy n + 1 termíny (polynom má délku n + 1). Zbytek má délku n. CRC má název formuláře CRC-n-XXX.

Konstrukce polynomu CRC závisí na maximální celkové délce chráněného bloku (data + bity CRC), požadovaných funkcích ochrany před chybami a typu prostředků pro implementaci CRC a také na požadovaném výkonu. Běžná mylná představa je, že „nejlepší“ polynomy CRC jsou odvozeny od obou neredukovatelné polynomy nebo neredukovatelné polynomy krát faktor1 + X, což přidává do kódu schopnost detekovat všechny chyby ovlivňující lichý počet bitů.^[8] Ve skutečnosti by všechny výše popsané faktory měly vstoupit do výběru polynomu a mohou vést k redukovatelnému polynomu. Volba redukovatelného polynomu však bude mít za následek určitý podíl zmeškaných chyb, vzhledem k tomu, že kvocientový kroužek má nulové dělitele.

Výhoda výběru a primitivní polynom jako generátor pro kód CRC je to, že výsledný kód má maximální celkovou délku bloku v tom smyslu, že všechny 1-bitové chyby v této délce bloku mají různé zbytky (také nazývané syndromy ) a proto, protože zbytek je lineární funkcí bloku, může kód detekovat všechny 2-bitové chyby v rámci této délky bloku. Li ${displaystyle r}$ je stupeň polynomu primitivního generátoru, pak je maximální celková délka bloku ${displaystyle 2 ^ {r} -1}$a přidružený kód je schopen detekovat jakékoli jednobitové nebo dvoubitové chyby.^[9] Tuto situaci můžeme zlepšit. Použijeme-li polynom generátoru ${displaystyle g (x) = p (1 + x)}$, kde ${displaystyle p}$ je primitivní polynom stupně ${displaystyle r-1}$, pak je maximální celková délka bloku ${displaystyle 2 ^ {r-1} -1}$, a kód je schopen detekovat jednoduchý, dvojitý, trojitý a libovolný lichý počet chyb.

Polynom ${displaystyle g (x)}$ který připouští další faktorizace, lze zvolit tak, aby se vyvážila maximální celková délka bloku s požadovanou silou detekce chyb. The BCH kódy jsou mocnou třídou takových polynomů. Zahrnují dva výše uvedené příklady. Bez ohledu na vlastnosti redukovatelnosti generátoru polynomu stupněr, pokud obsahuje výraz „+1“, bude kód schopen detekovat chybové vzory, které jsou omezeny na okno r sousedící bity. Tyto vzory se nazývají „chybové shluky“.

Specifikace

Koncept CRC jako kódu pro detekci chyb se zkomplikuje, když jej implementační nebo normalizační komise použije k návrhu praktického systému. Zde jsou některé z komplikací:

• Někdy implementace prefixuje pevný bitový vzor do bitového proudu, který má být zkontrolován. To je užitečné, když chyby taktování mohou před zprávu vložit 0 bitů, což je změna, která by jinak ponechala nezměněnou kontrolní hodnotu.
• Obvykle, ale ne vždy, implementace připojuje n 0 bitů (n je velikost CRC) do bitového toku, který má být zkontrolován před polynomiálním dělením. Takové připojení je výslovně předvedeno v Výpočet CRC článek. To má tu výhodu, že zbytek původního bitového toku s připojenou kontrolní hodnotou je přesně nula, takže CRC lze zkontrolovat jednoduše provedením polynomiálního dělení na přijatém bitovém toku a porovnáním zbytku s nulou. Kvůli asociativním a komutativním vlastnostem funkce exclusive-or, mohou praktické implementace řízené tabulkou získat výsledek numericky ekvivalentní nulovému připojování bez výslovného připojení jakýchkoli nul pomocí ekvivalentu,^[8] rychlejší algoritmus, který kombinuje bitový tok zpráv s tokem přesouvaným z registru CRC.
• Někdy implementace exclusive-NEBO fixní bitový vzor do zbytku polynomiálního dělení.
• Pořadí bitů: Některá schémata považují bit nízkého řádu každého bajtu za „první“, což pak během polynomiálního dělení znamená „úplně vlevo“, což je v rozporu s naším obvyklým chápáním „nízkého řádu“. Tato konvence má smysl, když sériový port přenosy jsou v hardwaru zkontrolovány CRC, protože některé rozšířené konvence přenosu na sériovém portu přenášejí bajty nejméně významného bitu jako první.
• Byte order: U vícebajtových CRC může docházet k nejasnostem ohledně toho, zda je byte přenášený jako první (nebo uložený v bitu s nejnižší adresou paměti) nejméně významný bajt (LSB) nebo nejvýznamnější bajt (MSB). Například některá 16bitová schémata CRC zaměňují bajty kontrolní hodnoty.
• Vynechání bitu vyššího řádu polynomu dělitele: Protože bit vyššího řádu je vždy 1, a protože an n-bit CRC musí být definován znakem (n + 1) -bitový dělitel, který přetečení an n-bit Registrovat, někteří autoři předpokládají, že je zbytečné se zmínit o dělicově vysokém řádu.
• Vynechání bitu nižšího řádu polynomu dělitele: Protože bit nízkého řádu je vždy 1, autoři jako Philip Koopman představují polynomy s neporušeným bitem vysokého řádu, ale bez bitu nízkého řádu ( ${displaystyle x ^ {0}}$ nebo 1 termín). Tato konvence kóduje polynom s jeho stupněm v jednom celém čísle.

Tyto komplikace znamenají, že existují tři běžné způsoby, jak vyjádřit polynom jako celé číslo: první dva, které jsou zrcadlovými obrazy v binární podobě, jsou konstanty nalezené v kódu; třetí je počet nalezený v dokumentech Koopmana. V každém případě je jeden výraz vynechán. Takže polynom ${displaystyle x ^ {4} + x + 1}$ lze přepsat jako:

• 0x3 = 0b0011, představující ${displaystyle x ^ {4} + (0x ^ {3} + 0x ^ {2} + 1x ^ {1} + 1x ^ {0})}$ (MSB-první kód)
• 0xC = 0b1100, představující ${displaystyle (1x ^ {0} + 1x ^ {1} + 0x ^ {2} + 0x ^ {3}) + x ^ {4}}$ (LSB-první kód)
• 0x9 = 0b1001, představující ${displaystyle (1x ^ {4} + 0x ^ {3} + 0x ^ {2} + 1x ^ {1}) + x ^ {0}}$ (Koopmanova notace)

V tabulce níže jsou zobrazeny jako:

Zmatek

CRC v proprietárních protokolech mohou být zmatený pomocí netriviální počáteční hodnoty a konečného XOR, ale tyto techniky nepřidávají algoritmu kryptografickou sílu a mohou být reverzní inženýrství pomocí přímých metod.^[10]

Normy a běžné použití

Byly začleněny četné varianty kontrol cyklické redundance technické normy. V žádném případě nevyhovuje jeden algoritmus nebo jeden z každého stupně každému účelu; Koopman a Chakravarty doporučují vybrat polynom podle požadavků aplikace a očekávaného rozložení délek zpráv.^[11] Počet použitých odlišných CRC zmátl vývojáře, což je situace, kterou se autoři snažili řešit.^[8] U CRC-12 jsou hlášeny tři polynomy,^[11] 22 protichůdných definic CRC-16 a sedm CRC-32.^[12]

Obvykle používané polynomy nejsou nejúčinnější možné. Od roku 1993 zkoumají Koopman, Castagnoli a další prostor polynomů o velikosti 3 až 64 bitů,^{[11][13][14][15]} hledání příkladů, které mají mnohem lepší výkon (ve smyslu Hammingova vzdálenost pro danou velikost zprávy) než polynomy dřívějších protokolů a publikování nejlepších z nich s cílem zlepšit kapacitu detekce chyb budoucích standardů.^[14] Zejména, iSCSI a SCTP přijali jedno ze zjištění tohoto výzkumu, polynom CRC-32C (Castagnoli).

Návrh 32bitového polynomu, který standardizované orgány nejčastěji používají, CRC-32-IEEE, byl výsledkem společného úsilí o Římská laboratoř a divize elektronických systémů letectva Joseph Hammond, James Brown a Shyan-Shiang Liu z Gruzínský technologický institut a Kenneth Brayer z Mitre Corporation. Nejdříve známá vystoupení 32bitového polynomu byla v jejich publikacích z roku 1975: Technická zpráva 2956 Brayera pro Mitre, publikovaná v lednu a zveřejněná pro veřejné šíření prostřednictvím DTIC v srpnu,^[16] a zpráva Hammonda, Browna a Liu pro Římskou laboratoř, zveřejněná v květnu.^[17] Obě zprávy obsahovaly příspěvky druhého týmu. V prosinci 1975 představili Brayer a Hammond svou práci v příspěvku na IEEE National Telecommunications Conference: polynom IEEE CRC-32 je generujícím polynomem Hammingův kód a byl vybrán pro výkon detekce chyb.^[18] I přesto polynom Castagnoli CRC-32C používaný v iSCSI nebo SCTP odpovídá jeho výkonu u zpráv od 58 bitů do 131 kbits a překonává jej v několika velikostních rozsazích, včetně dvou nejběžnějších velikostí internetového paketu.^[14] The ITU-T G.hn Standard také používá CRC-32C k detekci chyb v užitečném zatížení (i když používá CRC-16-CCITT pro Hlavičky PHY ).

Výpočet CRC32C je implementován v hardwaru jako operace (CRC32) z SSE4.2 instrukční sada, poprvé představena v Intel procesory Nehalem mikroarchitektura. Operace CRC32C jsou také definovány v AArch64.

Polynomiální reprezentace kontrol cyklické redundance

Níže uvedená tabulka uvádí pouze polynomy různých používaných algoritmů. Variace konkrétního protokolu mohou ukládat pre-inverzi, post-inverzi a obrácené pořadí bitů, jak je popsáno výše. Například CRC32 použitý v Gzip a Bzip2 používá stejný polynom, ale Gzip používá obrácené řazení bitů, zatímco Bzip2 nikoli.^[12]Všimněte si, že i paritní polynomy v GF (2) se stupněm větším než 1 nejsou nikdy primitivní. Dokonce i paritní polynom označený v této tabulce jako primitivní představuje primitivní polynom vynásobený ${displaystyle left (x + 1ight)}$.

název	Použití	Polynomiální reprezentace				Parita[19]	Primitivní[20]	Maximální kousky užitečného zatížení o Hammingova vzdálenost[21][14][20]
		Normální	Obráceně	Reciproční	Obrácená vzájemnost			≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2[22]
CRC-1	většina hardwaru; také známý jako paritní bit	0x1	0x1	0x1	0x1	dokonce
		${displaystyle x + 1}$
CRC-3-GSM	mobilní sítě[23]	0x3	0x6	0x5	0x5	zvláštní	Ano [24]	–	–	–	–	–	–	–	–	–	–	–	–	–	4	∞
		${displaystyle x ^ {3} + x + 1}$
CRC-4-ITU	ITU-T G.704, str. 12	0x3	0xC	0x9	0x9	zvláštní
		${displaystyle x ^ {4} + x + 1}$
CRC-5-EPC	Gen 2 RFID[25]	0x09	0x12	0x05	0x14	zvláštní
		${displaystyle x ^ {5} + x ^ {3} +1}$
CRC-5-ITU	ITU-T G.704, str. 9	0x15	0x15	0x0B	0x1A	dokonce
		${displaystyle x ^ {5} + x ^ {4} + x ^ {2} +1}$
CRC-5-USB	USB tokenové pakety	0x05	0x14	0x09	0x12	zvláštní
		${displaystyle x ^ {5} + x ^ {2} +1}$
CRC-6-CDMA2000 -A	mobilní sítě[26]	0x27	0x39	0x33	0x33	zvláštní
CRC-6-CDMA2000 -B	mobilní sítě[26]	0x07	0x38	0x31	0x23	dokonce
CRC-6-DARC	Datový rádiový kanál[27]	0x19	0x26	0x0D	0x2C	dokonce
CRC-6-GSM	mobilní sítě[23]	0x2F	0x3D	0x3B	0x37	dokonce	Ano [28]	–	–	–	–	–	–	–	–	–	–	1	1	25	25	∞
		${displaystyle x ^ {6} + x ^ {5} + x ^ {3} + x ^ {2} + x + 1}$
CRC-6-ITU	ITU-T G.704, str. 3	0x03	0x30	0x21	0x21	zvláštní
		${displaystyle x ^ {6} + x + 1}$
CRC-7	telekomunikační systémy, ITU-T G.707, ITU-T G.832, MMC, SD	0x09	0x48	0x11	0x44	zvláštní
		${displaystyle x ^ {7} + x ^ {3} +1}$
CRC-7-MVB	Vlak komunikační síť, IEC 60870-5[29]	0x65	0x53	0x27	0x72	zvláštní
CRC-8	DVB-S2[30]	0xD5	0xAB	0x57	0xEA[11]	dokonce	Ne [31]	–	–	–	–	–	–	–	–	–	–	2	2	85	85	∞
		${displaystyle x ^ {8} + x ^ {7} + x ^ {6} + x ^ {4} + x ^ {2} +1}$
CRC-8-AUTOSAR	automobilová integrace,[32] OpenSafety[33]	0x2F	0xF4	0xE9	0x97[11]	dokonce	Ano [31]	–	–	–	–	–	–	–	–	–	–	3	3	119	119	∞
		${displaystyle x ^ {8} + x ^ {5} + x ^ {3} + x ^ {2} + x + 1}$
CRC-8-Bluetooth	bezdrátové připojení[34]	0xA7	0xE5	0xCB	0xD3	dokonce
		${displaystyle x ^ {8} + x ^ {7} + x ^ {5} + x ^ {2} + x + 1}$
CRC-8-CCITT	ITU-T I.432.1 (02/99); bankomat HEC, ISDN HEC a vymezení buněk, SMBus PEC	0x07	0xE0	0xC1	0x83	dokonce
		${displaystyle x ^ {8} + x ^ {2} + x + 1}$
CRC-8-Dallas /Maxim	1-vodič autobus[35]	0x31	0x8C	0x19	0x98	dokonce
		${displaystyle x ^ {8} + x ^ {5} + x ^ {4} +1}$
CRC-8-DARC	Datový rádiový kanál[27]	0x39	0x9C	0x39	0x9C	zvláštní
		${displaystyle x ^ {8} + x ^ {5} + x ^ {4} + x ^ {3} +1}$
CRC-8-GSM -B	mobilní sítě[23]	0x49	0x92	0x25	0xA4	dokonce
		${displaystyle x ^ {8} + x ^ {6} + x ^ {3} +1}$
CRC-8-SAE J1850	AES3; OBD	0x1D	0xB8	0x71	0x8E	zvláštní
		${displaystyle x ^ {8} + x ^ {4} + x ^ {3} + x ^ {2} +1}$
CRC-8-WCDMA	mobilní sítě[26][36]	0x9B	0xD9	0xB3	0xCD[11]	dokonce
		${displaystyle x ^ {8} + x ^ {7} + x ^ {4} + x ^ {3} + x + 1}$
CRC-10	BANKOMAT; ITU-T I.610	0x233	0x331	0x263	0x319	dokonce
		${displaystyle x ^ {10} + x ^ {9} + x ^ {5} + x ^ {4} + x + 1}$
CRC-10-CDMA2000	mobilní sítě[26]	0x3D9	0x26F	0x0DF	0x3EC	dokonce
CRC-10-GSM	mobilní sítě[23]	0x175	0x2BA	0x175	0x2BA	zvláštní
CRC-11	FlexRay[37]	0x385	0x50E	0x21D	0x5C2	dokonce
		${displaystyle x ^ {11} + x ^ {9} + x ^ {8} + x ^ {7} + x ^ {2} +1}$
CRC-12	telekomunikační systémy[38][39]	0x80F	0xF01	0xE03	0xC07[11]	dokonce
		${displaystyle x ^ {12} + x ^ {11} + x ^ {3} + x ^ {2} + x + 1}$
CRC-12-CDMA2000	mobilní sítě[26]	0xF13	0xC8F	0x91F	0xF89	dokonce
CRC-12-GSM	mobilní sítě[23]	0xD31	0x8CB	0x197	0xE98	zvláštní
CRC-13-BBC	Časový signál, Rádiový teleskopický spínač[40][41]	0x1CF5	0x15E7	0x0BCF	0x1E7A	dokonce
		${displaystyle x ^ {13} + x ^ {12} + x ^ {11} + x ^ {10} + x ^ {7} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {2} +1}$
CRC-14-DARC	Datový rádiový kanál[27]	0x0805	0x2804	0x1009	0x2402	dokonce
CRC-14-GSM	mobilní sítě[23]	0x202D	0x2D01	0x1A03	0x3016	dokonce
CRC-15-UMĚT		0xC599[42][43]	0x4CD1	0x19A3	0x62CC	dokonce
		${displaystyle x ^ {15} + x ^ {14} + x ^ {10} + x ^ {8} + x ^ {7} + x ^ {4} + x ^ {3} +1}$
CRC-15-MPT1327	[44]	0x6815	0x540B	0x2817	0x740A	zvláštní
CRC-16-Chakravarty	Optimální pro užitečné zatížení ≤64 bitů[29]	0x2F15	0xA8F4	0x51E9	0x978A	zvláštní
CRC-16-ARINC	ACARS aplikace[45]	0xA02B	0xD405	0xA80B	0xD015	zvláštní
CRC-16-CCITT	X.25, V.41, HDLC FCS, XMODEM, Bluetooth, PAKTOR, SD, DigRF, mnoho dalších; známý jako CRC-CCITT	0x1021	0x8408	0x811	0x8810[11]	dokonce
		${displaystyle x ^ {16} + x ^ {12} + x ^ {5} +1}$
CRC-16-CDMA2000	mobilní sítě[26]	0xC867	0xE613	0xCC27	0xE433	zvláštní
CRC-16-DECT	bezdrátové telefony[46]	0x0589	0x91A0	0x2341	0x82C4	dokonce
		${displaystyle x ^ {16} + x ^ {10} + x ^ {8} + x ^ {7} + x ^ {3} +1}$
CRC-16-T10 -DIF	SCSI DIF	0x8BB7[47]	0xEDD1	0xDBA3	0xC5DB	zvláštní
		${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	dokonce
		${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, mnoho dalších; také známý jako CRC-16 a CRC-16-ANSI	0x8005	0xA001	0x4003	0xC002	dokonce
		${displaystyle x ^ {16} + x ^ {15} + x ^ {2} +1}$
CRC-16-OpenSafety -A	bezpečnostní sběrnice[33]	0x5935	0xAC9A	0x5935	0xAC9A[11]	zvláštní
CRC-16-OpenSafety -B	bezpečnostní sběrnice[33]	0x755B	0xDAAE	0xB55D	0xBAAD[11]	zvláštní
CRC-16-Profibus	sítě fieldbus[48]	0x1DCF	0xF3B8	0xE771	0x8EE7	zvláštní
Fletcher-16	Použito v Adler-32 Kontrolní součty A & B.	Často zaměňováno za CRC, ale ve skutečnosti kontrolní součet; vidět Fletcherův kontrolní součet
CRC-17-CAN	MŮŽE FD[49]	0x1685B	0x1B42D	0x1685B	0x1B42D	dokonce
CRC-21-CAN	MŮŽE FD[49]	0x102899	0x132281	0x064503	0x18144C	dokonce
CRC-24	FlexRay[37]	0x5D6DCB	0xD3B6BA	0xA76D75	0xAEB6E5	dokonce
		${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, RTCM 104v3	0x864CFB	0xDF3261	0xBE64C3	0xC3267D	dokonce
		${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	Použito v OS-9 RTOS. Zbytek = 0x800FE3.[50]	0x800063	0xC60001	0x8C0003	0xC00031	dokonce	Ano[51]	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	∞
		${displaystyle x ^ {24} + x ^ {23} + x ^ {6} + x ^ {5} + x + 1}$
CRC-30	CDMA	0x2030B9C7	0x38E74301	0x31CE8603	0x30185CE3	dokonce
		${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,[52] PNG,[53] ZMODEM, mnoho dalších	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB[14]	zvláštní	Ano	–	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 užitečné zatížení, SSE4.2, Btrfs, ext4, Ceph	0x1EDC6F41	0x82F63B78	0x05EC76F1	0x8F6E37A0[14]	dokonce	Ano	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})	Vynikající na délku rámce Ethernet, špatný výkon s dlouhými soubory	0x741B8CD7	0xEB31D82E	0xD663B05D	0xBA0DC66B[14]	dokonce	Ne	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})	Vynikající na délku rámce Ethernet, špatný výkon s dlouhými soubory	0x32583499	0x992C1A4C	0x32583499	0x992C1A4C[14]	dokonce	Ne	–	–	3	–	16	–	26	–	134	–	32738	–	65506	–	∞
CRC-32Q	letectví; AIXM[54]	0x814141AB	0xD5828281	0xAB050503	0xC0A0A0D5	dokonce
		${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		Často zaměňováno za CRC, ale ve skutečnosti kontrolní součet; vidět Adler-32
CRC-40-GSM	Ovládací kanál GSM[55][56][57]	0x0004820009	0x9000412000	0x2000824001	0x8002410004	dokonce
		${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	dokonce
		${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 ), Swiss-Prot /TrEMBL; považován za slabý pro hašování[58]	0x000000000000001B	0xD800000000000000	0xB000000000000001	0x800000000000000D	zvláštní
		${displaystyle x ^ {64} + x ^ {4} + x ^ {3} + x + 1}$

Implementace

• Implementace CRC32 v Gnuradio;
• Kód třídy C pro výpočet kontrolního součtu CRC s mnoha různými CRC na výběr

Katalogy CRC

• Katalog parametrizovaných CRC algoritmů
• CRC Polynomial Zoo

Viz také

• Matematika kontrol cyklické redundance
• Výpočet kontrol cyklické redundance
• Seznam hashovacích funkcí
• Seznam algoritmů kontrolního součtu
• Informační bezpečnost
• Jednoduché ověření souboru
• LRC

Reference

Další čtení

• Warren Jr., Henry S. (2013). Hacker's Delight (2. vyd.). Addison Wesley – Pearson Education, Inc. ISBN  978-0-321-84268-8.

externí odkazy

• ISO/IEC 13239:2002: Information technology -- Telecommunications and information exchange between systems -- High-level data link control (HDLC) procedures
• CRC32-Castagnoli Linux Library