Zobrazení zdroje stránky Cyklický redundantní součet

{{bibliografie}}
'''Cyklický redundantní součet''', označovaný také '''CRC''' (zkratka anglického ''Cyclic redundancy check'') je speciální [[hašovací funkce]], používaná k [[Detekce a oprava chyb|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í součet|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.

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í [[Algoritmus|algoritmy]].

== Ekvivalence polynomů a bitových posloupností ==
Například [[posloupnost]] bitů „100101“ může být interpretována jako polynom <math>x^5 + x^2 + 1</math>, posloupnost bitů „110011“ může být přepsána jako polynom <math>x^5 + x^4 + x + 1</math>. Pokud nad bity těchto dvou posloupností provedeme operaci [[Exkluzivní disjunkce|XOR]], dostáváme posloupnost „010110“, která odpovídá polynomu <math>x^4 + x^2 + x</math>.

Stejný výsledek dostaneme při sčítání polynomů v [[konečné těleso|konečném tělese]] <math>GF(2^n)</math>:
: <math>(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</math>

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

== Princip výpočtu CRC ==
Výsledek výpočtu CRC je určen vstupní posloupností bitů (polynom <math>M(x)</math>) a zvoleným klíčem (což je také posloupnost bitů, polynom <math>G(x)</math>). Když vstupní posloupnost a klíč interpretujeme jako polynomy nad tělesem <math>GF(2^n)</math>, pak CRC je zbytek po dělení (polynom <math>R(x)</math>) [[polynom]]u 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 <math>1 - 1/2^{16} \approx 0,999985</math>).

CRC je tedy založen na dělení v konečném [[těleso (algebra)|tělese]] <math>GF(2^n)</math>, 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.
:<math>(x^2 + x) + (x + 1) = x^2 + 2x + 1 \equiv x^2 + 1</math>
Ze dvojky se v tomto případě stane 0, protože operace nad koeficienty se provádí modulo 2. [[Násobení]] je podobné:
:<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x</math>
Můžeme také dělit polynomy modulo 2. Například
:<math>\frac{x^3 + x^2 + x}{x+1} = (x^2 + 1) - \frac1{x+1}</math>
To lze přepsat jako
:<math>(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1 \equiv (x^2 + 1)(x + 1) + 1</math>
Ve výše uvedeném dělení představuje <math>M(x)=x^3 + x^2 + x</math> vstupní bitovou posloupnost „1110“, <math>G(x)=x+1</math> představuje klíč (jeho bitová posloupnost je „11“, jeho stupeň je 1), zbytkem po dělení je polynom <math>R(x)=1</math>. Hodnota CRC odpovídá zbytku po dělení převedeném na bitovou posloupnost, v tomto případě tedy jde o hodnotu „1“.

== Základní vlastnosti CRC ==
* Schopnost detekce chyb záleží na volbě klíče (též generující polynom, <math>G(x)</math>). 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 <math>x^{16}</math>).
* 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 [[Šestnáctková soustava|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 <math>G(x) = x^{16} + x^{12} + x^7 + 1</math>.
* 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 <math>M(x)</math>. 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 <math>R(x)</math> (zbytek po dělení) na nenulovou hodnotu před zahájením vlastního výpočtu (např. <tt>0xFFFF</tt> 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říklad výpočtu CRC ==
Předpokládejme 8bitové CRC s generujícím polynomem <math>G(x)=x^8+x^2+x+1</math>, což odpovídá 9bitovému řetězci „100000111“.

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

Před vlastním výpočtem je <math>M(x)</math> doplněn zprava osmi nulovými bity. Výpočet zbytku po dělení polynomu <math>M(x) \cdot x^8</math> polynomem <math>G(x)</math> 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 <math>GF(2^n)</math> (takže např. 1 + 1 = 0; 0 − 1 = 1),
* nezajímá nás podíl, ale pouze zbytek po dělení.

{| border=1 align=center
! MSB první !! LSB první
|-
|
{|
|-
| ||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0||0||0||0||0||0||0
|-
|−||0||0||0||0||0||0||0||0||0
|-
|=||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0||0||0||0||0||0
|-
| ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0||0||0||0||0
|-
| || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0||0||0||0
|-
| || || ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0||0||0
|-
| || || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0||0
|-
| || || || || ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||0||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0
|-
| || || || || || ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||0||0||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||0
|-
| || || || || || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||0||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0
|}
||
{| border="0"
|-
| ||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0||0||0||0||0||0||0
|-
|−||1||0||0||0||0||0||1||1||1
|-
|=||0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0||0||0||0||0||0
|-
| ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||0||0||0||0||0||0
|-
| || ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||0||0||0||0||0
|-
| || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0||0||0
|-
| || || || ||−||1||0||0||0||0||0||1||1||1
|-
|=||0||0||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||0||0||0
|-
| || || || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||0||0
|-
| || || || || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||0||0||0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||0
|-
| || || || || || || ||−||0||0||0||0||0||0||0||0||0
|-
|=||0||0||0||0||0||0||0||0||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|1||bgcolor=LightBlue|1||bgcolor=LightBlue|0||bgcolor=LightBlue|0||bgcolor=LightBlue|0
|}
|}

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 <math>R(x)=x^7+x^5+x</math>, což lze šestnáctkově zapsat jako A2<sub>16</sub>. V případě prvního LSB je zbytkem po dělení <math>R(x)=x^7+x^4+x^3</math>, což lze zapsat šestnáctkově jako 19<sub>16</sub>, ovšem za předpokladu, že LSB je první.

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

Následuje první příklad výpočtu CRC o ''n''-bitech v [[pseudokód]]u. Na vstupu je pole ''len'' bitů obsahující zprávu. Operace [[exkluzivní disjunkce|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] * ''x''<sup>0</sup>   ''// Předpokládejme, že bitString[j]=0 for j>len''
          '''if''' coefficient of ''x''<sup>n</sup> of remainderPolynomial = 1 {
              remainderPolynomial := remainderPolynomial '''xor''' generatorPolynomial
          }
      }
      '''return''' remainderPolynomial
  }

Operaci <tt>remainderPolynomial * ''x''</tt> lze nahradit posunem doleva (shift-left, shl, <tt>&lt;&lt;</tt>).

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 <tt>remainderPolynomial</tt>, druhou vadou je potřeba doplňovat ''n'' nulových bitů vpravo za <tt>bitString</tt>. První problém lze snadno vyřešit vhodným přehozením operací (např. <tt>rem = (msb(rem)) ? ((rem<<1 + bit) xor gen) : (rem<<1 + bit);</tt>). Druhý problém lze vyřešit úpravou posledních ''n'' [[iterace|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 <tt>remainderPolynomial</tt>. A navíc bit z pole <tt>bitString</tt> stačí přidat až na poslední chvíli před testováním, zda provést <tt>xor</tt>. V následující ukázce také není potřeba předvyplňovat <tt>remainderPolynomial</tt> 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] * ''x''<sup>n-1</sup>)
          '''if''' (coefficient of ''x''<sup>n-1</sup> 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 <tt>xor</tt> na poslední chvíli, ale lze jej provést i dříve a lze provést i <tt>xor</tt> 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]) * x<sup>n-8</sup>
          '''for''' j '''from''' 1 '''to''' 8 {    ''// Assuming 8 bits per byte''
              '''if''' coefficient of ''x''<sup>n-1</sup> of remainderPolynomial = 1 {
                  remainderPolynomial := (remainderPolynomial * ''x'') '''xor''' generatorPolynomial
              } '''else''' {
                  remainderPolynomial := (remainderPolynomial * ''x'')
              }
          }
      }
      ''// A popular variant complements remainderPolynomial here''
      '''return''' remainderPolynomial
  }

== Odkazy ==

=== Reference ===
<references />

=== Související články ===
* [[ECC]]
* [[Reedovy–Solomonovy kódy]]
* [[pevný disk]]
* [[SSD]]
* [[USB flash disk]]
* [[VHD soubor]]
* [[záchrana dat]]
{{Autoritní data}}

{{Portály|Internet}}
[[Kategorie:Kontrolní součty]]