Устройство для сортировки чисел

 

Изобретение относится к вычислительной технике и может быть использовано для упорядочения информации в убывающем порядке по мере ее поступления. Целью изобретения является увеличение быстродействия устройства. Устройство содержит п регистров 1, п групп элементов И-ИЛИ 2, п-1 элементов И 3, п схем сравнения 4, п-2 элемента ИЛИ 6. Устройство осуществляет сортировку (упорядочение чисел) по мере их поступления в порядке убывания, т.е. максимальное число размещается в первом регистре . Выполнение каждого регистра по двухступенчатой схеме позволяет осуществить одновременный сдвиг информации в требуемых регистрах при размещении очередного числа в упорядоченном Массиве. 1 ил. с

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИН

„„SU„„1365076 A 1 (51)4 G 06 F 7 06

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4132842/24-24 (2e) 16.07.86 (46) 07 ° 01.88. Бюл. В 1 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В,А,Авдеев, И.А.Каракошенко и В.П.Карелин (53) 681.325 (088,8) (56) Авторское свидетельство СССР

У 826339, кл. G 06 F 7/06, 1979, Авторское свидетельство СССР

У 1037246, кл. С 06 Г 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для упорядочения информации в убывающем порядке по мере ее поступления. Целью изобретения является увеличение быстродействия устройства. Устройство содержит п регистров 1, и групп элементов И-ИЛИ

2, п-1 элементов И 3, п схем сравнения 4, и-2 элемента ИЛИ 6, Устройство осуществляет сортировку (упорядочение чисел) по мере их поступления в порядке убывания, т.е. максимальное число размещается в первом регистре, Выполнение каждого регистра по двухступенчатой схеме позволяет осуществить одновременный сдвиг информации в требуемых регистрах при размещении очередного числа в упорядоченном массиве. 1 ил.

Я fg e

1365076

25.

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

Цель изобретения — повышение быстродействия.

На чертеже представлена функциональная схема устройства.

Устройство для сортировки чисел содержит и регистров 1, и групп элементов И-ИЛИ 2, (n-1) элементов И 3, схемы 4 сравнения, информационные входы 5 устройства, элементы ИЛИ 6, тактовый вход 7.

Каждый регистр 1 устройства вы1 полнен по двухступенчатой схеме, т.е. каждый разряд регистра можно представить, например, в виде двухступенчатого триггера. При наличии управляющего сигнала, поступающего на вход, 7 устройства, происходит запоминание входной информации на элементах памяти (триггерах) первой ступени, а при отсутствии управляющего сигнала информация переписывается на триггеры второй ступени.

Схема 4. сравнения осуществляет

1 сравнение двух чисел. Если входное число больше (равно) числа, хранимого в регистре 1, то на первом

1 (верхнем) выходе схемы 4 сравнения ! формируется сигнал единичного уровня, в противном случае сигнал вырабатывается на втором (нижнем) выходе °

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

На входы последовательно по словам и параллельно по разрядам поступают m-разрядные коды чисел. Устройство осуществляет сортировку (упорядочение чисел) по мере их поступления в порядке убывания, т,е. максимальное число размещается в первом регистре.

После подачи очередного кода числа на входы устройства через промежуток времени, в течение которого заканчиваются переходные процессы в устройстве, на вход 7 поступает управляющий сигнал, осуществляющий прием в регистр 1 информации через

1 группу элементов И-ИЛИ 2, либо со стороны регистра 1;, либо со стороны входов 5.

Управление приемом информации в регистр 1 со стороны входов 5 выполняется

1 сигналом элемента И 3;, (i = 2,п-1), а управление вводом информации из регистра 1 — сигналом с выхода элемента ИЛИ 6 . Элементы И 3 предназ1-2 начены для определения соотношения, когда очередное входное число меньше предыдущего, но больше последующего, Например, пусть четвертое входное число оказывается меньше второго, хранимого во второй ступени регистра 1, но больше третьего, записанного во второй ступени регистра 1з.

Тогда на выходе элемента И 3 сформирован сигнал единичного уровня, который разрешает прием информации в первую ступень регистра 1 со стороны входов 5,-5 по управляющему сигналу, поступающему на вход 7..Кроме того, в это же время происходит одновременный сдвиг содержимого второй ступени регистра 1 в первую ступень регистра 1, т.е. сигнал с выхода элемента И 3, последовательно проходя логические элементы ИЛИ 6 и

6 осуществляет соответственно разрешение на передачу содержимого второй ступени регистра 1 в первую ступень регистра 1, второй ступени регистра

11 в первую ступень регистра 1 и так далее, которая осуществляется одновременно с приходом управляющего сигнала единичного уровня на вход 7.

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

Устройство для сортировки чисел, содержащее и регистров, и групп элементов И-ИЛИ, (n-1) элементов И и п схем сравнения, причем информационные входы устройства соединены с входами первых групп схем сравнения и первыми входами элементов И-ИЛИ групп, входы второй группы i-й схемы сравнения, где i = 1,...,n, соединены с выходами разрядов i-го регистра, выходы разрядов j-го регистра, где

j = 1,..., (п-1), соединены с вторыми входами элементов И-ИЛИ (j+1)-й группы, выходы элементов И-ИЛИ i-й группы соединены с входами соответствующих разрядов i-го регистра, выход j-го элемента И соединен с третьими входами элементов И-ИЛИ (j+1)-й группы, выход "Больше" первой схемы сравнения подключен к вторым вхорам элементов И-ИЛИ первой группы, выход

"Больше" (j+1)-й схемы сравнения соединен с первым входом j-го элемента

И, второй вход которого соединен с выходом Меньше-равно j é схемы

1365076

Составитель Е.Иванова

Техред Л.Сердюкова

Корректор В.Гирняк

Редактор М.Бланар

Заказ 6611/42 Тираа 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Уагород, ул. Проектная, 4 сравнения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены (п-2) элемента ИЛИ, причем выход К-го элемента И, где К = 1,...,(n-2), соединен с первым входом К-го элемента

ИЛИ, второй вход р-го элемента ИЛИ, где р = 2,...,(n-2), соединен с выходом (р-1)-го элемента ИЛИ, второй вход первого элемента ИЛИ соединен с выходом Больше" первой схемы сравнения, вторыми входами элементов

И-ИЛИ первой группы и четвертыми входами элементов И-ИЛИ второй группы, выход К-ro элементаИЛИ подключенк чет— вертым входам элементов И-ИЛИ (К+2) -й г руппы, тактовый вход устройства подключен куправляющим входамвсех регистров.