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

 

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

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

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

РЕСПУБЛИК @4 G 06 F 7/ОЬ

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4434503/24-24 (22) 29.04,88 (46) 07.11.89. Бюл. У 41 (72) В.И.Язневич, К.И.Язневич и И.И.Овсеец (53) 681.325.66 (088.8) (56) Авторское свидетельство СССР

9 1123030, кл. С 06 Р 7/06, 1983.

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

Ф 1298737, кл. G 06 Р 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретения— упрощение устройства. Устройство содержит Зп/2 3 ячеек анализа (ЯА) i-го

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

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

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

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

1 1 1 2

1,е lyte ° ° y 1w gy 1

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

„„Я0„„1520509 А1

2 типа, где п — количество сортируемых чисел, i = 1,2,...)1оВ,р (, счетчик, формирователи импульсов, вход начальной установки, тактовый вход, информационные выходы, выход окончания работы. ЯА i-го типа содержит две группы регистров, элементы сравнения, коммутаторы, входы управления записью, информационные входы и выходы.

Каждая ЯА i-ro типа формирует на своих выходах упорядоченную последовательность из 2 чисел, составленную из двух упорядоченных последовательностей из 2 чисел каждая, которые были отсортированы двумя ЯА (i-1)-го типа. 2 ил., 1 табл.

91 — 9;,и вторую 10, — 10,-1 группы регистров 3JIeMPHTbl 11, — 11 ;, cpGBнения, коммутаторы 12, — 12 ;,, входы 1-1

13 и 14 управления записью, информационные входы 15„ - 15,, информационные выходы 16, — 16 .

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

На входы 6 „ — 6 „ устройства поступают сортируемые числа, которые по сигналу начальной установки с входа

4 записываются в регистры 9 и 10 ячеек 1 — 1 „, анализа первого типа.

Одновременно в счетчик 2 записывается число "1".Через время, достаточное для сравнения чисел элементами

11 сравнения и соответствующей коммутации (в триггер 9 коммутируется меньшее,.а в регистр 10 — большее из чисел) по входу 5 поступает тактовый импульс, по которому происходит эа1520509

Такт

5 6 7 8 1 2 3 4

2 3 4 1 5 б 7 8

3 4 1 2 5 6 7 8

4 1 2 3 5 6 7 8

2 3 4 5 6 7 8

Д

6

Следующий массив чисел может быть записан в устройство через 2 тактов, т.е. после того, как числа отрабатываемого массива будут записа5О лы в ячейку 1 г анаЛиза последнего типа.

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

Устройство для сортировки чисел, содержащее )n/2 h ячеек анализа i-го типа, где n — количество сортируемых чисел, х = 1,2,..., 1о п f, )x(лись попарно отсортированных чисел в регистры 9 и 10. Одновременно содержимое счетчика 2 увеличивается на единицу при этом при появлении полоУ

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

Ячейки анализа следующих типов работают аналогично, причем ячейка 2 го типа производит в течение 2 . тактов сортировку — слияние двух отсор- 20 тированных двумя ячейками анализа пре= дыдущего типа массивов из 2 чисел каждый.

М

В ячейках анализ- иервые выходы коммутаторов 12 соединены с входами регистров .9 со сдвигом на один регистр. влево. Такое соединение обес . печивает слияние двух отсортированных массивов чисел, что ыапострируется на примере работы ячейки анализа

36 третьего типа, По сигналу с выхода формирователя 3 импульсов в регистры 9, - 9 „ и 10 - 10 . записываются соответственно числа 5 — 8 и 1 - 4.

Содержимое регистров 9 и 10 после .каждого такта указано в таблице. ближайшее целое, не меньшее х, причем каждая ячейка анализа i-го типа содержит 2 элементов сравнения и 2 коммутаторов, в каждой ячейке анализа

i-го типа первая и вторая группы информационных входов j-ro коммутатора и j-го элемента сравнения, где j

1,2,...,2, соответственно объединены, выход j-ro элемента сравнения соединен с управляющим входом j-ro коммутатора, первая и вторая группы информационных входов К-й ячейки анализа первого типа, где К = 1,2,..., n/2, являются соответственно (2К- t)-й и 2К-й группой информационных входов устройства, 1-я группа информационных выходов Р-й .ячейки анализа q-го типа где "=-1 2 .. 2 p 1 2 ° и/2, q=1.,2,..., 31og п-1(, соединеHà с (2q(p-1)+1)-й группой информационных входов tP/2 L -й ячейки анализа (q+1) "о типа г я группа информа» о ционных выходов ячейки анализа

) Тog и Г-го типа, где г=1, 2,...,n является выходом г-го отсортированного числа устройства, о т л и ч а ю щ ее с я тем, что, с целью упрощения устбойства, оно содержит llog n"1Ã формирователей импульсов и счетчик, а каждая ячейка анализа -го типа содержит первую и вторую группы из

2 регистров каждая, причем такто.вый вход устройства соединен с первы-! ми входами разрешения записи всех регистров всех ячеек анализа и счетным входом счетчика„ выход (q-1)-rо разряда которого через q-й формирователь импульсов соединен с вторыми входами разрешения записи всех регистров ячеек анализа (q+1)-го типа, вход на-. чальной установки устройства соединен с вторыми входами разрешения записи всех регистров всех ччеек анализа первого типа, входом установки в едияичное состояние первого разряда счетчика и входами установки в нулевое состояние остальных разрядов счетчика, в каждой ячейке анализа S-я грунта информационных входов ячейки, Б1,2, ...,2, соединена с первой группой информационных входов S=2 (f S/2 f

-1)-го регистра 38/2 l: - и группы, группы выходов j-ro регистра первой и второй группы соединены соответственно с первой и второй группами входов 1»го элемента сравнения и являются соответственно j--й и (j+2 )-й группой информационных выходов ячейки

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

=2,3,...,2, соединена с второй

9 б группой информационных входов (Ч-1)го регистра первой группы, вторая группа выходов j-го коммутатора соединена с второй группой информационных входов j-го регистра второй группы, 1520509

Ю1: fS?H

Б и+1)+ 16 с

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

Редактор В Данко Техред А.Кравчук Корректор Л.Катай

Заказ 6758/49 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101