Контрольная сумма. Циклический избыточный код

Циклический избыточный код (англ. Cyclic redundancy code, CRC^[1]) — алгоритм вычисления контрольной суммы, предназначенный для проверки целостности передаваемых данных. Алгоритм CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов.^[2]

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов,

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

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

где

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

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

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

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

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