Циклическая проверка на четность

Циклическая проверка на четность

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

Содержание

Алгоритм CRC

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

Каждой конечной последовательности битов a_0, a_1, \dots, a_{N-1} взаимооднозначно сопоставляется двоичный многочлен \sum_{n=0}^{N-1} a_n x^n, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 0,1,0,1,1,0,1 соответствует многочлену:

P(x) = 1\cdot x^6 + 0\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 0\cdot x^0 = x^6 + x^4 + x^3 + x^1

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

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

R(x) = P(x)\cdot x^N\, \bmod\, G(x)

где

R(x) — многочлен, представляющий значение CRC.
P(x) — многочлен, коэффициенты которого представляют входные данные.
G(x) — порождающий многочлен.
N = \deg\,G(x)степень порождающего многочлена.

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

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

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

\left(\begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0  \end{array}\right)

Тогда контрольная сумма будет равна операции 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 на полином. Полученный результат, вне зависимости от того, выполнялась ли операция XOR, сдвигаем на один бит влево (то есть умножаем на 2). После сдвига (умножения) теряется старый старший бит, а младший бит освобождается (обнуляется). На место младшего бита загружается очередной бит из файла. Операция повторяется до тех пор, пока не загрузится последний бит файла.

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

CRC-8

CRC-16

CRC-CCITT (отличается от классического CRC-16, так как использует другой полином и порядок данных).

CRC-32

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

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

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

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

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

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

См. также

Ссылки

Литература

  • Генри С. Уоррен, мл. Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker's Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4

Wikimedia Foundation. 2010.

Нужна курсовая?

Полезное



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»