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

1 11

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

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

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

Для сортировки П чисел в описанном устройстве необходимо произвести запись в регистры, а затем вьшолнить Ц циклов, в каждом из которых выполняется In тактов (т-разрядность данных) .

Недостаток устройства - низкое

быстродействие.

I....

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

3622

первый вход управления записью ре- 1 гистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым 5 входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом устройства, группы 0 информационных входов каждой ячейки, кроме первой, соединены с группой выходов предьщущей ячейки а группа информационных входов первой ячейки является группой информацион5 ных входов устройства. Для сортировки чисел в устройстве необходимо выполнить 2) тактов. Для построения устройства необходимо 2 m регистров. In схем сравнения и HI коммутаторов 2, 0 Недостаток устройства - низкое быстродействие и большие затраты оборудования.

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

5 .

Указанная цель достигается тем,

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

к выходу схемы сравнения, выходы коммутатора 1 -го узла сравнения, где

1,2,..., (п1-2), соединены с установочными входами регистра (i+1)-ro

О узла сравнения, вход задания режима сортировки устройства подключен к управляющим входам схем сравнения всех узлов сравнения, введены входной и выходной регистры, два эле мента И и элемент НЕ, а в каждьй узел сравнения - элемент И, первый вход которого соединен с выходом схемы сравнения этого узла сравнения, а выход - с входом управления за0 писью регистра этого узла сравнения, вторые входы элементов И всех узлов сравнения подключены к входу тактовых импульсов устройства, подключенному также к входам управления за5 писью входного и выходного регистров, информационные входы устройства соединены с установочными входами входного регистра, выходы разрядов которого соединены с устйново ными входами регистра первого узла (Сравнения, информационными входами второй группы схем сравнения и ком мутаторов всех узлов сравнения, выходы коммутатора (П1-1)-го узла сравнения соединены с установочными входами выходного регистра, вход за дания режима сортировки устройства подключен к первому входу первого элемента И и через элемент НЕ к пер вому входу второго элемента И, вторые входы первого и второго элементов И подключены к шине начальной установки устройства, а вькоды - к входам установки соответственно в единичное и нулевое состояние регистров всех узлов сравнения. На чертеже представлена схема устройства. Устройство содержит информационные входы 1, вход 2 тактовьк импуль сов, вход 3 задания режима сортировки, шину 4 начальной установки, элемент НЕ 5, элементы И 6, и 7, входной регистр 8, выходной регист 9, (m-i) узлов 10 сравнения (тколичество ; сортируемых чисел), при чем каждьй узел 10 сравнения содержит элемент И 11, регистр 12 схему 13 сравнения, коммутатор 14, Устройство работает следующим образом. Перед началом сортировки уровнем сигнала на входе задания режима сортировки 3 выставляется режим сор тировки по возрастанию (логическая 1) или по убыванию (логический О Импульсом положительной полярности на входе 4 начальной установки реги ры 12 устройства устанавливаются в нуль (режим сортировки по убыванию) или все разряды регистров 12 в единицы (режим сортировки по возрас нию) . Сортируемая последовательност чисел с информационных входов 1 пос пает на входы регистра 8. В каждом такте работы в регистр 8 записывает одно из чисел этой последовательнос Информация с выхода регистра 8 пост пает на первые входы всех схем 13 сравнения, на вторые входы которых поступает информация с соответствую щих регистров 12. В режиме сортировки чисел по убы ванию при превышении содержимого регистра 8 над содержимым регистра 12 на выходе схемы 13 сравнения формируется сигнал логической 1, в других случаях сигнал логического О. При работе устройства в режиме сортировки чисел по возрастанию сигнал логической Г-на выходе схемы 13 сравнения формируется, когда содержимое регистра 12 превьш1ает содержимое регистра 8, в остальных случаях формируется сигнал логическо го О. Информация на выходе схемы 13 сравнения управляет коммутатором 14. Сигнал логической 1 на управляющем входе коммутатора 14 устанайливает его в положение, когда на его выход поступает информация с выходов регистра 12. Сигнал логического О на управляющем входе коммутатора 14 устанавливает его в положение, когда на его выход поступает информация с выходов регистра 8. Информация на выходе схемы 13 сравнения каждого узла 10 сравнения, разрешает (логическая 1) или запрещает (логический О) прохождение тактовых импульсов через элемент И 11на вход управления записью регист- ра 12. Рассмотрим работу устройства в ре- жиме сортировки чисел по убьгоанию. I По первому тактовому импульсу в регистр 8 записывается первое число, которое с его выхода поступает на первые входы всех схем 13 сравнения, на вторые входы которых поступает нуль. Если первое число не равно нулю, то на выходе всех схем 13 сравнения формируется сигнал логической 1. По второму тактовому импульсу в регистр 8 записывается второе число из сортируемого массива, в регистр 12первого узла 10 сравнения переписывается первое число из регистра 8, а в регистры 12 остальных узлов 10 сравнения и регистр 9 записывается информация с выходов коммутаторов 13, т.е. нули. Второе число сравнивается с содержимым регистра 12 каждого узла 10 сравнения и если второе число больше первого то на выходе всех схем 13 сравнения формируется сигиал логической 1. Если же второе число меньше первого, то на вьпсоде схемы 13сравнения первого узла 10 сравнения формируется сигнал логического О, а на выходе схем 10 сравнения формируется сигнал логической 1. По третьему тактовому импульсу происходит: запись третьего числа

511

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

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

23626

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

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

Время сортировки составляет T(m+iH тактов. Технико-экономический эффект заключается в повышении быстродействия устройства по сравнению с прототипом в два раза. Вьйгрьш по оборудованию в сравнении с прототипом составляет (1п-2) регистров. 2 J

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