Устройство для сортировки чисел Советский патент 1989 года по МПК G06F7/06 

/7

Ь vj

ю

оо о

00

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

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

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

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

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

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

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

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

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

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

С выхода n-го триггера 9 группы логическая единица поступает на n-й элемент группы элементов ИЛИ 1 Затем содержимое счетчика 1 уменьшается на единицу, а на адресных входах блока 3 памяти устанавливается код адреса х 2 +1 х 2п

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

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

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

, а если мены - л от- л.1

. . - А ,- / 4- /

ше - то по адресу А ;., А; -2 +2 т.е. поиск нужной градации осуществляется по принципу дихотомии.

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

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

Устройство для сортировки чисел, содержащее счетчик, дешифратор, группу из п элементов И, где (2 -1) - количество градаций сортировки чисел, регистр, распределитель импульсов, блок памяти и триггер, причем выходы разрядов счетчика соединены с соответствующими входами дешифратора.; i-и выход которого (где i 15 2,...,п) соединен с первым входом 1-го элемента И группы, вторые входы всех элементов И группы объединены, отличающееся тем, что, с целью повышения быстродействия, в него введены элемент сравнения, группа из п элементов ИЛИ группа из п триггеров, формирователь импульсов и элемент И-НЕ, причем вход задания количества градаций устройства соединен с информационными входами счетчика, вход запуска устройства - с входом формирователя импульсов, выход которого соединен с входом записи счетчика, входами установки в нулевое состояние триггеров группы и входом установки в единичное состояние триггера

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

0

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

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