Устройство для сортировки @ -разрядных чисел

 

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

COOS СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 С 06 F 7/04

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТНЕККЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЭОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3843573/24-24 (22) 14.01.85 (46) 30.07.86. Бюл. N 28 (72) E.ß. Ваврук, Ю.М. Захарко, - А.А. Мельник и И.Г. Цмоць (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

9 563774, кл. G 06 F 7/04, 1977.

Авторское свидетельство СССР

Р 964628, кл, G 06 F 7/02, 1982.

Авторское свидетельство СССР

Ф 993251, кл. G 06 F 7/08, 1981. (54 ) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ И-РА3РЯДНЫХ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки массива чисел, представленных числоимпульсным кодом. Целью изобретения является повышение быстродействия устройства, а также упрощение наращивания устройства. С этой целью в устройство введены m вычитающих счетчиков, где m — количество сортируемых чисел, триггер и элемент И. При поУ о

)247859 ступлении очередного i-го числа (i=

1,2,...,m) оно записывается в i-м суммирующем счетчике, и вычитается из l-ro, 2-ro, (i-1)-ro вычитающего счетчика, где записаны числа уже отсортированной части массива.

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

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

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

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

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

)lО

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

Устройство содержит m блоков анализа I, -I, которые содержат m п-разрядных суммирующих счетчиков

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

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

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

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

Поскольку элементы И анализа

4 — 4 закрыты сигналом логического нуля, поступающего с инверсного выхода вычитающих счетчиков 3„ -3 „,то первое число, поступившее по входу 9 в виде пачки из 1 импульсов (где

1„ — значение первого числа) через элемент И 4„ на счетный вход счетчика 2„, запишется в последнем. Та же пачка импульсов поступит на входы всех вычитающих счетчиков 3 -3 .

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

1 в нулевом состоянии.

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

859 4

Составитель В. Горохов

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

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, И-35, Раушская наб., д. 4/5

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

3 1247

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

1 то второе число полностью запишется в счетчик 22 . Если 1 р 1,,то после 10

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

1 окончания передачи второго числа в счетчике записывается число 1 + 1 — 20

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

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

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

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