Устройство для умножения чисел в модулярной системе счисления Советский патент 1991 года по МПК G06F7/72 

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

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

На фиг. 1 представлена структурная схема устройства для умножения чисел в модулярной системе счисления; на фиг. 2 и 3 - структурные схемы соответственно первого и второго блоков формирования вычетов; на фиг. 4 и 5 - структурная схема блока формирования старшей части произведения; на фиг. 6 - структурная схема блока усеченного формирования интегральных характеристик модулярного кода.

Устройство для умножения чисел в модулярной системе счисления содержит первый 1 и второй 2 информационные входы, управляющий вход 3, установочный вход 4 и тактовый вход 5 устройства, первый 6 и второй 7 входные регистры, регистр 8 сдвига, первый мультиплексор 9, блок 10 задержки,

блок 11 модульных умножителей, первый 12 и второй 13 блоки формирования вычетов, второй мультиплексор 14, третью группу блоков 15 суммирования вычетов, регистр

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

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

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

Блок 12 формирования вычетов реализуется на t К/2 долговременных блоках 26.1,

26.2 26.t памяти (см. фиг. 2, на которой

приведены структура блока для К 7).

Блок 13 формирования вычетов реализуется при помощи долговременных блоков

памяти 27.1,27.227К-1, 28.1, 28.2,.... 28.г

(г К/2) и 29J . s(j 2s-1,2s; s 1,2г1;

)/2(см. фиг. 3).

w

Ё

(

О

VI о о ел

Блок 17 формирования старшей части произведения (фиг. 4, 5) содержит узлы вычисления цифр интервального индекса произведения по модулям, в состав которых входят сумматор по модулю т0 30.0, сумматоры по модулю mi 31.0 - 31.К-1, вспомогательные регистры 32.0; 3X0 - ЗЗ.К-1, мультиплексоры 34.1 - 34.К-1, умножители по модулю mi 35,0 - 35.К-1, вычитатели по модулю mi 36.0 - 36.К-1, вспомогательные регистры 37.0 - 37.К-1, 38.0 - 38.К-1, первый 39 и второй 40 регистры, блоки 41.1 - 41.К деления на вспомогательный модуль, элементы И 42, схему 43 равенства кодов, элемент И-ИЛИ-НЕ 44, элемент 45 задержки. Блок 19 усеченного формирования интегральных характеристик модулярного кода (см. фиг. 6) содержит блоки 46.1 - 46.К-2 памяти хранения констант, группу схем 47 сравнения с константой, регистр 48 и элемент И-ИЛИ-НЕ 49.

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

k

регистров составляет L bi бит. Здесь и

I 1

ниже bi 1од2ГП| (1 1,2 К), где гти, та,

..., тк - основания модулярной системы счисления, являющиеся попарно простыми целыми числами, т. е. (mi, mj) 1, i, J 1, 2, .... К; I / J, через х обозначается наименьшее число (целое), не меньшее х. Далее для простоты рассматривается случай, когда все модули mi, m2тк являются нечетными.

Разрядность регистра сдвига составляет (Т+5) бит (где Т 1од2К), выходы нулевого, первого, второго, третьего, (Т + 2)-го и (Т + 4}-го разрядов регистра 8 являются соответственно его выходами.

Блок 10 задержки представляет собой цепочку Т+2 последовательно соединенных регистров разрядностью L - Ьк бит. Блок 11 модульных умножителей содержит умножители по модулям mi, m2тк.

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

U2s-1,s( У 2s-l) R2s-1. 2s-l(y 2s-1);(1)

U|,S(X 2s-1,y 2s)|Rl,2s-l(y 2s-l) + Rl,2s(y 2s) Imi, (Ri.2s-i(X2s-i) + Ri.2s(y2s))/mi ; I 2s, 2s+ 1, ...,K-1,. (2)

UK,s(y2s-1. У2з)1 RK,2s-l(y 2s-l) + RK.2S (У28У /mK, (3)

Ri,i(yi) yi; вычеты RJ,I( yi) (I 1, 2J;

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

Mfl-ЙК.нГ.-Н,1

k-1

(4)

гдеМ|.к-1 Мк-1/mi, Мк-1 П mi.yi 6(0, 1,

I 1 ..., mi-i},B случае нечетного К полагается

У21 О И UK,t {у 2М, У21) - UK,t(y 2t-l). При

подаче на информационные входы блока 12

модулярного кода (у i, у гу к) числа С на

выходах блока формируются наборы величин Ui(C), U2(C)UK(C),

где

Ul(C) Ul,l(y 1, у 2,), Ul.2(y 3, У 4), ...i U|,|/2

(yi-i,yi).(5)

если I четно и Ui(C) Ui,i(yi, y2) Ui.(i-i)/2(yi-2, УМ),

Ul,(l+1)/2(X l) .(6)

если i нечетно (I 1,2К).

Блок памяти 27.1 (1 1,2К-1) представляет собой блок памяти, к выходу кото- РОГО подключен регистр для запоминания считываемой информации, при этом блок

памяти 27.I обладает емкостью 22Ь| слов разрядностью bi бит и служит для получения по входным величинам аи и/ft из множест- ва {0, 1,..., тм} вычета R (O) ,/3i), определяемого по формуле

,;.

lMl«-. „..я

Емкости блоков памяти 28.s и 29.J.S 0

2s - 1, 2s; s 1, 2 г1) соответственно

составляют

(2.5-1+Ь гб

К-

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

2b2S-i+b2s/ 2be + K-2SW,atfreMN 2s-1 r

костью 2ьк-1 + bk x ( + Ьк) бит при четном К и емкостью 2Ьк х Ьк бит при нечетном К. В ячейку блока памяти 26.s (s 1, 2, ...,

t) с адресом yzs-i + y2S 2b2S 1 для всех

У2з-)€ { 0, 1ГП28-1 - 1} И у 2s6 {0. 1,

.... m2s -1} записывается набор величин LTS

- U2s-1,s(y 2s-1), U2s,s(y 2s-1, У 2s)UK.S

(У 23-1. У 2s) , где

I 2S- 1,2S бит, и предназначены для получения набора вычетов

Г° Vo,sO/2s-1, У28)V28-2,sO/2s-1,y 2s).

