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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах о.бработки информации, предназначенных для сортировки массива данных поступающих параллельным кодом одно за другим в реальном масштабе времени. Цель изобретения 7J Tf (Л со Oi 00

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

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

РЕСПУБЛИН

ÄÄSUÄÄ 1341631

А1 ид 4 G 06 F 7 08

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

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

1Ô

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4007494/24-24 (22) 10.01.86 (46) 30.09.87. Бюл. Nl 36 (72) Е.Я.Ваврук и В.М.Равский (53) 681.325(088.8) (56) Авторское свидетельство СССР

9 1007099, кл. G 06 F 7/08, 1981.

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

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

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

И 5, регистр 6, схему 7 сравнения и коммутатор 8, сумматор-вычитатель

9, выходной регистр 10. Устройство выполняет сортировку разностей сортируемых чисел и заданного числа.

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

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

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

Устройство для сортировки чисел содержит входной регистр 1,регистр

2 заданного числа, вычитатель 3, (ш-i) узлов 4 сравнения (m — количество сортируемых чисел),причем каждый узел 4 сравнения содержит элементы И 5, регистр 6, схему 7 сравнения, коммутатор 8, сумматор-вычитатель 9, выходной регистр 10, вход 11 сортируемых чисел, входы 12 заданног o числа, вход 13 тактовых импульсов устройства и вход 14 начальной установки.

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

По сигналу начальной установки на входе 14 регистры 6 устанавливаются в нулевое положение. Сортируемая последовательность чисел в прямом коде с информационных входов 11 поступает на.входы регистра 1.В каждом

В сумматоре-вычитателе формируется сумма или разность заданного числа с наименьшей разностью. После поступ ления (m+1) импульсов ближайшее к заданному число будет записано в выходной регистр. В регистрах 6 узлов сравнения будут записаны разности между заданным числом и сортируемыми числами, при этом наибольшая разность будет записана в регистре 6 первого узла сравнения.При считывании чисел в сумматоре-вычитателе формируется ранжированная последовательность чисел.1 ил. 4 табл. такте работы в регистр 1 записывается одно из чисел этой последовательности. Информация с выхода регистра

1 поступает на первые входы вычитателя.В регистре 2 записывается число (с входов 12), к которому необходимо найти ближайшее (сигнал записи на чертеже не приведен).

Схема сравнения формирует сигнал

1О "1", когда содержимое регистра 6 меньше содержимого вычитателя З.Этот сигнал служит для передачи на выход коммутатора 8 содержимого регистра б. На выходах разности вычитателя 3

15 формируется разность между содержимым регистров 1 и 2, на выходе знака — знак разности, который записывается в регистр 6.

Устройство работает в трех режи2р мах: -в режиме определения числа ближайшего к заданному,в режиме сортировки по возрастанию, и в режиме сортировки по убыванию.

Рассмотрим работу устройства в

25 режиме определения чисел, ближайшего к заданному.

По первому тактовому импульсу в регистр 1 записывается первое число, которое с его выхода поступает

30 на входы уменьшаемого вычитателя 3, на входы вычитаемого которого поступает число с регистра 2.Значение разности этих чисел с вычитателя 3 поступает на входы регистра б,входы вторых групп схемы 7 сравнения и

1341631 4 ние (если сортируемое число меньше заданного) заданной и сортируемой разности. Режимом сумматора-вычитателя 9 управляет второй выход коммутатора 8 (m-1) узла 4 сравнения.

Дальнейшая работа устройства в данном режиме происходит аналогично.

После поступления (ш+1) импульсов числа массива сортируются в порядке ближайшего к заданному.При этом ближайшее к заданному число записывается з регистр 10, а в регистрах 6 узлов 4 сравнения записывается разность между заданным и сортируемым числом (в регистре 6 первого узла 4 сравнения — наибольшая разность).

Для считывания чисел с выхода регистра 10 необходимо подать еще (m-1) тактовый импульс, предварительно установив регистр 2 в "0".

В режиме сортировки по убыванию и возрастанию работа устройства про ходит аналогично за исключением то го,что в регистр 2 записывается соответственно минимальное (нули) и максимально допустимое число (все "1").

Работа устройства при сортировке

-З0 чисел: 8, 12, 9, 10, 14 при заданном числе 10 происходит следующим образом.

Таблица!

Начальная установка

0 х

1 (8-10) =-2 О

-2 (I 2-10) =+2 0

+2 (9-10) =-1 0

-1 (9-9) =0 х

5 (14 — 10)=

= +4

+2 -1

-2 ° коммутатора 8. На выходе всех схем

7 сравнения формируется сигнал "1"

По второму тактовому импульсу в регистр 1 записывается второе из массива,в регистр 6 первого узла

4 сравнения переписывается число иэ вычитателя 3, а в регистры 6 остальных узлов 4 сравнения записывается информация с выходов коммутаторов

8, т.е. нули. В регистры 6 записывается и знак разности, который присутствует и на выходе коммутаторов 8.

Вторая разность сравнивается с содержимым регистра 6 каждого узла

4 сравнения, и если вторая разность больше первой,то на выходе всех схем

7 сравнения формируется сигнал ".1".Ес ли же вторая разность меньше первой, то на выходе схемы 7 сравнения перв го узла 4 сравнения формируется сиг нал "0"

По третьему тактовому импульсу происходит запись третьего числа в регистр 1, запись второй разности (для случая, когда вторая разность больше первой) в регистр 6 первого узла 4 сравнения, запись информации с выходов коммутаторов 8 предыдущих узлов 4 сравнения в регистры 6 последующих узлов 4 сравнения.

Так как знак разности проходит через все регистры и коммутаторы, на сумматоре-вычитателе 9 происходит суммирование (если сортируемое число меньше заданного) или вычитаРежим определения числа, ближайшего к заданному показан в табл. 1.

1341631

10+0=10

+4

10-1=9

10+2=12, +5

10-2=8

10+4=14

+5 +5 показан в табл. 2.

Режим сортировки по возрастанию

Т а б л и ц а 2

TU ш 1 m=2 ш=З ш=4 m=5

Примечание

12

12

14

10

Режим сортировки по убыванию по- казан в ! табл. 3.

T à á ë H ö à 3

TU ш 1 m = 2 ш=З m=-4 m=5 Примечание

1 (8-15) =-7 0

2 -7 (12-15) =-3 О

0 (9-15) =-6 -3

0 (10-15) =-3 -3

0 (14-15) =-1

-3 -3

-2 +2

+4 -2

+5 +4

При считывании разность устанавливается в состояние 4 например, +5) В регистр 2 записывается минимальное число "0"

