Преглед на кода на CRC

'''CRC''' ({{lang|en|'''C'''yclic '''R'''edundancy '''C'''heck – проверка на цикличния остатък}}) е [[алгоритъм]] за проверка за грешки при предаване и съхранение на данни чрез използване на [[контролна сума]] (''контролно число'', ''CRC сума''). Устройството източник изчислява CRC сумата на данните, които следва да бъдат проверявани и я изпраща заедно със самите данни. Устройството получател извършва същото изчисление след прочитане на данните и контролната сума и установява тяхната непокътнатост чрез сравняване на записаната CRC сума и новоизчислената CRC сума. Ако двете суми не съвпадат, CRC може да коригира информацията или да поиска наново изпращането ѝ.<ref>{{икона|en}} [http://www.hackersdelight.org/crc.pdf Hacker's Delight by Henry S. Warren, Jr.] {{Webarchive|url=https://web.archive.org/web/20150503014404/http://www.hackersdelight.org/crc.pdf |date=2015-05-03 }}</ref>

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

В долния пример се кодира съобщение от 14 бита с 3-битов CRC, чийто полином е x<sup>3</sup> + x + 1. Полиномът трябва да бъде представен в [[Бинарен код|бинарна форма]], така че се поставят коефициенти 1 или 0 пред всеки член. В нашия случай коефициентите са 1x<sup>3</sup> + 0x<sup>2</sup> + 1x + 1 (1011).

Съобщение за кодиране:

<pre>
11010011101100
</pre>

В края на съобщението добавяме толкова нули, колкото бита е дължината на CRC. В нашия CRC е 3-битов:

<pre>
11010011101100 000 ← добавяме 3 нули
1011               ← делител, коефициентите от полинома
</pre>

Алгоритъмът използва логическата операция [[XOR]] на числата точно над делителя. Числата, които не са над делителя се копират директно на долния ред. След това делителят се премества един бит надясно и процесът се повтаря, докато делителят стигне най-дясната част на съобщението.

<pre>
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 бита)
</pre>

