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

111 Изобретение относится к автоматик и вычислительной технике и может быт использовано при реализации техничес ких средств ЭВМ и создании устройств обработки статистической ийформации. Известно устройство для сортировки чисел, содержащее кольцевые ре гистры, управляющие элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр и узел синхронизации fl Недостатком данного устройства является низкое быстродействие, обус ловленное тем, что сортировка N чисел осуществляется з-а N /2 тактов. I Наиболее близким по технической Сущности к предложенному является устройство для сортировки чиселл сос тоящее из m ячеек, где га - количество чисел в выходном множествеj причем каждая ячейка содержит, элемент сравнения, коммутатор, регистр результата и приемный регистр, выходы разрядов которого соединены с цервой группой информационных входов элемента сравнения, выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой Информационных входов коммутатора, установочные входы приемного регистра являются информационными входами ячейки, разрядов приемного ре гистра соединены с установочными входами регистра результата и с второй группой информационных входов коммутатора, а выходы коммутатора яв ляются выходами ячейки, входы устано ки приемного регистра и регистра результата в исходное состояние соедин ны с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с входом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом у равления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения с управляющим входом устройства группы информационных входов каждой ячейки, кроме первой, соединены с Группой выходов предьщущей ячейкие. а группа информационных входов перво ячейки является группой информационных, входов уст,ройства С 2 , , Недостатком известного устройства является низкое быстродействие. 42 так как оно позволяет провести сортировку m чисел за 2т тактов. Цель изобретения - повьшение быстродействия работы устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее N ячеек анализа, где N - количество сортируемых чисел, причем каждая ячейка анализа содержит схему сравнения и регистр, вькоды разрядов которого соединены с входами первой группы схемы сравнения, j-я ячейка анализау где .,.Nj содержит коммутатор, введен элемент задержки, в i-K) ячейку анализа2 где ,,25 .,,jN5 - элемент И записи, в первую ячейку анализа - входные элементы И в j-ю ячейку анализа элемент И переписи и элементы задержКИ5 причем информационные входы устройства соединены с соответствующими входами второй группы cxei-ibi сравнения i-й ячейки анализа с инфор мационныг-ш входами первой группы KOMviyTaTopa j-й ячейки анализа и информационными входами соответствующих входных элементов И первой ячейки анализа выходы которых подключены к установочным входам регистра первой ячейки анализа;, вход окончания приема числа устройства подключен к первому входу элемента И переписи j-й ячейки анализа и через элемент задержки к первому входу элемента И записи i-й ячейки анализа, второй вход которого соединен с вьрсодом превышения первого числа схемы сравнения той же ячейки анализа, выход превышения первого числа схемы сравнения k-й ячейки анализа где ,25,.,s(N-1) подключены также к второму входу элемента И переписи ()-й ячейки анализа, выход которого соединен с входом управле -здя переписью коммутатора этой ячейки анализа, выходы которого соединены с установочными входами регистра данной ячейки анализа; а информационные входы второй группы через элементы задержки подключены к вьжодам разрядов регистра k-й ячейки анализа; вькод равенства чисел к превышеш-ге зтсрого числа схемы сравнения ячейки анализа соединен с третьим входом злемента И записи ()--й ячейки анал1-гзаэ выкоц которого подключен к входу управления записыо коммутатора этой ячейки аналг- за., вькод элемента И записи в 311 первой ячейке анализа соединен с управляющими входами входных элементов И.. На чертеже представлена блок-схема устройства для сортировки чисел. Устройство содержит N регистров 1 N схем 2 сравнения, N элементов И 3 записи, N-1 злементов И 4 переписи, злементы И 5, N групп злементов И-ИЛИ 6, N-1 групп злементов 7 задержки, информационный вход 8 устрой ства и вход 9 окончания приема очере ного числа. Сущность работы устройства заключается в том, что при поступлении на информахщонный вход 8 устройства оче редного числа в регистрах 1, хранящих числа меньшие поступившего, осуществляется перезапись из т-го регистра в (т+1)-й, а поступившее число записывается в первый освободившийся в результате сдвига информации регистр 1, в результате чего поступакнцие на информационный вход 8 устройства числа располагаются в регистрах 1 в порядке убывания (невозрастания) . В исходном состоянии регистры 1 установлены в состояние О. Для удобства описания работы устройства рассмотрим поступление на его информационный вход 8 следующих одно за другим чисел , , , , охватываюш11х все возможные случаи соотношений как значений, так и последовательности их поступления на вход устройства. При приходе на информационный вход 8 первого числа х() и его поступлении на первые входы схем 2 сравнения вследствие подачи на вторые входы схем 2 сравнения нулевых к дев с выходов регистров 1 на первых вьгходах всех схем 2 сравнения появля ется разрешающий потенциал, который подается на первые входы всех элементов И 3 и 4 соответственно записи и переписи. С второго выхода каждой i-й схемы 2 сравнения (,2,...,N-1 на третьи входы (i+1)-ro элемента И 3 записи подается запрещающий потенциал.Поступивший на вход 9 устройства сигнал окончания приема очередного числа через элементы И 4 сдвига подается на четвертые входы элементо И-ИЛИ 6, осуществляя перепись содержимого i-ro регистра 1 в (1+1)-й. Этот же сигнал, задержанный элементом 5, пройдя через первый элемент 4 И 3 записи, открывает первую пруппу элементов И-ИПИ 6, осушествляя запись первого числа х в первый регистр 1. При поступлении на вход 8 устройства второго числа () на первом вькоде каждой j-й схемы 2 сравнения ,3,...,N) и на втором выходе первой схемы сравнения присутствуют разрешающие потенциалы. Поступивший на вход устройства 9 сигнал окончания приема очередного числа проходит через k-e злементы И 4 переписи (k 2, 3, . . . ,N-1), осуществля-я перезапись содержимого k-ro регистра 1 в ( с+О-й Этот же сигнал, задержанный элементом 5,поступает на вторые входы злементов И 3 записи, при этом только второй элемент И 3 записи открыт, и по- . ступившее на информационный вход 8 число () записывается через вторую группу элементов И-ИЛИ 6 во второй регистр 1. При поступлении на информационный вход 8 устройства третьего числа () на вторых входах первой и второй схем 2 сравнения на первых входах остальных схем.2 сравнения появляется разрушающий потенциал, обеспе чивакхдий при поступлении на вход 9 устройства сигнала окончания приема числа запись поступившего очередного числа Xj в третий регистр. При приходе на информационный вход 8 устройства четвертого числа ()и его поступления на первые входы схем 2 сравнения кодов, меньших кода поступившего числа х, на первых выходах: всех схем 2 сравнения появляется разрешающий потенциал, которьй подается на первые входы соответствующих элементов записи и сдвига. С второго вьсхода каждой i-й схемы сравнения (,2,,..,N-1) на третьи входы (1+1)-го элемента И 3 записи подается запрещающий потенциал. Поступивший на вход 9 устройства сигнал окончания приема очередного числа проходит через элементы Н 4 сдвига на четвертые входы элементов И-ИЛИ 6, осуществляя перепись содержимого i-ro регистра 1 в (1+1)-й. Этот же сигнал, задержанный элементом 5, лройдя первый элемент И 3 записи, открывает первую группу элементов И-ИЛИ 6,осуществляя запись четвертого числа X в первый регистр 1. В результате рассмотренных процессов в первом регистре 1 записано максимальное из чисел, поступивших на информационный

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