Прямой алгоритм вычисления CRC
Даже маленькая практика стоит большой теории.
Закон Букера
(Прикладная Мерфология)
После всех этих рассуждений мы готовы к тому, чтобы осмысленно воспринять общую схему реального алгоритма вычисления CRC – алгоритма прямого (поразрядного) вычисления CRC. При этом удобно CRC-алгоритм рассматривать с точки зрения двух сторон-участников процесса: источника – объекта, формирующего сообщение для передачи, и приемника – объекта, который принимает сообщение и проверяет его целостность. Действия источника следующие.
- Выбрать полином Р, в результате автоматически становится известной его степень N.
- Добавить к исходной двоичной последовательности N нулевых битов. Это добавление делается для гарантированной обработки всех битов исходной последовательности.
- Выполнить деление дополненной N нулями исходной строки S на полином Р по правилам CRC-арифметики. Запомнить остаток, который и будет являться CRC.
- Сформировать окончательное сообщение, которое будет состоять из двух частей: собственно сообщения и добавленного в его конец значения CRC.
К примеру, вычисление по этому алгоритму CRC для исходной последовательности 1101001110010110100 (см. рис. 9.4) и сама окончательная последовательность на стороне источника будут выглядеть так, как показано на рис. 9.5.
Из рисунка видно, что в начале вычисления исходная последовательность 1101001110010110100 дополняется нулями в количестве, равном степени полинома (Р=1011 – степень полинома N=3): 1101001110010110100+000. При выполнении CRC-деления эти дополнительные биты гарантируют, что все биты исходной последовательности примут участие в процессе формирования значения CRC. Результирующая последовательность получается равной исходной последовательности, дополненной значением CRC: 1101001110010110100+011.
Заметим, что длина присоединяемого к исходной последовательности значения CRC должна быть равна степени полинома, даже если CRC, как в нашем случае, имеет ведущие нули. Это очень важный момент, понимание которого является ключом к пониманию сути процессов, происходящих на стороне приемника при получении и определении целостности исходного сообщения. Действия алгоритма для приемника просты – выполнить деление полученной последовательности на полином. При этом для выполнения деления нет необходимости дополнять исходную последовательность нулями, тем более что на практике соблюдение этого условия крайне неудобно.
Приемник попросту выполняет CRC-деление полученной исходной строки (дополненной в конце исходным значением CRC) на полином и анализирует остаток. Если остаток от этого деления нулевой, то исходная последовательность не была нарушена во время передачи. В обратном случае существует очень большая вероятность нарушения целостности исходной последовательности, и нужно принимать дополнительные меры по выяснению и исправлению ситуации. Одной из таких мер может быть попытка восстановления нужного значения CRC.
Рис. 9.5. Схема формирования выходного сообщения из исходного с использованием CRC-алгоритма