Устройство для сортировки чисел
Изобретение относится к вычислительной технике и предназначено для сортировки (ранжирования) 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-х ключей всех групп, а выходы являются дополнительными выходами устройства.
