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

(5115 6 06 С 7 П 2 ГОСУДАРСТ 8 Е Н 1 181 И КОМИТЕПО ИЗОЬРЕТЕНИ 51 М И ОТКР Ь 1 ТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ,К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ г гв б Фе(71) Научно-исследовательский институт прикладных физических проблем им. А.Н,Севченко(56) Авторское свидетельство СССРМ 14325 17, кл, 6 06 С 772, 1987,Авторское свидетельство СССРМ 1322278, . С 06 С 7 П 2. 1986.(54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ ЧИСЕЛ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ.Я 2 и 1672448 А 1 использования в быстродействующих специализированных вычислительных системах конвеиерного типа, фукционирующих в модулярной системе счисления, Целью изобретения является повышение пропускной способности, Устройство содержит регистр 7 интервального индекса, сумматор-вычитатель 10, первый и второй регистры 11 и 12 сдвига, второй и первый сумматоры 13 и 21 интервального индекса, второй и первый блоки 14 и 15 вычсления интервального индекса числа, блок 16 мультиплексоров, формирователь 17 числа переполнений, формирователь 18 интегральных характеристик модулярного кода, второй и первый вспомогательные регистры 19 и 20, регистр 22 результата, блок 23 элементов задержки и узел 24 контроля переполнения со связями, 1 з,п. ф-лы. 2 ил, 1672448Изобретение относится к вычислительнои технике и предназначено дляиспользования в быстродействующих специализированных вычислительных системах конвейерного типа, функционирующихв модулярной системе счисления.Целью изобретения является повышение пропускной способности,На фиг.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 составляет=, В бит, где=1В = 1092 щ, щ 1, щ 2,щк - основания модулярной системы счисления, являющиеся попарно простыми целыми числами, т,е. (щ 1,щ) = 1,1,= 1, 2,К;Ф ), через )х обозначается наименьшее целое число, не меньшее х, Далее для простоты рассматриваетсяслучай, когда все модули щ являются нечетными,Сумматор-вычитатель 10 содержитблок модульных сумматоров и блок модульных вычитателей по модулям щ 1,щ 2щк системы счисления Сумматор-вычитатель 10 получает модулярный код как формальнои суммыА+ В 1 Мк, так и формальной разности1 А-В 1 Мк операндов А и В вмп те с на 5 10 15 20 25 30 35 40 45 50 55 борами поразрядных признаков переполне 11 Ия= П 1, П)2 ик - 1 ) и О ( - г 1, - и- и ксоотдетстве.нно, где А, В-Оо= (-М 1, -М 1 2 М), Оо - диапазон модулярнои системы счисления, М= гпоМк.1, Мк 1=- П ще що вспомогательный модуль, выбираемый из условий гпк2 що + К.2; п 1 оК. ол =(1 М, 1 -гс, гп +М к1 /3гп, ),гп ,гт 1 =( 1 М; Р - 1 гдгп --м,-г-, рт, 1 т) (2) гдеа =1 А 1 щ,/3, =1 В гп, МкМк/щ, 1- 1-К;1 У 1 гп - наименьший неотрицательный вычет, срдвнимыи с величиной У по модулю Наборы величин1 А Б 1 Мк,ьи1 А-В 1 Мк,й снимаются с соответствующих выходов сумматора-вычипателя 10.Разрядность первого и второго регистров 11 и 12 сдвига составляет соответственно Т+1 и Тбит, где Т = од 2 К, Выходы нулевого и Т-го разрядов первого регистра 11 сдвига являются соответственно выходами его младшего и старшего разрядов. Выход (Т+3)-го разряда второго регистоа 12 сдвига является его выходом,Разрядность регистра 7 интервального индекса составляет Вк бит,Второй сумматоор 13 интервального индекса по входным величинам 1 к(А) и Ь 1 К(А) б (О, 1 п 1 К), 1 б (О, 1,., 2(п 1 о+ КполУчает паРУ вычетов0(А)+ 1/щвО/А)+ 1)1 щ 14 = ЙС), 1)(С)4, где л лЪсА ) . если Гк ( А )тпк - по - К + 2,1(А ) к (А) - птк в противном случае:1, если 1пт, + К - 2,(1 - (2 по + 2 к - 3) в противном случае Сумматор 13 интервального индекса реализуется таблично на основе постоянного запоминаютего устройства обладающего емкостью 2 " )пь слов разрядностью Во + 2 бит Во = )ос 12 що), в памЯтьцР"которого по адресу 1 к(А)ф 2 1 записывается пара констант(С), 13(С)14,1672448 Второй и первый блоки 14 и 15 вычисления интервального индекса числа служат для определения эа Т тактов по входному модулярному коду ( х 1, х 2хк ) числа х 600 машинного интервального индекса числа по формуле(4) где х 1=1 х 1 п 1 ь 1= 1, 2 К.Структурно второй и первый блоки 14 и 15 вычисления интервального индекса числа аналогичны параллельно-конвейерному блокусуммирования вычетов по модулю п 1 к.Блок 16 мультиплексоров содержит+ К - 1 мультиплексоров. Разрядность регистра 22 результата составляет1 К -1 бит,Формирователь 17 числа переполнений выполнен на основе постоянного запоминаюц 1 его устройства, обладающего емкостью 2 слов разрядностью Т бит, в память кок.К - 1торого по адресу,) в 2 1 пл б(0,1) за =1(5)- 1 М 1 писывается константа П =, гл 1 .1=Блок 23 элементов задержки представляет собой цепочку из Тпоследовательно соединенных регистров разрядностью Т бит, вход первого и выход (Т)-го иэ которых являются соответственно входом и выходом блока 23 элементов задержки.Формирователь 18 интегральных хара теристик модулярного кода является изв стным устройством, представляющи собой упрощенный вариант устройства д формирования интегральных характер стик модулярного кода конвейерного тип быстродействие которого составляет Т такта при пропускной способности од операция в один такт. Формирователь 18 входному интервально-модулярному ко У 1 )2 " У К - 1, 1( С ) чиСла С ОСущЕСт ляет формирование лишь одной характер стики: поправки Амербаева О( С )б(0,1 соответствующей числу С в системе мод ЛЕй ПЪ, ГП 1 ГПК 1.Разрядность второго и первого вспом гвтельных регистров 19 и 20 составляет с ответственно В+ 2 и 1 о 92 (2 п 1 о+ 2 К - 3)( биПервый сумматор 21 интервально индекса является сумматором по модул (2 п 10+ 2 К - 3) и в зависимости от значен сигнала Гб(0,1), подаваемого на его упра 35 где ЯС) - поправка Амербаева;к определяется согласно формуле (5)40 О и )1 - цифры двоичного кода вычета1 1(С)14,и Рассмотрим, как работает устройствоа,для сложения чисел в модулярной системе-2 числения (фиг,1), По сигналу Го, подавана45 емомус входа 5 устройства, второй регистр12 сдвига обнуляется, тем самым устройствоподуприводится в исходное рабочее состояние.В целях формирования необходимыхвуправляющих сигналов первый и второй50 регистры 11 и 12 сдвига ежетаткно сдвигаются на один бит в сторону старших разрядов по сигналу, подаваемому стактового входа 6 устройства, Поэтому на(1) (г)и 1 = О, 1 Т+3 для второго регистров 11 и12 сдвига, Гб (0,1),1 М- 1 х 11 п 111 К(х ) =П 11 и ляющий вход, подоходным величинам к(В) и )1 находит вычет)= 1 юЩВ)+ П)/2 п 1 о+ 2 К-З, где Як(В) и 1(В) связаны между собой в соответствии с формулой (3), а5 Наиболее просто сумматор 21 интер 10 вального индекса реализуется на основе постоянного запоминающего устройства,в т+обладающего емкостью 2 слов разрядностью 1 о 92 (2 п 10 + 2 К - 3)( бит, в памятьВк+лв,которого по адресу.(кВ)+ 2 "П+ 2 Г записывается вычет = 1(-1)фВ)+ П)1Схема 29 сравнения с константой (фиг.2)предназначена для формирования признака г - признака равенства формальной20 суммы 1 С 1 ру=(У 1, У 2УК ) константе -М=-(0, О.,рк) по правилукк1, если 1 С 1 м== - М,0 в противном случае,25У, = С 1 1= 1, 2, К; 30 Элемент 31 задержки осуществляет задержку на Т+ 2 такта,Мультиплексор 33 реализует следующее булево соотношение:= ,1 ОЮ УЧ,1, ВК) ч.1 а, 1672448Для инициации очередной аддитивной операции код Г операции, подлежащей выполнению, с входа 3 кода операции устройства поступает на вход первого регистра 11 сдвига, при этом в случае, если Г=- 0 (операция сложения), в младший разряд первого регистра 11 сдвига записывается "0"; если Г= 1 (операция вычитания), то в младший разряд первого регистра 11 сдвига записывается "1". Г 1 о сигналу Г = 1, поступающему с входа 4 устройства, младший разряд второго регистра 12 сдвига устанавливается в единичное состояние. Модулярные коды (Гх, а 2,ак ) операнда А и (уЗ,/6Рк ) операнда В через первый 1 и второй 2 информационные входы устройства передаются соответственно в первый и второй входные регистры 8 и 9, и после этого начинается первый такт операции.Инициированная операция реализуется следующим образом. На первом такте модулярные коды (а, а 2,.,ак) и(3, % ,3 к ) операндов А и В из первого и второго входных регистров 8 и 9 поступают соответственно во второй и первый блоки 14 и 15 вычисления интервального индекса числа. где в течение очередных Т тактов, считая текущий, вычисляются машинные интервальные индексык(А) и 1 к(В), формула (4), Одновременно с этим модулярные коды операндов А и В поступают на входы сумматора-вычитателя 10, который получает по модулям п 1, пз 2.гпк системы счисления модулярный код как формальной суммы, так и формальной разности вместе с наборами поразрядных пдриэнаков переполнения, формулы (1) и (2). Наборы величин1 А+ В 1 Мк, Й и1 А-В 1 Мк, Й с выходов сумматора-вычитателя 10 подаются соответственно на первый и второй информационные входы блока 16 мультиплексоров, на управляющий вход которого с выхода младшего разряда первого регистра 11 сдвига. подается код Г (0,1) реализуемой операции. В результате на вход блока 16 мультиплексора, а следовательно, и в регистр 22 результата поступает набор величин1 С 1 м, Й, где С= АВ: Й=в, игвк -,гй, если Г=О, и- ом, если Г =1;1= 1, 2., К.5 10 15 20 25 30 35 40 45 50 55 Результат модульной операции сложения (вычитания) 1 См,может быть считан с выхода 25 результата угтройства,На втором такте модулярный код (у 1, у 2 , ук ) числа С миз 1 младших разрядов регистра 22 результата передается в узел 24 контроля переполнения через первый вход, поступает на вход схемы 29 сравнения с константой (фиг,2), где формируется признак к формула (5), который записывается в элемент задержки. Параллельно с этим первые Кцифр модулярного кода числа 1 См,поступают на первый вход формирователя 18 интегральных характеристик модулярного кода, который на следующем такте приступает к формированию поправки Амербаева 0( С ), Что касается набора признаков Й, то он в ходе второго такта операции из Кстарших разрядов регистра 22 результата поступает на вход формирователя 17 числа переполнений, который получает величину П, передающуюся в блок 23 элементов задержки,На (Т+ 1)-м такте машинный интервальный индекс 1 к(А) числа А, полученный вторым блоком 14 вычисления интервального индекса числа, пересылается в регистр 7 интервального индекса, В это же время на входы первого и второго слагаемых первого сумматора 21 интервального индекса поступают величины 1 к(В) и П соответственно с выходов первого блока 15 вычисления интервального индекса числа и блока 23 элементов задержки, а на управляющий вход с второго выхода первого регистра 11 сдвигав подается код Г выполняемой операции, В результате первый сумматор 21 интервального индекса находит вычет 1, который передается в первый вспомогательный регистр 20,На (Т+ 2)-м такте на входы слагаемых второго сумматора 13 интервального индекса с выходов регистра 7 интервального индекса и первого вспомогательного регистра 20 подаются величины 1 к(А) и 1 соответственно. Второй сумматор 13 интервального индекса получает пару вычетовДС), ЩС)14, которые записываются во второй вспомогательный регистр 19.На (Т+3)-ем такте содержимое ЦС) из В 0 младших разрядов второго вспомогательного регистра 19 поступает на второй вход формирователя 18 интегральных характеристик модулярного кода, где выполняется заключительная стадия процесса формирования поправки Амербаева 6 С). Параллельно с этим двухразрядная величина,)(С)14 с выхода второго вспомогательного регистра 19 через третий вход узла 245 10 15 20 25 30 35 40 45 50 контроля переполнения передается в регистр 30 (фиг 2)Нд заключительном (Т 1 4)-м такте операции вычет 13(С)14 иэ регистра 30 поступает в счетчик 32, Кроме этого, поправка Амербаева 0(С) с выходя формирователя 18 интегральных характеристик модулярного кода передается в узел 24 контроля переполнения через второй его вход, где наряду с признаком Г появляющимся в данный момент на выходе элемента 31 задержки, и цифрами )и и 1 двоичного кода вычета О(С)1 п, содержащегося в счетчике 32, онд используется в качестве входной величины мультиплексора 33, который, реализуя булево соотношение (6), определяет искомое значение признака дддитивного переполнения Й;. Одновременно с этим поправка Амербаева 0 (С) поступает на счетный вход счетчика 32, в результате чего в нем формируется двоичный код вычета Л(С) 0 (С)1, старшая цифра которого представляет собой знак 5(С) суммы С, Признак аддитивного переполнения й и знак ЯС) с первого и второго выходов уэлд контроля переполнения передаются на выходы 26 и 27 устройства, а на выходе 28 устрой(2) ства появляется сигнал г = ттт + з = 1, который служит признаком окончания операции сложения.Инициация очередной аддитивной операции в устройстве для сложения чисел е модулярной системе счисления может быть осуществлена уже нд первом такте текущей операции. т.е. максимальная частота обращения к данному устройству составляет ( =- 1/ъ, (т, - длительность модульного такта). Формула изобретения 1. Устройство для сложения чисел в модулярной системе счисления, содержащее первый и второй регистры сдвига, сумматор-вычитатель, первый блок вычислений интервального индекса числа, блок мультиплексоров, формирователь числа переполнений, формирователь интегральных характеристик модулярного кода, первый вспомогательный регистр, первый сумматор интервального индекса, регистр результата и блок элементов задержки, причем информационные входы первого и второго регистров сдвига подключены соответственно к входу кода операции устройства и входу сигнала начала работы устройства, вход начальной установки которого подключен к входу сброса второго регистра сдвига. входы разрешения сдвига первого и второго реисгров сдвига обьединены и ссединены с тдковым входом устройства, первый информационный вход сумматора-вглчитателя соединен с первым информационным входом устройства, второй информационный вход сумматора-вычитдтеля обьединен с входом первого блока вычисления интервального индекса числа и подключен к второму информационному входу устройства, выходы суммы и разности сумматора-вычитателя соединены соответственно с первым и вторым информационными входами блока мультиплексоров, упрдвляющии вход которого подключен к выходу младшего разряда первого регистра сдвига, выход блока мультиплексоров соединен с входом регистра результата, выходы старших разрядов которого подключены к входам рдзрядов входа формирователя числа переполнений, выход которого соединен с входом блока элементов задержки, выходы первого блока вычисления интервального индекса числа и блока элементов задержки подключены соответственно к входам первого и второго слагаемых первого сумматора интервального индекса, выход которого подключен к входу первого вспомогательного регистра, входы разрядов первого входа формирователя интегральных характеристик модулярного кода соединены с выходами младших разрядов регистра результата, выход второго регистра сдвига является выходом сигнала окончания работы устройства, выходы разрядов выхода результата которого соединены с выходами младших разрядов регистра результата, о т л и ч а ю щ е е с я тем, что, с целью повышения пропускной способности, оно содержит регистр интервального индекса. второй сумматор интервального индекса, второй блок вычисления интервального индекса числа, второй вспомогательный регистр и узел контроля переполнения, причем выход старшего разряда первого регистра сдвига соединен с входом разрешения инвертирования суммы первого сумматора интервального индекса, первый информационный вход устройства соединен с входом второго блока вычисления интервального индекса числа, выход ко. торого подключен к входу регистра интервального индекса. выходы регистра интервального индекса и первого вспомогательного регистра соединены соответственно с входами первого и второго слагаемых второго сумматора интервального индекса,выход которого подключен к входу второго вспомогательного регистра. выходы младших разрядов которого соединены с входами разрядов второго входа формирователя интегральных характеристик модулярного