ранговый сортировщик

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

Ранговый сортировщик, содержащий n реляторов, каждый из которых содержит объединенные выходами замыкающий и размыкающий ключи, два устройства выборки/хранения, элемент MIN, элемент МАХ и булевый инвертор, подсоединенный выходом и входом соответственно к входу записи первого устройства выборки/хранения и входу записи второго устройства выборки/хранения, второму управляющему входу релятора, первый управляющий вход которого образован входом управления замыкающего, размыкающего ключей, в каждом реляторе первый, второй входы и выход элемента МАХ соединены соответственно с вторым, первым входами элемента MIN и информационным входом второго устройства выборки/хранения, подключенного выходом к информационному входу первого устройства выборки/хранения, выход которого соединен с входом размыкающего ключа, подсоединенного выходом к второму входу элемента MIN, первый вход и выход которого соединены соответственно с информационным входом и первым выходом релятора, опорный вход которого образован входом замыкающего ключа, первый выход каждого предыдущего релятора соединен с информационным входом последующего релятора, а второй выход i-го и первый выход n-го реляторов подключены соответственно к i-му и (n+1)-му выходам рангового сортировщика, информационный вход и первый, второй настроечные входы которого образованы соответственно информационным входом первого релятора и объединенными первыми, объединенными вторыми управляющими входами всех реляторов, отличающийся тем, что в каждом реляторе выход элемента МАХ соединен с вторым выходом релятора, а опорный вход первого релятора образует дополнительный информационный вход рангового сортировщика.

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

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

Известны ранговые сортировщики (см., например, фиг.1 в описании изобретения к патенту РФ 2240598, кл. G06G 7/25, 2004 г.), которые выполняют сортировку n+1 аналоговых сигналов по их ранговым признакам.

К причине, препятствующей достижению указанного ниже технического результата при использовании известных ранговых сортировщиков, относится сложное управление, обусловленное тем, что для выполнения сортировки требуется n+1 периодов импульсного управляющего сигнала.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятый за прототип, ранговый сортировщик (фиг.1 в описании изобретения к патенту РФ 2284573, кл. G06G 7/25, 2006 г.), который содержит n реляторов и выполняет сортировку n+1 аналоговых сигналов по их ранговым признакам.

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится сложное управление, обусловленное тем, что для выполнения сортировки требуется n+1 периодов импульсного управляющего сигнала.

Техническим результатом изобретения является упрощение управления за счет обеспечения сортировки n+1 аналоговых сигналов по их ранговым признакам с помощью меньшего количества периодов импульсного управляющего сигнала.

Указанный технический результат при осуществлении изобретения достигается тем, что в ранговом сортировщике, содержащем n реляторов, каждый из которых содержит объединенные выходами замыкающий и размыкающий ключи, два устройства выборки/хранения, элемент MIN, элемент МАХ и булевый инвертор, подсоединенный выходом и входом соответственно к входу записи первого устройства выборки/хранения и входу записи второго устройства выборки/хранения, второму управляющему входу релятора, первый управляющий вход которого образован входом управления замыкающего, размыкающего ключей, в каждом реляторе первый, второй входы и выход элемента МАХ соединены соответственно с вторым, первым входами элемента MIN и информационным входом второго устройства выборки/хранения, подключенного выходом к информационному входу первого устройства выборки/хранения, выход которого соединен с входом размыкающего ключа, подсоединенного выходом к второму входу элемента MIN, первый вход и выход которого соединены соответственно с информационным входом и первым выходом релятора, опорный вход которого образован входом замыкающего ключа, первый выход каждого предыдущего релятора соединен с информационным входом последующего релятора, а второй выход i-го и первый выход n-го реляторов подключены соответственно к i-му и (n+1)-му выходам рангового сортировщика, информационный вход и первый, второй настроечные входы которого образованы соответственно информационным входом первого релятора и объединенными первыми, объединенными вторыми управляющими входами всех реляторов, особенность заключается в том, что в каждом реляторе выход элемента МАХ соединен с вторым выходом релятора, а опорный вход первого релятора образует дополнительный информационный вход рангового сортировщика.

На фиг.1 и фиг.2 представлены соответственно схема предлагаемого рангового сортировщика и временные диаграммы управляющих сигналов.

