Статья 1993 г.
Предисловие
Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy
Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их
вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным
разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так
показалось). Статья была написана с целью дать простое и вместе с тем точное опи
сание CRC, вникающее во все тонкости реализации его высокоскоростных вариан
тов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft
Model CRC Algorithm", которая может быть настроена таким образом, чтобы рабо
тать подобно большинству стандартных реализаций алгоритмов расчета CRC, и ко
торая, одновременно, является хорошим примером для демонстрации особенностей
некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а
также 2 варианта высокоскоростной табличной реализации, и программа генерации
таблицы поиска для расчета CRC.
Оглавление.
Предисловие.
Введение: обнаружение ошибок.
Требования сложности.
Основная идея, заложенная в алгоритме CRC.
Полиномиальная арифметика.
Двоичная арифметика без учета переносов.
Полностью рабочий пример.
Выбор полинома.
Прямая реализация CRC.
Реализация табличного алгоритма.
Слегка преобразованный табличный алгоритм.
"Зеркальный" табличный алгоритм.
"Зеркальные" полиномы.
Начальные и конечные значения.
Полное определение алгоритма.
Параметрическая модель CRC алгоритма.
Каталог параметров стандартных реализаций CRC алгоритма.
Реализация модельного алгоритма.
Создай собственную табличную реализацию.
Генерация таблицы просмотра.
Резюме.
Поправки.
A. Словарь.
B. Ссылки.
C. Другие, обнаруженные мной, но не просмотренные ссылки.
Предисловие
Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy
Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их
вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным
разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так
показалось). Статья была написана с целью дать простое и вместе с тем точное опи
сание CRC, вникающее во все тонкости реализации его высокоскоростных вариан
тов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft
Model CRC Algorithm", которая может быть настроена таким образом, чтобы рабо
тать подобно большинству стандартных реализаций алгоритмов расчета CRC, и ко
торая, одновременно, является хорошим примером для демонстрации особенностей
некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а
также 2 варианта высокоскоростной табличной реализации, и программа генерации
таблицы поиска для расчета CRC.
Оглавление.
Предисловие.
Введение: обнаружение ошибок.
Требования сложности.
Основная идея, заложенная в алгоритме CRC.
Полиномиальная арифметика.
Двоичная арифметика без учета переносов.
Полностью рабочий пример.
Выбор полинома.
Прямая реализация CRC.
Реализация табличного алгоритма.
Слегка преобразованный табличный алгоритм.
"Зеркальный" табличный алгоритм.
"Зеркальные" полиномы.
Начальные и конечные значения.
Полное определение алгоритма.
Параметрическая модель CRC алгоритма.
Каталог параметров стандартных реализаций CRC алгоритма.
Реализация модельного алгоритма.
Создай собственную табличную реализацию.
Генерация таблицы просмотра.
Резюме.
Поправки.
A. Словарь.
B. Ссылки.
C. Другие, обнаруженные мной, но не просмотренные ссылки.