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

 

Изобретение относится к вычислительной технике, в частности к устройствам аппаратной поддержки вычислительного процесса. Целью изобретения является расширение функциональных возможностей устройства за счет возможности сортировки чисел в заданном диапазоне, а также за счет возможности определения ближайшего большего и ближайшего меньшего к заданному. Устройство содержит первый 1 и второй 2 регистры, первую 3 и вторую 4 схемы сравнения, первый 5 и второй 6 элементы ИЛИ, элемент задержки 7, счетчик 8, элемент НЕ 9, три элемента И 10 - 12, входной 13 и выходной 14 регистры и группу 15 узлов сравнения, а в каждом узле сравнения регистр 16, коммутатор 18, схему сравнения 17, элемент И 19. Предлагаемое устройство осуществляет сортировку чисел по возрастанию или убыванию, если числа расположены в границах заданного диапазона. При работе устройства в режиме поиска ближайшего большего или ближайшего меньшего к заданному запись заданного числа производится в один из регистров границ диапазона. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (s))s Г 06 Г 7/08

3

1, ;\, 1 го гi Z

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

flQ ИЗОБРЕТЕНИЯМ И РТНРЫТИЯМ

ПРИ ГКНТ СССР (61) 1112362 (21) 44743 50/24-24 (22) 1б.08.88 (46) 23,03.90."Бюл. P 11 (72) В.И.Бенкевич, В.В.иазаник и М.И,Зарецкий (53) 681.325.бб(088.8) (56) Авторское свидетельство СССР

У 1112362, кл. G Об F 7/08, 1983. (54) УСТРОЙСТВО ЦЛЯ СОРТИРОВ((И ЧИСЕЛ (57) Изобретение относится к вычислительной технике, в частности к устройствам аппаратной поддержки вычислительно;,о процесса. Целью изобретения является расширение функциональных воэможностей устройства за счет возможности сортировки чисел в зада, ном диапазоне, а также эа счет воэможности определения ближайшего

„„ЯО„„1552173

2 большего и ближайшего меньшего к заданному. Устройство содержит первый

1 и второй 2 регистры, первую 3 и вторую 4 схемы срав:,ения, первый 5 и второй б элементы ИЛИ, элемент задержки 7, счетчик 8, элемент ИЕ 9, три элемента И 10-12, входной 13 и выходной 14 регистры и группу 15 узлов сравнения, а в каждом узле сравнения - регистр lб, коммутатор 18, схему сравнения 17, элемент И 19, Предлагаемое устройство осушествляет сортировку чисел по возрастанию или убыванию, если числа расположены в границах заданного диапазона. При работе устройства в режиме поиска ближайшего большего или ближайшего меньшего.к заданному, запись заданного числа производится в один из регистров границ диапазона. 1 ил., С

1 табл. !

15521 73

Изобретение относится к вычислительной технике, в. частности к устройствам аппаратурной поддержки вычислительного процесса, и является усовершенствованием известного устройства по авт. св. " 1112362.

Целью изобретения является расширение функциональных возможностей устройства за счет возможности сорти- 10 ровки чисел в заданном диапазоне и определения ближайшего большего или ближайшего меньшего к заданному.

На чертеже представлена функциональная схема устройства. 15

Устройство содержит первый 1 и которой 2 регистры, первую 3 и вторую е схемы сравнения, первый 5 и второй элементы ИЛИ, элемент 7 задержки,. четчик 8, элемент НЕ 9, первый 10, торой 11 и третий 12 элементы И, выходной 13 и выходной 14 регистры и группу узлов 15 сравнения, а в каждом узле сравнения регистр 16, схему 17 cpaBI1eH1я коммутатор 18 и 25 элемент И 19.

Устройство имеет вход 20 начальной установки, вход 21 зацания режима сортировки, первый 2 и второй 23 управляющие входы, вход 24 нижней g0 границы и вход 25 верхней границы циапазона, вход 26 тактовых импульсов, информационный вход 27, контрольный выход 28, группу информационных выходов 29, Устройство работает в одном из

35 шести режимов, приведенных в таблице, где "Сортировка по убыванию" означает, что по окончании работы на первом выходе 29 устройства присутст- „ вует максимальное число, на тп-м выхоце — минимальное из чисел, "Сортировка по возрастанию" — на первом выхоце 29 устройства присутствует минимальное из чисел, на m-м выходе максимальное.

Устройство работает следующим образом.

В исхоцном состоянии в соответст- вии с выбранным режимом работы на

50 входы 21-23 поданы логические уровни сигналов ° С приходом по вхоцу 20 импульса начальной установки счетчик

8 обнуляется. В зависимости от сигнала на входе 21 импульс с входа 20 через элемент И 11 (при единичном сигнале на exoqe 21) устанавливает в единичное состояние регистры 16 узлов 15 сравнения или через инвертор 9 и элемент И 10 (при нулевом сигнале на входе 21) устанавливает в нулевое состояние регистры 16.

В 1-м и 6-м режимах в регистр 1 по sxoqy 24 записывается код нижней границы, в регистр 2 по входу 25код верхней границы диапазона. При работе в 3-м режиме заданное число записывается в регистр 2 по входу

25, при работе в 4-м режиме зацанное число по входу 24 записывается в регистр 1. При этом подготовка устройства к работе заканчивается.

Рассмотрим работу устройства во

2-м режиме. В этом режиме регистры

16 обнулены, элемент И 12 открыт, так как на его первый и третий входы поданы уровни логической единицы.

По входу 27 на вход устройства поступает очередное число, которое сопровождается тактовым импульсом по

axoqy 26. В результате поступившее число записывается в регистр 13, выполняющий функцию буфера. Поступившее число сравнивается с содержимым регистра 16 на схемах 17 сравнения.

Схема сравнения 17 работает следующим образом. При нулевом сигнале на входе 21 устройства на выходе схе- мы 17. сравнения сигнал равен логическому нулю, если число по первому вхоцу схемы сравнения больше либо равно числу по второму входу, и равен логической единице, если число по первому входу меньше числа по второму axoqy. При единичном сигнале на входе 21 устройства на выходе схемы сравнения сигнал равен логической единице, если число по первому .входу больше числа по второму входу схемы сравнения, и равен нулю, если число по первому входу меньше либо равно числу по второму входу.

Во 2-м режиме в результате поступления числа в регистр 13 и сравнения его с содержимым регистров 16 узлов 15 сравнения возможны две комбинации сигналов на выходах схем t7 сравнения:

Комбинация x x . ° .х;, x x

1) 1 1 1 1 1

2) 0 0 0 0 1 где x; — сигнал на выходе из схемы

