Патент на изобретение №2338249

(54) РАНГОВЫЙ СОРТИРОВЩИК

(57) Реферат:

Изобретение относится к автоматике и аналоговой вычислительной технике и может быть использовано для построения функциональных узлов аналоговых вычислительных машин, средств автоматического регулирования и управления, аналоговых процессоров. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения совместного преобразования несортированного последовательного набора n+1 аналоговых сигналов x₁,…, x_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразование несортированного параллельного набора n+1 аналоговых сигналов z₁,…, z_n+1 (z_ij; 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_ij; i,j{1,…, n+1}) в их сортированный по их ранговым признакам последовательный набор.

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения совместных преобразования несортированного последовательного набора n+1 аналоговых сигналов x₁,…, x_n+1 в их сортированный по их ранговым признакам параллельный набор и преобразования несортированного параллельного набора n+1 аналоговых сигналов z₁,…, z_n+1(z_ij; 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=x1x2	V13=x1x2x3	V14=x1x2x3x4
W11=z1	W12=x1x2	W12=x1x2	W14=x1x4x2x4x3x4
V21=z1z2	V22=x1x2	V23=x1x2x1x3x2x3	V24=x1x2x1x3x1x4x2x3x2x4x3x4
W21=z1z2	W22=z1z2	W23=x1x2x3	W24=x1x2x4x1x3x4x2x3x4
V31=z1z2z3	V32=z1z2z3	V33=x1x2x3	V34=x1x2x3x1x2x4x1x3x4x2x3x4
W31=z1z2z3	W32=z1z2z1z3z2z3	W33=z1z2z3	W34=x1x2x3x4
V41=z1z2z3z4	V42=z1z2z1z3z2z3z4	V43=z1z2z3z4	V44=x1x2x3x4
W41=z1z2z3z4	W42=z1z2z3z1z2z4z1z3z4z2z3z4	W43=z1z2z1z3z1z4z2z3z2z4z3z4	W44=z1z2z3z4

С учетом данных, приведенных в таблице, нетрудно вывести непосредственные выражения для 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_ij; i,j{1,…, n+1}) в их сортированный по их ранговым признакам последовательный набор.

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

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

РИСУНКИ

MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 28.04.2009

Извещение опубликовано: 20.09.2010 БИ: 26/2010