V2s-1,s(R2s-1,y 2s), V2s.s(X2s-1. R2s), V2s+1.s(y2s-1,y2s)VK-1,s(X2K-1, У2в) .

где

V|,S(X 2s-1, У2з) I R l.2s-l( У28-1) + R l.2s( 2s)V

(8)

1 0, 12s-2, 2s+1K-1;

V2s-1,s(R2s-1,y 2s) I R 2s-1 + R 2s-1,2s(y 2s) I m2s-1,(9)

V2s,s(y2s-1, R2s) I R2s,2s l(X2s-l) + R2s I

m2s;(10)

У 2з-1 - величина, подаваемая на группы из Ь2з-1 младших адресных шин блоков памяти 28.S и 29.2s.s;

y2s - величина, подаваемая на группы из b2s старших адресных шин блоков памяти 28.s и 29.2s-1.s;

R 2s-i и R2s - соответственно младшая и старшая части входных адресов блоков памяти 29.2s - 1s и 29.2s.s;

вычеты R i.i(yi)(l 0, 1K-1; i 1, 2K-1;

I Ґ I) определяются по формуле

.i

i

m;

4 M.

V

-J;

m;

to

e (11)

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

При четном К (именно этот случай представлен на фиг. 3) блок памяти 28. г обладает

ь -1 k 2 емкостью 2 k х У bi бит (Ь0 log2m0),

I 0

причем в его память по адресу ук-1 записываются первые К-1 компонент набора вычет°вvw- v.,(r«.).v.r(M. Л.Л..),

v,,,. .), r «vii«,).R,, ,i(. . ,fj);

v.,,«.,).,(12)

Процесс функционирования второго

блока 13 формирования вычетов является

двухтактовым, В ходе первого такта блоки

памяти 27.1,27.227. К-1 получают вычеты

Ri1(ai .# )- R21( 02 ,02 )RK-I WiЈ к-i)

(см. форм. 4), а на втором такте блоки памяти

2г ) по цифрам у 1,у2,.... у к модулярного

