Здравствуйте.

До этого вычислял 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):


Для вычислений требуется просчитанная таблица остатков от деления всевозможных полиномов Top*x^16.

Остальные хитрости табличной реализации относятся к тому, чтобы не модифицировать входной массив и хранить результаты сложения в регистрах.

Если читаете на английском, то вот несколько полезных документов

Все так, но немного не так...
Если данные появляются "мгновенно" и CRC нужна "мгновенно", то без сомнения..
Но обычно данные приходят либо последовательно, либо тетрадами, либо байтами... Вот, в темпе приема они и должны обрабатываться... Приходят последовательно - значит и обрабатываются последовательно. Приходят тетрадами - значит надо посмотреть, насколько внутренняя тактовая выше, чем частота приема. И если есть возможность, то принимать тетрадой, а обрабатывать опять же последовательно... А иначе - огромная потеря ресурса...


Все так, но немного не так...
Если данные появляются "мгновенно" и CRC нужна "мгновенно", то без сомнения..
Но обычно данные приходят либо последовательно, либо тетрадами, либо байтами... Вот, в темпе приема они и должны обрабатываться... Приходят последовательно - значит и обрабатываются последовательно. Приходят тетрадами - значит надо посмотреть, насколько внутренняя тактовая выше, чем частота приема. И если есть возможность, то принимать тетрадой, а обрабатывать опять же последовательно... А иначе - огромная потеря ресурса...

У меня данные приходят побитово. То есть, в этой ситуации мне как раз таки и следует использовать схему с вычислением CRC через xor содержимого регистра сдвига с полиномом каждый такт (как на картинке) - я правильно вас понял?

А Вы сравните схему вычисления по-битовую и по-байтовую по ресурсам... И это при том, что есть "ближние" интерконнекты и "глобальные". Так вот, при байтовой обработке уже никаких "ближних" не хватает.. А если брать табличный способ, то сколько надо памяти? И если она внешняя, то как быстро ее можно прочесть?

И самый главный вопрос: Вы прежде чем закапывать деньги, рисуете карту "поля дураков"? Или в проекте лепите файлы, как лоскутное одеяло и смотрите, куда кривая вывезет???