Сборник по задачам и примерам Assembler



         

CRC-арифметика - часть 4


Возьмем произвольную двоичную последовательность и разделим ее на некоторое число по правилам двоичной арифметики с циклическим переносом

(Рисунок 9.3).

По правилам CRC-арифметики деление для приведенных выше исходных данных даст следующий результат (Рисунок 9.4).

Рисунок 9.3. Схема вычисления двоичного деления (с циклическим переносом)

Рисунок 9.4. Схема вычисления CRC-деления

Как видите, результаты обычного и CRC-делений отличаются. Главное, чтобы вы подметили особенность выполнения CRC-деления. Особое внимание обратите на порядок формирования промежуточных результатов в процессе деления. Снос двоичных разрядов из делимого продолжается до тех пор, пока размерности промежуточного битового значения и делителя не сравняются, а их старшие разряды не станут равными 1. После этого над двоичными разрядами выполняется побитовое CRC-вычитание. Соотношение разрядов не важно, главное — это одинаковая размерность и единичные старшие биты. В этом случае считается, что вычитаемое больше вычитаемого, что влечет за собой включение 1 в частное и выполнение операции CRC-вычитания. Это как раз и есть проявление слабого

понятия размерности. Корзина для мусора, показанная на Рисунок 9.4, означает тот факт, что частное для процесса вычисления CRC-битовой последовательности не имеет никакого значения.

Реальные двоичные последовательности являются результатом сцепления порой огромного количества отдельных байтов (символов), образуя одно большое двоичное число, для представления которого нужно использовать двоичные полиномы огромных степеней. При этом каждый бит в подобной последовательности произвольной длины представляется в виде коэффициента длинного полинома. Например, для представления 128-разрядного блока необходим полином, состоящий из 1024 слагаемых, а для 1024-битного блока необходим полином уже с 8192 слагаемыми. В терминах полиномиальной арифметики двоичное число, сформированное в результате подобной сцепки составляющих блока данных, называется полиномом данных {сообщения) и обозначается как D(x) [5, 44]. В алгоритме вычисления CRC вводится еще несколько полиномов и соотношений между ними:




Содержание  Назад  Вперед