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

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств обработки информации. Цель изобретения - упрощение устройства. Устройство содержит счетчик 1, группу триггеров 2, приоритетный шифратор 3, элементы И 4-7, элемент ИЛИ 8, коммутатор 9, группу сумматоров 10 по модулю два, дешифратор 11. В процессе ввода устройством поочередно опрашиваются информационные входы,по каждому из которых поступает сортируемое число. В зависимости от величины числа и направления упорядочения - по убыванию или возрастанию - устанавливается соответствующий, имеющий свой приоритет, триггер. В процессе вывода на информационный выход устройства поступает упорядоченный список. 2 ил.

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

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

РЕСПУБЛИК (19) (11) (5l)5 С 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ну

Чт

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

Н А BTOPCKOMV СВИДЕТЕЛЬСТВУ

1 (21) 4419518/24-24 (22) 04.05.88 (46) 07.08.90. Бюл. М - 29 (71) Львовский политехнический институт им. Ленинского комсомола (72) О.К. Мешков, И.Б.Боженко и П.А.Кондратов (53) 681.325(088,8) (56) Авторское свидетельство СССР

У 993251, кл. G 06 F 7/08, 1983.

Авторское свидетельство СССР

9 1 201833, кл. С 06 F 7/08, 1984. .(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализиро- ванных вычислительных устройств об2 работки информации. Цель иэобретения— упрощение устройства. Устройство содержит счетчик 1, группу триггеров 2, приоритетный шифратор 3, элементы

И 4-7, элемент ИЛИ 8, коммутатор 9, группу сумматоров 1 0 по модулю два, дешифратор 11. В процессе ввода устройством поочередно опрашиваются информационные входы, по каждому из которых поступает сортируемое число.

В зависимости от величины числа и направления упорядочения — по убыванию или возрастанию — устанавливается соответствующий, имеющий свой приоритет, триггер. В процессе вывода на информационный выход устройства поступает упорядоченный список. 2 ил.

l 58Э9Э4

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств об5 работки информации.

Цель изобретения — упрощение устройства.

На фиг. 1 изображена функциональная схема предлагаемого устройства, на фиг. 2 - временные диаграммы его работы.

Устройство (фиг.l) содержит счет" чик 1, группу триггеров 2, приоритетный шифратор 3, элементы И 4-7 и !5

ИЛИ 8, коммутатор 9, группу сумматоров 10 по модулю два, дешифратор 11.

С выхода 12 поступает сигнал окончания операции ввода, с выхода 13сигнал окончания вывода. По входу 14 2р поступает сигнал "Чтение", по входу 15 - "Запись", по входу 16 - "Убывание", по входу !.7 - сигнал сброса

"НУ". По входам 18 и 19 поступают синхросигналы, соответственно Т2, Tl. 25

По входам 20 поступают ш-разрядные числа иормализуемого списка. С выхода 21 поступают m-разрядные числанормализованного списка.

На фиг.2 q, 6 — синхросигналь1 со- 3р ответственно Т2, Tl 6 — сигнал "За-. пись"; 1, - сигналы инкремента счетчика с выхода элемента 8, — сигнал переноса счетчика е — сигналы установки. триггеров 2 с выхода элемента 5, х -, сигнал "Чтение" сигналы сброса триггеров с выхода элемента 4 ц - сигнал запроса шифратора 3.

Предлагаемое устройство предназна- 40 чено для сортировки пятнадцати четырехразрядных чисел.

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

Начальная установка устройства осуществляется сигналом "НУ". Этот сигнал обнуляет триггер 2 и через элемент ИЛИ 8 счетчик !. Операция ввода задается сигналом "Запись" (фиг.2b)

По нему элемент И 7 разрешает поступление синхросигналов Tl (фиг.2ц) на инкрементацию счетчика 1 (фиг.2 ).

В соответствии с состояниями счетчика коммутатор 9 поочередно подключа55 ет к первым входам сумматоров IO no модулю два входы 20 устройства, по каждому из которых поступает входящее в упорядочиваемый список число.

Сумматоры 10 выполняют функцию управляемых инверторов. При сортиров. ке чисел в порядке их возрастания на входе 1 6 устройства устанавливается уровень "0". Соответственно, "0" на выходе элемента И 6 ойределяет передачу числа на выход сумматоров 10 без его инверсии. При сортировке в порядке убывания на входе 1 6 устанавливается "1" — сигнал "Убывание" и при совпадении его с сигналом "3aпись" элемент 6 формирует на своем выходе "1 ", а сумматоры 10 инвертируют поступающее на их первые входы число.

В зависимости от значения поступающего íà его вход числа дешифратор

ll разрешает установку соответствующего триггера 2 синхросигналом Т2 (фиг. 2б, о) ° В группе триггеров 2 запоминаются сортирующие числа в зависимости от их значения, причем числу наибольшей величины при упорядочивании по возрастанию присваивается наименьший приоритет, при упорядочивании по убыванию — наибольший. На1. информационном выходе шифратора 3 устанавливается код, соответствующий числу с наибольшим приоритетом.

Окончание операции ввода определяется по сигналу переноса счетчика I (фиг. 2 g). По нему сигнал "Запись" сбрасывается.Выдача из устройства упорядоченного списка инициируется сигналом

"Чтение" (фиг.2ж) . По нему счетчик 1 обнуляется сигналом с выхода элемента 8. По этому состоянию счетчика коммутатор 9 подключает к первым входам сумматоров 10 информационный выход шифратора 3. На выходе элемента 6 устанавливается "О" и сумматоры 0 переводятся в режим передачи данных без их инверсии.

В соответствии с состоянием информационного выхода шифратора 3 дешифратор 11 устанавливает на своем выходе разрешение на сброс того из триггеров 2, которому присвоен наибольший приоритет. По синхросигналу

Т2 с выхода элемента И 4 (4иг.2 ) этот триггер сбрасывается. Иа Iaвыходе шифратора устанавливается код следующего по приоритету числа. На выход 21 устройства поступает синхронно с сигналом Т2 упорядоченный список. Процесс продолжается до обну. ления всех триггеров 2, что вызывает

1583934

ZNC

I7epen/

СТ6 Услу

9m стб СбР

Е0 сброс сигнала запроса шифратора (фиг. 2и) — на выходе 13 устройства устанавливается сигнал окончания copt TI тировки, по которому сигнал Чтение сбрасывается.

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

Устройство для сортировки чисел, содержащее счетчик, группу триггеров, элемент ИЛИ, четыре элемента И, приоритетный шифратор, причем первые входы первого и второго элементов И объединены, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит коммутатор, дешифратор, группу сумматоров по модулю два, причем выход запроса приоритетного шифратора является выходом "Оконча- 20 ние вывода" устройства, выходы приоритетного шифратора являются информационными выходами устройства и подключены к входам первой группы коммутатора, входы групп с второй по 25 (N+))-ю (0 — количество сортируемых чисел) которого являются входами чисел устройства, а управляющие входы коммутатора подключены к выходам разрядов счетчика, выход пере- З0 носа которого является выходом "Окончание ввода" устройства, счетный вход подключен к выходу первого элемента

И, а вход сброса — к выходу элемента

ИЛИ, первый вход которого является входом начальной установки устройст ва и соединен с входами установки в

"0" всех триггеров, выходы которых соединены с соответствуюгими входами приоритетного шифратора, вход записи устройства подключен к первым входам первого и третьего элементов И, выход третьего элемента И подключен к первым входам всех сумматоров по мо-, дулю два, вторые входы которых подключены к соответствующим выходам коммутатора, выходы сумматоров по модулю два подключены к соответствующим входам дешифратора, выходы которого подключены к управляемым входам установки в "1" и "0" соответствующего триггера, входы управления установки в "1" всех триггеров объединены и подключены к выходу второго элемента И, первый тактовый вход устройства соединен с вторым входом первого элемента И, второй тактовый вход устройства соединен с вторым входом второго элемента И и первым входом четвертого элемента И, второй вход которого является входом Чтение" устройства и соединен с вторым входом элемента ИЛИ, а выход соединен с вхо" дом управления установки в "0" всех триггеров, вход Убывание" устройства подключен к второму входу третьего эле" мента И.