Výpočet kontrol cyklické redundance - Computation of cyclic redundancy checks

Výpočet a kontrola cyklické redundance je odvozen z matematiky polynomiální dělení, modulo dva. V praxi se to podobá dlouhé rozdělení z binární řetězec zprávy s připojeným pevným počtem nul řetězcem „generátoru polynomu“ kromě toho exkluzivní nebo operace nahrazují odčítání. Dělení tohoto typu je efektivně realizováno v hardwaru modifikovaným posuvný registr,^[1] a v softwaru řadou ekvivalentů algoritmy, počínaje jednoduchým kódem blízkým matematice a rychlejším (a pravděpodobně i více) zmatený^[2]) přes byte -moudrý rovnoběžnost a časoprostorové kompromisy.

Příklad generování 8 bitů CRC. Generátor je typu Galois posuvný registr s Brány XOR umístěny podle mocnin (bílá čísla) z X v polynomu generátoru. Stream zpráv může mít libovolnou délku. Poté, co byl posunut přes registr, následovaný 8 nulami, výsledkem v registru je kontrolní součet.

Kontrola přijatých dat pomocí kontrolního součtu. Přijatá zpráva je posunuta o stejný registr, jaký je použit v generátoru, ale přijatý kontrolní součet je k ní připojen místo nul. Správná data přinášejí výsledek nuly; poškozený bit ve zprávě nebo kontrolním součtu by poskytl jiný výsledek, varoval, že došlo k chybě.

Různé standardy CRC rozšiřují algoritmus dělení polynomů zadáním počáteční hodnoty posuvného registru, závěrečného výlučného kroku OR a nejkritičtějšího uspořádání bitů (endianismus ). Výsledkem je, že kód viděný v praxi se matoucí odchyluje od „čistého“ dělení,^[2] a registr se může posunout doleva nebo doprava.

Příklad

Jako příklad implementace polynomiálního dělení v hardwaru předpokládejme, že se pokoušíme vypočítat 8bitový CRC 8bitové zprávy vytvořené z ASCII znak "W", což je binární 01010111₂, desetinné číslo 87₁₀nebo hexadecimální 57₁₆. Pro ilustraci použijeme CRC-8-ATM (HEC ) polynom ${displaystyle x ^ {8} + x ^ {2} + x + 1}$ . Zápis prvního přeneseného bitu (koeficient nejvyššího výkonu ${displaystyle x}$ ) vlevo, toto odpovídá 9bitovému řetězci „100000111“.

Hodnota bajtu 57₁₆ mohou být přenášeny ve dvou různých řádech, v závislosti na použité konvenci řazení bitů. Každý generuje jiný polynom zprávy ${displaystyle M (x)}$ . Msbit-první, to je ${displaystyle x ^ {6} + x ^ {4} + x ^ {2} + x + 1}$ = 01010111, zatímco lsbit-first, to je ${displaystyle x ^ {7} + x ^ {6} + x ^ {5} + x ^ {3} + x}$ = 11101010. Ty pak mohou být vynásobeny ${displaystyle x ^ {8}}$ k vytvoření dvou 16bitových polynomů zpráv ${displaystyle x ^ {8} M (x)}$ .

Výpočet zbytku pak sestává z odečtení násobků polynomu generátoru ${displaystyle G (x)}$ . Je to jako desetinné dlouhé dělení, ale ještě jednodušší, protože jediné možné násobky v každém kroku jsou 0 a 1 a odčítání půjčit si „od nekonečna“ místo snižování horních číslic. Protože nám na kvocientu nezáleží, není třeba jej zaznamenávat.

Nejvýznamnější bit jako první

Nejméně významný bit jako první

	0	1	0	1	0	1	1	1	0	0	0	0	0	0	0	0
−	0	0	0	0	0	0	0	0	0
=	0	1	0	1	0	1	1	1	0	0	0	0	0	0	0	0
	−	1	0	0	0	0	0	1	1	1
=	0	0	0	1	0	1	1	0	1	1	0	0	0	0	0	0
		−	0	0	0	0	0	0	0	0	0
=	0	0	0	1	0	1	1	0	1	1	0	0	0	0	0	0
			−	1	0	0	0	0	0	1	1	1
=	0	0	0	0	0	1	1	0	1	0	1	1	0	0	0	0
				−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	0	1	1	0	1	0	1	1	0	0	0	0
					−	1	0	0	0	0	0	1	1	1
=	0	0	0	0	0	0	1	0	1	0	1	0	1	1	0	0
						−	1	0	0	0	0	0	1	1	1
=	0	0	0	0	0	0	0	0	1	0	1	0	0	0	1	0
							−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	0	0	0	0	1	0	1	0	0	0	1	0

	1	1	1	0	1	0	1	0	0	0	0	0	0	0	0	0
