Контроль передачи данных прямым алгоритмом вычисления CRC

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

1. 1. Выбрать полином Р, в результате автоматически становится известной его степень N.
   2. Добавить к исходной двоичной последовательности N нулевых битов. Это добавление делается для гарантированной обработки всех битов исходной последовательности.
   3. Выполнить деление дополненной N нулями исходной строки S на полином Р по правилам CRC-арифметики. Запомнить остаток, который и будет являться CRC.
   4. Сформировать окончательное сообщение, которое будет состоять из двух частей: собственно, сообщения и добавленного в его конец значения CRC.

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

Рисунок 3 Схема формирования выходного сообщения из исходного с использованием CRC-алгоритма

Описанный выше алгоритм вычисления значения CRC называется прямым и чаще всего реализуется аппаратно. Но, тем не менее, для совершенствования навыков программирования на ассемблере составим реализующий его пример программы. Хотя эффективность этой программы не слишком высока, у нее есть две учебные цели:

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