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

(51)5 0 06 Е 7/04 ПИСАН И ЗОБР ТЕН ут им. листиП,Мар АКик к ус ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Киевский политехнический инсти50-летия Великой Октябрьской социаческой революции(54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИСИМАЛЬНОГО ЧИСЛА(57) Изобретение относится к автомавычислительной технике, в частност Изобретение относится к автоматике и вычислительной технике, в частности к устройствам сортировки данных, и предназначено, например, для электронных цифровых систем повышенного быстродействия, выполненных на узлах с большой степенью интеграции.Цель изобретения - повышение быстродействия и расширение области применения за счет .возможности восстановления исходной информации.На чертеже изображена функциональная схема устройства.Устройство содержит.л гоупп элеменмяти, п 1 групп элементов И 21, 222 п, 21, 22, , 2 п21, 2 в," 2 п, п много 1697076 А ройствам сортировки данных, и предназначено; например, для электронных цифровых систем повышенного быстродействия, выполненных на узлах с большой степенью интеграции, Целью изобретения является повышение быстродействия и расширение области применения за счет возможности восстановления исходной информации. Устройство содержит гп групп элементов 1 памяти, гп групп элементов И 2, п многовходовых элементов ИЛИ 3, п управляющих элементов И 4, п элементов НЕРАВНОЗНАЧНОСТЬ 7 регистр 8 результата, и восстанавливающих элементов И 9. В конце работы устройства код максимального числа фиксируется на регистре 8 результата, а информация на элементах 1 памяти восстанавливается в первоначальном виде. входовых элементов ИЛИ 3.1-3.п., п управляющих элементов И 4,1 - 4.п, вход 5 начала работы, выход 6 конца работы, п элементов НЕРАВНОЗНАЧНОСТЬ 7.1 - 7.п, регистр 8 результата, й восстанавливающих элементов И 9,1 - 9 п,Устройство для выделения максимального числа может выполняться в виде заказной специализированной БИС с использованием различных технологий либо в виде платы с использованием серийных ИМС малой и средней степени интеграции серий К 155, К 531, К 555. При выполнении устройства по последнему вариантус использованием, например, ИМС серии К 155 элементы 1 памяти могут строиться нэ микросхемах К 155 ТВ 9; причем вхо 1897076ды Я и Я могут быть использованы для записи информации в элемент 1 памяти, вход:и К объединены и образуют вход инвертирования состояния элемента 1 памяти, входсинхронизации С и вход синхронизации ргистра 8 результата объединены и подсоединены к внешнему источнику тактирующихсигналов, Элементы И 2, 4, 9 можно выполнять с использованием ИЬЛС К 155 ЛИ 1, многовходовыые элементы ИЛИ 3-с Оиспользованием, ИУС К 155 ЛЛ 1, элементыНЕРАВНОЗНАЧНОСТЬ 7 - с использованием ИМС К 155 ЛП 5, Регистр 8 результата выполняют в виде набора триггеров.,реализуемых, например, микросхемами 15К 155 ТВ 9, причем выводы Б и г используютдля установки в "1" всех разрядов оегистрэ8 при приведении устройства в исходнгесостояние, входподключен к источникупотенциала логического нуля, а вход К подсоединен к выходу соответствующе-о элемента НЕРАВНОЗНАЧНОСТЬ 7,Устройство работает следующим образом.Перед началом работы все разряды регистра 8 устанавливают в единичное состояние, В элементы 1 памяти заносят гпп-разрядных чисел, образующих множес во Й,Сигнал начала операции подают на вход 305 устоойства в виде положи.ельного потенциала.Пусть для произвольного Х "- Р, б 1х,б 2 ,бг(гх и ) - гозиции (начиная сох хстарших разрядов) нулей в записл кода числа Х, И пусть далее В б Й. - искомое максимальное число на множестве Й. Так как несуществует такого У Й, что б 1б 1, "оочевидно что на выходах элементов ИЛИ40Зл(т ( бБ 1) формируются едлничные пстенциалы, открывающие соответствующие управляющие элементы И 4,т дляпрохождения сигнала с входа 5, На выходемноговходового элемента ИЛИ З,о 1 фоо 45мируется нулевой потенциал, который закрывает управляющий элемент И 4,бдля прохождения сигнала с входа 5. Соответственно, на выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.б 1 формируетсяоОединичный сигнал (так как потенциалы навтором входе и выходе элемента И 4,б 1 неВ,совпадают), который поступает нэ инвертирующие входы всех элементов1 ,1 Я ,1 Я, в памяти л на вход уст:,нонки в нуль б -гс разряда регистра 8 реВзультата. По приходе перепада тактовогимпульса переключаются в инверсное ссстояние все элементы 1 г,1 , 11, в памяти и ус ганавливается в нуль о 1 -ый разБряд регистра 8 результата. Поскольку элемент Д памяти устанавливается вединицу появляется единичный потенциална выходе элемента ИЛИ З,б 1, который отВкрывает управляющий элемент И 4.б 1 длявпро.окдения единичного сигнала с выходаэлемента И 4 б 1 -1 (или непосредственно свхода 5,.при с 11 =1), Элементы И 4.цБ(б 1 Вцб 2) гакже отказываются открытымиединичными сигналами с выходов соответствующих элементов ИЛИ З,ц для прохождения сигнала с входа 5, На выходе элемента3,б 2 оказыг 3 ается нулевой потециндл, котоВрый закрывает элемент И 4,б 2 и, так какБпотенциалы на втором входе и выходе последнего не совпадают формируется единичный потенциал на выходе элементаНЕРАВНОЗНАЧНОСТЬ 7.б 2, которым инвертируется содержимое элементов1 Я, 1 Я1 "4, памяти и устанавливается внуль б 2 -ыи разряд регистра 8 результата,ВСоответственно открь;вается элемент И4,б 2Аналогично происходят инвертирование соответствующих элементов памяти 1 иустановка в нуль разрядов оегистра 8 реБ Б Взультата в позициях бз, бл, бгвКак только вследствие инвертирования2 лэлементов 3, 3 г "д открываетсяэлемент И 4.бгБ, потенциал с входа 5 пров Бходит чере: цепочку открытых элементов И4,1-4,п на выход 6 устройства, Так как всеразряды б 1 ,б 2,б регистра 8 результаБ, Б Бта установл:-ны в нуль(остальные нахсдятсяв единичном, исходном, состоянии), то кодна регистре 8 резуль.,ата является кодоммаксимального числа В 6 Й,Нулевые разряды регистра 8 результатасоответствуют инвертированным столбцамэлементсв 1 памяти, Единичные сигналы синверсных выходов упомянутых разрядовб 1,б 2 бг поступают на входы элеменВ В Втов И Я и по появлению сигнала на выходеэлемента И 4,п (открывающего элементы И9) пБооходят на выход элементов И 9,б 19.б 2 ,ц,б 2,.,9.бг И даЛЕЕ На ВХОДЫ СОВ Вответствующих элементов НЕРАВНОЗНАЧНОСТЬ 7(на другие.даа их входа поступаютединичные сигналы), так что на выходахэлементов НЕРАВНОЗНАЧНОСТЬ 7,б 1,7,б 2 7,бгз формируются единичные сигВ вналы, которые инвертиоуют ранее инвертированные в процессе поиска элементы 1памяти, восстанавливая тем самым их ис.одное состояние,Работа устройства может быть иллюстрирована следующим примером, Пусть наэлементах 1 памяти хранятся числа и,гп=5):1 0 0 ", 1 0 0 11 1 1 0 1 1 О 11 0 1 О 1 0 1 00 1 1 1 1 1 0 000101010Для макслмального числа В=11101301,б 1 =4, б 2 =7,гв=2: Соответственно. при подав вче сигнала на вход 5 элементы И 4,1-4,3 сткрыты для его прохождения, а элемент И 4,4- закрыт, Единичный сигнал формируется навыходе элемента Н ЕРАВ НОЗ НАЧ НОСТЬ 7.4и соответственно инвертируются элементы 1памяти четвертого столбца и устанавллвается в нуль четвертый разряд регистра 8, После первого такта на элементах 1 паь ятихранятся коды: .1 0 0 0 1 0 О 11 1 1 1 1 1 0 1 201 0 1 1 1 0 1 00 1 1 0 1 1 0 О0 0 1 1 1 0 1 0После первого такта сигнал с входа 5распространяется через открытые элементы И 4.1 - 4.6 до входа закрытого элементаИ 4.7. На выходе элемента НЕРАВНОЗНАЧНОСТЬ 7,7 формируется единичный сигнал,которым инвертируется седьмой столбецэлементов 1 памяти, та что после второго 30такта на них хранятся коды:1 0 0 0 1 0 1 11 1 1 1 1 1 1 11 0 1 1 1 0 0 00 1 1 0 1 1 1 0 350 0 1 1 1 0 0 1а на регистре 8 результата фиксируется код111101101 максимального числа, нули в котором указывают на номера столбцов элементов 1 памяти, которые инвертируются в 40третьем такте для восстановления информации на элементах 1 памяти в первоначальном виде,Формула изобретения 45 Устройство для выделения максимальногочисла, содержащее ги групп поп элементов памяти, где гп - число сравниваемых чисел, и - разрядность сравниваемых чисел. ги групп50 пс иэлементов И, и мнсгсвхсдсвых зле. ментов ИЛИ, регистр результата, и управляющих элементов И, причем вход начала работы устройства г 1 сдключен к первому входу первогоуправляющего элемента И, выходы первы элементов памяти всех групп соединены с первыми входами первых элементов И соответствующих групп и входами первого мнсговходовсго элемента ИЛИ, выход р-гс элемента И в каждой группе, где р=1,2,и, соединен с первым входом р+1-го элемента И той же группы, выходы )-ых элементов И всех групп, где - 1,2 (и), соединены с входами 1+1-го многовходовсго элемента ИИ, выход 1+1-го элемента памяти в каждол рупие соединен с вторым входом )-гс элемента И соответствующей группы, вхсды установки в нулевое состояние -ых элементов памяти всех групп, где =1,2и, обьединены, отл ича ющееся тем, что,сцелью повышения быстродействия и расширения области применения за счет возможности восстановления исходной информации, в него введены и элементов НЕРАВНОЗНАЧНОСТЬ и и восстанавливающих элементов И, причем выход)-го управляющего элемента И подключен к первым входам )+1-гс управляющего элемента И и )+1-гс элемента НЕРАВНОЗНАЧНОСТЬ, первы 1 вход первогс элемента НЕРАВНОЗНАЧНОСТЬ подключен к входу начала работы устройства, выход -го управляющего элемента И соеди-, нен с вторым входом -го элемента НЕРАВНОЗНАЧНОСТЬ, а второй вход - с выходом -го многовходового элемента ИЛИ, выход -го элемента НЕРАВНОЗНАЧНОСТЬ подключен к входам установки в нулевое состояние -х элементов памяти всех гоупп и входу установки в нулевое состояние -го разряда регистра результата, инверсный выход которого подключен к первому входу -го восстанавливающего элемента И, выход которого соединен с третьим входом 1-го элемента НЕРАВНОЗНАЧНОСТЬ, выход иго управляющего элемента И подключен к вторым входак всех восстанавливающих элементов И и является выходом конца работы устройства,1697076 Составитель Е.ИвановаТехред М.Моргентал Корректор М,Кучерявая Редактор то акаэ 4306 Тираж Подписное ВНИИПИ Государственного комитета по иэобретениям и открытиям при ГКН 113035, Москва, Ж, Раушская наб 4/5 Проиэводственно-иэдательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101