Kód cyklické redundance

Kontrola cyklické redundance _ , CRC ^[1] ) je algoritmus pro nalezení kontrolního součtu určený ke kontrole integrity dat^[2] . CRC je praktická aplikace kódování pro opravu chyb založené na určitých matematických vlastnostech cyklického kódu .

Úvod

Pojem cyklických kódů je poměrně široký ^[3] . V anglické literatuře je CRC chápáno dvěma způsoby v závislosti na kontextu: Cyclic Redundancy Code nebo Cyclic Redundancy Check ^[4] . První pojem znamená matematický jev cyklických kódů, druhý - konkrétní aplikaci tohoto jevu jako hašovací funkce .

Cyklické kódy se nejen snadno implementují, ale mají také výhodu v tom, že jsou vhodné pro detekci shlukových chyb: souvislé sekvence chybných datových znaků ve zprávách. To je důležité, protože shlukové chyby jsou běžné chyby přenosu v mnoha komunikačních kanálech, včetně magnetických a optických paměťových zařízení. Typicky n-bitový CRC, aplikovaný na blok dat libovolné délky, a s kontrolním součtem bezprostředně následujícím za daty, detekuje každý jednotlivý shluk chyb, který není delší než n bitů, a podíl všech delších shluků chyb, který detekuje je (1 − 2 ⁻ⁿ ).

Kódování pro korekci šumu

První pokusy o vytvoření kódů s nadbytečnými informacemi začaly dávno před příchodem moderních počítačů. Například v 60. letech 20. století Reed a Solomon vyvinuli účinnou techniku kódování - Reed-Solomonův kód . Použití v té době nebylo možné, protože první algoritmy nedokázaly provést dekódovací operaci v rozumném čase . Berlekampova základní práce , publikovaná v roce 1968 , tento problém ukončila . Tato technika , na jejíž praktické použití Massey poukázal o rok později , se dodnes používá v digitálních zařízeních, která přijímají data kódovaná RS . Navíc: tento systém umožňuje nejen určovat pozice, ale i opravovat nesprávné kódové symboly (nejčastěji oktety ).

Ale zdaleka ne vždy je z kódu vyžadována oprava chyb . Mnoho moderních komunikačních kanálů má přijatelné vlastnosti a často stačí zkontrolovat, zda byl přenos úspěšný nebo zda se vyskytly nějaké potíže; struktura chyb a konkrétní pozice nesprávných symbolů přijímající stranu vůbec nezajímají. A za těchto podmínek se algoritmy využívající kontrolní součty ukázaly jako velmi úspěšné řešení. CRC je pro takové úkoly nejvhodnější: nízké náklady na zdroje, snadná implementace a již vytvořený matematický aparát z teorie lineárních cyklických kódů mu zajistily obrovskou popularitu.

I když se CRC kód obvykle používá pouze pro detekci chyb, jeho matematické vlastnosti umožňují najít a opravit jednu chybu v bloku bitů, pokud každý bit chráněného bloku (včetně kontrolních bitů) má při rozdělení svůj vlastní jedinečný zbytek. pomocí generátorového polynomu. Například pokud je generující polynom neredukovatelný a délka bloku nepřesahuje řád generované cyklické skupiny.

Kontrolní součet

Obecně je kontrolní součet hodnota vypočítaná podle určitého schématu na základě zakódované zprávy. K přenášeným datům je přiřazena kontrolní informace v systematickém kódování . Na přijímací straně zná předplatitel algoritmus pro výpočet kontrolního součtu: podle toho má program schopnost kontrolovat správnost přijatých dat.

Když jsou pakety přenášeny přes síťový kanál, informace o zdroji mohou být zkresleny v důsledku různých vnějších vlivů: elektrické rušení, špatné povětrnostní podmínky a mnoho dalších. Podstata techniky spočívá v tom, že při dobrých charakteristikách kontrolního součtu v naprosté většině případů povede chyba ve zprávě ke změně jeho kontrolního součtu. Pokud se původní a vypočítané součty neshodují, rozhodne se o neplatnosti přijatých dat a lze požádat o opětovné odeslání paketu.

Matematický popis

