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

Алгоритм CRC

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

Каждой конечной последовательности битов взаимооднозначно сопоставляется двоичный многочлен , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей N равно , что совпадает с числом всех двоичных последовательностей длины N.

Значение CRC с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

где

— многочлен, представляющий значение CRC.

— многочлен, коэффициенты которого представляют входные данные.

— порождающий многочлен.

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

Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком степень многочлена-остатка строго меньше степени многочлена-делителя, то есть при делении на многочлен G(x) степени N можно получить 2^N различных остатков от деления. При «правильном» выборе порождающего многочлена G(x), остатки от деления на него будут обладать нужными свойствами хеширования — хорошей перемешиваемостью и быстрым алгоритмом вычисления. Второе обеспечивается тем, что степень порождающего многочлена обычно пропорциональна длине байта или машинного слова (например 8, 16 или 32).

Операция деления на примитивный полином также эквивалентна следующей схеме:

Пусть выбран примитивный полином, задающий цикл де Брейна 0010111001011100… и блок данных 0111110, построена таблица, верхняя строка заполнена блоком данных, а нижние строки — смещения на 0,1,2 бит цикла де Брейна

Тогда контрольная сумма будет равна операции XOR тех столбцов, над которыми в верхней строке расположена 1. В этом случае, 010 xor 101 xor 011 xor 111 xor 110 = 101 (CRC).

Ниже представлены реализации получения некоторых CRC для многочленов степени 8 (CRC-8), 16 (CRC-16) и 32 (CRC-32).

Формализованный алгоритм расчёта CRC16

Для получения контрольной суммы, необходимо сгенерировать полином. Основное требование к полиному: его степень должна быть равна длине контрольной суммы в битах. При этом старший бит полинома обязательно должен быть равен «1».

Из файла берется первое слово. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига (умножения) теряется старый старший бит, а младший бит освобождается (обнуляется). На место младшего бита загружается очередной бит из файла. Операция повторяется до тех пор, пока не загрузится последний бит файла.

После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

CRC-4

/*
  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);
        }
 
    }
}

CRC-8

/*
  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;
}

/*
  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, так как использует другой полином и порядок данных).

/*
  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;
}

/*
  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 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/

/*
  Name  : CRC-16
  Poly  : 0x8005    x^16 + x^15 + x^2 + 1
  Init  : 0xFFFF
  Revert: true
  XorOut: 0x0000
  Check : 0x4B37 ("123456789")
  MaxLen: 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/

/*
  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;
}

CRC-32

Алгоритм CRC32 основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7).

#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;
}

#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 бит) - обнаружение
   одинарных, двойных, пакетных и всех нечетных ошибок
*/

Наиболее используемые и стандартизованные CRC

В то время, как циклические избыточные коды являются частью стандартов, сами они не стандартизированы в плане адаптации одного алгоритма для конкретной степени полинома. Например, существуют три описания полинома для CRC-12^[1], десять противоречивых определений CRC-16 и четыре — CRC-32^[2]. При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах Koopman, Castagnoli и другие исследовали пространство полиномов разрядности до 16^[1], 24 и 32 битов,^[3][4] найдя полиномы, дающие лучшую производительность (в смысле кодового расстояния), чем полиномы из существующих протоколов, и опубликовали лучшие из них с целью улучшения качества функций обнаружения ошибок в будущих стандартах^[4]. Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный, рекомендуемый IEEE полином для CRC-32, используемый в Ethernet, FDDI и др., является генератором кода Хемминга, и был выбран, основываясь на его производительности и способности обнаружения ошибок передачи данных^[5]. Использование другого полинома CRC-32C, предложенного Castagnoli и применяемого, в частности, в iSCSI, позволяет достичь такой же производительности (при длине исходного сообщения от 58 бит до 131 кбит). А в некоторых диапазонах длины входного сообщения, включая два наиболее распространенных размера IP-пакетов, скорость вычисления CRC-32C может быть даже выше^[4]. Стандарт ITU-T G.hn также использует CRC-32C с целью обнаружения ошибок в полезной нагрузке, а для заголовков PHY — CRC16МККТТ.

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

Существующие стандарты:

• CRC-128 (IEEE)
• CRC-256 (IEEE)

в настоящее время вытеснены криптографическими хеш-функциями.

Классификация реализаций алгоритмов CRC

Для точного указания, как именно рассчитывается CRC, чаще всего приходится полностью приводить алгоритм её расчёта.^{[источник не указан 1231 день]}

На самом деле достаточно указать ряд параметров, точно описывающих конкретный частный алгоритм CRC (если это на самом деле CRC).

В модели алгоритма CRC Rocksoft^{[источник не указан 1231 день]}, получившей некоторое хождение, используются следующие параметры:

Name: Это имя, присвоенное данному алгоритму.

Width: Степень алгоритма, выраженная в битах. Она всегда на единицу меньше длины полинома, но равна его степени.

Poly: Собственно полином. Это битовая величина, которая для удобства может быть представлена шестнадцатеричным числом. Старший бит при этом опускается (он всегда 1). Например, если используется полином 10110, то он обозначается числом «06h». Важной особенностью данного параметра является то, что он всегда представляет собой необращенный полином, младшая часть этого параметра во время вычислений всегда является наименее значащими битами делителя.