−	1	0	0	0	0	0	1	1	1
=	0	1	1	0	1	0	0	1	1	0	0	0	0	0	0	0
	−	1	0	0	0	0	0	1	1	1
=	0	0	1	0	1	0	0	0	0	1	0	0	0	0	0	0
		−	1	0	0	0	0	0	1	1	1
=	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
			−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
				−	1	0	0	0	0	0	1	1	1
=	0	0	0	0	0	0	0	0	1	0	0	1	1	0	0	0
					−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	0	0	0	0	1	0	0	1	1	0	0	0
						−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	0	0	0	0	1	0	0	1	1	0	0	0
							−	0	0	0	0	0	0	0	0	0
=	0	0	0	0	0	0	0	0	1	0	0	1	1	0	0	0

Všimněte si, že po každém odečtení jsou bity rozděleny do tří skupin: na začátku skupina, která je celá nula; na konci skupina, která se nezměnila od originálu; a uprostřed modrá skupina, která je „zajímavá“. „Zajímavá“ skupina je 8 bitů dlouhá a odpovídá stupni polynomu. V každém kroku se odečte příslušný násobek polynomu, aby byla nulová skupina o jeden bit delší, a nezměněná skupina se zmenší o jeden bit, dokud nezbude jen poslední zbytek.

V příkladu msbit-first je zbytek polynomu ${displaystyle x ^ {7} + x ^ {5} + x}$ . Převod na šestnáctkové číslo pomocí konvence, která má nejvyšší sílu X je msbit; toto je A2₁₆. V lsbit-first je zbytek ${displaystyle x ^ {7} + x ^ {4} + x ^ {3}}$ . Převod na hexadecimální pomocí konvence, že nejvyšší síla X je lsbit, to je 19₁₆.

Implementace

Napsání celé zprávy v každém kroku, jak je uvedeno v příkladu výše, je velmi zdlouhavé. Efektivní implementace ${displaystyle n}$ -bit posuvný registr držet jen ty zajímavé kousky. Vynásobení polynomu ${displaystyle x}$ je ekvivalentní posunutí registru o jedno místo, protože koeficienty se nemění v hodnotě, ale pouze se pohybují nahoru k dalšímu členu polynomu.

Zde je první koncept některých pseudo kód pro výpočet n-bit CRC. Používá nepřirozený složený datový typ pro polynomy, kde X není celočíselná proměnná, ale a konstruktor generování a Polynomiální objekt které lze sčítat, vynásobit a umocnit. Na xor dva polynomy je přidat je, modulo dva; to znamená, že exkluzivní NEBO koeficienty každého shodného termínu z obou polynomů.