Algoritmus CRC je založen na vlastnostech dělení se zbytkem binárních polynomů, tedy polynomů nad konečným tělesem . Hodnota CRC je v podstatě zbytek dělení polynomu odpovídajícímu vstupu nějakým fixním generátorovým polynomem . $GF(2)$

Každá konečná posloupnost bitů je spojena jedna ku jedné s binárním polynomem , jehož posloupnost koeficientů je původní posloupností. Například bitová sekvence 1011010 odpovídá polynomu: $a_0, a_1, \tečky, 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.

Počet odlišných polynomů stupně menšího než je roven , což je stejné jako počet všech binárních sekvencí délky . $N$ $2^N$ $N$

Hodnota kontrolního součtu v algoritmu s generujícím stupněm polynomu je definována jako bitová posloupnost délky , která představuje polynom, jehož výsledkem je zbytek dělení polynomu představujícího vstupní bitový tok polynomem : $G(x)$ $N$ $N$ $R(x)$ $P(x)$ $G(x)$

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

kde

R(x)

je polynom představující hodnotu CRC;

P(x)

je polynom, jehož koeficienty představují vstupní data;

G(x)

je generující polynom;

N

je stupeň generujícího polynomu.

Násobení se provádí přiřazením nulových bitů vstupní sekvenci, což zlepšuje kvalitu hashování pro krátké vstupní sekvence. $x^N$ $N$

Při dělení se zbytkem různých původních polynomů generujícím polynomem stupně , lze z dělení získat různé zbytky. je často neredukovatelný polynom . Obvykle se vybírá v souladu s požadavky na hašovací funkci v kontextu každé konkrétní aplikace. $G(x)$ $N$ $2^{N}$ $G(x)$

Existuje však mnoho standardizovaných generátorů polynomů, které mají dobré matematické a korelační vlastnosti (minimální počet kolizí , snadnost výpočtu), z nichž některé jsou uvedeny níže.

Výpočet CRC

Parametry algoritmu

Jedním z hlavních parametrů CRC je generující polynom.

Dalším parametrem spojeným s polynomem generátoru je jeho stupeň , který určuje počet bitů použitých k výpočtu hodnoty CRC. V praxi se nejčastěji vyskytují 8-, 16- a 32bitová slova, což je důsledek zvláštností architektury moderní výpočetní techniky.

Dalším parametrem je počáteční (počáteční) hodnota slova. Tyto parametry zcela definují "tradiční" výpočetní algoritmus CRC. Existují také úpravy algoritmu, například pomocí obráceného pořadí bitů zpracování.

Popis postupu

První slovo je převzato ze souboru – může to být bit (CRC-1), byte (CRC-8) nebo jakýkoli jiný prvek. Pokud je nejvýznamnější bit ve slově "1", pak se slovo posune o jeden bit doleva a následuje operace XOR s generujícím polynomem. Pokud je tedy nejvýznamnější bit ve slově "0", operace XOR se po posunu neprovede . Po posunu se ztratí nejvýznamnější bit a místo nejméně významného bitu se načte další bit ze souboru a operace se opakuje, dokud se nenačte poslední bit souboru. Po projití celého souboru zůstane ve wordu zbytek, což je kontrolní součet.

Populární a standardizované polynomy

Zatímco kódy cyklické redundance jsou součástí standardů, tento pojem nemá obecně přijímanou definici – výklady různých autorů si často protiřečí ^[1]^[5] .

Tento paradox platí také pro volbu generátorového polynomu: často standardizované polynomy nejsou nejúčinnější z hlediska statistických vlastností jejich odpovídajícího kontrolního redundantního kódu .

Mnoho široce používaných polynomů však není nejúčinnějších ze všech možných. V letech 1993-2004 se skupina vědců zabývala studiem generování polynomů s kapacitou až 16 ^[1] 24 a 32 bitů ^[6]^[7] a našla polynomy, které poskytují lepší výkon než standardizované polynomy, pokud jde o vzdálenost kódu . ^[7] . Jeden z výsledků této studie si již našel cestu do protokolu iSCSI .

