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

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

 

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

Известны ранговые сортировщики (см., например, рис.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_i0∨W_(i-1)1∨...∨W_(i-1)(j-1)=x_i∨W_(i-1)1∨...∨W_(i-1)(j-1),

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

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

W11=x1x4 U11=Θ	W21=x1x2x4 U21=Θ	W31=U41=x1x2x3x4 U31=Θ
W12=x1∨x4 U12=Θ	W22=x1x2∨x1x4∨x2x4 U22=Θ	W32=U42=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4 U32=W31
W13=xmax U13=Θ	W23=x1∨x2∨x4 U23=W31	W33=U43=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4 U33=W32
W14=xmax U14=W31	W24=xmax U24=W32	W34=U44=x1∨x2∨x3∨x4 U34=W33

С учетом данных, приведенных в таблице, нетрудно вывести непосредственное выражение, определяющее сигнал на 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 отсортированных аналоговых сигналов.

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