Устройство для сортировки чисел

1532913 20 сортируемых чисел в массиве, ш - количество информационных входов устройства, иузлов сравнения 1010. Каждый узел сравнения содержит регистр, ш схем сравнения, элемент И, ш элементов ИЛИ, ш элементовИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик-дешифратори 2 ш-входовый коммутатор. Блок сортировки предназначен для сортировкиза один такт щ чисел, что является Изобретение относится к вычислительной технике и может .быть использовано в специализированных устройствах обработки информации.Цель изобретения - повышениебыстродействияНа фиг, 1 представлена схема устройства; на фиг. 2 - схема узласравнения.Устройство для сортировки чиселсодержит вход 1 начальной установки, информационные входы 2, вход 3тактовых импульсов, блок 4 сортировки, ш входных регистров 5, 1 триггеров 6, элемент И 7, выходной регистр 8, информационные выходы 9 и(и) узлов 10 сравнения,Каждый узел 10; сравнения состоит из элемента И 11, регистра 12,ш схем 13 сравнения, ш элементовИЛИ 14, ш элементов ИСКЛЮЧАЮЩЕЕИЛИ 15, счетчика-дешифратора 16,2 ш-входового коммутатора 17,Устройство работает следующим образом.Перед началом сортировки импульсом положительной полярности навходе 1,начальной установки триггербустанавливается в "0". В первом .такте работы числа первого сортируемого массива с входов 2 поступают на входы блока 4 сортировки.На выходе блока 4 сортировки получают ш просортированных чисел впорядке убывания (наибольшее числонаходится на первом, следующее навтором и т,д., наименьшее на ш-мвыходе),По переднему фронту первого тактового импульса в регистры 5 и5 5 записывается информацияс выходов блока 4 сортировки, а втриггер б, - нуль. За время такто 25 30 35 40 45 50 55 1-й частью массива из п-чисел, последуюшая обработка чисел требуетсядля получения полностью просортированного массива из и чисел. Увеличение быстродействия достигается засчет распараллеливания процесса сортировки чисел, по сравнению с прототипом быстродействие повьппено в шраз; 2 ил,ваго импульса сигнал "1" с инверсного выхода триггера б, проходя черезэлемент И 7, успевает установитьтриггеры 6, б,, бк в "1". Во втором такте "1" с выходов триггеров б 6 бк, поступает на первые входы элементов ИЛИ 14, 1414 во всех узлах 1010., 10, сравнения, В каждом 1.-м узле .10; сравнения "1" с выходов элементов ИЛИ 14, 14 14 поступает на входы счетчика-дешифратора 16, на котором подсчитывается количество единиц и формируется сигнал "1" на выходе. Информация с выхода перво" го элемента ИЛИ 14 разрешает("1") или запрешает("0"1 прохождение тактовых импульсов через элемент И 11 на синхровход регистра.12. Состояние выходов счетчика-дешифратора 16 узла 10; сравнения определяет номер узла 10 сравнения, в который число с выходов регистра 12 переписывается, При нулях на выходах счетчика-дешифратора 16 информация в регистре 12 не изменяется, Если на первом выходе счетчика-дешифратора 16 узла 10; сравнения имеется сигнал "1", информация с выхода регистра 12 переписывается в (д+1)-й узел сравнения, на втором выходе - в (1+2)-й узел сравнения и т.д. На первые и вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15, 15 а,.15 узлов 10, 1010, , сравнения поступает "1", которая устанавливает на выходах "0". На первые и вторые входы элементов ИСКЛЮЧАК 6 ЕЕ ИЛИ 15, 15 15 щ первого узла 10 срав-. нения поступают соответственно "0" и "1", которые устанавливают на выходах сигнал,"1"."1" с выходов элемента ИСКЛЮЧАКЩЕЕИЛИ 15 п, 15 15 п первого узлаО сравнения устанавливаются в по"ложения, когда на их вход поступаетинформация соответственно с второго,третьего, , ш-го входов. Коммута-.торы 17 узлов 10, 10 10- 10сравнения сигналом "1" с ш-х выходов счетчиков-дешифраторов 16соответственно узлов 10, 10 э10. сравнения устанавливаются вположение, когда на их выходы поступает информация с 2 ш-го входа. Свходов 2 на входы блока 4 сортировки поступают вторые ш чисел первогосортируемого массива.По переднему Фронту второго так Отового импульса происходит записьвторых ш просортированных чисел извыходов блока 4 сортировки в регистры 5, 5 5 , запись информациис выходов регистров 5, 55 е 25в регистры 12 соответственно узлов10, 10 а 10 сравнения, перезапись информации с выходов регистра .12 узла 10; сравнения в регистр 12узла 10; сравнения, запись нуля с 3 Оинверсного выхода триггера 6втриггер 61.В третьем такте "0" с выходовтриггера б, поступает на первые вхо-,ды элемента ИЛИ 14, 14,.14 е узлов 10., 10 п. , 101,сравнения и35разрешает прохождение информациичерез данные элементы с выходов схем13, 13 13 сравнения. Информация с выходов входного регистра 5поступает на первые входы схем 13сравнения всех узлов 10 сравнения,где она сравнивается с содержимымрегистров 12При превышении содер.жимого регистра 5 над содержимымрегистра 12 на выходе схемы 13сравнения получают сигнал "1", а вдругих случаях - сигнал "0", В узлах 10, 10 п101 сравнения результаты сравнения с выхода схемы13 сравнения проходят через элемент ИЛИ 14 и поступают на 1-йвход счетчика-дешифратора 16, который подсчитывает количество чиселв регистрах 5 5 п 5 больших,чем число с выхода регистра 12, иФормирует на выходе, соответствующем данному числу, сигнал "1". В уэ;ле 10; сравнения на.входы элемента 3 6ИСКЛЮЧАЮЩЕЕ ИЛИ 15 . поступает икфор 3мация с выходов элементов ИЛИ 14узлов 1 О; 10; сравнения, котораяустанавливает на выходе сигнал "0"(информация на первом и втором входах одинакова) или "1" (информацияна первом и втором входах разная)Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 15 узла 10; сравненияпоступает на -й управляющий входкоммутатора 17 узла 101;д сравнения и разрешает("1")или запрещает(,"0") прохождение на выход коммутатора17 информации с выхода регистра 51 .По переднему фронту третьего тактового импульса происходит запись следующих ш просортируемых чисел из вы"ходов блока 4 сортировки в регистры5, 5 5,п, запись нуля свыхода триггера 61 в триггер б, записьинформации с выходов коммутаторов 17предыдущих узлов 10, сравнения в регистры 12 последующих узлов 10;+,сравнения,По приходу следующих тактовых импульсов устройство работает аналогично.По переднему Фронту (1+1)-го тактового импульса происходит записьпервых ш чисел второго сортируемогомассива в регистры 5, 55 д запись информации с выходов коммутаторов 17 предыдущих узлов 10; сравненияв регистры 12 последующих узлов10 ,ч сравнения, запись куля втриггер 6 .За время (1+1)-го тактового импульса сигнал "1" с инверсного выхода триггера бп, проходя через элемент И 7, успевает установить триггеры 64, бп,6в единицуПосле (1+1)-го тактового импульсачисла первого массива сортируются впорядке убывания (наибольшее числонаходится в регистре 12 первого узла10 сравнения, следующее число повеличине в регистре 12 второго узла10 сравнения и т.д., наименьшее врегистре 8).По приходу следующих тактовых импульсов одновременно с сортировкойвторого массива производится последовательный по ш чисел вывод первогоотсортированного массива и т,д,формула изобретения Устройство для сортировки чисел,содержащее входной и выходной регистры, К-триггеров, где 1 щ - ," и - кош личество сортируемых чисел в массиве; ш - количество информационных входов устройства, (и) узлов сравнения, элемент И, выход которого соединен с входом установки в "1" Х-го триггера. (1 = 1,2, 1 с), прямой вы - г. од р-го триггера (р = 1,2К"1) соединен с информационным входом р+1)-го триггера, вход начальной установки устройства соединен с входном установки в "О" (М)-го тригге 1 а, инверсный выход К-го триггера оединен с информационным входом ервого триггера и с первым входом элемента И, каждый узел сравнения содержит регистр, схему сравнения, элемент И и элемент ИЛИ, причем так 1 овый вход устройства соединен сходами синхронизации первого входного и выходного регистров, с тактоВыми входами всех триггеров, с первыми входами элементов И каждого уз". 25 Ла сравнения, в котором выход элеМента И соединен с входом синхронизации регистра, выход которого сое 1 инен с первым входом схемы сравнеия, второй вход которой соединен с 3 О ыходом входного регистра и информаионным входом регистра первого уза сравнения, второй вход элементасоединен с выходом элемента ИЛИ, ервый вход которого соединен с выодом схемы сравнения, о т л и ч а -щ е е с я тем, что, с целью повыения быстродействия, в него введены ш) входных регистров, блок сортиовки, а в кащцый узел сравнения вве ены (ш) схем сравнения, (ш) .лементов ИЛИ, ш элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, счетчик-дешифратор и 2 шВходовый коммутатор, причем информационные входы устройства соединены С входами блока сортировки, выходы которого соединены с входами соответствующих входньж регистров, и Выходы второго, третьего, ш-го выходного регистров соответственно сое" динены с первыми входами второй, третьей, ш-й схем сравнения, в каждомузле сравнения с первого по (и)-йпрямой выход 1-го триггера (11,21) соединен с первыми входами элементов ИЛИ в 1-1)ш+1)-м,1-1)ш+2), 1-1)ш+ш) узлах сравнения, выход коммутатора (и)-го узла сравнения соединен с информационным входом выходного регистра, выход которого соединен с ш-м выходомустройства, в каждом -м узле сравнения (1,2п) выход регистра соединен с вторым входом 2,3ш-Й схем сравнения, выходы которых соединены с вторыми входами соответствующих элементов ИЛИ, выход1-го: элемента ИЛИ ( = 1,2 ш)соединен с первыми входами -го элемента ИСКЛЮЧА 16 ЦЕЕ ИЛИ, -м входомсчетчика-дещифратора и первым входом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ(х + 1)-го узла сравнения, -й информационный вход коммутатора соединен с выходом -го входного регистра, -Й управляющий вход коммутатора соединен с выходом -.го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (х + 2 -)-гоузла сравнения, (ш+)-й информационный вход коммутатора соединен свьжодом регистра ( + 1-)-го узласравнения, (ш+)-Й управляющий входкоммутатора соединен с -м выходомсчетчика-дещифратора (+1-)-го узла сравнения, выход коммутатотах-го узла сравнения соединен с входом регистра (+1.)-го узла сравнения, в (-1)-м узле сравнения управляющие и информационные входы ком"мутатора с (ш+)-го по 2 ш-й соединены с вторыми входами элементовИСКЛЮЧАЮЩЕЕ ИЛИ первого узла сравнения и с входом логического нуляустройства, выходы регистров (и-ш++1), (п-ш 2)(а)-го узлов сравнения соединены соответственно спервым, вторым(ш)-м выходамиустройства.1532913 рректор-Т. Палий ктор Л. Пчолинская Тех 00/53 Тираж 668 Подписноосударственного комитета по изобретениям и открыти 113035, Москва, Ж, Раушская наб., д. 4/ ри ГКНТ СС Производственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 10 Заказ ВНИИПИ Составитель В. Ивано редЛ.Олийнык