CS
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

Cyklický redundantní součet

From Wikipedia, the free encyclopedia

Cyklický redundantní součet
Ekvivalence polynomů a bitových posloupnostíPrincip výpočtu CRCZákladní vlastnosti CRCPříklad výpočtu CRCImplementaceOdkazyReferenceSouvisející články

Cyklický redundantní součet, označovaný také CRC (zkratka anglického Cyclic redundancy check) je speciální hašovací funkce, používaná k detekci chyb během přenosu či ukládání dat. Pro svou jednoduchost a dobré matematické vlastnosti jde o velmi rozšířený způsob realizace kontrolního součtu. Kontrolní součet bývá odesílán či ukládán společně s daty, při jejichž přenosu nebo uchovávání by mohlo dojít k chybě. Po převzetí dat je znovu nezávisle spočítán. Pokud je nezávisle spočítaný kontrolní součet odlišný od přeneseného nebo uloženého, je zřejmé že při přenosu nebo uchovávání došlo k chybě. Pokud je shodný, tak téměř jistě k žádné chybě nedošlo. V určitých případech je možné chybu pomocí CRC opravit.

ikona
Tento článek potřebuje doplnit či upravit literaturu.

CRC je vhodný pro zjišťování chyb vzniklých v důsledku selhání techniky, avšak jako metoda pro odhalení záměrné změny dat počítačovými piráty je příliš slabý. V tomto případě je třeba používat speciální hašovací funkce určené pro šifrovací algoritmy.

Například posloupnost bitů „100101“ může být interpretována jako polynom x 5 + x 2 + 1 {\displaystyle x^{5}+x^{2}+1} {\displaystyle x^{5}+x^{2}+1}, posloupnost bitů „110011“ může být přepsána jako polynom x 5 + x 4 + x + 1 {\displaystyle x^{5}+x^{4}+x+1} {\displaystyle x^{5}+x^{4}+x+1}. Pokud nad bity těchto dvou posloupností provedeme operaci XOR, dostáváme posloupnost „010110“, která odpovídá polynomu x 4 + x 2 + x {\displaystyle x^{4}+x^{2}+x} {\displaystyle x^{4}+x^{2}+x}.

Stejný výsledek dostaneme při sčítání polynomů v konečném tělese G F ( 2 n ) {\displaystyle GF(2^{n})} {\displaystyle GF(2^{n})}:

( x 5 + x 2 + 1 ) + ( x 5 + x 4 + x + 1 ) = 2 x 5 + x 4 + x 2 + x + 2 ≡ x 4 + x 2 + x {\displaystyle (x^{5}+x^{2}+1)+(x^{5}+x^{4}+x+1)=2x^{5}+x^{4}+x^{2}+x+2\equiv x^{4}+x^{2}+x} {\displaystyle (x^{5}+x^{2}+1)+(x^{5}+x^{4}+x+1)=2x^{5}+x^{4}+x^{2}+x+2\equiv x^{4}+x^{2}+x}

Právě jednoduchá implementace operací nad bitovými posloupnostmi je jedním z hlavních důvodů širokého rozšíření CRC algoritmů.

Výsledek výpočtu CRC je určen vstupní posloupností bitů (polynom M ( x ) {\displaystyle M(x)} {\displaystyle M(x)}) a zvoleným klíčem (což je také posloupnost bitů, polynom G ( x ) {\displaystyle G(x)} {\displaystyle G(x)}). Když vstupní posloupnost a klíč interpretujeme jako polynomy nad tělesem G F ( 2 n ) {\displaystyle GF(2^{n})} {\displaystyle GF(2^{n})}, pak CRC je zbytek po dělení (polynom R ( x ) {\displaystyle R(x)} {\displaystyle R(x)}) polynomu vstupní posloupnosti polynomem klíče. Výsledkem je polynom, který následně interpretujeme jako bitovou posloupnost. Při vhodně zvoleném klíči vede i malá změna ve vstupní posloupnosti k podstatně odlišnému výsledku, při náhodné změně vstupní posloupnosti pak pravděpodobnost odhalení chyby roste s šířkou klíče (např. pro klíč stupně 16 by to měla být hodnota 1 − 1 / 2 16 ≈ 0 , 999985 {\displaystyle 1-1/2^{16}\approx 0,999985} {\displaystyle 1-1/2^{16}\approx 0,999985}).

