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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и предназначено для использования в быстродействующих специализированных вычислительных системах конвейерного типа, функционирующих в модулярной системе счисления. Целью изобретения является повышение пропускной способности. Устройство содержит регистр 7 интервального индекса, сумматор-вычитатель 10, первый и второй регистры 11 и 12 сдвига, второй и первый сумматоры 13 и 21 интервального индекса, второй и первый блоки 14 и 15 вычисления интервального индекса числа, блок 16 мультиплексоров, формирователь 17 числа переполнений, формирователь 18 интегральных характеристик модулярного кода, второй и первый вспомогательные регистры 19 и 20, регистр 22 результата, блок 23 элементов задержки и узел 24 контроля переполнения со связями. 1 з.п. ф-лы, 2 ил.

СОНЗЗ СОВЕГСКИХ

СОЦИИЯИСТИЧЕСКИХ

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

ГОСУДАРСТ8ЕННЫИ КОМИТЕ!

ПО ИЗОЬРЕТЕ НИЯМ И ОТКР Ь!ТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ г7 гв (21) 4739743/24 (22) 21.09.89 (46) 23.08.91. Бюл. N. 31 (71) Научно-исследовательский институт прикладных физических проблем им. А.Н.Севченко (72) А.А.Коляда, В.К.Кравцов, И.Н.Кукель и

М.Ю.Селянинов (53) 681.325(088.8) (56) Авторское свидетельство СССР

N. 1432517, кл. G 06 F 7/72. 1987.

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

N 1322278, кл. G 06 F 7/72. 1986. (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ ЧИСЕЛ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ (57) Изобретение относится к вычислительной технике и предназначено для

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

7 интервального индекса, сумматор-вычитатель 10, первый и второй регистры 11 и 12 сдвига, второй и первый сумматоры 13 и 21 интервального индекса, второй и первый блоки 14 и 15 вычсления интервального индекса числа, блок 16 мультиплексоров, формирователь 17 числа переполнений, формирователь 18 интегральных характеристик модулярного кода, второй и первый вспомогательные регистры 19 и 20, регистр

22 результата, блок 23 элементов задержки и узел 24 контроля переполнения со связями. 1 з.п. ф-лы. 2 ил.

1672448

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

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

На фиг.1 представлена схема устройства для сложения чисел в модулярной системе счисления; на фиг.2 — схема узла контроля переполнения.

Устройство (фиг,1) содержит первый и второй информационные входы 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 результата устройства, выход 26 признака аддитивного переполнения устройства, знаковый выход 27 устройства. выход 28 сигнала окончания работы устройства.

Узел 24 контроля переполнения (фиг,2) содержит схему 29 сравнения с константой, регистр 30, элемент 31 задержки, счетчик 32 и мультиплексор 33.

Разрядность первого и второго входных к регистров 8 и 9 составляет! =, > Bi бит, где

i =1

В! = )Iogz m (, m1, mz„„,тк — основания модулярной системы счисления, являющиеся попарно простыми целыми числами, т.е. (mi, m!) = 1, i, = 1, 2,...,К; W j, через )х(обозначается наименьшее целое число, не меньшее х. Далее для простоты рассматривается случай, когда все модули m являются нечетными, Сумматор-вычитатель 10 содержит блок модульных сумматоров и блок модульных вычитателей по модулям п11, mz,...,вк системы счисления. Сумматор-вычитатель 10 получает модулярный код как формальнои суммы ! А+ В IMк, так и формаfl ьн Ой ра 3 ности !

А-BIMy операндов А и В вк« ".те с на5

55 борами поразрядных признаков переполне11Ия S3 = < (»1, П)2 ..., мк — ) и

0 (— и1, — or.>,..., — и! к > соответстве

I . 1 нно, где А, В Оо= (-М,, -М+ 2.... М-1), Dp — диапазон модулярнои системы счислеК вЂ” ния, M= mpMK-1, Мк 1=- П п1е mo вспомога1=1 тельный модуль, выбираемый из условий

mx > 2mp + К-2; п1о К-1. п =((I М, ) — 1 гс, I m -1

+ M, 2 — 1 /3; m, )Хгп) ), гт3! =((I М; p — iz; I mi— — I M; 3 — i 3, I m t )/mt)„ (2) гдеа! = I А I mi,/3, =1 В 1mi, М! к-1=-Мк-1/mi, i- 1-К-1;

