Сборник по задачам и примерам Assembler



         

Прямой алгоритм вычисления CRC - часть 2


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

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

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

  • показать в виде программной реализации суть алгоритма вычисления CRC и самого CRC-деления;
  • подготовить себя к пониманию более совершенных алгоритмов расчета CRC, к которым относится, в частности, рассматриваемый ниже табличный алгоритм.
  • Для компьютерной реализации алгоритмов вычисления CRC удобно выбирать полиномы со степенями, кратными 8 (то есть размерности регистров) — 8, j5, 24, 32 или даже 64. В этом случае можно подобрать команды из системы команд микропроцессора, наиболее оптимально реализующие алгоритмы вычисления CRC. В качестве полинома выберем один из рекомендуемых полиномов (см. ниже) — 4003. И еще одно важное замечание — степень полинома определяет размерность регистра, используемого в алгоритме, при этом считается, что старший (всегда единичный) бит полинома находится сразу за левой границей регистра. В этих условиях программа реализации прямого алгоритма вычисления CRC функционирует следующим образом (для лучшего понимания в процессе разбора алгоритма см. Рисунок 9.6). В регистр побитно вдвигаются биты исходной строки. Это происходит до тех пор, пока при очередном сдвиге слева появится единичный бит. В этом случае все содержимое регистра подвергается операции XOR со значением полинома без старшего бита. Далее процесс сдвига и анализа выдвигаемого бита продолжается до тех пор, пока не будет выдвинут очередной единичный бит, в результате чего опять между регистром и полиномом выполняется операция XOR, и т. д. После того как последний бит вдвинут в регистр, в него вдвигается количество нулевых битов, равное степени полинома. Этим, как мы не раз уже отмечали, достигается участие всех бит исходной битовой строки в формировании значения CRC. В результате в регистре остается значение CRC, которое необходимо добавить к исходной строке и передать приемнику.




    Содержание  Назад  Вперед