- Циклический избыточный код
-
Циклический избыточный код (англ. Cyclic redundancy check, CRC[1]) — алгоритм вычисления контрольной суммы, предназначенный для проверки целостности данных[2]. CRC является практическим приложением помехоустойчивого кодирования, основанном на определенных математических свойствах циклического кода.
Содержание
Введение
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.Понятие циклические коды достаточно широкое[3]. В англоязычной литературе CRC расшифровывается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check[4]. Под первой расшифровкой понимают математический феномен циклических кодов, под второй — конкретное применение этого феномена как хэш-функции.
Помехоустойчивое кодирование
Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).
Но далеко не везде от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.
Контрольная сумма
В самом общем своем виде контрольная сумма представляет собой некоторое значение, построенное по определенной схеме на основе кодируемого сообщения. Проверочная информация при систематическом кодировании дописывается в конец сообщения — после полезных данных. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.
При передаче пакетов по реальному каналу, разумеется, могут возникнуть искажения исходной информации вследствие разных внешних воздействий: электрических наводок, плохих погодных условий и многих других. Сущность методики в том, что при хороших характеристиках хэш-функции в подавляющем числе случаев ошибка в сообщении приведет к изменению вычисленного на приеме значения CRC. Если исходная и вычисленная суммы не равны между собой, принимается решение о недостоверности принятых данных, и можно запросить повторную передачу пакета.
Математическое описание
Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем . Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.
Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:
Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .
Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):
где
- — многочлен, представляющий значение CRC.
- — многочлен, коэффициенты которого представляют входные данные.
- — порождающий многочлен.
- — степень порождающего многочлена.
Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.
При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.
Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число коллизий, простота вычисления). В статье приведены некоторые из них, а также соответствующие реализации на языке Си.
Вычисление CRC
Параметры алгоритма
Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic reduntancy code; многие из них указаны в конце статьи.
Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.
И последний параметр, важный при описании определенной методики — начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC, если данная модификация методики не имеет специфических особенностей, таких, как обратный порядок обработки битов.
Описание процедуры
Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.
Наиболее используемые и стандартизованные полиномы
В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу.[1][5]
Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check reduntancy code .
При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа ученых занималась исследованием порождающих многочленов разрядности до 16,[1] 24 и 32 бит,[6][7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния.[7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.
Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга[8]. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью.[7] К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.
Ниже в таблице перечислены наиболее распространенные многочлены — генераторы CRC.На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.
Название Полином Представления:[9] нормальное / реверсированное / реверсированное от обратного CRC-1 (используется в аппаратном контроле ошибок; также известен как бит чётности) 0x1 / 0x1 / 0x1 CRC-4-ITU (ITU G.704[10]) 0x3 / 0xC / 0x9 CRC-5-EPC (Gen 2 RFID[11]) 0x09 / 0x12 / 0x14 CRC-5-ITU (ITU G.704[12]) 0x15 / 0x15 / 0x1A CRC-5-USB (USB token packets) 0x05 / 0x14 / 0x12 CRC-6-ITU (ITU G.704[13]) 0x03 / 0x30 / 0x21 CRC-7 (системы телекоммуникации, ITU-T G.707[14], ITU-T G.832[15], MMC, SD) 0x09 / 0x48 / 0x44 CRC-8-CCITT (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99) 0x07 / 0xE0 / 0x83 CRC-8-Dallas/Maxim (1-Wire bus) 0x31 / 0x8C / 0x98 CRC-8 (ETSI EN 302 307[16], 5.1.4) 0xD5 / 0xAB / 0xEA[1] CRC-8-SAE J1850 0x1D / 0xB8 / 0x8E CRC-10 0x233 / 0x331 / 0x319 CRC-11 (FlexRay[17]) 0x385 / 0x50E / 0x5C2 CRC-12 (системы телекоммуникации[18][19]) 0x80F / 0xF01 / 0xC07 CRC-15-CAN 0x4599 / 0x4CD1 / 0x62CC CRC-16-IBM (Bisync, Modbus, USB, ANSI X3.28[20], многие другие; также известен как CRC-16 и CRC-16-ANSI) 0x8005 / 0xA001 / 0xC002 CRC-16-CCITT (X.25, HDLC, XMODEM, Bluetooth, SD и др.) 0x1021 / 0x8408 / 0x8810[1] CRC-16-T10-DIF (SCSI DIF) 0x8BB7[21] / 0xEDD1 / 0xC5DB CRC-16-DNP (DNP, IEC 870, M-Bus) 0x3D65 / 0xA6BC / 0x9EB2 CRC-16-Fletcher Not a CRC; see Fletcher's checksum Used in Adler-32 A & B CRCs CRC-24 (FlexRay[17]) 0x5D6DCB / 0xD3B6BA / 0xAEB6E5 CRC-24-Radix-64 (OpenPGP) 0x864CFB / 0xDF3261 / 0xC3267D CRC-30 (CDMA) 0x2030B9C7 / 0x38E74301 / 0x30185CE3 CRC-32-Adler Not a CRC; see Adler-32 See Adler-32 CRC-32-IEEE 802.3 (V.42, MPEG-2, PNG[22], POSIX cksum) 0x04C11DB7 / 0xEDB88320 / 0x82608EDB[7] CRC-32C (Castagnoli) (iSCSI, G.hn payload) 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0[7] CRC-32K (Koopman) 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B[7] CRC-32Q (aviation; AIXM[23]) 0x814141AB / 0xD5828281 / 0xC0A0A0D5 CRC-64-ISO (HDLC — ISO 3309) 0x000000000000001B / 0xD800000000000000 / 0x800000000000000D CRC-64-ECMA-182 [24] 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49 Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.
Попытки описания алгоритмов CRC
Одной из самых известных является методика Ross N. Williams[25]. В ней используются следующие параметры:
- Название алгоритма (name);
- Степень порождающего контрольную сумму многочлена(width);
- Сам производящий полином (poly). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен в данной нотации будет записан числом . Для удобства полученное двоичное представление записывают в шестнадцатеричной форме. Для нашего случая оно будет равно или 0x11;
- Стартовые данные (init), то есть значения регистров на момент начала вычислений;
- Флаг (RefIn), указывающий на начало и направление вычислений. Существует два варианта: начиная со старшего значащего бита (MSB-first), или с младшего (LSB-first);
- Флаг (RefOut), определяющий, инвертируется ли данные регистра при входе на элемент XOR;
- Число (XorOut), с которым складывается по модулю 2 полученный результат;
- Значение CRC (check) для строки «123456789» .
Примеры спецификаций некоторых алгоритмов CRC
Name : CRC 16 Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : BB3D
Name : CRC 16/IBM Width : 16 Poly : 8005 Init : FFFF RefIn : True RefOut : True XorOut : 0000 Check : 4B37
Name : CRC 32 Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : CBF43926
Name : CRC 16/CITT Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : 0000
Name : XMODEM Width : 16 Poly : 8408 Init : 0000 RefIn : True RefOut : True XorOut : 0000
Name : ARC Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000
Примеры программ для вычисления CRC на языке C
Некоторые из этих алгоритмов заимствованы у Ross Williams[26].
CRC-4
Пример программы, генерирующей массив, предназначенный для табличного способа вычисления CRC4 на языке C#/* Name : CRC-4 Poly : 0x13 x4 + x + 1 rtbOutput : объект класса RichTextBox */ using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace CRC_Table { public partial class Form1 : Form { const int Polinom = 0x13; public Form1() { InitializeComponent(); } private void btnGenerate_Click(object sender, EventArgs e) { rtbOutput.Text = "const int CRC4_Table[256] = {\n"; int local = 0; for (int i = 0; i < 256; i++) { rtbOutput.Text += (local == 0) ? "\t\t" : ""; rtbOutput.Text += CRCTableCell(i) + ", "; rtbOutput.Text += (local == 0xf) ? "\n" : ""; local++; local &= 0xf; } rtbOutput.Text += "};"; } string CRCTableCell(int value) { int r; r = (value << 8) & 0xFF00; int shifted_Polinom = Polinom << (3+8); // 3 сдвига для дополнения полинома до размера 1 байта, 8 сдв. для заполнения нулями for(byte j=0; j<8; j++) { if ((r & (1 << 15)) == 0x8000) { r ^= shifted_Polinom; r = (r << 1); } else r = r << 1; } r = r >> 8; return String.Format("0x{0:X2}", r); } } }
Итоговый массив для табличного (быстрого) расчёта CRC4 (результат работы вышеприведенного кода)CRC-8
Пример программы расчёта CRC8 на языке Си/* Name : CRC-8 Poly : 0x31 x^8 + x^5 + x^4 + 1 Init : 0xFF Revert: false XorOut: 0x00 Check : 0xF7 ("123456789") MaxLen: 15 байт(127 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */ unsigned char Crc8(unsigned char *pcBlock, unsigned int len) { unsigned char crc = 0xFF; unsigned int i; while (len--) { crc ^= *pcBlock++; for (i = 0; i < 8; i++) crc = crc & 0x80 ? (crc << 1) ^ 0x31 : crc << 1; } return crc; }
Пример программы табличного (быстрого) расчёта CRC8 на языке Си/* Name : CRC-8 Poly : 0x31 x^8 + x^5 + x^4 + 1 Init : 0xFF Revert: false XorOut: 0x00 Check : 0xF7 ("123456789") MaxLen: 15 байт (127 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */
CRC-16
CRC-CCITT отличается от классического CRC-16, так как использует другой полином и порядок данных.
Оптимизированный расчёт CRC-16 CCITT на языке Си, полином 0x8408/* Name : CRC-16 CCITT Poly : 0x8408 Init : 0xFFFF Revert: false XorOut: 0x0000 Check : 0x6F91 ("123456789") MaxLen: 4095 байт (32767 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */ unsigned short crc_ccitt_update (unsigned short crc, unsigned char data){ unsigned short t; data ^= crc&255; data ^= data << 4; t = (((unsigned short)data << 8) | ((crc>>8)&255)); t^=(unsigned char)(data >> 4); t^= ((unsigned short)data << 3); return t; }
Пример программы расчёта CRC-16 CCITT на языке Си/* Name : CRC-16 CCITT Poly : 0x1021 x^16 + x^12 + x^5 + 1 Init : 0xFFFF Revert: false XorOut: 0x0000 Check : 0x29B1 ("123456789") MaxLen: 4095 байт (32767 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */ unsigned short Crc16(unsigned char *pcBlock, unsigned short len) { unsigned short crc = 0xFFFF; unsigned char i; while (len--) { crc ^= *pcBlock++ << 8; for (i = 0; i < 8; i++) crc = crc & 0x8000 ? (crc << 1) ^ 0x1021 : crc << 1; } return crc; }
Пример программы табличного (быстрого) расчёта CRC-16 CCITT на языке Си/* Name : CRC-16 CCITT Poly : 0x1021 x^16 + x^12 + x^5 + 1 Init : 0xFFFF Revert: false XorOut: 0x0000 Check : 0x29B1 ("123456789") MaxLen: 4095 байт (32767 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */
Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си/* Name : CRC-16 Poly : 0x8005 x^16 + x^15 + x^2 + 1 Init : 0xFFFF Revert: true XorOut: 0x0000 Check : 0x4B37 ("123456789") MaxLen: 4095 байт (32767 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */
Пример программы расчёта CRC-16 CCITT на языке PHP/* Name : CRC-16 CCITT Poly (default) : 0x1021 x^16 + x^12 + x^5 + 1 Init (default) : 0xFFFF XorOut (default): 0x0000 Revert : false Check : 0x29B1 ("123456789") MaxLen : 4095 байт (32767 бит) - обнаружение одинарных, двойных, тройных и всех нечетных ошибок */ function crc16($sStr, $aParams = array()){ //-- устанавливаем значения по умолчанию у незаданных параметров $aDefaults = array( "polynome" => 0x1021, "init" => 0xFFFF, "xor_out" => 0, ); foreach ($aDefaults as $key => $val){ if (!isset($aParams[$key])){ $aParams[$key] = $val; } } //-- инициализируем переменные $sStr .= ""; $crc = $aParams['init']; $len = strlen($sStr); $i = 0; //-- считаем while ($len--){ $crc ^= ord($sStr[$i++]) << 8; $crc &= 0xffff; for ($j = 0; $j < 8; $j++){ $crc = ($crc & 0x8000) ? ($crc << 1) ^ $aParams['polynome'] : $crc << 1; $crc &= 0xffff; } } $crc ^= $aParams['xor_out']; return $crc; }
Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке AVR assembler; Name : CRC-16 ; Poly : 0x8005 x^16 + x^15 + x^2 + 1 ; Init : 0xFFFF ; Revert: true ; XorOut: 0x0000 ; Check : 0x4B37 ("123456789"
CRC-32
Алгоритм CRC32 основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7).
Пример программы расчёта CRC-32 на языке Си#include <stddef.h> #include <stdint.h> /* Name : CRC-32 Poly : 0x04C11DB7 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 Init : 0xFFFFFFFF Revert: true XorOut: 0xFFFFFFFF Check : 0xCBF43926 ("123456789") MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение одинарных, двойных, пакетных и всех нечетных ошибок */ uint_least32_t Crc32(unsigned char *buf, size_t len) { uint_least32_t crc_table[256]; uint_least32_t crc; int i, j; for (i = 0; i < 256; i++) { crc = i; for (j = 0; j < 8; j++) crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1; crc_table[i] = crc; }; crc = 0xFFFFFFFFUL; while (len--) crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8); return crc ^ 0xFFFFFFFFUL; }
Пример программы табличного (быстрого) расчёта CRC-32 на языке Си#include <stddef.h> #include <stdint.h> /* Name : CRC-32 Poly : 0x04C11DB7 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 Init : 0xFFFFFFFF Revert: true XorOut: 0xFFFFFFFF Check : 0xCBF43926 ("123456789") MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение одинарных, двойных, пакетных и всех нечетных ошибок */
Примечания
- ↑ 1 2 3 4 5 Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks (2004). Архивировано из первоисточника 23 августа 2011. Проверено ???.
- ↑ Интернет-Университет Информационных Технологий. Лекция: Организация беспроводных сетей
- ↑ Интернет-Университет Информационных Технологий. Лекция: Алгоритмы сети Ethernet/Fast Ethernet
- ↑ Walma, M.; Pipelined Cyclic Redundancy Check (CRC) Calculation
- ↑ Greg Cook. Catalogue of parameterised CRC algorithms (29 апреля 2009). Архивировано из первоисточника 23 августа 2011. Проверено ???.
- ↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits // IEEE Transactions on Communications. — июнь 1993. — Т. 41. — № 6. — С. 883. — DOI:10.1109/26.231911
- ↑ 1 2 3 4 5 6 P. Koopman. 32-Bit Cyclic Redundancy Codes for Internet Applications // The International Conference on Dependable Systems and Networks. — июнь 2002. — С. 459. — DOI:10.1109/DSN.2002.1028931
- ↑ Brayer, K; Hammond, J L Jr. (December 1975). "Evaluation of error detection polynomial performance on the AUTOVON channel" in National Telecommunications Conference, New Orleans, La. Conference Record 1: 8-21 to 8-25, New York: Institute of Electrical and Electronics Engineers.
- ↑ В представлениях опущен старший бит.
- ↑ G.704, p. 12
- ↑ Class-1 Generation-2 UHF RFID Protocol version 1.2.0. — 23 октября 2008. — С. 35.
- ↑ G.704, p. 9
- ↑ G.704, p. 3
- ↑ G.707 : Network node interface for the synchronous digital hierarchy (SDH)
- ↑ G.832 : Transport of SDH elements on PDH networks — Frame and multiplexing structures
- ↑ EN 302 307. Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)
- ↑ 1 2 FlexRay Protocol Specification version 2.1 Revision A. — 22 декабря 2005. — С. 93.
- ↑ A. Perez, Wismer, Becker. Byte-Wise CRC Calculations // IEEE Micro. — 1983. — Т. 3. — № 3. — С. 40—50. — DOI:10.1109/MM.1983.291120
- ↑ T. V. Ramabadran, S. S. Gaitonde. A tutorial on CRC computations // IEEE Micro. — 1988. — Т. 8. — № 4. — С. 62—75. — DOI:10.1109/40.7773
- ↑ http://www.incits.org/press/1997/pr97020.htm
- ↑ Pat Thaler. 16-bit CRC polynomial selection. INCITS T10 (28 августа 2003). Архивировано из первоисточника 23 августа 2011. Проверено ???.
- ↑ Thomas Boutell, Glenn Randers-Pehrson и др. PNG (Portable Network Graphics) Specification, Version 1.2 (14 июля 1998). Архивировано из первоисточника 23 августа 2011. Проверено ???.
- ↑ AIXM Primer version 4.5. European Organisation for the Safety of Air Navigation (20 марта 2006). Архивировано из первоисточника 23 августа 2011. Проверено ???.
- ↑ ECMA-182 p. 51
- ↑ Ross N. Williams. CRC Rocksoft (1993). Архивировано из первоисточника 15 мая 2012.
- ↑ Ross N.Williams. Элементарное руководство по CRC-алгоритмам обнаружения ошибок. (1993). Архивировано из первоисточника 16 декабря 2012.
Литература
- Генри С. Уоррен, мл. Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4
Ссылки
- Элементарное руководство по CRC алгоритмам обнаружения ошибок
- CRC, и как его восстановить
- Восстановление CRC
- CRC-калькулятор
- Генератор CRC-функций на языках VHDL и Verilog
- Ross N. Williams/Anarchriz. Всё о CRC32 // Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок
- Ross N. Williams. A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS (англ.)
Эта статья выставлена на рецензию.
Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.Хеш-функции Общего назначения Криптографические JH • HAVAL • Keccak (SHA-3) • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94
Категории:- Хеш-функции
- Обнаружение и устранение ошибок
Wikimedia Foundation. 2010.