17 сравнения i-го узла сравнения (i = 1, m — 1).

В первом случае поступившее число по сравнению с числами, хранящимися

52173 6 закрыты, коммутаторы этих узлов сравь-ro узла сравнения подключен к выходу регистра 13) . Элементы И 19 узлов сравнения с i--го по (m-1)-й открыты, коммутаторы 18 этих узлов сравнения открыты по первому информационному входу. С приходом тактового импульса содержимое регистров 16 узлов сравнения с первого по (i-1)-й не изменяется, информация в регистрах 16 узлов сравнения с i-го по (m-1)-й и в регистре 14 обновляется.

Таким образом, во 2-м режиме работы на вход 27 устройства, последовательно поступают сортируемые числа. Очередное поступившее число размещается в одном из регистров 16 так, что в каждый момент времени в регистрах 16 узлов 15 сравнения -хранится упорядоченная последовательность поступивших чисел, причем в регистре 16 первого узла сравнения находится наибольшее число. По окон-:

5 15 в регистрах 16, является наибольшим, следовательно, оно должно быть записано в регистр 16 первого узла сравнения, а содержимое регистра 16 i-ro узла сравнения должно быть переписано в регистр (i+1)-го узла сравнения (содержимое регистра (i щ-1)-. го узла сравнения переписывается в регистр 14). На выходе схемы 17 сравнения - логическая единица, элементы

И 19 открыты, коммутаторы 18 открыты по первому информационному входу.

Через время задержки, определяемое элементом 7 задержки, тактовый

-импульс поступает на входы открытых элементов И 19 и на вход управления записью регистра 14. Происходит oGновление информации, причем в регистр

16 первого узла сравнения записывается максимальное число.

