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

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

Иллюстрации

Показать все

Реферат

 

Б.С. Богумирский и Э.ll. Чернако

{Уй} Авторы нзобретеиия (Vl) Заявятель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

Известно устройство для сортировки чисел, содержащее и регистров, выходы которых соединены с входами. схем сравнения, другие входы которых подключены к выходам регистра результата, выходы схем сравнения соединены через переключатели с входами элемента ИЛИ, элементы И, триг гер и узлы запрета (1).

Недостатком этого устройства является низкое быстродействие.

Наиболее близкое по технической сущности к предлагаемому устройство, содержащее m регистров, выходы которых соединены с входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходы схем сравнения соединены через переключатель .с входами элемен2 та ИЛИ, элементы И, триггер, узлы запрета и временной распределитель(2)

Недостатком этого устройства является также низкое быстродействие, так как сортировка всего исходного массива чисел требует m(n+1) тактов работы устройства, где m — - число, а n - -разность сортируемых чисел.

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

tO

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

1-ой схемы сравнения и i-ой группы элементов И, выходы которых подключены к входам i-ой группы регистра результата, а каждый i — ûé выход распределителя импульсов соединен

9!15

Таким образом, с

9 на один из входов ется код количества сел, меньших числа, гистре 4 результата. сумматора 8 подается выхода счетчика сумматора 8 подасортируемых чиэаписанного в реНа второй вход код адреса об3 с управляющим входом элементов И

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

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

На чертеже представлена схема предлагаемого устройства.

Устройство содержит распредели20 тель 1 импульсов, и регистров 2, и схем 3 сравнения, регистр 4 результата, группы 5-7 элементов И, сумматор 8, счетчик 9, входы устройства

l0 и 11, вход 12 управления устрой- 33 ства и выходы !3 и 14 устройства.

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

В регистры 2 заносятся сортируе мые числа, регистр 4 результата уста30 навливается в нуль, а распределитель

1 импульсов - в исходное состояние (не показано). После этого устройство готово к сортировке чисел в порядке возрастания.

Затем на вход 10 устройства пода35 ется первый тактовый сигнал, по которому появляется сигнал на,первом (верхнем) выходе распределителя 1 импульсов. При этом открывается

40 группа 6 элементов И и число из верхнего регистра 2 переэаписывается в регистр 4 результата. Это число сравнивается со всеми сортируемыми числами в схемах 3 сравнения, сигнал на выходе которых появляется лишь в том

4$ случае, когда числа, находящиеся в соответствующих регистрах 2, меньше числа, записанного в регистре 4 результата. Счетчик 9 подсчитывает количество схем 3 сравнения, имеющих сигнал на своем выходе.

13 4 ласти памяти, начиная с которого необходимо разместить отсортированную информацию. Тогда адрес области памяти,по которому следует записать число, находящееся в регистре 4 результата, определяется соотношением где А С1Ч - адрес области памяти, начиная с которого необходимо разместить отсортированные числа

М - число чисел, меньших числа, записанного в регистре результата.

Сумматор 8 вычисляет сумму

ИИс1ц+ Й. По сигналу на входе 12 устройства число, находящееся в регист- ре 4 результата, записывается в запоминающее устройство по адресу, выдаваемому сумматором 8.

Второй такт работы устройства начинается с подачи второго тактового сигнала на вход !0 устройства. При этом появляется сигнал на втором выходе распределителя 1 импульсов, который открывает соответствующую группу 6 элементов И, вследствие чего в регистр 4 результата перезаписывается число из регистра 2. Дальнейшая работа устройства аналогична рассмотренному выше.

После того, как устройство отработает и тактов, в запоминающем устройстве будет записан отсортированный массив чисел по адресу, заданному на входе !1 устройства.

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

Предлагаемое устройство обладает высоким быстродействием, так как для сортировки и чисел требуется и тактов работы. формула изобретения

Устройство для сортировки чисел, содержащее распределитель импульсов, п регистров, и схем сравнения, группы элементов И, счетчик, сумматор, регистр результата,, причем выходы каждого i-ro регистра, где

1,2,...,!>, соединены с информационными входами первой группы .

5 911513 6

i-ой схемы сравнения и i-ой группы сумматора, входы второй группы котоэлементов И, выходы которых подклю- рого соединены с входными шинами чены к входам i-ой группы регистра устройства, а выходы - с информационрезультата, а каждый i-ый выход рас- ными входами выходных элементов И пределителя импульсов соединен с s второй группы элементов; управляюуправляющим входом элементов И i-ой щие входы выходных элементов И пергруппы, о т л и ч а ю щ е е с я тем, вой и второй групп подключены к упчто, с целью повышения быстродей- равляющей шине устройства. ствия, выходы регистра результата подключены к информационным входам 10 Источники информации, второй группы всех схем сравнения и принятые во внимание при экспертизе к информационным входам первых выход-, 1. Авторское свидетельство СССР ных элементов И группы, выход каж- 11 263277, кл. С 06 Р 7/00, 1958. дой 1-ой схемы сравнения соединен с 2. Авторское свидетельство СССР.

i-ым входом счетчика, выходы которых <5 ?? 637810,????. g 06 f 7>

ВНИИПИ Заказ 1129/40 Тираж 732 Подписное филиал ППП "Патент", г..Ужгород, ул.Проектная,4