CRC () е алгоритъм за проверка за грешки при предаване и съхранение на данни чрез използване на контролна сума (контролно число, CRC сума). Устройството източник изчислява CRC сумата на данните, които следва да бъдат проверявани и я изпраща заедно със самите данни. Устройството получател извършва същото изчисление след прочитане на данните и контролната сума и установява тяхната непокътнатост чрез сравняване на записаната CRC сума и новоизчислената CRC сума. Ако двете суми не съвпадат, CRC може да коригира информацията или да поиска наново изпращането ѝ. Hacker's Delight by Henry S. Warren, Jr.
Изчисление Определянето на CRC кода зависи от т.нар. генератор на полиноми. Контролната сума се получава от остатъка от деление на полиноми, където блокът информация е делимо, а CRC полиномът е делител.
В долния пример се кодира съобщение от 14 бита с 3-битов CRC, чийто полином е x3 + x + 1. Полиномът трябва да бъде представен в бинарна форма, така че се поставят коефициенти 1 или 0 пред всеки член. В нашия случай коефициентите са 1x3 + 0x2 + 1x + 1 (1011).
Съобщение за кодиране:
11010011101100
В края на съобщението добавяме толкова нули, колкото бита е дължината на CRC. В нашия CRC е 3-битов:
11010011101100 000 ← добавяме 3 нули 1011 ← делител, коефициентите от полинома
Алгоритъмът използва логическата операция XOR на числата точно над делителя. Числата, които не са над делителя се копират директно на долния ред. След това делителят се премества един бит надясно и процесът се повтаря, докато делителят стигне най-дясната част на съобщението.
11010011101100 000 ← добавяме 3 нули 1011 ← делител, коефициентите от полинома 01100011101100 000 ← резултат (забележете, че само първите 4 бита са променени от операцията XOR) 1011 ← делител 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 ← делителят се премества докато срещне 1 в делимото (нулите се пропускат) 1011 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1
00000000000000 100 ← остатък (3 бита)
Стандарти Име Полином / Приложение Представяне: нормално / обратно / обратно реципрочноCRC-1 (повечето хардуер; познат е и като бит за паритет) 0x1 / 0x1 / 0x1CRC-4-ITU (ITU-T) 0x3 / 0xC / 0x9CRC-5-EPC (Gen 2 RFID) 0x09 / 0x12 / 0x14CRC-5-ITU (ITU-T) 0x15 / 0x15 / 0x1ACRC-5-USB (USB) 0x05 / 0x14 / 0x12CRC-6-ITU (ITU-T) 0x03 / 0x30 / 0x21CRC-7 (системи на телекоми, ITU-T, MMC, SD) 0x09 / 0x48 / 0x44CRC-8-CCITT (ATM HEC), ISDN Header Error Control, Cell Delineation, ITU-T 0x07 / 0xE0 / 0x83CRC-8-Dallas/Maxim (1-Wire шина) 0x31 / 0x8C / 0x98CRC-8 0xD5 / 0xAB / 0xEA Koopman, Philip; Chakravarty, Tridib. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded NetworksCRC-8-SAE J1850 0x1D / 0xB8 / 0x8ECRC-8-WCDMA 0x9B / 0xD9 / 0xCDCRC-10 (ATM, ITU-T) 0x233 / 0x331 / 0x319CRC-11 (FlexRay) 0x385 / 0x50E / 0x5C2CRC-12 (системи на телекоми) 0x80F / 0xF01 / 0xC07CRC-13-BBC 0x1CF5 / 0x15E7 / 0x1E7ACRC-15-CAN 0x4599 / 0x4CD1 / 0x62CCCRC-16-IBM (Bisync, Modbus, USB, ANSI, много други; познат е и като CRC-16 и CRC-16-ANSI) 0x8005 / 0xA001 / 0xC002CRC-16-CCITT (X.25, V.41, HDLC, XMODEM, Bluetooth, SD, много други; познат е и като CRC-CCITT) 0x1021 / 0x8408 / 0x8810CRC-16-T10-DIF (SCSI DIF) 0x8BB7 / 0xEDD1 / 0xC5DBCRC-16-DNP (DNP, IEC 870, M-Bus) 0x3D65 / 0xA6BC / 0x9EB2CRC-16-DECT (безжични телефони) 0x0589 / 0x91A0 / 0x82C4CRC-24 (FlexRay) 0x5D6DCB / 0xD3B6BA / 0xAEB6E5CRC-24-Radix-64 (OpenPGP) 0x864CFB / 0xDF3261 / 0xC3267DCRC-30 (CDMA) 0x2030B9C7 / 0x38E74301 / 0x30185CE3CRC-32 (ISO 3309, ANSI X3.66, FIPS PUB 71, FED-STD-1003, ITU-T V.42, Ethernet, SATA, MPEG-2, Gzip, PKZIP, POSIX cksum, PNG, ZMODEM) 0x04C11DB7 / 0xEDB88320 / 0x82608EDB Koopman, Philip. 32-Bit Cyclic Redundancy Codes for Internet ApplicationsCRC-32C (Castagnoli) (iSCSI & SCTP, G.hn, SSE4.2) 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0CRC-32K (Koopman) 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66BCRC-32Q (авиация; AIXM) 0x814141AB / 0xD5828281 / 0xC0A0A0D5CRC-40-GSM (GSM контролен канал) 0x0004820009 / 0x9000412000 / 0x8002410004CRC-64-ISO (HDLC – ISO 3309, Swiss-Prot/TrEMBL) 0x000000000000001B / 0xD800000000000000 / 0x800000000000000DCRC-64-ECMA-182 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49
Източници
Категория:Информатика