IYIm — наименьший неотрицательный вычет, сравнимыи с величиной Y по модулю

Наборы величин IAt БIМк,Q) и

< lA-В!Мк,12. снимаются с соответствующих выходов сумматора-вычипателя 10.

Разрядность первого и второго регистров 11 и 12 сдвига составляет соответственно T+1 и T+4 бит, где Т = )!од2К(. Выходы нулевого и T-ro разрядов первого регистра

11 сдвига являются соответственно выходами его младшего и старшего разрядов. Выход (T+3)-ro разряда второго регистоа 12 сдвига является его выходом.

Разрядность регистра 7 интервального индекса составляет Вк бит.

Второй сумматоор 13 интервального индекса по входным величинам1к(А) и 1/ty(A) E 10, 1...., птк- 1), I F (О, 1,..., 2(п1о+ К-2)} полУчает паРУ вычетов

II(A)+ 1/m, l(g/A)+ 1)1гпо)!4 =< 1(С), I J(C)14>, где л л

1к (А ), если Гк (А ) < тл к — m 0 — К + 2 к (А ) — mp в противном случае: (1, если1 m + К вЂ” 2 . (2 mo + 2к — 3 ) в противном случае, Сумматор 13 интервального индекса реализуется таблично на основе постоянного запоминают его устройства обладающего емкостью 2 "+ ) 1 "" 2к )(слов разрядНОСтЬЮ Во + 2 бИт Во = )!ОО2ГПо(), В ПаМЯтЬ

ВГ" которого по адресу i<(A)+2 1 записывается пара констант < фС), I J(C)14>.

1672448

Второй и первый блоки 14 и 15 вычисления интервального индекса числа служат для определения эа Т тактов по входному модулярному коду (х1, хр ...,.хк ) числа хаОО машинного интервального индекса числа по формуле к 1 1М д 1xI I m!

1к(x) = +

I =1

mI Р1)

М," (4) где xI=lxlmI, i= 1, 2,..., К.

Структурно второй и первый блоки 14 и

15 вычисления интервального индекса числа аналогичны параллельно-конвейерному блокусуммирования вычетов по модулю п1к.

Блок 16 мультиплексоров содержит

L 4- К - 1 мультиплексоров. Разрядность регистра 22 результата составляет L < К - 1 бит, Формирователь 17 числа переполнений выполнен на основе постоянного запоминаюц его устройства. обладающего емкостью

2 слов разрядностью Т бит, в память кокК вЂ” 1 торого по адресу, > о 2 I ол 6 (0,1) эаI =1

К вЂ” 1 писывается константа П = > в

1=1

Блок 23 элементов задержки представляет собой цепочку из T-1 последовательно соединенных регистров разрядностью Т бит, вход первого и выход (Т-1)-го иэ которых являются соответственно входом и выходом блока 23 элементов задержки.

Формирователь 18 интегральных характеристик модулярного кода является известным устройством, представляющим собой упрощенный вариант устройства для формирования интегральных характеристик модулярного кода конвейерного типа, быстродействие которого составляет Т-2 такта при пропускной способности одна операция в один такт. Формирователь 18 по входному интервально-модулярному коду у1, у2,..., y к — 1 I (С ) числа С осуществляет формирование лишь одной характеристики: поправки Амербаева О(С )E(0,1), соответствующей числу С в системе модуЛЕй mp, m1... „m V,-1.

Разрядность второго и первого вспомогвтельных регистров 19 и 20 составляет соответственно Bp+ 2 и )logg (2mp+ 2К - 3)(бит.

Первый сумматор 21 интервального индекса является сумматором по модулю (2гпо + 2К - 3) и в зависимости от значения сигнала ГC (0,1), подаваемого на его управляющий вход, подоходным величинам (к(В) и

Р находит вы«ет)= 1 ЩВ)+ П)/2mpi 2К-3, где

3к(В) и 1(В) связаны между собой в соответствии с формулой (3), а

+, если Г =О, —, если Г = 1.

Наиболее просто сумматор 21 интер10 вального индекса реализуется на основе постоянного запоминающего устройства, в т+1 обладающего емкостью 2 слов разрядностью )log2 (2mp + 2К - 3)(бит, в память

Вк +1 л в, которого по адресу (к(В)+ 2 "П+ 2 Г записывается вычет j = I(-1)(ЯВ)+ П)(, „

Схема 29 сравнения с константой (фиг.2) предназначена для формирования признака r, — признака равенства формальной

20 суммы С 1 „= (y1 ур,..., ук ) константе—

М=- (О, О,...,рк) по правилу

F =

1, если I С!мк== — М, О в противном случае .

y, = l C I,, l= 1, 2...., К; (5) Рк =-1 — M „,, Элемент 31 задержки осуществляет задержку на Т + 2 такта.

Мультиплексор 33 реализует следующее булево соотношение: ñð 1,1ЦЮЧ,j Vj ),ВК)Ч .jf., 35 где ЯС) — поправка Амербаева; к определяется согласно формуле (5);

40 Jp и J1 — цифры двоичного кода вычета

Ia(c) i 4.

Рассмотрим, как работает устройство для сложения чисел в модулярной системе числения (фиг,1). По сигналу Гр- 1, подава45 емомус входа 5устройства, второй регистр

12 сдвига обнуляется, тем самым устройство приводится в исходное рабочее состояние.

В целях формирования необходимых

I управляющих сигналов первый и второй регистры 11 и 12 сдвига ежетаткно сдвигаются на один бит в сторону старших разрядов по сигналу, подаваемому с тактового входа 6 устройства, Поэтому на (1 + 1)-м такте инициированной операции

rr„сложения 1-тые разряды соответственно первого и второго регистров 11 и 12 сдвига будут установлены в следующее состояние: о () = Г и O1() =1(t=0,1,....Тдля первого и t = О, 1„...Т+3 для второго регистров 11 и

12 сдвига, Гб (0,1).

1672448

1Сlм„, O где C= А В; о, если Г =О, и — о, если Г =1;

I= 1, 2,..., К-1.

Для инициации очередной аддитивной операции код Г операции, подлежащей выполнению, с входа 3 кода операции устройства поступает на вход первого регистра 11 сдвига, при этом в случае, если Г=- 0 (операция сложения), в младший разряд первого регистра 11 сдвига записывается "0"; если

Г= 1 (операция вычитания), то в младший разряд первого регистра 11 сдвига записывается "1". Г1о сигналу Г = 1, поступающему с входа 4 устройства, младший разряд второго регистра 12 сдвига устанавливается в единичное состояние.

М одул я р н ы е коды (с, а2 ....,ак ) операнда А и (/3,/4,...,/Зк ) операнда В через первый 1 и второй 2 информационные входы устройства передаются соответственно в первый и второй входные регистры 8 и 9, и после этого начинается первый такт операции.

Инициированная операция реализуется следующим образом. На первом такте модул ярн ые коды (ai, а ...„ак ) и (Pi, /% ...., /Зк ) операндов А и В из первого и второго входных регистров 8 и 9 поступают соответственно во второй и первый блоки 14 и 15 вычисления интервального индекса числа. где в течение очередных Т тактов, считая текущий, вblчисляются Màшинные интервальные индексы 1к(А) и 1к(В), формула (4). Одновременно с этим модулярные коды операндов А и В поступают на входы сумматора-вычитателя 10, который получает по модулям п, m2„...гпк системы счисления модулярный код как формальной суммы, так и формальной разности вместе с наборами поразрядных пдриэнаков переполнения, формулы (1) и (2). Наборы величин

< IA+ В1Мк, Q и < IA-BIMv, Q с выходов сумматора-вычитателя 10 подаются соответственно на первый и второй информационные входы блока 16 мультиплексоров, на управляющий вход которого с выхода младшего разряда первого регистра 11 сдвига. подается код Г {0,1) реализуемой операции. В результате на вход блока 16 мультиплексора, а следовательно, и в регистр 22 результата поступает набор величин

Результат модульной операции сложения (вычитания) 1С!м,может быть считан с выхода 25 результата устройства.

На втором такте модулярный код (1 >, у2,..., ук ) числа Itl „из 1 младших разрядов регистра 22 результата передается в узел 24 контроля переполнения через первый вход, поступает на вход схемы 29 сравнения с константой (фиг,2), где формируется признак : формула (5), который записывается в элемент задержки. Параллельно с этим первые К-1 цифр модулярного кода числа 1С1м,поступают на первый вход формирователя 18 интегральных характеристик модулярного кода. который нэ следующем такте приступает к формированию поправки Амербаева 0(С ) . Что касается набора признаков О,,то он в ходе второго такта операции из К-1 старших разрядов регистра

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

23 элементов задержки.

На (Т+ 1)-м такте машинный интервальный индекс 1к(А) числа А, полученный вторым блоком 14 вычисления интервального индекса числа, пересылается в регистр 7 интервального индекса, В это же время на входы первого и второго слагаемых первого сумматора 21 интервального индекса поступают величины Тк(В) и П соответственно с выходов первого блока 15 вычисления интервального индекса числа и блока 23 элементов задержки, а на управляющий вход с второго выхода первого регистра 11 сдвигав подается код Г выполняемой операции. В результате первый сумматор 21 интервального индекса находит вычет1, который передается в первый вспомогательный регистр 20.

На (T+ 2)-м такте на входы слагаемых второго сумматора 13 интервального индекса с выходов регистра 7 интервального индекса и первого вспомогательного регистра

20 подаются величиныЗк(А) и1соответственно. Второй сумматор 13 интервального индекса получает пару вычетов 1(С), 11(С)14>, которые записываются во второй вспомогательный регистр 19.

На (Т+3)-ем такте содержимое J(C) из Во младших разрядов второго вспомогательного регистра 19 поступает на второй вход формирователя 18 интегральных характеристик модулярного кода, где выполняется заключительная стадия процесса формирования поправки Амербаева 6(С).

Параллельно с этим двухразрядная величина ЩС)14 с выхода второго вспомогательного регистра 19 через третий вход узла 24

16 ? 148

5

15

55 контроля переполнения передается в регистр 30 (фиг.2).

На заключительном (Тi 4)-м такте операции вычет 13(С)14 из регистра 30 поступает в счетчик 32. Кроме этого, поправка Амербаева 0(С) с выхода формирователя 18 интегральных характеристик модулярного кода передается в узел 24 контроля переполнения через второй его вход, где наряду с признаком к, появляющимся в данный момент на выходе элемента 31 задержки, и цифрами ), и ji двоичного кода вычета

1.1(С)1п, содержащегося в счетчике 32. она используется в качестве входной величины мультиплексора 33, который, реализуя булево соотношение (6). определяет искомое значение признака аддитивного переполнения Q-.<. Одновременно с этим поправка

Амербаева 0 (С) поступает на счетный вход счетчика 32. в результате чего в нем формируется двоичный код вычета

IJ(C) 0 (С)1а старшая цифра которого представляет собой знак S(C) суммы С, Признак аддитивного переполнения Q и знак

S(C) с первого и второго выходов узла контроля переполнения передаются на выходы

26 и 27 устройства, а на выходе 28 устрой(2 ) ства появляется сигнал ten — — ттт + з = 1 . который служит признаком окончания операции сложения.

Инициация очередной аддитивной операции в устройстве для сложения чисел в модулярной системе счисления может быть осуществлена уже на первом такте текущей операции. т.е. максимальная частота обращения к данному устройству составляет fi =- 1/t, (t — длительность модульного такта).

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

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

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

1672448

2. Устройство по п.1, о т л и ч а ю щ е ес я тем, что узел контроля переполнения содержит схему сравнения с константой, реС оста вител ь А. Кл ю ее

Редактор О.Юрковецкая Техред М.Моргентал Корректор М. Максимишинец

Заказ 2840 Тираж 375 Подписное

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

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

Производственно и лательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 кода, выходы младших разрядов регистра результата соединены с входами разрядов первого входа узла контроля переполнения, второй вход которого соединен с выходом формирователя интегральных характеристик модулярного кода, выходы старших разрядов второго вспомогательного регистра соединены с входами разрядов третьего входа контроля переполнения, первый и второй выходы которого являются выходом признака аддитивного переполнения и знаковым выходом устройства соответственно, гистр, элемент задержки, счетчик и мультиплексор, причем первый вход узла контроля переполнения соединен с входом схемы сравнения с константой, выход которой че5 рез элемент задержки соединен с первым информационным входом мультиплексора, выход которого является первым входом узла контроля переполнения, второй вход которого соединен с вторым информа10 ционным входом мультиплексора и счетным входом счетчика, выход которого является вторым выходом узла контроля переполнения, третий вход которого соединен с входом регистра, выход которого соединен с

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