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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее N ячеек анализа, где N - количество сортируемых чисел, причем каждая ячейка анализа содержит схему сравнения и регистр, вькоды разрядов которого соединены с входами первой группы схемы сравнения, j-я ячейка анализа, где ,3,...,N, содержит коммутатор, отличающееся тем, что, с целью повьшения его быстродействия, в «его введен элемент задержки,.в i-ю ячейку анализа , где ,3,...М - элемент И записи в первую ячейку анализа - входные элементы И, в j-ю ячейку анализа - элемент И переписи и элементы задержки, причем информационные входы устройства соединены с соответствующими входами второй группы схемы сравнения i-й ячейки анализаj с информационными входами первой группы коммутатора, j-й ячейки анализа и информационными входами соответствующих входных Элементов И первой ячейки анализа, выходы которых подключены к установочным входам регистра , первой ячейки анализа, вход окончания приема числа устройства подключен к первому входу элемента И переписи j-й ячейки анализа и через элемент. задержки к первому входу элемента И записи 1гй ячейки анализа, второй вход fcoToporo соединен с выходом пребышення первого числа схемы сравнения той же ячейки анализа, выход превы -ения первого числа схемы срав нения k-й ячейки анализа, где k 21,2, . ,., (N-1), подключен также к вто рому входу элемента Ипереписи (с+1)-й. ячейки анализа, вход которого соединен с входом управления переписью ком мутаторй этой ячейки анализа, выходы которого соединены с установочными входами регистра данной ячейки анализа , а информационные входы второй группы через элементы задержки подключены к выходам разрядов регистра lk-й ячейки анализа, выход равенст-г ва чисел и превьшения второго числа схемы сравнения ячейки анализа соединен с третьим входом элемента И записи (к+1)-й ячейки анализа, выход которого подключен к входу управления записью коммутатора этой ячейки анализа, элемента И записи в первой ячейке анализа соединен с управляющими -вход ьш входных элементов И.

СООЗ СОВЕТСНИХ

ВИЛ М

РЕСПУБЛИК

А (19) 01), зсю 6 F

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

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

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

Н AB TDP|:ATOMY СИИДЕТОЪСТВ)Г (21) 3563954/18-24 (22) 11.03.83 (46) 23.10.84. Бюл. 1Ô 39 (72) Н.И.Крылов и В.В.Соколов (53) 681.325.66(088.8) (56) 1. Авторское свидетельство СССР

Р 826339, кл. 6 06 F 7/06, 1979.

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

У 1007099, кл. С 06 F 7/08, 1981 (прототип). (54)(57) УстРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее Н ячеек анализа, где Ы вЂ” количество сортируемых чисел, причем каждая ячейка анализа содержит . схему сравнения и регистр, выходы разрядов которого соединены с входами первой группы схемы сравнения, 3-я ячейка анализа, где =2,3,...,И, содержит коммутатор, о т л и ч а ю— щ е е с я тем, что, с целью повьппения его быстродействия, в -него введен элемент задержки, в i-ю ячейку анализа, где х=2,3,...,Ж вЂ” элемент И записи в первую ячейку анализа — входные элементы И, в j-ю ячейку анализа — элемент И переписи и элементы задержки, причем информационные входы устройства соединены с соответствующими входами второй группы схемы сравнения i-й ячейки анализа, с информационными входами aeysoO группы коммутатора, j -й ячейки анализа и информационными входамн соответствую щих входных элементов И первой ячейки анализа, выходы которых подключены к установочным входам регистра, первой ячейки анализа, вход окончания .М приема числа устройства подключен к первому входу элемента И переписи

j -й ячейки анализа и через элемент, задержки к первому входу элемента И записи i-, é ячейки анализа, второй вход которого соединен с выходом превышения первого числа схемы сравне- . ния той же ячейки анализа, выход превы" ения первого числа схемы сравнения k-й ячейки анализа, где k =

