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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее (т-1) узлов сравнения , где m - количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения , коммутатор и регистр, выходы разрядов которого соединены с информационными входами первой группы схемы сравнения и коммутатора, управляющий вход которого подключен к выходу схемы сравнения, выходы коммутатора i-ro узла сравнения, где ,2,... (т-2), соединены с установочными входами регистра (i+l)-ro узла сравнения , вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, отличающееся тем, что, с целью повышения быстродействия и упрощения устройства, в него введены входной и выходной регистры , два элемента И и элемент НЕ, а в каждый узел, сравнения - элемент И, первый вход которого соединен с выходом схемы сравнения этого узла сравнения, а выход - с входом управления записью регистра этрго узла сравнения, вторые входы элементов И всех узлов сравнения подключены к входу тактовых импульсов устройства подключенному также к входам управления записью входного и выходного регистров, информационные входы устройства соединены с установочными входами входного регистра, выходы разрядов которого соединены с установочными входами регистра первого узла сравнения, информационными входами второй группы схем сравне (Л ния и коммутаторов всех узлов сравнения , выходы коммутатора (m-l)-ro узла сравнения соединены с установоч8 ными входами вькодного регистра, вход задания режима сортировки устройства подключен к первому входу первого элемента И и через элемент НЕ - к первому входу второго элемента И, вторые входы первого Ю и второго элементов И подключены к : шине начальной установки устройства, 35 а выходы - к входам установки соотю ветственно в единичное и нулевое сое-, стояния регистров всех узлов сравнения.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (И) 2 А

3(51) "т 06 F 7/08

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ:

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3599666/ 18-24 (22) 03.06.83 (46) 07.09.84. Бюл.ВЗЗ (72) А.А.Мельник и И.Г.Цмоць (53) 681.325.66(088.8) (56) 1. Авторское свидетельство СССР

-928342, кл. С) 06 Г 7/06, 1982.

2. Авторское свидетельство СССР

И- 1007099, кл. G 06 F 7/08, 1981

