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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения за счет обеспечения параллельного ввода сортируемых чисел. Устройство содержит управляющий регистр 1, элементы запрета 2, 3 и m узлов анализа (УА) 4 - 4m(m - количество сортируемых чисел). Каждый узел анализа содержит шинный формирователь 5, блок сравнения 6, комму з I8i ML

(19 (И) СОЮЗ COSETCHHX

РЕСПЮЛИН (Si)S С 06 Р 7/08 списочник изоврктания

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ИЗОЬРЕТЕНИЯМ И ОТХРЫТИЯМ

ПРИ ГНКТ CCCP (21) 4698019/24 (22) 29,05.89 (46) 15.05.91. Бюл. Р 18 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.П.Карелин, В.Ф. Гузик, С.Ю. Фомин и Д.И.Чехов (53) 681.325.5(088.8) (56) Авторское свидетельство- СССР

Р 497583, кл. G 06 F 7/06, 1974.

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

В 1112362, кл. G 06 F 7/08, 1983.

2 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — расширение области применения за счет обеспечения параллельного ввода сортируемых чисел.

Устройство содержит управлявщий регистр 1, элементы запрета 2, 3 и m узлов анализа (УА) 4 — 4щ(тп — количество сортируемых чисел). Каждый узел анализа содержит шинный формирователь 5, блок сравнения 6, комму1649533

40 таторы 7, 8, регистр 9, элемент И 10, . элементы ИЛИ 11, 12, шину ввода-вывода 13. Устройство содержит также . вход записи 14, тактовый вход 15, информационный выход 16, выход окончания работы 17, входы каращивания устройства 18 -18З. В каждом i-м такте работы (i = 1, 2, ... m) выделяется максимальное число иэ чисел, эаписан15

Ф

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

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

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

Устройство содержит управляющий регистр 1, элементы 2 и 3 запрета и ш узлов 4 — 4 анализа (m - количест4 «>

so сортируемых чисел) .

Каждый узел анализа образуют шинный формирователь 5, блок 6 сравнения, коммутаторы 7 и О, регистр 9, элемент И 10, элементы ИЛИ 11 и 12, шину 13." ввода-вывода i-ro сортируемого числа (i = 1, 2, ..., m) ° Уст- 35 ройство содержит также вход 14 записи, тактовый вход 15, информационный выход 16, выход 17 окончания работы, входы.и выходы наращивания устройства 181-18 з.

Устройство работает следующим обpasoM, На шины 13 -13,„ одновременно поступает ш сортируемых чисел а -ащ и сигналом по входу 14 через соответ- 45 ствующие шинные формирователи 5 н коммутаторы 8 записываются в регистры 9 узлов 4q -4я, анализа, регистр 1 обнуляется(не показано) . Затем сигнал с входа 14 снимается, а на входе 18 устанавливается код минимального . Возможного числа. В каждом иэ узлов анализа 4, коммутатор 7 выбирает боль mee из двух чисел: поступившее с выходов коммутатора 7 предыдущего узла

Э анализа 4, > и хранящееся в регистре

9, . В результате на выходе 16 устройства формируется код максимального из чисел, записанных в регистры 9 ных в регистры 9 УА 4 -4 кото-, fry-1+1 ю рое записывается в регистр g УА 4

Одновременно числа из регистров 9 УА

4 -4 о .< переписываются в регистры 9 :

УА соответственно 4 -4, где (6- номер УА, в котором находится выделенное на этом такте максимальное число.

1 ил.

I устройства. Это число под воздействием тактового импульса по входу 15 записывается в регистр 9 узла 4<. Одновременно число, хранящееся в регистре 9 этого узла, переписывается в регистр

9 узла 4 и т.д. вплоть до того узла анализа 4 (, в регистре 9 которого находилось выделенное максимальное число. В этом узле 4 на выходе блока 6 сравнения имеется "A" который поступает на вход цепочки элементов И 10, что предопределяет нулевой сигнал на входах разрешения записи V всех регистров 9 узлов анализа 4я для ф ) DC. В узт лах 4р, p c g, на входах разрешения записи 7 регистров 9 присутствует потенциал "1". Тем же тактовым сигналом с входа 15 содержимое регистра 1 сдвигается в сторону старших разрядов, а в младший разряд записывается единица.

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

4 -4 . Это приводит к тому, что уже выделенные н записанные в регистры 9 узлов 41-4, i максимальных чисел не принимаются во внимание при поиске очередного (i+1)-ro по величине числа.

На выходах элементов ИЛИ 11 этих узлов анализа присутствует сигнал ,"1", который вызывает перезапись чисел, находящихся в регистрах 9.После ш тактов на выходе ш-го разряда регистра 1 и на выходе 17 окончания работы устройства формируется сигнал "1", а в регистрах 9 узлов

4 -4 находится исходный массив чи1Yl сел, отсортированный в порядке возрастания .

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

Устройство для сортировки чисел, сбдержащее регистр управления и m

164953

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

Редактор Л. Пчолинская ТехредЛ.Олийнык Корректор -А. Обручар

Заказ 1522 Тираж 404 Подписное

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

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

Производственно-издательский комбинат "Патент", г; Ужгород, ул, Гагарина, 101 е узлов анализа, где m — количество сортируемых чисел, каждый узел анализа содержит регистр, первый коммутатор, блок сравнения и элемент И при5 чем в каждом блоке анализа информационные входы первой и второй групп первого коммутатора и блока сравнения попарно объединены, о т л ич а ю щ е е с я тем, что, с целью расширения области применения путем

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

3 6 ввода-вывода второй группы шинного формирователя соединены с информационными входами первых групп первого и второго коммутаторов и выходами соответствующих разрядов регистра, выход блока сравнения и выход i-го разряда регистра управления соединены соответственно с первым и вторым входами второго элемента ИЛИ того же узла анализа, выход этого элемента ИЛИ соединен с управляющим входом первого коммутатора и первым входом элемента И, выход первого элемента

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

ИЛИ ()+1)-го узла анализа, первый и второй входы первого коммутатора и выход элемента И m-го узла анализа являются соответственно входами и выходом наращивания устройства.