Табличный метод вычисления CRC

Операция деление по модулю 2

Пусть массив (последовательность бит) имеет следующий вид: 101111001110 (для простоты примера берем небольшую разрядность). Число, на которое выполняется деление по модулю (носит название образующего полинома) для примера будет 10011. Выбирается это число с учетом тех свойств, что оно должно делиться по модулю 2 без остатка только на единицу и само на себя. Образующий полином имеет разрядность на единицу больше чем разрядность контрольного кода. К примеру, если требуется получить 8 – разрядный контрольный код необходимо взять образующий полином 9 – разрядный.

В рассматриваемом примере это полином 5-го разряда, а контрольная сумма (остаток от деления) будет 4-х разрядной. Если бы требовалось получить 8-разрядный остаток то можно, к примеру, было бы взять образующий полином равным 100011101 в шестнадцатеричном коде 11D.

Операция деления по модулю два выполняется практически так же как обычное деление в столбик (рис. 1), но вместо вычитания выполняется поразрядное сложение по модулю 2, где каждый полученный бит есть результат выполнения функции исключающее ИЛИ (XOR) от соответствующих слагаемых битов. Остаток от деления в данном примере 1000 есть циклическая контрольная сумма (частное отбрасывается).

Рис. 1

Реализация на практике вычисления циклического контрольного кода, выполняется параллельным и последовательным методами. Практическая реализация вычисления этого остатка возможна по приведенному здесь примеру аппаратным или программным способом, но этот способ считается медленным. Увеличить скорость вычисления контрольного кода можно, прибегнув, к так называемому табличному методу. Суть метода такова создается таблица чисел размером 2ⁿхn, где n — разрядность контрольной суммы. Метод вычисления чисел в таблице следующий (табл. 1).

Таблица 1. Табличный метод вычисления контрольной суммы.

Адрес в таблице	Данные в таблице (числа)
	Остаток от деления числа 1 0000 0000 на полином
	Остаток от деления числа 10 0000 0000 на полином
	Остаток от деления числа 11 0000 0000 на полином
	Остаток от деления числа 100 0000 0000 на полином
	Остаток от деления числа 101 0000 0000 на полином
…
	Остаток от деления числа 1111 1111 0000 0000 на полином

Числа являются остатком от деления по модулю 2 числа с n конечными нулями (в нашем примере n = 8) и с n начальными разрядами, равными номеру числа (его адресу) в таблице. Выполняется деление на 9-разрядный образующий полином. Вычисление таблицы производится однократно, и она хранится в ПЗУ или на диске.

Алгоритм вычисления контрольного кода при помощи данной таблицы следующий (рассматриваем случай n = 8). Выбирается первый байт массива, который рассматривается как адрес в таблице (номер числа). Выбираем в таблице число с данным номером — получаем остаток О¹. Берем второй байт информационного массива и суммируем его по модулю 2 с остатком О¹. Полученное число есть адрес в таблице. Для этого адреса берем из таблицы остаток О². Выбираем третий байт массива, суммируем его по модулю 2 с остатком О². Полученное число есть адрес в таблице, выбираем из нее остаток О³ и так далее до конца массива.

Дата добавления: 2015-08-31