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

(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

1

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

Известно устройство для сортировки двоичных чисел, сод жащее N сдвигающих регистров сортируемых чисел, элементы угфавления

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

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

Это устройство обладает низким быстродействием.

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

Поставленная цель достигается тем, что в устройство для ссртировки чисел, содержащее регистр результата, узел сравнения и узел анализа количества единиц, выходы которого соединены со входами первой группы узла сравнения, входы второй группы которого подклю,Q чены к группе входов задания константы устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен ко входу тактовых

15 С1ггналов устройства, введены п узлов анализа, каждый из которых состоит из кольцевого регистра сдвиге, элемента памяти, тригг а к схемы сравнения, |$ричем1информаиионный вход кольцевого

20 регистра сдвига каждого i -го узла анализа соединен с i -м информадиончым входом устройства, где А 1,2,..., п , выход дольцевого регистра сдвига каждого узпа анапвэа подключен ко входу элемента памяти и к первому входу схемы сравнения, Bxqpoft вход соединен с выходом узла сравнения, а выход - со входом установки в единичное состояние триггера, вход установки в нулевое состояние которого подключен ко входу управления устройства, а выход - ко входу управления элемента памяти, выход элемента памяти каждого -i -го узла анализа соединен с -i -м входом узла анализа количества единиц, входы управления кольцевых регистрс)в сдвига каждого узла анализа подключены ко входу тактовых сигналов устройства. Узел анализа количества единиц состоит из дешифратора, шифратора, элементов ИЛИ, причем входы узла анализа соединены со входами дешифратора, каждый -й выход которого для единиц во входном числе соединен со входом J-го элемента ИЛИ, где В 1,2,...,к, j 1, 2,,..,m-1, к - количество выходов дешифратора; гл - количество выходов с одинаковым количеством единиц во входном числе, выход каждого j-ro элемента ИЛИ подключен к j -му входу ши ратора, выходы дешифратора, соответствующие j О и j m соединены с гп-м и (m-f l)-M входами шифратора cooTBeTCTBeifflo. На фиг. 1 1редставлена блок- хема устройства; на фиг. 2 - схема узла анализа количества единиц. Устройство содержит регистр результата 1, узел сравнения 2, узел анализа количества единиц 3, п узлов анализа 4 состояших из элементов .памяти 5, триггеров 6, схем сравнения 7, кольцевых сдвигающих регистров 8, входов тактовых сигналов 9, вход установки в исход ное состояние 10, вход задания констан 11, информационные входы 12, Узел анализа количества единиц 3 (фиг, 2) содержит дешифратор 13, элементы ИЛИ 14, шифратор 15, входы 16 и выходы 1 Элементы памяти 5 могут представлять собой D-триггеры с синхронизирующими входами. Устройство работав следующим обра зом. Под выделением числа с задагшым ран гом понимается нахождение в исходном массиве числа, относительная величина которого задана, начиная с минимальног числа (например, найти девятое fto величине число). Ранг числа R - это номер этого числа в отсортированном по возрастанию массиве чисел. Так, если необходимо найти девятое по величине чис .ло, то R 9, в кольцевые сдвигающие регистры 4 при помощи импульсов, подаваемых на вход тактовых сигналов 9 устройства, записываются сортируемые числа, начиная со старщих разрядов. На вход установки в исходное состояние 10 устройства подается импульс, который устанавливает триггеры 6 в 1, и на управляющих входах элементов 5 памяти появляется разрещающий сигнал. На управляющий вход 8 устройства подается константа сравнения А N+ 1-R, где N - количество сортируемых чисел; R - ранг выб1фаемого числа. После этого устройство переходит в режим выделения двоичного числа с наперед заданным рангом. Этот процесс проходит за m тактов, где TTI - разрядность сортируемых чисел.. В первомтакте на информационные входы элементов 5 памяти поступают значения старших разрядов N чисел и проходят на узел анализа количества единиц 3, ЕЗ этом узле подсчитывается количество единиц, содержащихся в старщих разрядах сортируемых чисел, и выдается результат подсчета на узел 2 сравнения. Если количество единиц в с. старших разрядах чисел не меньше константы сравнения И, то на выходе узла 2 сравнения появляется i, в противном случае - О. Выходное значение узла 2 сравнения записывается в регистр результата 1 в качестве цифры старшего разряда вьщеляемого числа и подается на вторые входы схем сравнения 7, на первые входы которых поступают сигналы старших разрядов сортируемых чисел. Каждая схема 7 сравнения вьщает единичный сигнал, если значения, подаваемые на ее входы, не совпадают, в противном случае - нулевой. Таким о Jj образом, если значения на выходах кольцевого сдвигающего регистра 4 и узла сравнения 2 не совпадают, то снимается разрешающий сигнал с соответствующего элемента 5 памяти, чем блокируется запись в него последующих значений в течение всех последующих тактов работы устройства. Заблокированный элемент 5 памяти выдает в узел анализа количества единиц 3 то значение, было записано в него до снятия с управляющего входа разреш,ающего сигнала. Во втором такте на утравляюший вход 9 устройства подается импульс, по которому информация

в регистрах 1 и 4 сдвигается на один разряд в сторону старших разрядов, причем в регистрах 4 осуществляется кольцевой сдвиг. В дальнейшем устройство работает аналогично описанному. После выполнения m тактов в сдвигающем регистре 1 результата находится вьщеленное число, которое выводится из устройства, а в регистрах 4 - сортируемые числа. Для последующего выделения числа с заданным рангом из этого же набора двоичных чисел необходимо подать импульс на управляющий вход 10 устройства, а затем повторить все операции, описанные вьпие.

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

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

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

Источники информации, принятые во внимание при экспертизе

IS

Iff

,,

Фиг.г