funkce crc (bitové pole bitString [1..len], int len) {remainderPolynomial: = polynomialForm(bitString [1..n]) // Prvních n bitů zprávy    // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Přednastaveno na -1 níže    pro i z 1 na len {remainderPolynomial: = remainderPolynomial * X + bitString [i + n] * X⁰   // Definujte bitString [k] = 0 pro k> len        -li koeficient Xⁿ of remainderPolynomial = 1 {remainderPolynomial: = remainderPolynomial xor generatorPolynomial}} // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Post-inverze níže    vrátit se zbytekPolynomial}

Fragment kódu 1: Jednoduché dělení polynomů

Všimněte si, že tento ukázkový kód se vyhne potřebě určit konvenci řazení bitů nepoužíváním bajtů; vstup bitString je již ve formě bitového pole a zbytek Polynomiální je manipulováno z hlediska polynomiálních operací; násobení ${displaystyle x}$ může to být levý nebo pravý posun a přidání bitString [i + n] se provádí na ${displaystyle x ^ {0}}$ koeficient, kterým může být pravý nebo levý konec registru.

Tento kód má dvě nevýhody. Nejprve to vlastně vyžaduje n+ 1-bitový registr pro uložení zbytekPolynomiální takže ${displaystyle x ^ {n}}$ lze testovat koeficient. Ještě důležitější je, že vyžaduje bitString být polstrován n nula bitů.

První problém lze vyřešit testováním ${displaystyle x ^ {n-1}}$ koeficient zbytek Polynomiální než se vynásobí ${displaystyle x}$ .

Druhý problém lze vyřešit provedením posledního n iterace odlišně, ale existuje důvtipnější optimalizace, která se používá univerzálně v hardwarových i softwarových implementacích.

Protože operace XOR použitá k odečtení polynomu generátoru od zprávy je komutativní a asociativní, nezáleží na tom, v jakém pořadí jsou různé vstupy kombinovány do zbytek Polynomiální. A konkrétně daný kousek bitString není třeba přidávat do zbytek Polynomiální až do posledního okamžiku, kdy je testováno, aby se zjistilo, zda xor s generatorPolynomial.

To eliminuje potřebu předinstalovat zbytekPolynomiální s první n kousky zprávy také:

funkce crc (bitové pole bitString [1..len], int len) {remainderPolynomial: = 0 // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Přednastaveno na -1 níže    pro i z 1 na len {remainderPolynomial: = remainderPolynomial xor (bitstring [i] * X^{n − 1})        -li (koeficient X^{n − 1} of remainderPolynomial) = 1 {remainderPolynomial: = (remainderPolynomial * X) xor generatorPolynomial} jiný {remainderPolynomial: = (remainderPolynomial * X)        }    }    // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Post-inverze níže    vrátit se zbytekPolynomial}

Fragment kódu 2: Polynomiální dělení s odloženou zprávou XORing

Jedná se o standardní implementaci hardwarového CRC bit-at-a-time a je hodné studia; jakmile pochopíte, proč to počítá přesně stejný výsledek jako u první verze, zbývající optimalizace jsou zcela jednoduché. Li zbytekPolynomiální je pouze n bity dlouhé, pak ${displaystyle x ^ {n}}$ jeho koeficienty a generátor Polynom jsou jednoduše vyřazeny. To je důvod, proč obvykle uvidíte binárně psané polynomy CRC s vynecháním předního koeficientu.

U softwaru je vhodné si uvědomit, že zatímco jeden může oddálit xor každého bitu až do poslední chvíle je možné to udělat i dříve. Obvykle je vhodné provést xor A byte najednou, dokonce i v implementaci bit-at-a-time, jako je tato:

funkce crc (bajtové pole řetězec [1..len], int len) {remainderPolynomial: = 0 // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Přednastaveno na -1 níže    pro i z 1 na len {remainderPolynomial: = remainderPolynomial xor polynomialForm(řetězec [i]) * x^n-8        pro j z 1 na 8 {    // Za předpokladu 8 bitů na bajt            -li koeficient X^{n − 1} of remainderPolynomial = 1 {remainderPolynomial: = (remainderPolynomial * X) xor generatorPolynomial} jiný {remainderPolynomial: = (remainderPolynomial * X)            }        }    }    // Populární varianta zde doplňuje zbytek parametru Polynomial; vidět § Post-inverze níže    vrátit se zbytekPolynomial}

Fragment kódu 3: Polynomiální dělení s bajtovou zprávou XORing

Toto je obvykle nejkompaktnější softwarová implementace používaná v mikrokontroléry když je prostor nadprůměrně rychlý.

Řazení bitů (endianness)

Při implementaci v bitové sériové číslo Hardware, polynom generátoru jednoznačně popisuje přiřazení bitů; první přenášený bit je vždy koeficient nejvyššího výkonu ${displaystyle x}$ , a poslední ${displaystyle n}$ přenesené bity jsou zbytek CRC ${displaystyle R (x)}$ , počínaje koeficientem ${displaystyle x ^ {n-1}}$ a končí koeficientem ${displaystyle x ^ {0}}$ , a.k.a. koeficient 1.

Když jsou však bity zpracovávány a byte najednou, například při použití paralelní přenos, rámování bajtů jako v Kódování 8B / 10B nebo RS-232 -styl asynchronní sériová komunikace, nebo při implementaci CRC v software, je nutné specifikovat bitové řazení (endianness) dat; který bit v každém bajtu je považován za „první“ a bude koeficientem vyššího výkonu ${displaystyle x}$ .

Pokud jsou data určena sériová komunikace, je nejlepší použít pořadí bitů, do kterých budou data nakonec odeslána. Je to proto, že schopnost CRC detekovat chyby série je založen na blízkosti polynomu zprávy ${displaystyle M (x)}$ ; pokud se sousední polynomiální členy nepřenášejí postupně, lze shluk fyzické chyby jedné délky považovat za delší shluk kvůli přeskupení bitů.

Například obojí IEEE 802 (ethernet ) a RS-232 (sériový port ) standardy specifikují přenos s nejméně významným bitem jako první (little-endian), takže softwarová implementace CRC na ochranu dat odesílaných přes takový odkaz by měla mapovat nejméně významné bity v každém bajtu na koeficienty s nejvyššími ${displaystyle x}$ . Na druhou stranu, diskety a většina pevné disky nejdříve zapište nejvýznamnější bit každého bajtu.

Implementace softwaru CRC prvního lsbit je o něco jednodušší, takže je vidět o něco častěji, ale pro mnoho programátorů je snazší sledovat pořadí bitů na prvním místě. Tak například XMODEM Rozšíření -CRC, rané použití CRC v softwaru, používá CRC s prvním bitmbitem.

Doposud se pseudokód vyhýbal specifikaci řazení bitů v bajtech popisem posunů v pseudokódu jako násobení ${displaystyle x}$ a psaní explicitních převodů z binární do polynomiální formy. V praxi se CRC uchovává ve standardním binárním registru pomocí konkrétní konvence uspořádání bitů. Ve formě s prvním bitem budou nejdříve odeslány nejvýznamnější binární bity, které tak budou obsahovat polynomiální koeficienty vyššího řádu, zatímco ve formě ssbit-first budou nejméně významné binární bity obsahovat koeficienty vyššího řádu. Výše uvedený pseudokód lze napsat v obou formách. Pro konkrétnost to používá 16bitový CRC-16-CCITT polynomiální ${displaystyle x ^ {16} + x ^ {12} + x ^ {5} +1}$ :

// Nejvýznamnější bit nejprve (big-endian)// x ^ 16 + x ^ 12 + x ^ 5 + 1 = (1) 0001 0000 0010 0001 = 0x1021funkce crc (bajtové pole řetězec [1..len], int len) {rem: = 0 // Populární varianta zde doplňuje rem    pro i z 1 na len {rem: = rem xor (řetězec [i] levý Shift (n-8)) // n = 16 v tomto příkladu        pro j z 1 na 8 {   // Za předpokladu 8 bitů na bajt            -li rem a 0x8000 { // pokud je nastaven bit nejvíce vlevo (nejvýznamnější)                rem: = (rem levý Shift 1) xor 0x1021} jiný {rem: = rem levý Shift 1} rem: = rem a 0xffff // Oříznout zbytek na 16 bitů}} // Populární varianta zde doplňuje rem    vrátit se rem}

Fragment kódu 4: Rozdělení založené na posuvném registru, nejprve MSB

// Nejméně významný bit nejprve (malý endian)// x ^ 16 + x ^ 12 + x ^ 5 + 1 = 1000 0100 0000 1000 (1) = 0x8408funkce crc (bajtové pole řetězec [1..len], int len) {rem: = 0 // Populární varianta zde doplňuje rem    pro i z 1 na len {rem: = rem xor řetězec [i] pro j z 1 na 8 {   // Za předpokladu 8 bitů na bajt            -li rem a 0x0001 { // pokud je nastaven bit nejvíce vpravo (nejvýznamnější)                rem: = (rem rightShift 1) xor 0x8408} jiný {rem: = rem rightShift 1            }        }    }    // Populární varianta zde doplňuje rem    vrátit se rem}

Fragment kódu 5: Rozdělení založené na posuvném registru, nejprve LSB

Všimněte si, že forma lsbit-first vyhýbá se nutnosti přesouvat řetězec [i] před xor. V obou případech nezapomeňte přenášet bajty CRC v pořadí, které odpovídá vaší zvolené konvenci řazení bitů.

Vícebitový výpočet

Další běžná optimalizace používá a vyhledávací tabulka indexováno nejvyššími koeficienty řádu rem zpracovat více než jeden bit dividendy na iteraci.^[3] Nejčastěji se používá vyhledávací tabulka s 256 položkami, která nahradí vnitřní smyčku j s:

// Msbit-firstrem = (rem levý Shift 8) xor big_endian_table [řetězec [i] xor ((úplně vlevo 8 bitů rem) rightShift (n-8))] // Lsbit-firstrem = (rem rightShift 8) xor little_endian_table [řetězec [i] xor (úplně 8 bitů rem)]

Fragment kódu 6: Jádra dělení na základě tabulky

Jeden z nejčastěji se vyskytujících algoritmů CRC je známý jako CRC-32, používaný (mimo jiné) Ethernet, FDDI, ZIP a další archivní formáty, a PNG formát obrázku. Jeho polynom lze zapsat nejprve msbit jako 0x04C11DB7 nebo lsbit-first jako 0xEDB88320. Webová stránka W3C zapnuta PNG obsahuje dodatek s krátkou a jednoduchou tabulkovou implementací v C CRC-32.^[4] Všimněte si, že kód odpovídá zde prezentovanému pseudokódu lsbit-first byte-at-a-time a tabulka je generována pomocí kódu bit-at-a-time.

Obvykle je nejvhodnější použít tabulku s 256 položkami, ale lze použít i jiné velikosti. V malých mikrokontrolérech poskytuje 16-vstupová tabulka ke zpracování čtyř bitů najednou užitečné zlepšení rychlosti při zachování malé tabulky. Na počítačích s dostatečným úložištěm a 65536-vstupní tabulku lze použít ke zpracování 16 bitů najednou.

Generování tabulek

Software pro generování tabulek je tak malý a rychlý, že je obvykle rychlejší je vypočítat při spuštění programu, než načítat předpočítané tabulky z úložiště. Jednou populární technikou je použití kódu bit-at-a-time 256krát ke generování CRC 256 možných 8bitových bajtů. To však lze výrazně optimalizovat využitím výhody této vlastnosti tabulka [i xor j] == tabulka [i] xor tabulka [j]. Pouze záznamy v tabulce odpovídající mocnině dvou je třeba vypočítat přímo.

V následujícím příkladu kódu crc drží hodnotu tabulka [i]:

big_endian_table [0]: = 0crc: = 0x8000 // Za předpokladu 16bitového polynomui: = 1dělat {    -li crc a 0x8000 {crc: = (crc levý Shift 1) xor 0x1021 // Polynom CRC    } jiný {crc: = crc levý Shift 1} // crc je hodnota big_endian_table [i]; nechat j iterovat přes již inicializované položky    pro j z 0 na i − 1 {big_endian_table [i + j]: = crc xor big_endian_table [j]; } i: = i levý Shift 1} zatímco i <256

Fragment kódu 7: Generování tabulky CRC typu Byte-at-a-time, nejprve MSB

little_endian_table [0]: = 0crc: = 1; i: = 128dělat {    -li crc a 1 {crc: = (crc rightShift 1) xor 0x8408 // Polynom CRC    } jiný {crc: = crc rightShift 1} // crc je hodnota little_endian_table [i]; nechat j iterovat přes již inicializované položky    pro j z 0 na 255 podle 2 × i {little_endian_table [i + j]: = crc xor little_endian_table [j]; } i: = i posun práv 1} zatímco i> 0

Fragment kódu 8: Generování tabulky CRC typu Byte-at-a-time, nejprve LSB

V těchto ukázkách kódu index tabulky i + j je ekvivalentní k i xor j; můžete použít jakoukoli formu, která je pohodlnější.

Byte-Slicing pomocí více tabulek

^[5]^[6]^[7]^[8]^[9]

Paralelní výpočet bez tabulky

Paralelní aktualizaci bajtu nebo slova najednou lze provést také explicitně, bez tabulky.^[10] To se běžně používá při vysokorychlostních hardwarových implementacích. Pro každý bit je rovnice vyřešena po posunutí 8 bitů. V následujících tabulkách jsou uvedeny rovnice pro některé běžně používané polynomy s použitím následujících symbolů:

C_i	CRC bit 7… 0 (nebo 15… 0) před aktualizací
r_i	CRC bit 7… 0 (nebo 15… 0) po aktualizaci
d_i	bit vstupních dat 7… 0
E_i = d_i + c_i	E_p = e₇ + e₆ +… + E₁ + e₀ (paritní bit)
s_i = d_i + c_{i + 8}	s_p = s₇ + s₆ +… + S₁ + s₀ (paritní bit)

Bitová aktualizace aktualizačních rovnic pro některé polynomy CRC-8 po posunutí 8 bitů
Polynom:	(X⁷ + X³ + 1) × X (vlevo posunutý CRC-7-CCITT)	X⁸ + X⁵ + X⁴ + 1 (CRC-8-Dallas / Maxim)
Koeficienty:	0x12 = (0x09 << 1) (MSBF /normální)	0x8c (LSBF /zvrátit)
r₀ ← r₁ ← r₂ ← r₃ ← r₄ ← r₅ ← r₆ ← r₇ ←	0e₀ + e₄ + e₇E₁ + e₅E₂ + e₆E₃ + e₇ + e₀ + e₄ + e₇E₄ + e₁ + e₅E₅ + e₂ + e₆E₆ + e₃ + e₇	E₀ + e₄ + e₁ + e₀ + e₅ + e₂ + e₁E₁ + e₅ + e₂ + e₁ + e₆ + e₃ + e₂ + e₀E₂ + e₆ + e₃ + e₂ + e₀ + e₇ + e₄ + e₃ + e₁E₃ + e₀ + e₇ + e₄ + e₃ + e₁E₄ + e₁ + e₀E₅ + e₂ + e₁E₆ + e₃ + e₂ + e₀E₇ + e₄ + e₃ + e₁
Kód C. fragmenty:	uint8_t C, d, E, F, r; … E = C ^ d; F = E ^ (E >> 4) ^ (E >> 7); r = (F << 1) ^ (F << 4);	uint8_t C, d, E, F, r; … E = C ^ d; F = E ^ (E << 3) ^ (E << 4) ^ (E << 6); r = F ^ (F >> 4) ^ (F >> 5);

Bitová aktualizace aktualizovaných rovnic pro některé polynomy CRC-16 po posunutí 8 bitů
Polynom:	X¹⁶ + X¹² + X⁵ + 1 (CRC-16-CCITT)		X¹⁶ + X¹⁵ + X² + 1 (CRC-16-ANSI)
Koeficienty:	0x1021 (MSBF / normální)	0x8408 (LSBF / reverzní)	0x8005 (MSBF / normální)	0xa001 (LSBF / reverzní)
r₀ ← r₁ ← r₂ ← r₃ ← r₄ ← r₅ ← r₆ ← r₇ ← r₈ ← r₉ ← r₁₀ ← r₁₁ ← r₁₂ ← r₁₃ ← r₁₄ ← r₁₅ ←	s₄ + s₀s₅ + s₁s₆ + s₂s₇ + s₃ s₄ s₅ + s₄ + s₀ s₆ + s₅ + s₁ s₇ + s₆ + s₂C₀ + s₇ + s₃C₁ + s₄C₂ + s₅C₃ + s₆C₄ + s₇ + s₄ + s₀C₅ + s₅ + s₁C₆ + s₆ + s₂C₇ + s₇ + s₃	C₈ + e₄ + e₀C₉ + e₅ + e₁C₁₀ + e₆ + e₂C₁₁ + e₀ + e₇ + e₃C₁₂ + e₁C₁₃ + e₂C₁₄ + e₃C₁₅ + e₄ + e₀ E₀ + e₅ + e₁ E₁ + e₆ + e₂ E₂ + e₇ + e₃ E₃ E₄ + e₀ E₅ + e₁ E₆ + e₂ E₇ + e₃	s_p s₀ + s_p s₁ + s₀ s₂ + s₁ s₃ + s₂ s₄ + s₃ s₅ + s₄ s₆ + s₅C₀ + s₇ + s₆C₁ + s₇C₂C₃C₄C₅C₆C₇ + s_p	C₈ + e_pC₉C₁₀C₁₁C₁₂C₁₃C₁₄ + e₀C₁₅ + e₁ + e₀ E₂ + e₁ E₃ + e₂ E₄ + e₃ E₅ + e₄ E₆ + e₅ E₇ + e₆ E_p + e₇ E_p
Kód C. fragmenty:	uint8_t d, s, t; uint16_t C, r; … s = d ^ (C >> 8); t = s ^ (s >> 4); r = (C << 8) ^ t ^ (t << 5) ^ (t << 12);	uint8_t d, E, F; uint16_t C, r; … E = C ^ d; F = E ^ (E << 4); r = (C >> 8) ^ (F << 8) ^ (F << 3) ^ (F >> 4);	uint8_t d, s, p; uint16_t C, r, t; … s = d ^ (C >> 8); p = s ^ (s >> 4); p = p ^ (p >> 2); p = p ^ (p >> 1); p = p & 1; t = p \| (s << 1); r = (C << 8) ^ (t << 15) ^ t ^ (t << 1);	uint8_t d, E, p; uint16_t C, r, F; … E = C ^ d; p = E ^ (E >> 4); p = p ^ (p >> 2); p = p ^ (p >> 1); p = p & 1; F = E \| (p << 8); r = (C >> 8) ^ (F << 6) ^ (F << 7) ^ (F >> 8);

Dvoustupňový výpočet

Vzhledem k tomu, že polynom CRC-32 má velké množství termínů, při výpočtu zbytku bajt v každém okamžiku závisí každý bit na několika bitech předchozí iterace. V bajtparalelních hardwarových implementacích to vyžaduje buď vícevstupové nebo kaskádové brány XOR, což se zvyšuje šíření zpoždění.

Chcete-li maximalizovat rychlost výpočtu, an mezilehlý zbytek lze vypočítat předáním zprávy přes 123bitový posuvný registr. Polynom je pečlivě vybraný násobek standardního polynomu, takže termíny (zpětnovazební odbočky) jsou široce rozmístěny a žádný zbytek není XORed více než jednou na bajtovou iteraci. Proto jsou zapotřebí pouze nejrychlejší možné brány XOR se dvěma vstupy. Nakonec je mezilehlý zbytek rozdělen standardním polynomem ve druhém posuvném registru, čímž se získá zbytek CRC-32.^[11]

Kontrola jedním průchodem

Při připojování CRC ke zprávě je možné odpojit přenesený CRC, přepočítat jej a ověřit přepočítanou hodnotu proti přenesenému. V hardwaru se však běžně používá jednodušší technika.

Když je CRC vysílán se správným pořadí bytů (odpovídající zvolené konvenci řazení bitů), může přijímač vypočítat celkový CRC přes zprávu a CRC, a pokud jsou správné, bude výsledek nulový. Tato možnost je důvodem, proč to dělá většina síťových protokolů, které obsahují CRC před koncový oddělovač; pro kontrolu CRC není nutné vědět, zda se blíží konec paketu.

Varianty CRC

V praxi většina standardů stanoví přednastavení registru na všechny a invertování CRC před přenosem. To nemá žádný vliv na schopnost CRC detekovat změněné bity, ale dává mu to schopnost všimnout si bitů, které jsou přidány ke zprávě.

Přednastaveno na -1

Základní matematika CRC přijímá (považuje za správně přenášené) zprávy, které, když jsou interpretovány jako polynom, jsou násobkem polynomu CRC. Pokud jsou před takovou zprávu přidány některé úvodní 0 bitů, nezmění její interpretaci jako polynom. To odpovídá skutečnosti, že 0001 a 1 jsou stejné číslo.

Ale pokud se přenášená zpráva stará o vedení 0 bitů, je neschopnost základního algoritmu CRC detekovat takovou změnu nežádoucí. Pokud je možné, že chyba přenosu může přidat takové bity, jednoduchým řešením je začít s rem posuvný registr nastaven na nějakou nenulovou hodnotu; pro pohodlí se obvykle používá hodnota all-ones. To je matematicky ekvivalentní s doplňováním (binární NENÍ) prvního n kousky zprávy, kde n je počet bitů v registru CRC.

To nijak neovlivňuje generování a kontrolu CRC, pokud generátor i kontrola používají stejnou počáteční hodnotu. Jakákoli nenulová počáteční hodnota bude stačit a několik standardů specifikuje neobvyklé hodnoty,^[12] ale hodnota všeho (−1 v binární dvojici komplementu) je zdaleka nejběžnější. Všimněte si, že generování / kontrola CRC s jedním průchodem bude při správné zprávě stále poskytovat výsledek nula, bez ohledu na přednastavenou hodnotu.

Post-inverze

Stejný druh chyby může nastat na konci zprávy, i když u omezenější sady zpráv. Přidání 0 bitů ke zprávě je ekvivalentní vynásobení jeho polynomu číslem X, a pokud to byl dříve násobek polynomu CRC, bude také výsledkem tohoto násobení. To odpovídá skutečnosti, že protože 726 je násobkem 11, je to také 7260.

Podobné řešení lze použít na konci zprávy a invertovat registr CRC před jeho připojením ke zprávě. Jakákoli nenulová změna bude opět fungovat; invertování všech bitů (XORing s all-ones vzorem) je prostě nejběžnější.

To má vliv na kontrolu CRC jedním průchodem: místo vytváření výsledku nula, když je zpráva správná, vytvoří pevný nenulový výsledek. (Přesněji řečeno, výsledkem je CRC (bez nenulové předvolby, ale s post-invertem) inverzního vzoru.) Jakmile je tato konstanta získána (nejsnadněji provedením jednoprůchodového generování / kontroly CRC na libovolná zpráva), lze ji použít přímo k ověření správnosti jakékoli jiné zprávy kontrolované pomocí stejného algoritmu CRC.

Viz také

Obecná kategorie

Chyba při opravě kódu
Seznam hashovacích funkcí
Parita je ekvivalentní 1bitovému CRC s polynomem $X +1$ .

Kontrolní součty jiné než CRC

Reference

^ Dubrova, Elena; Mansouri, Shohreh Sharif (květen 2012). „Přístup BDD ke konstrukci LFSR pro paralelní kódování CRC“. Proceedings of IEEE International Symposium on Multiple-Valued Logic: 128–133. ISBN 978-0-7695-4673-5.
^ ^A ^b Williams, Ross N. (1996-09-24). „Bezbolestný průvodce algoritmy detekce chyb CRC V3.00“. Archivovány od originál dne 2006-09-27. Citováno 2016-02-16.
^ Sarwate, Dilip V. (srpen 1998). "Výpočet kontrol cyklické redundance prostřednictvím vyhledání tabulky". Komunikace ACM. 31 (8): 1008–1013. doi:10.1145/63030.63037.
^ „Specifikace přenosné síťové grafiky (PNG) (druhé vydání): příloha D, implementace ukázkového kódu cyklické redundance“. W3C. 2003-11-10. Citováno 2016-02-16.
^ Kounavis, Michael E .; Berry, Frank L. (27. – 30. Června 2005). Systematický přístup k budování vysoce výkonných softwarových generátorů CRC (PDF). 2013 IEEE Symposium on Computers and Communications (ISCC). Cartagena, Murcia, Španělsko. str. 855–862. doi:10.1109 / ISCC.2005.18. ISBN 0-7695-2373-0.
^ Berry, Frank L .; Kounavis, Michael E. (listopad 2008). "Nové algoritmy vyhledávání na základě tabulek pro vysoce výkonnou generaci CRC". Transakce IEEE na počítačích. 57 (11): 1550–1560. doi:10.1109 / TC.2008.85.
^ Vysoce oktanová generace CRC s algoritmem Intel Slicing-by-8 (PDF) (Technická zpráva). Intel. Archivovány od originál (PDF) dne 22. 7. 2012.
^ Menon-Sen, Abhijit (2017-01-20). „Kdo vynalezl algoritmus CRC32 pro krájení podle N?“.
^ https://github.com/torvalds/linux/blob/master/Documentation/crc32.txt
^ Jon Buller (1996-03-15). „Re: 8051 and CRC-CCITT“. Diskusní skupina: comp.arch.embedded. Usenet: [email protected]. Citováno 2016-02-16.
^ Glaise, René J. (1997-01-20). „Dvoustupňový výpočet kódu cyklické redundance CRC-32 pro sítě ATM“. IBM Journal of Research and Development. Armonk, NY: IBM. 41 (6): 705. doi:10.1147 / rd.416.0705. Archivovány od originál dne 30. 1. 2009. Citováno 2016-02-16.
^ Např. nízkofrekvenční RFID Datový list TMS37157 - Pasivní zařízení nízkofrekvenčního rozhraní s EEPROM a rozhraním transpondéru 134,2 kHz (PDF), Texas Instruments, Listopad 2009, s. 39, vyvoláno 2016-02-16, Generátor CRC je inicializován s hodnotou 0x3791, jak je znázorněno na obrázku 50.

externí odkazy

JohnPaul Adamovsky. „64bitový cyklický redundantní kód - XOR dlouhé rozdělení k vyhledání tabulky po bytewise“.

Andrew Kadarch, Bob Jenkins. "Efektivní (~ 1 cyklus CPU na bajt) implementace CRC".

[1] Dubrova, Elena; Mansouri, Shohreh Sharif (květen 2012). „Přístup BDD ke konstrukci LFSR pro paralelní kódování CRC“. Proceedings of IEEE International Symposium on Multiple-Valued Logic: 128–133. ISBN 978-0-7695-4673-5.

[williams96-2] A ^b Williams, Ross N. (1996-09-24). „Bezbolestný průvodce algoritmy detekce chyb CRC V3.00“. Archivovány od originál dne 2006-09-27. Citováno 2016-02-16.

[3] Sarwate, Dilip V. (srpen 1998). "Výpočet kontrol cyklické redundance prostřednictvím vyhledání tabulky". Komunikace ACM. 31 (8): 1008–1013. doi:10.1145/63030.63037.

[4] „Specifikace přenosné síťové grafiky (PNG) (druhé vydání): příloha D, implementace ukázkového kódu cyklické redundance“. W3C. 2003-11-10. Citováno 2016-02-16.

[5] Kounavis, Michael E .; Berry, Frank L. (27. – 30. Června 2005). Systematický přístup k budování vysoce výkonných softwarových generátorů CRC (PDF). 2013 IEEE Symposium on Computers and Communications (ISCC). Cartagena, Murcia, Španělsko. str. 855–862. doi:10.1109 / ISCC.2005.18. ISBN 0-7695-2373-0.

[6] Berry, Frank L .; Kounavis, Michael E. (listopad 2008). "Nové algoritmy vyhledávání na základě tabulek pro vysoce výkonnou generaci CRC". Transakce IEEE na počítačích. 57 (11): 1550–1560. doi:10.1109 / TC.2008.85.

[7] Vysoce oktanová generace CRC s algoritmem Intel Slicing-by-8 (PDF) (Technická zpráva). Intel. Archivovány od originál (PDF) dne 22. 7. 2012.

[8] Menon-Sen, Abhijit (2017-01-20). „Kdo vynalezl algoritmus CRC32 pro krájení podle N?“.

[9] ttps://github.com/torvalds/linux/blob/master/Documentation/crc32.txt

[10] Jon Buller (1996-03-15). „Re: 8051 and CRC-CCITT“. Diskusní skupina: comp.arch.embedded. Usenet: [email protected]. Citováno 2016-02-16.

[glaise-11] Glaise, René J. (1997-01-20). „Dvoustupňový výpočet kódu cyklické redundance CRC-32 pro sítě ATM“. IBM Journal of Research and Development. Armonk, NY: IBM. 41 (6): 705. doi:10.1147 / rd.416.0705. Archivovány od originál dne 30. 1. 2009. Citováno 2016-02-16.

[12] Např. nízkofrekvenční RFID Datový list TMS37157 - Pasivní zařízení nízkofrekvenčního rozhraní s EEPROM a rozhraním transpondéru 134,2 kHz (PDF), Texas Instruments, Listopad 2009, s. 39, vyvoláno 2016-02-16, Generátor CRC je inicializován s hodnotou 0x3791, jak je znázorněno na obrázku 50.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]