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

 

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

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

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

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

Необходимость сортировки нескольких последовательностей чисел с изменяемым уровнем сортировки возникает, например, в радиолокации при синтезе оптимальных законов управления одноканальным информационным средством (ИС) при наблюдении за m объектами. При этом под m-й последовательностью понимается последовательность l дискретных значений программной функции M_i ((i= ) ). Согласно определению программной функции i-й объект наблюдается в j-й момент времени ( (j=)) в том случае, если M_i(j) max M_k(j), k= M_i(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 обозначены 1₁-1_l группы элементов И по элементов И в каждой; 2₁-2_m элементы И; 3 генератор импульсов; 4 управляющий счетчик; 5 управляющий триггер; 6 управляющий элемент И; 7 управляющий элемент ИЛИ; 8₁-8_m триггеры; 9 вход запуска устройства; 10₁-10_l элементы ИЛИ; 11₁-11_m счетчики чисел; 12₁-12_l элементы И; 13₁-13_l выходы устройства, каждый из которых имеет m шин; 14₁-14_l группы счетчиков чисел по m счетчиков чисел в каждой; 15₁-15_l группы триггеров по m триггеров в каждой.

На фиг. 2 соответственно отмечены следующие цифры: по оси абсцисс на первом (верхнем) графике номер элемента последовательностей, подлежащий сортировке (от 1 до 10), на втором, третьем и четвертом графиках номер выхода устройства 13₁-13₁₀ (цифра 13 опущена) от 1 до 10. По оси координат: на первом графике величин чисел последовательностей M_i(i=), на втором, третьем и четвертом графиках величина логического сигнала (0 или 1) на шинах соответственно первой (первые выводы всех выходов устройства 13₁-13₁₀), второй (вторые выводы всех выходов устройства 13₁-13₁₀) и третьей (третьи выводы всех выходов устройства 13₁-13₁₀).

Устройство содержит генератор импульсов 3, управляющий триггер 5, управляющий счетчик 4, управляющий элемент И 6, l групп l₁-1_l элементов И 2₁-2_m по m элементов И в каждой, где l количество чисел последовательности, m количество последовательностей, l групп 14₁-14_lсчетчиков чисел 11₁-11_m по m счетчиков чисел в каждой, l элементов ИЛИ 10₁-10_l, l групп 15₁-15_l триггеров 8₁-8_m по m триггеров в каждой, l элементов И 12₁-12_l, управляющий элемент ИЛИ 7.

Причем вход запуска устройства 9 соединен с входом установки в единицу управляющего триггера 5 и входом запуска генератора импульсов 3, выход которого соединен с первым входом управляющего элемента И 6, второй вход которого соединен с прямым выходом управляющего триггера 5, инверсный выход которого соединен с входом останова генератора импульсов 3, а вход установки в ноль с выходом переполнения управляющего счетчика 4, выходы счетчиков чисел 11₁-11_m групп с первой по l-ю 14₁-14_lсоединены с входами соответствующих элементов ИЛИ 10₁-10_l, выход управляющего элемента И 6 соединен с первыми входами элементов И 2₁-2_mвсех групп 1₁-1_l, вторые входы элементов И 2₁-2_m i-й группы 1, где i 1,2,l, cоединены с выходом i-го элемента И 12_i, входы которого соединены с инверсными выходами триггеров 8₁-8_m i-й группы 15_i, прямые выходы которых являются выходами соответствующей группы устройства 13_i, а входы установки в единицу подключены к входу соответствующего элемента ИЛИ 10_i и выходу соответствующего счетчика чисел 11₁-11_m i-й группы 14_i, cчетный вход которого соединен с выходом соответствующего элемента И 2₁-2_m i-й группы 1_i, выходы всех элементов И 12₁-12_l подключены к входам управляющего элемента ИЛИ 7, выход которого соединен со счетным входом управляющего счетчика 4, вход запуска устройства 9 подключен к входам установки в ноль триггеров 8₁-8_m всех групп 15₁-15_l.

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

Пусть сортировке подлежат m последовательностей M_i ( i=) по l чисел, а значение уровня сортировки равно _o В исходном состоянии в счетчики чисел 11₁-11_m всех групп 14₁-14_lзаписаны значения последовательностей М₁-M_m, так что в q-й счетчик числа 11_q р-й группы 14_р записано число, соответствующее р-му значению последовательности М_q. Кроме того, в управляющий счетчик 4 записано дополнение числа _o до его переполнения.

Пусковой импульс поступает на вход 9 устройства и запускает генератор 3, переводит управляющий триггер 5 в единичное состояние, а триггеры 8₁-8_m всех групп 15₁-15_l в нулевое. Потенциал на единичном выходе управляющего триггера 5 разрешает прохождение сигнала через управляющий элемент И 6 импульсов с включенного генератора 3 на первые входы элементов И 2₁-2_m всех групп 1₁-1_l. На вторые входы этих элементов подается единичный сигнал, формируемый соответствующими элементами И 12₁-12_l по единичным сигналам с инверсных выходов триггеров 8₁-8_mсоответствующих групп 15₁-15_l. Следовательно, на выходах элементов И 2₁-2_m групп 1₁-1_l формируются единичные сигналы, поступающие на вход счетчиков чисел 11₁-11_m соответствующих групп 14₁-14_l.

Пусть максимальное значение M_maх maх M_i(j) последовательностей записано в счетчике числа 11₂ первой группы 14₁, т.е. M_max М₂(1). Тогда на выходе счетчика числа 11₂ группы 14₁ импульс переполнения появится в первую очередь. При этом единичный сигнал будет подан на единичный вход триггера 8₂ группы 15₁, что переведет его в единичное состояние. Нулевой сигнал с его инверсного выхода запретит формирование на выходе элемента И 12 единичного сигнала И, следовательно, группы 1₁элементов И 2₁-2_m запретит прохождение единичных сигналов от управляющего элемента И 6. Таким образом, только на выводе второй шины выхода устройства 13₁ сформируется единичный сигнал, а на выходах остальных шин выхода устройства 13₁ нулевой.

Следующий импульс переполнения поступит со счетчика числа, где записано значение последовательности M_i (i 1,m), являющееся максимальным среди оставшихся значений в оставшиеся значения.

После каждого переполнения счетчиков чисел 11₁-11_m групп 14₁-14_lединичный сигнал с этого счетчика через соответствующий элемент ИЛИ 10₁-10_l и управляющий элемент ИЛИ 7 поступает на вход управляющего счетчика 4. При переполнении его, что соответствует достижению заданного уровня сортировки _o, импульс переполнения с его выхода переводит управляющий триггер 5 в нулевое положение. Нулевой потенциал с единичного выхода управляющего триггера 5 запрещает прохождение импульсов от генератора через управляющий элемент И 6, а потенциал единичного выхода отключает генератор 3.

Таким образом, на выходах 13₁-13_l устройства сформированы сигналы, соответствующие отсортированным значениям последовательностей М₁-M_mразномерности l при наличии ограничения на уровень сортировки =_o Рассмотрим работу устройства на примере, когда сортировке подлежат три последовательности, состоящие из 10 элементов каждая, в уровень сортировки равен 4 (см.фиг.2).

Перед началом работы в счетчики чисел 11₁-11₃ групп 14₁-10₁₀записываются значения последовательностей М₁(j) M₃(j) ( j=), так как описано выше, т. е. например, в счетчик числа 11₁ группы 14₂записано число, соответствующее второму значению первой последовательности М₁(2). Кроме того, в управляющий счетчик 4 записано дополнение до переполнения числа 4.

После поступления пускового импульса и начала поступления единичных сигналов на счетчики чисел 11₁-11₃, групп 14₁-14₁₀ происходит переполнение счетчика числа 11₂ группы 15, так как М₂(5) maх M_i(j),i=;j= . При этом сигнал переполнения поступает на единичный вход триггера 8₂ группы 15₅, переводя его в единичное состояние, что приведет в конечном счете к запрету прохождения единичных сигналов через группу 1₅ элементов И 2₁-2₃. Таким образом, только на выводе второй шины выхода устройства 13₅ будет сформирован единичный сигнал (см.фиг.2).

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

Итак, по окончании работы устройства на десяти его выходах 13₁-13₁₀сформированы совокупности сигналов по трем шинам (см.фиг.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" триггеров всех групп.

РИСУНКИ

Рисунок 1, Рисунок 2