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

7) Изобретение отно ке и вычислительной т быть использовано маотся хнике и еализаГОСУДАРСТВЕННЫИ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГННТ СССР Д ВТОРСНОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ СОРТИРО цин устройств автоматического управления. Цель изобретения - повышение быстродействия, Устройствосодержит счетчик 1, дешифратор 2,блок 3 памяти, элемент 4 сравнения,регистр 5, формирователь 6 импульсов, триггер 7, распределитель 8 импульсов, группу триггеров 9, группыэлементов И 10 и ИЛИ 11, элементИ-ИЕ 12, информационный вход 13,вход 14 задания количества градаций сортировки, вход 15 запуска,выход 16 окончания работы, информационный выход 17. Устройство позволяет сортировать по величине числа по 2 ф градациям (уставкам) за птактов, используя принцип дихотомии.Изобретение относится к автоматике и вычислительной технике и может быть использовано при,реализации устройств автоматического уп"равления,Цель изобретения - повышениебыстродействия.Схема устройства приведена начертеже.Устройство содержит счетчик 1,дешифратор 2, блок 3 памяти, элемент 4 сравнения, регистр 5, формирователь .6 импульсов, триггер 7,распределитель 8 импульсов, группутриггеров 9, группы элементов И 10и ИЛИ 11, элемент И-НЕ 12, информационный вход 13 вход 14 количестваградаций сортировки, вход 15 запуска, выход 16 окончания работы, информационный выход 17.Устройство работает следующимобразом,Предварительно в блок 3 памятизаписывается в порядке возрастания2 " - 1 границ градаций сортировкичисел. Затем по сигналу запуска повходу 15 в счетчик 1 записываетсякод числа п,Двоичный код состояния счетчика 1преобразуется дешифратором 2 в позиционный и-разрядный и поступаетчерез группу элементов ИЛИ 11 наадресные входы блока 3 памяти.Блок 3 памяти устанавливаетсяв адрес А,=2" , который являетсясерединой заданного поля адресовуставок (границ градаций сортировки).Злемент 4 сравнения сравниваетчисло, поступающее на вход 13, суставкой, записанной в блоке 3 пад мяти по адресу 2 . Если число боль.ше или равно уставке, то на выходеэлемента 4 сравнения устанавливает.ся логическая единица, которая.поступает на П-входы группы триггеров9, и импульсом с выхода распределителя импульсов устанавливает п-йтриггер 9 в единичное состояние.С выхода п-го триггера 9 группылогическая единица поступает наи-й элемент группы элементов ИЛИ 11.Затем содержимое счетчика 1 уменьшается на единицу, а на адресныхвходах блока 3 памяти устанавливаМН ется код адреса А =1 х 2 +1 х 2"й к. 2 , т.е. дальнейшее сравнениепроизводится с уставками, записанны Формула из обре тенияУстройство для сортировки чисел,содержащее счетчик, дешифратор, груп.о 35 пу из и элементов И, где (2 -1)количество градаций сортировки чисел, регистр, распределитель импульсов, блок п"мяти и триггер, причем выходы разрядов счетчика соединены с соответствующими входами дедяфратора .-Й выход которого (где1, 2п) соединен с первымвходом х-го элемента И группы, вторые входы всех элементов И группыобъединены, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него введены элементсравнения, группа из и элементов ИЛИ,группа из п триггеров, формирователь импульсов и элемент И-НЕ,причем вход задания количества градаций устройства соединен с информационныья входами счетчика, входзапуска устройства - с входом формирователя импульсов, выход которого .соединен с входом записи счетчика,входами установки в нулевое состояние триггеров группы и входом установки в единичное состояние триггера,5 1 О 15 2 О 25 ЗО ми в зоне блока 3 памяти по адресам,большим 2"Если число меньше уставки, записанной по адресу А, =1 х 2 " , то навыходе элемента 4 сравнения устанавливается логический нуль, которыйпоступает на 0-входы группы триггеров 9. Поэтому в следующем тактесортируемое число сравнивается с уставкой, записанной по адресу А=Ох 2 +1 х 2 2" ",Таким образом, если на х-м тактесортируемое число сравнивается суставкой, записанной в блоке памятипо адресу А, и не меньше этой уставки, то на (+1)-м такте сортируемое число сравнивается с уставкой,записанной в блоке 3 памяти по ад 1-1-ресу А;, = А, + 2, а если мень-,л-ше - то по адресу А+, = А;:-2 +2т.е. поиск нужной градации осуществляется по принципу дихотомии.Через и тактов сигнал логическойединицы устанавливается на нулевомвыходе дешифратора 2, импульсом через элемент И-НЕ 12 останавливаетсяраспределитель 8 импульсов и производится запись адреса найденной градации в регистр 5.Заказ 1711/47 Тираж 667 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР 113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 прямой выход которого является выходом окончания работы устройства и соединен с входом запуска распределителя импульсов, первый выход которого соединен с вторыми входами элементов И группы, второй выход распределителя импульсов соединен со счетным входом счетчика и первым входом элемента И-НЕ, выход которого соединен с входом разрешения записи регистра и входом установки триггера в нулевое состояние, -й выход дешифратора соединен с первым входом -го элемента ИЛИ группы, выход которого соединен с Х-м адресным входом блока памяти, информационный выход которого соединен спервым входом элемента сравнения,выход которого соединен с информационными входами триггеров группы, выход -го элемента И группы соединенс входом синхронизации х-го триггерагруппы, прямой выход которого соединен с вторым входом х-го элементаИЛИ группы и -м информационным входом регистра, выход х-го разрядакоторого является -м информационным выходом устройства, выход кодануля дешифратора соединен с вторым 15 входом элемента И-НЕ, информационныйвход устройства соединен с вторымвходом элемента сравнения.