CRC

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

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

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

P(x) = 1 * x6 + 0 * x5 + 1 * x4 + 1 * x3 + 0 * x2 + 1 * x1 + 0 * x0

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

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

R(x) = P(x) * xrmodG(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    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;
              if (flag) temp=temp ^ 0xA001;
         }
    }

    return(temp);
}


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

См. также

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home