Init: Этот параметр определяет исходное содержимое регистра на момент запуска вычислений. Данный параметр указывается шестнадцатеричным числом.

RefIn(Revert): Логический параметр. Если он имеет значение False, байты сообщения обрабатываются, начиная с 7 бита, который считается наиболее значащим, а наименее значащим считается бит 0 (сдвиг налево). Если параметр имеет значение True («Истина»), то каждый байт перед обработкой обращается (сдвиг направо).

RefOut: Логический параметр. Если он имеет значение False, то конечное содержимое регистра сразу передается на стадию XorOut, в противном случае, когда параметр имеет значение True, содержимое регистра обращается перед передачей на следующую стадию вычислений. в приведённых алгоритмах, по-видимому, False).

XorOut: W битное значение, обозначаемое шестнадцатеричным числом. Оно комбинируется с конечным содержимым регистра (после стадии RefOut), прежде чем будет получено окончательное значение контрольной суммы.

Check: Это поле, собственно, не является частью определения алгоритма, данное поле служит контрольным значением, которое может быть использовано для слабой проверки правильности реализации алгоритма. Поле содержит контрольную сумму, рассчитанную для ASCII строки «123456789» (шестнадцатеричные значение «313233…»).

После определения всех этих параметров, можно точно описать особенности применённого CRC алгоритма.

Примеры спецификаций некоторых алгоритмов CRC:

  Name : CRC 16
 Width : 16
  Poly : 8005
  Init : 0000
 RefIn : True
RefOut : True
XorOut : 0000
 Check : BB3D

  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

  Name : CRC 32
 Width : 32
  Poly : 04C11DB7
  Init : FFFFFFFF
 RefIn : True
RefOut : True
XorOut : FFFFFFFF
 Check : CBF43926

Циклический избыточный код CRC-4

Из всей совокупности методов контроля с использованием циклической структуры группового сигнала наибольшее распространение получил метод контроля первичных цифровых трактов CRC-4.

При передаче потока Е1 по сети связи, включающей в себя ряд систем передачи плезиохронной и синхронной цифровых иерархий, прозрачных для его прохождения, возникает необходимость проверки качественных показателей первичного цифрового канала на всём его протяжении.

Из 256 бит, образующих стандартный цикл 2-мегабитного сигнала, сигналы с 1-ого по 31-й КИ (канальный интервал) являются случайными. Поэтому из всего группового сигнала можно идентифицировать только 7 бит циклового синхросигнала, что позволяет обнаруживать битовые ошибки без остановки связи, однако указанные 7 бит составляют только 1,4 % от общего объёма передаваемой информации. Проблема обеспечения контроля ошибок в остальных 31 каналах оптимально решается путём использования метода контроля с использованием избыточности циклического сигнала CRC-4.

CRC-4 был определён в 1980-х годах рекомендацией МСЭ-Т, но широкое распространение получил только в последнее время вследствие трудностей схемотехнической реализации, которую можно осуществить только методами микросхемотехники.

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

16 следующих друг за другом циклов образуют сверхцикл, который, в свою очередь, делится на два субсверхцикла (1-й и 2-й) по 8 циклов каждый. Таким образом, временной интервал CRC-4 равен 16 × 125 мкс = 2 мс.

Для формирования сигнала CRC-4 сумма бинарных символов каждого субсверхцикла делится на полином четвертой степени (х⁴ + х + 1). Результат деления, представляющий собой 4 бинарных символа, вводится в групповой сигнал в позициях от С1 до С4. Приёмная сторона использует аналогичный метод для того, чтобы затем сравнить кодовое слово, поступающее от передатчика, с результатом, полученным на приёмном конце. Если указанные слова различны, значит субсверхцикл, равный 2048 битам, был передан с ошибками.

Преимуществом этого метода является то, что с его помощью можно контролировать цифровой поток без остановки связи и независимо от его содержания.

Вместе с тем, при использовании указанного метода невозможно точно указать, какие биты из тысяч переданных были приняты с ошибками.

Сверхцикловый сигнал CRC-4 служит для того, чтобы можно было обеспечить синхронизацию по битам от С1 до С4. Биты Е (Е1 и Е2 для 1-го и 2-го субсверхциклов) инвертируются для сохранения структуры сверхцикла в моменты обнаружения ошибок. Таким образом, приёмная сторона может информировать передающую сторону об обнаружении ошибок передачи. После того, как установится цикловая синхронизация, сигналы CRC-4 будут передаваться непрерывно. Потеря синхронизации CRC-4 происходит тогда, когда более чем 914 сигналов CRC-4, передаваемые в течение 1 секунды, не будут соответствовать нормированным.

Аналогично организуется и проверка цифровых трактов других ступеней иерархии. Меняется только величина блоков и степень полинома: 6-я степень для CRC-6, используемого для контроля ИКМ-120, 8-я — для CRC-8, используемого для контроля ИКМ-480.

См. также

• Циклический код

Примечания