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




CRC-арифметика - часть 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
<


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