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

 

Гс .теитио-тL..

1 (!1) 603987

Союз Советских

Социалистических

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 20.07.76 (21) 2336498/1 8-24 с присоединением заявки № (23) Приоритет (43) Опубликовано 25.04.78)бюллетень № 1 5 (45) Дата опубликования описания.qî,бЦ.чо

2 (5!) М. Кл.

Сг 06 F 7/04

Государственный комитет

Совета Министров СССР по делан изобретений и открытий (53) УДК 681.327 (088.8) (72) Авторы изобретения

M. Г. Факторович и Ю. Д. Пописский (71) Заявитель

Научно-исспедоватепьский и опытно-конструкторский институт автоматизации черной металлургии (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО

И МИНИМАЛЬНОГО ИЗ vt ЧИСЕЛ ПРЕДСТАВЛЕННЫХ

В СИСТЕМЕ ОСТАТОЧНЬ1Х КЛАССОВ

1 2

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

Недостатком его является то, что оно оз- Это достигается тем, что в предложенное оляет лишь Устанавливать совпадение или устройство введены (n + 2) сумматоров, (и 2) несовпадение дВУх чисел по величине и вслед- входных элементов ИЛИ, п пар выходных элествие этого не дает пРедставлениЯ об их KO ментов И, второй и-входовой элемент ИЛИ-НР, личественном соотношении (больше, меньше, две схемы сравнения, элемент задержки, блок явно равно) .. памяти, причем выходы и сумматоров соединеНаиболее близким техническим решением ны с первыми входами соответствующих рек предложенному является устройство, содер- гистров сравниваемых чисел, первые и вторые жащее и регистров сравниваемых чисел, и вы- выходы которых соединены со входами соотвстходных элементов ИЛИ вЂ” НЕ, прямые выходы ствующих сумматоров и выходных элементов которых соединены с первыми входами соот- ИЛИ вЂ” HE инверсные выходы которых соединс20 ! ветствующих входных элементов И, со входа- ны со вторыми входами соответствующих рязми и-входового элемента И и со входами пер- рядов регистров сравниваемых чисел и с одним вого и-входового элемента ИЛИ-НЕ, регистры из входов второго из каждой пары выходных наибольшего и наименьшего числа, генератор, элементов И, выходы которых соединены с выход которого соединен с одним из входов ун- и входами первой и второй схем сравнения, равляющего элемента И, выход которого соедн- 25 (и+1)-ный вход первой из которых через элс603987 мент задержки соединен с выходом и-входового элемента И, а (и+ 1) -ный вход второй схемы сравнения соединен с инверсным выходом первого и-входового элемента ИЛИ-НЕ, вторые и третьи выходы регистров сравниваемых чисел соединены со входами соответствующих пар, выходных элементов И, а вторые выходы регистров сравниваемых чисел соединены также со входами второго и-входового элемента

ИЛИ вЂ” HE, инверсный выход которого соединен со вторым входом управляющего элемента И, третий вход которого соединен с прямым выходом первого и-входового элемента ИЛИ вЂ” НЕ. выход каждого первого из пары выходных элементов И соединен с одним их входов соответствующих входных элементов ИЛИ, вторые входы которых соединены с выходом управляющего элемента И, а выходы каждого входного элемента ИЛИ через соответствующие вход-ные элементы И соединены с третьими входами соответствующих сумматоров, выходы (и -«- 1) -ого и (и + 2)-oro сумматоров соединены со входами регистров наименьшего и наиболь шего числа, выходы которых соединены с первы ми входами (и+1)-ого и (и+2)-ого сумматора, вторые входы которых соединены с выходами соответствующих входных элементов

ИЛИ, первые входы которых соединены соответственно с выходами первой и второй схемой сравнения, а вторые входы соответственно— с выходом (и + 1)-oro входного элемента И и через управляющий элемент И вЂ” с выходом блока памяти.

На чертеже схематически изображено предложенное устройство.

Оно содержит регистры сравниваемых чисел 1«,1>,....1, выходные элементы ИЛИ вЂ” НЕ

2.„2;,....2., входные элементы И 3 „32> 3„, и-входовой элемент И 4, первый п-входовой элемент ИЛИ вЂ” НЕ 5, регистры наименьшего и наибольшего числа 6 и 7, генератор 8, управляющий элемент И 9, сумматоры 10,, 10,..., ..., 10, 10„„,, 10,.2, входные элементы ИЛИ 1 I„

11,,...,11„, 11,.„11„,, пары выходных элементов И 12 ««,12 «,122,,122,,12„„12, второй п-входовой элемент ИЛИ вЂ” HE 13, первую и вто рую схемы сравнения 14 и 15, элемент задержки 16 блок памяти 17.

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

Сравниваемые числа

А« —— (а«,а «....т «,, )

А2 (а ««- .ат )

А, = (а«",а;",...а ) представим в виде

А«=К«Р + а!„

A a = К Рт+ а,л

А,= К,Р+ а, отличаются значениями К и а (i = 1,2,...п) (i) Если из каждого числа вычесть свой остаток а от деления числа на модуль Р,, полученные числа

A,- "= К,г-А2 — а .: = К7Р.п

Ап — а,". = К, P кратны Р,„и отличаются одно от другого количеством P„, содержащимся в числах.

Если затем вычитать из сравниваемых чисел Р„, в нуль раньше других обратится наименьшее из чисел. Значения u . а 2 ... а

«Т) Л1 m не играют роли в случае не одновременного обнуления сравниваемых чисел, так как а" (Р

