Вычисление CRC при помощи таблицы поиска (lookup table) Опции

[sqrt(2)]

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

До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска.

Вот нашел краткое описание:

http://plc4good.org.ua/files/02_materials/.../CRC_revers.PDF

На странице 5 написано:

Значение (*3) для нас достаточно важно, так как в случае, когда старшая группа бит равна 1011, младшие W=8 бит всегда будут
равны 10111100 (естественно, для данного примера). Это означает, что мы можем заранее рассчитать величины XORслагаемого для каждой комбинации старшей
группы бит. Обратите внимание, что эта старшая группа в результате всегда превратится в 0.

Может я чего не понимаю, но разве результат, приведенный там же, зависит не только от выдвинутой группы бит, но и от содержимого регистра (при одном и том же полиноме)? Короче, не совсем понятно, как все же рассчитать эту несчастную таблицу.

Сообщение отредактировал sqrt(2) - Nov 3 2016, 10:27

[iosifk]

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

До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска.

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

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

До этого вычислял CRC в модели в Матлабе, и в целях понимания расписал всё сам, но через регистр сдвига и xor. И не заморачивался, ибо в этой модели было не важно время вычисления. С другой стороны, на практике такой подход не применим. Как я понял, основной алгоритм - это вычисление CRC при помощи таблиц поиска.

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