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

Изобретение относится к технологиям сетевой связи. Технический результат заключается в повышении быстродействия устройства. Ранговый сортировщик содержит: восемь логических ячеек, первый, второй входы i-й (i∈{4,9}) и первый, второй входы j-й (j∈{6,11}) логических ячеек соединены соответственно с первыми выходами (i-[i/3]-2)-й, (i-2)-й логических ячеек и вторыми выходами (j+[j/11]-4)-й, (j-[j/2])-й логических ячеек, первый, второй входы q-й {q∈{5,10}) и первый, второй входы g-й (g∈{7,8,12,13}) логических ячеек подключены соответственно к второму выходу (q+[q/10]-4)-й, первому выходу (q-2)-й логических ячеек и второму выходу (g-3)-й, первому выходу (g-2)-й логических ячеек, а первый, второй входы k-й и первый, второй выходы m-й логических ячеек соединены соответственно с (2×k-1)-м, (2×k)-м входами и (2×m-22)-м, (2×m-21)-м выходами рангового сортировщика, первый и шестой выходы которого подключены соответственно к первому выходу девятой и второму выходу одиннадцатой логических ячеек, при этом [] есть оператор выделения целой части. 1 ил.

 

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

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип ранговый сортировщик (патент РФ 2262740, кл. G06G 7/25, 2005 г.), который содержит логические ячейки и может быть использован для преобразования параллельного набора шести аналоговых сигналов в параллельный набор этих сигналов, отсортированных по их ранговым признакам.

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится низкое быстродействие, обусловленное тем, что минимальное время упомянутого преобразования превышает 6×Δt_я, где Δt_я есть длительность задержки, вносимой логической ячейкой.

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

Указанный технический результат при осуществлении изобретения достигается тем, что в ранговом сортировщике, содержащем пять логических ячеек, каждая из которых содержит элемент MIN, подсоединенный первым, вторым входами и выходом соответственно к ее первому, второму входам и первому выходу, и элемент МАХ, первый, второй входы и выход которого соединены соответственно с ее первым, вторым входами и вторым выходом, особенность заключается в том, что в него дополнительно введены восемь аналогичных упомянутым логических ячеек, первый, второй входы i-й (i∈{4,9}) и первый, второй входы j-й (j∈{6,11}) логических ячеек соединены соответственно с первыми выходами (i-[i/3]-2)-й, (i-2)-й логических ячеек и вторыми выходами (j+[j/11]-4)-й, (j-[j/2])-й логических ячеек, первый, второй входы q-й (q∈{5,10}) и первый, второй входы g-й (g∈{7,8,12,13}) логических ячеек подключены соответственно к второму выходу (q+[q/10]-4)-й, первому выходу (q-2)-й логических ячеек и второму выходу (g-3)-й, первому выходу (g-2)-й логических ячеек, а первый, второй входы k-й и первый, второй выходы m-й логических ячеек соединены соответственно с (2×k-1)-м, (2×k)-м входами и (2×m-22)-м, (2×m-21)-м выходами рангового сортировщика, первый и шестой выходы которого подключены соответственно к первому выходу девятой и второму выходу одиннадцатой логических ячеек, при этом [] есть оператор выделения целой части.

На чертеже представлена схема предлагаемого рангового сортировщика.

Ранговый сортировщик содержит логические ячейки 1₁, …, 1₁₃. Каждая логическая ячейка содержит элемент MIN 2, подсоединенный первым, вторым входами и выходом соответственно к ее первому, второму входам и первому выходу, и элемент МАХ 3, подсоединенный первым, вторым входами и выходом соответственно к ее первому, второму входам и второму выходу. Первый, второй входы ячейки 1_i (i∈{4,9}) и первый, второй входы ячейки 1_j (j∈{6,11}) соединены соответственно с первыми выходами ячеек 1_i-[i/3]-2, 1_i-2 и вторыми выходами ячеек 1_j+[j/11]-4, 1_j-[j/2], первый, второй входы ячейки 1_q (q∈{5,10}) и первый, второй входы ячейки 1_g (g∈{7,8,12,13}) подключены соответственно к второму выходу ячейки 1_q+[q/10]-4, первому выходу ячейки 1_q-2 и второму выходу ячейки 1_g-3, первому выходу ячейки l_g-2, а первый, второй входы ячейки 1_k и первый, второй выходы ячейки 1_m соединены соответственно с (2×k-1)-м, (2×k)-м входами и (2×m-22)-м, (2×m-21)-м выходами рангового сортировщика, первый и шестой выходы которого подключены соответственно к первому выходу ячейки 1₉ и второму выходу ячейки 1₁₁, при этом [] есть оператор выделения целой части.

