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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН (5D4 С 06 F 06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (61) 1203508 (21) 4117022/24-24 (22) 20 ° 05.86 (46) 15.07.88. Бюл. и 26 (71) Северо-Западный заочный политехнический институт (72) Л.В.Боброва, В.С.Ильичев, Ф.А.Ульяновский, В.В.Щипцов и и А.Г.Якубовская (53) 681.325 (088.8) (56) Авторское свидетельство СССР

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

„„SU„„1418021 А 2 за счет возможности отбора оптимальных наборов цанных, Устройство содержит группу элементов сравнения (компараторов) 1, группы ключей 2, элементы 3, 4 задержки, масштабируюшие элементы 5, блок 6 умножения, комцарВТор 7, коммутатор 8, дополнительные ключи 9. Элементы задержки в схеме служат для временного согласования отдельных блоков, компараторы 1 в совокупности с ключами 2 — для определения амплитудного интервала, в котором находятся входные данные, компаратор 7 в совокупности с коммутатором, блоком умножения, дополнительными ключами и масштабируюшими элементами — для выцеления оптимальных наборов данных, 1 ил.

1410021

Изобретение относится к вь1числительной технике и является дополнительным к основномУ авттсв. II"-1203508.

Цель изобретения — расширение

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

На чертеже показана блок-схема устройства. 1О

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

Устройство предназначено для ранрования N входных сигналов по амп- итуде и выделения оптимальных по 2О екоторому признаку данных. Если на ход поступают сигналы х,х ... х 1т 2р х йв о на первых выходах должны быть иг калы,25

Х (Х, 1 1 р а, ilр,i+ 1 р т с о р — х, х>р х > х;;

) = 1,...,N; j 9 М, j ф

° ° но о С а с с сс с " с с ,и

Х Х Д вЂ” 1рвнар в

1! п4-1 р . o ров

" .е. на первом из этих выходов долл ен быть сигнал, минимальный по амптуде, на N-ом — максимальный по мплитуде °

На вторых выходах появляются сиг=Налы только в том случае, если вход11ая совокупность соответствует некоч орой оптимизирующей функции у = opt (х, х,...,х ).

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

Предварительно устанавливают N у!ровней градации для одновходовых к омпараторов 1 и 7. Эти уровни один аковы для всех компараторов 1-1-1-N

ai определяются для них спедующим обр азом. Пределы для изменения амплитудны при появлении сигнала на первых х >

ЗО вь дах К от хм,„до Х„„„Ф

1вК Х ИК на вторых выхохах от -на — — ЙМЛ вЂ” + с

N д,о 2 на третьих от 55

N ркс Хм

N и т.д. Пределы с во 3--в — т ——

»кк Х м»»»»

N для изменения амплиту1 ды входного сигнала, необходимого для появления сигнала на И-м выходе компараторов 1, от (N-1) " " +

+ »1 до х, . Здесь »1 — произвольно выбираемая малая величина. Для компаратора 7 эти градации определяются в зависимости от вида функции у =

opt: (х,...,х ).

Компараторы 1 и 7 могут быть выполнены на базе ЭЛТ ЛФ9П-политрон.

Блоки S-9 служат для одновременного выделения тех групп переменных х, х .. .,х, которые удовлетворяют оптимизирующей функции вида и у = opt П С х

1 1 где i 1...N х; — входные переменные, С; — весовые коэффициенты.

Для задания весовых коэффициентов

С; в схеме используются масштабирующие элементы 5 †-5-N для перемножения значений С на х., = I, N—

< блок умножения. Компаратор 7 в совокупности с коммутатором 8 необходимы для задания вида оптимизирующей функции. Например, если необхо,цимо выделить набор переменных

Х 9 X 9 Х соотве тствующий MHHH

2Р 9» вр

»» муму произведения П C х, на выход

1» 1 1Р коммутатора 8 подключается .его первый вход (в этом случае на выходе коммутатора 8 будет сигнал только в том случае, если на вход ключа поступил минимальный сигнал, что равносильно появлению сигнала на его первом выходе) .

Если необходимо выделить набор пер™енн 1 х 2.,, 9хяq соответствующий максимальному произведению

1"1 С;х °, на выход коммутатора подключается его последний вход.

На вход устрой тва поступает в общем случае N переменныхх1,Х2р ° - ° р -Iepes время задержки 2, обусловленное элементом 4р эти переменные поступают на входы К 1. Пусть величина х, находится в первом амплитудном интервале (т.е. х, с х, х (x ( х, (х ), Это значит, что появится

1 сигнал на первом выходе К 1 — 1 (т ° е. на урпавля ощем входе ключа 2-1-1).

IIyc ть величина х2 находится во втором амплитудном интервале (т.е.

Х ) Х1s Х Х Х2 (

Это значит, что появится сигнал на

1410021

15 втором выходе К1-2 (т.е..на управляющем входе ключа 2-2-2).

Наконец, пусть х находится в

hl

N-ом амплитудном интервале (х ) х

М < х„) х,. ° .,х,„) х„,) . Это значит, что появится сигнал на N-ом выходе

K1-N (т.е. на управляющем входе ключа 2-N-N).

В результате будут открыты ключи

2 -1-1, 2-2-2,...,2-N-N Поскольку одновременно с поступлением сигналов на управляющие входы ключей с выходов К на их информационные входы поступают сигналы с входа устройства, задержанные до данного момента времени элементами 3 задержки, на выходе устройства будут величины у, = х а х с х ... с х

Е у =х, х (x ах ...(х

Е у,„=х ) х ... ) х

В общем случае, если не выполняется условие х, а х а х (х, (х, на первом выходе устройства н будет величина у, = х „„, на втором у = х ", х (; х, 1 = 1,...,И, j ) i а на последнем выходе — велиУя = x „„, На входы элементов (5-1)-(5-N) переменные х „ х,...,х„ поступают на t . раньше, чем на входы компараторов 1. С выхода масштабирующих элементов промасштабированные переменные

С,х „ С х,...,С„х,„ поступают на вход блока б, на выходе которого появляется сигнал, пропорциональный величине Г1 С;х, который поступает

« минимальное значение Л С,х. а с

< последнего, е ли на входе максимальное значение << С.х..

1 1

Таким образом, если задана оптимизирующая функция у = min П,С,.х,, 20

50 сигнал на выходе коммутатора 8 будет только в том случае, если набор х.„ х,...,х,„ является оптимальным. Пока переменные х <, х,...,х„ не удовлет- . уф ° ° ° ф воряют требованию оптимальности, на выходе коммутатора 8 сигнал отсутствует, ключи (9-1)-(9-N) закрыты и сигналы будут только на первых N выходах устройства.

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

8 откроет ключи 9 и на вторых выходах устройства появится ранжированный набор переменных х<, х,...,х,„, удовлетворяющих оптимизирующей функции.

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

Устройство для сортировки чисел по авт.св. Ф 1203508, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей за счет возможности отбора оптимальных наборов данных, в него введены N масштабирующих элементов, блок умножения, дополнительный компаратор, коммутатор, N дополнительных элементов задержки, N дополнительных ключей, причем каждый из Н информационных входов устройства соединен с соответствующим входом масштабирующего элемента и через дополнительные элементы задержки с соответствующим входом компаратора, выход каждого масштабирующего элемента соединен с соответствующим входом блока умножения, выход которого соединен с входом дополнительного компаратора, N выходов которого соединены с соответствующими входами коммутатора, выход которого соединен с управляющими входами дополнительных ключей, информационные входы которых соединены с соответствующими объединенными выхо" дами j-х ключей всех групп, а выходы являются дополнительными выходами устройства.