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

Изобретение относится к автоматике и аналоговой вычислительной технике и может быть использовано для построения функциональных узлов аналоговых вычислительных машин, средств автоматического регулирования и управления, аналоговых процессоров. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения совместного преобразования несортированного последовательного набора n+1 аналоговых сигналов x₁,..., x_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразование несортированного параллельного набора n+1 аналоговых сигналов z₁,..., z_n+1 (z_i<x_j; i,j∈{1,..., n+1}) в их сортированный по их ранговым признакам последовательный набор. Устройство состоит из n+1 реляторов, каждый из которых содержит замыкающий и размыкающий ключи, два устройства выборки/хранения, элемент MIN, элемент МАХ, булевый инвертор. 2 ил., 1 табл.

 

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

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

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

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

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняются совместные преобразование несортированного последовательного набора n+1 аналоговых сигналов х₁,..., х_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразование несортированного параллельного набора n+1 аналоговых сигналов z₁,..., z_n+1 (z_i<x_j; i,j∈{1,..., n+1}) в их сортированный по их ранговым признакам последовательный набор.

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения совместных преобразования несортированного последовательного набора n+1 аналоговых сигналов x₁,..., x_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразования несортированного параллельного набора n+1 аналоговых сигналов z₁,..., z_n+1(z_i<x_j; i,j∈{1,..., n+1}) в их сортированный по их ранговым признакам последовательный набор.

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

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

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

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

и

где символами ∨ и · обозначены соответственно операции max и min; есть номер момента времени t_j (фиг.2); V_i0=z_i; W_0j=x_j. В представленной ниже таблице приведены значения выражений (1) при n=3.

V11=x1	V12=x1∨x2	V13=x1∨x2x3	V14=x1∨x2∨x3∨x4
W11=z1	W12=x1x2	W12=x1x2	W14=x1x4∨x2x4∨x3x4
V21=z1∨z2	V22=x1x2	V23=x1x2∨x1x3∨x2x3	V24=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4
W21=z1z2	W22=z1∨z2	W23=x1x2x3	W24=x1x2x4∨x1x3x4∨x2x3x4
V31=z1z2∨z3	V32=z1∨z2∨z3	V33=x1x2x3	V34=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
W31=z1z2z3	W32=z1z2∨z1z3∨z2z3	W33=z1∨z2∨z3	W34=x1x2x3x4
V41=z1z2z3∨z4	V42=z1z2∨z1z3∨z2z3∨z4	V43=z1∨z2∨z3∨z4	V44=x1x2x3x4
W41=z1z2z3z4	W42=z1z2z3∨z1z2z4∨z1z3z4∨z2z3z4	W43=z1z2∨z1z3∨z1z4∨z2z3∨z2z4∨z3z4	W44=z1∨z2∨z3∨z4

С учетом данных, приведенных в таблице, нетрудно вывести непосредственные выражения для V_i(n+1) и W_(n+1)j:

где x_k(n+2-i)≠...≠x_k(n+1)∈{x₁,..., x_n+1}; z_kj≠...≠z_k(n+1)∈{z₁,..., z_n+1}; есть количество неповторяющихся БЛ-конъюнкций x_k(n+2-i)...x_k(n+1), определяемое как число сочетаний из n+1 по n+1-i; есть количество неповторяющихся БЛ-конъюнкций z_kj...z_k(n+1), определяемое как число сочетаний из n+1 по j-1. При i=n+2-r выражение (2) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выделения из множества {x₁,..., x_n+1} элемента х^(r) заданного ранга r∈{1,..., n+1) (x⁽¹⁾≤...≤x⁽ⁿ⁺¹⁾; {x⁽¹⁾}U...U{x⁽ⁿ⁺¹⁾}={x₁,..., x_n+1}). При j=r выражение (3) совпадает с видом упомянутой поисковой функции, которая в этом случае реализует алгоритм выделения из множества {z₁,..., z_n+1} элемента z^(r) заданного ранга r∈{1,..., n+1}(z⁽¹⁾≤...≤z⁽ⁿ⁺¹⁾; {z⁽¹⁾}U...U{z⁽ⁿ⁺¹⁾}={z₁,..., z_n+1}). Таким образом, в момент времени t_n+1 на первом,..., (n+1)-ом параллельных выходах предлагаемого сортировщика и на его последовательном выходе в моменты времени t₁,...,t_n+1 соответственно имеем V_1(n+1)=x⁽ⁿ⁺¹⁾,..., V_(n+1)(n+1)=x⁽¹⁾ сортированный параллельный набор сигналов х₁,..., х_n+1 и W_(n+1)1=z⁽¹⁾,..., W_(n+1)(n+1)=z⁽ⁿ⁺¹⁾ сортированный последовательный набор сигналов z₁,..., z_n+1.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемый ранговый сортировщик обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает совместные преобразование несортированного последовательного набора n+1 аналоговых сигналов x₁,..., x_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразование несортированного параллельного набора n+1 аналоговых сигналов z₁,...,z_n+1 (z_i<x_j; i,j∈{1,..., n+1}) в их сортированный по их ранговым признакам последовательный набор.

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