устройство для сортировки последовательностей чисел

Классы МПК:G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации
Автор(ы):,
Патентообладатель(и):Хуторцев Валерий Владимирович,
Строцев Андрей Анатольевич
Приоритеты:
подача заявки:
1992-02-03
публикация патента:

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

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

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ, содержащее генератор импульсов, управляющий триггер, управляющий счетчик, управляющий элемент И, 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" триггеров всех групп.

Описание изобретения к патенту

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

Известно устройство для упорядочения n чисел, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, элементы ИЛИ, входной регистр [1]

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

Наиболее близким по техническому решению к предлагаемому устройству является устройство для сортировки чисел, содержащее управляющий счетчик, управляющий триггер, генератор импульсов, элемент И, счетчики чисел, группы элементов И, элемент ИЛИ, счетчик номера переменной, регистры, элементы задержки [2]

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

Необходимость сортировки нескольких последовательностей чисел с изменяемым уровнем сортировки возникает, например, в радиолокации при синтезе оптимальных законов управления одноканальным информационным средством (ИС) при наблюдении за m объектами. При этом под m-й последовательностью понимается последовательность l дискретных значений программной функции Mi ((i= устройство для сортировки последовательностей чисел, патент № 2050583) ). Согласно определению программной функции i-й объект наблюдается в j-й момент времени ( (j=устройство для сортировки последовательностей чисел, патент № 2050583)) в том случае, если

Mi(j) max Mk(j), k=устройство для сортировки последовательностей чисел, патент № 2050583

Mi(j) устройство для сортировки последовательностей чисел, патент № 2050583 устройство для сортировки последовательностей чисел, патент № 2050583 где устройство для сортировки последовательностей чисел, патент № 2050583 есть некоторое заданное число, характеризующее суммарное временное ограничение на работу ИС и являющееся в изобретении величиной уровня сортировки.

Указанная задача должна решаться в реальном масштабе времени, что накладывает дополнительные требования на быстродействие вычислительной системы, управляющей ИС. Таким образом, цель изобретения создание специализированных устройств, позволяющих сортировать 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=устройство для сортировки последовательностей чисел, патент № 2050583), на втором, третьем и четвертом графиках величина логического сигнала (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=устройство для сортировки последовательностей чисел, патент № 2050583) по l чисел, а значение уровня сортировки устройство для сортировки последовательностей чисел, патент № 2050583 равно устройство для сортировки последовательностей чисел, патент № 2050583o

В исходном состоянии в счетчики чисел 111-11m всех групп 141-14lзаписаны значения последовательностей М1-Mm, так что в q-й счетчик числа 11q р-й группы 14р записано число, соответствующее р-му значению последовательности Мq. Кроме того, в управляющий счетчик 4 записано дополнение числа устройство для сортировки последовательностей чисел, патент № 2050583o до его переполнения.

Пусковой импульс поступает на вход 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. При переполнении его, что соответствует достижению заданного уровня сортировки устройство для сортировки последовательностей чисел, патент № 2050583o, импульс переполнения с его выхода переводит управляющий триггер 5 в нулевое положение. Нулевой потенциал с единичного выхода управляющего триггера 5 запрещает прохождение импульсов от генератора через управляющий элемент И 6, а потенциал единичного выхода отключает генератор 3.

Таким образом, на выходах 131-13l устройства сформированы сигналы, соответствующие отсортированным значениям последовательностей М1-Mmразномерности l при наличии ограничения на уровень сортировки устройство для сортировки последовательностей чисел, патент № 2050583=устройство для сортировки последовательностей чисел, патент № 2050583o

Рассмотрим работу устройства на примере, когда сортировке подлежат три последовательности, состоящие из 10 элементов каждая, в уровень сортировки равен 4 (см.фиг.2).

Перед началом работы в счетчики чисел 111-113 групп 141-1010записываются значения последовательностей М1(j) M3(j) ( j=устройство для сортировки последовательностей чисел, патент № 2050583), так как описано выше, т. е. например, в счетчик числа 111 группы 142записано число, соответствующее второму значению первой последовательности М1(2). Кроме того, в управляющий счетчик 4 записано дополнение до переполнения числа 4.

После поступления пускового импульса и начала поступления единичных сигналов на счетчики чисел 111-113, групп 141-1410 происходит переполнение счетчика числа 112 группы 15, так как М2(5) maх Mi(j),i=устройство для сортировки последовательностей чисел, патент № 2050583;j= устройство для сортировки последовательностей чисел, патент № 2050583. При этом сигнал переполнения поступает на единичный вход триггера 82 группы 155, переводя его в единичное состояние, что приведет в конечном счете к запрету прохождения единичных сигналов через группу 15 элементов И 21-23. Таким образом, только на выводе второй шины выхода устройства 135 будет сформирован единичный сигнал (см.фиг.2).

Далее устройство работает аналогично описанному до переполнения управляющего счетчика 4, после чего генератор импульсов 3 отключается.

Итак, по окончании работы устройства на десяти его выходах 131-1310сформированы совокупности сигналов по трем шинам (см.фиг.2), которые позволяют выбрать следующие четыре (по величине уровня сортировки, устройство для сортировки последовательностей чисел, патент № 2050583о 4) числа:

4-й элемент третьей последовательности (код на 4-м выходе устройства 13: 00, т.е. единичный сигнал на выходе 3-й шины);

5-й элемент второй последовательности (код на 5-м выходе устройства 13: 010, т.е. единичный сигнал на выходе 2-й шины);

6-й элемент первой последовательности (код на 6-м выходе устройства 13: 100, т.е. единичный сигнал на выводе 1-й шины);

7-й элемент первой последовательности (код на 7-м выходе устройства 13: 100, т.е. единичный сигнал на выводе 1-й шины).

Все блоки устройства могу быть выполнены на основе существующей элементной базы.

Класс G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации

способ и система поиска нарушений авторских прав на изображения -  патент 2515706 (20.05.2014)
медиа-процессор для организации мультимедийных данных -  патент 2487395 (10.07.2013)
интеграция рекламы и расширяемые темы для операционных систем -  патент 2473127 (20.01.2013)
устройство сортировки двоичных чисел -  патент 2445678 (20.03.2012)
устройство перепаковки потоков для ввода данных -  патент 2414742 (20.03.2011)
устройство сортировки двоичных чисел -  патент 2383052 (27.02.2010)
селектор двоичных чисел -  патент 2365975 (27.08.2009)
устройство селекции двоичных чисел -  патент 2363038 (27.07.2009)
устройство сравнения двоичных чисел -  патент 2353966 (27.04.2009)
способ и устройство для обработки графической информации, имеющейся на почтовых отправлениях -  патент 2349395 (20.03.2009)
Наверх