SU1583934A1

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

Info

Publication number: SU1583934A1
Application number: SU884419518A
Authority: SU
Inventors: Олег Кузьмич Мешков; Игорь Борисович Боженко; Петр Александрович Кондратов
Original assignee: Львовский политехнический институт им.Ленинского комсомола
Priority date: 1988-05-04
Filing date: 1988-05-04
Publication date: 1990-08-07

Abstract

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

Description

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

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

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

Устройство (фиг.1) содержит счетчик 1, группу триггеров 2, приоритетный шифратор 3, элементы И 4-7 и ИЛИ 8, коммутатор 9, группу сумматоров 10 по модулю два, дешифратор 11.

С выхода 12 поступает сигнал окончания операции ввода, с выхода 13 сигнал окончания вывода. По входу 14 поступает сигнал ’’Чтение, по входу 15 - Запись, по входу 16 - Убывание, по входу 1.7 - сигнал сброса НУ. По входам 18 и 19 поступают синхросигналы, соответственно Т2, Т1. По входам 20 поступают т-разрядные числа нормализуемого списка. С выхода 21 поступают m-разрядные числа нормализованного списка.

, На фиг.2ч , 6 - синхросигналы соответственно Т2, Т1 ; 0- сигнал За-. пись; г - сигналы инкремента счетчика 1 с выхода элемента 8; сигнал переноса счетчика; е- сигналы установки, триггеров 2 с выхода элемента 5; ж - сигнал Чтение”* j сигналы, сброса триггеров с выхода элемента 4; и~ сигнал запроса шифратора 3.

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

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

Начальная установка устройства осуществляется сигналом’ НУ. Этот сигнал обнуляет триггер 2 и через элемент ИЛИ 8 счетчик I. Операция ввода задается сигналом Запись (фиг.2й). По нему элемент И 7 разрешает поступление синхросигналов Т1 (фиг.2а) на инкрементацию счетчика 1 (фиг.2г). В соответствии с состояниями счетчика коммутатор 9 поочередно подключает к первым входам сумматоров 10 по модулю два входы 20 устройства, по каждому из которых поступает входящее в упорядочиваемый список число·

Сумматоры 10 выполняют функцию управляемых инверторов. При сортировке чисел в порядке их возрастания на входе 16 устройства устанавливается уровень 0. Соответственно,’ 0 на выходе элемента И 6 определяет передачу числа на выход сумматоров 10 без его инверсии. При сортировке в порядке убывания на входе 16 устанавливается 1 - сигнал Убывание и при совпадении его с сигналом Запись элемент 6 формирует на своем выходе 1, а сумматоры 10 инверти>5 руют поступающее на их первые входы число.

В зависимости от значения поступающего на его вход числа дешифратор 11 разрешает установку соответствую20 щего триггера 2 синхросигналом Т2 (фиг.25,0) . В группе триггеров 2 запоминаются сортирующие числа в зависимости от их значения, причем числу наибольшей величины при упорядо25 чивании по возрастанию присваивается наименьший приоритет, при упорядочивании по убыванию - наибольший. На; информационном выходе шифратора 3 устанавливается код, соответствую30 щий числу с наибольшим приоритетом.

Окончание операции ввода определяется по сигналу переноса счетчика 1 (фиг. 2j). По нему сигнал Запись сбрасывается

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

В соответствии с состоянием информационного выхода шифратора 3 дешифратор 11 устанавливает на своем выходе разрешение на сброс того из 5Q триггеров 2, которому присвоен наибольший приоритет. По синхросигналу Т2 с выхода элемента И 4 (4иг.2|) этот триггер сбрасывается. На 1авыходе шифратора устанавливается код следующего по приоритету числа. На выход 21 устройства поступает синхронно с сигналом Т2 упорядоченный список. Процесс продолжается до обнуления всех триггеров 2, что вызывает сброс сигнала запроса шифратора (фиг.2и) - на выходе 13 устройства устанавливается сигнал окончания сортировки, по которому сигнал Чтение” сбрасывается.

Claims

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

Устройство для сортировки чисел, содержащее счетчик, группу триггеров, элемент ИЛИ, четыре элемента И, приоритетный шифратор, причем первые входы первого и второго элементов И объединены, отличающееся тем, что, с целью упрощения устройства, оно содержит коммутатор, дешифратор, группу сумматоров по модулю два, причем выход запроса приоритетного шифратора является выходом Окончание вывода устройства, выходы приоритетного шифратора являются информационными выходами устройства и подключены к входам первой группы коммутатора, входы групп с второй по (N+l)-to (Ν· - количество сортируемых чисел) которого являются входами чисел устройства, а управляющие входы коммутатора подключены к выходам разрядов счётчика, выход переноса которого является выходом Окончание ввода устройства, счетный вход подключен к выходу первого элемента И, а вход сброса - к выходу элемента

1583934 6

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

I

Фиг. 2

СТб Уст

Ут

СТб СБР £0