В случае одновременного обращения в нуль нескольких чисел, наименьшим из них будет число с наименьп«им а", наибольшим — число

m с наибольшим Ы"..

К моменту начала сравнения в регистрах сравниваемых чисел 1«,l I„çàïèñàíû сравниваемые числа. На выходах выходных элементов ИЛИ вЂ” НЕ 2 «,22,...,2, имеется единичный сигнал, свидетельствующий о неравенстве срав ниваемых чисел нулю.

Управляющий элемент И 9 закрыт, так как отсутствует сигнал на его третьем входе (xo20 тя бы один из остатков, записанных в m — х разрядах регистров сравниваемых чисел, не равен нулю) .

На выходах и входах элементов И 4 и

ИЛИ вЂ” НЕ 5 имеется сигнал. На входы схем сравнения 14 и 15 остатки, записанные в

«ш + 1)-ных разрядах регистров сравниваемых чисел, не поступают, так как закрыты выходные элементы И 12,2,122,...,12„2 (на вторых входах этих схем сигналы отсутствуют).

После включения единичный импульс появляется на первых входах выходных элементов И ,12««,12 «,...,12„«, разрешая перезапись содержимого m-ных разрядов регистров сравниваемых чисел через выходные элементы ИЛИ

11 «,112,...,11., и открытые входные элементы

И 3«,3,,...,3п на входы сумматоров 10«,102,...,10 где осуществляется вычитание А — а

«т«

После перезаписи результатов вычитания в регистры сравниваемых чисел содержимое

m-ных разрядов всех регистров становится равным нулю и на выходе второго и-входового

4О элемента ИЛИ вЂ” НЕ 13 появляется сигнал. Уп равляющий элемент И 9 открывается, и, на входы сумматоров поступают значения P с частотой генерации. Частоту генератора выбирают такой, что следующая подача значения P на входы сумматоров осуществляется после пе45 резаписи результатов действий сумматоров в свои регистры.

Сумматоры 10 «,10 >,...,10., осуществляют вычитание А — 0;„- 1с р., а сумматоры 10„, и

10„. складывают поступающие на их вход

Процесс вычитания — сложения продолжается до тех пор, пока одно или несколько чисел одновременно не станут равными нулю.

В этот момент на инверсном выходе выходного элемента ИЛИ вЂ” НЕ 2i (i = 1,2,....,п) обнулившегося регистра появляется сигнал и значение а, „поступает на вход первой схемы сравнения 14, которая перезаписывает результат сравнения (в случае обнуления нескольких IHсел) или само это число в сумматор 10 ..«.

При обнулении одного из регистров исчезает сигнал с выхода и-входового элемента И 4, 603987 а через элемент задержки 1 6 с некоторой задержкой он исчезает на (п+1) входе первой схемы сравнения 14, в результате чего нс осуществляется дальнейшее сравнение чисел в первой схеме сравнения 14.