Ранговый сортировщик содержит n реляторов 1 ₁, ..., 1_n. Каждый релятор содержит замыкающий и размыкающий ключи 2₁ и 2 ₂, первое и второе устройства выборки/хранения 3 ₁ и 3₂, элемент MIN 4, элемент МАХ 5 и булевый инвертор 6, причем первый, второй входы и выход элемента 5 соединены соответственно с вторым, первым входами элемента 4 и информационным входом устройства 3₂ , подключенного входом записи и выходом соответственно к входу инвертора 6 и информационному входу устройства 3 ₁, вход записи и выход которого соединены соответственно с выходом инвертора 6 и входом ключа 2₂ , подсоединенного выходом к выходу ключа 2₁ и второму входу элемента 4, первый вход и выход которого соединены соответственно с информационным входом и первым выходом релятора, опорный вход, первый, второй управляющие входы и второй выход которого образованы соответственно входом ключа 2 ₁, входом управления ключей 2₁, 2 ₂, входом записи устройства 3₂ и выходом элемента 5. Первый выход каждого предыдущего релятора соединен с информационным входом последующего релятора, а второй выход релятора 1_i и первый выход релятора 1_n подключены соответственно к i-му и (n+1)-му выходам рангового сортировщика, информационный и дополнительный информационный и первый, второй настроечные входы которого образованы соответственно информационным и опорным входами релятора 1₁ и объединенными первыми, объединенными вторыми управляющими входами реляторов 1₁, ..., 1_n.

Работа предлагаемого рангового сортировщика осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно двоичные сигналы у₁, у₂ {0,1} (фиг.2), причем длительность t высокого уровня сигнала у₂ должна удовлетворять условию t>>n , где есть длительность задержки, вносимой элементом 4. В течение временного интервала t_j на информационный вход рангового сортировщика подается аналоговый сигнал (напряжение) х_j>х _min, где х_min - опорное напряжение, фиксируемое на опорных входах реляторов 1₂ , ..., 1_n. На дополнительном информационном входе рангового сортировщика фиксируется аналоговый сигнал (напряжение) х_n+1>x_min. Если у₁=1 (у₁=0), то ключ 2₁ замкнут (разомкнут), а ключ 2 ₂ разомкнут (замкнут). При у₂=1 (у ₂=0) устройства 3₂ и 3 ₁ работают соответственно в режимах выборки (хранения) и хранения (выборки). Элементы 4 и 5 воспроизводят базовые операции бесконечнозначной логики (БЛ): соответственно БЛ-конъюнкцию (min) и БЛ-дизъюнкцию (max), то есть осуществляют выбор соответственно наименьшего и наибольшего из двух аналоговых сигналов, действующих на их входах. Тогда напряжения на первом и втором выходах релятора 1_i, будут определяться рекуррентными выражениями

где символами и · обозначены соответственно операции max и min; есть номер момента времени t_j (фиг.2); V₁₀=x_n+1; V ₂₀=...=V_n0=x_min ; W_0j=x_j. В представленной ниже таблице приведены значения выражений (1) при n=3.

V11=x1 x4	V 12=x1 x2 x4	V 13=x1 x2 x3 x4
W11=x1x 4	W12=x 1x2 x2x4	W13=x1x 4 x2x4 x3x4
V21=x 1x4	V 22=x1x2 x1x4 x2x4	V23=x1x 2 x1x3 x1x4
W21 =xmin	W 22=x1x2x 4	x2x3 x2x4 x3x4
		W23=x1x 2x3 x1x3x 4 x2x3x 4
V31 =xmin	V 32=x1x2x 4	V33=x 1x2x3 x1x2x 4 x1x3x 4 x2x3x 4
W31 =xmin	W 32=xmin	W 33=x1x2x 3x4

С учетом данных, приведенных в таблице, нетрудно вывести непосредственное выражение, определяющее сигнал на g-м выходе предлагаемого сортировщика при j=n:

где x_k(n+2-g) ... x_k(n+1) {x₁, ..., x_n+1 }; есть количество неповторяющихся БЛ-конъюнкций x _k(n+2-g)...x_k(n+1), определяемое как число сочетаний из n+1 по n+1-g. При g=n+2-r выражение (2) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выделения из множества {х₁, ..., х _n+1} элемента x^(r) заданного ранга r {1, ..., n+1} (x⁽¹⁾ ... х⁽ⁿ⁺¹⁾; {x⁽¹⁾ }U...U{x⁽ⁿ⁺¹⁾}={x₁ , ..., x_n+1}). Таким образом, на первом,..., n-м, {n+1)-м выходах предлагаемого сортировщика соответственно имеем V_1n=x^(n+l), ..., V_nn=х⁽²⁾, W _nn=x⁽¹⁾ отсортированные аналоговые сигналы x⁽ⁿ⁺¹⁾ ... x⁽²⁾ x⁽¹⁾. При этом согласно фиг.2 для выполнения сортировки потребовалось n-1 периодов сигнала у ₂.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемый ранговый сортировщик имеет более простое по сравнению с прототипом управление, так как выполняет сортировку n+1 аналоговых сигналов по их ранговым признакам с помощью на две единицы меньшего количества периодов импульсного управляющего сигнала.