При считывании эти числа складываются (вычитаются с "0" регистра 2 на сумматоре вычитателе 9

В регистр 2 заносится число (1111)

15 для дан-, ного примера

1341631

8 гистра (i+1)-ro узла сравнения, соответствующие информационные входы вторых групп схем сравнения и коммутаторов всех углов сравнения объединены, отличающееся тем, что, с целью расширения функциональных воэможностей за счет определения чисел, ближайших к заданному, в него введены .вычитатель, сумматор-вычитатель и ре10 гистр заданного числа, причем выходы разрядов входного регистра соединены с входами уменьшаемого вычитателя,. входы вычитаемого которого соединены с вхоДами. первой группы сумматора-вы15 читателя и выходами разрядов регистра заданного числа, информационные входы которого являются входами заданного числа устройства, выходы разности вычитателя подключены к информационным входам регистра первого узла сравнения и информационным входам вторых групп схем сравнения коммутаторов всех узлов сравнения, выход знакового разряда вычитателя подключен к входу знакового разряда регистра первого узла сравнения,и входам знаковых разрядов второй группы коммутаторов всех узлов сравнения,а каждом узле сравнения выход знакового разряда регистра подключен к входу знакового разряда второй группы, информационные выходы коммутатора (m-1)-ro узла сравнения соединены с информационными входами второй группы сумматора-вычитателя, управляющий вход которого соединен с выходом знака коммутатора (m-1)-ro узла сравнения, выход знака коммутатора i-ro узла сравнения подключен к входу знакового разряда регистра (i+1)-го узла сравнения, выходы сумматора-вычитателя соединены с информационными входами выходного регистра, вход начальной установки устройства подключен к входам установки в

"0" регистров всех узлов сравнения.

При считывании информации в регистр 10 происходит следующее: 1,см. табл. 4).

Т а б л и ц а 4

TU (15-1) = 14 (15-3) = 12 (15-5) = 10 (15-6) = 9 (15-7) = 8

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

Устройство для сортировки чисел, содержащее входной и выходной регистры и (m-1) узлов сравнения, где m — - количество чисел сортируемого массива, каждый узел сравнения содержит элемент И, схему сравнения коммутатор и регистр выходы разрядов которого соединены с соответствующи-, ми информационными входами первых групп схемы сравнения и групп ком- 30 мутатора, управляющий вход которого соединен с выходом схемы сравнения и первым входом элемента И, выход которого подключен к входу управления записью регистра, вход тактовых импульсов устройства подключен к входам управления записью входного и выходного регистров и вторым входам элементов И всех узлов сравнения,входы сортируемых чисел устройст- 40 ва соединены с информационными входами входного регистра, информаци онные выходы коммутатора i-ro узла

"сравнения, где i = 1,2.. .,(ш-2),сое-.. динены с информационными входами ре- 45

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

Техред M.Äèäûê Корректор С.Черни

Редактор Е. Копча

Заказ 4437/52 Тираж 672 Подписное .ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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