Устройство для определения максимального и минимального из п чисел, представленных в системе остаточных классов Советский патент 1978 года по МПК G06F7/04 

(54) УСТРОЙСТВ И МИНИМА В СИСТЕМ Изобретение относится к области автоматики и вычислительной техники и может быть использовано для обработки данных в схемах автоматики и цифровых вычислительных машинах, работающих в системе остаточных классов. Известно устройство для сравнения чисел, представленных в системе остаточных классов, содержащее регистры сравниваемых чисел и схему сравнения. Недостатком его является то, что оно позволяет лишь устанавливать совпадение или несовпадение двух чисел по величине и вследствие этого не дает представления об их количественном соотношении (больше, меньше, равно). Наиболее близким техническим решением к предложенному является устройство, содержащее п регистров сравниваемых чисел, п выходных элементов ИЛИ-НЕ, прямые выходы которых соединены с первыми входами соответствующих входных элементов И, со входами п-входового элемента И и со входами первого п-входового элемента ИЛИ-НЕ, регистры наибольшего и наименьшего числа, генератор, выход которого соединен с одним из входов равляющего элемента И, выход которого соедиЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ОГО ИЗ И ЧИСЕЛ ПРЕДСТАВЛЕННЫХ СТАТОЧНЫХ КЛАССОВ йен с одним из входов (п+1)-го входного элемента И, другой вход которого соединен с выходом п-входного элемента И. Недостатком его является низкое быстродействие, обусловленное тем, что для получения результата сравнения необходимо затратить количество тактов, равное абсолютному значению наибольшего числа. Целью изобретения является повышение быстродействия устройства. Это достигается тем, что в иредложенное устройство введены (п + 2) сумматоров, (п 2) входных элементов ИЛИ, п пар выходных элементов И, второй п-входовой элемент ИЛИ-НЕ, две схемы сравнения, элемент задержки, блок памяти, причем выходы п сумматоров соединены с первыми входами соответствующих регистров сравниваемых чисел, первые и вторые выходы которых соединены со входами соответствующих сумматоров и выходных элементов ИЛИ-НЕ, инверсные выходы которых соединены со вторыми входами соответствующих разрядов регистров сравниваемых чисел и с одним из входов второго из каждой пары выходных элементов И, выходы которых соединены с п входами первой и второй схем сравнения. u vy tiiviM n DlUUUil СЛСМ иаЬНсНИЯ {п+ 1 )-ный вход первой из которых через э,чемент задержки соединен с выходом п-входового элемента И, а (п + 1)-ный вход второй схемы сравнения соединен с инверсным выходом первого п-входового элемента ИЛИ-НЕ, вторые и третьи выходы регистров сравниваемых чисел соединены со входами соответствующих пар, выходных элементов И, а вторые выходы регистров сравниваемых чисел соединены также со входами второго п-входового элемента ИЛИ-НЕ, ииверсный выход которого соединен со вторым входом управляющего элемента И, третий вход которого соединен с прямым выходом первого п-входового элемента ИЛИ-НЕ. выход каждого первого из пары выходных элементов И соединен с их входов соответствующих входных элементов ИЛИ, вторые входы которых соединены с выходом управляющего элемента И, а выходы каждого входного элемента ИЛИ через соответствующие входные элементы И соединены с третьими входами соответствующих сумматоров, выходы {п -1- 1 )-ого и (п + 2)-ого сумматоров соединены со входами регистров наименьщего и наибольщего числа, выходы которых соединены с первы ми входами (п.+ 1)-ого и (пЧ-2)-ого сумматора, вторые входы которых соединены с выходами соответствующих входных элементов ИЛИ, первые входы которых соединены соответственно с выходами первой и второй схемой сравнения, а вторые входы соответственно - с выходом (п + 1)-ого входного элемента И и через управляющий элемент И - с выходом блока памяти.

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

Оно содержит регистры сравниваемых чисел 1 1,12,..-.1л , выходные элементы ИЛИ-НЕ 2,,2г,....2„, входные элементы И Зь32,...3„, п-входовой элемент И 4, первый п-входовой элемент ИЛИ-НЕ 5, регистры наименьщего и наибольшего числа 6 и 7, генератор 8, управляющий элемент И 9, сумматоры 10, lOj,..., ..., 10,, , , входные элементы ИЛИ 11, 112,...,И,т, 1 11 nt2, пары выходных элементов И 12 11,12|2,1221,1222,,12,1,12л2, второй п-входовой элемент ИЛИ-НЕ 13, первую и вто рую схемы сравнения 14 и 15, элемент задержки 16 блок памяти 17.

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

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

А, (а,, иг ....а .,. )

А2 (а,2,а2а|, )

А„ ( аГ ,а/ ,...0.:;)

представим в виде

А, К,Рп,+ а,„ ,+ ai A, а;;

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

A,-tiV i,p

А,-а 2, КаАя An-a;i, Кл Рт

кратны Р,п И отличаются одно от другого количеством Р,„ , содержащимся в числах.

Если затем вычитать из сравниваемых чисел Pf, в нуль раньше других обратится наименьшее из чисел. Значения а Д, ,..., не играют роли в случае не одновременного обнуления сравниваемых чисел, так как

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

К моменту начала сравнения в регистрах сравниваемых чисел Ii,l2,l/i записаны сравниваемые числа. На выходах выходных элементов ИЛИ-НЕ 2i,22,...,2r, имеется единичный, сигнал, свидетельствующий о неравенстве срав ниваемых чисел нулю.

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

На выходах и входах элементов И 4 и ИЛИ-НЕ 5 имеется сигнал. На входы схем сравнения 14 и 15 остатки, записанные в (1п + 1)-ных разрядах регистров сравниваемых чисел, не поступают, так как закрыты выходные элементы И 12| 2,1222,..-,12п2 (на вторых входах этих схем сигналы отсутствуют).

После включения единичный импульс появляется на первых входах выходных элементов И ,12,1,1221,...,12,11, разрешая перезапись-содержимого гп-ных разрядов регистров сравниваемых чисел через выходные элементы ИЛИ 11 1,112,---,11, и открытые входные элементы И 3|,32,...,3,.,на входы сумматоров 101,102,...,10, где осуществляется вычитание А,-- а,:,

После перезаписи результатов вычитания в регистры сравниваемых чисел содержимое ш-ных разрядов всех регистров становится равным нулю и на выходе второго л-входового элемента ИЛИ-НЕ 13 появляется сигнал. Управляющий элемент И 9 открывается, и. на входы сумматоров поступают значения Р с частотой генерации. Частоту генератора выбирают такой, что следующая подача значения Р на входы сумматоров осуществляется после перезаписи результатов действий сумматоров в свои регистры.

Сумматоры 1р|,10г,...,10г-, осуществляют вычитание А)-«,,,-k.p,, а сумматоры Юпч и 10к;,2 складывают поступающие на их вход числа.

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

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

При обнулении одного из регистров исчезает сигнал с выхода п-входового элемента И 4,

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

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

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

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

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

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

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

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

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

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

0 из которых через элемент задержки соединен с выходом п-входового элемента И, а (n-f 1)ный вход второй схе.мы сравнения соединен с инверсным выходом первого п-входового э.лемента ИЛИ-НЕ, вторые и третьи выходы регистров сравниваемых чисел соединены со входами выходных элементов И соответствуюи1их нар, а вторые выходы регистров сравнивае.мых чисел соединены со входами второго Л-ВХОДОЕЮго элемента ИЛИ-НЕ, инверсный выход которого соединен со вторым входом управляющего

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

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