CRC (kontrolní součet)

Už se vám někdy stalo, že jste si takhle k večeru sedli k počítači, že si zasurfujete, zapli browser a nevěděli, co napsat jako URL? Prostě se jen tak odreagovat, přečíst si něco zajímavého? Už ani nevím, co mě to napadlo, asi jsem ten den zrovna nahlížel do nějakého zdrojového kódu nějakého programu a viděl tam kód počítající CRC, kterému jsem nerozuměl, nevím. Jisté je to, že jsem prostě do Googlu napsal CRC a rozhodl se přijít na to, jak vlastně takové CRC funguje a co je na tom zajímavého. Tento článek by vám chtěl stručně poreferovat o tom, co jsem se dozvěděl.

Cílem takového kontrolního součtu je, jak jistě všichni víte, detekování chyb v datech. Celý princip kontrolních součtů je celkem zřejmý. K datům samotným se připojí výsledek určité funkce, která ze vstupních dat vypočítá určité číslo, to může příjemce přepočítat, a zkontrolovat tak správnost dat. Jak však takovou funkci sestavit tak, aby odhalila opravdu co nejvíce chyb?

Abych mohl snadno demonstrovat, jak takové CRC funguje, bude dobré, když si zavedeme nějaká demonstrativní data. Tato data budou celkem zřejmě posloupnost jedniček a nul (dále jen vektor).

                10100001011111110001

Tento vektor pošleme po vymyšleném drátě do USA. Data to mají daleko, a tak dojdou porušená:

                10100000010111110001
                       ^  ^

Všimněte si jedné vlastnosti vymyšleného drátu. Tato vlastnost se velmi podobá i skutečným drátům vedoucím do USA. :-) Data se poškodila jen někde, valná většina bitů zůstala nepoškozena.

Abychom mohli říci, jaké bity se oproti původnímu vektoru při přenosu změnily, zavedeme si pojem – takzvaný chybový vektor, který bude mít jedničky právě na těch místech, kde se liší původní vektor od vektoru, který dorazil do USA:

                00000001001000000000

Charakter takových chybových vektorů je pro různá média různý. Například bude-li oním pomyslným drátem do USA poškrábaná disketa, je zřejmé, že takový škrábanec na disketě zničí data v určitě souvislé oblasti v závislosti na tloušťce drápu :-). Takže výsledný chybový vektor bude mít s největší pravděpodobností jedničky kumulované velmi blízko u sebe.

Návrh kontrolního součtu tedy musí takové častější chyby odhalovat spolehlivěji než chyby, které vznikly například propícháním diskety špendlíkem, kde by byl chybový vektor v podstatě náhodný (bude-li píchanců dostatečně mnoho a bude-li špendlík dostatečně úzký). Je nutné poznamenat, že disketu většinou na hraní dikobrazovi nedáváme :-)

Budete-li navrhovat algoritmus kontrolního součtu pro určité médium, rozhodně si nejprve uděláte obrázek o tom, jak v případě chyby bude nejčastěji chybový vektor vypadat. CRC je kontrolní součet, který, jak za okamžik uvidíme, lze jednoduchou modifikací do značné míry přizpůsobit různým typům chybových vektorů.

Hlavní operací, kterou budete při počítání CRC potřebovat, je XOR:

0 xor 1 = 1
1 xor 0 = 1
0 xor 0 = 0
1 xor 1 = 0

Celou operaci „c = a xor b“ si můžete představit také tak, že je-li a=1, pak se b zneguje.

je dobré si všimnout komutativity a asociativity:

a xor b = b xor a
(a xor b) xor c = a xor (b xor c)

zajímavá vlastnost je také:

a xor b xor b = a
a xor b xor a = b
a xor 0 = a
a xor a = 0

Příklad:

A =        10011101
B =        00100010
A xor B =  --------
           10111111
             ^   ^

Všimněte si, že výsledek xorování je vlastně stejný jako A resp. B, pouze na místech, kde bylo B=1 resp. A=1, se bity změnily. Tato vlastnost je velmi důležitá pro další pochopení!

Jak jsem se již zmínil, výstupem funkce, počítající CRC, je číslo. Toto číslo může být obecně n-bitové. Naše počítače však většinou počítají lépe s čísly, kde n je mocnina 2, počítáme zásadně CRC-16bit, CRC-32bit; možná i CRC-64bit nebo CRC-128bit. Čím je CRC „více-bitové“, tím je samozřejmě menší pravděpodobnost, že bude mít špatná zpráva v USA stejné CRC jako zpráva původní, tedy že se chyba nepozná.

