tflipaenemw для X

управление

для у управление

дляг

Тактовые часы

Рис. 2.5. Триггер с тремя входами.

Перевести с в

Перевести 0» левый сдвиг А

Перевести С в левый сдвиг В

Р и с 2 6 Сдвиг регистра или прибавление содержимого регистра к содер жимому другого регистра.

гер регистра С имеет три возможных входа, а именно «левый сдвиг содержимого Л-регистра», «левый сдвиг содержимого 5-регистра» и «покомнонентная сумма содержимого регистров А и 5». Заметим, что сигналы управления «перевести С в А @ В», «перевести С в левый сдвиг Л» и «перевести С в левый сдвиг В» подаются в каждый триггер регистра С. Таким образом, соответствующий сигнал команды воздействует сразу на весь регистр С.

Цепь, изображенная на рис. 2.6, является двухтактовой, так как тактовые сигналы для регистров А, В и С яе совпадают. Регистры Л я В должны управляться только в течение одного такта.

перевести Met

Перевести L в "м или сдвигм

£

Перевести L в "ми сдвигМ"

Рис. 2.7. Регистр для выполнения операций логического умножения «М И левый сдвиг М» и логического сложения «М ИЛИ левый сдвиг М».

а регистр С - в течение другого. Такое использование тактовых часов исключает любые состязания и связанные с этим нарушения функционирования, которые могут возникнуть, если попытаться устанавливать состояние самого регистра и одновременно использовать его выход для установления еще какой-нибудь команды.

Сдвиг регистра А влево осуществляется в два шага. Сначала в регистре С устанавливается команда левого сдвига регистра А, а затем это управляющее воздействие передается на регистр А. Полная операция реализуется за две временные фазы или один полный временной цикл. Подобным же образом осуществляется сложение содержимых регистров А и В или сдвиг влево регистра В. Каждая из этих операций также занимает один временной цикл. Аналогично, в схеме рис. 2.7 регистр М работает в одной фазе временного цикла, а регистр L - в другой фазе. Эта цепь позволяет ])еализовать операции типа «М И левый сдвиг М» и «М ИЛИ левый сдвиг М». Каждая из этих операций занимает также один временной цикл. Наконец, на рис. 2.8 изображена схема, выполняющая несколько более сложную операцию, а именно реализующая команду «записать символы В, расположенные слева от наиболее левого

нуля В М, В соответствующие позиции С». Эта команда является второй фазой в полном цикле команд «прибавить к соответствующим

Записать символы В, расположенные слова от наиболее левого нуля в М, в соответствующие позиции С

Рис. 2.8. Схема для выполнения более сложной команды.

символам В те символы А, которые расположены слева от наиболее левого нуля в регистре М». Нетрудно сконструировать аналогичные

Сдвиг А влево

Прибавить Вк А

X и левый сдвиг X Рис. 2.9. Сокращенное обозначение логических схем.

схемы, реализующие и другие простые логические операции подоб-. ного типа.

Так как диаграммы, примеры которых представлены на рис. 2.6- 2.8, употребляются все чаще, то намечается тенденция к использо-: ванию для них сокращенных изображений, приведенных на рис. 2.9. В этих изображениях опускаются множество управляющих команд f и регистры второго такта временного цикла.

*2.3. Мультипликативное обращение

Рассмотрим теперь задачу определения мультипликативного обратного для элементов поля классов вычетов по модулю некоторого неприводимого двоичного многочлена М (х) степени т. Для заданного класса вычетов, содержащего многочлен г (х) степени < т, необходимо найти такой многочлен р (х) степени <; т, чтобы их произведение удовлетворяло сравнению

г (х) р (х) = 1 mod М (х),

что эквивалентно равенству г (х) р {х) + М (х) g (х) = 1 для некоторого многочлена q (х). Так как М (х) неприводим, то н.о.д. М и г равен единице. Следовательно, можно применить вариант непрерывных дробей алгоритма Евклида, описанный в разд. 2.1. Начиная с r-> = М, г-1> = г, р<-2 = О, р<-1 = 1, д<-2> = 1, g-i) = О, используем алгоритм определения а< и г<-\ таких, что

r(- 2) = а()г(-1) + rW, deg rW < deg r-1). Затем полагаем

q(k) + q(>~),

p(ft) a(ft)p(ft-1) p(ft-2)

