CRC

A CRC a Cyclic Redundancy Code rövidítése.

CRC-12

Polinomja: CRC-12 = x¹² + x¹¹ + x³ + x² + x¹ + 1.

CRC-16

Polinomja: CRC-16 = x¹⁶ + x¹⁵ + x² + 1.

CRC-32

Polinomja: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x¹ + 1

CRC-CCITT

Polinomja: CRC-CCITT = x¹⁶ + x¹² + x⁵ + 1.

Rádióamatőr alkalmazása:

• AX.25 esetén használatos hibadetektáló ellenörző kód.

Hardver implementáció

A fenti ábrán 1 bites tárolók (latch-ek) vannak egymás után kötve, így az adatbit minden egyes órajel hatására eggyel balra lép. A bit a bal oldalon érkezik, és 1 bites XOR áramkörön keresztül kerül az X₀ tároló bemenetére. A jel a megfelelő tároló bemenet előtt szintén XOR kapuba van csatlakoztatva.

Amikor beérkezett az utolsó bit is, a tárolók kimeneteit kell kiolvasni, és megvan a CRC. Természetesen az új számítás előtt a kezdőértékre vissza kell állítani a tárolókat (reset).

Algoritmikus implementáció

<HIGHLIGHTSYNTAX language="c">/* Alábbi példa egy CRC-CCITT kiszámítására alkalmas algoritmust ismertet */ const unsigned short crc_poly=0x0810; // binaris erteke: 0000 1000 0001 0000 unsigned short crc;

void init_crc() {

   crc=0xffff

}

/* 1 byte hozzáadása a CRC polinomhoz */ void calc_crc(unsigned char x) {

   int k, i;
   for (k=0; k<8; k++) {
       i = (x >> 7) & 1;  // MSB
       if (crc & 0x8000) crc = (crc ^ crc_poly) << 1 + (i ^ 1);
       else crc = (crc ^ crc_poly) << 1 + i;
       crc =^ 0xffff;
       x << 1;
   }

} </HIGHLIGHTSYNTAX>

Mint látszik, elég nehézkes számítás a CRC. A gyorsítás érdekében vagy hardveres gyorsítást alkalmaznak (visszacsatolt shift regiszter) vagy keresőtáblás megoldást.

Keresőtáblás algoritmus gyorsítás

Alább bemutatásra kerülő megoldás körülbelül 10-szer gyorsabb, mint a fennt bemutatott bitről bitre számoló megoldás. Ezért szoftveres megoldás esetén szinte kivétel nélkül ezzel a keresőtáblás megoldással találkozunk.

<HIGHLIGHTSYNTAX language="c">/* A keresőtábla 256 db 16 bites értéket tartalmaz. Alább egy teljes csomag keresőtáblás CRC számító algoritmusa látható */ unsigned short crc_ccitt(u16 crc, u8 const *buffer, size_t len) {

       while (len--) crc = (crc >> 8) ^ crc_ccitt_table[(crc ^ *buffer++) & 0xff];
       return crc;

} </HIGHLIGHTSYNTAX>

A keresőtáblázatot a Linux kernelforrás ( http://www.kernel.org ) linux-2.6.xx/lib/crc-ccitt.c állományából lehet kimásolni.