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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации устройств автоматического управления. Цель изобретения - повышение быстродействия. Устройство содержит счетчик 1, дешифратор 2, блок памяти 3, элемент сравнения 4, регистр 5, формирователь импульсов 6, триггер 7, распределитель импульсов 8, группу триггеров 9, группы элементов И 10 и ИЛИ 11, элемент И-НЕ 12, информационный вход 13, вход задания количества градаций сортировки 14, вход запуска 15, выход окончания работы 16, информационный выход 17. Устройство позволяет сортировать по величине числа по 2<SP POS="POST">N</SP> градациям (уставкам) за N тактов, используя принцип дихотомии. 1 ил.

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

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

РЕСПУБЛИК ии4 С 06 F 7/06

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

Н ABTOPCH0MV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР (21) 429979 О/24-2- (22) 19,08,87 (46) 15. 04. 89. В|с:т, - 14 (7 1 ) Омское произ .>дстве нное обно†динение электрических точных приборов "Электроточприбор" (72) В,M.Îñèïoâ, Г.А.Сподарцев и Л.Г.Шафионецкая (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР № 978143, кл. С 06 F 7/04, 1981., Авторское свидетельство СССР

¹ 1151952, кл. G 06 Г 7/06, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализаÄÄSUÄÄ 1472898 А1 ции устройств автоматического управчения. Цель изобретения — повышение быстродействия. Устройство содержит счетчик 1, дешифратор 2, блок 3 памяти, элемент 4 сравнения, регистр 5, формирователь 6 импульсов, триггер 7, распределитель 8 импульсов, группу триггеров 9, группы элементов И 10 и ИЛИ 11, элемент

И-ИЕ 12 информационный вход 13, вход 14 задания количества градаций сортировки, вход 15 запуска, выход 16 окончания работы, информационный выход 17 ° Устройство позволяет сортировать по величине числа по 2 градациям (уставкам) за п тактов, используя принцип дихотомии.

1 ил.

14 72898

1О

2О

ЗО

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

Цель изобретения — повышение быстродействия.

Схема устройства приведена на чертеже.

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

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

Предварительно в блок 3 памяти записывается в порядке возрастания

2 " — 1 границ градаций сортировки чисел. Затем по сигналу запуска по входу 15 в счетчик 1 записывается код числа п.

Двоичный код состояния счетчика i преобразуется дешифратором 2 в позиционНЬ1й и-разрядный и поступает через группу элементов ИЛИ 11 на адресные входы блока 3 памяти.

Блок 3 памяти устанавливается в адрес А,=2, который является серединой заданного поля адресов уставок (границ градаций сортировки).

Злемент 4 сравнения сравнивает число, поступающее на вход 13, с уставкой, записанной в блоке 3 па44-4 мяти по адресу 2 . Если число больше или равно уставке, то на выходе элемента 4 сравнения устанавливает.ся логическая единица, которая.поступает на D-входы группы триггеров

9, и импульсом с выхода распределителя импульсов устанавливает п-й триггер 9 в единичное состояние.

С выхода п-ro триггера 9 группы логическая единица поступает на п-й элемент группы элементов ИЛИ 11.

Затем содержимое счетчика 1 уменьшается на единицу, а на адресных входах блока 3 памяти устанавлива44 -1 41 - ется код адреса А =1х 2 +I х 2" >

1l -1 к

O 2, т.е. дальнейшее сравнение производится с уставками, записанными в зоне блока 3 памяти по адресам, большим 2"

Если число меньше уставки, записанной по адресу А, =1 х 2 ", то на выходе элемента 4 сравнения устанавливается логический нуль, который поступает на D-входы группы триггеров 9. Поэтому в следующем такте сортируемое число сравнивается с уставкой, записанной по адресу А =

0 х 2 44 1 + 1 х 2 44 . 2 "

Таким образом, если на i-м такте сортируемое число сравнивается с уставкой, записанной в блоке памяти по адресу А, и не меньше этой уставки, то на (i+i)-м такте сортируемое число сравнивается с уставкой, записанной в блоке 3 памяти по ад44 1-4 ресу А;, = А, + 2, а если мень-.

44-1 ше — то по адресу А„+4 = А;:-2 +2 т.е. поиск нужной градации осуществляется по принципу дихотомии.

Через и тактов сигнал логической единицы устанавливается на нулевом выходе дешифратора 2, импульсом через элемент И-НЕ 12 останавливается распределитель 8 импульсов и производится запись адреса найденной граI дации в регистр 5.

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

Устройство для сортировки чисел, содержащее счетчик, дешифратор, груп.

44

35 пу из и элементов И, где (2 -1} количество градаций сортировки чисел, регистр, распределитель импульсов, блок п мяти и триггер, причем выходы разрядов счетчика соединены с соответствующими входами де4ш1фратора., i-й выход которого (где

1, 2,...,п) соединен с первым входом i-ro элемента И группы, вторые входы всех элементов И группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент

1 сравнения, группа из и элементов ИЛИ, группа из и триггеров, формирователь импульсов и элемент И-НЕ, причем вход задания количества градаций устройства соединен с информационны1я входами счетчика, вход запуска устройства — с входом формирователя импульсов, выход которого . соединен с входом записи счетчика, входами установки в нулевое состояние триггеров группы и входом установки в единичное состояние триггера, 1472898 .

Составитель В. Горохов

Редактор И.Рыбченко Техред М.Дидык Корректор Э.Лончакова

Заказ 1711/47 Тираж 667 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,101 прямой выход которого является выходом окончания работы устройства и соединен с входом запуска распределителя импульсов, первый выход которого соединен с вторыми входами элементов И группы, второй выход распределителя импульсов соединен со счетным входом счетчика и первым входом элемента И-НЕ, выход которого соединен с входом разрешения за писи регистра и входом установки триггера в нулевое состояние, i-й выход дешифратора соединен с первым входом i-ro элемента ИЛИ группы, выход которого соединен с $. — м адресным входом блока памяти, информационный выход которого соединен с первым входом элемента сравнения, выход которого соединен с информационными входами триггеров группы, выход i-ro элемента И группы соединен с входом синхронизации i-го триггера группы, прямой выход которого соединен с вторым входом i-го элемента

ИЛИ группы и i-м информационным входом регистра, выход i-ro разряда которого является i-м информационным выходом устройства, выход кода нуля дешифратора соединен с вторым входом элемента И-НЕ, информационный вход устройства соединен с вторым входом элемента сравнения.