В основе CRC-арифметики лежит полиномиальная арифметика.

Особенности CRC-арифметики.

CRC-арифметика отличается от привычной двоичной арифметики с циклическим переносом отсутствием переносов и вычислением всех коэффициентов по модулю 2.

CRC-арифметика

Приемник данной информации выполняет деление на то же фиксированное двоичное число и сравнивает его остаток с исходным значением CRC.

Интерес представляет остаток от этого деления, который и является значением CRC.

Эта последовательность делится на некоторое фиксированное двоичное число.

Исходная последовательность байтов представляется единой последовательностью битов.

Идея вычисления CRC

CRC (Cyclic Redundancy Code) — последовательность бит, полученная по определенному алгоритму на основании другой (исходной) битовой последовательности.

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

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

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

4) Полученное значение CRC сохраняется и передаётся вместе с исходной последовательностью.

6) Если при сравнении оказалось, что полученное при делении CRC и старое значение CRC равны, то исходное сообщение не повреждено, иначе – повреждено.

 

Реальный алгоритм вычисления CRC использует особые правила арифметики, в соответствии с которыми производятся все вычисления – правила CRC-арифметики.Эти правила отличаются от правил обычной двоичной арифметики.

 

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

.

Здесь u_n — элементы некоторой алгебраической системы S, называемые коэффициентами; х — переменная полинома, которую можно рассматривать как формальный символ без определенного значения.

Для рассмотрения CRC арифметики важна полиномиальная арифметика по модулю 2, в которой каждый коэффициент полинома равен одному из двух значений — 0 или 1. Например, шестнадцатеричное значение 0Е3h может быть представлено следующим полиномом:

1*2⁷ + 1*2⁶ + 1*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1*2°.

 

Если ввести в качестве переменной х=2, то получим следующий двоичный полином:

1*x⁷ + 1*x⁶ + 1*x⁵ + 0*х⁴ + 0*x³ + 0*x² + 1*x¹ + 1*х°.