CRC

CRC (на английски: Cyclic Redundancy Check – проверка на цикличния остатък) е алгоритъм за проверка за грешки при предаване и съхранение на данни чрез използване на контролна сума (контролно число, CRC сума). Устройството източник изчислява CRC сумата на данните, които следва да бъдат проверявани и я изпраща заедно със самите данни. Устройството получател извършва същото изчисление след прочитане на данните и контролната сума и установява тяхната непокътнатост чрез сравняване на записаната CRC сума и новоизчислената CRC сума. Ако двете суми не съвпадат, CRC може да коригира информацията или да поиска наново изпращането ѝ.^[1]

Изчисление

Определянето на CRC кода зависи от т.нар. генератор на полиноми. Контролната сума се получава от остатъка от деление на полиноми, където блокът информация е делимо, а CRC полиномът е делител.

В долния пример се кодира съобщение от 14 бита с 3-битов CRC, чийто полином е x³ + x + 1. Полиномът трябва да бъде представен в бинарна форма, така че се поставят коефициенти 1 или 0 пред всеки член. В нашия случай коефициентите са 1x³ + 0x² + 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	$x+1$ (повечето хардуер; познат е и като бит за паритет)	0x1 / 0x1 / 0x1
CRC-4-ITU	$x^{4}+x+1$ (ITU-T)	0x3 / 0xC / 0x9
CRC-5-EPC	$x^{5}+x^{3}+1$ (Gen 2 RFID)	0x09 / 0x12 / 0x14
CRC-5-ITU	$x^{5}+x^{4}+x^{2}+1$ (ITU-T)	0x15 / 0x15 / 0x1A
CRC-5-USB	$x^{5}+x^{2}+1$ (USB)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^{6}+x+1$ (ITU-T)	0x03 / 0x30 / 0x21
CRC-7	$x^{7}+x^{3}+1$ (системи на телекоми, ITU-T, MMC, SD)	0x09 / 0x48 / 0x44
CRC-8-CCITT	$x^{8}+x^{2}+x+1$ (ATM HEC), ISDN Header Error Control, Cell Delineation, ITU-T	0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim	$x^{8}+x^{5}+x^{4}+1$ (1-Wire шина)	0x31 / 0x8C / 0x98
CRC-8	$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$	0xD5 / 0xAB / 0xEA^[2]
CRC-8-SAE J1850	$x^{8}+x^{4}+x^{3}+x^{2}+1$	0x1D / 0xB8 / 0x8E
CRC-8-WCDMA	$x^{8}+x^{7}+x^{4}+x^{3}+x+1$	0x9B / 0xD9 / 0xCD^[2]
CRC-10	$x^{10}+x^{9}+x^{5}+x^{4}+x+1$ (ATM, ITU-T)	0x233 / 0x331 / 0x319
CRC-11	$x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1$ (FlexRay)	0x385 / 0x50E / 0x5C2
CRC-12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$ (системи на телекоми)	0x80F / 0xF01 / 0xC07^[2]
CRC-13-BBC	$x^{13}+x^{12}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1$	0x1CF5 / 0x15E7 / 0x1E7A
CRC-15-CAN	$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1$	0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM	$x^{16}+x^{15}+x^{2}+1$ (Bisync, Modbus, USB, ANSI, много други; познат е и като CRC-16 и CRC-16-ANSI)	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16}+x^{12}+x^{5}+1$ (X.25, V.41, HDLC, XMODEM, Bluetooth, SD, много други; познат е и като CRC-CCITT)	0x1021 / 0x8408 / 0x8810^[2]
CRC-16-T10-DIF	$x^{16}+x^{15}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$ (SCSI DIF)	0x8BB7 / 0xEDD1 / 0xC5DB
CRC-16-DNP	$x^{16}+x^{13}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{2}+1$ (DNP, IEC 870, M-Bus)	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-DECT	$x^{16}+x^{10}+x^{8}+x^{7}+x^{3}+1$ (безжични телефони)	0x0589 / 0x91A0 / 0x82C4
CRC-24	$x^{24}+x^{22}+x^{20}+x^{19}+x^{18}+x^{16}+x^{14}+x^{13}+x^{11}+x^{10}+x^{8}+x^{7}+x^{6}+x^{3}+x+1$ (FlexRay)	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64	$x^{24}+x^{23}+x^{18}+x^{17}+x^{14}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$ (OpenPGP)	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	$x^{30}+x^{29}+x^{21}+x^{20}+x^{15}+x^{13}+x^{12}+x^{11}+x^{8}+x^{7}+x^{6}+x^{2}+x+1$ (CDMA)	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$ (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^[3]
CRC-32C (Castagnoli)	$x^{32}+x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+1$ (iSCSI & SCTP, G.hn, SSE4.2)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0^[3]
CRC-32K (Koopman)	$x^{32}+x^{30}+x^{29}+x^{28}+x^{26}+x^{20}+x^{19}+x^{17}+x^{16}+x^{15}+x^{11}+x^{10}+x^{7}+x^{6}+x^{4}+x^{2}+x+1$	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B^[3]
CRC-32Q	$x^{32}+x^{31}+x^{24}+x^{22}+x^{16}+x^{14}+x^{8}+x^{7}+x^{5}+x^{3}+x+1$ (авиация; AIXM)	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-40-GSM	$x^{40}+x^{26}+x^{23}+x^{17}+x^{3}+1$ (GSM контролен канал)	0x0004820009 / 0x9000412000 / 0x8002410004
CRC-64-ISO	$x^{64}+x^{4}+x^{3}+x+1$ (HDLC – ISO 3309, Swiss-Prot/TrEMBL)	0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA-182	$x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+$ $x^{32}+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21}+x^{19}+x^{17}+x^{13}+x^{12}+x^{10}+x^{9}+x^{7}+x^{4}+x+1$	0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49