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

СООЗ СОВЕТСНИХСВЮЛИОьеПикЕСПУБЛИН 19) 01 ИСАНИЕ ИЗОБРЕТЕНИЯ ТОРСИО ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬТИ(56) 1. Авторское свидетельство СССР Р 826339, кл. 6 06 Р 7/06, 1979.2. Авторское свидетельство СССР У 1007099, кл. С 06 Р 708, 1981 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее Н ячеек анализа, где Ы - количество сортируемых чисел, причем каждая ячейка анализа содержит . схему сравнения и регистр, выходы разрядов которого соединены с входа" ми первой группы схемы сравнения,3-я ячейка анализа, где 1=2,301 содержит коммутатор, о т л и ч а ю - щ е е с я тем, что, с целью повышения его быстродействия, в .него введен элемент задержки, в х-ю ячейку анализа, где х=2,3Ж - элемент И записи в первую ячейку анализа - вход ные элементы И, в 3-ю ячейку анализа - элемент И переписи и элементы задержки, причем инфорйационные входы устройства соединены с соответствующими входами второй группы схемы сравнения 1.-й ячейки анализа, с инфор мационными входами первой группы коммутатора, 1-й ячейки анализа и информационными входамн соответствую щих входных элементов И первой ячейки анализа, выходы которых подключены к установочным входам регистра, первой ячейки анализа, вход окончанияприема числа устройства подключен кпервому входу элемента И переписи)-й ячейки анализа и через элемент,задержки к первому входу элемента Изаписи ).-, й ячейки анализа, второйвход которого соединен с выходом превышения первого числа схемы сравне-,ния той же ячейки анализа, выходпревы"ения первого числа схемы срав-.нения -й ячейки анализа, где с = 4,2(Б), подключен также к вто 1 рому входу элемента Ипереписи +1) -йячейки анализа, вход которого соединен с входом управления переписью коммутатора этой ячейки анализа, выходыкоторого соединены с установочнымивходами регистра данной ячейки анализа, а информационные входы второйгруппы через элементы задержки подключены к выходам разрядов регистрак-й ячейки анализа, выход равенст-.ва чисел и превьппения второго числасхемы сравнения к-й ячейки анализасоединен с третьим входом элементаИ записи (к+1)-й ячейки анализа,выход которого подключен к входу управления записью коммутатора этойячейки анализа, выход элемента И .записи в первой ячейке анализа соединен с управляющими .входами входныхэлементов И.Изобретение относится к автоматикеи вычислительной технике и может бытьиспользовано при реализации технических средств ЭВМ и создании устройств обработки статистической ийформации.Известно устройство для сортировки чисел, содержащее кольцевые регистры, управляющие элементы И-ИЛИ, дешифраторы счетчики, элементы И, ИЛИ, регистр и узел синхронизации 11 ОНедостатком данного устройства является низкое быстродействие, обус - ловленное тем, чтосортировка М чисел осуществляется за И /2 тактов.Наиболее близким по технической 15Сущности к предложенному является устройство для сортировки чисел, состоящее из ш ячеек, где ш - количество чисел в выходном множестве, причем каждая ячейка содержит. эле О мент сравнения, коммутатор, регистр результата и приемный регистр, выходы разрядов которого соединены с Первой группой информационных входов элемента сравнения, выходы ре гистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов коммутатора, установочные входы приемного регистра являются информационными входами ячейки, выходы разрядов приемного регистра соединены с установочными входами регистра результата и с второй группой информационных входов коммутатора, а выходы коммутатора являются выходами ячейки, входы установки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения с управляющим входом устройства,50 группы информационных входов каждой чейки, кроме первой, соединены сруппой выходов предыдущей. ячейки а группа информационных входов первой ячейки является группой информацион ных. входов устройства 1.22. Недостатком известного устройстваявляется низкое быстродействие,так как оно позволяет провести сортировку ш чисел за 2 ш тактов.Цель изобретения - повышение быстродействия работы устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее Я ячеек анализа, где И - количество сортируемьсс чисел, причем каждая ячейка анализа содержит схему сравнения и регистр, выходы разрядов которого соединены с входами первой группы схемы сравнения, 1-я ячейка анализа, где 1=2,Э,Б, содержит коммутатор, введен элемент задержки, в а-ю ячейку анализа, где х= 1,2,М, , - элемент И записи, в первую ячейку анализа - входные элементы И, з 1-ю ячейку анализа элемент И переписи и элементы задержки,. причем информационные входы устройства соединены с соответствующими входами второй группы схемы сравнения -й ячейки анализа, с инфор мационными входами первой группы коммутатора 1-й ячейки анализа и информационными входами соответствующих входных элементов И первой ячейки анализа, выходы которых подключены к установочным входам регистра первой ячейки анализа, вход скончания приема числа устройства подключен к первому входу элемента И переписи 1-й ячейки анализа и через элемент задержки к первому входу элемента И записи-Й ячейки анализа, второй вход которого соединен с выходом превышения первого. числа схемы сравнения той же ячейки анализа, выход превышения первого числа схемы сравнения 1(-й ячейки анализа,где 1=1, 2, ,Х) подключены также к второму входу элемента И переписи Ь+ 1) -й ячейки анализа, выход которого соединен с входом управления переписью коммутатора этой ячейки анализа, выходы которого соединены с установочными входами регистра данной ячейки анализа, а информационные входы второй группы через элементы задержки подключены к выходам разрядов регистра Е-й ячейки анализа, выход равенства чис ел и превышение второго числа схемь 1 сраьнения к Й ячейки анализа с оединен с третьим входом элемента И записи Ь) -й ячейки анализа, выход которого подключен к входу управления за:исью коммутатора этой ячейки анализа, выход элемента И записи вЭ 11203 первой ячейке анализа соединен с управляющими входами входных элементов И.На чертеже представлена блок-схема устройства для сортировки чисел.Устройство содержит М регистров 1, М схем 2 сравнения, М элементов И 3 записи, Мэлементов И 4 переписи, элементы И 5, М групп элементов И-ИЛИ 6, Мгрупп элементов 7 за - держки, информационный вход 8 устройства и вход 9 окончания приема очеред. ного числа.Сущность работы устройства заключается в том, что при поступлении на информационный вход 8 устройства очередного числа в регистрах 1, хранящих числа меньшие поступившего, осуществляется перезапись из ш-го регистра в (ш+1)-й, а поступившее число записывается в первый освободившийся в результате сдвига информации регистр 1, в результате чего поступающие на информационный вход 8 устройства числа располагаются в регистрах 1 в порядке убывания (невозрастания) .В исходном состоянии регистры 1 установлены в состояние "О".30Для удобства описания работы устройства рассмотрим поступление на его информационный вход 8 следующих одно за другим чисел х=9, х,=7, х,=7, х =11, охватывающих все возможные случаи соотношений как значений, так и последовательности их по- З 5 ступления на вход устройства.При приходе на информационный вход 8 первого числа х(х,=9) и его поступлении на первые входы схем 2 сравнения вследствие подачи на вто- ф рые входы схем 2 сравнения нулевых ко дов с выходов регистров 1 на первых выходах всех схем 2 сравнения появляется разрешающий потенциал, который подается на первые входы всех элементов И 3 и 4 соответственно записи и переписи. С второго выхода каждой 1-й схемы 2 сравнения (1=1,2М) на третьи входы (д+1) -го элемента И 3 записи подается запрещающий потенциал. Поступивший на вход 9 устройства сигнал окончания приема очередного числа через элементы И 4 сдвига подается на четвертые входы элементов И-ИЛИ 6, осуществляя перепись содер жимого д-го регистра 1 в (1+1) -й. Этот же сигнал, задержанный элементом 5, пройдя через первый элемент 14 4И 3 записи, открывает первую группу элементов И-ИЛИ 6, осуществляя запись первого числа х в первый регистр 1.При поступлении на вход 8 устройства второго числа (х,=7) на первом выходе каждой 3-й схемы 2 сравнения (3=2,3М) и на втором выходе первой схемы сравнения присутствуют разрешающие потенциалы. Поступивший на вход устройства 9 сигнал окончания приема очередного числа проходит че- рез 1-е элементы И 4 переписи (1 с= .2,3М), осуществляя перезапись содержимого к-го регистра 1 в (к+1) -й Этот же сигнал, задержанный элементом 5, поступает на вторые входы элементов И 3 записи, при этом только второй элемент И 3 записи открыт, и по- . ступившее на информационный вход 8 число (х,=7) записывается через вторую группу элементов И-ИЛИ 6 во второй регистр 1.При поступлении на информационный вход 8 устройства третьего числа (х, =7) на вторых входах первой и второй схем 2 сравнения на первых входах остальных схем. 2 сравнения появляется разрушающий потенциал, обеспе чивающий при поступлении на вход 9 устройства сигнала окончания приема числа запись поступившего очередного числа х, в третий регистр.При приходе на информационный вход 8 устройства четвертого числа (х =11) и его поступления на первые входы схем 2 сравнения кодов, меньших кода поступившего числа х, на первых выходах: всех схем 2 сравнения появляется разрешающий потенциал, который подается на первые входы соответствующих элементов записи и сдвига. С второго выхода каждой д-й схемы сравнения (=1,2М) на третьи входы (1+1) -го элемента И 3 записи подается запрещающий потенциал, Поступивший на вход 9 устройства сигнал окончания приема очередного числа проходит через элементы И 4 сдвига на четвертые входы элементов И-ИЛИ 6, осуществляя перепись содержимого -го регистра 1 в (д+1) -й. Этот же сигнал, задержанный элементом 5, лрой" дя первый элемент И 3 записи, открывает первую группу элементов И-ИЛИ 6, осуществляя запись четвертого чйсла х в первый регистр 1. В результате рассмотренных процессов в первом регистре 1 записано максимальное из чисел, поступивших на информационныйажйа .д ю 4 В 4 Ш Ю ВНИИПИ Зак з 7742/35 .Гщал 698 Ьуйс,ше Фюжае ППП беат, й.Ужйоредэ ;т,.Преажтвйб вход 8 устройства, т.е. число 1 вовторой - число 9 в третьем и четвертом - число 7. Далее устройствоработает аналогично. 5Таким образом, поступающие на инФормационный вход 8 устройства числа записываются и запоминаются в регистрах 1 в порядке убывания (невозрастания). Если необходимо записать числа в порядке возрастания (неубывания), достаточно поменять выходы схемы 2 сравнения или подавать на схему 2 сравнения числа в обратном коде. КромЕ того, данное устройство может быть 15 Ипользовано в качестве устройства дпя определения экстремальных чисел. Предлагаемое устройство обладает большим быстродействием, чем извест ное, в нем каждое поступающее на вход устройство число одновременно сравнивается с числами, записанными в запоминающих регистрах, и осуществляется одновременный сдвиг в запись числа, поступившего на вход устройства. Для упорядочения чисел массива в известном устройстве требуется М /2 тактов работы, тогда как предлагаемое устройство обеспечивает сортировку чисел за Н тактов работы. Кроме того, предлагаемое устройство обеспечивает сортировку чисел при их поступлении на вход устрой ства в режиме реального времени, что расширяет область его применения.