Nejpopulárnější a doporučený polynom IEEE pro CRC-32 se používá v Ethernetu , FDDI ; také tento polynom je generátor Hammingova kódu ^[8] . Použití jiného polynomu - CRC-32C - umožňuje dosáhnout stejného výkonu s délkou původní zprávy od 58 bitů do 131 kbps a v některých rozsazích délky vstupní zprávy může být i vyšší, takže je také dnes populární ^[7] . Například standard ITU-T G.hn používá CRC-32C k detekci chyb v užitečné zátěži.

V tabulce níže jsou uvedeny nejběžnější polynomy – generátory CRC. V praxi může výpočet CRC zahrnovat před a po inverzi, stejně jako obrácené pořadí zpracování bitů. Proprietární implementace CRC používají nenulové počáteční hodnoty registru, aby bylo obtížnější analyzovat kód.

název	Polynom	Reprezentace: ^[9] normální / obrácené / obrácené z opačného směru
CRC-1	$x+1$ (používá se při kontrole chyb hardwaru; také známý jako paritní bit )	0x1 / 0x1 / 0x1
CRC-4-ITU	$x^{4}+x+1$ ( ITU G.704 ^[10] )	0x3 / 0xC / 0x9
CRC-5-EPC	$x^5 + x^3 + 1$ ( RFID Gen 2 ^[11] )	0x09 / 0x12 / 0x14
CRC-5-ITU	$x^5 + x^4 + x^2 + 1$ ( ITU G.704 ^[12] )	0x15 / 0x15 / 0x1A
CRC-5-USB	$x^5 + x^2 + 1$ ( Pakety USB tokenů)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ ( ITU G.704 ^[13] )	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (telekomunikační systémy, 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-wire 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$ (telekomunikační systémy ^[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] , mnoho dalších; také známé jako CRC-16 a CRC-16-ANSI )	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$ ( X.25 , HDLC , XMODEM , Bluetooth , SD atd.)	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	Ne CRC; viz Fletcherův kontrolní součet	Používá se v 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	Ne CRC; viz Adler-32	Viz 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 , užitečné zatížení G.hn )	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0 ^[7]
CRC-32K (Koopman)	$x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^ {16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1$	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B ^[7]
CRC-32Q	$x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^ {5} + x^{3} + x + 1$ (letectví; AIXM ^[23] )	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	$x^{64} + x^4 + x^3 + x + 1$ ( HDLC - ISO 3309 )	0x000000000000001B / 0xD80000000000000 / 0x800000000000000D
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

Stávající standardy CRC-128 (IEEE) a CRC-256 (IEEE).^{[ kdy? ]} byly nahrazeny kryptografickými hašovacími funkcemi .

Specifikace algoritmu CRC

Jednou z nejznámějších je technika Rosse N. Williamse ^[25] . Používá následující možnosti:

Název algoritmu ( name );

Stupeň polynomu generujícího kontrolní součet ( width );

Samotný generující polynom ( poly ). Aby bylo možné jej zapsat jako hodnotu, je nejprve zapsán jako bitová posloupnost, přičemž nejvýznamnější bit je vynechán - vždy je 1. Například polynom v tomto zápisu bude zapsán jako číslo . Pro usnadnění je výsledná binární reprezentace zapsána v hexadecimálním tvaru. V našem případě se bude rovnat nebo 0x11; $x^8+x^4+1$ $00010001_2$ $11_h$

Počáteční data ( init ), tedy hodnoty registrů v době zahájení výpočtů;

Příznak ( RefIn ), označující začátek a směr výpočtu, se musí shodovat s pořadím přenosu v kanálu, aby bylo možné detekovat shluky chyb. Existují dvě možnosti: False - začíná nejvýznamnějším bitem ( MSB -first) nebo True - začíná nejnižším významným bitem ( LSB -first);

Flag ( RefOut ), který určuje, zda je pořadí bitů registru při vstupu do prvku XOR invertováno ;

Číslo ( XorOut ), ke kterému je výsledek přidán modulo 2 ;

Hodnota CRC ( kontrola ) pro řetězec "123456789" .

Příklady ^[26]

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

Poznámky

↑ ¹ ² ³ ⁴ ⁵ Philip Koopman, Tridib Chakravarty. Cyklický redundantní kód (CRC) Polynomial Selection for Embedded Networks (2004). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)
↑ Internetová univerzita informačních technologií. Přednáška: Organizace bezdrátových sítí
↑ Internetová univerzita informačních technologií. Přednáška: Síťové algoritmy Ethernet/Fast Ethernet
↑ Walma, M.; Výpočet zřetězené cyklické redundance (CRC).
↑ Greg Cook. Katalog parametrizovaných CRC algoritmů (29. dubna 2009). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)
↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimalizace kódů pro kontrolu cyklické redundance s 24 a 32 bity parity // Transakce IEEE při komunikaci. - Červen 1993. - T. 41 , č. 6 . - S. 883 . - doi : 10.1109/26.231911 .
↑ ¹ ² ³ ⁴ ⁵ ⁶ P. Koopman. 32bitové cyklické redundantní kódy pro internetové aplikace // Mezinárodní konference o spolehlivých systémech a sítích. - červen 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .
↑ Brayer, K; Hammond, JL Jr. (prosinec 1975). „Vyhodnocení polynomiálního výkonu detekce chyb na kanálu AUTOVON“. záznam konference . Národní telekomunikační konference, New Orleans, La. 1 . New York: Institut elektrických a elektronických inženýrů. str. 8-21 až 8-25. Použitý zastaralý parametr |month=( nápověda )
↑ Nejdůležitější bit v reprezentacích vynechán.
↑ G.704 , str. 12
↑ Protokol UHF RFID Class-1 Generation-2 verze 1.2.0 . - 23. října 2008. - S. 35 . Archivováno z originálu 20. listopadu 2008.
↑ G.704 , str. 9
↑ G.704 , str. 3
↑ G.707: Rozhraní síťového uzlu pro synchronní digitální hierarchii (SDH)
↑ G.832: Transport prvků SDH v sítích PDH — Rámcové a multiplexní struktury
↑ EN 302 307 Digital Video Broadcasting (DVB); Rámcová struktura druhé generace, kódování kanálů a modulační systémy pro vysílání, interaktivní služby, shromažďování zpráv a další širokopásmové satelitní aplikace (DVB-S2)
↑ ¹ ² Specifikace protokolu FlexRay verze 2.1 Revize A. - 22. prosince 2005. - S. 93 .
↑ A. Perez, Wismer, Becker. Byte-Wise CRC výpočty // IEEE Micro. - 1983. - V. 3 , č. 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .
↑ TV Ramabadran, SS Gaitonde. Výukový program o výpočtech CRC // IEEE Micro. - 1988. - V. 8 , č. 4 . - S. 62-75 . - doi : 10.1109/40.7773 .
↑ Archivovaná kopie (odkaz není dostupný) . Získáno 16. října 2009. Archivováno z originálu 1. října 2009. (neurčitý)
↑ Pat Thaler. Výběr 16bitového polynomu CRC . INCITS T10 (28. srpna 2003). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)
↑ Thomas Boutell, Glenn Randers-Pehrson a kol. Specifikace PNG (Portable Network Graphics), verze 1.2 (14. července 1998). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)
↑ AIXM Primer verze 4.5 . Evropská organizace pro bezpečnost letového provozu (20. března 2006). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)
↑ ECMA-182 str. 51
↑ Ross N. Williams. CRC Rocksoft (nedostupný odkaz) (1993). Získáno 17. dubna 2012. Archivováno z originálu 3. září 2011. (neurčitý)
↑ Greg Cook. Katalog parametrizovaných CRC algoritmů (18. ledna 2016). (neurčitý)

