Устройство для сортировки чисел
Патент 943707
Авторы
Классы МПК
Устройство для сортировки чисел
Иллюстрации
Реферат
Союз Советских
Социалистических
Республик
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К .АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и943707 (Sl ) Дополнительное к авт. свид-ву (22) Заявлено 02.07.80 (21) 2951056/18-24 (S l ) IVL. Кд.
0 06 F 7/ос с присоединением заявки М
Риударстееюв1 квинтет
СССР ао аеаак нзобретеннй и открктвй (23) П риоритет—
Опубликовано 15.07.82. Бюллетень № 26 (53) УДК681.325..5 (088.8) Дата опубликования описаиия 17.07.82 (72) Авторы изобретения
Э. П. Чернаков и Б. С. Богумирский (71 ) 3ая вител ь (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ
Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных.
Известно устройство для сортировки двоичных чисел, содержащее М сдвигающих регистров сортируемых чисел, элементы управления (Ц .
Данное устройство позволяет выбирать из N двоичных кодов чисел только минимальные или максимальные значения, что ограничивает область его применения.
Наиболее близким по технической сущности и достигаемому результату к предложенному является устройство, со. держащее М сдвигающих регистров сортируемых чисел, узел сравнения, узел анализа количества единиц и сдвигающий регистр результата (2).
Это устройство обладает низким быстродействием.
Целью изобретения является повышение быстродействия.
Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее регистр результата, узел
5 сравнения и узел анализа количества единиц, выходы которого соединены со входами первой группы узла сравнения, входы второй группы которого подключены к группе входов задания константы устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен ко входу тактовых сигналов устройства, введены rl узлов анализа, каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и схемы сравнения, причем информационный вход кольцевого то регистра сдвига каждого q -го узла анализа соединен с 1-м ивформациончым входом устройства, где i 1,2,..., и, выход дольцевого регистра сдвига каж-. дого узла анализа подключен ко входу
9437 элемента памяти и к первому входу схемы сравнения, второй вход которой соединен с выходом узла сравнения, а выход — со входом установки в единичное состояние триггера, вход установки в нулевое состояние которого подключен ко входу управления устройства, а выход » ко входу управления элемента памяти, выход элемента памяти каждого
i -го узла анализа соединен с i -м входом узла анализа количества единиц, входы управления кольцевых регистров сдвига каждого узла анализа подключены ко входу тактовых сигналов устройства.
Узел анализа количества единиц состоит из дешифратора, шифратора, элементов ИЛИ, причем входы узла анализа соединены со входами дешифратора, каждый Р-й выход которого для единиц во входном числе соединен со входом щ
j -ro элемента ИЛИ, где 8 = l, 2,..., к, j = 1,2,...,п -1, к — количество выходов дешифратора; щ — количество выходов с одинаковым количеством единиц во входном числе, выход каждого -го элемента ИЛИ подключен к j -му входу шифратора, выходы дешифратора, соответствуюшие 1 =0 и = tn соединены с m--M и (hl+ 1) м входами шифратора соответственно. зо
На фиг. 1 представлена блок- хема устройства; на фиг. 2 — схема узла анализа количества единиц. .Устройство содержит регистр результата 1, узел сравнения 2, узел анализа
35 количества единиц 3, и узлов анализа 4, состоящих из элементов. памяти 5, триггеров 6, схем сравнения 7, кольцевых сдвигающих регистров 8, входов тактовых сигналов 9, вход установки в исходное состояние 10, вход задания констант
11, информационные входы 12. Узел анализа количества единиц 3 (фиг. 2) содержит дешифратор 13, элементы ИЛИ
14, шифратор 15, входы 16 и выходы 17.
Элементы памяти 5 могут представлять собой Ц-триггеры с синхронизируюшими входами.
Устройство работаеч следующим образом.
Под выделением числа с заданным рангом понимается нахождение в исходном массиве числа, относительная величина которого задана, начиная с минимального числа (например, найти девятое ho величине число). Ранг числа К - это номер
55 этого числа в отсортированном по возрастанию массиве чисел. Так, если не4 обходимо найти девято< по величине чис07 ф ,ло, то R = 9. B кольцевые сдвигаюшие регистры 4 при помощи импульсов, подаваемых на вход тактовых сигналов 9 устройства, записываются сортируемые числа, начиная со старших разрядов. На вход установки в исходное состояние 10 устройства подается импульс, который устанавливает триггеры 6 в "1", и на управляющих входах элементов 5 памяти появляется разрешающий сигнал. На управляющий вход 8 устройства подается константа сравнения где М вЂ” количество сортируемых чисел;
g — ранг выбираемого числа.
После этого устройство переходит в режим выделения двоичного числа с наперед заданным рангом.
Этот процесс проходит за m тактов, где Vh — разрядность сортируемых чисел.
B первом такте на информационные входы элементов 5 памяти поступают значения старших разрядов N чисел и проходят на узел анализа количества единиц 3. В этом узле подсчитывается количество единиц, содержашихся в старших разрядах сортируемых чисел, и выдается результат подсчета на узел 2 сравнения. Если количество единиц в с, старших разрядах чисел не меньше конВ станты сравнения И, то на выходе узла
2 сравнения появляется "1", в противном случае — "0". Выходное значение узла 2 сравнения записывается в регистр результата 1 в качестве цифры старшего разряда выделяемого числа и подается на вторые входы схем сравнения 7, на первые входы которых поступают сигналы старших разрядов сортнруемых чисел. Каждая схема 7 сравнения выдает единичный сигнал, если значения, подаваемые на ее входы, не совпадают, в противном случае - нулевой. Таким с образом, если значения на выходах кольцевого сдвигающего регистра 4 и узла сравнения 2 не совпадают, то снимается разрешающий сигнал с соответствующего элемента 5 памяти, чем блокируется запись в него последующих значений в течение всех последуюших тактов работы устройства.
Заблокированный элемент 5 памяти выдает в узел анализа количества единиц 3 то значение, которое было записано в него до снятия с управляющего входа разрешающего сигнала. Во втором такте на управляюший вход 9 устройства подается импульс, по которому информация
5 9437 в регистрах 1 и 4 сдвигается на один разряд в сторону старших разрядов, причем в регистрах 4 осуществляется кольцевой сдвиг. В дальнейшем устройство работает аналогично описанному. После выполнения TA тактов в сдвигающем регистре 1 результата находится выделенное число, которое выводится из устройства, а в регистрах 4 - сортируемые числа. Для последующего выделения чис- 10 .ла с заданным рангом из этого же набора двоичных чисел необходимо подать импульс на управляющий вход 10 устройства, а затем повторить все операции, описанные выше. 13
Таким образом, использование данного устройства позволяет сократить время выборки из исходного массива двоичных чисел нескольких значений в определенном порядке. 20
Формула изобретения
1. Устройство для сортировки чисел, содержащее регистр результата, узел сравнения и узел анализа количества единиц, выходы которого соединены со входами первой группы узла сравнения, входы второй группы которого подклю- Зр чены к группе входов задания константы устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен ко входу тактовых сигналов устройства, о т л и ч а ю щ е е с я . тем, что, с целью повышения быстродействия, в него введены и узлов анализа, каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триг- 40 гера и схемы сравнения, причем информационный вход кольцевого регистра сдвига каждого -го узла анализа соединен
07 6 с -м информационным входом устройства где $ -3.,2,..., n, выход кольцевого ре- гистра сдвига каждого узла анализа подключен ко входу элемента памяти и к первому входу схемы сравнения, второй вход которой соединен с выходом узла сравнения, а выход - со входом установки в единичное состояние триггера, вход установки в нулевое состояние которого подключен ко входу управления устройства, а выход - ко входу управления элемента памяти, выход элемента памяти каждого 1 -ro узла анализа соединен с -м входом узла анализа количества единиц, входы управления кольцевых регистров сдвига каждого узла анализа подключены ко входу тактовых сигналов устройства.
2. Устройство по п. 1, а т л и ч а— ю щ е е с я тем, что узел анализа количества единиц состоит из дешифратора, шифратора, элементов ИЛИ, причем входы узла анализа соединены со входами дешифратора, каждый Р -й выход которого идя единиц во входном числе соединен со входом у -го элемента ИЛИ, где 0 = 1,2,...,к, ) .1,2,...,11 -1, к - количество выходов дешифратора; m — количество выходов с одинаковым количеством единчц во входном числе, выход каждого j -го элемента ИЛИ подключен к j -му входу шифратора, выходы дешифратора, соответствующие j =0 и 1 =m, соединены с щ -м и (111+1)-м входами шифратора соответственно.
Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР
% 285347, кл. Cj 06 Г 7/00, 1963.
2. Авторское свидетельство СССР
Ж 610107, кл. Ci 06 F 7/06, 1978 (прототип).
94Э7 07
7б
7б
Iui. 2
Заказ 5110/55 Тираж 7 3 1 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ЛПП "Патент", r. Ужгород, ул. Проектная, 4
Составитель Б. Богумирский
Редактор М; Дылын Техред И. Гайду Корректор А. Форенн