CRC

Материал из Википедии — свободной энциклопедии

CRC (англ. cyclic redundancy check) — проверка избыточности циклической суммы. Способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её циклического избыточного кода.

С точки зрения математики CRC является типом хэш-функции, используемой для вычисления контрольного кода — небольшого количества бит внутри большого блока данных, например сетевого пакета или блока компьютерного файла, применяемого для обнаружения ошибок при передаче или хранении информации. Результат вычисления CRC добавляется в конец блока данных непосредственно перед началом передачи или сохранения данных на каком-либо носителе информации. Впоследствии он проверяется для подтверждения её целостности. Популярность CRC обусловлена тем, что подобная проверка просто реализуема в двоичном цифровом оборудовании, легко анализируется, и хорошо подходит для обнаружения общих ошибок, вызванных наличием шума в каналах передачи данных.

Принцип CRC основан на использовании свойств двоичного многочлена, в виде которого представляется исходная битовая последовательность блока данных. При этом каждый бит такой последовательности соответствует одному из полиномиальных коэффициэнтов. Так, к примеру, десятичное число 90 (1011010 в двоичной записи) соответствует многочлену следующего вида:

$P (x) = 1 * x 6 + 0 * x 5 + 1 * x 4 + 1 * x 3 + 0 * x 2 + 1 * x 1 + 0 * x 0$

Подобным же образом в виде многочлена может быть представлен любой из блоков обрабатываемых данных.

При вычисления контрольного кода по методу CRC используется свойство поведения многочленов, позволяющее выполнять с ними любые арифметические действия. Контрольный код рассчитывается, как остаток от деления по модулю 2 многочлена полученного из исходной битовой последовательности на некоторый другой заранее определённый многочлен (такой многочлен называется порождающим или примитивным).

$R (x) = P (x) * x r m o d G (x)$

где

$R (x)$ — контрольный код многочлена $P (x)$ .

$P (x)$ — исходный многочлен.

$G (x)$ — порождающий многочлен.

$r$ — степень порождающего многочлена.

Пример программы расчета CRC (CRC-16-IBM) на языке C

/****************************************************************************
Файл crc.c
Параметры функции:
Входные:
    buf   ->  Ссылка на массив типа unsigned char для которого необходимо расчитать CRC сумму.            
    start ->  С какого элемента массива начинать подсчет, обычно = 0.
    cnt   ->  Сколько элементов массива участвует в рассчитываемой CRC сумме
Выходные:
    temp  ->  Возвращает подсчитанную CRC сумму в слове (unsigned int).
COMMENTS:
    Используемый полиномиальный коэффициент - 0xA001.
    This routine calculates the crc high and low byte of a message.
****************************************************************************/

unsigned int crc(unsigned char *buf, int start, int cnt) 
{
    int i, j;
    unsigned int temp, flag;

    temp = 0xFFFF; /* Начальное состояние сдвигового регистра */

    for (i = start; i < cnt; i++)
    {
         temp = temp ^ buf[i];

         for (j = 1; j <= 8; j++)
         {
              flag = temp & 0x0001;
              temp = temp >> 1; /* Сдвиг регистра на 1 позицию */
              if (flag) temp = temp ^ 0xA001;
         }
    }

    return(temp);
}

Алгоритм CRC32 основан на примитивном полиноме EDB88320 (hex)