Во втором случае поступившее число меньше либо равно числам, хранящимся в регистрах 16 узлов сравнения с первого по (i-й)-й, и больше чисел, хранящихся в регистрах 16 узлов сравнения с i-го по (m — 1)-й. Поэтому поступившее число должно быть записано в регистр i-ro узла сравнения, а соПераимое регистра S-го узла сраеиеииа (S = i, m-1) полило быть переписано в регистр (S+t)-го узла сравнения (при S = m-1 перепись информации в регистр 14). Элементы И 19 узлов сравнения с первого по (i-1)-й нения открыты по второму информацион ному входу (т.е. вход регистра 16 чании работы устройства в счетчике 8 хранится код количества поступивших чисел и который подается на выход

28 устройства. С первых и выходов

5 29 устройства снимается уйорядоченная последовательность чисел.

Аналогичным образом устройство работает в 5-м режиме. Отличие состоит в том, что при подготовке уст" ройства регистры 16 установлены в единичное состояние и изменен режим работы схем 17 сравнения (на входе 21 уровень логической единицы), что обеспечивает упорядочение чисел по возрастанию.

Работа устройства в 1-м и 6-м режимах заключается в следующем. Поступившее в регистр 13 очередное чис.ло сравнивается на схемах 3 и 4 сравнения с нижней и верхней границами заданного диапазона соответственно, На выходах схем 3 и 4 сравнения уровень логической единицы, если

25 число по первому входу схемы сравнения больше либо равно числу по второму входу. Если поступившее число попадает в заданный диапазон, то на выходах схем 3 и 4 сравнения - уровни логических единиц, которые через

ЗО элементы ИЛИ 5 и 6 открывают элемент

И 12. 8 этом случае тактовый импульс с входа 26 проходит через элемент 7 задержки и элемент И 12 и устройство работает так же, как во 2-м и 5-м

35 режимах. В том случае, если поступившее число не входит в заданный диапазон, элемент И 12 закрыт и тактовый импульс не проходит, обновление информации в регистрах 16 и 14 не

4О происходит. По окончании работы в счетчике 8 хранится код числа поступивших чисел, входящих в заданный .диапазон.

45. При работе в 3-м режиме происходит сравнение поступившего числа с содержимым регистра 2 на схеме 4 сравнения. Содержимое регистра 1 на работу устройства не влияет, так как на вход

50 22 подан потенциал логической единицы, который поступает на первый вход элемента И 12. В 3-м режиме иэ поступающей последовательности чисел выделяются числа, меньшие заданного, 55 и осуществляется их сортировка по убыванию. Если по окончании работы содержимое счетчика О не равно нулю, то ближайшее меньшее к заданному находится в регистре 1б первого узла

1 552173

15 сравнения и подается на выход устройства по первому выходу 291 (10

Характеристика работы устройства

Вход

Режим

21 ?2 23

Выделение и "Сортировка по убыванию" чисел в заданном диапазоне

"Сортировка по убыванию"

Выделение ближайшего меньшего к заданному

Выделение ближайшего большего к заданному

"Сортировка по возрастаниюн

Выделение и "Сортировка по возрастанию" чисел в заданном диапазоне

Составитель Е.Иванова

Техред Л.Олийнык Корректор С.Черни

Редактор В.Петраш

Тираж 560

>аказ 330

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Носква, Ж-35, Раушская наб;, д. 4/5

Производственно-издательский комбинат Патент, г.Ужгород, ул. Гагарина,101

При работе устройства в 4-м режиме посредством схемы 3 сравнения, элемента ИЛИ 5 и элемента И 12 из поступающей последовательности чисел выделяются числа больше заданного и офуществляется их сортировка по возрастанию. Если по окончании работы сфдержимое счетчика 8 не равно нулю, т ближайшее большее к заданному выд ется по первому выходу 29 устройс ва.

1 (Ф ормула изобретения

Устройство для сортировки чисел по авт. св. V 111?36?., о т Jl и ч а ю

gl е е с я тем, что, с целью расши-! рения функциональных возможностеи за сечет возможности сортировки чисел в заданном диапазоне и выделения ближайшего большего или ближайшего мень- 25

Шего к заданному, в него введены два регистра, две схемы сравнения, два элемента ИЛИ, элемент задержки, счетчик и третий элемент И, причем входы нижней и верхней границ диапазона устройства соединены с установочными входами регистров, выходы разрядов которых соединены с входами первых групп соответственно первой и второй схем сравнения, входы вторых групп которых подключены к выходам разрядов входного регистра, а выходы соединены с первыми входами соответственно первого и второго элементов ИЛИ, вторые входы которых соединены соответственно с первым и вторым управляющими входами устройства, а выходы подключены соответственно к первому и второму входам третьего элемента И, третий вход которого через элемент задержки соединен с входом тактовых импульсов устройства, и синхровходом входного регистра, а выход подключен к вторым входам элементов И всех узлов сравнения и суммирующему входу счетчика, вход установки в "0" которого подключен к шине начальной установки устройства, а выходы разрядов соединены с контрольным выходом устройства.