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

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

Ранговый сортировщик, содержащий n реляторов, каждый из которых содержит объединенные выходами замыкающий и размыкающий ключи, два устройства выборки/хранения, элемент MIN, элемент МАХ и булевый инвертор, подсоединенный выходом и входом соответственно к входу записи первого устройства выборки/хранения и входу записи второго устройства выборки/хранения, второму управляющему входу релятора, первый управляющий вход которого образован входом управления замыкающего, размыкающего ключей, в каждом реляторе первый, второй входы и выход элемента МАХ соединены соответственно с вторым, первым входами элемента MIN и информационным входом второго устройства выборки/хранения, подключенного выходом к информационному входу первого устройства выборки/хранения, выход которого соединен с входом размыкающего ключа, подсоединенного выходом к второму входу элемента MIN, первый вход и выход которого соединены соответственно с информационным входом и первым выходом релятора, опорный вход и второй выход которого образованы соответственно входом замыкающего ключа и выходом второго устройства выборки/хранения, первый выход каждого предыдущего релятора соединен с информационным входом последующего релятора, а второй выход g-го релятора подключен к g-му параллельному выходу рангового сортировщика, последовательный вход и первый, второй настроечные входы которого соединены соответственно с информационным входом первого релятора и объединенными первыми, объединенными вторыми управляющими входами всех реляторов, отличающийся тем, что в него дополнительно введен аналогичный упомянутым (n+1)-й релятор, подключенный информационным входом и первым, вторым управляющими входами соответственно к первому выходу n-го релятора и первому, второму настроечным входам рангового сортировщика, i-й параллельный вход и последовательный, (n+1)-й параллельный выходы которого соединены соответственно с опорным входом i-го и первым, вторым выходами (n+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=x 1	V12=x 1 x2	V 13=x1 x2x3	V14=x1 x2 x3 x4
W 11=z1	W 12=x1x2	W12=x1 x2	W 14=x1x4 x2x4 x3x4
V21=z 1 z2	V 22=x1x2	V23=x1 x2 x1x3 x2x3	V24=x1x 2 x1x3 x1x4 x2x3 x2x4 x3x4
W21=z 1z2	W 22=z1 z2	W 23=x1x2x 3	W24=x 1x2x4 x1x3x 4 x2x3x 4
V31 =z1z2 z3	V 32=z1 z2 z3	V 33=x1x2x 3	V34=x 1x2x3 x1x2x 4 x1x3x 4 x2x3x 4
W31 =z1z2z 3	W32=z 1z2 z1z3 z2z3	W33=z1 z2 z3	W 34=x1x2x 3x4
V 41=z1z2z 3 z4	V 42=z1z2 z1z3 z2z3 z4	V 43=z1 z2 z3 z4	V 44=x1x2x 3x4
W 41=z1z2z 3z4	W 42=z1z2z 3 z1z2z 4 z1z3z 4 z2z3z 4	W43=z 1z2 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}) в их сортированный по их ранговым признакам последовательный набор.