1а; + 0а;2+1а;3 + 1а;*-Ь1а;5, : О + Ix + + 0а;3 Ох* -f- 0а;5,

1х + 0х2 + 1хЗ + 1х* + 1х5, : О + Ох 4- 0x2 13-3 ia.4 la-s

: 1 + Ох f 1x2 .. ia.4 ц 0а;5 :0 + 0х + 0х2 + 1хЗ I 1х* + 1а;5, : О + Ох + 1x2 + 1x3 + 1х* + 0x5, : 1 + Ох + 1x2 + 0x3 Ох* + 1x5, : 1 + Ох + 1x2 1а.з ia.4 [.. Охв, 1х + 0x2 + 1x3 + Ох* + 0x5 + 1х Коэффициенты для г<* и р< определяются следующим образом:

2.33. Вычисления. 10 0 10 1, 1

0 10 0 1 1, о 10 0 10 1, 1

1 о о 1 1, о

начальное положение

0 0 0 0 1,1, 1

1 о о 1 1, О 1

0 о о 1 1, 1

1 о о 1 1, о

0 о 1 1, 1 о

1 о о 1 1, о

0 1 1, 1 о о

10 0 1 1,0

1 1, 1 о о о 10 о 1 1,0

1 1, 1 о о о

0 10 1 1,0

вычисление г" и р

1 1, 01

1 О 01 1 1, 01

о 01

1 1, 1

11 1, о 10

1 1, 1 он

0 0 1, о 10

1 1, 1 0 11 о 1, о 100

1 1, 1 о 00 1 .

л П л л Р> л 1Л

вычисление г и р<

1 1, 1 О 1 1 1 1, О 1 0 0 0 0

О 1, 1, О

10 111 0 0 111

1, 1 о 1 1 1 о

1, о о о 1 1 1

1, 1 о 1 1 1 о

1, 1 о 1 о о 1

,10 1110 0

1, 1 о 1 о о 1

вычисление г<2 и р

конечное положение

(Вычисления 2.33 являются сокращением вычислений 2.31 и 2.32.)

Здесь мы используем запись, при которой старшие коэффициенты г располагаются в крайнем левом положении, а старшие коэффициенты р - в крайнем правом положении. Используя такую запись, можно производить вычисления с помощью всего лишь двух основных регистров, каждый из которых содержит т -\- 2 ячейки. Правила вычисления сводятся к следующему.

2.34. Алгоритм вычисления мультипликативного обратного. В начальном положении в верхнем регистре записаны неприводимый многочлен М (х), запятая и единица, а в нижнем регистре - многочлен г (х), запятая и нуль. Первоначальное значение А; равно -1. Затем поступаем следующим образом.

Если крайний левый элемент верхнего регистра равен нулю, то сдвигаем верхний регистр (вместе с его запятой) на одну позицию влево.

Если крайний левый элемент нижнего регистра равен нулю, то сдвигаем нижний регистр (вместе с его запятой) на одну позицию влево.

Если крайние левые элементы и верхнего и нижнего регистров равны единице и к четно, то прибавляем к верхнему регистру ту часть содержимого нижнего регистра, которая стоит слева от запятой, а к нижнему регистру ту часть содержимого верхнего регистра, которая стоит справа от запятой.

Если крайние левые элементы и нижнего и верхнего регистров равны единице и к нечетно, то прибавляем к нижнему регистру ту часть содержимого верхнего регистра, которая стоит слева от запятой, а к содержимому верхнего регистра ту часть нижнего регистра, которая стоит справа от запятой.

После установки запятых и осуществления сдвига четность к изменяется. Для четных к нижняя запятая находится слева от (или совпадает с) верхней запятой; дЛя нечетных к нижняя запятая находится справа от (или совпадает с) верхней запятой.

Вычисление заканчивается, когда обе запятые сдвигаются на левый конец своего регистра. Регистр, запятая в котором выдвинута совсем, содержит р, р, . . ., pm-i, О, 0; другой регистр содержит 1, Мо, . . ., Mm-

Описанный метод сводит итерацию алгоритма деления (многочленов) и алгоритма Евклида в единую процедуру, каждый шаг которой заключается лишь в сдвиге регистра или в сложении. Общее число сдвигов равно 2/п + 1, так как каждый сдвиг передвигает одну из занятых, причем верхняя запятая проходит через {т 1) положений, а нижняя - через т положений. Так как каждое сложение выполняется непосредственно за каждым сдвигом, то ясно, что всего требуется не более 2т операций сложения и предлагаемая процедура в общей сложности требует не более 4т 4 1 one- раций.

Практически эта процедура может быть реализована с помощью различных логических схем. Одним из возможных методов фикса-; ции местоположения запятых является использование специального ; (маркерного) регистра, в котором всюду содержатся единицы, за исключением одного отрезка нулей, первая и последняя позиции] которого соответствуют запятым. При выполнении операций сдвига i символы маркерного регистра перемещаются путем выполнения i логических операций И и ИЛИ над символом в данной позиции] и в соседней справа в соответствии с четностью числа к и положением] (верхний, нижний) сдвигаемого регистра. Так как единственный] нуль содержится в маркерном регистре тогда и только тогда, когда! в нем нет двух смежных нулей, то условие совпадения запятых может быть проверено с помощью операции ИЛИ, примененной! к логическому произведению И символов в четных позициях маркер-! ного регистра и логическому произведению И символов, стоящих! в его нечетных позициях. Для иллюстрации приведем несколько! первых шагов вычислений 2.33 с использованием маркерного реги- стра вместо запятых.

