Цитата(sqrt(2) @ Nov 3 2016, 12:13)
Здравствуйте.
До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска.
Вот нашел краткое описание:
http://plc4good.org.ua/files/02_materials/.../CRC_revers.PDFНа странице 5 написано:
Может я чего не понимаю, но разве результат, приведенный там же, зависит не только от выдвинутой группы бит, но и от содержимого регистра (при одном и том же полиноме)? Короче, не совсем понятно, как все же рассчитать эту несчастную таблицу.
Источник совсем какой-то негодный. Попробую объяснить на пальцах. Возможность табличной реализации построена на правилах вычисления остатков в кольце полиномов (что собственно и делается при вычислении CRC).
Пусть мы хотим за раз обрабатывать по 8 старших коэффициентов и полином для расчета CRC у нас степени 16. Тогда
для вычисления CRC нужно N+16 коэффициентный полином A*x^16 поделить на 16-ти битный полином С, чтобы найти остаток R_а, который и есть собственно CRC
A*x^16 = C*g_A + R_a , здесь и далее g_a - частное от деления A на С.
ну или A*x^16 mod C = R_a
Запишем A в виде cуммы двух полиномов : 8ми битного полинома Hi и полинома Lo степени N-8:
A = Hi*x^(N-8) + Lo
Тогда
(A*x^16) mod C = ((Hi * x^(N-8) + Lo) * x^16) mod C = (Hi*x^(N+8)) mod C + (Lo*x^16) mod C. (*)
Пусть Hi*x^16 mod C = g_hi * C + R_hi
Рассмотрим первое слагаемое (*)
(Hi*x^(N+8)) mod C = (g_hi * С + R_hi) * x^(N-8) mod C = R_hi * x^(N-8) mod C
Подставим его в (*) и получим:
(A*x^16) mod C = R_hi * x^(N-8) mod C + (Lo*x^16) mod C = (R_hi * x^(N-8) + Lo * x ^ 16) mod C
Видно, что если R_hi уже рассчитан, то задача свелась к нахождению остатка от деления полинома степени, на 8 меньшей, чем у полинома A.
Отсюда собственно и вырисовывается табличная реализация, если заранее вычислить все возможные R_hi (которых может быть 256):
Код
Умножаем A на x^16
Для каждых 8 коэффициентов полинома A (Top)
{
Находим R_hi(Top)
Суммируем 16 следующих старших коэффициентов полинома с коэффициентами остатка по модулю 2
}
//CRC находтся в 16 младших коэффициентах A, умноженного на x^16
Для вычислений требуется просчитанная таблица остатков от деления всевозможных полиномов Top*x^16.
Остальные хитрости табличной реализации относятся к тому, чтобы не модифицировать входной массив и хранить результаты сложения в регистрах.
Если читаете на английском, то вот несколько полезных документов
Сообщение отредактировал andyp - Nov 3 2016, 11:58
Вычисление CRC при помощи таблицы поиска (lookup table)
Nov 3 2016, 09:13
РЈРСВВВВВеньшено Р В Р’В Р СћРІР‚ВВВВР С• 79%