== Стандарти ==
{|class="wikitable" style="font-size: auto; width: 80%;"
! Име || Полином / Приложение || Представяне: нормално / обратно / обратно реципрочно
|-
|CRC-1 || <math>x + 1</math> (повечето [[хардуер]]; познат е и като ''[[бит за паритет]]'') || 0x1 / 0x1 / 0x1
|-
|CRC-4-ITU || <math>x^4 + x + 1</math> ([[ITU-T]]) || 0x3 / 0xC / 0x9
|-
|CRC-5-EPC || <math>x^5 + x^3 + 1</math> ([[Радиочестотна идентификация|Gen 2 RFID]]) || 0x09 / 0x12 / 0x14
|-
|CRC-5-ITU || <math>x^5 + x^4 + x^2 + 1</math> (ITU-T) || 0x15 / 0x15 / 0x1A
|-
|CRC-5-USB || <math>x^5 + x^2 + 1</math> ([[USB]]) || 0x05 / 0x14 / 0x12
|-
|CRC-6-ITU || <math>x^6 + x + 1</math> (ITU-T) || 0x03 / 0x30 / 0x21
|-
|CRC-7 || <math>x^7 + x^3 + 1</math> (системи на [[Телекомуникационни оператори|телекоми]], ITU-T, [[MMC]], [[Secure Digital|SD]]) || 0x09 / 0x48 / 0x44
|-
|CRC-8-[[CCITT]] || <math>x^8 + x^2 + x + 1</math> ([[Асинхронен режим на пренос|ATM]] [[Header Error Correction|HEC]]), [[ISDN]] [[Header Error Control]], [[Cell Delineation]], ITU-T || 0x07 / 0xE0 / 0x83
|-
|CRC-8-[[Dallas Semiconductor|Dallas]]/[[Maxim Integrated Products|Maxim]] || <math>x^8 + x^5 + x^4 + 1</math> ([[1-Wire]] [[Шина (компютри))|шина]]) || 0x31 / 0x8C / 0x98
|-
|CRC-8 || <math>x^8 + x^7 + x^6 + x^4 + x^2 + 1</math> || 0xD5 / 0xAB / 0xEA<ref name="koop04">{{икона|en}} [https://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf Koopman, Philip; Chakravarty, Tridib. ''Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks'']</ref>
|-
|CRC-8-[[SAE J1850]] || <math>x^8 + x^4 + x^3 + x^2 + 1</math> || 0x1D / 0xB8 / 0x8E
|-
|CRC-8-[[W-CDMA (UMTS)|WCDMA]] || <math>x^8 + x^7 + x^4 + x^3 + x + 1</math> || 0x9B / 0xD9 / 0xCD<ref name="koop04"/>
|-
|CRC-10 || <math>x^{10} + x^9 + x^5 + x^4 + x + 1</math> (ATM, ITU-T) || 0x233 / 0x331 / 0x319
|-
|CRC-11 || <math>x^{11} + x^9 + x^8 + x^7 + x^2 + 1</math> ([[FlexRay]]) || 0x385 / 0x50E / 0x5C2
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math> (системи на телекоми) || 0x80F / 0xF01 / 0xC07<ref name="koop04"/>
|-
|CRC-13-BBC || <math>x^{13} + x^{12} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^2 + 1</math> || 0x1CF5 / 0x15E7 / 0x1E7A
|-
|CRC-15-[[Controller Area Network|CAN]]|| <math>x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1 </math> || 0x4599 / 0x4CD1 / 0x62CC
|-
|CRC-16-[[IBM]] || <math>x^{16} + x^{15} + x^2 + 1</math> ([[Binary Synchronous Communications|Bisync]], [[Modbus]], USB, [[ANSI]], много други; познат е и като ''CRC-16'' и ''CRC-16-ANSI'') || 0x8005 / 0xA001 / 0xC002
|-
|CRC-16-CCITT || <math>x^{16} + x^{12} + x^5 + 1</math> ([[X.25]], [[V.41]], [[HDLC]], [[XMODEM]], [[Bluetooth]], [[Secure Digital|SD]], много други; познат е и като ''CRC-CCITT'') || 0x1021 / 0x8408 / 0x8810<ref name="koop04"/>
|-
|CRC-16-[[International Committee for Information Technology Standards|T10]]-[[Data Integrity Field|DIF]] || <math>x^{16} + x^{15} + x^{11} + x^{9} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math> ([[SCSI]] DIF) || 0x8BB7 / 0xEDD1 / 0xC5DB
|-
|CRC-16-[[DNP3|DNP]] || <math>x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1</math> (DNP, [[IEC 60870-5|IEC 870]], [[Meter-Bus|M-Bus]]) || 0x3D65 / 0xA6BC / 0x9EB2
|-
|CRC-16-[[Digital Enhanced Cordless Telecommunications|DECT]] || <math>x^{16} + x^{10} + x^8 + x^7 + x^3 + 1</math> (безжични телефони) || 0x0589 / 0x91A0 / 0x82C4
|-
|CRC-24 || <math>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</math> (FlexRay) || 0x5D6DCB / 0xD3B6BA / 0xAEB6E5
|-
|CRC-24-[[Radix-64]] || <math> 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 </math> ([[OpenPGP]]) || 0x864CFB / 0xDF3261 / 0xC3267D
|-
|CRC-30 || <math>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 </math> ([[CDMA]]) || 0x2030B9C7 / 0x38E74301 / 0x30185CE3
|-
|CRC-32 || <math>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</math> ([[ISO]] 3309, [[ANSI]] X3.66, [[Federal Information Processing Standard|FIPS]] PUB 71, FED-STD-1003, [[ITU-T]] [[V.42]], [[Ethernet]], [[SATA]], [[MPEG-2]], [[Gzip]], [[PKZIP]], [[POSIX]] [[cksum]], [[Portable Network Graphics|PNG]], [[ZMODEM]])
|| 0x04C11DB7 / 0xEDB88320 / 0x82608EDB<ref name="koop02">{{икона|en}} [https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf Koopman, Philip. ''32-Bit Cyclic Redundancy Codes for Internet Applications'']</ref>
|-
|CRC-32C (Castagnoli) || <math>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</math> ([[iSCSI]] & [[SCTP]], [[G.hn]], [[SSE4.2]]) || 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0<ref name="koop02"/>
|-
|CRC-32K (Koopman) || <math>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</math> || 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B<ref name="koop02"/>
|-
|CRC-32Q || <math>x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^{5} + x^{3} + x + 1</math> (авиация; [[AIXM]]) || 0x814141AB / 0xD5828281 / 0xC0A0A0D5
|-
|CRC-40-[[GSM]] || <math>x^{40} + x^{26} + x^{23} + x^{17} + x^3 + 1</math> (GSM контролен канал) || 0x0004820009 / 0x9000412000 / 0x8002410004
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math> ([[High-Level Data Link Control|HDLC – ISO 3309]], [[UniProt|Swiss-Prot]]/[[TrEMBL]]) || 0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
|-
|CRC-64-[[Ecma International|ECMA]]-182 || <math>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} +</math><math>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</math> || 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49
|-
|}

== Източници ==
<references/>

[[Категория:Информатика]]