Итерацию продолжаем до тех пор, пока не получим г" = 0. При

этом решение задается равенствами

q = g<"-i.

Р = Р

(П-1)

deg g < deg г и deg р < deg М = т. Так как нам необходимо найти только р (q практически нам не нужно), то можно обойтись только величинами (р*}.

Прежде чем переходить к логическим устройствам, рассмотрим пример. Предположим, что г (х) = х* + х + I и М (х) = х + -f х + 1. Один из возможных методов вычисления а*, г*» и состоит в следующем:

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

г(-2) 1а;б 0а;4 -{-. Ох -}- 1x2 + Ох + 1, г<-1> = 0x5 0x3 + 0x2 + 1х +1,

г<-> = 1x5 + Ох* + 0x3 + 1а;2 4- Ох +1, хг-" = 1x5 Qi 0а;3 1а;2

г<-« . хг- 0x5 Ох« + Ох» + 0x2 -Ь 1х + 1, хг<-" =--: 1x5 4. Qi 0x3 ia.2 la-

а° = х.

г" = Ох* -f 0x3 + 0x2 -f 1х +1, г-" = 1х* + 0x3 + 0x2 + 1х -f 1,

г<°=1х + 1, г<»=0х+1,

•"» = 1х+1,

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

хр<-" =

х/?<-" = хр-" + р-" = <-о -

хг<» = 1х,

г«» + х/-<» = 0хН хг"> = 1х,

г<»> + хг<» = 1, г<" = 1,

г"" + (х+1)г"> = 0, г<"=1.

-Ох Ох

+ 0х,

+ 1х,

+ 0х, + 1х,

+ 0x2,

+ 1X2,

а<==х + 1.

(0)

г" = 0, г<" = 1.

В данном случае, очевидно, получаем

г<-2=х5 + л:2+1, г-" = х* + х +1,

=х+1, ,

г<" = 1, г> = 0,

а°=х,

„(1) 3

a;.J+x2 + x,

а< = х + 1.

1 +0х +0x2 -Ь 0x3,

0x2+1x3,

1 + 0x4-0x2+ 0x3 +Ох*, 0x3 + 14

1 +Ох+ 0x2+ 0x3 +1.4 0x3 j

1 + 0х + 0х2 + 0хЗ + 1х*, 0x2+ 1x3 +Ох*,

Ох + 0x2 + 1х + 1х*, 0x2 1а:3 Ох*,

р<-1) + (а;3 + а;2) р» = 1 + Ох + 0x2 + 1хЗ + 1х*,

Ох+1x2+ 0x3 +Ох*,

0х+1х2 + 1хЗ + 1х*, Ох+1x2+ 0x3 +Ох*,

1 + 0х + 1х2 + 1хЗ + 1х*, 0 + 1х + 0х2 + 0хЗ + 0х*,

Х2р«":

хЗр<»> =

+ хЗр"» хЗр<»

(-1) [ а;3р«

Х2р (Х3 + Х2) р«"

,(0)

D<--"(X3 + X2+X) р"» ,0) -

= l-J-i

хр" =

р<1=

„(0) 1

Начиная с р<"2)о и р<-" = 1, для величин имеем

Р<-=-=0, р<-» = 1,

= X,

Р»=1+Х2 + Х3 + Х*,

р<2> = 1 а;2 + х

Чтобы избежать запоминания коэффициентов а*", целесообразно выполнять эти вычисления одновременно с вычислением г*". Это позволяет записать

а;г<»> = Ох* + Ох» + 1х« + 1х, г-» = 1х* + 0x3 + 0x2 + 1х +1,

xV" = 0x + 1x3 +1x2, r<-" = lx* + 0x3 + 0x2-f lx+1,

xV» = lx* + lx»,

Г-I = Ix* + 0x3 ц 0a;2 -f la; +1,

г-" + хг"» = Ox* + ix* + 0x2 + Ix +1,

xV 1x3+ 1x2, r<-i + хг» = 1x3 4- 0x2 f la; +1,

X2r«» = lx3 + lx2, r<-l) 4- (x3 + X2) r<° = 0x3 -f- 1x2 + Ix + 1,

Xr<°> = 1x2 + Ix,

r<-" + (a + a;2) r<°> = 1x2 + Ix +1,

Xr"» = lx2+lx, r<-l + (x3 + X2 + X) r°> = 0x2 + Ox + 1,