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. Например, шестнадцатеричное значение ОеЗh может быть представлено следующим полиномом: 1х27 + 1х26 + 1х25 + 0х24 + 0х23 + 0х22 + 1x21 + 1x20.
Если ввести в качестве переменной х=2, то получим следующий двоичный полином: 1хx7 + 1xx6 + 1xx5 + 0хх4 + 0xx3 + 0xx2 + 1xx1 + 1хх0.
В этом полиноме, строго говоря, значение х не играет особой роли, так как данное двоичное число можно представить полиномом в другой системе счисления, например, шестнадцатеричной: ехх1 + 2хх°, где х = 16. При этом заметим, что в том и другом случае цифры 0, 1, е, 2 – это просто цифры двоичной и шестнадцатеричной систем счисления.
Так как слагаемые двоичного полинома с нулевыми коэффициентами не дают никакого вклада в конечный результат, то их можно попросту отбросить, оставив только слагаемые, переменные которых имеют единичные коэффициенты: 1xx7 + 1xx6 + 1xx5 + 0xx4 + 0xx3 + 0xx2 + 1xx1 + 1хх° = 1xx7 +1xx6 + lxx5 + 1xx1+ 1xx0 = = x7 + x6 + x5 + x1 + x°.
Здесь x = 2.
Над полиномами можно выполнять арифметические операции: сложение, умножение и вычитание. Процессы выполнения этих операций для полиномиальной арифметики и обычной арифметики многократной точности (см. главу 1) похожи. Главное отличие в том, что из-за отсутствия связи между коэффициентами полинома понятие переноса в полиномиальной арифметике отсутствует.
Например, для умножения 7h (0111b) на 5h (0101b) выполняются действия: (х2 + х1 + х°)х(х2 + х°) = (х4 + х3 + х2 + х2 + х1 + х°) – =х4 + х3 + х2 + х2 + х1 + х° + х°= х4 + х3 + 2х2 + х1 + 2х°.
Для того чтобы получить в ответе 35, мы должны х взять равным 2 и привести коэффициенты у членов полинома 2х° и 2х2 к двоичным, сделав перенос соответствующих единиц в старшие разряды: 01010 переносы 11111 результат 100011 = 35)0.
В результате получим двоичный полином х5+х'+х°.
Эти рассуждения призваны сформулировать очередной тезис о том, что переносы, как и в обычной арифметике, можно выполнять в случае, когда известно основание системы счисления. То есть до тех пор, пока мы не знаем х, мы не можем производить и переносы. В приведенном выше примере, мы не знаем, что 2х2 и 2х° на самом деле являются х3 и х1 до тех пор, пока не известно, что х = 2. То есть в полиномиальной арифметике коэффициенты при разных степенях изолированы друг от друга и отношения между ними не определены.
Из-за этого возникает первая странность полиномиальной арифметики – операции сложения и вычитания в ней абсолютно идентичны и вместо них можно смело оставлять одну. Например, сложение по правилам полиномиальной арифметики по модулю 2, будем ее далее называть CRC-арифметикой, будет выполнено так:
| 11111011 | |
| + | 11001010 |
| 00110001 |
Из этого примера видны правила сложения двоичных разрядов в арифметике с отсутствием переносов: 0+0=0; 0+1 = 1; 1+0=1; 1 + 1=0.