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

(19) (11) 2 А 7/08 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 933И,Г.Цмоц этого элеменодключень стройств управле ного одя хода ьк регистров, информационные входы устройства соединены с установочными входами входного регистра, выходы разрядов которого соединены с установочными входами регистра первого узла сравнения, информационными входами второй группы схем сравнения и коммутаторов всех узлов сравнения, выходы коммутатора (ш)"го узла сравнения соединены с установочными входами выходного регистра, вход задания режима сортировки устройства подключен к первому входу первого элемента И и через элемент НЕ - к первому входу второго элемента И, вторые входы первого . и второго элементов И подключены к шине начальной установки устройства,австроа,ной ре(21) 3599666/ 18-24(56) 1. Авторское свидетельство СССР 9928342, кл. С 1 06 Г 7/06, 1982.2. Авторское свидетельство СССР Иф 1007099, кл, С 06 Г 7/08, 1981 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее (щ) узлов сравнения, где а - количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с информационными входами первой группы схемы сравнения и коммутатора, управляющий вход которого подключен к выходу схемы сравнения, выходы коммутатора -го узла сравнения, где 1=1,2, (щ), соединены с установочными входами регистра (1+1)-го узла ср нения, вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, о т л и ч а ю щ е е с я тем, что, с целью повышения бы действия и упрощения устройств в него введены входной и выход гистры, два элемента И и элемент а в каждый узел сравнения - эле И, первый вход которого соедин ходом схемы сравнения этого узравнения, а вькод - с входом правления записью рег зла сравнения, вторые ов И всех узлов сравн входу тактовых импул одключенному также к ия записью входного и а выходы - к входам установки соответственно в единичное и нулевое сосстояния регистров всех узловсравнения.Изобретение относится к вычислительной технике и может быть исполь-зовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данных, поступающих параллельным кодом одно за другим в реальном масштабе времени.В задачах, связанных с обработкой данных сейсморазведки, гидроакус тики при распознавании образов необходимо производить сортировку данных. Причем, часто обработку необг ходимо производить в реальном масштабе времени, т.е, с той же частотой, 15 с которой поступают данные.ИзвеСтно устройство для сортиров.ки чисел, содержащее П регистров, и схем сравнения, регистр результата, распределитель импульсов, 11 элемен тов запрета, 01+1) элементов И 1.Для сортировки ц чисел в описанном устройстве необходимо произвести запись в регистры, а затем выполнить Д циклов, .в каждом иэ которых выпол няется Ф тактов (Ф -разрядность дан-. ньм) .Недостаток устройства - низкое быстродействие.130Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, содержащее 1 П ячеек, где В -количество чисел в выходном множестве, причем каждая ячейка содержит элемент 35 сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр 40 результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационнов входов коммутатора,установоч ные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочными входами регистра результата и с второй 50 группой информационньм входов коммутатора, а выходы коммутатора являются выходами ячейки, входы установки приемного регистра и регистра ре-.зультата в исходное состояние соеди иены а входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом. устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки а группа информационных входов первой ячейки является группой информационных входов устройства. Для сортировки чисел в устройстве необходимо выполнить 2 щ тактов. Лля построения устройства необходимо 2 Ф регистров, 111 схем сравнения и й 1 коммутаторов 2,Недостаток устройства - низкое быстродействие и большие затраты 1.оборудования.Цель изобретения - повышение быстродействия и упрощение устройства.Укаэанная цель достигается тем, что в устройство для сортировки чисел, содержащее (В) узлов сравнения, где Ю - количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения, коммутатор и регистр, вьмоды разрядов которого соединены с информационными входами первой группы схемы сравнения и коммутатора, управляющий вход которого подключен к выходу схемы сравнения, выходы коммутатора-го узла сравнения, где =1,2 (а), соединены с установочными входами регистра (1+ 1)"го узла сравнения, вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, введены входной и выходной регистры, два элемента И и элемент НЕ, а в каждый узел сравнения - элемент И, первый вход которого соединен с выходом схемы сравнения этого узла сравнения, а выход - с входом управления записью регистра этого узла сравнения, вторые входы элементов И всех узлов сравнения подключены к входу тактовых импульсов устройства, подключенному также к входам управления записью входного и выходного регистров, информационные входы устройства соединены с установочными входами входного регистра, вьмоды раз3 111236рядов которого соединены с установочными входами регистра первого узла1 сравнения, информационными входами, второй группы схем сравнения и коммутаторов всех узлов сравнения, выходы коммутатора (П 1-1)-го узласравнения соединены с установочнымивходами выходного регистра, вход задания режима сортировки устройстваподключен к первому входу первого 10элемента И и через элемент НЕ к первому входу второго элемента И, вторые входы первого и второго элементов И подключены к шине начальнойустановки устройства, а выходы - квходам установки соответственнов единичное и нулевое состояние регистров всех узлов сравнения.На чертеже представлена схемаустройства. 20Устройство содержит информационные входы 1, вход 2 тактовых импульсоз, вход 3 задания режима сортировки, шину 4 начальной установки,элемент НЕ 5, элементы И 6, и 7, 25входной регистр 8, выходной регистр9, (Ю) узлов 10 сравнения (пколичество: сортируемых чисел), причем каждый узел 10 сравнения содер- .жит элемент И 11, регистр 121 схему13 сравнения, коммутатор 14,Устройство работает следующимобразом.Перед началом сортировки уровнемсигнала на входе задания режима35сортировки 3 выставляется режим сортировки по возрастанию (логическая"1") или по убыванию (логический "0"),Импульсом положительной полярностина входе 4 начальной установки регистры 12 устройства устанавливаютсяв нуль (режим сортировки по убыванию) или все разряды регистров 12 вединицы (режим сортировки по возрастанию). Сортируемая последовательность 4чисел с информационных входов 1 посту.пает на входы регистра 8. В каждомтакте работы в регистр 8 записываетсяодно из чисел этой последовательности.Информация с выхода регистра 8 посту 50пает на первые входы всех схем 13сравнения, на вторые входы которыхпоступает информация с соответствующих регистров 12,В режиме сортировки чисел по убыванию при превышении содержимогорегистра 8 над содержимым регистра12 на выходе схемы 13 сравнения 2 4формируется сигнал логической "1",в других случаях сигнал логического"0". При работе устройства в режимесортировки чисел по возрастанию сигнал логической "1",на выходе схемы13 сравнения формируется, когда содержимое регистра 12 превышает содержимое регистра 8, в остальныхслучаях формируется сигнал логическо"го "0". Информация на выходе схемы13 сравнения управляет коммутатором14. Сигнал логической "1" на управляющем входе коммутатора 14 устанавливает его в положение, когда на еговыход поступает информация с выходоврегистра 12. Сигнал логического "0"на управляющем входе коммутатора 14устанавливает его в положение, когда .на его выход поступает информацияс выходов регистра 8,Информация на выходе схемы 13 сравнения каждого узла 1 О сравнения,разрешает (логическая "1") или запрещает (логический "0") прохождениетактовых импульсов через элемент И11 на вход управления записью регист-,ра 12.Рассмотрим работу устройства в режиме сортировки чисел по убыванию.По первому тактовому импульсу врегистр 8 записывается первое число,которое с его выхода поступает напервые входы всех схем 13 сравнения,на вторые входы которых поступаетнуль. Если первое число не равно нулю, то на выходе всех схем 13 сравнения формируется сигнал логической "1".По второму тактовому импульсув регистр 8 записывается второе число из сортируемого массива, в регистр12 первого узла 10 сравнения пере"писывается первое число из регистра8, а в регистры 12 остальных узлов10 сравнения и регистр 9 записываетсяинформация с выходов коммутаторов 13,т.е. нули. Второе число сравниваетсяс содержимым регистра 12 каждого узла 10 сравнения и если второе числобольше первого то на выходе всехсхем 13 сравнения формируется сигналлогической "1". Если же второе числоменьше первого, то на выходе схемы13 сравнения первого узла 10 сравне"ния формируется сигнал логического"0", а на выходе схем 10 сравненияформируется сигнал логической "1".По третьему тактовому импульсупроисходит: запись третьего числаказ 6460/34дписное иал ППП "Патент",Ужгород, ул, Проек из сортируемого массива в регистр 8, запись второго числа (для случая когда второе число больше первого) .в регистр 12 первого узла 10 сравнения, зались информации с выходов коммутаторов 14 предыдущих узлов 1 О сравнения в регистры 12 последующих узлов 10 сравнения; запись информации с выхода коммутатора 14 последнего узла 10 сравнения в регистр 9.Дальнейщая работа устройства в данном режиме будет проходить аналогично. После поступления (п+ 1) импульсов числа массива будут просортированы в порядке убывания 12362 6(наибольшее число будет в регистре12 первого узла 10 сравнения, следующее число по величине в регистре 12 второго узла 1 О сравнения5 и т.д наименьшее в регистре 9) .Работа устройства в режиме сортировки по возрастанию аналогична работе устройства в режиме сортировкичисел по убыванию.1 О Время сортировки составляет Т=(пн 1 Ктактов, Технико-экономический эффектзаключается в повышении быстродействия устройства по сравнению с прототипом в два раза. Выигрыш по оборудо ванию в сравнении с прототипом составляет (Ю) регистров.гд