Работа предлагаемого рангового сортировщика осуществляется следующим образом. На его первый, …, шестой входы подается параллельный набор аналоговых сигналов (напряжений) x_l,…,x₆ соответственно. Элементы 2 и 3 воспроизводят базовые операции бесконечнозначной логики (БЛ) БЛ-конъюнкцию (min) и БЛ-дизъюнкцию (шах), применительно к сигналам, действующим на их входах. Тогда на первом, …, шестом выходах предлагаемого сортировщика получим

,

,

,

,

,

,

где символами и обозначены операции max и min. Следовательно, сигнал на r-м выходе предлагаемого сортировщика определяется выражением

где x_sr,…,x_s6 ∈ {x₁,…,x₆} (1≤sr<…<s6≤6); есть количество неповторяющихся БЛ-конъюнкций x_sr…x_s6, определяемое как число сочетаний из 6 по 7-r. Выражение (1) совпадает с видом n-арной поисковой функции (функция (6.7) на стр. 117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая при n=6 реализует алгоритм выделения из множества {x₁,…,x₆} элемента x^(r) заданного ранга r∈{1,…,6} (x⁽¹⁾≤…≤x⁽⁶⁾;). Таким образом, на первом, …, шестом выходах предлагаемого сортировщика имеем z₁= x⁽¹⁾,…,z₆=x⁽⁶⁾, где x⁽¹⁾,…,x⁽⁶⁾ - параллельный набор аналоговых сигналов x₁,…,x₆, отсортированных по их ранговым признакам.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемый ранговый сортировщик обладает более высоким по сравнению с прототипом быстродействием, так как преобразует параллельный набор шести аналоговых сигналов в параллельный набор этих сигналов, отсортированных по их ранговым признакам, за время, не превышающее 5×Δt_я, где Δt_я есть длительность задержки, вносимой логической ячейкой.

Ранговый сортировщик, содержащий пять логических ячеек, каждая из которых содержит элемент MIN, подсоединенный первым, вторым входами и выходом соответственно к ее первому, второму входам и первому выходу, и элемент МАХ, первый, второй входы и выход которого соединены соответственно с ее первым, вторым входами и вторым выходом, отличающийся тем, что в него дополнительно введены восемь аналогичных упомянутым логических ячеек, первый, второй входы i-й (i∈{4,9}) и первый, второй входы j-й (j∈{6,11}) логических ячеек соединены соответственно с первыми выходами (i-[i/3]-2)-й, (i-2)-й логических ячеек и вторыми выходами (j+[j/11]-4)-й, (j-[j/2])-й логических ячеек, первый, второй входы q-й {q∈{5,10}) и первый, второй входы g-й (g∈{7,8,12,13}) логических ячеек подключены соответственно к второму выходу (q+[q/10]-4)-й, первому выходу (q-2)-й логических ячеек и второму выходу (g-3)-й, первому выходу (g-2)-й логических ячеек, а первый, второй входы k-й и первый, второй выходы m-й логических ячеек соединены соответственно с (2×k-1)-м, (2×k)-м входами и (2×m-22)-м, (2×m-21)-м выходами рангового сортировщика, первый и шестой выходы которого подключены соответственно к первому выходу девятой и второму выходу одиннадцатой логических ячеек, при этом [] есть оператор выделения целой части.