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



         

CRC-арифметика



CRC-арифметика

Расчеты CRC ведутся в двоичной системе счисления. При проведении CRC-вы-числений используется специальная CRC-арифметика, которая, по сути, является полиномиальной арифметикой по модулю 2. Полиномиальная арифметика по модулю 2 — это еще один из видов арифметик, используемых для решения задач в определенной предметной области и отличающихся от привычной двоичной арифметики с циклическим переносом отсутствием переносов и вычислением всех коэффициентов по модулю 2 . В уроке 20 «ММХ-технология микропроцессоров Intel» учебника при рассмотрении ММХ-команд мы знакомились с одной из таких альтернативных арифметик — арифметикой с насыщением. Теперь рассмотрим особенности CRC-арифметики.

Итак, как отмечено выше, в основе CRC-арифметики лежит полиномиальная арифметика. По определению, полином — линейная комбинация (сумма) произведений целых степеней заданного набора переменных с постоянными коэффициентами. Частный случай — полином, содержащий одну переменную:

u(x)=unxn+...u,x1+uoxo.

Здесь un, nu щ — элементы некоторой алгебраической системы S, называемые коэффициентами; х — переменная полинома, которую можно рассматривать как формальный символ без определенного значения. Алгебраическая система S обычно представляет собой множество целых или рациональных чисел в диапазоне 0..m-1 со сложением, вычитанием и умножением, выполняемыми по модулю т. Для нашего рассмотрения особенно важна полиномиальная арифметика по модулю 2, в которой каждый коэффициент полинома равен одному из двух значений — 0 или 1. Например, шестнадцатеричное значение ОеЗп может быть представлено следующим полиномом:

1х27 + 1х26 + 1х25 + 0х24 + 0х23 + 0х22 + 1x21 + 1x2°.

Если ввести в качестве переменной х=2, то получим следующий двоичный полином:

1хx7 + 1xx6 + 1xx5 + 0хх4 + 0xx3 + 0xx2 + 1xx1 + 1хх°.

В этом полиноме, строго говоря, значение х не играет особой роли, так как данное двоичное число можно представить полиномом в другой системе счисления, например, шестнадцатеричной: ехх1 + 2хх°, где х = 16. При этом заметим, что в том и другом случае цифры 0, 1, е, 2 — это просто цифры двоичной и шестнадцатеричной систем счисления.




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