Устройство для сортировки чисел Советский патент 1987 года по МПК G06F7/08 

13

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

1

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

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

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

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

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

1

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

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

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

1, когда содержимое регистра 6

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

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

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

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

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

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

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

коммутатора 8. На выходе всех схем 7 сравнения формируется сигнал 1

По второму тактовому импульсу в регистр 1 записывается второе из массива,в регистр 6 первого узла 4 сравнения переписывается число из вычитателя 3, а в регистры 6 остальных узлов 4 сравнения записывается информация с выходов коммутаторов 8, т.е. нули. В регистры 6 записыва ется и знак разности,который присутствует и на выходе коммутаторов 8. Вторая разность сравнивается с содержимым регистра 6 каждого узла .4 сравнения, и если вторая разность больше первой,то на выходе всех схем 7 сравнения формируется сигнал 1.Если же вторая разность меньше первой, то на выходе схемы 7 сравнения первго узла 4 сравнения формируется сиг нал О,

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

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

О

О

(8-10)-2 ООО

-.2 (12-10)+2 ОО

-2+2 (9-10).-1 О

-2

(14-10) +4

+2

-2

-1 (9

+2

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

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

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

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

Работа устройства при сортировке чисел: 8, 12, 9, 10, 14 при заданном числе 10 происходит следующим образом.

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

Таблица 1

О

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

X X

X

-1 (9-9)0 X

+2 -1

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

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

Т а б л и ц а 3

Продолжение табл.1

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

Т а б л и ц а 2

В регистр 2 записывается минимальное число О

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

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

Таблица4

ти

Т

10

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

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

дам элементов И всех узлов сравнения,входы сортируемых чисел устройст- 40 (i+l)-ro узла сравнения, выходы сум- ва соединены с информационными матора-вычитателя соединены с инфор- входами входного регистра, информаци- мационными входами выходного регист- онные выходы коммутатора i-ro узла ра, вход начальной установки устрой- сравнения, где i 1,2,,.,,(m-2),сое-, ства подключен к входам установки в динены с информационными входами ре- 45 С регистров всех узлов сравнения.

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

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

Техред М.Дидык Корректор С.Черни

Заказ 4437/52Тираж 672Подписное

.ВНИИПИ Государственного комитета СССР

по дел-ам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

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

30 подключен к входу знакового разряда второй группы, информационные выходы коммутатора (т-1)-го узла сравнения соединены с информационными входами второй группы сумматора-вычитателя,

35 управляющий вход которого соединен с выходом знака коммутатора Чш-О-го узла сравнения, выход знака коммутатора i-ro узла сравнения подключен к входу знакового разряда регистра

20

25

40 (i+l)-ro узла сравнения, выходы сум- матора-вычитателя соединены с инфор- мационными входами выходного регист- ра, вход начальной установки устрой- ства подключен к входам установки в 45 С регистров всех узлов сравнения.

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