Устройство для сортировки @ -разрядных чисел Советский патент 1986 года по МПК G06F7/04 

ступлении очередного i-ro числа {1 l,2,...,m) оно записывается в i-м суммирукяДем счетчике, и вычитается из l-ro,j2-го,..., (1-1)-го вычитающего счетчика, где записаны числа уже отсортированной части массива. В момент равенства вновь поступающв го числа и числа, хранившегося в вычитающем (1-1)-м счетчике, произойдет переключение на запись оставшейИзобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массива, чисел, представленных число- мпульсным кодом.

Цель изобретения - повышение быстродействия устройства при сортировке чисел, представленных числоимпульс- ным кодом, а также упрощение наращивания устройства.

На чертеже представлена схема устройства.

Устройство содержит m блоков анализа 1 которые содержат m п-разрядных суммирующих счетчиков 2 -2 ,m(n+l)-разрядных вычитающих счетчиков 3 3, m элементов И анализа . Устройство содержит так- ,же триггер 5, управляющие элементы И 6 и 7, элемент ИЛИ 8, информа- ционньй вход 9, вход 10 начальной установки, вход 11 начала цикла сравнения и вькод 12 разрешения переписи числа устройства.

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

Перед началом работы импульсом по входу начальной установки 10 триггер 5, суммирующие и вычитающие 3,-3 счетчики устанавливаются

т

В нулевое состояние.

По входу 11 начала цикла сравнения поступают импульсы начала и конца передачи числа. Первый из этих импульсов поступает на счетный вход триггера 5 и через элементы И 7 и ИЛИ 8 - на счетные входы триггера вьмитающих счетчиков ,. По заднему фронту этого импульса триггер 5 устанавливается в единичное

47859

ся части поступающего числа в (1- |)-й счетчик. Поэтому в i-й счетчик перепишется значение, хранящееся в | (i-l)-M счетчике, а в (1-1)-й счетчик запишется большее число. В результате массив чисел будет отсортирован в порядке убьшания - в первом счетчике будет находиться максимальное, а в т-м - минимальное число из массива. 1 ил.

«О

20

состояние, а содержимое вычитающих счетчиков 3 -3 уменьшается на единицу, т.е. во всех разрядах счетчиков будут единицы. Сигнал ло- 5 гической единицы с (n-f 1 )-х разрядов вычитающих счетчиков поступает на входы элементов И 4 inПоскольку элементы И анализа закрыты сигналом логического нуля, поступающего с инверсного выхода вьиитающих счетчиков 3 -3,„ ,то

1 fn-f

первое число, поступившее по входу 9

в виде пачки из 1 импульсов (где .

значение первого числа) через элемент И 4 на счетный вход счет- ,чика 2 , запишется в последнем. Та же пачка импульсов поступит на входы всех вычитающих счетчиков . Так как эти счетчики имеют на один разряд больше, то значение самого старшего, (п-4-1)-го, разряда не из- , менится. После передачи первого числа на вход 11 поступает импульс окончания передачи числа. Этот импульс через открытьй элемент И 6 поступает на входы разрешения записи всех вычитающих счетчиков и на счет- ньй вход триггера 5. В результате триггер 5 установлен в нулевое со- стояние, в счетчике 3 находится число 1 (переписанное из счетчика 2, ). Счетчики 3„-3,„ находятся

тt

в нулевом состоянии. I Передача второго числа начинается

с импульса начала передачи по входу J . Как и в предыдущем случае, этим импульсом триггер 5 устанавливается в единичное состояние, а из - хранящихся в вычитающих счетчиках чисел вычитается единица.

5

Поэтому в счетчике 3, находится число , а в счетчиках числа, во всех разрядах которых единицы. Элемент И 4 закрыт, так как на прямом выходе (п+1)-го разряда счетчика 3 - нуль, но открыт элемент И 4,, поэтому второе число начинает записываться в счетчике 2.. Если 1„ 1

2.

1

1

то второе число полностью запишется

в счетчик 2„ . Если 1,

поступления 1 импульсов в счетчи; 1 , ,то после 10

а в счетке 2 записывается число 1 чике 3 - число, во всех разрядах которого единица. Поэтому элемент И 4 закрывается, но открывается элего числа, равна в счетчик

мент И 4 , и оставшаяся часть второ- 1 - 1, записывается 2 и таким образом после окончания передачи второго числа в счетчике записьшается число 1 + 1 - - 1 1 . Дальнейшая работа устройства аналогична, В результате исходный массив отсортирован в порядке убывания: в счетчике 2 - максимальное, в счетчике 2 - минимальное число.

Формула изобретения

Устройство для сортировки п-раз- рядных чисел, содержащее m п-разряд- ных суммирующих счетчиков, где и - количество сортируемых чисел, m элементов И анализа, первый элемент И и элемент ИЛИ, причем выход i-ro элемента И анализа, где i 1,2,.,.,m, соединен со счетным входом i-Po суммирующего счетчика, а первые входы, всех элементов И анализа объединены, отличающееся тем, что, с целью повьшения быстродействия уст

Составитель В. Горохов Редактор И. Сегляник Техред М.Ходанич Корректор Л. Пилипенко

-ч-...-.- .. - ---.- - --..и.--«.- - - ------- -

Заказ 4126/48 Тираж 671Подписное

В1ШИ1Ш Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раущская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

,

10

т

15

20 25

30

до

35

ройства при сортировке чисел, представленных числоимпульсным кодом, а также с целью упрощения наращ1 вания устройства, оно содержит триггер, второй элемент И и m (п+1)-разрядных вычитающих счетчиков, причем вход начала цикла сравнения устройства соединен с первыми входами первого и второго элементов И и со счетным входом триггера, прямой и инверсный выходы которого соединены с вторыми входами соответственно первого и второго элементов И, выход второго элемента И соединен с первым входом элемента ИЛИ, выход которого соединен со счетными входами всех вычитающих счетчиков, входы разрешения з-аписи которых подключены к выходу первого . элемента И, выход j-ro разряда i-ro суммирующего счетчика, где j 1,2,...,п, соединен с информационным входом j-ro разряда i-ro вычитающего счетчика, прямой выход (п+1)-го разряда которого соединен с вторым входом i-ro элемента И анализа, инверсный выход (п+1)-го разряда k-ro вычитающего счетчика, где k 1,2,..., т-1, соединен с третьим входом (k+1)-го элемента И анализа, инверсный выход (п+1)-го разряда т-го вычитающего счетчика является выходом разрешения переписи числа устройства; информационный вход устройства соединен с вторым входом элемента ИЛИ и первыми входами всех элемент.ов И анализа, вход начальной установки устройства соединен с входами установки в нулевое состояние триггера и всех суммирующих и вычитающих счетчиков.

Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массива чисел, представленных числоим- пульсным кодом. Целью изобретения является повышение быст.родействия устройства, а также упрощение наращивания устройства. С этой целью в устройство введены m вычитающих счетчиков , где m - количество сортируемых чисел, триггер и элемент И. При по