Literatura

Henry S. Warren, Jr. Kapitola 5 Počítání bitů // Algoritmické triky pro programátory = Hacker's Delight. — M .: Williams , 2007. — 288 s. — ISBN 0-201-91465-4 .

Odkazy

Základní průvodce algoritmy detekce chyb CRC
CRC a jak jej obnovit
Generátor funkcí CRC ve VHDL a Verilog
Ross N. Williams/Anarchriz. Vše o CRC32 // Ross N. Williams. Základní průvodce algoritmy detekce chyb CRC
Ross N. Williams. BEZBOLESTNÝ PRŮVODCE ALGORITHMY CRC DETEKCE CHYB

CRC kalkulačky

[koop04-1] ¹ ² ³ ⁴ ⁵ Philip Koopman, Tridib Chakravarty. Cyklický redundantní kód (CRC) Polynomial Selection for Embedded Networks (2004). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)

[2] Internetová univerzita informačních technologií. Přednáška: Organizace bezdrátových sítí

[3] Internetová univerzita informačních technologií. Přednáška: Síťové algoritmy Ethernet/Fast Ethernet

[4] Walma, M.; Výpočet zřetězené cyklické redundance (CRC).

[5] Greg Cook. Katalog parametrizovaných CRC algoritmů (29. dubna 2009). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)

