Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

CRC-2: немного алгебры

Благодаря разговору с kodt_rsdn в прошлом посте, удалось переформулировать происходящее, добавив туда немного математического смысла.

Потому что сначала он там есть и очень явный -- просто вычисляем остаток от деления по несколько необычным правилам, а вот потом куда-то полностью пропадает.

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

Делим в столбик математически грамотно
Можно заметить, что алгоритм деления в столбик "не знает", когда именно кончится сообщение. Просто в какой-то момент на вход перестают поступать биты, и работа алгоритма останавливается. Каждый бит может стать последним (Кастанеда-стайл). Отсюда, у алгоритма есть полезный инвариант: в любой момент в регистре находится остаток от деления уже обработанной части сообщения.

Как это работает можно понять, если многочлен

x^7 + x^6 + x^4 + x

переписать в виде

((((((x + 1) * x + 0) * x + 1) * x + 0) * x + 0) * x + 1) * x + 0

и теперь для получения остатка можно каждую операцию + и * заменить на +-по-модулю и *-по-модулю (перейдем в кольцо вычетов по модулю). Обозначаются как +' и *'.

((((((x +' 1) *' x +' 0) *' x +' 1) *' x +' 0) *' x +' 0) *' x +' 1) *' x +' 0

если теперь вычислять эту штуку изнутри наружу, то внутренние скобки будут постепенно раскрываться, и в каждый момент в текущей самой внутренней скобке будет находиться остаток от уже вычисленной части. Это и есть процесс вычисление остатка делением в столбик.

Табличный алгоритм
Чем хорош алгоритм двоичного деления в столбик -- тем что он прост как бревно. Потому что на каждом шаге в частное может добавиться только 0 или 1, а значит проверять надо только отношения больше/меньше и вычитать. А с нашей специальной арифметикой даже больше/меньше не надо, достаточно значения старшего бита.

Чем он плох -- тем, что приходится возиться с битами, а это медленно и печально, если не реализовано аппаратно.

Давайте попробуем его обобщить. Если у нас есть число, записанное как abcde, где каждая буква это цифра, то

abcde mod X = ((a0000 mod X) + (bcde mod X)) mod X

Это верно в общем случае. Что можно сказать про наш случай, если считать, что bcde как раз влезают в регистр (т.е. меньше X):

bcde mod X = bcde
операция + в нашей арифметике не даёт переноса, а операция сравнения так устроена, что без переноса не стать больше. В общем, правый "mod X" тоже можно убрать. Итого, остается

abcde mod X = (a0000 mod X) + bcde

видно, что если a это 0 или 1, то мы возвращаемся к корректному двоичному делению в столбик.
Если же a может быть больше 1, то вычислять (a0000 mod X) можно по таблице, она получается небольшой, на все возможные значения a.

Это и есть табличный алгоритм.

Прямой алгоритм
Алгоритмы выше работают для произвольных входных многочленов-сообщений. У нас не произвольный, у нас сообщение всегда заканчивается на n нулей.

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

Допустим, обработанная часть сообщения это abcd, и у нас в регистре остаток от деления abcd0000, равный klmn. Следующая цифра сообщения -- e.

abcde0000 mod X =                                          // остаток, который нужно получить
 = ((abcd00000 mod X) + (e0000 mod X)) mod X               // разбили на 2 части, чтобы свести к предыдущему
 = (((abcd0000 mod X) * 10 mod X) + (e0000 mod X)) mod X   // сводим к предыдущему остатку
 = ((klmn0 mod X) + (e0000 mod X)) mod X 
 = ((k0000 mod X) + (lmn0 mod X) + (e0000 mod X)) mod X    // отделили младшую часть
 = ((k0000 + e0000 mod X) + (lmn0 mod X)) mod X            // сгруппировали старшие вместе

Теперь, в нашем случае, аналогично рассуждениям выше:
lmn0 mod X = lmn0
правый "mod X" тоже можно убрать.

Остается

(k0000 + e0000 mod X) + lmn0 = ((k + e) * 10000 mod X) + lmn0 = (z0000 mod X) + lmn0

И, поскольку операция + без переноса, z = k + e это всегда какая-то цифра, то есть нам подойдет точно та же самая таблица, что и в табличном алгоритме выше.

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

Мне кажется, стало гораздо понятнее. Математика рулит!
Tags: математика, программинг
Subscribe

Recent Posts from This Journal

  • (без темы)

    Из внезапного: мальчик, с которым я 3.5 года занимался математикой получил второй результат на всеросе (9-й класс). В такой формулировке это звучит…

  • Знамя

    (с) zh3l отсюда

  • birchpunk

    Очень редко встречается ролик, которым хочется поделиться. Этот такой. В конце сюрприз.

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments