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

О vj Ю 4 N

00

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

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

На фиг.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 составляет L BI бит, где

i 1

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

Сумматор-вычитатель 10 содержит блок модульных сумматоров и блок модульных вычитателей по модулям гщ,

гп2тк системы счисления. Сумматор-вымитате л ь 10 получает модулярный код как формальной суммы IA+ , так и формальной разности операндов А и В с наборами поразрядных признаков переполнения Q - . - и

Q - d) . -ah - i соответстве

нно, где А. ВЈ0о {-М- 1, -М+ 2.... М-1}; Do - диапазон модулярной системы счислек - i ния, М т0Мк-1, Мк 1 П те т0 вспомогаI 1

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

ОХ ( I М ,. к1 - i с/, I т, 4

+ I МГк1 -- i i I т, )/mi .

щ ( I М Гк1- 1 (Ъ I mi - -I МГк1- i Д I mi )/mi,

(1)

(2)

где«| I А I гщ , /, I В I mi , М|.к-1 Мк-1/гп|, i- 1-K-1;

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

Наборы величин : В IМ к. Q и

1А-В Мк,Ј2 снимаются с соответствующих выходов сумматора-вычипателя 10.

Разрядность первого и второго регистров 11 и 12 сдвига составляет соответственно Т+1 и Т+4 бит. где Т log2K. Выходы нулевого и Т-ro разрядов первого регистра 11 сдвига являются соответственно выходами его младшего и старшего разрядов. Выход (Т+3)-го разряда второго регистоа 12 сдвига является его выходом.

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

Второй сумматоор 13 интервал ного индекса по входным величинам к(А)

и 1/1к(А)6 {0, 1 тк-1}, 16 {0, 1

2(то+ К-2)} получает пару вычетов

II(A)+l/m0, )+J) 1(Q, IJ(C)l4, r«e

ЦА)

ii{«i-j

если Гк(А)ггчс- m0- K+2, тк в противном случае :

-, - Ц если m0 +K -2 . (2т0+2к-3)в противном случае

Сумматор 13 интервального индекса реализуется таблично на основе постоянного запоминающего устройства, обладающего емкостью 2 Jog (йь гк - з слов pa3pqflностью Во + 2 бит Во lloqgmoD. в память которого по адресу 1к(А)+2 1 записывается пара констант 1(С), и(С)Ц.

Второй и первый блоки 14 и 15 вычисления интервального индекса числа служат для определения за Т тактов по входному

модулярному коду ( xi , Х2хк ) числа

xЈD0 машинного интервального индекса числа по формуле

ляющий вход, подходным величинам 1к(В) и П находит вычет - )+ П)/2т0+ 2К-3, где JK(B) и 1(В) связаны между собой в соответствии с формулой (3), а

„, j + . если Г 0 , - . если Г 1 .

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

/KV1/ IMi.iJ-ixilmi )/ Z

i 1

mi

lmt

+ /T

I XK / /

/ M K -1 К I™

где xi lxlmi, i 1, 2K.

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

Блок 16 мультиплексоров содержит L + К - 1 мультиплексоров. Разрядность регистра 22 результата составляет L - К -1 бит.

Формирователь 17 числа переполнений выполнен на основе постоянного запоминающего устройства, обладающего емкостью 2 слов разрядностью Т бит, в память кок - 1

торого по адресу о/ 2 1 I аЈе {0,1} зак - 1 писывается константа П щ .

1

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

Формирователь 18 интегральных характеристик модулярного кода является известным устройством, представляющим собой упрощенный вариант устройства для формирования интегральных характеристик модулярного кода конвейерного типа, быстродействие которого составляет Т-2 такта при пропускной способности одна операция в один такт. Формирователь 18 по входному интервально-модулярному коду yi ,/2Ук-1 ,Т(С)числа С осуществляет формирование лишь одной характеристики: поправки Амербаева #(С)Ј{0,1), соответствующей числу С в системе модулей mo, miтк-1.

Разрядность второго и первого вспомогательных регистров 19 и 20 составляет соответственно Во + 2 и log2 (2гп0 + 2К-ЗХ бит.

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

Наиболее просто сумматор 21 интер- Ю вального индекса реализуется на основе по- стоянного запоминающего устройства, обладающего емкостью 2слов разрядностью log2 (2m0 + 2К-ЗХ бит, в память

вВк+1

15 которого по адресу Гк(В)+2 КП+2 -Г записывается вычет 1 1(-1)(КВ)+ П).

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

20 суммы I С 1/7ц (У1 . КгУК ) константе М (О, ) по правилу

(5)

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

у, 1 С Ц, 1 1.2К;

/« I - М тк

Элемент 31 задержки осуществляет задержку на Т + 2 такта.

Мультиплексор 33 реализует следующее булево соотношение:

S Jojfl VjJ jJ tOVjJe ,

где (3(С) - поправка Амербаева;

Ј определяется согласно формуле (5);

Jo и J1 - цифры двоичного кода вычета

IJ(C)U.

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

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

приводится в исходное рабочее состояние.

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

управляющих сигналов первый и второй

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

сложения t-тые разряды соответственно первого и второго регистров 11 и 12 сдвига будут установлены в следующее состояние:

Г и Ол2 1(, 1Т для первого

и t 0, 1Т+3 для второго регистров 11 и

12 сдвига, Ге{0,1}.

Для инициации очередной аддитивной операции код Г операции, подлежащей выполнению, с входа 3 кода операции устройства поступает на вход первого регистра 11 сдвига, при этом в случае, если Г 0 (операция сложения), о младший разряд первого регистра 11 сдвига записывается если Г 1 (операция вычитания), то в младший разряд первого регистра 11 сдвига записывается 1. По сигналу Г 1, поступающему с входа 4 устройства, младший разряд второго регистра 12 сдвига устанавливается в единичное состояние. Модулярные коды ( а , «2«к ) операнда А и ( , /Зк ) операнда В через

первый 1 и второй 2 информационные входы устройства передаются соответственно в первый и второй входные регистры 8 и 9, и после этого начинается первый такт операции.

Инициированная операция реализуется следующим образом. На первом такте модулярные коды (cti.«2«к ) и

( , ) операндов А и В из первого

и второго входных регистров 8 и 9 поступают соответственно во второй и первый блоки 14 и 15 вычисления интервального индекса числа, где в течение очередных Т тактов, считая текущий, вычисляются машинные интервальные индексы к(А) и к(В), формула (4). Одновременно с этим модулярные коды операндов А и В поступают на входы сумматора-вычитателя 10, который

получает по модулям пгп, татк системы

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

, Ј, где С

Й а , аъ мк - 1

;

I ад , если Г - 0 .

( 1г 1

1 - oJ| . если Г 1 ;

1 1, 2К-1.

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

На втором такте модулярный код

(} 1 , угук ) числа из L младших

разрядов регистра 22 результата передается в узел 24 контроля переполнения через . первый вход, поступает на вход схемы 29 сравнения с константой (фиг.2). где формируется признак е формула (5), который записывается в элемент задержки. Параллельно с этим первые К-1 цифр модулярного кода числа С мкпоступают на первый вход формирователя 18 интегральных характеристик

модулярного кода, который на следующем такте приступает к формированию поправки Амербаева в( С ) . Что касается набора

признаков fiT, то он в ходе второго такта операции из К-1 старших разрядов регистра

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

На (Т+ 1);м такте машинный интервальный индекс 1к(А) числа А, полученный вторым блоком 14 вычисления интервального индекса числа, пересылается в регистр 7 интервального индекса. В это же время на входы первого и второго слагаемых первого

сумматора 21 интервального индекса поступают величины Тк(В) и П соответственно с выходов первого блока 15 вычисления интервального индекса числа и блока 23 элементов задержки, а на управляющий вход с

второго выхода первого регистра 11 сдвигав подается код Г выполняемой операции. В результате первый сумматор 21 интервального индекса находит вычет, который передается в первый вспомогательный регистр20.

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

20 подаются величины к(А)и1соответствен- но. Второй сумматор 13 интервального индекса получает пару вычетов J(C), U(C)U, которые записываются во второй вспомогательный регистр 19.

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

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

На заключительном (Т- 4)-м такте операции вычет IJ(C)U из регистра 30 поступает в счетчик 32. Кроме этого, поправка Амербэ- евэ 0(С) с выхода формирователя 18 интегральных характеристик модулярного кода передается в узел 24 контроля переполнения через второй его вход, где наряду с признаком г. появляющимся в данный момент на выходе элемента 31 задержки, и цифрами jo и ji двоичного кода вычета IJ(C)M содержащегося в счетчике 32. она используется в качестве входной величины мультиплексора 33.который,реализуя булево соотношение (6). определяет искомое значение признака аддитивного переполнения fin. Одновременно с этим поправка Амербаева О (С) поступает на счетный вход счетчика 32. в результате чего в нем формируется двоичный код вычета и(С)4 О (C)U. старшая цифра которого представляет собой знак S(C) суммы С Признак аддитивного переполнения О:Л и знак S(C) с первого и второго выходов узла контроля переполнения передаются на выходы 26 и 27 устройства, а на выходе 28 устрой(2) ства появляется сигнал ten с/т +з - 1 .

который служит признаком окончания операции сложения.

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

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

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

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

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

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

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

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

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

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

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

Фиг. I