2.35. Вычисления.

С запятыми

1 О О 1 О 1,1 1

0 1 О О 1 1,0 J

1 О О 1 О 1,1 •» 1 О О 1 1,0 О /

С маркерным регистром

10 0 10 11 1111110 1 0 10 0 110

10 0 10 11 111110 0 1 10 0 110 0

О 1 1,1 I

1 о о 1 1,0 1 J

0 о о 1 1,1 о

1 о о 1 1,0 1

0 о 1 1,1 о о

1 о о 1 1,0 1

0 1 1,1 о о о

1 о о 1 1,0 1 1 1,1 о о о о 1 о о 1 1,0 1 1 1,1 о о о 1 1

0 1 о 1 1,0 1 J

1 1,1 о о о 1 1 1 о 1 1,0 1 о /

0 0 0 0 1 1 1 111110 0 1 10 0 110 1

0 0 0 1 1 1 0 111110 11 10 0 110 1

0 0 1110 0 11110 0 11 10 0 110 1

0 1110 0 0 1 1 1 0 0 0 1 1

10 0 110 1

1 1 1 0 0 0 0 1 1 0 0 0 0 1 1

10 0 110 1

1 1 1 0 0 0 1 1 1 0 0 0 0 1 1

0 10 110 1

1 1 1 0 0 0 1 1 1 0 0 0 1 1 1

10 110 10

Заметим, что окончанир. алгоритма отмечается появлением нуля в крайней левой нозициг маркерного регистра.

При использовании синхронной логики и двухтактовых часов для наиболее дешевой реализации данной процедуры требуется до Am + 1 циклов работы. Вычисления могут быть ускорены за счет введения дополнительной аппаратуры. Например, одновременное выполнение последовательных сдвигов и сложений сокращает время вычислений вдвое, а если требуется максимальная скорость, то мол;но строить отдельную логическую схему для каждого шага процедуры. Такая схема позволит выполнить полное вычисление в один временной цикл (точнее, за время, определяемое прохождением сигналов через т ячеек регистра), но стоимость будет пропорциональна т. При больших т для большинства приложений, по-видимому, наилучшими являются схемы, для которых и стоимость п время вычислений пропорциональны т.