[6] G. Castagnoli, S. Braeuer, M. Herrman. Optimalizace kódů pro kontrolu cyklické redundance s 24 a 32 bity parity // Transakce IEEE při komunikaci. - Červen 1993. - T. 41 , č. 6 . - S. 883 . - doi : 10.1109/26.231911 .

[koop02-7] ¹ ² ³ ⁴ ⁵ ⁶ P. Koopman. 32bitové cyklické redundantní kódy pro internetové aplikace // Mezinárodní konference o spolehlivých systémech a sítích. - červen 2002. - S. 459 . - doi : 10.1109/DSN.2002.1028931 .

[8] Brayer, K; Hammond, JL Jr. (prosinec 1975). „Vyhodnocení polynomiálního výkonu detekce chyb na kanálu AUTOVON“. záznam konference . Národní telekomunikační konference, New Orleans, La. 1 . New York: Institut elektrických a elektronických inženýrů. str. 8-21 až 8-25. Použitý zastaralý parametr |month=( nápověda )

[9] Nejdůležitější bit v reprezentacích vynechán.

[10] G.704 , str. 12

[11] Protokol UHF RFID Class-1 Generation-2 verze 1.2.0 . - 23. října 2008. - S. 35 . Archivováno z originálu 20. listopadu 2008.

[12] G.704 , str. 9

[13] G.704 , str. 3

[14] G.707: Rozhraní síťového uzlu pro synchronní digitální hierarchii (SDH)

[15] G.832: Transport prvků SDH v sítích PDH — Rámcové a multiplexní struktury

[16] EN 302 307 Digital Video Broadcasting (DVB); Rámcová struktura druhé generace, kódování kanálů a modulační systémy pro vysílání, interaktivní služby, shromažďování zpráv a další širokopásmové satelitní aplikace (DVB-S2)

[flexray-spec-17] ¹ ² Specifikace protokolu FlexRay verze 2.1 Revize A. - 22. prosince 2005. - S. 93 .

[18] A. Perez, Wismer, Becker. Byte-Wise CRC výpočty // IEEE Micro. - 1983. - V. 3 , č. 3 . - S. 40-50 . - doi : 10.1109/MM.1983.291120 .

[19] TV Ramabadran, SS Gaitonde. Výukový program o výpočtech CRC // IEEE Micro. - 1988. - V. 8 , č. 4 . - S. 62-75 . - doi : 10.1109/40.7773 .

[20] Archivovaná kopie (odkaz není dostupný) . Získáno 16. října 2009. Archivováno z originálu 1. října 2009. (neurčitý)

[21] Pat Thaler. Výběr 16bitového polynomu CRC . INCITS T10 (28. srpna 2003). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)

[22] Thomas Boutell, Glenn Randers-Pehrson a kol. Specifikace PNG (Portable Network Graphics), verze 1.2 (14. července 1998). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)

[23] AIXM Primer verze 4.5 . Evropská organizace pro bezpečnost letového provozu (20. března 2006). Datum přihlášky: ???. Archivováno z originálu 22. srpna 2011. (neurčitý)

[24] ECMA-182 str. 51

[25] Ross N. Williams. CRC Rocksoft (nedostupný odkaz) (1993). Získáno 17. dubna 2012. Archivováno z originálu 3. září 2011. (neurčitý)

[26] Greg Cook. Katalog parametrizovaných CRC algoritmů (18. ledna 2016). (neurčitý)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA