Устройство для умножения чисел в модулярной системе счисления

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 7/72

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4739093/24 (22) 21.09.89 (46) 30.07.91. Бюл. М 28 (71) Научно — исследовательский институт прикладных физических проблем им. А.Н.

Севченко (72) А.А. Коляда, И.Н, Кукель, В.В. Ревинский и M.Þ. Селянинов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1149254, кл. G 06 F 7/72, 1985.

Авторское свидетельство СССР

М 1325475, кл. G 06 F 7/72, 1986. (54) УСТРОЙСТВОДЛЯ УМНОЖЕНИЯ ЧИСЕЛ

В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

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

Цель изобретения .— повышение пропускной способности устройства.

На фиг. 1 представлена структурная схема устройства для умножения чисел в модулярной системе счисления; на фиг. 2 и 3— структурные схемы соответственно первого и второго блоков формирования вычетов; на фиг. 4 и 5- структурная схема блока формирования старшей части произведения; на фиг. 6- структурная схема блока усеченного формирования интегральных характеристик модулярного кода, Устройство для умножения чисел в модулярной системе счисления содержит первый 1 и второй 2 информационные входы, управляющий вход 3, установочный вход4 и тактовый вход 5 устройства, первый 6 и второй 7 входные регистры, регистр 8 сдвига, первый мультиплексор 9, блок 10 задержки, . Ж 1667065 А1 (57) Изобретение относится к вычислительной технике и предназначено для использования в быстродействующих специализированных вычислительных системах конвейерного типа, функционирующих в модулярной системе счисления, Цель изобретения состоит в повышении пропускной способности устройства. Наиболее существенными признаками устройства являются дополнительная группа параллельно — конвейерных блоков суммирования вычетов по модулям системы счисления и модифицированный блок формирования старшей части произведения с пропускной способностью два такта. 2 з. п. ф — лы, 6 ил. блок 11 модульных умножителей, первый 12 и второй 13 блоки формирования вычетов, второй мультиплексор 14, третью группу блоков 15 суммирования вычетов, регистр

16 кода младшей части произведения, блок

17 формирования старшей части произведения, вторую группу блоков 18 суммирования вычетов, блок 19 усеченного формирования интегральных характеристик модулярного . кода, первую группу блоков 20суммирования вычетов, выход 21 младшей части произведения, выход 22 старшей части произведения, выход 23 признака мультипликативного переполнения, сигнальный выход 24 и знаковый выход 25 устройства.

Блок 12 формирования вычетов реализуется на t = )К/2(долговременных блоках 26.1, 26.2...„26л памяти (см, фиг. 2, на которой приведены структура блока для К = 7).

Блок 13 формирования вычетов реализуется при помощи долговременных блоков памяти 27,1, 27.2, ..., 27К-1; 28.1, 28.2, ..., 28.r (r = (К/2Э и 29.J . s O = 2s-1, 2 s; s = 1, 2, ..., r".

r = )(К-1)/2((см. фиг. 3).

1667065

Блок 17 формирования старшей части произведения (фиг. 4, 5) содержит узлы вычисления цифр интервального индекса произведенияя по модулям, в состав которых . входят сумматор по модулю m> 30.0, сумматоры по модулю ml 31.0 — 31.К-1, вспомогательные регистры 32.0; 33.0 — 33.К-1, мультиплексоры 34.1 — 34. К-1, умножители по модулю пц 35,0 — 35.К-1, вычитатели по мбдулю е! 36,0 — 36.К-1, вспомогательные регистры 37.0 — 37.К-1, 38.0 — 38.К-1, первый

39 и второй 40 регистры, блоки 41.1 — 41.К деления на вспомогательный модуль, элементы И 42, схему 43 равенства кодов, элемент И вЂ” WIN-НЕ 44, элемент 45 задержки, Блок 19 усеченного формирования интегральных характеристик модулярного кода (см. фиг. 6) содержит блоки 46.1 — 46.К-2 памяти хранения констант, группу схем 47 сравнения с константой, регистр 48 и элемент И-ИЛИ вЂ” НЕ 49.

Рассмотрим назначение и примеры возможной реализации отдельных блоков.

Разрядность первого 6 и второго 7 входных

k регистров составляет L = bl бит. Здесь и ! ==1 ниже bl = )logZmlf (i = 1, 2, ..., К), где mt, тг, ..., mK — основания модулярной системы счисления, являющиеся попарно простыми целыми числами, т. е. (пц, m!) = 1, 1, J = 1, 2, ..„К; I Ф j, через )x(обозначается наименьшее число (целое), не меньшее х, Далее для простоты рассматривается случай, когда все модули mt, mz, ..., пц< являются нечетными.

Разрядность регистра сдвига составляет (Т+5) бит (где Т = )!ogZKf), выходы нулевого. первого, второго, третьего, (I + 2)-го и (Т+ 4)-го разрядов регистра 8 являются соответственно его выходами, Блок 10 задержки представляет собой цепочку Т+2 последовательно соединенных регистров разрядностью L — Ьк бит. Блок 11 модульных умножителей содержит умножители по модулям mt, m2, ..., тк.

S-e блоки памяти в блоке 12 обладают, емкостью

2 э гз Ье + К вЂ” 2$ бит,а е-емЬгэ — 1+ Ьгз

=2s — 1 костью2 " 1 х (Ьк-1+Ьк)битпричетном

bK — 1+ bk

К и емкостью 2 х Ьк бит при нечетном

bê

К. В ячейку блока памяти 26 s (s -1, 2, ..., t) с адресом s-1+) э 2ьгэ " для всех багз-)6 (О, 1, ..., вг -1 - 1) и у Zs6 (О 1, .„, агз - Ц записываетсЯ набоР величин !У ) =

*= С Цгв-1,8() 2s-1), Цгв, (y 2в-1 ) 2s) "° UK s

{) гз-1,) гз)>, где

I t

I Ф 2S -1,2S бит,и предназначеныдля получения набора вычетов ч =< VO,s() 2в- tс ) Zs)1 " VZs-2,в() 2з-1,Г 2s)в т)=

Чгв-1,з(йгв-1 ) 2з) Чгз.s() 2в-1, Йгз), Чгв+1,з() 2s- I ) гв) " VK-1,s() 2К-1 ) 2s)> в где

Vl,s() 2s-1, "г гз) = 1 R f,2ç-1(ггз-1) + R I,2s(Qs) l» (8) U2s- l,s(y 2з-1) = Йгз-1, Zs-1() 2з-1); (1)

Ul,s() 2в-11g 2s) =<(RI,2s-t() 2з-1)+ RI,2 2з) !П1, ((Rl,2s-1(гз-1) + Rl гз() 2в))/ml)>; I = 2s, 2s+ 1, ..., К-1, (2)

UK,s(j 2s-t, г гз) =I RK,2s-1ф 2з-1) + RK,ZS ®S$

/mK, (3)

Я1,1(у !) = 7 t, вычеты й),!(у ) (! = 1, 2, ..., );

j = 2, 3...Д К) определяется по формуле

io,; ф) = (и.,„),/„,,), k — 1 где Ml,к-1 = Мк-1/пц, Мк-1 = Д гп!, y I C (О, 1, I=1

15 ..„т!-1},в случае нечетного К полагается

) 2 = О и Ока ф гм, ) 21) = UK,ф Zt-1). При подаче на информационные входы блока.12 модулярного кода (у 1, у 2, ...,y к) числа С на выходах блока формируются наборы вели20 чин 01(С), UZ(C), ..., Ок(С), где

UI{C) = < Ul,t(t, 2) U1,2{7 з, 74), " l О!,!!г (уь1, yl) >, (5) если четно и

Ф(С) = <. Ь,i(yt, )2), ",, Ь,{ь1)/2()4-г, )И).

Ul,(н-!)/2{у I) >, (6) если i нечетно(! = 1,2, ..., К), Блок памяти 27.! (i = 1., 2, .„К-1) представляет собой блок памяти, к выходу кото30 рого подключен регистр для запоминания считываемой информации, при этом блок памяти 27.! обладает емкостью 2 слов разрядностью b! бит и служит для получения по входным величинам Q иф из множест35 ва {О, 1, ..., ть1) вычета R { а), pl), определяI емого по формуле (,(„p;)= — — "" и, „,к, 40 -г „р.

Емкости блоков памяти 28.s и 29.j,s () =

2s - 1, 2s; s = 1, 2, ..., r ) соответственно составляют

Ь I+42g, 2В ге

g-Q 1667065

I = О, 1, ..., 2s-2, 2s+1, ..., К-1;

Ч2з-1,в(Й2в-1 у 2в) = i 8 2з-1 + 2в-1,2s(y 2s) (П12з-1, (9)

Ч2з,s(y 2в-1 R2s) = I R2s,2з-1(y 2s-1) + 82з l

m2s, (10) у 2,-1 — величина, подаваемая на группы из

Ь2в-1 младших адресных шин блоков памяти

28.s и 29.2s.s;

У2в — величина, поДаваемаЯ на гРУппы

ИЗ b2s СтарШИХ адрЕСНЫХ ШИН бЛОКОВ ПаМяти 28.s и 29.2s-1.s;

R 2в-1 И R2s — СООтВЕтСтВЕННО МЛадШая И старшая части входных адресов блоков памяти 29.2s - 1s и 29.2s,s; вычеты R l(yi) (! = О, 1, ..., К-1; = 1, 2, ..., К-1; ! М !) определяются по формуле ! е,,(il :} т, М .«- " e»e >I,>

mp — вспомогательный модуль, выбираемый из условий тк > 2mp+ К-2, mp + К-1.

При четном К (именно этот случай пред, ставлен на фиг. 3) блок памяти 28.r обладает ь 1" 2 емкостью 2 " "х fbi бит (Ьо = )!о92то(1, !

=о причем в его память по адресу ук-1 записываются первые К-1 компонент набора вычеч" :, .»»,(о,)- ee*,, (12)

Процесс функционирования второго блока 13 формирования вычетов является двухтактовым. В ходе первого такта блоки памяти 27.1; 27.2, ..., 27. К-1 получают вычеты й! (а1, i|!I ), R2 (а2, Д ), ..., Rle-1 (а к-1ô к-1) (см. форм. 4), а на втором такте блоки памяти

28.1, 28.2, ..., 28.r и 29.).s 0 = 2s-1, 2s; s = 1, 2, ..., r ) по цифрам у 1, у 2, ..., у к модулярного кода входного числа С и величинам Ri = Ri, (а1ф 1),ïoñòóïàþùèì с выходов блоков 27 (i = 1, 2, ..., К-1), формируют на выходах второго блока 13 формирования вычетов искомые наборы вычетов

И, М)= "о. (У }(.1«V„(i! з4о}),-о /... (}(, fee,) > (13)

< Vi,1 (y 1 р 2). "° Vi,)1/2(-1 () 1-2 ) 1-1), ЧЦ1/2((Ri у I+1) Vi,)i/2(+1 (y i+2, р i+3), „„

Ч!,г (7 К-2, у К-1) >, ЕСЛИ НЕЧЕтНО;

< Че, 1 (y 1, у 2), ..., Че,o/2)-1 (/" I-3 y i-2), Vi,i/2 (y 1-1 Ri), Vi,(I/2)+1 (.y 1+1 г н-2), ..., Ч!,r(yК-2, рК-1), ЕСли чЕтнО. (14)

При четном К последние компоненты наборов (13) и (14) заменя ются на соответствующие вычеты вида (12).

Группа блоков 15 суммирования вычетов содержит два блока суммирования вычетов по модулям mp, m<, которые осуществляют сложение за Т тактов наборов из К вычетов по соответствующим модулям. Блоки 15 суммирования вычетов первой группы имеют

Т вЂ” каскадную конвейерную структуру и реа5 лиэуются известным образом.

Блок деления на вспомогательный модульь 41. I (I = 1, 2, ..., К) в блоке 17 реализуется на основе блоков памяти емкостью 2 о слов разрядностью bi+ 3 бит, в память кото10

bp рого по адресу д + I - r i I m 2 при I = 1, 2, „., К-1 и по адресу о+ ri k 2 при i = К для всех ур6 (0, 1, ..., mp -1) и qI6 (0, 1, ..., mi- 1) записывается набор величин

A ;,K,;) Е ...Е„), где

g,==(}- ()(- (")

1, если 9!= Ii lm;

20 й,/= (16)

О в рстальных случаях,  — (l;-e/.У., l „

25 ".о,-e«f»+I<-«,./»,, „/ /„«

//2«»,))" через (х) обозначается ближайшее к х целое число.

Элемент И 42 определяет признаки

Е 2 Š— 1 ° б гДе

k е =,Л Ее, e (-z,-f,o} (17)

35 а величины е !,/ (i = 1, 2, ..., К) определяются согласно (16).

Схема 43 равенства кодов предназначена для формирования признака е- признака равенства формального произведения

40 IClmle =(у1,) ...,,)1 ) константе — M=(0, О, ..., О,ик) по правилу

1, если !С!щ = — M, (18)

О в противном случае

45 К

"е«- П»«,, M=m*е «.„p«=/-nn/«»

Элемент 45 задержки осуществляет задержку на (T+1) такт.

50 Элемент И вЂ” ИЛИ вЂ” НЕ 44 реализует следующее булево соотношение

Р„Ä=6(C E. VE.E.,VЙ(с а, 55 (19) где О(С) 6 (О, 1) — поправка Амербаева, соответствующая произведению С = АВ в модулярной системе счисления с основани1667065

55 (27) Ями п11, Гп2, ..., пцс-1, mp, а ер (! = -2, -1, О) и е определяются согласно (17) и (18).

Группа блоков суммирования вычетов

18 содержит К+1 блок суммирования вычетов по модулям mO, m1, ..., тК. Блоки 18 5 суммирования вычетов группы имеют(Т

- 1)-каскадную конвейерную структуру и

1 осуществляют сложение за Т - 1 такт наборов вычетов по модулям mo m< и пц< без формирования, а по модулям mj (I = 2, 3...Ä 10

К-1) с формированием числа переполнений.

Блок 19 усеченного формирования ин. тегральных характеристик модулярного кода выполняет заключительную двухтактную стадию процесса определения интеграль- 15 ных характеристик модулярного кода.

Блок 46.1 памяти обладает емкостью ьз+1 л

2ьз бит, в его память по адресу Д + 2!з записывается двухзначная величина

$з = ((p + !з)/гпз) (20)

Блок памяти 46.j (I = 2, 3, ..., К-3) облада1 ет емкостью 2 т! двухразрядных слов (Т! = )!о92С! + 1)(), причем в его память по ! и -г л адресу о!+1 + 2 !!+2записывается набор 25 величин < д!+ 2, $!+2 >, где Sj+2 = д!+ 2в!+2, при этом !+2 = ((Я+1 + !)+2)/m!+2), (21)

О, если I pj,+1+iI+2 !е!+2 + mj+2 1

4+2 (22) 30

1 в остальных случаях, Блок 46.К вЂ” 2 памяти обладает емкостью

2bo + TK 2двухразрядных слов, в его память тк — 2" по адресу рк — 1+2 к записывается на- 35 бор величин < g, s>, где s= Av, при этом

w =(P к-1+ I)/mo), „(23)