CRC je tedy založen na dělení v konečném tělese G F ( 2 n ) {\displaystyle GF(2^{n})} {\displaystyle GF(2^{n})}, tělese polynomů nad celými čísly modulo 2. Jednodušeji řečeno, je to množina polynomů, jejichž koeficienty mohou nabývat pouze hodnot 0 a 1. Tyto polynomy sčítáme, odčítáme, dělíme a násobíme jako obyčejné polynomy, avšak nad výslednými koeficienty provádíme operaci modulo 2 (zbytek po dělení dvěma). Například −2 modulo 2 je 0, −1 modulo 2 je 1, 0 modulo 2 je 0, 1 modulo 2 je 1, 2 modulo 2 je 0, 3 modulo 2 je 1, 4 modulo 2 je 0 atd.

( x 2 + x ) + ( x + 1 ) = x 2 + 2 x + 1 ≡ x 2 + 1 {\displaystyle (x^{2}+x)+(x+1)=x^{2}+2x+1\equiv x^{2}+1} {\displaystyle (x^{2}+x)+(x+1)=x^{2}+2x+1\equiv x^{2}+1}

Ze dvojky se v tomto případě stane 0, protože operace nad koeficienty se provádí modulo 2. Násobení je podobné:

( x 2 + x ) ( x + 1 ) = x 3 + 2 x 2 + x ≡ x 3 + x {\displaystyle (x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x} {\displaystyle (x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x}

Můžeme také dělit polynomy modulo 2. Například

x 3 + x 2 + x x + 1 = ( x 2 + 1 ) − 1 x + 1 {\displaystyle {\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}} {\displaystyle {\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}}

To lze přepsat jako

( x 3 + x 2 + x ) = ( x 2 + 1 ) ( x + 1 ) − 1 ≡ ( x 2 + 1 ) ( x + 1 ) + 1 {\displaystyle (x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1\equiv (x^{2}+1)(x+1)+1} {\displaystyle (x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1\equiv (x^{2}+1)(x+1)+1}

Ve výše uvedeném dělení představuje M ( x ) = x 3 + x 2 + x {\displaystyle M(x)=x^{3}+x^{2}+x} {\displaystyle M(x)=x^{3}+x^{2}+x} vstupní bitovou posloupnost „1110“, G ( x ) = x + 1 {\displaystyle G(x)=x+1} {\displaystyle G(x)=x+1} představuje klíč (jeho bitová posloupnost je „11“, jeho stupeň je 1), zbytkem po dělení je polynom R ( x ) = 1 {\displaystyle R(x)=1} {\displaystyle R(x)=1}. Hodnota CRC odpovídá zbytku po dělení převedeném na bitovou posloupnost, v tomto případě tedy jde o hodnotu „1“.

  • Schopnost detekce chyb záleží na volbě klíče (též generující polynom, G ( x ) {\displaystyle G(x)} {\displaystyle G(x)}). Při správné volbě hodnoty mají delší klíče lepší schopnost detekce chyb.
  • Číslo za písmeny CRC určuje stupeň řídícího polynomu, např. CRC16 je kontrolní součet typu CRC s řídícím polynomem stupně 16 (nejvyšší koeficient je x 16 {\displaystyle x^{16}} {\displaystyle x^{16}}).
  • Při uvádění číselných hodnot kontrolních polynomů se často zanedbává nejvyšší bit, protože má vždy hodnotu 1. Co tedy znamená „kontrolní součet typu CRC16 s řídícím polynomem 0x1081“? 0x1081 je hexadecimální číslo s binární hodnotou „0001 0000 1000 0001“, bitová posloupnost řídícího polynomu je „1 0001 0000 1000 0001“. Bez jedničky přidané na začátek by se jednalo o polynom pouze 12. stupně! Řídící polynom má v tomto případě tedy hodnotu G ( x ) = x 16 + x 12 + x 7 + 1 {\displaystyle G(x)=x^{16}+x^{12}+x^{7}+1} {\displaystyle G(x)=x^{16}+x^{12}+x^{7}+1}.
  • Určení CRC pouze řídícím polynomem je nejednoznačné, protože různé algoritmy mohou vytvářet vstupní bitové posloupnosti různým způsobem. Z různých historických a technických důvodů může při výpočtu docházet například ke změně pořadí bajtů, k otočení pořadí bitů v bajtu, nebo k přidávání různých bitových posloupností před vstupní data a za ně.
  • Protože CRC je založeno na dělení, nerozezná přidané nuly na začátku vstupních dat M ( x ) {\displaystyle M(x)} {\displaystyle M(x)}. Proto se někdy při výpočtu CRC před vstupní data dává jednička.
  • Předchozí problém s přidanými nulami na začátku lze v některých implementacích výpočtu odstranit nastavením polynomu R ( x ) {\displaystyle R(x)} {\displaystyle R(x)} (zbytek po dělení) na nenulovou hodnotu před zahájením vlastního výpočtu (např. 0xFFFF u protokolu Modbus/RTU).
  • Při některých způsobech výpočtu se za vstupní data přidává stejný počet nul, jako je šířka CRC. CRC vypočtené ze vstupních dat a uloženého CRC je pak nulové.

Předpokládejme 8bitové CRC s generujícím polynomem G ( x ) = x 8 + x 2 + x + 1 {\displaystyle G(x)=x^{8}+x^{2}+x+1} {\displaystyle G(x)=x^{8}+x^{2}+x+1}, což odpovídá 9bitovému řetězci „100000111“.

Cílem je spočítat CRC pro 8bitovou zprávu obsahující písmeno „W“, jehož ASCII kód je dekadicky 8710 nebo šestnáctkově 5716. Tato hodnota může být odeslána dvěma způsoby, čemuž odpovídají dva různé polynomy M ( x ) {\displaystyle M(x)} {\displaystyle M(x)}. V případě, že nejvýznamnější bit (MSB) bude první (vlevo), bude M ( x ) = x 6 + x 4 + x 2 + x + 1 {\displaystyle M(x)=x^{6}+x^{4}+x^{2}+x+1} {\displaystyle M(x)=x^{6}+x^{4}+x^{2}+x+1} = 01010111. V případě prvního LSB (nejméně významný bit) bude M ( x ) = x 7 + x 6 + x 5 + x 3 + x {\displaystyle M(x)=x^{7}+x^{6}+x^{5}+x^{3}+x} {\displaystyle M(x)=x^{7}+x^{6}+x^{5}+x^{3}+x} = 11101010.

Před vlastním výpočtem je M ( x ) {\displaystyle M(x)} {\displaystyle M(x)} doplněn zprava osmi nulovými bity. Výpočet zbytku po dělení polynomu M ( x ) ⋅ x 8 {\displaystyle M(x)\cdot x^{8}} {\displaystyle M(x)\cdot x^{8}} polynomem G ( x ) {\displaystyle G(x)} {\displaystyle G(x)} bude připomínat ruční dělení víceciferných čísel se dvěma zjednodušeními:

  • počítá se pouze se symboly 0 a 1, navíc v tělese G F ( 2 n ) {\displaystyle GF(2^{n})} {\displaystyle GF(2^{n})} (takže např. 1 + 1 = 0; 0 − 1 = 1),
  • nezajímá nás podíl, ale pouze zbytek po dělení.
Další informace MSB první, LSB první ...
MSB prvníLSB první
0101011100000000
−000000000
=0101011100000000
−100000111
=0001011011000000
−000000000
=0001011011000000
−100000111
=0000011010110000
−000000000
=0000011010110000
−100000111
=0000001010101100
−100000111
=0000000010100010
−000000000
=0000000010100010
1110101000000000
−100000111
=0110100110000000
−100000111
=0010100001000000
−100000111
=0000100010100000
−000000000
=0000100010100000
−100000111
=0000000010011000
−000000000
=0000000010011000
−000000000
=0000000010011000
−000000000
=0000000010011000
Zavřít

Je vidět, že po každém odčítání lze rozdělit bity do třech skupin: vlevo je skupina nulových bitů; vpravo je skupina zatím původních bitů; uprostřed je zvýrazněna „zajímavá“ část dlouhá 8 bitů. V každém kroku se levá skupina o jeden bit rozšíří a pravá skupina o jeden bit zúží, až vpravo zbude pouze CRC.

V případě prvního MSB je výsledný polynom R ( x ) = x 7 + x 5 + x {\displaystyle R(x)=x^{7}+x^{5}+x} {\displaystyle R(x)=x^{7}+x^{5}+x}, což lze šestnáctkově zapsat jako A216. V případě prvního LSB je zbytkem po dělení R ( x ) = x 7 + x 4 + x 3 {\displaystyle R(x)=x^{7}+x^{4}+x^{3}} {\displaystyle R(x)=x^{7}+x^{4}+x^{3}}, což lze zapsat šestnáctkově jako 1916, ovšem za předpokladu, že LSB je první.

Při programování výpočtu CRC dle příkladu výše stačí držet v posuvném registru pouze zvýrazněnou střední část.

Následuje první příklad výpočtu CRC o n-bitech v pseudokódu. Na vstupu je pole len bitů obsahující zprávu. Operace XOR je použita pro sčítání/odčítání dvou polynomů modulo 2.

 function crc(bit array bitString[1..len], int len) {
     remainderPolynomial := polynomialForm(bitString[1..n])   // Prvních n bitů z bitString
     for i from 1 to len {
         remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0   // Předpokládejme, že bitString[j]=0 for j>len
         if coefficient of xn of remainderPolynomial = 1 {
             remainderPolynomial := remainderPolynomial xor generatorPolynomial
         }
     }
     return remainderPolynomial
 }

Operaci remainderPolynomial * x lze nahradit posunem doleva (shift-left, shl, <<).

Pro příklad v předchozí kapitolce by se tento algoritmus choval následovně:

 G = 1 0 0 0 0 0 1 1 1                  // n = 8
 M = 0 1 0 1 0 1 1 1                    // len = 8
 R = 0 1 0 1 0 1 1 1                    // remainderPolynomial := polynomialForm(bitString[1..n])
                                        // i = 1
 R = 0 1 0 1 0 1 1 1 0                  // remainderPolynomial := remainderPolynomial * x + bitString[9]
                                        // i = 2
 R =   1 0 1 0 1 1 1 0 0                // remainderPolynomial := remainderPolynomial * x + bitString[10]
 R =   0 0 1 0 1 1 0 1 1                // remainderPolynomial := remainderPolynomial xor generatorPolynomial
                                        // i = 3
 R =     0 1 0 1 1 0 1 1 0              // remainderPolynomial := remainderPolynomial * x + bitString[11]
                                        // i = 4
 R =       1 0 1 1 0 1 1 0 0            // remainderPolynomial := remainderPolynomial * x + bitString[12]
 R =       0 0 1 1 0 1 0 1 1            // remainderPolynomial := remainderPolynomial xor generatorPolynomial
                                        // i = 5
 R =         0 1 1 0 1 0 1 1 0          // remainderPolynomial := remainderPolynomial * x + bitString[13]
                                        // i = 6
 R =           1 1 0 1 0 1 1 0 0        // remainderPolynomial := remainderPolynomial * x + bitString[14]
 R =           0 1 0 1 0 1 0 1 1        // remainderPolynomial := remainderPolynomial xor generatorPolynomial
                                        // i = 7
 R =             1 0 1 0 1 0 1 1 0      // remainderPolynomial := remainderPolynomial * x + bitString[15]
 R =             0 0 1 0 1 0 0 0 1      // remainderPolynomial := remainderPolynomial xor generatorPolynomial
                                        // i = 8
 R =               0 1 0 1 0 0 0 1 0    // remainderPolynomial := remainderPolynomial * x + bitString[16]

První vadou výše uvedené ukázky je potřeba mít v paměti n+1 bitů pro remainderPolynomial, druhou vadou je potřeba doplňovat n nulových bitů vpravo za bitString. První problém lze snadno vyřešit vhodným přehozením operací (např. rem = (msb(rem)) ? ((rem<<1 + bit) xor gen) : (rem<<1 + bit);). Druhý problém lze vyřešit úpravou posledních n iterací, ale existuje i vtipnější optimalizace použitá jak v hardwarových i softwarových implementacích [zdroj?].

Protože operace XOR použitá pro odečítání generujícího polynomu od zprávy je asociativní a komutativní, nezáleží na pořadí operandů při výpočtu remainderPolynomial. A navíc bit z pole bitString stačí přidat až na poslední chvíli před testováním, zda provést xor. V následující ukázce také není potřeba předvyplňovat remainderPolynomial prvními n bity.

 function crc(bit array bitString[1..len], int len) {
     remainderPolynomial := 0
     for i from 1 to len {
         remainderPolynomial := remainderPolynomial xor (bitString[i] * xn-1)
         if (coefficient of xn-1 of remainderPolynomial) = 1 {
             remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
         } else {
             remainderPolynomial := (remainderPolynomial * x)
         }
     }
     return remainderPolynomial
 }

Tato varianta, která v jednom cyklu vyhodnotí jeden bit, je běžná v hardwarových implementacích CRC[zdroj?]. Je dobrá i pro studijní účely, po pochopení provedené optimalizace jsou již další úpravy průhlednější.

Pro příklad v předchozí kapitolce by se tento algoritmus choval následovně:

 G = 1 0 0 0 0 0 1 1 1                  // n = 8
 M = 0 1 0 1 0 1 1 1                    // len = 8
 R = 0 0 0 0 0 0 0 0                    // remainderPolynomial := 0
                                        // i = 1
 R = 0 0 0 0 0 0 0 0                    // remainderPolynomial := remainderPolynomial xor (bitString[1] * x^7)
 R =   0 0 0 0 0 0 0 0                  // remainderPolynomial := (remainderPolynomial * x)
                                        // i = 2
 R =   1 0 0 0 0 0 0 0                  // remainderPolynomial := remainderPolynomial xor (bitString[2] * x^7)
 R =     0 0 0 0 0 1 1 1                // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
                                        // i = 3
 R =     0 0 0 0 0 1 1 1                // remainderPolynomial := remainderPolynomial xor (bitString[3] * x^7)
 R =       0 0 0 0 1 1 1 0              // remainderPolynomial := (remainderPolynomial * x)
                                        // i = 4
 R =       1 0 0 0 1 1 1 0              // remainderPolynomial := remainderPolynomial xor (bitString[4] * x^7)
 R =         0 0 0 1 1 0 1 1            // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
                                        // i = 5
 R =         0 0 0 1 1 0 1 1            // remainderPolynomial := remainderPolynomial xor (bitString[5] * x^7)
 R =           0 0 1 1 0 1 1 0          // remainderPolynomial := (remainderPolynomial * x)
                                        // i = 6
 R =           1 0 1 1 0 1 1 0          // remainderPolynomial := remainderPolynomial xor (bitString[6] * x^7)
 R =             0 1 1 0 1 0 1 1        // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
                                        // i = 7
 R =             1 1 1 0 1 0 1 1        // remainderPolynomial := remainderPolynomial xor (bitString[7] * x^7)
 R =               1 1 0 1 0 0 0 1      // remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
                                        // i = 8
 R =               0 1 0 1 0 0 0 1      // remainderPolynomial := remainderPolynomial xor (bitString[8] * x^7)
 R =                 1 0 1 0 0 0 1 0    // remainderPolynomial := (remainderPolynomial * x)

Lze sice odkládat xor na poslední chvíli, ale lze jej provést i dříve a lze provést i xor pro 8 bitů (tedy pro celý bajt) zprávy najednou.

 function crc(byte array string[1..len], int len) {
     remainderPolynomial := 0
     for i from 1 to len {
         remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn-8
         for j from 1 to 8 {    // Assuming 8 bits per byte
             if coefficient of xn-1 of remainderPolynomial = 1 {
                 remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
             } else {
                 remainderPolynomial := (remainderPolynomial * x)
             }
         }
     }
     // A popular variant complements remainderPolynomial here
     return remainderPolynomial
 }

Reference

    Související články

    • ECC
    • Reedovy–Solomonovy kódy
    • pevný disk
    • SSD
    • USB flash disk
    • VHD soubor
    • záchrana dat
    Portály: Internet
    Edit in WikipediaRevision historyRead in Wikipedia

    Wikiwand in your browser!

    Seamless Wikipedia browsing. On steroids.

    Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

    Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

    Chrome
    Wikiwand for Chrome
    Edge
    Wikiwand for Edge
    Firefox
    Wikiwand for Firefox

    Ekvivalence polynomů a bitových posloupností

    Princip výpočtu CRC

    Základní vlastnosti CRC

    Příklad výpočtu CRC

    Implementace

    Odkazy