Прямой алгоритм вычисления 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, как в нашем случае, имеет ведущие нули. Это очень важный момент, понимание которого является ключом к пониманию сути процессов, происходящих на стороне приемника при получении и определении целостности исходного сообщения. Действия алгоритма для приемника просты – выполнить деление полученной последовательности на полином. При этом для выполнения деления нет необходимости дополнять исходную последовательность нулями, тем более что на практике соблюдение этого условия крайне неудобно.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Приемник попросту выполняет CRC-деление полученной исходной строки (дополненной в конце исходным значением CRC) на полином и анализирует остаток. Если остаток от этого деления нулевой, то исходная последовательность не была нарушена во время передачи. В обратном случае существует очень большая вероятность нарушения целостности исходной последовательности, и нужно принимать дополнительные меры по выяснению и исправлению ситуации. Одной из таких мер может быть попытка восстановления нужного значения CRC.
Рис. 9.5. Схема формирования выходного сообщения из исходного с использованием CRC-алгоритма