{прототип). (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее (m-1) узлов сравнения, где m — количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с информационными входами первой группы схемы сравнения и коммутатора, управляющий вход которого подключен к выходу схемы сравнения, выходы коммутатора

i-ro узла сравнения, где i=1,2,... (m-2), соединены с установочными входами регистра (1+1)-го узла сравнения, вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и упрощения устройства, в него введены входной и выходной регистры, два элемента И и элемент

НЕ, а в каждый узел сравнения — элемент И, первый вход которого соединен с выходом схемы сравнения этого узла сравнения, а вькод - с входом управления записью регистра этого узла сравнения, вторые входы элементов И всех узлов сравнения подключены к входу тактовых импульсов устройства, подключенному также к входам управления записью входного и вькодного регистров, информационные входы устройства соединены с установочными входами входного регистра, выходы разрядов которого соединены с установочными входами регистра первого узла сравнения, информационными, ((1 входами второй группы схем сравнения и коммутаторов всех узлов сравнения, выходы коммутатора (m-1)"го узла сравнения соединены с установочными входами выходного регистра, вход задания режима сортировки устройства подключен к первому входу первого элемента И и через элемент НŠ— к первому входу второго элемента И, вторые входы первого и второго элементов И подключены к шине начальной установки устройства, а выходы — к входам установки соот} ветственно в единичное и нулевое сос-, стояния регистров всех узлов сравнения.

1112362

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

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

Известно устройство для сортиров.ки чисел, содержащее П регистров, и схем сравнения, регистр результата, распределитель импульсов, 11 элемен- 20 тов запрета, (tl+1) элементов И (1) .

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

Д циклов, .s каждом иэ которых выпол- 25 няется Ф тактов (й1-разрядность дан-ньм) .

Недостаток устройства — низкое быстродействие.

Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, со держащее 1П ячеек, где В -количество чисел в выходном множестве, причем каждая ячейка содержит элемент 35 сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр 40 результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационнов входов коммутатора,установоч- 45 ные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочными входами регистра результата и с второй 50 группой информационньм входов коммутатора, а выходы коммутатора являются выходами ячейки, входы установки приемного регистра и регистра ре-. зультата в исходное состояние соеди- 55 иены а входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом. устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группой выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства. Для сортировки чисел в устройстве необходимо выполнить 2щ тактов. Лля построения устройства необходимо 2 N регистров, 1д схем сравнения и й1 коммутаторов $2), Недостаток устройства — низкое быстродействие и большие затраты

1 . оборудования.

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

Укаэанная цель достигается тем, что в устройство для сортировки чисел, содержащее (В-1) узлов сравнения, где П1 — количество чисел сортируемого массива, причем каждый узел сравнения содержит схему сравнения, коммутатор и регистр, выходы разрядов которого соединены с информационными входами первой группы схемы сравнения и коммутатора, уп- . равляющий вход которого подключен к выходу схемы сравнения, выходы ком-! мутатора -го узла сравнения, где

=1,2,..., (e-2), соединены с уста" новочными входами регистра (i+ 1)"го узла сравнения, вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, введены входной и выходной регистры, два элемента И и элемент НЕ, а в каждый узел сравнения — элемент И, первый

I вход которого соединен с выходом схемы сравнения этого узла сравнения, а выход — с входом управления записью регистра этого узла сравнения, вторые входы элементов И всех узлов сравнения подключены к входу тактовых импульсов устройства, подключенному также к входам управления записью входного и выходного регистров, информационные входы устройства соединены с установочными входами входного регистра, вьмоды разз 111236 рядов которого соединены с установоч ными входами регистра первого узла

1сравнения, информационными входами, второй группы схем сравнения и ком:мутаторов всех узлов сравнения, выходы коммутатора (m-1)-ro узла сравнения соединены с установочными входами выходного регистра, вход задания режима сортировки устройства подключен к первому входу первого 10 элемента И и через элемент НЕ к первому входу второго элемента И, вторые входы первого и второго элементов И подключены к шине начальной установки устройства, а выходы — к входам установки соответственно в единичное и нулевое состояние регистров всех узлов сравнения.

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

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

9, (N-1) узлов 10 сравнения (Фколичество: сортируемых чисел), причем каждый узел 10 сравнения содер-жит элемент И 11, регистр 12 1 схему

13 сравнения, коммутатор 14, Устройство работает следующим образом.

Перед началом сортировки уровнем сигнала на входе задания режима

35 сортировки 3 выставляется режим сортировки по возрастанию (логическая

"1") или по убыванию (логический "0").

Импульсом положительной полярности на входе 4 начальной установки регист. ры 12 устройства устанавливаются в нуль (режим сортировки по убыванию) или все разряды регистров 12 в единицы (режим сортировки по возрастанию). Сортируемая последовательность 4 чисел с информационных входов 1 поступает на входы регистра 8. В каждом такте работы в регистр 8 записывается одно из чисел этой последовательности.

Информация с выхода регистра 8 посту50 пает на первые входы всех схем 13 сравнения, на вторые входы которых поступает информация с соответствующих регистров 12.

В режиме сортировки чисел по убы- 55 ванию при превышении содержимого регистра 8 над содержимым регистра

12 на выходе схемы 13 сравнения

2 4 формируется сигнал логической "1", в других случаях сигнал логического

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

13 сравнения формируется, когда содержимое регистра 12 превышает содержимое регистра 8, в остальных случаях формируется сигнал логическо" го "0". Информация на выходе схемы

13 сравнения управляет коммутатором

14. Сигнал логической "1" на управляющем входе коммутатора 14 устанавливает его в положение, когда на его выход поступает информация с выходов регистра 12. Сигнал логического "0" на управляющем входе коммутатора 14 устанавливает его в положение, когда . на его выход поступает информация с выходов регистра 8.

Информация на выходе схемы 13 сравнения каждого узла 10 сравнения, разрешает (логическая "1") или запрещает (логический "0") прохождение тактовых импульсов через элемент И

11 на вход управления записью регист-. ра 12.

Рассмотрим работу устройства в режиме сортировки чисел по убыванию.

По первому тактовому импульсу в регистр 8 записывается первое число, которое с его выхода поступает на первые входы всех схем 13 сравнения, на вторые входы которых поступает нуль. Если первое число не равно нулю, то на выходе всех схем 13 сравнения формируется сигнал логической "1".

По второму тактовому импульсу в регистр 8 записывается второе число из сортируемого массива, в регистр

12 первого узла 10 сравнения переписывается первое число из регистра

8, а в регистры 12 остальных узлов

10 сравнения и регистр 9 записывается информация с выходов коммутаторов 13, т.е. нули. Второе число сравнивается с содержимым регистра 12 каждого узла 10 сравнения и если второе число больше первого> то на выходе всех схем 13 сравнения формируется сигнал логической "1". Если же второе число меньше первого, то на выходе схемы

13 сравнения первого узла 10 сравнения формируется сигнал логического

"0", а на выходе схем 10 сравнения формируется сигнал логической "1".

По третьему тактовому импульсу происходит: запись третьего числа

Заказ 6460/34

Подписное из сортируемого массива в регистр 8, запись второго числа (для случая когда второе число больше первого) .в регистр 12 первого узла 10 сравнения, зались информации с выходов коммутаторов 14 предыдущих узлов

10 сравнения в регистры 12 последующих узлов 10 сравнения; запись информации с выхода коммутатора

14 последнего узла 10 сравнения в регистр 9.

Дальнейшая работа устройства в данном режиме будет проходить аналогично. После поступления (m+ 1) импульсов числа массива будут просортированы в порядке убывания

12362 d (наибольшее число будет в регистре

12 первого узла 10 сравнения, следующее число по величине в регистре 12 второго узла 10 сравнения и т.д., наименьшее в регистре 9) .

Работа устройства в режиме сортировки по возрастанию аналогична работе устройства в режиме сортировки чисел по убыванию.

1О Время сортировки составляет Т-(fhe1)t тактов. Технико-экономический эффект заключается в повышении быстродействия устройства по сравнению с прототипом в два раза. Выигрыш по оборудо15 ванию в сравнении с прототипом составляет (e-2) регистров.

2 Л

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4