CRC
A CRC a Cyclic Redundancy Code rövidítése.
Tartalomjegyzék
CRC-12
Polinomja: CRC-12 = x12 + x11 + x3 + x2 + x1 + 1.
CRC-16
Polinomja: CRC-16 = x16 + x15 + x2 + 1.
CRC-32
Polinomja: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1
CRC-CCITT
Polinomja: CRC-CCITT = x16 + x12 + x5 + 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 X0 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.