4,2,...,(N-1), подключен также к вто рому входу элемента И переписи (%+1) -й ячейки анализа, вход которого соединен с входом управления переписью ком мутатора этой ячейки анализа, выходы которого соединены с установочными входами регистра данной ячейки анализа, а информационные входы второй группы через элементы задержки подключены к выходам разрядов регистра

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

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

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

Известно устройство для сортировки чисел, содержащее кольцевые peFHcTpb1> управляющие элементы И-ИЛИ, дешифраторы„ счетчики, элементы И, ИЛИ, регистр и узел синхрониз" öèè (1)1О

Недостатком данного устройства является низкое быстродействие, обус— ловленное тем, что сортировка М чисел осуществляется за И /2 тактов.

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

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

35 коммутатора, а выходы коммутатора являются выходами ячейки, входы установки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения с управляющим входом устройства, 50 группы информационных входов каждой чейки, кроме первой, соединены с руппой выходов предыдущей ячейки„ а группа информационных axopos первой ячейки является группой информацион-ГC ных входов устройства 23.

Недостатком известного устройства является низкое быстродействие, так KBK оно позволяет провести сортировку m чисел за 2m тактов.

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

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее N ячеек анализа, где

N — количество сортируемья чисел, причем каждая ячейка анализа содержит схему сравнения и регистр, выходы разрядов которого соединены с входами первой группы схемы сравнения, j ÿ ячейка анализа, где j=2,3, N, содержит коммутатор, введен элемент задержки, в i-н> ячейку анагп за, где

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

j-й ячейки анализа и через элемент задержки к первому входу элемента И записи 1-й ячейки анализа, второй вход которого соединен с выходом превышения первого. числа схемы сравнения той же ячейки анализа, выход превышения первого числа схемы сравнения

1<-й ячейки анализа,где 1=1,2,...,(N-1) подключены также к второму входу элемента И переписи (1+ 1) -й ячейки анализа, выход которого соединен с входом управле. -.мя переписью коммутатора этой ячейки анализа, выходы которого соединены с установочными входамн регис-ра данной ячейки анализа, а информационные входы второй группы через элементы задержки подключены к выходам разрядов регистра k-й ячейки анализа, выход равенства чи< ел н

-ipeabaaem e э ropor О числа схемы сра» нения к и ячейки анализа с оединен с третьим входом элемента И записи (1<+1)-й ячейки анализа, выход котоРого поту<лючен к входу управления за исью коммутатора этой ячейки анализа, вью<од элемента И за-.иси в

Э 11203 первой ячейке анализа соединен с управляющими входами входных элементов

И.

На чертеже представлена блок-схема устройства для сортировки чисел.

Устройство содержит N регистров 1, Nсхем 2 сравнения,,N элементов И

3 записи, N- 1 элементов И 4 переписи, элементы И 5, N групп элементов

И-ИЛИ 6, N-1 групп элементов 7 за— держки, информационный вход 8 устройства и вход 9 окончания приема очередного числа.

Сущность работы устройства заключается в том, что при поступлении на информационный вход 8 устройства очередного числа в регистрах 1, хранящих числа меньшие поступившего, осуществляется перезапись из m-го регистра в (ш+1) -й, а поступившее число записывается в первый освободившийся в результате сдвига информации регистр 1, в результате чего поступающие на информационный вход 8 устройства числа располагаются в регистрах 1 в порядке убывания (невозрастания) .

В исходном состоянии регистры 1 установлены в состояние "0".

Для удобства описания работы устройства рассмотрим поступление на его информационный вход 8 следующих одно за другим чисел х„=9, х, =7, х,=7, х+=11, охватывающих все возможные случаи соотношений как значений, так и последовательности их поI ступления на вход устройства.

При приходе на информационный вход 8 первого числа х„(х,=9) и его поступлении на первые входы схем 2 сравнения вследствие подачи на вторые входы схем 2 сравнения нулевых ко дов с выходов регистров 1 на первых выходах всех схем 2 сравнения появляется разрешающий потенциал, который подается на первые входы всех элементов И 3 и 4 соответственно записи и переписи. С второго выхода каждой

i-й схемы 2 сравнения (i=1,2,...,N-1) на третьи входы (i+1) -го элемента И

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

И-ИЛИ 6, осуществляя перепись содер- 55 жимого i-го регистра 1 в (i+1) -й.

Этот же сигнал, задержанный элементом 5, пройдя через первый элемент

14 4

И 3 записи, открывает первую группу элементов И-ИЛИ 6, осушествляя запись первого числа х в первый регистр 1.

При поступлении на вход 8 устройства второго числа (х,=7)»a первом выходе каждой j-й схемы 2 сравнения (j=2,3,...,N) и на втором выходе первой схемы сравнения присутствуют разрешающие потенциалы. Поступивший на вход ус тр ойс тва 9 сиг нал оконча ния приема очередного числа проходит че- рез k-e элементы И 4 переписи (k= .2,3,...,N-1), осуществляя перезапись содержимого к-го регистра 1 в (к+1) -й

Этот же сигнал, задержанный элементом

5, поступает на вторые входы элементов И 3 записи, при этом только второй элемент И 3 записи открыт, и по- . ступившее на информационный вход 8 число (x2=7) записывается через вторую группу элементов И-ИЛИ 6 во второй регистр 1.

При поступлении на информационный вход 8 устройства третьего числа (х,=7) на вторых входах первой и второй схем 2 сравнения на первых входах остальных схем. 2 сравнения появляется разрушающий потенциал, обеспе чивающий при поступлении на вход 9 устройства сигнала окончания приема числа запись поступившего очередного числа х, в третий регистр.

При приходе на информационный вход 8 устройства четвертого числа (х =11) и его поступления на первые входы схем 2 сравнения кодов, меньших кода поступившего числа х, на первых выходах: всех схем 2 сравнения появляется разрешающий потенциал, который подается на первые входы соответствующих элементов записи и сдвига. С второго выхода каждой i-й схемы сравнения (i=t,2,...,N-1) на третьи входы (i+1) -го элемента И 3 записи подается запрещающий потенциал. Поступивший на вход 9 устройства сигнал окончания приема очередного числа проходит через элементы И 4 сдвига на четвертые входы элементов И-ИЛИ 6, осуществляя перепись содержимого

i-ro регистра 1 в (i+1) -й. Этот же сигнал, задержанный элементом 5, лройдя первый элемент И 3 записи, открывает первую группу элементов И-ИЛИ

6, осуществляя запись четвертого чйсла х в первый регистр 1. В результате рассмотренных процессов в первом регистре 1 записано максимальное из чисел, поступивших на информационный

112031ч ВНИИПИ Зак з 7742/35 .Ьц ал,698 Жщлйаж

Фюжаа ППП беат, з 7m pep, ;:т,.Проектам, 4 вход 8 устройства, т.е. число 11„во второй — число 9, в третьем и четвертом — число 7. Далее устройство работает аналогично.

Таким образом, поступающие на информационный вход 8 устройства числа записываются и запоминаются в регистрах 1 в порядке убывания (невозрастания). Если необходимо записать числа в порядке возрастания (неубывания), достаточно поменять выходы схемы 2 сравнения или подавать на схему 2 сравнения числа в обратном коде. КромЕ того, данное устройство может быть 15

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

Предлагаемое устройство обладает большим быстродействием, чем извест ное, в нем каждое поступающее на вход устройство число одновременно сравнивается с числами, записанными в запоминающих регистрах, и осуществляется одновременный сдвиг в запись числа, поступившего на вход устройства. Для упорядочения чисел массива в известном устройстве .требуется М /2 тактов работы, .тогда как предлагаемое устройство обеспечивает сортировку чисел за Н тактов работы. Кроме того, предлагаемое устройство обеспечивает сортировку чисел при их поступлении на вход устрой ства в режиме реального времени, что расширяе".област.ь его применения.