sqrt(2) 0 3 ноября, 2016 Опубликовано 3 ноября, 2016 (изменено) · Жалоба Здравствуйте. До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска. Вот нашел краткое описание: http://plc4good.org.ua/files/02_materials/.../CRC_revers.PDF На странице 5 написано: Значение (*3) для нас достаточно важно, так как в случае, когда старшая группа бит равна 1011, младшие W=8 бит всегда будут равны 10111100 (естественно, для данного примера). Это означает, что мы можем заранее рассчитать величины XORслагаемого для каждой комбинации старшей группы бит. Обратите внимание, что эта старшая группа в результате всегда превратится в 0. Может я чего не понимаю, но разве результат, приведенный там же, зависит не только от выдвинутой группы бит, но и от содержимого регистра (при одном и том же полиноме)? Короче, не совсем понятно, как все же рассчитать эту несчастную таблицу. Изменено 3 ноября, 2016 пользователем sqrt(2) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 9 3 ноября, 2016 Опубликовано 3 ноября, 2016 (изменено) · Жалоба Здравствуйте. До этого вычислял 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. Остальные хитрости табличной реализации относятся к тому, чтобы не модифицировать входной массив и хранить результаты сложения в регистрах. Если читаете на английском, то вот несколько полезных документов crc_v3.txt CRC_Implementation_Code_in_C___Embedded_Systems_Experts.pdf Sarwate88Computing.pdf Изменено 3 ноября, 2016 пользователем andyp Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iosifk 3 3 ноября, 2016 Опубликовано 3 ноября, 2016 · Жалоба Здравствуйте. До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска. Все так, но немного не так... Если данные появляются "мгновенно" и CRC нужна "мгновенно", то без сомнения.. Но обычно данные приходят либо последовательно, либо тетрадами, либо байтами... Вот, в темпе приема они и должны обрабатываться... Приходят последовательно - значит и обрабатываются последовательно. Приходят тетрадами - значит надо посмотреть, насколько внутренняя тактовая выше, чем частота приема. И если есть возможность, то принимать тетрадой, а обрабатывать опять же последовательно... А иначе - огромная потеря ресурса... Здравствуйте. До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска. Все так, но немного не так... Если данные появляются "мгновенно" и CRC нужна "мгновенно", то без сомнения.. Но обычно данные приходят либо последовательно, либо тетрадами, либо байтами... Вот, в темпе приема они и должны обрабатываться... Приходят последовательно - значит и обрабатываются последовательно. Приходят тетрадами - значит надо посмотреть, насколько внутренняя тактовая выше, чем частота приема. И если есть возможность, то принимать тетрадой, а обрабатывать опять же последовательно... А иначе - огромная потеря ресурса... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
sqrt(2) 0 3 ноября, 2016 Опубликовано 3 ноября, 2016 (изменено) · Жалоба Все так, но немного не так... Если данные появляются "мгновенно" и CRC нужна "мгновенно", то без сомнения.. Но обычно данные приходят либо последовательно, либо тетрадами, либо байтами... Вот, в темпе приема они и должны обрабатываться... Приходят последовательно - значит и обрабатываются последовательно. Приходят тетрадами - значит надо посмотреть, насколько внутренняя тактовая выше, чем частота приема. И если есть возможность, то принимать тетрадой, а обрабатывать опять же последовательно... А иначе - огромная потеря ресурса... У меня данные приходят побитово. То есть, в этой ситуации мне как раз таки и следует использовать схему с вычислением CRC через xor содержимого регистра сдвига с полиномом каждый такт (как на картинке) - я правильно вас понял? Изменено 3 ноября, 2016 пользователем sqrt(2) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iosifk 3 3 ноября, 2016 Опубликовано 3 ноября, 2016 · Жалоба У меня данные приходят побитово. То есть, в этой ситуации мне как раз таки и следует использовать схему с вычислением CRC через xor содержимого регистра сдвига с полиномом каждый такт (как на картинке) - я правильно вас понял? А Вы сравните схему вычисления по-битовую и по-байтовую по ресурсам... И это при том, что есть "ближние" интерконнекты и "глобальные". Так вот, при байтовой обработке уже никаких "ближних" не хватает.. А если брать табличный способ, то сколько надо памяти? И если она внешняя, то как быстро ее можно прочесть? И самый главный вопрос: Вы прежде чем закапывать деньги, рисуете карту "поля дураков"? Или в проекте лепите файлы, как лоскутное одеяло и смотрите, куда кривая вывезет??? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