Исчезновение сигнала с выхода п-входового элемента И 4 приводит к закрыванию входного элемента И 3.<, в результате чего в регистре наименьшего числа 6 оказывается записанным наименьшее из сравниваемых чисел.

Единичный сигнал, появившейся на инверсном выходе соответствующего выходного элемента ИЛИ вЂ” НЕ 2 „2,,...,2n сбрасывает в нуль содержимое дублирующего (m+ 1) -ого разряда своего регистра.

Процесс вычитания р„, продолжается до тех пор, пока не обнулятся все числа, а значит, и наибольшее из сравниваемых. В этот момент на (п+1)-ном входе второй схемы сравнения 15 появляется сигнал и сравниваются на. максимум остатки а, чисел, обнулившихся 20 в этом такте. Результат сравнения через входной элемент ИЛИ l! .„. перезаписывается в сумматор 10,. .

В регистре 7 наибольшего числа оказывается записанным наибольшее из сравниваемых чисел. Исчезновение сигнала на прямом выходе первого п-входового элемента ИЛИ вЂ” НЕ 5 приИ водит к закрытию управляющего элемент.

ы

9, что обеспечивает непоступление значения

D, на входы сумматоров.

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

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

Устройство для определения максимального и минимального из и чисел, представленных в системе остаточных классов, содержащее и регистров сравниваемых чисел, п выходных элементов ИЛИ-НЕ, прямые выходы которых соединены с первыми входами соответствуюших входных элементов И, со входами и-входового элемента И и со входами первого и-входового элемента ИЛИ-НЕ, регистры наибольшего и наименьшего числа, генератор, выход которого соединен с одним из входов управляюшего элемента И, выход которого соединен с одними из входов (n + 1) -ого входного элемента 11, другой вход которого соединеH с выходом и-вхо дового элемента И, отличающееся тем, что, с целью повышения быстродействия, в устройство дополнительно введены (п+2) сумматоров, (и+ 2) входных элементов ИЛИ, п пар выходных элементов И, второй и-входовой элемент ИЛИ-HF., две схемы сравнения, элемент задержки, блок памяти, причем выходы п сумо маторов соединены с первыми входами соответствующих регистров сравниваемых чисел, первые и вторые выходы которых соединены со входами соответствуюших сумматоров и выходных элементов ИЛИ-HF, инверсные выходы которых соединены со вторыми входами соответствующих разрядов регистров сравниваемых чисел и с одним из входов второго из каждои пары выходных элементов И, выходы которых соединены с и входами первой и второй схем сравнения, (и+1)-ный вход первой из которых через элемент задержки соединен с выходом и-входового элемента И, а (и+ 1)ный вход второй схемы сравнения соединен с инверсным выходом первого и-входового элемента ИЛИ вЂ” НЕ, вторыс и третьи выходы регистров сравниваемых чисел соединены со входами выходных элементов И соответствуюших пар, а вторые выходы регистров сравниваемых чисел соединены со входами второго и-входового элемента ИЛИ вЂ” HE, инверсный выход которого соединен со вторым входом управляющего элемента И, третий вход которого соединен с прямым выходом первого ll-входового элемента ИЛИ вЂ” НЕ, выход каждого первого из пары выходных элементов И соединен с одним из входов соответствующих входных элементов

ИЛИ, вторые входы которых соединены с выходом управляющего элемента И, а выходы каждого входного элемента ИЛИ через соответствующие входные элементы И соединены с третьими входами соответствующих сумматоров, выходы (п + 1) -ого и (n + 2) -ого сумматоров соединены со входами регистров наименьшего и наибольшего числа, выходы которых соединены с первыми входами (п + 1) -ого и (и + 2 ого сумматора, вторые входы которых соединены с выходами соответствующих входных элементов ИЛИ, первые входы которых соединены соответственно с выходами первой и второй схемой сравнения, а вторые входы соответственно — с выходом (п + 1)-ого входного элемента И и через управляющий элемент

И вЂ” с выходом блока памяти.

603987

Составитель P. Яворовская

Техред О. Луговая Корректор Н. Тупица

Тираж 826 Подписное

Редактор В. Гончуков

Заказ 2089/40

11НИИ ПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4