Что такое CRC?

- Помнишь, в школе всякой ерундой маялись типа "загадай число, сделай то, сделай это, а сейчас я его угадаю!"

- Ну и?

- Возьми любой файл. Вычисли его CRC32. Допиши его в конец файла в обратном порядке (например, 3432AA8D как 8DAA3234). Вычисли CRC32 получившегося файла. Это магия! Я угадаю его! Оно равно 2144DF1C.

- Ого. Ты владеешь черной магией.

По мотивам bash.org.ru

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

Расшифровывается эта аббревиатура как cyclic redundancy check, или, говоря по-русски, циклический избыточный код. Может показаться, что за таким сложным и громоздким названием кроется что-то очень сложное, но на самом деле, с точки зрения конечного пользователя, всё предельно просто. CRC - это просто контрольное значение, которое способно служить подтверждением целостности данных.

Ключи CRC могут быть разной длины. Как правило, наиболее широко используются 16-, 32- и 64-битные ключи. Впрочем, также достаточно часто применяются и ключи другой длины - например, 12-битные. Существует множество различных алгоритмов вычисления CRC, которые, кстати, как ни странно, до сих пор до конца не стандартизованы. По сути, все алгоритмы заключаются в делении с остатком многочлена, соответствующего входным данным, на некоторый заранее известный делитель. Степень полинома, генерируемого из входных данных, должна быть равна длине контрольной суммы, то есть, например, при использовании CRC16 нужно генерировать многочлен 16-й степени.

Суть использования CRC заключается в том, что вероятность получения точно такого же CRC при какой-либо перестановке в исходных данных исчезающе мала, то есть, фактически, в обычной жизни CRC стопроцентно гарантирует сохранность и уникальность полученных данных. Например, вероятность того, что случайно измененные данные будут иметь такое же CRC, как и исходные, в случае с использованием 64-битной контрольной суммы будет равна 5•10-20.

Вадим СТАНКЕВИЧ,
[email protected]

Версия для печатиВерсия для печати

Номер: 

31 за 2010 год

Рубрика: 

Software
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!

Комментарии

Аватар пользователя mike
>"cyclic redundancy check, или, говоря по-русски, циклический избыточный код"

Говоря по-русски -- КОНТРОЛЬНЫЙ ОСТАТОК ЦИКЛИЧЕСКОГО КОДА. Точнее, остаток от деления на полином циклического кода. Связисты юзают уже полвека. :)

>"Существует множество различных алгоритмов вычисления CRC, которые, кстати, как ни странно, до сих пор до конца не стандартизованы"

Стандартизованы не алгоритмы, а ПОЛИНОМЫ. Например, X^16+X^12+X^5+1. :)

Аватар пользователя ЫнкогнитА
Чё? o_O