Polinom CRC

CRC (Cyclic Redundancy Check, ciklikus redundancia ellenőrzés) az előzőekhez képes jelentősen bonyolultabb megoldás, amellyel csoportos bithibák felismerése valósítható meg. A kódot alkotó biteket egy polinom együtthatóiként kezeljük. Egy n-bites kód esetén az együtthatók x^n-1 és x⁰ közöttiek lesznek. Így a polinom felírható

x^n-1+ x^n-2+x^n-3 +x^n-4 +x^n-5 + x^n-6+ x^n-7+ .......... +x⁴ +x³ +x² + x¹+ x⁰

Például: legyen a kód 10011001. Ebben az esetben a polinom a következő lesz:

x⁷ +x⁴ + x³+ x⁰

Csak azokat a tagokat kell felírnunk, amelyik helyiértéken az eredeti kódban 1 állt.

A polinomok alkalmazásakor a kommunikációban résztvevőknek meg kell egyezniük egy közös polinomban, amelyet generátor polinomnak (Generator Polynomial) nevezünk és általában a G(x) módon jelöljük. A generátor polinommal kapcsolatban alapvető követelmény, hogy a legalsó és a legfelső bitjének 1-esnek, valamint a továbbítandó keretnek hosszabbnak kell lennie, mint a generátor polinom.

A CRC védelem során olyan ellenőrző összeget fűzünk a továbbítandó kerethez, amely úgy egészíti ki azt, hogy az így kapott keret által meghatározott polinom osztható legyen a generátor polinommal. Miután a vevő megkapta a keretet, megpróbálja elosztani a generátor polinommal. Ha az osztás során van maradék, akkor hiba történt az átvitel során. Az eljárás meglehetősen bonyolult matematikailag, de a számítógépek ezt nagyon gyorsan képesek elvégezni, sőt. 1961-ben Peterson és Brown bebizonyította, hogy az ellenőrző kód léptető-regiszterekkel előállítható. Ezt a hardvert ma már a legtöbb hibajavítással kapcsolatba kerülő áramkör használja. A m-bites ellenőrző bittel ellátott polinomkód legfeljebb m-bites csoportos bithibát hibát képes jelezni. A gyakorlatban három polinom vált szabvánnyá:

CRC-12 = x¹² +x¹¹ +x² + x¹+ 1, amit olyankor használhatunk, amikor a karakterhossz 6 bit.
CRC-16 = x¹⁶ +x¹⁵ +x² + 1, 8 bites karakterekhez használható.
CRC-CCITT = x¹⁶ +x¹² +x⁵+ 1, szintén 8 bites karakterekhez alkalmazhatjuk.

A 16 bites CRC kódok képesek felismerni minden egybites-, kétbites-, minden páratlan hibás bitet tartalmazó hibát, minden 16 vagy kevesebb bitnyi csoportos bithibát, a 17 bites csoportos bithibák 99, 997%-át, a 18 vagy magasabb bitszámú hibák 99,998%-át (forrás: Andrew S. Tannenbaum Számítógéphálózatok, Panem kiadó).