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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик 1199904 )(22) Заявлено 100881 (21) 3326709/18-24с присоединением заявки МВ(23) ПриоритетОпубликовано 230283, Бюллетень М 9 7Дата опубликования описания 230283 Р 1 М К з 0 06 Р 7/02 Государственный комитет СССР по делам изобретений и открытий(72) Авторы изобретен В. И, Корнейчук В.П. Тарасенко Зеебауэр (ВНР Киев ий орд Велик Ленина политехничесОктябрьской социалис летия) ) Заявител 54) УСТРОЙСТВО ДЛ ЬНОГО ИЗ в ЧИСЕ РЕДЕЛЕНИЯ МАК л к 15 п 5 Изобретение относится к автоматйке и вычислительной технике, в.част-.ности к устройствам сортировки чисел, и может быть использовано в цифровых вычислительных системах,выполненных на узлах с больщой степеньюинтеграции,Известно устройство для определения экстремального из и чисел, содержащее связанные собтветствующим об"разом регистр, полусумматор, элементИ-НЕ, в узлов сравнения, каждый изкоторых содержит полусумматор, элемент запрета, В-триггер, элементИ-НЕ (1),Недостатком этого устройства является низкое быстродействие.Наиболее близким к изобретениюо технической сущности.и достигаемому эФФекту является устройстводля определения максимального из вдвоичных чисел, содержащее в группэлементов И,в групп элементов памяти,в групп элементов ИЛИ, многовходовыеэлементы ИЛИ, управляющие элементыИ, регистр результата, элементы задержки, причем вход управления началом работы соединен с первым входомпервого управляющего элемента И и свходом первого элемента задержки,выход каждого ) -го управляющего элемента И, где ) = 1,2, п, и - чисо разрядов сравниваемых кисел, подлючен к информационному входу ) "го разряда регистра результата, инверсный выход каждого первого элемента памяти К-й группы, где К = 1,2,в, соединен с первым входом первого элемента И К-й группы, выход каждого из которых подключен к входу установки в нулевое состояние второго элемента памяти К-й группы и к первому входу первого элемента ИЛИ К-й группы, выход каждого Р-го элемента ИЛИ каждой К-й группы, гге Р = 1,2,(п), соединен с первым входом (Р+1)-.го элемента ИЛИ К-й группы, инверсный выход каждого 1-го элемента памяти К-й группы, где 1 = 2,3(п), подключен к первому входу 1-го элемента И К-й группы выход которого подключен к второму входу (1"1)-го элемента ИЛИ К-й группы, прямой выход каждого. ) -го элемента памяти К-й группы соединен с К-ьж входом )-го многовходового элемента ИЛИ, выход каждого из,которых подключен ко второму входу ) -го, управляющего элемента И, вЫход каждого-го управляю. щего элемента И соединен со вторыми(2),Недостатком укаэанного устройстваявляется низкое быстродействие, связанное с тем, что цикл сравнения производится поразрядно, т,е. для выделения максимального числа из в двоич-,ных чисел необходимо произвести итактов поразрядного сравнения, гдеи - число разрядов сравниваемых чисел.10Целью изобретения является повышение быстродействия.ПостаВленная цель достигается тем,что в устройстве для определения мак-.,симального из в чисел, содержащем в ;15групп элементов памяти, в групп элементов И, группу в-входовых элементовИЛИ, в групп элементов ИЛИ, регистррезультата., и узлов управления, причем информационные входы устройства 20соединены с информационными входамиэлементов памяти групп, прямой выходкаждого 1-го элемента памяти-й группы, где 1 = 1,2.и, 1 = 1,2 в,подключен к 1-му входу-го в-входо вого элемента ИЛИ группы, выход каждого из которых соединен с первымвходом 1-го узла управления, инверсный выход каждого К-го элемента памя,ти-й группы подключен к первому входу Кго элемента И 1-й группы, гдеК = 1,2, (и), выход каждого Р-гоэлемента И каждой ;й группы, гдеР = 1,2, (и), соединен с входомустановки в нулевое состояние(Р+1) -го,элемента памяти 1-й группы и с первымвходом (Р)-го элемента. ИЛИ 1 -йгруппы, выход первого элемента И каждой группы подключен к входу установки в нулевое состояние второго элемента памяти-й группы и к второму 40входу первого элемента ИЛИ 1 -й груп,пы, выход каждого 1-го элемента ИЛИкаждой ) -й группы .соединен с вторымвходом (2+1)-го элемента ИЛИ, где2 =, 1,2, и-З, 1 -й группы, первый 45выход каждого 1-го узла управлениясоединен с 1-ым.входом регистра результата и с вторым входом 1-ых элементов И всех групп, вход управления:устройства подключен к второму входу 50первого узла управления, второй выход каждого К-го узла управления соединен с вторым входом (К+1)-го узлауправления,Кроме того, кажцый К-ый узел управления состоит из элементов И, ИЛИ, НЕ,элемента задержки, причем первыйвход узла соединен с первым входомпервого элемента И и через элементНЕ - с первым входом второгб элемен-, цта И, выход которого подключен к первому входу элемента ИЛИ, второй входузла соединен с вторыми входами первого и второго элементов И, выходпервого элемента, И подключен к первому выходу узла и через .элемент задержки к второму входу элемента ИЛИ, выход которого соединен с вторым выходом узла, и-ый узел управления содержит элемент И, первый и второй входы которого соединены с первым и вторым входами узла соответственно, а выход - с первым выходом узла.На.чертеже приведена функциональная схема устройства.Устройстуо содержит в групп элемен 1 1 гтов И 1, У 1 У, - 1 л 11 Р 12 Р 1 Г/Щ Ф Ъ11 ф.1 групп Элементов ИЛИ2, - 2 д д у 2 2 2 1Ф щ в212 г,2, в гРУппг элементов1памяти 3, З,3, у 31, ЗгП 1 11 Ч ФЗп г 31 ю Згг Зц и в-входовых элементов ИЛИ 41, 4 г,4 и, и узлов управления 51, 52,5 каждый из которых состоит из элемента задержки 6, элемента НЕ 7, элемента И 8, эле-, мента ИЛИ 9, .элемента И 10, выход 11 устройства, регистр 12 результата, вход 13 управления устройства.Устройство работает следующим образом. Перед началом работы регистр 12 результата сбрасывается в нулевое состояние, так же как и все элементы па- мяти 3 перед приемом чисел. В элементы 3 памяти заносятся в, и-разрядных чисел и в устройство поступает импульс начала операции по входу 13 управления устройства, который разрешает прохождение сигнала через элемент И 10 узла 51 управления. Если хотя бы :в однОм элементе памяти 3",1 = 12в, записана единица, сигнал через элемент ИЛИ 41 и элемент И 10 поступает .в первый разряд регистра 12 результата и .записывает в него единицу, этот же сигнал, с выхода элемента И 10 поступает на вторые входы элементов И 1. Если в 1-.ом (1 Я(12 в ) ) числе старший разряд равен нулю, то с инверсного выхода 1-го элемента 3 памяти снимается разрешающий потенциал, открывающий элемент.И 1, и на все элементы 3 памяти младших разря- дов 1-го числа через элемент ЕЛИ 2 поступает сигнал, сбрасывающий их в нулевое состояние. таким 1 образом данное число исключается из процесса дальнейшего сравнения, Если на выходе элемента И 10,( сформирован был единичный сигнал, то он поступает на элемент 5 задержки управления, обеспечивающий задержку сигнала на время переключения элементов 3 памяти, и затем, пройдя через управляющий элемент ИЛИ 9 узла 51 управления, поступает на вход управляющего элемента И 10 узла 52 управления, обеспечивая обработку второго разряда всех сравниваемых чисел описанным образом, Если в каком-то из обрабатываемых разрядов всех сравниваемъв чисел окажутся записанными.нули, то сбрасыванйя в нуль элементов 3 памяти.не потребуется. В этом случае на выходе элемента ИЛИ 4 , где 1 - номер обрабатываемого разряда, 1 = 1,2, (п), бу дет сформирован сигнал нулевого уровня, который, инвертируясь элементом НЕ 7 1-го узла 5 управления и пройдя через элемент И 8, открытый тем же сигналом, который открывает элемент 10 И 10, через элемент ЙЛИ 9 поступнт на вход элемента И (1+1) го узла управления, блокируя таким образом, задержку сигнала элементом б задержки. Описанная операция позволяет сократить 15 обработку разряда, не требующего сбро- са в нуль элементов З.памяти, примерно вдвоеТакю образом, предлагаемое устройство позволяет повысить быстродейст вие в.средием на 16 при среднем повышении аппаратурных затрат на 5,8 , причем эффективность устройдтва повы,1 рается при увеличении числа сравниваемых чисел и числа разрядов. 25формула изобретения1. Устройство для определения максимального из ш чисел, содержащее в групп элементов памяти, в групп элементов И, группу в-входовых элементов ИЛИ, в групп элементов ИЛИ, регистр результата, п узлов управления, при" чем информационийе входы устройства З 5 соединены с информационныки входами:," элементов памяти групп, прямой .выход каждого .1-го элемента памяти 1 -йФгруппы, где 1 = 1,2,.и,= 1,2, щ,подключен к 1-му входу-го е-вхо-4 О дового элемента ИЛИ группы, выход каж-, дого из которых соединен с первый входом 1-го узла управления, инверсный выход каждого х-го элемента памяти, -й группы подключен к первому 45 .входу и-го элемента И .( -й груйпы, где к = 1,2,(п),выход каждого р-го элемента И каждой-ой группы, где р = 2,3, (п), соединен с входом установки в нулевое состояние(р+1)-го элемента памяти-й группыи с первым входом (р)-го элементаИЛИ ) -и группы, выход первого элемента И каждой 1 -й группы подключенк входу установки в нулевое состояниевторого элемента памяти 1 -й группыи к второму входу первого элементаИЛИ-й группы, выход каждого 1-гоэлемента ИЛИ каждой 1 -й группы соединен с вторым входом (1+1)",го элемента ИЛИ, где 11,2,(п), ) -йгруппы, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродейст-.вия, в нем первый выходкаждого 1-гоузла управления соединен с 1-.ьи входом регистра результата и с вторимвходом 1-ых элементов И всех групп,вход управления устройства подключенк второму входу первого .узла управления, второй выход каждого к-го узлауправления соединен с вторыа входом(К+1) -го узла управления.2. Устройство по п.1,о т л.и ч аю щ е е с я тем, что к-ый узел управления состоит из элементов И, ИЛИ,НЕ, элемента задержки, причем первыйвход узла соединен с первым входомпервого элемента И и через элементНЕ - с первым входом второго элементаИ; выход которого подключен к первому входу элемейта ИЛИ, второй входузла соединен с вторыми входами первого и второго элементов И, выход первого элемента И подключен к первомувыходу узла и через элемент задержки - к.второму входу элемента ИЛИ, выход которого соединен с вторыа. выхо-дом узла, и-ый узел управления содержит элемент И, первый и второй входыкоторого соединены с первым и вторымвходами узла соответственно, а выходс первыч выходом узла,ФИсточники информации,принятые во внимание при экспертизе1. Авторское свидетельство СссРЮ 726528, кл. О 06 Р 7/04, 1980.2. Авторское свидетелЬство СССРпо заявке 9 2886601/18-24,кл. 6 06 Г 7/04, 1980 (прототип).999041 Составитель В.Техред М, Гергел едактор Т. Киселе аказ 1156/71 ная, 4 лиал ППП " Патент , г, Ужгород, Ул, П ТиражВНИИПИ Государпо делам изо 113035, Москва, Ж лкин Корректор А 04 Подписноественного комитета СССРбретений.и открытий