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

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

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

На фиг. 1 приведена схема устройства; на фиг. 2 - схема ячейки анализа.

Устройство содержит п/2 ячеек

.1-1 -I .a,i ,1 t

..., анализа i-ro типа, где п - количество сортируемых чисел, ближайшее целое, не меньшее х, счетчик 2, формирователи 3 - з- импульсов, вход 4 начальной установки, тактовый вход 5, группы информационных входов 6, - 6, группы выходов 7 отсортированных чисел, выход 8 окончания работы устройства. Ячейка анализа i-ro типа содержит первую

9 - ,,и вторую 10, - 10 ,--1 группы регистров, элементы 11 - 11-., сравнения, коммутаторы 12, - 12,,-.,, входы 13 и 14 управления записью, информационные входы 15, - 15.1 , информационные выходы 16 - .

Устройство работает следующим образом.

На входы 6 - 6р устройства поступают сортируемые числа, которые по сигналу начальной установки с входа 4 записываются в регистры 9 и 10 ячеек 1 - анализа первого типа. Одновременно в счетчик 2 записывается число 1.Через время, достаточное для сравнения чисел элементами 11 сравнения и соответствующей коммутации (в триггер 9 коммутируется меньшее,.а в регистр 10 - большее из чисел) по входу 5 поступает тактовый импульс, по которому происходит заСП

ю

о

С71

О QD

пись попарно отсортированных чисел в регистры 9 и 10. Одновременно содержимое счетчика 2 увеличивается на единицу, при этом при появлении положительного фронта на выходе второго разряда счетчика 2 через время, достаточное для записи чисел в регист ры, на выходе формирователя 3 импульсов формируется импульс. Этот им- пульс поступает на входы разрешения записи регистров 9 и 10 ячеек 1 анализа второго типау куда упорядоченные пары чисел переписываются из регистров 9 и 10 ячеек анализа первого типа.

Ячейки анализа -следующих типов работают аналогично5 йричем ячейка го типа производит в течение 2 V тактов сортировку - слияние двух отсортированных двумя ячейка ш анализа пре дьщущего типа массивов яз 2. чисел каждый.

В ячейках а нал11за йврвке вьшоды коммутаторов 12 соединены с вxpдa да регистров .9 со сдвигом на один ре гистр- влево. Такое соединение обес-- печивает слияние двух отсортировак- ных массивов чисел, что ш1ЯЕЮстрирует ся на примере работы ячейки анализа третьего типа. По сигналу с выхода формирователя 3 шшульсов в регистры 9.J - 94 и 10 - tOji- записываются соответственно числа 5 8 я t 4с Содержимое регистров 9 и 10 после каждого такта указано в таблице.

Следующий массив чисел мозйет быть записан в устройство через 2- f тактов, т.е. яосле того, как числа oтpaбaтывJaeмoгo массива, будут записа50

-ны в ячейку анализа последнего типа. Формула изобретения

Устройство для сортировки чисел 3 содержащее ячеек анализа 1-го типа, где п количество сортируемых

чисел.

Г Т,2,.,,, 1о§гпС, 1хС

S

.

0

5

0

0

5

0

5

ближайшее целое, не меньшее х, причем каждая ячейка анализа i-ro типа содержит 2 элементов сравнения и 2 коммутаторов, в каждой ячейке анализа i-ro типа первая и вторая группы информационных входов j-ro коммутатора и j-ro элемента сравнения, где j 1525... 5 , соответственно объе- диненЫ9 выход j-ro элемента сравнения соединен с управляющим входом j-ro коммутатора, первая и вторая группы информационных входов К-й ячейки анализа первого типа, где К 1,2,..,, п/2, являются соответственно (2К-1)-й и группой информационных входов устройства, 1-я группа информационных, выходов Р-й .ячейки анализа q-ro типа, где ..., 2% р 1,2,.,,, q 1s25o,,, 11 ogjn-1 , соединена с (2q(p-1)+l)M группой информационных входов JP/2C -и ячейки анализа (q+1)-ro типа, г-я группа информа- Цйоикых выходов ячейки анализа

llog nr-ro типа, где ,2,:o . ,п, является виходом г-го отсортированного числа устройства, о т л и ч а ю щ е- е с я тем, чтоз с целью упрощения уетройстваэ оно содерзшт . формирователей импульсов и счетчик, а каждая ячейка анализа i-ro типа содержит первую и вторую группм из 2 регистров каждая S причем такто- г-.вьШ вход устройства соединен с первы- Ыи входами разрешения записи всех ре- гистров всех ячеек анализа, и счетным входом счетчика выход (q-l)-ro разряда которого через q-й формирователь и шульсоБ соединен с вторыми входами разрешения записи всех регистров ячеек анализа (q+1)-ro типа5 вход на-. . ча.льной установки устройства соединен с вторыми входами разрешения записи всех регистров всех ячеек анализа первого типа э входом установки в единичное состояние первого разряда счет чика и входами установки в нулевое состояние остальных разрядов счетчика, в каждой ячейке анализа S-я группа информационных входов ячейки, ,2,

,,,52, соединена с первой группой/ информационных 1входов ( 1)-го регистра 3S/2 С -и группы, группы выходов j-ro регистра первой и второй группы соединены соответственно с первой и второй группами входов j-ro элемента сравнения и являются соответственно j-й и (j- -2 )-й группой информационных вьгходов ячейки

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

(-1

группой информационных входов 2 -го регистра первой группы, первая группа выходов V-ro коммутатора, где V

2,3,..,,2

соединена с второй

группой информационных входов (V-1)- го регистра первой группы, вторая группа выходов j-ro коммутатора соединена с второй группой информационных входов j-ro регистра второй группы.

Изобретение относится к вычислительной технике. Цель изобретения - упрощение устройства. Устройство содержит ] N/2I[ ячеек анализа (1ЯА)I-го типа, где N - количество сортируемых чисел, I = 1,2,...] LOG₂ H[, счетчик, формирователи импульсов, вход начальной установки, тактовый вход, информационные выходы, выход окончания работы. ЯА I-го типа содержит две группы регистров, элементы сравнения, коммутаторы, входы управления записью, информационные входы и выходы. Каждая ЯА I-го типа формирует на своих выходах упорядоченную последовательность из 2^I чисел, составленную из двух упорядоченных последовательностей из 2^I-1 чисел каждая, которые были отсортированы двумя ЯА I-1-го типа. 2 ил.

яг. /

Щг1$2Н

/5,./

аг.2

(