кода входного числа С и величинам Ri Ri1, (2i .поступающим с выходов блоков 27.1

(I 1, 2 К-1), формируют на выходах

второго блока 13 формирования вычетов искомые наборы вычетов иV.,(f.,ft).VW.r«)«

ta

0,г (|Гк-1| fK-lP

(13)

V|,t(yi,y2)V|,(yi-2, У1-1),

V|,l/2f(R|, У|-И), V|. (УМ, )

Vi,r (у к-2, У к-0 , если i нечетно;

V|, 1 ( у 1, у 2)V,.(i/2)-1 ( У i-З, У 1-2),

Vl,i/2(yi-1, Ri), V,,(,/2K1 (У1+1.УН-2)

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

Группа блоков 15 суммирования вычетов содержит два блока суммирования вычетов по модулям т0, тк, которые осуществляют

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

Блок деления на вспомогательный модуль 41.1(1 1,2К) в блоке 17 реализуется

на основе блоков памяти емкостью 2Ь° слов разрядностью bi + 3 бит, в память которого по адресу г}„ + -t mi 2Ь° при I 1.

2К-1 и по адресу rf0+ rjv.2 при I К для

всех г} 06 {0,1т0-1}и Ј{0,1mi- 1} записывается набор величин

А

ji Ј-2.;) Ј-1,; i о,;

где д,

Н гоЮ/-;

1, если gplllmj

Ј1.1 7

О в остальных случаях,

Ъ-Ь0

5

0

(15) (16)

.)/

О I КП;

5 )(,k-2+/t

;

/г.-,,-

через xf обозначается ближайшее к х целое число.

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

Ј-2 , Ј-1 , ЕО где

ernEe,i;ee{-2,-i,ol

i-1 (17)

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

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

0 IСI mk ( yi , уаyk ) константе - М (О,

00,«к) по правилу

Г1, если 1С1«к М Ј j(18)

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

k

5

м

M ,fUk-/-AA/

т.

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

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

9(c)e.avЈЈ,v0(cie0.

55«7 (19)

где 0 (С) 6 {0, 1} - поправка Амербаева, соответствующая произведению С АВ в модулярной системе счисления с основаниями mi, гп2TIM, mo, a Јo (I -2, -1, 0) и е

определяются согласно (17) и (18).

Группа блоков суммирования вычетов 18 содержит К+1 блок суммирования вычетов по модулям то, пц, ..., mi. Блоки 18 суммирования вычетов группы имеют (Т - 1)-каскадную конвейерную структуру и осуществляют сложение за Т - 1 такт наборов вычетов по модулям гл0, гщ и тк без

формирования, а по модулям mj (J 2, 3

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

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

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

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

5з (Pi + з)(20)

Блок памяти 46.J 0 2,3К-3) обладает емкостью 2bJ г т двухразрядных слов (Tj log2Cj + 1)0- причем в его память по адресу Р)-Н + 2Т| Ij+a записывается набор, величин д}+ 2, Sj+2 , где Sj+2 2wj+2, при этом л

WH-2 (/ЭМ-1 + lj+2)/mj-KZ,(21)

), если I р + 1 +1j + 2 I mj+2 mj+2 -1 (22) I в остальных случаях. Блок 46.К-2 памяти обладает емкостью

2Ь° Тк 2двухразрядных слов, в его память по адресу /5к-1 -I- записывается набор величин 6 , s , где s 5w, при этом w (pK-i-H)/m0, A(23)

10, если I /OK-1 + I I m0 т0-1 (24) 1 в остальных случаях. Группа 47 состоит из двух схем сравнения с константами. Первая и вторая схемы сравнения вырабатывают соответственно сигналы So и д0 где

fD, если IK тк - т0-К+ 2 (25) 1 в остальных случаях. (О, если IK тк - т0 5о (26)

L1 в остальных случаях. Разрядность регистра 48 составляет 2К- Збит.

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

e-svs &vs & fv... я Ј

К-t ° 1

...VS,

(27)

S So3oVGk

(28)

Элемент И-ИЛИ-НЕ 49 может быть выполнен на основе программируемой логической матрицы.

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

по модулям m0l miтк, имеющие Т-каскадную конвейерную структуру. Рассмотрим как работает предлагаемое устройство для умножения чисел в модуляр0 ной системе счисления.

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

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

0 (t + 1)-м такте инициированной операции умножения t-й разряд сдвигового регистра 8 будет установлен в единичное состояние:

Ot 1 (t 0, 1Т+ 5).

Для инициации очередной мультипли5 кативной операции по сигналу Fi 1, подаваемому с управляющего входа 3 устройства, в младший разряд регистра 8 сдвига записывается единица, а во входные регистры 6 и 7 поступают соответственно

0 модулярные коды (а , ац«k , ) операнда А и (Р ,faД , ) операнда В, где А,

B€D {-M+1,-M+2-М-1 , }

(ai IAI mi,/9 i I ВI mi, 1 1,2К;через

|Ylm обозначается наименьший неотрица5 тельный вычет, сравнимый с величиной Y по

модулю т. Кроме того, код (ft .fkA-f,)

через мультиплексор 9 (7о 0) передается в блок 10 задержки.

На первом такте операции блок 11 мо0 дульного умножения получает модулярный

код (у ,угyk, )yi Iai/Silm|i 1.2

К) младшей части (С)мк произведения С чисел А и В, который по истечении данного такта может быть снят с выхода 21 младшей части произведения устройства. Запись кода числа IClHK в регистр 16 на текущем такте не происходит, так как а 0. Кроме того, на первом такте цифры модулярного

0 кода (en , asOk , ) через мультиплексор 14, на управляющий вход которого подается сигнал a 1 0, поступает на вход группы блоков 20 суммирования вычетов, цифры модулярного кода ( , /fc/ k , ) подаются

5 в блок 15 суммирования вычетов группы а код ( а, СиOk-1.) через мультиплексор 9, на управляющий вход которого подается сигнал а о 1, передается в блок

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

тов, считая текущий, формируют соответственно наборы вычетов Ао(А), Ai(A)

Лк-1(А),к(А) и Ло(В),к(В) , при этом

А-„(«1

zXwL/, AjiM-ZR j.iMl.j.i.z, к., 5

i.w-121I,.(I

IKK-i ii ;

m,

M ,

m I m.

где R uM (I 0, 1, .... K-1 определяются согласно (5);

lk(x) - машинный интервальный индекс числа X 6D;

Xi I XI m(, l 1,2К.

В ходе второго такта операции из пер- вого разряда сдвигового регистра 8 на управляющий вход мультиплексора 14 подается сигнал Oj 1, поэтому цифры модулярного кода , /fc/ k) с выхода второго входного регистра 7 поступают в блоки 20 сумми- рования вычетов, которые начнут вычисление

набора вычетов Ло(В), Ai(B) Ax-i(B),

1к(В)

В регистр 16 кода младшей части произведения записывается код числа lCl|Ytk поступающий с выхода блока 11 модульных умножителей ( а 1). Кроме того, на данном такте операции на информационные входы блока 13 формирования вычетов с выходов первого 6 и второго 7 входных регистров соответственно поступают коды (

«1 ,02«k-1, )и (fi ,fh/#k--i) (см.

фиг. 3), поэтому по истечении второго такта в выходном регистре блока памяти 27.I (1 1,2, ..., К-1) будет сформирован вычет R|(O) ,)(см. форм. 7).

На третьем такте модулярный код ( Х1 , , ) числа | С 1м« с выхода регистра 16 кода младшей части произведения поступает на информационный вход блока 13 формирования вычетов, на второй управляющий вход которого подается единичный сигнал О2 1 (см. фиг. 3). Поэтому на выходе блока 13 будет сформирован набор величин

V0(C), Vi(C,Ri1(ai 1)) VK-i(C,RK-iWi,

)(CM. форм. 7 - 14), который передается в блоки 18 суммирования вычетов через второй вход.

На четвертом такте операции моду- лярный код числа 1C Ink c выхода регистра 16 поступает на информационный вход блока 12 формирования вычетов, на управляющий вход которого с выхода сдвигового регистра 8 подается сигнал сгз 1 (см. фиг. 2). По истечении данного такта на выходе блока 12 будет сформирован набор величин Ui(C), U2(C)

U«(C) (см. форм. 1 - 6), который передается в блоки 18 суммирования вычетов.

5

30

10

15 20

25

„

п45

5055

Параллельно с этим на четвертом такте

модулярный код (yi , у2УЬ. . ) числа

ICltfk c выхода регистра 16 кода младшей части произведения через информационный вход блока 17 формирования старшей части произведения поступает на вход схемы равенства кодов 43 (см. фиг. 5), на выходе которой формируется признак Ј (см. форм. 18), пересылающийся в элемент 45 задержки.

По истечении Т-го такта на выходах блоков 20 и 15 суммирования вычетов будут

получены наборы вычетов Ло(А), Ai(A)

Лк-1(А),1к(А) и Ло(В)Лк(В) , которые на (Т + 1)-м такте передаются в блок формирования старшей части произведения (фиг. 4). При этом величины Ло(В) и I«(B) поступают на входы первого сумматора по модулю т0

входы второго сумматора по модулю т0 30.0 и сумматора по модулю mi 31.1 соответственно, а 1«(А) - на первые входы этих сумматоров. В результате во вспомогательных регистрах 32.0 и 33.0 формируются вычеты Н0(В) |1(В)+ Л0(В)| т0ияо(А)| 1(А) + + Ло(А)1 т0, а во вспомогательном регистре

f IK (X). если IK (X) тк - m0 - К + 2 к(Х) А

IK (X) - тк, в противном случае. По истечении (Т + 1)-го такта операции умножения группа блоков 20 суммирования вычетов получит набор вычетов Ло(В),

(B)(B),k (B) , который на (Т +

такте пересылается в блок 17 формирования старшей части произведения, на информационный вход которого в это же время с выхода блока 10 задержки поступает код

,) вследствие чего сумматор

по модулю mi 31.1 находит величину ЩВ) I (В) + Л((В)| mi(,2, ,,К-1) Параллельно с этим модульные умножители 35 0 по модулю то и 35.i по модулю mi получают соответственно величины Н01 1мк-1Н0(В)Но(А)| т0 и |/3,Н,(А) |т, (i 1. 2 К-1), которые записываются во вспомогательные регистры 37.0 и 37.1 (см. фиг. 4) По окончании (Т + 2)-го такта группа блоков 18 суммирования вычетов получит набор вычетов Ло(С), I Ai(C) + Ri («i , ) Imi

|Лк-1(С) + RK-iVrk-l,)lmk 1, который на (Т + 3)ем такте передается в блок 17 формирования старшей части произведения. На информационный вход блока 17 с выхода блока 10 задержки поступает код

( си , О2c. - , ) Вычет Л0(С) вместе с

содержимым Н0 вспомогательного регистра

цифры /о I Н0 - (C)|mo интервального индекса I(C) произведения С АВ по модулю Гор. Так как на (Т + 3)-ем такте на управляющий вход блока 17 формирования старшей части произведения подается сигнал от+2 1, который подается на управляющие входы мультиплексоров 34.1, то вычет I А(С) + RI («i, ) I mi через информационный вход группы мультиплексоров 34,1 поступает на первый вход вычитателя по модулю mi 36.1 (1 1,2 К-1), на

второй вход которого из вспомогательного регистра 37.I подается вычет I/9 iHi(A) I mi, в результате во вспомогательном регистре 38.1 сформируется величина

HHA-.UVR ....

Параллельно с этим умножитель по модулю mj 35.1 получает вычет |cqHi(B)l nil. который передается во вспомогательный регистр

такта группа блоков 18 суммирования вычеJOB получает наборы величин 1з(С), М(С)

1к(С) ир2(С), /Зз(С), ...j к-i(C), где

Ie(,;(-,)|Mt,

(«bta SRe.itx-.l).....}

a Ri.i(Xi) определяется согласно форм. (4).

На (Т + 4)-м такте вычет т)0 из вспомогательного регистра 38.0 пересылается в первый регистр 39, вычет Hi с выхода вспомогательного регистра 38.1 через информационный вход группы мультиплексоров 34.1 (ot+2 0) поступает на первый вход вычитателя по модулю mj 36.1, на второй вход которого из вспомогательного регистра 37.1 поступает вычет I a iHi(B) I mi. Модульный вы- читатель 36.1 получает величину I Imi - l(Hi1 - ajHt(B) I mi, являющуюся дополнением цифры г интервального индекса (С) числа С по модулю mi. Вычет | -r m записывается во вспомогательный регистр 38.1 (1-1,2,..., К-1). Г|араллельно с этим наборы

величин 1з(С), М(С)Гк(С) и /Э2(С),

рз(С)/5к-1(С) группы блоков суммирования вычетов поступают на соответствующие входы блока 19 усеченного формирования интегральных характеристик модулярного кода, на третий вход которого из вспомогательного регистра 38.0 блока 17 формирования старшей части произведения поступает вычет ijo . Вычет 1к(С) с выхода группы блоков 18

0

5

0

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

фиг. 6) блока памяти хранения констант 46.1, 46.2, ..., 46.К-2 и группа схем 47 сравнения с константой формируют набор двухзначных признаков Зз. S4, 5о ..., SK-;, 5|(-1, S,d , So, 30 , которые передаются в регистр

0 48 (см. форм. 20-26).

На заключительном (Т+5)-м такте работы устройства элемент 49 (см. фиг. 6) по набору признаков Зз, S4, 4 ..., SK-L Зк-1, S, 5 , So, 60 , поступающему на ее входы с

5 выходов регистра 48 завершает формирование поправки Амербаева 0(С) и знаковой функции s(C) (см. форм. 27 и 28). Знак s(C) с выхода блока 19 усеченного формирования интегральных характеристик модулярного кода передается на знаковый выход 25 умножителя, а поправка 0 (С) поступает на информационный вход блока 17 формирования старшей части произведения произведения.

Параллельно с этим в блоке 17 (см. фиг. 5) вычет tj0 из первого регистра 39 поступает на первые входы блоков деления на вспомогательный модуль 41.1, 41,241.К. На

вторые входы блоков 41.1 (I 1, 2К-1) и 41,К

подаются соответственно величины I -rj I mi из вспомогательного регистра 38.1 и к Тк(С) из второго регистра 40. В результате блок деления на вспомогательный модуль 41.1(1 1,

2К) на первом выходе получает 1-ю цифру

yi целочисленного приближения к дроби АВ/

по формуле (15), а на втором выходе - набор признаков е-2,i, Ј-i,i, е-0,1 (см.форм.(16), поступающий на входы элемента И 42, где определяются признаки Ј-2 , е-1, Е-о (форм. 17). Признаки е-2 , е-1, Ј-о поступают на первый вход элемента 44, на второй и третий входы которого подаются величины 0(С) и с. Элемент 44 формирует признак мультиплика5 тивного переполнения (см. форм. 19), передающийся на выход 23 устройства. Мо- дуля|эный код (yi , уг/k , ) старшей части Со произведения С АВ снимается с первых выходов блоков деления на вспомога0 тельный модуль 41.1,41.241. К и поступает

на выход 22 устройства. Признаком конца операции умножения служит единичный сигнал Бум ot+4 1, появляющийся на сигнальном выходе 24 устройства.

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

5

0

составляет f2 1 /(2t Mr) (t и г - длительность модульного такта).

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

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

J 0, 1К-1), два регистра, К блоков деле0 ния на вспомогательный модуль, элемент И, схему равенства кодов, элемент задержки и элемент И - ИЛИ - НЕ, причем узел вычисления цифр интервального индекса произведения по модулю т0 содержит два сумматора, 5 умножитель и вычитатель по модулю то и четыре вспомогательных регистра, при этом выход первого сумматора по модулю т0 через первый вспомогательный регистр соединен с первым входом умножителя по модулю т0, второй вход которого через второй вспомогательный регистр соединен с выходом второго сумматора по модулю т0, выход умножителя по модулю точерез третий вспомогательный регистр соединен с первым входом вычитателя по модулю т0, выход которого соединен с входом четвертого вспомогательного регистра, а узел вычисления цифр интервального индекса

произведения по модулю mi (i 1 К-1)

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

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

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

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

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

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

Фиг. I

Фиг 3

if-1 г

Фиг. 4