Использование описанных в предыдущем разделе устройств позволяет сравнительно просто строить схемы, выполняющие правила алгоритма 2.34. На рис. 2.10 изображено устройство управления для такой схемы.

О О О О 1 1,1

Крайняя левая позиция верхнего регистра

Крайний левая позиция нижнего регистра

Сдвиг нижнего регистра влево

Прибавить содержимое нижнего регистра к содержимому верхнего слева от наиболее левого нуля вМ и содержимое верхнего регистра к содержимому ниж-jweo справа от наиболее правого нуля М

Прибавить содержимое верхнего регистра к содержимому нижнего справа от наиболее правого нуля в Ми содержимое нижнего регистра к содержимому в------слева от наиболее левого нуля в М

О о

Четные позиции М

Нечетные позиции М

"М и левый сдвиг М"

"М или левый сдвиг М"

Изменить четность к

Рис. 2.10. Схема управления для вычисления с помощью алгоритма Евклида мультипликативного обратного по модулю неприводимого двоичного многочлена. (Здесь М - маркерный регистр, а не многочлен М (х), коэффициенты которого задают начальное состояние верхнего регистра.)

*2.4, Умножение

Для описания умножения в поле классов вычетов по модулю неприводимого двоичного многочлена М (х) степени т удобно обозначить специальным символом а класс вычетов, содержащий х. Тогда «2 будет представлять класс вычетов, содержащий х, и вообще для произвольного многочлена г (х) символ г (а) соответствует классу вычетов, содержащему г (х). Так как М (х) = О mod М (х), то должно выполняться равенство М (а) = 0. Поэтому элемент а является корнем многочлена М (х). Следовательно, мы имеем очевидный изоморфизм между 2"* классами вычетов по модулю М (х) и полем, содержащим двоичное поле (поле из двух элементов) и все j многочлены от а, где М (а) = 0.

Любой элемент Y этого поля может быть однозначно представлен

Б виде многочлена от а степени < т, т. е. в виде Y - У] Yia\ где

числа из двоичного поля. В соответствии с этим элемент Y может быть записан в т-разрядном регистре, ячейки которого содержат двоичные числа Ym-i, 5m-2. • • м 50-

2.41. Умножение «регистра») на фиксированную константу. Рассмотрим прежде всего умнонение элемента Y, записанного в регистре, на постоянный элемент А поля. Элемент А может быть представлен в виде некоторого двоичного

ш-1 m-i

многочлена от а. Так как У = S то YA = У, {Аа).

г=0 г=0

Выражая Аа- в виде многочлена от а степени <т, т. е. в виде Аа* =

= 2 О» получим, что

m-i m-i т-1 m-1

YA-Y, Auja- S ( S У1Аи,)а\

i=0 3=0 3=1 i=0

Таким образом, умножение элемента Y поля на элемент А поля эквивалентно умножению т-мерной двоичной вектор-строки Y =

[Ym-\, Ym-г, • • Yff] на матрицу размерности т X т, элементами которой являются числа Aij. Строки этой матрицы представляют собой произведения Ла™~, Аа~, . . ., А. Пусть, например, М (х) = х + х -\- I и нужно умножить записанный в регистре элемент Y на элемент 4 = а* -j- а. Сначала вычисляем

Аа = а* + а,

Аи} = «5 а = «3 + -f- 1,

Аа? = а* + аЗ а,

Аа = «5 4- ее* -1- = а* -1- 1.

Равенство Z = YA эквивалентно равенству

14, 3, 2, 1, о] = [4, 3, Y-i, YI, Уо]

1 0 0 0 1 110 10 0 110 1 10 10 0 О 1 О 1 0J

Такая операция легко может быть реализована с помощью схемы, изображенной на рис. 2.11,

1) Автор для краткости употребляет такую терминологию, хотя в виду имеется, конечно, умножение содержимого регистра на константу.- Прим.

перев.

Сдвиг верхнего регистра влево