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

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

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

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

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

Известны ранговые сортировщики (см., например, рис.76а в кн.: Волгин Л.И. Синтез устройств для обработки и преобразования информации в элементном базисе реляторов. Таллинн: Валгус, 1989 г.), которые выполняют сортировку четырех аналоговых сигналов по их ранговым признакам.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип ранговый сортировщик (фиг.1 в описании изобретения к патенту РФ 2172980, кл. G 06 G 7/25, 2001 г.), который содержит m-1 реляторов и выполняет сортировку m аналоговых сигналов по их ранговым признакам.

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

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

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

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

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

Работа предлагаемого рангового сортировщика осуществляется следующим образом. На вторые информационные входы реляторов 1 ₁,...,1_m-1, четвертый и третий информационные входы релятора 1₁ подаются соответственно аналоговые сигналы (напряжения) х₁,...,х_m<x _max и опорное напряжение x_max; на первый, второй настроечные входы рангового сортировщика подаются соответственно двоичные сигналы y₁, y₂{0,1} (фиг.2), причем длительность t ^* низкого (высокого) уровня сигнала у₂ должна удовлетворять условию t ^*>t=(m-1), где есть длительность задержки, вносимой элементом 5. Если у ₁=1 (у₁=0), то ключи 2₁, 2₃ замкнуты (разомкнуты), а ключи 2₂, 2₄ разомкнуты (замкнуты). При у₂=1 (у₂=0) устройства 3₁, 3₂ и 3₃, 3 ₄ работают соответственно в режимах выборки (хранения) и хранения (выборки). Элементы 4 и 5 воспроизводят базовые операции бесконечнозначной логики (БЛ): соответственно БЛ-дизъюнкцию (max) и БЛ-конъюнкцию (min), то есть осуществляют выбор соответственно наибольшего и наименьшего из двух аналоговых сигналов, действующих на их входах. Тогда напряжения на выходе элемента 4 релятора втором выходе релятора l_i и i-ом, m-ом выходах рангового сортировщика будут определяться рекуррентными выражениями

и

где символами и · обозначены операции max и min; есть номер момента времени t_j (фиг.2); V_i0 =x_i; W₀₁=x_m; W₀₂=...=W _0m=x_max; U₂₀=...=U_m0 = ( - неопределенное значение сигнала). Поскольку согласно (1.1) имеем

V_i(j-1)=V_i(j-2)W _(i-1)(j-1)=V_i(j-4)W _(i-1)(j-3)W _(i-1)(j-2)W _(i-1)(j-1)=V_i0W _(i-1)1...W _(i-1)(j-1)=x_iW _(i-1)1...W _(i-1)(j-1),

то с учетом (1.2) получим

В представленной ниже таблице приведены значения выражений (2) и (1.3) при m=4.

W11=x1 x4 U11=	W21=x 1x2x4 U21=	W31=U 41=x1x2x 3x4 U31 =
W12=x 1x 4 U12=	W22=x 1x2x 1x4x 2x4 U 22=	W32=U 42=x1x2x 3x 1x2x 4x 1x3x 4x 2x3x 4 U32=W31
W13=x max U13=	W23=x 1x 2x 4 U23=W 31	W33=U 43=x1x2x 1x3x 1x4x 2x3x 2x4x 3x4 U 33=W32
W14=xmax U14=W31	W24=xmax U24=W32	W34=U44=x 1x 2x 3x 4 U34=W 33

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

где есть количество неповторяющихся БЛ-конъюнкций x_kr ...x_km, определяемое как число сочетаний из m по r-1. Выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выделения из множества {х₁,...,х_m,} элемента х^(r) заданного ранга r{l,...,m} (x⁽¹⁾...x ^(m); . Таким образом, на первом,...,m-ом выходах предлагаемого сортировщика соответственно имеем U_1m=x⁽¹⁾,...,U _mm=x^(m) отсортированные аналоговые сигналы х ⁽¹⁾...x ^(m).

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