Forbidden

You don't have permission to access /zzz_siteguard.php on this server.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ - Патент РФ 2050583
Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ
УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ

Патент Российской Федерации
Суть изобретения: Изобретение относится к автоматике, вычислительной технике и радиолокации и может быть использовано в системах оптимального управления измерительными процессами. Предлагаемое устройство позволяет сортировать m последовательностей чисел с изменяемым уровнем сортировки. Устройство содержит генератор импульсов, управляющий триггер, управляющий счетчик, управляющий элемент И, группы элементов И, группы счетчиков чисел, группы триггеров, элементы ИЛИ, элементы И и управляющий элемент ИЛИ. 2 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2050583
Класс(ы) патента: G06F7/06
Номер заявки: 5025345/09
Дата подачи заявки: 03.02.1992
Дата публикации: 20.12.1995
Заявитель(и): Хуторцев Валерий Владимирович; Строцев Андрей Анатольевич
Автор(ы): Хуторцев Валерий Владимирович; Строцев Андрей Анатольевич
Патентообладатель(и): Хуторцев Валерий Владимирович; Строцев Андрей Анатольевич
Описание изобретения: Изобретение относится к автоматике, вычислительной технике и радиолокации и может быть использовано в системах оптимального управления измерительными процессами.
Известно устройство для упорядочения n чисел, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, элементы ИЛИ, входной регистр [1]
Однако данное устройство обладает узкими функциональными возможностями, поскольку не позволяет сортировать несколько последовательностей чисел с изменяемым уровнем сортировки.
Наиболее близким по техническому решению к предлагаемому устройству является устройство для сортировки чисел, содержащее управляющий счетчик, управляющий триггер, генератор импульсов, элемент И, счетчики чисел, группы элементов И, элемент ИЛИ, счетчик номера переменной, регистры, элементы задержки [2]
Недостатком устройства является невозможность сортировки нескольких последовательностей чисел с изменяемым уровнем сортировки.
Необходимость сортировки нескольких последовательностей чисел с изменяемым уровнем сортировки возникает, например, в радиолокации при синтезе оптимальных законов управления одноканальным информационным средством (ИС) при наблюдении за m объектами. При этом под m-й последовательностью понимается последовательность l дискретных значений программной функции Mi ((i= ) ). Согласно определению программной функции i-й объект наблюдается в j-й момент времени ( (j=)) в том случае, если
Mi(j) max Mk(j), k=
Mi(j) ≥ α где α есть некоторое заданное число, характеризующее суммарное временное ограничение на работу ИС и являющееся в изобретении величиной уровня сортировки.
Указанная задача должна решаться в реальном масштабе времени, что накладывает дополнительные требования на быстродействие вычислительной системы, управляющей ИС. Таким образом, цель изобретения создание специализированных устройств, позволяющих сортировать m последовательностей чисел с изменяемым уровнем сортировки.
Это достигается тем, что в устройство, содержащее генератор импульсов, управляющий триггер, управляющий счетчик, управляющий элемент И, l групп элементов И по m элементов И в каждой, где l количество чисел последовательности, m количество последовательностей, l групп счетчиков чисел по m счетчиков чисел в каждой, первый элемент ИЛИ, причем вход запуска устройства соединен с входом установки в единицу управляющего триггера и входом запуска генератора импульсов, выход которого соединен с входом управляющего элемента И, второй вход которого соединен с прямым выходом управляющего триггера, инверсный выход которого соединен с входом останова генератора импульсов, а вход установки в ноль с выходом переполнения управляющего счетчика, выходы счетчиков чисел первой группы соединены с входами первого элемента ИЛИ, дополнительно введены следующие элементы: l групп триггеров по m триггеров в каждой, (l-1) элементов ИЛИ, l элементов И и управляющий элемент ИЛИ. Причем выходы счетчиков чисел групп с второй по l-ю cоединены с входами соответствующих элементов ИЛИ, выход управляющего элемента И соединен с первыми входами элементов И всех групп, вторые входы элементов И i-й группы, где i 1,2, l, соединены с выходом i-го элемента И, входы которого соединены с инверсными выходами триггеров i-й группы, прямые выходы которых являются выходами соответствующей группы устройства, а входы установки в единицу подключены к входу соответствующего элемента ИЛИ и выходу соответствующего счетчика чисел i-й группы, счетный вход которого соединен с выходом соответствующего элемента И i-й группы, выходы всех элементов И подключены к входам управляющего элемента ИЛИ, выход которого соединен со счетным входом управляющего счетчика, вход запуска устройства подключен к входам установки в ноль триггеров всех групп.
Введение новых структурных элементов И связей позволяет в совокупности с общими признаками расширить функциональные возможности устройства для сортировки чисел за счет сортировки последовательности чисел с изменяемым уровнем сортировки.
Предложенное устройство может быть применено в любых информационных системах, системах автоматического управления, например, в устройстве оптимального управления одноканальным информационным средством при наблюдении за объектами.
На фиг. 1 представлена схема устройства для сортировки последовательностей чисел с изменяемым уровнем сортировки; на фиг.2 диаграмма работы устройства.
Причем на фиг. 1 обозначены 11-1l группы элементов И по элементов И в каждой; 21-2m элементы И; 3 генератор импульсов; 4 управляющий счетчик; 5 управляющий триггер; 6 управляющий элемент И; 7 управляющий элемент ИЛИ; 81-8m триггеры; 9 вход запуска устройства; 101-10l элементы ИЛИ; 111-11m счетчики чисел; 121-12l элементы И; 131-13l выходы устройства, каждый из которых имеет m шин; 141-14l группы счетчиков чисел по m счетчиков чисел в каждой; 151-15l группы триггеров по m триггеров в каждой.
На фиг. 2 соответственно отмечены следующие цифры: по оси абсцисс на первом (верхнем) графике номер элемента последовательностей, подлежащий сортировке (от 1 до 10), на втором, третьем и четвертом графиках номер выхода устройства 131-1310 (цифра 13 опущена) от 1 до 10. По оси координат: на первом графике величин чисел последовательностей Mi(i=), на втором, третьем и четвертом графиках величина логического сигнала (0 или 1) на шинах соответственно первой (первые выводы всех выходов устройства 131-1310), второй (вторые выводы всех выходов устройства 131-1310) и третьей (третьи выводы всех выходов устройства 131-1310).
Устройство содержит генератор импульсов 3, управляющий триггер 5, управляющий счетчик 4, управляющий элемент И 6, l групп l1-1l элементов И 21-2m по m элементов И в каждой, где l количество чисел последовательности, m количество последовательностей, l групп 141-14lсчетчиков чисел 111-11m по m счетчиков чисел в каждой, l элементов ИЛИ 101-10l, l групп 151-15l триггеров 81-8m по m триггеров в каждой, l элементов И 121-12l, управляющий элемент ИЛИ 7.
Причем вход запуска устройства 9 соединен с входом установки в единицу управляющего триггера 5 и входом запуска генератора импульсов 3, выход которого соединен с первым входом управляющего элемента И 6, второй вход которого соединен с прямым выходом управляющего триггера 5, инверсный выход которого соединен с входом останова генератора импульсов 3, а вход установки в ноль с выходом переполнения управляющего счетчика 4, выходы счетчиков чисел 111-11m групп с первой по l-ю 141-14lсоединены с входами соответствующих элементов ИЛИ 101-10l, выход управляющего элемента И 6 соединен с первыми входами элементов И 21-2mвсех групп 11-1l, вторые входы элементов И 21-2m i-й группы 1, где i 1,2,l, cоединены с выходом i-го элемента И 12i, входы которого соединены с инверсными выходами триггеров 81-8m i-й группы 15i, прямые выходы которых являются выходами соответствующей группы устройства 13i, а входы установки в единицу подключены к входу соответствующего элемента ИЛИ 10i и выходу соответствующего счетчика чисел 111-11m i-й группы 14i, cчетный вход которого соединен с выходом соответствующего элемента И 21-2m i-й группы 1i, выходы всех элементов И 121-12l подключены к входам управляющего элемента ИЛИ 7, выход которого соединен со счетным входом управляющего счетчика 4, вход запуска устройства 9 подключен к входам установки в ноль триггеров 81-8m всех групп 151-15l.
Устройство работает следующим образом.
Пусть сортировке подлежат m последовательностей Mi ( i=) по l чисел, а значение уровня сортировки α равно αo
В исходном состоянии в счетчики чисел 111-11m всех групп 141-14lзаписаны значения последовательностей М1-Mm, так что в q-й счетчик числа 11q р-й группы 14р записано число, соответствующее р-му значению последовательности Мq. Кроме того, в управляющий счетчик 4 записано дополнение числа αo до его переполнения.
Пусковой импульс поступает на вход 9 устройства и запускает генератор 3, переводит управляющий триггер 5 в единичное состояние, а триггеры 81-8m всех групп 151-15l в нулевое. Потенциал на единичном выходе управляющего триггера 5 разрешает прохождение сигнала через управляющий элемент И 6 импульсов с включенного генератора 3 на первые входы элементов И 21-2m всех групп 11-1l. На вторые входы этих элементов подается единичный сигнал, формируемый соответствующими элементами И 121-12l по единичным сигналам с инверсных выходов триггеров 81-8mсоответствующих групп 151-15l. Следовательно, на выходах элементов И 21-2m групп 11-1l формируются единичные сигналы, поступающие на вход счетчиков чисел 111-11m соответствующих групп 141-14l.
Пусть максимальное значение Mmaх maх Mi(j) последовательностей записано в счетчике числа 112 первой группы 141, т.е. Mmax М2(1). Тогда на выходе счетчика числа 112 группы 141 импульс переполнения появится в первую очередь. При этом единичный сигнал будет подан на единичный вход триггера 82 группы 151, что переведет его в единичное состояние. Нулевой сигнал с его инверсного выхода запретит формирование на выходе элемента И 12 единичного сигнала И, следовательно, группы 11элементов И 21-2m запретит прохождение единичных сигналов от управляющего элемента И 6. Таким образом, только на выводе второй шины выхода устройства 131 сформируется единичный сигнал, а на выходах остальных шин выхода устройства 131 нулевой.
Следующий импульс переполнения поступит со счетчика числа, где записано значение последовательности Mi (i 1,m), являющееся максимальным среди оставшихся значений в оставшиеся значения.
После каждого переполнения счетчиков чисел 111-11m групп 141-14lединичный сигнал с этого счетчика через соответствующий элемент ИЛИ 101-10l и управляющий элемент ИЛИ 7 поступает на вход управляющего счетчика 4. При переполнении его, что соответствует достижению заданного уровня сортировки αo, импульс переполнения с его выхода переводит управляющий триггер 5 в нулевое положение. Нулевой потенциал с единичного выхода управляющего триггера 5 запрещает прохождение импульсов от генератора через управляющий элемент И 6, а потенциал единичного выхода отключает генератор 3.
Таким образом, на выходах 131-13l устройства сформированы сигналы, соответствующие отсортированным значениям последовательностей М1-Mmразномерности l при наличии ограничения на уровень сортировки α=αo
Рассмотрим работу устройства на примере, когда сортировке подлежат три последовательности, состоящие из 10 элементов каждая, в уровень сортировки равен 4 (см.фиг.2).
Перед началом работы в счетчики чисел 111-113 групп 141-1010записываются значения последовательностей М1(j) M3(j) ( j=), так как описано выше, т. е. например, в счетчик числа 111 группы 142записано число, соответствующее второму значению первой последовательности М1(2). Кроме того, в управляющий счетчик 4 записано дополнение до переполнения числа 4.
После поступления пускового импульса и начала поступления единичных сигналов на счетчики чисел 111-113, групп 141-1410 происходит переполнение счетчика числа 112 группы 15, так как М2(5) maх Mi(j),i=;j= . При этом сигнал переполнения поступает на единичный вход триггера 82 группы 155, переводя его в единичное состояние, что приведет в конечном счете к запрету прохождения единичных сигналов через группу 15 элементов И 21-23. Таким образом, только на выводе второй шины выхода устройства 135 будет сформирован единичный сигнал (см.фиг.2).
Далее устройство работает аналогично описанному до переполнения управляющего счетчика 4, после чего генератор импульсов 3 отключается.
Итак, по окончании работы устройства на десяти его выходах 131-1310сформированы совокупности сигналов по трем шинам (см.фиг.2), которые позволяют выбрать следующие четыре (по величине уровня сортировки, αо 4) числа:
4-й элемент третьей последовательности (код на 4-м выходе устройства 13: 00, т.е. единичный сигнал на выходе 3-й шины);
5-й элемент второй последовательности (код на 5-м выходе устройства 13: 010, т.е. единичный сигнал на выходе 2-й шины);
6-й элемент первой последовательности (код на 6-м выходе устройства 13: 100, т.е. единичный сигнал на выводе 1-й шины);
7-й элемент первой последовательности (код на 7-м выходе устройства 13: 100, т.е. единичный сигнал на выводе 1-й шины).
Все блоки устройства могу быть выполнены на основе существующей элементной базы.
Формула изобретения: УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ, содержащее генератор импульсов, управляющий триггер, управляющий счетчик, управляющий элемент И, l групп элементов И по m элементов И в каждой, где l количество чисел последовательности, m количество последовательностей, l групп счетчиков чисел по m счетчиков чисел, первый элемент ИЛИ, причем вход запуска устройства соединен с входом установки в "1" управляющего триггера и входом запуска генератора импульсов, выход которого соединен с первым входом управляющего элемента И, второй вход которого соединен с прямым выходом управляющего триггера, инверсный выход которого соединен с входом останова генератора импульсов, а вход установки в "0" с выходом переполнения управляющего счетчика, выходы счетчиков чисел первой группы соединены с входами первого элемента ИЛИ, отличающееся тем, что в него введены l групп триггеров по m триггеров в каждой, l 1 элементов ИЛИ, l элементов И и управляющий элемент ИЛИ, причем выходы счетчиков чисел групп с второй по l-ю соединены с входами соответствующих элементов ИЛИ, выход управляющего элемента И соединен с первыми входами элементов И всех групп, вторые входы элементов И i-й группы, где i 1, 2, l, соединены с выходом i-го элемента И, входы которого соединены с инверсными выходами триггеров i-й группы, прямые выходы которых являются выходами соответствующей группы устройства, а входы установки в "1" подключены к входу соответствующего элемента ИЛИ и входу соответствующего счетчика чисел i-й группы, счетный вход которого соединен с выходом соответствующего элемента И i-й группы, выходы всех элементов И подключены к входам управляющего элемента ИЛИ, выход которого соединен со счетным входом управляющего счетчика, вход запуска устройства подключен к входам установки в "0" триггеров всех групп.