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

(54 j УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

Известно устройство для сс тировки информации, cojq pmaiqee элементы памяти f cxeva. сравне(я и мажоритарный элемент, в котором использованы программные методы сортировки .l . ,

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

Известно устройство для сортировки mn-разрядных чисел,, содержащее пи регистров, регистр результата, m схем сравнения, коммутатор, m узлов запрета, триггер,-элементы И, ИЛИ, переключатели С2 ji

Недостатком этого устройства является его сложность, обусловленная во-первых, большим количеством таких элементов как схемы сравнения, узлы запрета, коммутатор; во-вторых, наличием большого Числа межэлементных связей (только регистр результата связан со входами m схем сравнения )ji

в-третьих, множеством управляющих шин, что требует специального устроил ства управления.

близким к предлагаемому является устройство для сортировки, mn-разрядных чисел, содержащее регистры, элементы И и НЕ, элемент равнозначности, две группы элементов И,схему сравнения группу элементов ИЛИ, причем олходы регистра результата соединешл с входами п вой группы -схемы, сравнения, вваход которой подключен к первому входу элемента равнозначности, выход которого соеда1нен с перклм входом элемента И, выход которого соедийен с входом упргшления регистра результата, выходы каждого i-го регистра, где i 1, 2,..., Im-l), соединены .с входами (1 + 1)-го регистра выходы т-го регистра соединены с входами регистра результатгъ, выходы которого соединены с информационными входамя элe 4eнтoв И первой группы, выход кгикдого J-ro из которых соединен с первым входом J-го элемента ИЛИ группы, тде J 1, 2,....п, выход каждого из которых соединен со вхоЯ хл J-ro разряда первого регистра, выходы т-го регистра соединены с входами второй группы схем сравнения и с информацрСонными входами эле ментов И второй группы, выход каждо го J-го из которых соединен с вторым входом j-ro элемента ИЛИ группы выход элемента равнозначности соеди нен с управляюгцими входами элементов И первой группы и через элемент НЕ с управляющими входами элементов второй группы- t.3 3. Недостатки данного устройства сос тоят в сложности и недостаточной Надежности. . . Цель изобретения - упрсядение устройства и повышение надежности. Поставленная цель-достигается тем, что устройство, содержащее груп пу элементов И, входной элемент И, содержит счетчики, выходной счетчик, элементы ИЛИ, дифференциру нзщие элементы, запрещающие элементы И, причем выходы счетчиковпоразрядно сое динены с входами соответствующих эле ментов ИЛИ, выходы которых соединены с входами соответствующих дифференцирующих элементов, первыми входами соответствующих запрещающих элементо И и соответствующими входами первого элемента ИЛИ, выходы дифференцирующих элементов соединены с соответ ствующими входами второго элемента ИЛИ, выход которого соединен с первыми входами элементов И группы, выходы которых являются выходами устройства, выход первого элемента ИЛИ соединен с первым входом входного элемента И, второй вход которого сое динен с входом тактовых импульсов устройства, выход входного элемента И соединен с вторыми входайи запрещающих элементов И и суммирующим входом выходного счетчика, выходы запрещающих элементов И соединены с вычитающими входами соответствующих счетчиков, выходы выходного счетчика поразрядно соединены с вторыми входами элементов И группы. На чертеже представлена схема уст ройства. Устройство содержит счетчики 1, выходной счетчик 2, элементы ИЛИ 3 5, запрещающие элементы И б, входной элемент И 7, группу элементов И 8, дифференцирукяцие элементы 9, вход 1й тактовых импульсов устройства, выход 11 устройства. Устройство работает следуквдим образом. В регистры 1 r-l заносятся исходные чи.сла, выходной счетчик 2 на ходится в нулевс5м состоянии. На выходах элементов ИЛИ 3 высокие потенциалы, так как содержимое счетчиков l;j-1 не равно -О, и следовательно элементы И б и 7 открыты. На вход 10 подаются тактовые импульсы, которые через открытый элемент И 7 поступают на суммирующий вход выход ного счетчика 2 и через элементы И 6 на вычитающие входы счетчиков 1. При этом содержимое счетчиков 1 уменьшается, а выходного счетчика 2 увеличивается. Когда на вход устройства поступит количество тактовых импульсов, .соответствующее значению минимального числа из чисел, записанных в счетчиках 1, содержимое счетчика (где i l,2,,..,m), в которрм записано минимальное число, станет равным О. На выходе соответствующего элемента ИЛИ 3 низкий потенциал, закрывакздий элемент И 6г и, следовательно, вход регистра 1, а на выходе дифференцирующего элемента 9 , появляется импульс, который через элемент ИЛИ 5 открывает элементы И 8 и содержимое выходного счетчика 2, равное минимальному числу, поступает на выход 11 устройства. Когда во всех счетчиках 1 будет О, то на выходах всех элементов ИЛИ будут низкие потенциалы, закрывающие элемент И 7 через элемент ИЛИ 4 Тактовые импульсы на входы счетчиков 1 и 2 не поступают. Работа устройства окончена. Таким образом, значения чисел, записанных в счетчиках 1, поочередно, начиная с минимального, поступают на выход 11 устройства. Для того, чтобы провести сортировку чисел, начиная с максимального числа, достаточно записать числа в счетчики 1 в обратном коде и результат получать с нулевых выходов счетчика 2. В целом работа устройства не меняется. Технико-экономический эффект предлагаемого устройства по сравнению с базовый объектом состоит в упрощении устройства за счет отсутствия в предлагаемом устройстве схекш сравнения, элемента равнозначности, уменьшается число межэлементных связей. Кроме того, исключается режим перезаписи чисел, в связи с чем увеличивается надежность устройства. Формула изобретения Устройство для сортировки чисел, содержащее группу элементов И, входной элемент И, отлич. ающее с я тем, что, с целью упрочения устройства и повышения надежности устройства за счет исключения режима перезаписи чисел, оно содержит счетчики, выходной счетчик, элементы ИЛИ, дифференцирующие элементы, запре14ающие элементы И, причем выходы счетчиков поразрядно соединены с входами соответствующих элементов ИЛИ, выходы которых соединены с входами соответствующих дифференцирующих элементов, первым вхолами соответствующих эапрещакнцих элементов И и соответствующими входами первого элемента ИЛИ, выходы дифференцирукшшх элементоа соединены с соответствующими входами второго элемента ИЛИ, выход которого соединен с первыми входами элементов И группы, выходы которых являются выходам устройства, выход первого элемента ИЛИ соединен с первым входом входного элемента И, второй вход которого соединен с входом тактовых импульсов устройства, выход входного элемента И соедииен с вторыми входми запрещающих элементов И и суммиЦ1

uu

гул

L-S г

гул

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

Источники информации, принятые во внимание при экспертизе

0 463968, кл.

G 06 F 7/08, 197Б.

(прототип ).

5

I

W