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 .
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 −n ).
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.
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.
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 .
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:
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 .
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 :
kde
je polynom představující hodnotu CRC; je polynom, jehož koeficienty představují vstupní data; je generující polynom; 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.
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.
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.
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í.
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.
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 | (používá se při kontrole chyb hardwaru; také známý jako paritní bit ) | 0x1 / 0x1 / 0x1 |
CRC-4-ITU | ( ITU G.704 [10] ) | 0x3 / 0xC / 0x9 |
CRC-5-EPC | ( RFID Gen 2 [11] ) | 0x09 / 0x12 / 0x14 |
CRC-5-ITU | ( ITU G.704 [12] ) | 0x15 / 0x15 / 0x1A |
CRC-5-USB | ( Pakety USB tokenů) | 0x05 / 0x14 / 0x12 |
CRC-6-ITU | ( ITU G.704 [13] ) | 0x03 / 0x30 / 0x21 |
CRC-7 | (telekomunikační systémy, ITU-T G.707 [14] , ITU-T G.832 [15] , MMC , SD ) | 0x09 / 0x48 / 0x44 |
CRC-8- CCITT | ( ATM HEC ), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99) | 0x07 / 0xE0 / 0x83 |
CRC-8- Dallas / Maxim | ( 1-wire bus ) | 0x31 / 0x8C / 0x98 |
CRC-8 | ( ETSI EN 302 307 [16] , 5.1.4) | 0xD5 / 0xAB / 0xEA [1] |
CRC-8-SAE J1850 | 0x1D / 0xB8 / 0x8E | |
CRC-10 | 0x233 / 0x331 / 0x319 | |
CRC-11 | ( FlexRay [17] ) | 0x385 / 0x50E / 0x5C2 |
CRC-12 | (telekomunikační systémy [18] [19] ) | 0x80F / 0xF01 / 0xC07 |
CRC-15- CAN | 0x4599 / 0x4CD1 / 0x62CC | |
CRC-16- IBM | ( 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.25 , HDLC , XMODEM , Bluetooth , SD atd.) | 0x1021 / 0x8408 / 0x8810 [1] |
CRC-16- T10 - DIF | ( SCSI DIF) | 0x8BB7 [21] / 0xEDD1 / 0xC5DB |
CRC-16- DNP | (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 | ( FlexRay [17] ) | 0x5D6DCB / 0xD3B6BA / 0xAEB6E5 |
CRC-24 Radix-64 | ( OpenPGP ) | 0x864CFB / 0xDF3261 / 0xC3267D |
CRC-30 | ( CDMA ) | 0x2030B9C7 / 0x38E74301 / 0x30185CE3 |
CRC-32-Adler | Ne CRC; viz Adler-32 | Viz Adler-32 |
CRC-32 - IEEE 802.3 | ( V.42 , MPEG-2 , PNG [22] , POSIX cksum ) | 0x04C11DB7 / 0xEDB88320 / 0x82608EDB [7] |
CRC-32C (Castagnoli) | ( iSCSI , užitečné zatížení G.hn ) | 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0 [7] |
CRC-32K (Koopman) | 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B [7] | |
CRC-32Q | (letectví; AIXM [23] ) | 0x814141AB / 0xD5828281 / 0xC0A0A0D5 |
CRC-64-ISO | ( HDLC - ISO 3309 ) | 0x000000000000001B / 0xD80000000000000 / 0x800000000000000D |
CRC-64- ECMA | [24] | 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49 |
Stávající standardy CRC-128 (IEEE) a CRC-256 (IEEE).[ kdy? ] byly nahrazeny kryptografickými hašovacími funkcemi .
Jednou z nejznámějších je technika Rosse N. Williamse [25] . Používá následující možnosti:
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 |
Hashovací funkce | |
---|---|
obecný účel | |
Kryptografický | |
Funkce generování klíčů | |
Kontrolní číslo ( srovnání ) | |
Hashe |
|