О, если! рк — 1+! Imo W mo-1 д =,, (24)

1 в остальных случаях.

Группа 47 состоит иэ двух схем сравнения с константами. Первая и вторая схемы сравнения вырабатывают соответственно сигналы $о и до где и

/ 45

$o

О, если !к < mK — mo-К+ 2 (25)

1 в остальных случаях. до =

° °

О,если !к< тк-тр (26)

1 в остальных случаях.

Разрядность регистра 48 составляет 2 К3 бит.

Элемент И вЂ” ИЛИ вЂ” НЕ 49 реализует следующие булевы соотношения

О =Я „,27Ьк-г о к-1 8 V

$с. Д / гц; . (28)

Элемент И-ИЛИ вЂ” НЕ 49 может быть выполнен на основе программируемой логической матрицы, Группа блоков 20 суммирования вычетов содержит блоки суммирования вычетов по модулям mo, m>, ..., гпк, имеющие Т вЂ” каскадную конвейерную структуру.

Рассмотрим как работает предлагаемое устройство для умножения чисел в модулярной системе счисления.

По сигналу Го = 1, подаваемому с установочного входа 4 устройства, регистр 8 сдвига обнуляется, тем самым устройство приводится в исходное рабочее состояние.

В целях формирования необходимых управляющих сигналов сдвиговый регистр 8 ежетактно сдвигается на один бит в сторону старших разрядов по сигналу, подаваемому с тактового входа 5 устройства. Поэтому на (т + 1)-м такте инициированной операции умножения t-й разряд сдвигового регистра

8 будет установлен в единичное состояние: с = 1 (с = О, 1, ..., Т + 5).

Для инициации очередной мультипликативной операции по сигналу Г1 = 1, подаваемому с управляющего входа 3 устройства, в младший разряд регистра 8 сдвига записывается единица, а во входные регистры 6 и 7 поступают соответственно модулярные коды (а!, a2,..., at, ) операнда А и (,8, Pz, ..., Pt, ) операнда В, где А, В 6 D = (— М+ 1, — I4+ 2,..., — г1 —. 1, ) (а! = I A I mj,p = I B I mb = 1, 2, .... К; через

l Y lm обозначается наименьший неотрицательный вычет, сравнимый с величиной У по модулю m. Кроме того, код (P>, j4,..., Д.<,) через мультиплексор 9 (о о = О) передается в блок 10 задержки.

На первом такте операции блок 11 модульного умножения получает модулярный код (у1, у2, ° °,>,.)yi= la!a!mj !=1,2...„

К) младшей части (C) „произведения С чисел А и В, который по истечении данного такта может быть снят с выхода 21 младшей части произведения устройства. Запись кода числа С1йк в регистр 16 на текущем такте не происходит, так как 0 1 = О. Кроме того, на первом такте цифры модулярного кода { a1,a2,...,at.) через мультиплексор 14, на управляющий вход которого подается сигнал сг1 = О, поступает на вход группы блоков 20 суммирования вычетов, цифры модулярного кода {Р1, ф2...,, Д, ) подаются в блок 15 суммирования вычетов группы а код (a>,а, ...,а — 1,) через мультиплексор.9, на управляющий вход которого подается сигнал Его = 1, передается в блок

