Устройство для упорядочения чисел

СОКИ СОВЕТСНИХЮ,ИащНепмижРЕСПУБЛИН 17020,119) (11 Р 7/06 ГОСУД АРСПО ИЗОБ ВЕННЫЙ КОМИЮЕНИЯМ И ОТНРЦТ ССР СА ЛЬСТВ3 ескои кибернетиС.П чев СССР985,ССР983ель ст 7/96 ель ство Р 7/06(54) УСТРОЙСТВЧИСЕЛ ОРЯДОЧЕНИЯ и сится к автоматехнике и мо при построении ых. Цель изобЮ ВТОРСКОМУ СВИ(71) Институт технички АН БССР(57) Изобретение от тике и вычислительн жет быть использова средств обработки д ЗОБРЕТЕНИ ретения - расширение области применения за счет сортировки чисел большейразрядности. Устройство содержит иблоков 1 выделения наименьшего числа, (п-) блоков 2 исключения наименьшего числа и (и) групп элементов ИЛИ 3. Блок выделения наименьшего числа содержит матрицу (аХш) схеманализа. Схема анализа содержит дваэлемента ИЛИ и элемент ИСКЛИЧАЮ 1 ЕЕИЛИ, Устройство построено по комбинационной схеме, не требует синхронизации, отличается простотой, однородностью структуры и высоким быстродействием. Быстродействие устройствазависит от количества одновременнообрабатываемых чисел. 1 э.п, ф-лы,4 ип.11 зобретецие относится к вычисли 1тельной технике и может быть использовано для построения возрастающих(Ь, ( Ь ) или убывающих (Ь; Ь; )ва 1 гиацчонцьгх Рядов В = Ь;1 = 1,Пцз, массива чисел А = а; з. = 1,п,заданного в виде произвольных значегцш двоичного кода,1 ель изобретения - расширение облзсгц применения устройства за счетсортировки чисел большей цазрядностицрц "охрацении высокого. быстродействия.11 фиг. 1 показана схема устройства; ца фиг . 2 - схема блока вьделецьц ц 1 лецьшего числа; на фиг. 3схс".а блока исключения наиеньшегоцела; ца фиг. 4 - схема группы элемс итог 11 НУстройство содержит (фцг. 1) иб.мхов 1 вы вселения наименьшего числа, ,и) блоков 2 исключения наи. к: цьшсго числа, (п) г рупп элеменпо;,. 1.1 П 1 3, группы информационных вхочисел Л Л А, группы информационных выходов кодов упорядо еццых чисел В ( Б (Б .Блок 1 выделения наименьшего чис -ла содержит и ыш схем 4 анализа, горцзоц-.дльцье ряды которых соединеныпоследовательно по линиям переноса иразр".пения. Выходы переноса последнихрядах цогическцх схем с номерами4, , , , , 4 , образуют выходы2, 2блокирования, а ицформаццоцгп.е выходы вертикальных рядов:к г ио-.кцх хем 4 объединены и образуют 1 нг.":1 ормациоцные выходы Ь, Ь,блока. Входы разрешения пер 1 ого столбца схем анализа соединеныс входом логического нуля, а входыутройства переноса являются входамиб:сокщ;оцгици Р Р Р входныхчцсе; блока. Информационные входы горизонта;п.цых рядов логических схемобраэуггг группы Л Л Лвходовкодпе чц ел,Ссма 4 анализа состоит из двухцх.1 дового элемента ИЛИ 5, элементаИСК;Э 1 г 1 ЛИ 11 ЕЕ ИЛИ б и трехвходовогох.мента ИЛИ 7. Два входа элемента11:П 5 объединены с двумя входами эле.кгцга 1 Б 111 7 и образуют входы переноса Р ц разрешения К логической схемы.Трегцй вход элемента ИЛИ 7 соединенс первым входом элемента ИСКЛРЧАИЦЕЕ1 Г 1 6 ц информационным входом а схемы анализа, Второй вход элемента б и50 выход элемента 7 образуют информационньп выход Ь, а выходы элементовИЛИ 5 и ИСКЛЮЧАЮЩЕЕ ИЛИ б являютсявыходами переноса и разрешения соответственно .Блок 2 исключения наименьшего числа (фиг. 3) состоит из и элементовИЛИ, первые входы которых образуютвходы блока, а выходы каждого 1-гоэлемента (ь Е 1, и) соединены с(1+1)-ми входами всех элементов с номерами от (д+1) до и. Выходами блокаявляются выходы элементов ИЛИ.Устройство работает следующим образом.Двоичные коды чисел исходногомассива параллельно подаются на группы входов АА Л, так, чтоа- старший разряд а младший.Способ формирования этих кодов це ограничивается. Например, они могутбыть записаны в буферном регистре,как это сделано в прототипе.Все коды чисел параллельно поступают на все и блоков 1 выделения наименьшего числа, В первом из них происходит вьделение наименьшего числа,код которого формируется на группевыходов Б,. Одновременно ца выходах2 2 2вырабатываются уровнилогического "И" на тех выходах, номер которых соответствует номеругруппы входов А, Лс наименьшим числом. Таким образом, если вовходной комбинации имеется несколькоодинаковых и наименьших чисел, то навыходах 2 " 2также присутствует несколько уровней логического 40 нуля. В блоке 2 исключения наименьшего числа по сигналам 2 2, 2выбирается и передается на выход Р)в виде уровня логической единицы тот,который имеет наименьший номер 1, 45 т.е. из множества одинаковых наименьших чисел выбирается одно с наименьшим номером. Сигналы Р Р Рпоступают на входы Р Р, Рвторого блока 1 и уровень логической единицы на линии Р . исключаетсянаименьшее число, вьделенное в блоке1из дальнейшего рассмотрения. Та 1ким образом, блок 1,вьделяет наименьшее из оставшихся чисел и т,д.55На выходах В сформировано наибольшеечисло .Для формирования ускоренного переноса исключающих сигналов предназначены группы элементов ИЛИ 3, При этом151 702 О 5 10 сигналР1 одновременно действуетна соответствующие входы Р всех последующих блоков вьщеления наименьшего числа, практически одновременноисключая число Аиз анализа.а выходах В В В сформирована упорядоченная последовательность кодов чисел из входного массива А 1Ау у АБлок 1 выделения наименьшего числа построен по комбинационной схемеи работает следующим образом,На горизонтальные ряды схем 4 аналиха подаются двоичные коды исходныхчисел так, что а соответствует .11старшему разряду, а, - младшему. Изкомбинации входных кодов анализируются только те, для которых на входахР; и Р присутствуют уровни логического нуля.В блоке 1 использован алгоритм поразрядного сравнения чисел. Такоесравнение выполняется вертикальнымирядами схем анализа. Если хотя бы водном числе в старшем разряде присутствует "И", то этот "6" передается на выход элемента ИЛИ 7 (при наличии уровней "9" ца двух других еговходах) ц соответственно на информационный выход логической схемы 4. Таккак информационные выходы вертикальных рядов схем анализа объединены,то этот уровень логического нуляблокирует все уровни логической единицы на выходах элемента ИЛИ 7 других схем анализа, ца которых поданызаведомо большие числа.При наличии такого блокированияна выходе элемента ИСКЛИЧАИ 11,ЕЕ ИЛИ6 вырабатывается уровень логическойединицы, который поступает на выходразрешения данной схемы 4 анализа и,транспортируясь через все остальныесхемы анализа в горизонтальном ряду,исключает данное заведомо большеечисло из рассмотрения, а на выходеЬ, формируется уровень "ф".Предположим, что во втором разряде из оставшихся чисел все имеютуровни "1", тогда и на выходе Ь будет уровень "1". Если в третьем разряде хотя бы в одном из оставшихсячисел будет присутствовать уровень"9", то ца Ь будет 9, а из дальнейшего рассмотрения будут исключены течисла, в которых а, = .В последнем ш-м вертикальномстолбце анализируется последний млад 5 20 25 30 35 40 45 50 55 ший разряд. Те числа иэ оставшихся,в которых а, = 6, и есть наименьшие.1 йПри этом на выходах блокирования 2,соответствующим наименьшим числом выработаюгся уровни логического нуля,на остальных - логической единицы.Предложенное решение блока 1 выделения наименьшего числа отличаетсявысоким быстродействием, которое оценивается как (ш+1)т и не зависит отколичества чисел п,Формула изобретения1. Устройство для упорядочения и чисел, содержащее и блоков вьщеления наиецьшего числа и группу элементов ИПИ, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет сортировки чисел большей разрядности, в него введены (и) блоков исключения наименьшего числа и (и) групп элементов ИЛИ, причем информационные входы устройства подключены соответственно. к поразрядно объединенным информационным входам всех блоков вьщелеция наименьшего числа, выходы блокирования 1-го блока вьщеления наименьшего числа (1 = 1 и) соединены с соответствующими входами 1-го блока исключения наименьшего числа, выходы 1-го блока исключения наименьшего числа (1 = 2 и) соединены с соответствующими входами первой группы входов элементов ИЛИ К-й группы (К1 п), выходы которых соединены с соответствующими входами разрешения (К+2) -го блока выделения наименьшего числа, выходы элементов ИЛИ 1-й группы (1 = 1 и) соединены с соответствующими входами второй группы входов элементов ИЛИ (1+1)-й группы, выходы первого блока исключения наименьшего числа соединены с соответствующими входами второй группы входов элементов ИЛИ первой группы, группы входов блокирования первого и группы входов разрешения первого и второго блоков вьщелеция наименыпего числа соединены с входом логического нуля устройства, информационные выходы р-го блока вьщелеция цацмсць - шего числа являются р-ми информационными выходами устройства (ри).2. Устройство по и. 1, о т л ив ч а ю щ е е с я тем, что блок яьщеления наименьшего числа сод ржц 1 ат1517020рицу (пкш) схем анализа (и - числострок, ш - число столбцов), схемаанализа содержит первый и второй элементы ИЛИ, элемент ИСКЛИЧАЮПЕЕ ИЛИ,причем первый и второй входы первого .элемента ИЛИ соответственно соедиие"ны с первым и вторым входами второгоэлемента ИЛИ, третий вход которогосоединен с первым входом элементаИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которогосоединен с вькодом второго элементаИЛИ, причем первый и второй входыпервого элемента ИЛИ Ц-й схемы анализа (д 1п, 1 2ш) соответственно соединены с выходами первого элемента ИЛИ и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1(1-1) -й схемы анализа, в 1-м столбце (1 1, ш) выходы вто. - рых элементов ИЛИ всех схем анализа объединены по схеме монтажного И и являются выходом блокирования блока выделения наименьшего числа, 11.-й информационный выход блока выделения наименьшего числа соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 д-й схемы анализа, первый и второй входы первого элемента ИЛИ (11.)-й схемы анализа соединены соответственно с , д-м входом блокирования н д-м входом разрешения блока выделения .наименьшего числа, выходы первого элемента ИЛИ дш-й схемы анализа являются -м информационным выходом блокирования блока выделения наименьшего числа,151 7020 Составитель В.Журавлевактор О.Ирковецкая Техред Л,Олийнык орректор В,Кабаций оизводственно-издательский комбинат "Патент", г. Ужгор Гагарина, 101 каз 6391/51НИИПИ Госуда Тираж 668 Подлисноевенного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5