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

х (54) (57) 1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕ- н НИЯ МАКСИИАЛЬНОГО ЧИСЛА, содержащее т 1 Ч узлов анализа, каждый из которых к содержит триггер, элементы И и НЕ,в о т л и ч а ю щ е е с я тем, что, Щ с целью увеличения быстродействия, в в него введены блок динамического с приоритета, а в каждый узел анали" б за - второй триггер, первый и второй у элементы задержки, согласующий эле-в мент, блок сравнения, группу элемен- г тов И, причем информационные входы к устройства подключены к первым ин- ч формационным входам соответствующихд узлов анализа, вторые информацион- в ные входы которых подключены через к общую магистраль к выходам устройст" вг ва, в каждом узле анализа первые ии- к формационные входы соединены с инфор- с мационными входами элементов И груп" н пы и с первыми информационными входа- т ми блока сравнения, выходы элемен- тов И группы, являющиеся информацион- ч ными выходами узла анализа, соедине- м ны с вторыми информационными входамииблока сравнения, авыход блока срав- ( ервую по й кения соединен с первым входом первого элемента ИЛИ и через согласующий элемент - с входом установки внулевое состояние первого триггера,с входом элемента НЕ и через общуюшину с выходами согласующих элементов всех узлов анализа, выход первогоэлемента ИЛИ, являющийся выходом сиг".нала запроса узла анализа, подключенк соответствующему входу блока динамического приоритета, выход элемента НЕ в каждом узле анализа подключен к первому входу элемента И, выод которого соединен с входом устаовки в единичное состояние первогориггера, выход которого подключен 9первому входу второго элемента ИЛИ,ыход которого соединен с управляюими входами элементов И группы, С,ход разрешения анализа узла анализаоединен с соответствующим выходом Ялока динамического приоритета, а взле анализа - с входом установкиединичное состояние второго тригера, через первый элемент задержи - с вторым входом элемента И, иерез второй элемент задержки с вхо- СЛом установки в нулевое состояние 3торого триггера, выход которого под- влючен к вторым входам первого иторого элементов ИЛИ, шина установи начального состояния устройстваоединена с входами установки в едиичное состояние первого и второго фвриггеров всех узлов анализа,2. Устройство по и. 1, о т л и -а ю щ е е с я тем, что блок динаического приоритета содержит пвторую группы элементов И-НЕ11-1)/2 элементов И-НЕ в каждой,го элемента И каждого узла анализа соединен через элемент НЕ с первым входом второго элемента И, второй .вход которого подключен к выходу эле- , мента ИЛИ, а выход - к входу установ ки в нулевое состояние триггера того же узла анализа 2 3.Недостатком известного устройства является низкое быстродействие, вызванное последовательным поступлением сравниваемых чисел в устройство, а также отсутствие значения выбранного числа.Цель изобретения - увеличениебыстродействия устройства, а также расширение функциональных возможностей путем выдачи кода числа;Поставленная цель достигается тем, что в устройство для определения максимального числа, содержащее Й узлов анализа, каждый из которых содержит триггер, элементы И и НЕ, введены блок динамического приоритета, а в каждый узел анализа - второй триг-, гер, первый и второй элементы задерж-. ки, согласующий элемент, блок сравнения, группу элементов И, причем информационные входы устройства подключены к первым информационным входам соответствующих узлов анализа, вторые 30 информационные входы которых подключены через общую магистраль к выходам устройства, в каждом узле анализа первые информационные входы соединены с информационными входами эле- З ментов И группы и с первыми информационными входами блока сравнения, выходы элементов И группы являющие" ся информационными выходами узла ана" лиза, соединены с вторыми информаци оннымн входами блока сравнения, а выход блока сравнения соединен с первым входом первого элемента ИЛИ и через согласующий элемент - с входомустановки в нулевое состояние первогод 5 триггера, с входом элемента НЕ и через общую шину с въкодами согласующих элементов всех узлов анализа, выход первого элемента ИЛИ, являющийся выходом сигнала запроса узла ана лиза, подключен к соответствующему входу блока динамического приоритета, выход элемента НЕ в каждом узле анализа подключен к первому входу элемента И, выход которого соединен с входом установки в единичное состояние первого триггера, выход которого подключен к первому входу второго-. "зэлемента ИЛИ, выход которого соединенс управляющими входами элементов Игруппы, вход разрешения анализа узлаанализа соединен с соответствующимвыходом блока динамического приоритета, а в узле анализа - с входомустановки в единичное состояние второго триггера, через первый элементзадержки - с вторым входом элемента И, и через второй элемент задерж-:ки с входом установки в нулевое состояние второго триггера, выход которого подключен к вторым входам первого и второго элементов ИЛИ, шинаустановки начального состояния устройства соединена с входами установки в единичное состояние первого ивторого триггеров всех узлов анализа. Блок динамического приоритета содержит первую и вторую группы элементов И-НЕ по М(К-)/2 элементов И"НЕ в каждой, группу элементов ИЛИ-НЕ, включающую К элементов ИЛИ-ВЕ, группу элементов ИЛИ и группу элементов задержки по М(И-)(8-2)/3 соответствующих элементов в каждой, причем выход 1-го элемента И-НЕ первой, груп- пы, где 1 1, 2, , К (8-1)/2, соединен с первым входом 1-го элемента И-НЕ второй группы, выход которого соединен с первым входом .1-го элемента И-НЕ первой группы, в каждой паре ,е входов из всех И(К)/2 пар входов блока динамического приорите та, где 14(вФ, Ъ-й и пф"й входы соединены соответственно с вторюи входами двух (28-%)(с)/2+п-)-х элементов И-НЕ первой и второй групп, входы 1-го элемента ИЛИ-НЕ группы элементов ИЛИ-НЕ, где 1, 2,.; М, соединенй соответственно с вйходами (К"1)-х элементов И-НЕ первой и второй группы, вторые входы которых соединены с 1-м входом блока динамичес" кого приоритета, выход -го элемен" та КЮ-НЕ соединен с 1-м выходом бло.ка динамического приоритета, для каждой тройки входов -о-го, 3-го и 1 го входощ блока динамического приоритета, из всех возможных й(К)(Ю)/ /3 троек входов, где 4 ЫфСу 4 Й, выход (2 К-а)(а)/2+Р+рюЦ-го элемента И-НЕ .первой группъ 1, выход (2 М-а)(ф 6-1)/2+ +рюш-го элемента И-НЕ второй группы, выход (2 К-)(р-)/2+-ф)-го элемента И-НЕ первой группы соединены соот(элемента ИЛИ группы элементов ИЛИ, а выход (2 й-Ы) Ы"1)/2+ф-фО-го элемен- . та И-НЕ второй группы, вьиод (2 М-о (К)/2+у"Ц-го элемента первой груп" пы, выход (2 Й")(3"1)/2+у-р)-го элемента И-НЕ второй группы соединены соответственно с первым, вторым и третьим входами/элемента ИЛИ группы элементов ИЗ%,выход -го элемента ИЛИ, где 0 =1, 2,14(М)(М)/3, через элементзадержки соединен с третьим входомсоответствующего элемента И-НЕ первой и второй групп, выход которогосоединен с первым входом -го элемента ИЛИ.На фиг. 1 представлена схема предлагаемого устройства; на фиг, 2 -30схема блока анализа; на фиг. 3 - схема блока динамического приоритета;на фиг. 4 - схема группы элементов И;на фиг, 5 - схема блока сравнения;на фиг. б - схема поразрядного срав- Знения.Устройство содержит узлы анализа11, 12 ., 14, блок 2 динамическогоприоритета, общую магистрапь 3, информационные входы ч 1, 4, , 41Ф 40устройства, общую шину 5, информационный выход 6 устройства, шину 7 начальной установки, входы 8 блока динамического приоритета, выходы блока 9.динамического приоритета, информациоииые входы 10 узлов анализа. Блокдинамического приоритета содержитгруппу элементов И-НЕ 11 1, 112,11 д, группу элементов И-НЕ 121,12, , 12. где А= М(й)/2, груп-опу элементов ИЛИ 13,1, 13, 13, группу элементов 141, 14 14 б задержки, где В =И(8-1)(8-2)/3, группуэлементов ИЛИ-НЕ 15, 152, , 15 м,Узел анализа содержит группу элемеитов И 16, блок 17 сравнения, элемент И 18, триггер 19, элементы ИЛИ 20 и 21, триггер 22, элемент 23 задержки, элемент НЕ 24, согласующий элемент 25, элемент 26 задержки. Группа элементов И содержит элементы И 271, 27 .27, где М - число разрядов сравниваемых чисел, Блок сравнения содержит выход 28 и М схем поразрядного сравнения 291, 292, , 29. Схема поразрядного сравнения содержит элементы И-НЕ 30 - 33, элементы НЕ 34 и 35, элементы 36 задержки, выходы 37 и 38, выход 39.Устройство работает следующим образом.Числа в параллельных кодах, среди которых выделяется максимальное, выставляются на информационных входах 4 , 4,.1 4 м устройства,. В каждом узле анализа, например 1.,з ф число поступает на информационные входы группы элементов И 16 и блока 17 сравнения.На второй информационный вход блока 17 сравнения поступает хоп числа из магистрали 3, общей для всех узлов анализа. В результате блок 17 сравнения вырабатывает единичный сигнал на выходе 29, если число на входе 4 больше выставленного в магистрали 3. При этом этот сигнал поступает через согласующий элемент 25, пропускающий сигнал только в одном направлении, на выход 5 в общую шину, которая реализует функцию проводного ИЛИ. Сигнал из общей шины поступает на сбросовый вход второго триггера 22 и через элемент НЕ 24 на вход элемента И 18. Поэтому, если в каком-либо узле анализа число на входе 4 больше, чем в магистрали 3, то триггер 22 во всех узлах будет сбрасываться. В то же время сигнал с выхода 28 блока 17 сравнения через элемент ИЛИ 21 поступает на вход 8 блока динамического приоритета, кото" рый пропускает на свои выходы 9, 92, 9 только один из поступивших на входы сигналов в порядке времени поступления. В результате блок динамического приоритета выдает единичный сигнал только в один из узлов анализа, который выработал сигнал на выходе 28 блока 17 сравнения ранее других, Этот сигнал запускает триггер 19, сигнал с которого через элемент ИЛИ 20 поступает на управляю- щЮ вход блока элементов И. Группа элементов И пропускает код числа на выход 104 в магистраль 3 на время,определяемое задержкой 23, сигнал с выхода которой сбрасывает триггер 19, и является задержанным сигналом запуска триггера. Задержка в элементе 23 равна времени сраба тывания блока сравнения и выработки сигнала на выходе 28, н следователь-. но, на выходе 81, Кроме того, сигнал .с выхода триггера 19 через элемент ИЛИ 21 также поступает в блок динамического приоритета, чтобы на время выработки новых сигналов в блоках 17 сравнения в схемах фиксации максимального числа не произошло .подключение к магистрали 3 более одного числа. Сигнал с выхода задержки 26 поступает на вход элемента И 18. В случае отсутствия сигнала в шине проводного ИЛИ на второй вход элемента И 18 поступает единичный сигнал. Тогда запускается триггер 22 (сигнала сброса на нем в этом случае нет), сигнал с которого, проходя через элемент ИЛИ 20 на управляющие входы группы элементов И 16, обеспечивает прохождение иаксимального числа (сигналов в шине . проводного ИЛИ нет) в магистраль 3 до появления на входах устройства большего числа. При появлении боль- щего числа на одном из входов устройства 4, 42, , 4 м сигнал в шине проводного ИЛИ сбросит триггер 22, Задержка в элементе 26 мень" ше задержки в элементе 23 на величи ну, необходимую для запуска триггера 22 и выставлении ии сигнала на вход элемента ИЛИ 20 до сброса триггера 19.Груйга элементов И 16 осуществ-"юо ляет передачу при действии единичного сигнала на управляющем входе кода числа через элементы И 271, 27, , 27, где И - число разрядов числа, При этом элементы И 27 45 должны обеспечивать согласование с магистралью при нулевом значении управляющего сигнала, т.е. иметь при этом большое выходное сопротивление, которое. изолирует выход от 50 источников единичного и нулевого сигнала.Блок 17 сравнения содержит М ячеек поразрядного сравнения 29, 29229, каждая иэ которых осуществляет функцию, обеспечивающую единичное значение на выходе 39 при условии А;1 В, где А; значение 1-го раз" ряда, поступившего на вход числа, и В; - значение 1-го разряда числа в магистрали. Кроме того, единичное значение выхода 39 будет при А;В и единичном значении на входе 40.Эту функцию реализуют элементы И-НЕ 30 - 33 и элементы НЕ 34 и 35. Задержка 36 необходима для того, чтобы при одновременном появлении единичного сигнала на входах 37 и 38 (т.е. В и А) не было единичного сигнала на вйходе 39 на время задержки в элементе НЕ 34.Блок динамического приоритета работает следующим образом.Входы блока динамического приориазведены на все возможные 1 ч(М)/2 пары входов.Каждая пара входов 81 8задается двумя номерами входов к и в, а последо" вательность пар задается последовательным увеличением правого номера на единицу и при достижении ий.максимального. значения - увеличением левого номера на единицу. При этом начальное значение правого номера на единицу больше левого номера.Сквозная нумерация всех возможных пар входов задается вьеажениеи28-%1- Х; (Н+в-К- (с)+-с где 14 ксв 4 И, а;1 - номер пары входов. Иакснмальное значение номера 1 совпадает с выражением А=Я(й)/2 при к=8-1 и в=и, т.е. с числом элементов И-НЕ 11 и И-НЕ 12. Отсюда следует, что два входа блока динамического приоритета, входящие в 1-ю пару входов, соединяются соответственно с первыми входами 1-х элементов И-НЕ 11 и И-НЕ 12;, т.е. первой и второй групп, Каждая пара 1-х злеиен" тов И-НЕ 11 1, 12 1 образует триггер, который при отсутствии сигналов на своих входах на обоих выходах выстав" ляет единичное значение сигнала, При появлении единичного сигнала на входе одного элемента И-НЕ пары на его выходе образуется нулевое значение сигнала, в то время как на выходе второго элемента пары присутствует единичный сигнал. Появление одновре" менно двух единичных сигналов на входах обоих элементов И-НЕ 11 и 12 пары приведут к случайному выставлению единичного сигнала на выходе одного.из элементов И-НЕ.20 25 30 40 Пусть сигнал запроса появился на входе 8 с(, блока динамического приоритета с=1 М . Тогда нулевое значение сигнала появится на выходах (8-1)-го элементов И-НЕ 11 (12), так как каждый вход попадает в (М) пару изМ(М)/2 различных пар входов, а навыходах остальных элементов И-НЕ 11(12) останется единичное значение.Так как выходы элементов И-НЕ 11 (12) 0 первые входы которых соединены с входом 8соединены соответственно свходами элемента ИЛИ-НЕ 15то наего выходе появится единичное значенйе сигнала, а это значит, что на выходе 9блока динамического приоритета также появится единичный сигнал.При поступлении второго по времени сигнала запроса, например на вход 81 (14 р 4 йо Фр ), он пройдет на выход в виде нулевого сигнала только в (8-2) парах элементов И-НЕ 11 (12),которые не связаны с входом 8(существует одна пара элементов И-НЕ 11 и 12, первые входы которых соединены с входами 8и 8/ блока динамического приоритета). Следовательно, соответствующий входу 8 р элемент ИЛИ-НЕ 15 р не выдаст единичный сигнал на выход 9 так как на одном его входе будет действовать единичный сигнал, а именно на том, который соединен с выходом элемента И-НЕ 1 1 (12) пары, соответствующей входам 8 и 8 д.Каждый следующий сигнал запроса образовывает нулевые сигналы на выхопах элементов И-НЕ 11 (12) в тех8- - М (М - число запросных сигналов на входах 8) парах, которые несвязаны с возбужденйыми запроснымивходами. Это обеспечивает фиксациюприоритетов запросов по времени. Пос. ле снятия очередного запроса на выход пройдет сигнал, поступивший следую ,щим по времени после снятого запроса., 1;Таким образом, и случае разнесенного 1во. времени прихода сигналов запроса на входы 8 блока динамического приоритета, они проходят на выход в по рядке их поступления.При одновременном появлении двух сигналов запроса на входах 8 приоритет определяется случайно и зависит от разброса. фронтов сигналов запросаи характеристик срабатывания логических элементов. При одновременном появлении более двух сигналов запроса возможно их блокирование в парах элементов И-НЕ 11 (12), когда ни один из сигналов запроса не сможет пройти на выходы всех (Н) элементов ИНЕ 11 (12) в виде нулевого значения сигнала, на первые входы которых он подавался. В результате не откроется ни один из элементов ИЛИ-НЕ 15 и сигналов на выходах 91 9 , 9 щ не будет. Например, при одновременном появлении сигналов запроса на трех входах 8 8 8 в трех парах элементов И-НЕ 1 1 (12), подключенных первыми входами соответственно к парам входов 8 8 ф 8 О 8 8 ф могут пройти на выходы соответственно сигналы в виде нулевого значения от входов 88 8 либо от входов 8 88 . Др.;их взаимоблокировок сигналов для трех входов нет. Исключение этих двух комбинаций нулевых сигналов на выходах элемен тов И-НЕ необходимо осуществить для каждой тройки входов блока динамического приоритета. Выделение этих комбинаций сигналов осуществляется элементами ИЛИ 13, число которых равно удвоенному числу сочетаний из Я по 3, т.е. 1 Ч(8-1)(М)/3. Каждая тройка входов ( 8 8, задается тремя номерами этих входов Ы р огде 1 ЫрМ. Последовательность троек ;входов получаетея при последователь,ном увеличении- на единицу номеров входов, начиная с правого, причем при достижении номером максимального зна" чения левый номер увеличивается на единицу а правому присваивается зна 1чение на единицу больше левого номе" ра. Тогда последовательность номеров троек входов задается выражениемйМ п=-р+.Е. м-м 1Е .Е: (й-п: -р1 К+1 "=" 1+"ыь-в ги-ю-р + М -К- - 2 й+2 г ь гФ Максимальное значение п его равной(М) (М) /6.Последовательная нумерация троеквходов должна совпадать с удвоеннойнумерацией элементов ИЛИ 13, так какдля каждой тройки входов должно бытьдва элемента ИЛИ 13 - нечетный и чет.ный, т.е, для и-й тройки входов ис"пользуются элементы ИЛИ 13 с номерами132 и 13 . При появлении однойлиз двух блокировочных комбинацийсигналов на входах элементов И-НЕ 11(12), которые связаны с входами 8 ,8, 8,на три входа элемента ИЛИ 1321 Ъ 1(йли йли 132) на его выходе образует ся нулевой сигнал. Далее он черезэлемент 14 2задержки (или 142 )поступает на.вход того элемента И-НЕ 11 (12), который соединенсвоим выхопом с первым входом этогоэлемента ИЛИ 13, а входом с входомблока динамического приоритета, имеющего меньший номер из тройки входов.В результате происходит переключение,нулевого сигнала с выхода одного элемента И-НЕ 11 (12) на выход второгоэлемснта И-НЕ 11 (12) В паре элементов И-НЕ, входы которых связаны стройкой входов блока динамическогоприоритета. Таким образом, снимаетсяблокировка для всех троек входов,и следовательно, в каждой тройке парэлементов И-НЕ 11 (12).В случае одновременного поступления сигналов запроса на более, чемтри входа, например, 8(, Ц 2 ф1 О 28, также возможна взаимоблокировкахсигналов запроса в парах элементов И-.НЕ 11 (12). Например, сигналс входа 8, блокирует сигнал с входа 8, 8 блокирует 8,8 1, 1 блокирует с входа 8 С. Однаконайдется тройка пар элементов И-НЕ 11(12), где сигнал с входа 8блокирует сигнал с входа 8 У, 8 блокиУрует 8 Ы а 8,6 блокирует сигналхс входа 8, т.е, имеет место случайс тремя входами. Тогда найдется эле мент ИЛИ 13, который снимет взаимоблокироВку Для этОЙ тройки ВХОДОВ 40путем блокирования сигнала с меньшимномером в тройке. Последнее обеспечивает направленную коррекцию изменения сигналов на выходах элементов И-НЕ 11 (12).45.Время прохождения сигнала запросачерез блок динамического приоритетасоставляет с учетом времени возможной коррекции взаимоблокировок времясрабатывания четырех элементов. Задержка обеспечивает устойчивое переключение триггера, образованного парай элементов И-НЕ 11 (12) при коррекции вэаимоблокировок, а величинаее соответствует времени срабатывания одного элемента,Таким образом, предлагаемое устройство обеспечивает на своем выхо"де 6 появление кода максимальногочисла из поступивших на его входы 4,4, 414. При одновременном появлении чисел на входах устройствапервым сигнал,на выходе 28 блока 17сравнения появится у того узла анализа, в которьй подавалось максимальное число. Этот сигнал первымпоступит в блок динамического приоритета и ъройдетна запуск тригге"ра 19 и далее на управляющие входыэлемеятов И 16 группы, что позволитсразу выдать его в магистраль 3 ина выход 6 устройства. Если иэ-заразброса параметров элементов и близости по значению кодов чисел первьмна вход блока динамического приоритета поступит сигнал из узла анализа,куда поступило,не максимальное число,то после его появления в магистра"ли 3 и на входах блоков 17 сравнениянайдется такой блок 17, где вновьвыработается сигнал (так как имеетсячисло большее, чем В маГиСтрали 3).Он поступит вшину 16 проводного ИЛИ, и следовательно, на сбросовый вход триггера 22. Однако в узле анащза сигнал с выхода 28 поступит через ИЛИ 21 на вход блока динамического приоритета и далее на его выход. Это вызовет запуск триггера 19 и подклв" чение максимального числа к магистрапи 3. Таким образом, минимальное время определения максимального чис- ла составляет время срабатываиигруппы элементов И, блока сравнения, элемента ИЛИ 21, блока дийамического приоритета, триггера 19, элемента ИЛИ 20.В сравнении с известным устройст" вом быстродействие в предлагаемом устройстве выше в М Г,/Г раз, где Г 1%2 - времена срабатывания схемфиксации максимального числа, аИ " число разрядов сравниваемых чи1089574 Составитель Е.ИвановаТехред И.АсвалошКорректор А.З ктор А.Власен Заказ 2934/45ВНИИ 035, ИЬееаюююее ент", г.ужгород, ул.Проектная, 4 ППП Тираж 699Государственного коипо делам изобретенийква, Ж,. Раушская Падпи тета СССРоткрытий аб,д. 4