10 задержки. Группы блоков 15 и 20 суммирования вычетов в течении очередных Т так1667065

10 тов, считая текущий, формируют соответственно наборы вычетов < Ло(А), Л1(А), ..., Лк- (А), 1к(А) > и < Ло(В), lк(В)>, при этом

I х-(w-

Л,(х1-(;Е К,; (х:1 Л1(х1 =)K 1,(x !1 ; = ë,.„ê-<; 5 " lgl-™;". "l.. !.":.,И .. где R i(x) (I = О, 1, ..., К-1 определяются 10 согласно (5);

lp(x) — машинный интервальный индекс числа Х Е0;

Xi- X! пц,1= 1, 2...„К, В ходе второго такта операции из пер- 15 вого разряда сдвигового регистра 8 на управляющий вход мультиплексора 14 подается сигнал oi = 1, поэтому цифры модулярного кода (g>, jb,..., Д) с выхода второго входного регистра 7 поступают в блоки 20 сумми- 20 рования вычетов, которые начнут вычисление набора вычетов < Ло(В), Л (В), ..., Лк- (В), 1к(В) >

В регистр 16 кода младшей части произведения записы вается код числа ! С!у поступающий с выхода блока 11 модульных умножителей (й = 1). Кроме того, на данном такте операции на информационные входы блока 13 формирования вычетов с выходов первого 6 и второго 7 входных регистров соответственно поступают коды ( а>, а,..., ак — 1, ) и (8>, Д,..., Д вЂ” g (см. фиг. 3), поэтому по истечении второго такта в выходном регистре блока памяти 27.1(i = 1, 2, ..., К-1) будет сформирован вычет Ri(Q, Pi ) (см. форм. 7), На третьем такте модулярный код (у1, р,...;у, ) числа С !М„с выхода рЕгистра 16 кода младшей части произведения поступает на информационный вход блока 13 формирования вычетов, на второй управляющий вход которого подается единичный сигнал о2=1(cM. фиг.3). Поэтому на выходе блока 13 будет сформирован набор величин 45

Ч,(С), V)(C,R "(а1ф )), . „V к- (С, RK-1 "(ак-1, Вк-1) (см. форм. 7 — 14), который передается в блоки 18 суммирования вычетов через второй вход.

На четвертом такте операции моду- 50 лярный код числа !С!и с выхода регистра 16 поступает на информационный вход блока 12 формирования вычетов, на управляющий вход которого с выхода сдвигового регистра 8 подается сигнал îз55

= 1 (см. фиг. 2). По истечении данного такта на выходе блока 12 будет сформи-. рован набор величин U>(C), Uz(C), ..., 0к(С) (см. форм. 1 — 6), который переда° ется в блоки 18 суммирования вычетов.

Параллельно с этим на четвертом такте модулярный код (y>, y,..., у1,, ) числа ! С !11к с выхода регистра 16 кода младшей части произведения через информацион. ный вход блока 17 формирования старшей части произведения поступает на вход схемы равенства кодов 43(см. фиг. 5), на выходе которой формируется признак а (см. форм.

18), пересылающийся в элемент 45 задержки.

По истечении Т-го такта на выходах блоков 20 и 15 суммирования вычетов будут получены наборы вычетов < Л,(А), Л1(А)...„

Лк- (А),1к(А) > и < Ap(B), 1к(В)>, которые на (Т+ 1) — м такте передаются в блок формирования старшей части произведения (фиг. 4).

При этом величины Ло(В) и 1к(В) поступают на входы первого сумматора по модулю mp

30.0 A) и Л (А) (i = 1, 2, ..., К-1} — на вторые входы второго сумматора по модулю mp 30.0 и сумматора по модулю mi 31.1 соответственно, а lк(А) — на первые входы этих сумматоров. В результате во вспомогательных регистрах 32,0 и 33.0 формируются вычеты

Hp(B) = 11(B) + Ap(B) I mp и я p(A} =! 1(A) +

+ Л p(A) mp, а во вспомогательном регистре

331 — вычет ру i(A) =! 1(A) + Л i(A)Imi для всех i 1, 2, ..., К-1. Здесь через I(X} обозначается интервальный индекс числа Хб D, который связан с машинным интервальным индекса(ч I(X), следующим соотношением (к (Х), если 1к (Х) < my, — mp - К + 2

lк (Х) =

lк (Х) - тк, в противном случае.

По истечении (Т + 1)-го такта операции умножения группа блоков 20 суммирования вычетов получит набор вычетов < Ло(В), hz(B), ..., Лк- (В), 1к (В)>, который на (Т+ 2)-м такте пересылается в блок 17 формирования старшей части произведения, на информационный вход которого в это же время с выхода блока 10 задержки поступает код (P<, j4,..., j3p — g вследствие чего сумматор по модулю mi 31.1 находит величину Hi(B) =

= l(B)+ Л (В) mi(i = 1, 2, ..., К-1). Параллельно с этим модульные умножители 35,0 по модулю mp и 35.1 по модулю т; получают соответственно величины Ho = !1(к-i Ho(B)Ho(A)t

mp u IP iHi(A) Imi (i = 1, 2, ..., К-1), которые записываются во вспомогательные регистры 37.0 и 37.i(см. .фиг. .4). .По окончании. (Т + 2)-го такта группа блоков 18 суммирования вычетов получит набор вычетов < Л (С), I Л (С) + R1 (а,Pi ) Imi, ..., !

Лк- (С) + RK-1 (а — s, Д вЂ” () Imi-», который на (Т + 3) — ем такте передается в блок 17 формирования старшей части произведения, На информационный вход блока 17 с вы1667065

12 хода блока 10 задержки поступает код (а1, а,..., а! — q, ) Вычет Л О(С) вместе с содержимым Но вспомогательного регистра

37.0 поступает на входы вычитателя по модулю

m 360, который завершает формирование

ЦИФРЫ 11„= ) Но — Ле,(С) Imp ÈÍòÅÐÂàËÜÍOÃO индекса 1(С) произведения С = АВ по модулю

m . Так как на(Т+3) — ем такте на управляющий вход блока 17 формирования старшей части произведения подается сигнал от+2 = 1, который подается на управляющие входы мультиплексоров 34.1, то вычет I Ë(C) + В! (а!, p!) )т! через информационный вход группы мультиплексоров 34.1 поступает на первый вход вычитателя. по модулю т! 36.1 (1 = 1, 2, ..., К-1), на второй вход которого из вспомогательного регистра 37.1 подается вычет IP !Н!(А) I ть в результате во вспомогательном регистре 38.1 сформируется величина

H =j А;(с + и,(м; Я;)-P; w; (AI I „

Параллельно с этим умножитель по модулю

m; 35,1 получает вычет )а1Н!(В) I ml, который передается во вспомогательный регистр

37.1(1 = 1, 2, ..., К-1). По окончании (T + 3)-ro такта группа блоков 18 суммирования вычетов получает наборы величин <13(С), 14(С), ..., 1К(С) > и р 2(С), р 3(С), ... p К 1(С), где е () I Q R е, е х; )

РеЕ 1=(-, ее|И),е-ел,„,к; а В!,!(Х!) определяется согласно форм, (4), На (T+ 4) — м такте вычет qp из вспомогательного регистра 38,0 пересылается в первый регистр 39, вычет Н! с выхода вспомогательного регистра 381 через информационный вход группы мультиплексоров 34.1 (стт+2 = О) поступает на первый вход вычитателя по модулю m; 36, 1, на второй вход которого из вспомогательного регистра 371 поступает вычет ) а !Н!(В) I гл!, Модульный вычитатель 36.1 получает величину I -y I m! =

- )(Н! - а!Н!(В) lm!, являк)щуюся дополне1 нием цифры 1 интервального индекса I(C) числа С по модулю тпь Вычет I — д! )тп! записывается во вспомогательный регистр 38.1 (1 = 1, 2...,, К-1). Параллельно с этим наборы величин < Ъ(С), 14(C), ..., !К(С) > и < p2(C), рз(С), ...,p к-1(С) > группы блоков 18 суммирования вычетов поступают на соответствующие входы блока 19 усеченного формирования интЕгральных характеристик модулярного кода, на третий вход которого из вспомогательного регистра 38,0 блока 17 формирования старшей части произведения поступает вычет

1 О. Вычет lK(C) с выхода группы блоков 18

55 суммирования вычетов также пересылается в блок 17 во второй регистр 40(см. фиг. 5). В блоке 19 усеченного формирования интегральных характеристик модулярного кода (см. фиг, 6) блока памяти хранения констант

46.1, 46.2, ..., 46.К-2 и группа схем 47 сравнения с константой формируют набор двухзначных признаков < $3 $4 до " SK-;, дк 1, S, д, Sp, до>, которые передаются в регистр

48 (см. форм. 20 — 26).

На заключительном (Г+5)-м такте работы устройства элемент 49 (см. фиг. 6) по набору признаков < $3, $4, ä4 "., SK-1, дк-1, S, д, Sp, до>, поступающему на ее входы с выходов регистра 48 завершает формирование поправки Амербаева О(С) и знаковой функции s(C) (см, форм. 27 и 28). Знак з(С) с выхода блока 19 усеченного формирования интегральных характеристик модулярного кода передается на знаковый выход 25 умножителя, а поправка О(С) поступает на информационный вход блока 17 формирования старшей части произведения произведения, Параллельно с этим в блоке 17 (см. фиг.

5) вычет до из первого регистра 39 поступает на первые входы блоков деления на вспомогательный модуль 41,1, 41,2, .„, 41.К. На вторые входы блоков 41,1 (i = 1, 2, ..., К-1) и 41.К подаются соответственно величины I -т1! I mi из вспомогательного регистра 38 и gK = lк(С) из второго регистра 40. В результате блок деления на вспомогательный модуль 41.1(i = 1, 2, ..., К) на первом выходе получает i— - ю цифру

} целочисленного приближения к дроби AB/1 по формуле (15), а на втором выходе — набор признаков (е-г,i, е — 1,i, е — oö )(см, форм.(16), поступающий на входы элемента И 42, где определяются признаки е — 2, е — 1, ео (форм. 17).

Признаки е —, е — 1, е — 0 поступают на первый вход элемента 44, на второй и третий входы которого подаются величины О(С) и е. Элемент 44 формирует признак мультипликативного переполнения Я и (см. форм. 19), передающийся на выход 23 устройства. Модулярный код (у1, y2 „.. $, ) старшей части Со произведения С = A8 снимается с первых выходов блоков деления на вспомогательный модуль 41,1, 41,2, ..., 41. К и поступает на выход 22 устройства, Признаком конца операции умножения служит единичный сигнал еуе =&+y 1, появляющийся на сигнальном выходе 24 устройства, Инициация очередной мультипликативной операции в описанном устройстве для умножения чисел в модулярной системе счисления может быть осуществлена уже на втором такте текущей операции, т. е, максимальная частота обращена к данному умножителю

1667065

10 t5

25

35

45

55 составляет fz = 1/(2t r) (1 и — длительность модульного такта).

Формула изобретения

1. Устройство для умножения чисел в модулярной системе счисления, содержащее первый и второй входные регистры, два мультиплексора, блок задержки, блок модульных умножителей, регистр сдвига, регистр кода младшей части произведения, первую и вторую группы блоков суммирования вычетов, блок формирования старшей части произведения и блок усеченного формирования интегральных характеристик модулярного кода, первый выход которого соединен со знаковым выходом устройства, первый и второй информационные входы которого соединены соответственно с информационными входами первого и второго входных регистров, управляющие входы приема кода которых соединены с информационным входом регистра сдвига и уп равляющим входом устройства, установочный и тактовый входы которого соединены соответственно с входами сброса и управления сдвигом регистра сдвига, выход первого входного регистра соединен с первыми информационными входами первого и второго мультиплексоров и первым входом блока модульных умножителей, второй вход которого соединен с выходом второго входного регистра и вторым информационным входом второго мультиплексора, управляющий вход которого и управляющий вход приема кода регистра младшей части произведения соединены с первым входом регистра сдвига, второй выход которого соединен с.управляющим входом первого мултьтиплексора, выход блока модульных умножителей соединен с информационным входом регистра младшей части произведения, выход второго мультиплексора соединен с входами блоков суммирования вычетов первой группы, выходы которого соединены с первым информационным входом блока формирования старшей части произведения, второй информационный вход которого соединен с выходом блока задержки, второй выход блока усеченного формирования интегральных характеристик модуля рного кода соединен с третьим информационным входом блока формирования старшей части произведения, четвертый информационный вход которого соединен с первыми выходами блоков суммирования вычетов второй группы и первым входом блока усеченного формирования интегральных характеристик модулярного кода, второй вход которого соединен с вторыми выходами блоков суммирования вычетов второй группы, третий выход регистра сдвига соединен с управляющим входом блока формирования старшей части произведения, первый и второй выходы которого соединены соответственно с выходами старшей части произведения и признака мультипликативного переполнения устройства, сигнальный выход которого соединен с четвертым выходом регистра сдвига, о тл ич а ю ще е с я тем, что, с целью повышения пропускной способности устройства, в него введены два блока формирования вычетов и третья группа.блоков суммирования вычетов, вход которых соединен с выходом второго входного регистра, а выходы — с пятым информационным входом блока формирования старшей части произведения, шестой информационный вход которого соединен с выходом регистра младшей части произведения и первыми информационными входами первого и второго. блоков формирования вычетов, выходы первого и второго входных регистров соединены соответственно с вторым и третьим информационными входами второго блока формирования вычетов, первый и второй управляющие входы которого соединены соответственно с первым и пятым выходами регистра сдвига, шестой выход которого соединен с управляющим входом первого блока формирования вычетов, выходы первого и второго блоков формирования вычетов соединены соответственно с первым и вторым входами блоков суммирования вычетов третьей группы, третий вход блока усеченного формирования интегральных характеристик модулярного кода соединен с третьим выходом блока формирования старшей части произведения, выход блока модульных умножителей соедйнен с выходом младшей части произведения устройства, второй информационный вход которого соединен с вторым информационным входом первого мультиплексора, выход которого соединен с входом блока задержки.

2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок формирования старшей части произведения содержит К узлов вычисления цифр интервального индекса произведения по модулям ml (К вЂ” число оснований модулярной системы счисления;

J = О, 1, ..., К-1), два регистра, К блоков деления на вспомогательный модуль, элемент И, схему равенства кодов, элемент задержки и элемент И вЂ” ИЛИ вЂ” HE, причем узел вычисления цифр интервального индекса произведения гю модулю mo содержит два сумматора, умножитель и вычитатель по модулю а и четыре вспомогательных регистра, при этом выход первого сумматора по модулю mo через первый вспомогательный регистр соединен с первым входом умножителя по модулю mq, второй вход которого через вто15

1667065

16 рой вспомогательный регистр соединен с выходом второго сумматора по модулю m<, выход умножителя по модул ю mo через третий вспомогательный регистр соединен с . первым входом вычитателя по модулю m<, выход которого соединен с входом четвертого вспомогательного регистра, а узел вы числения цифр интервального индекса произведения по модулю <тц (i = 1, ..., К-1) содержит сумматор, вычитатель и умножитель по модулю пц, три вспомогательных регистра и мультиплексор, выход которого соединен с йервым выходом вычитателя по модулю т, выход которого через первый, вспомогательный регистр соединен с пер, вым информационным входом мультиплек .сора; выход сумматора по модулю mi через второй вспомогательный регистр соединен с первым входом умножителя по модулю пц, выход которого через третий вспомогатель-! ный регистр соединен с вторым входом вычитателя по модулю m, управляющие входы мультиплексоров узлов вычисления цифр интервального индекса произведения по модулю mi объединены и соединены с управляющим входом блока, первый информационный вход блока соединен с входами второго сумматора узла вычисления цифр интервального индекса произведения по модулю m< и входами сумматоров узлов вычисления цифр интервального индекса произведения по модулю mt, пятый информационный вход блока соединен с входами первого сумматора узла вычисления цифр интервального индекса произведения по модулю п1О, второй вход вычитателя которого и вторые информационные входы мультиплексоров узлов вычисления цифр интервального индекса произведения по модулю

mi соединены с четвертым информационным входом блока, второй информационный вход которого соединен с вторыми входами умножителей узлов вычисления цифр интервального индекса произведения по модулю пц, выходы первых вспомо ательных регистров которых соединены соответственно с входами делителя с первого по (К-1) блоков деления на вспомогательный модуль, выход четвертого вспомогательного регистра узла вычисления цифр интервального индекса

5 произведения по модулю m< соединен с третьим выходом блока и Входом первого регистра, выход которого соединен с входами делимого К блоков деления на вспомогательный модуль, первые входы которых

10 соединены с первым выходом блока, второй выход которого соединен с выходом элемента И вЂ” ИЛИ-НЕ, первый входкоторогосоединен с выходом элемента И, входы которого соединены соответственно с вторыми вы15 ходами К блоков деления на вспомогательный модуль, а второй — с выходом элемента задержки, вход которого соединен с выходом схемы равенства кодов, вход которой соединен с шестым информационным вхо20 дом блока, третий информационный вход которого соединен с третьим входом элемента И вЂ” ИЛИ-НЕ, второй вход К-го блока деления на вспомогательный модуль соединен с выходом второго регистра.

25 3. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок усеченного формирования интегральных характеристик модулярного кода содержит К-2 блоков памяти хранения констант, группу схем сравнения с констан30 той, регистр и элемент И-ИЛИ-НЕ, первый и второй выходы которого соединены соответственно с первым и вторым выходами блока, второй вход которого соединен с первыми адресными входами (К-2) блоков

35 памяти хранения констант, выходы которых и выходы схем сравнения с константой группы соединены с соответствующими входами регистра, выходы которого соединены с входами элемента И вЂ” ИЛИ-Н Е, пер40 вый вход блока соединен с вторыми адресными входами с первого по (К-3) блоков памяти хранения констант и входами схем сравнения с константой группы, третий вход блока соединен с вторым адресным

45 входом (К-2) — ro блока памяти хранения констант.

1667065

1667065

1667065

1667065

Раг. 5

Составитель Е, Мурзина

Техред M.Ìîðãåíòàë Корректор О. Кундри к

Редактор О.Спесивых

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Заказ 2524 Тираж 398, Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5