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

,ЯО 1552173 с 06 г 7/О ПИСАНИЕ ИЗОБРЕТЕНИЯ ВИДЕТЕЛЬСТВУ К АВТОРСКГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(57) Изобретение относится к вычислительной технике, в частности к устройствам аппаратной поддержки вычислительно;,о процесса. Целью изобретения является расширение функциональных воэможностей устройства засчет возможности сортировки чисел взаданном диапазоне, а также эа счетвоэможности определения ближайшего1 2,большего и ближайшего меньшего к заданному. Устройство содержит первыйи второй 2 регистры, первую 3 и вторую 4 схемы срав:,ения, первый 5 и второй б элементы ИЛИ, элемент задержки 7, счетцик 8, элемент % 9, три элемента И 10-12, входной 13 и выходной 14 регистры и группу 15 узлов сравнения, а в каждом узле сравнения - регистр 16, коммутатор 18, схему сравнения 17, элемент И 19, Предлагаемое устройство осуществляет сортировку чисел по возрастанию или убыванию, если числа расположены в границах заданного диапазона. При работе устройства в режиме поиска ближайшего большего или ближайшего меньшего.к заданному, запись заданного числа производится в один из регистров границ диапазона. 1 ил., 1 табл.Изобретение относится к вычислительной технике, в. частности к устройствам аппаратурной поддержки вычислительного процесса, и являетсяусовершенствованием известного устройства по авт. св. ф 1112362,Целью изобретения является расширение Функциональных возможностейустройства за счет возможности сорти Оровки чисел в заданном диапазоне иопределения ближайшего большего илиближайшего меньшего к заданному.На чертеже представлена функциональная схема устройства, 15Устройство содержит первый 1 иторой 2 регистры, первую 3 и вторуюсхемы сравнения, первый 5 и второйэлементы ИЛИ, элемент 7 задержки,начетчик 8, элемент НЕ 9, первый 1 О,торой 11 и третий 12 элементы И,выходной 13 и выходной 1 ч регистрыи группу узлов 15 сравнения, а вкаждом узле сравнения регистр 16,схему 17 сравнения, коммутатор 18 и 25элемент И 19.Устройство имеет вход 20 начальной установки, вход 21 задания режима сортировки, первый 22 и второй 23управляющие входы, вход 2 ч нижнейЗОГраницы и вход 25 верхней границыдиапазона, вход 26 тактовых импульсов, инФормационный вход 27, контрольный выход 28, группу инФормационных выходов 29.Устройство работает в одном из35шести режимов, приведенных в таблице,где "Сортировка по убыванию" означает, что по окончании работы напервом выходе 29 устройства присутст-вует максимальное число, на щ-м выходе - минимальное из чисел, "Сортировка по возрастанию" - на первомвыходе 29 устройства присутствует минимальное из чисел, на щ-м выходемаксимальное. Устройство работает следующимобразом.В исходном состоянии в соответст- . вии с выбранным режимом работы на50входы 21-23 поданы логические уровнисигналов. С приходом по входу 20 импульса начальной установки счетчик8 обнуляется. В зависимости от сигнала на входе 21 импульс с входа 20 через элемент И 11 (при единичном сигнале на входе 21) устанавливаетв единичное состояние регистры 16Р узлов 15 сравнения или через инвертор 9 и элемент И 1 О (при нулевом сигнале на входе 21) устанавливает в нулевое состояние регистры 16.В 1-м и 6-м режимах в регистр 1 по входу 24 записывается код нижней границы, в регистр 2 по входу 25- код верхней границы диапазона, При работе в 3-м режиме заданное число записывается в регистр 2 по входу 25, при работе в 4-м режиме заданное число по входу 2 ч записывается в регистр 1. При этом подготовка устройства к работе заканчиваетсл.Рассмотрим работу устройства во 2-м режиме. В этом режиме регистры 16 обнулены, элемент И 12 открыт, так как на его первый и третий входы по 1 аны уровни логической единицы,По входу 27 на вход устройства поступает очередное число, которое сопровождаетсл тактовым импульсом по входу 26. В результате поступившее число записывается в регистр 13, выполняющий Функцию буФера. Поступившее число сравнивается с содержимым регистра 16 на схемах 17 сравнения.Схема сравнения 17 работает следующим образом, При нулевом сигнале на входе 21 устройства на выходе схе- мы 17. сравнения сигнал равен логическому нулю, если число по первому входу схемы сравнения больше либо равно числу по второму входу, и равен логической единице, если число по первому входу меньше числа по второму входу. При единичном сигнале на входе 21 устройства на выходе схемы сравнения сигнал равен логической единице, если число по первому .входу больше числа по второму входу схемы сравнения, и равен нулю, если число по первому входу меньше либо равно числу по второму входу.Во 2-м режиме в результате поступления числа в регистр 13 и сравнения его с содержимым регистров 16 узлов 15 сравнения возможны две комбинации сигналов на выходах схем сравнения:Комбинация ххх;, х;х-,1) 1 1 112) 0 0 0 0 1 где х; - сигнал на выходе из схемы17 сравнения -го узла сравнения ( = 1, ш - 1).В первом случае поступившее число по сравнению с числами, хранящимися52173 6 закрыты, коммутаторы этих узлов сравь-го узла сравнения подключен к выхо. ду регистра 13), Элементы И 19 узлов сравнения с -го по (я-Ц-й открыты, коммутаторы 18 этих узлов сравнения открыты по первому информационному входу. 0 приходом тактового импульса содержимое регистров 16 узлов сравнения с первого по (-1)-й не изменяется, информация в регистрах 16 узлов сравнения с -го по (а)-й и в регистре 14 обновляется.Таким образом, во 2-м режиме работы на вход 27 устройства. последовательно поступают сортируемые числа. Очередное поступившее число размещается в одном из регистров 1 б так, что в каждый момент времени в регистрах 16 узлов 15 сравнения хранится упорядоченная последовательность поступивших чисел, причем в регистре 16 первого узла сравнения находится наибольшее число. По окон-: 5 15 в регистрах 16, является наибольшим, следовательно, оно должно быть записано в регистр 1 б первого узла срав" нения, а содержимое регистра 16 д-го узла сравнения должно быть переписано в регистр (+1)-го узла сравнения (содержимое регистра (1 щ)-. го узла сравнения переписывается в регистр 14). На выходе схемы 17 сравнения - логическая единица, элементы И 19 открыты, коммутаторы 18 открыты по первому информационному входу.Через время задержки с, определяемое элементом 7 задержки, тактовый -импульс поступает на входы открытых элементов И 19 и на вход управления записью регистра 14, Происходит обновление информации, причем в регистр 1 б первого узла сравнения записывается максимальное число.Во втором случае поступившее число меньше либо равно числам, хранящимсяв регистрах 16 узлов сравнения с первого по (1-й)-й, и больше чисел, хранящихся в регистрах 16 узлов сравнения с -го по (в - 1)-й. Поэтому поступившее число должно быть записано в регистр 1-го узла сравнения, а соПериииое регистра Я-го узла сраеиеииа (Б = т, ы) полило быть переписано в регистр (Б+)-го узла сравнения (при Я = иперепись информации в регистр 14). Элементы И 19 узлов сравнения с первого по (1-1)-й нения открыты по второму информационному входу (т.е. вход регистра 16 чании работы устройства в счетчике 8хранится код количества поступившихчисел и, который подается на выход28 устройства. С первых и выходов5 29 устройства снимается уйорядоченная последовательность чисел.Аналогичным образом устройствоработает в 5-м режиме. Отличие состоит в том, что при подготовке уст"ройства регистры 16 установлены вединичное состояние и изменен режимработы схем 17 сравнения (на входе 21уровень логической единицы), чтообеспечивает упорядочение чисел повозрастание,Работа устройства в 1-м и 6-мрежимах заключается в следующем. Поступившее в регистр 13 очередное число сравнивается на схемах 3 и 4 сравнения с нижней и верхней границамизаданного диапазона соответственно,На выходах схем 3 и 4 сравненияуровень логической единицы, если25число по первому входу схемы сравнения больше либо равно числу по второму входу, Если поступившее числопопадает в заданный диапазон, то навыходах схем 3 и 4 сравнения - уровни логических единиц, которые черезЗО элементы ИЛИ 5 и 6 открывают элементИ 12, В этом случае тактовый импульсс входа 26 проходит через элемент 7задержки и элемент И 12 и устройствоработает так же, как во 2-м и 5-м35 режимах. В том случае, если поступившее число не входит в заданный диапазон, элемент И 12 закрыт и тактовый импульс не проходит, обновлениеинформации в регистрах 16 и 14 не4 О происходит, По окончании работы всчетчике 8 хранится код числа поступивших чисел, входящих в заданныйдиапазон.145. При работе в 3-м режиме происходитсравнение поступившего числа с содержимым регистра 2 на схеме 4 сравнения. Содержимое регистра 1 на работуустройства не влияет, так как на вход50 22 подан потенциал логической единицы, который поступает на первый входэлемента И 12. В 3-м режиме иэ поступающей последовательности чисел выделяются числа, меньшие заданного,55 и осуществляется их сортировка поубыванию. Если по окончании работысодержимое счетчика о не равно нулю,то ближайшее меньшее к заданному находится в регистре 16 первого узла1 552173 15 сравнения и подается на выходустройства по первому выходу 29.1 10 15 Характеристика работы устройства"Сортировка по убыванию"Выделение ближайшего меньшего к заданномуВыделение ближайшего большего к заданному"Сортировка по возрастаниюнВыделение и "Сортировка повозрастанию" чисел в заданном диапазоне Составитель Е.ИвановаТехред Л.Олийнык Корректор С.Черни Редактор В.Петраш Тираж 560 Ваказ 330 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Иосква, Ж, Раушская наб;, д /5Производственно-издательский комбинат Патент, г.ужгород, ул. Гагарина,101 При работе устройства в 1-м режиме посредством схемы 3 сравнения, элемента ИЛИ 5 и элемента И 12 из поступающей последовательности чисел выделяются числа больше заданного и офуществляется их сортировка по возрастанию. Если по окончании работы сфдержимое счетчика 8 не равно нулю, т ближайшее большее к заданному выд ется по первому выходу 29 устройс ва, Формула изобретения Устройство для сортировки чисел по авт. св. Р 1112367, о т л и ч а ю - щ е е с я тем, что, с целью расшии рения Функциональных возможностеи за сечет возможности сортировки чисел в заданном диапазоне и выделения ближайшего большего или ближайшего мень Шего к заданному, в него введены два регистра, две схемы сравнения, два элемента ИЛИ, элемент задержки,счетчик и третий элемент И, причемвходы нижней и верхней границ диапазона устройства соединены с установочными входами регистров, выходыразрядов которых соединены с входамипервых групп соответственно первойи второй схем сравнения, входы вторых групп которых подключены к выходам разрядов входного регистра, а выходы соединены с первыми входамисоответственно первого и второгоэлементов ИЛИ, вторые входы которыхсоединены соответственно с первым ивторым управляющими входами устройст"ва, а выходы подключены соответственно к первому и второму входам третьего элемента И, третий вход которогочерез элемент задержки соединен свходом тактовых импульсов устройства,и синхровходом входного регистра,а выход подключен к вторым входамэлементов И всех узлов сравнения исуммирующему входу счетчика, входустановки в "0" которого подключен кшине начальной установки устройства,а выходы разрядов соединены с контрольным выходом устройства,