Pro naše účely si ukážeme výpočet CRC-4bitového. Jediným parametrem, kterým můžeme CRC „naštelovat“, je tzv. generační polynom (dále jen GP). Představte si ho jako 4bitové číslo (4bitové, protože je 4bitové CRC. Pro 32bitové CRC by byl GP 32bitový). Použitím jiného GP můžeme ovlivnit vhodnost CRC pro určité typy chyb.

Takže:

    GP = 1001

A data, pro která budeme CRC počítat:

    101101110

Nejprve k datům přidáme nakonec tolik nul, kolik je délka GP – resp. kolika bytové je počítané CRC. V našem případě 4:

    1011011100000
             ^^^^

Dále vezmeme GP a různě rotovaný doleva ho xorujeme na data tak dlouho, až je vynulujeme:

    1011011100000   0010011100000   0000001100000
    1001              1001                1001
xor -------------   -------------   -------------
    0010011100000   0000001100000   0000000101000



    0000000101000
           1001
xor -------------
    0000000001100
             ^^^^

Po této operaci si všimněte, že přidané nuly se nám změnily na 1100, což je kýžený výsledek, tedy 4bitové CRC.

Ke zprávě posílané do USA tedy přidáme CRC=1100:

    1011011101100
             ^^^^

V USA pak mají dvě možnosti. První je celkem zřejmá, úplně stejným způsobem, jako jsem popsal výše, spočítají CRC znovu a porovnají, zda se CRC shoduje. Zajímavější postup ověření CRC – v USA spočítají CRC pro celou takto došlou posloupnost znovu a měla by jim vyjít 0:

    1011011101100
    1001
      1001
          1001
           1001
xor -------------
    0000000000000

V tuto chvíli bude rozhodně dobré si rozmyslet, proč tomu tak vlastně je. Momentálně mě nenapadá žádný způsob, jak tuto vlastnost CRC jednoduše vysvětlit, takže to nechám na vás. Úvaha to zase až tak obtížná není a myslím, že byste si to měli být schopni odůvodnit sami. Bude-li nějaký problém, napíšu o tom další článek :-)

Je velmi důležité si uvědomit, že je úplně jedno, v jakém pořadí budete GP xorovat. Algoritmus, který bude ve skutečnosti CRC počítat, to samozřejmě bude dělat postupně. Obecně nám ale nic nebrání to udělat třeba takto:

    1011011101100
    1001
          1001
      1001
           1001
xor -------------
    0000000000000

Jak je to s chybou:

Takže, předpokládejme, že data přišla porušená a že chybový vektor je:

    0000000100000

Zpráva došlá do USA tedy bude:

    1011011101100
    0000000100000
xor -------------
    1011011001100

Jak jsem výše předestřel, je úplně jedno, v jakém pořadí budeme GP xorovat. Proto začneme úplně stejně jako u správné zprávy počítat CRC:

    10110111011000000
    1001
          1001
      1001
           1001
xor -------------
    00000001000000000
    ^^^^^^^^^^^^^

V tuto chvíli samozřejmě ještě nejsme u konce výpočtu. Všimněte si však, že jako mezivýsledek nám vyšel chybový vektor. Budeme-li pokračovat ve výpočtu dál, spočítáme tak vlastně CRC chybového vektoru. Bude-li CRC takového chybového vektoru 0, jsou data považována za správná. Volit GP je tedy potřeba tak, aby pro nejpravděpodobnější chybový vektor bylo CRC nenulové!

Jak volit GP?

Odpověď na tuto otázku jsem hledal docela dlouho a nikde jsem nenašel dostatečně vyčerpávající odpověď. Jisté však je jedno, není to úplně jednoduché a v pozadí toho všeho je jistá dávka matematiky. Obvykle si ale GP nevymýšlíme, ale používáme GP, které již někdo vymyslel za nás. Budete-li hledat na internetu, jistě patřičné hodnoty najdete :-)

Jen velmi krátce příklad: Chcete-li detekovat jednobitovou chybu, je celkem snadné si odůvodnit, že pro to stačí GP s více jak jednou jedničkou.