Устройство сортировки двоичных чисел

Устройство сортировки двоичных чисел

Иллюстрации

Показать все

Реферат

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

Известны устройства сортировки двоичных чисел (см., например, фиг.1 в описании изобретения к патенту РФ 2300136, кл. G06F 7/06, 2007 г.), преобразующие несортированный последовательный набор задаваемых двоичными сигналами n m-разрядных двоичных чисел в сортированный параллельный набор этих чисел.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство сортировки двоичных чисел (фиг.1 в описании изобретения к патенту РФ 2264645, кл. G06F 7/06, 2005 г.), которое содержит n-1 логических модулей и преобразует несортированный параллельный набор задаваемых двоичными сигналами n m-разрядных двоичных чисел в сортированный последовательный набор этих чисел.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройство сортировки двоичных чисел, содержащее n-1 логических модулей, каждый из которых содержит m замыкающих, m размыкающих ключей, постоянное запоминающее устройство и регистр, в g-ом логическом модуле первый управляющий и k-й входы образованы соответственно входом управления всех имеющихся в нем ключей и входом k-го замыкающего ключа, выход которого соединен с выходом k-го размыкающего ключа и k-ым адресным входом постоянного запоминающего устройства, подсоединенного k-ым выходом к k-му входу регистра, k-й выход и вход записи которого соединены соответственно с входом k-го размыкающего ключа и вторым управляющим входом g-го логического модуля, подсоединенного k-ым выходом к (m+k)-му выходу своего постоянного запоминающего устройства, в каждом логическом модуле, кроме первого, (m+k)-й вход образован (m+k)-ым адресным входом постоянного запоминающего устройства, k-й выход каждого предыдущего логического модуля подключен к (m+k)-му входу последующего логического модуля, а первый и второй управляющие входы g-го логического модуля соединены соответственно с первым и вторым настроечными входами устройства сортировки двоичных чисел, дополнительно введен аналогичный (n-1)-му n-й логический модуль, подключенный первым, вторым управляющими и (m+k)-ым входами соответственно к первому, второму управляющим входам и k-му выходу (n-1)-го логического модуля, в первом логическом модуле (m+k)-й вход образован (m+k)-ым адресным входом постоянного запоминающего устройства, а в i-ом логическом модуле (m+k)-й выход образован k-ым выходом постоянного запоминающего устройства.

На фиг.1 и фиг.2 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие принцип его работы.

Устройство сортировки двоичных чисел содержит логические модули 1₁,…,1_n. Модуль 1_i (i∈{1,…,n}) содержит размыкающие и замыкающие ключи 2₁,…,2_m и 3₁,…,3_m, постоянное запоминающее устройство 4, регистр 5, причем выход ключа соединен с выходом ключа 3_k и k-ым адресным входом устройства 4, k-й выход которого соединен с k-ым входом регистра 5, подсоединенного k-ым выходом и входом записи соответственно к входу ключа 2_k и второму управляющему входу модуля 1, первый управляющий, k-й, (m+k)-й входы и k-й, (m+k)-й выходы которого образованы соответственно входом управления всех имеющихся в нем ключей, входом ключа 3_k, (m+k)-ым адресным входом и (m+k)-ым, k-ым выходами устройства 4, k-й выход каждого предыдущего логического модуля соединен с (m+k)-ым входом последующего логического модуля, а объединенные первые и объединенные вторые управляющие входы всех логических модулей подключены соответственно к первому и второму настроечным входам устройства сортировки двоичных чисел.

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y₁,у₂∈{0,1} (фиг.2), причем длительность Т* высокого уровня сигнала y₁ и период Т сигнала y₂ должны удовлетворять условиям Т*>Δt* и Т>Δt, где Δt*=nτ₁, Δt=nτ₁+τ₂, а τ₁ и τ₂ есть длительности задержек, вносимых соответственно устройством 4 и регистром 5. Подлежащие сортировке m-разрядные двоичные числа x₁,…,x₂, задаваемые двоичными сигналами, либо последовательно подаются согласно фиг.2 на модуль 1₁ (при этом на входе всех модулей фиксируется логическая «1») либо параллельно подаются в течение времени действия высокого уровня сигнала у₁ соответственно на модули 1₁,…,1_n: V₁₀=x₁,…,V_n0=x_n (при этом на (m+k)-ом входе модуля 1₁ фиксируется логический «0»). Если у₁=1 (y₁=0), то ключи 3₁,…,3_m замкнуты (разомкнуты), ключи 2₁,…,2_m разомкнуты (замкнуты). Загрузка данных в регистр 5 происходит по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y₂). В устройстве 4 q-я ячейка с адресом содержит 2 m-разрядный двоичный код d*_m-1…d*₀ d_m-1…d₀, в котором d*_m-1…d*₀=max(a*_m-1…a*₀, a_m-1…a₀), d_m-1…d₀=min(a*_m-1…a*₀, a_m-1…a₀). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на (m+1)-ом - (m+m)-ом и первом - m-ом выходах модуля будут определяться рекуррентными выражениями

где символами ∨ и · обозначены операции max и min; есть номер момента времени t_j (фиг.2); V_i0=x_i, W_0j=x_min≤x_i либо V_i0=x_max, W_0j=x_j≤x_max. В представленных ниже табл.1 и табл.2 приведены значения выражений (1) при n=4, если соответственно V_i0=x_i, W_0j=x_min≤x_i и V_0j=x_max, W_0j=x_j≤x_max. С учетом данных, приведенных в табл.1 и табл.2, нетрудно вывести непосредственные выражения для соответственно W_nj и V_in

где x_s1≠…≠x_sn∈{x₁,…x_n}; есть количество неповторяющихся фрагментов x_s1…x_sj (x_si…x_sn), определяемое как число сочетаний из n по j (по n+1-i). При j=n+1-r выражение (2) и при i=r выражение (3) совпадают с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x₁,…,x_n} элемента x^(r) заданного ранга r∈{1,…,n} (x⁽¹⁾≤…≤x⁽ⁿ⁾;

Таким образом, при V_i0=x_i, W_0j=x_min≤x_i (при V_i0=x_max, W_0j=x_j≤ x_max) в моменты времени t₁,…,t_n (в момент времени t_n) имеем W_n1=x⁽ⁿ⁾,…,W_nn=x⁽¹⁾ (V_1n=x⁽¹⁾,…,V_nn=x⁽ⁿ⁾), то есть предлагаемое устройство формирует сортированный последовательный (параллельный) набор m-разрядных двоичных чисел x₁,…,x_n.

Таблица 1
V11=xmin	V21=x1x2	V31=x1x3∨x2x3	V41=x1x4∨x2x4∨x3x4
W11=x1	W21=x1∨x2	W31=x1∨x2∨x3	W41=x1∨x2∨x3∨x4
V12=xmin	V22=xmin	V32=x1x2x3	V42=x1x2x4∨x1x3x4∨x2x3x4
W12=xmin	W22=x1x2	W32=x1x2∨x1x3∨x2x3	W42=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4
V13=xmin	V23=xmin	V33=xmin	V43=x1x2x3x4
W13=xmin	W23=xmin	W33=x1x2x3	W43=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
V14=xmin	V24=xmin	V34=xmin	V44=xmin
W14=xmin	W24=xmin	W34=xmin	W44=x1x2x3x4

Таблица 2
V11=x1	V12=x1x2	V13=x1x2x3	V14=x1x2x3x4
W11=xmax	W12=x1∨x2	W13=x1x2∨x3	W14=x1x2x3∨x4
V21=xmax	V22=x1x2	V23=x1x2∨x1x3∨x2x3	V24=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
W21=xmax	W22=xmax	W23=x1∨x2∨x3	W24=x1x2∨x1x3∨x2x3∨x4
V31=xmax	V32=xmax	V33=x1∨x2∨x3	V34=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4
W31=xmax	W32=xmax	W33=xmax	W34=x1∨x2∨x3∨x4
V41=xmax	V42=xmax	V43=xmax	V44=x1∨x2∨x3∨x4
W41=xmax	W42=xmax	W43=xmax	W44=xmax

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

Устройство сортировки двоичных чисел, содержащее n-1 логических модулей, каждый из которых содержит m замыкающих, m размыкающих ключей, постоянное запоминающее устройство и регистр, причем в g-м логическом модуле первый управляющий и k-й входы образованы соответственно входом управления всех имеющихся в нем ключей и входом k-го замыкающего ключа, выход которого соединен с выходом k-го размыкающего ключа и k-м адресным входом постоянного запоминающего устройства, подсоединенного k-м выходом к k-му входу регистра, k-й выход и вход записи которого соединены соответственно с входом k-го размыкающего ключа и вторым управляющим входом, g-го логического модуля, подсоединенного k-м выходом к (m+k)-мy выходу своего постоянного запоминающего устройства, в каждом логическом модуле, кроме первого, (m+k)-й вход образован (m+k)-м адресным входом постоянного запоминающего устройства, k-й выход каждого предыдущего логического модуля подключен к (m+k)-му входу последующего логического модуля, а первый и второй управляющие входы g-го логического модуля соединены соответственно с первым и вторым настроечными входами устройства сортировки двоичных чисел, отличающееся тем, что в него дополнительно введен аналогичный (n-1)-му n-й логический модуль, подключенный первым, вторым управляющими и (m+k)-м входами соответственно к первому, второму управляющим входам и k-му выходу (n-1)-го логического модуля, в первом логическом модуле (m+k)-й вход образован (m+k)-м адресным входом постоянного запоминающего устройства, а в i-м логическом модуле (m+k)-й выход образован k-м выходом постоянного запоминающего устройства, причем устройство сортировки двоичных чисел выполняет преобразование несортированного последовательного набора m-разрядных двоичных чисел x₁,…,x_n (m разрядов числа x_j , задаваемых m двоичными сигналами, подаются в j-й момент времени на (m+1)-й - (m+m)-й входы первого логического модуля, при этом на k-м входе всех логических модулей фиксируется логическая 1 в их сортированный параллельный набор х⁽¹⁾,…,x⁽ⁿ⁾ (х⁽¹⁾≤…≤x⁽ⁿ⁾; так, что m разрядов числа x⁽ⁱ⁾ в n-й момент времени формируются на (m+1)-м - (m+m)-м выходах i-го логического модуля, либо устройство сортировки двоичных чисел выполняет преобразование несортированного параллельного набора m-разрядных двоичных чисел x₁,…,x_n (m разрядов числа x_i, задаваемых m двоичными сигналами, подаются в первый момент времени на первый - m-й входы i-го логического модуля, при этом на (m+k)-м входе первого логического модуля фиксируется логический 0) в их сортированный последовательный набор х⁽¹⁾,…,x⁽ⁿ⁾ так, что m разрядов числа х^(n+1-j) в j-й момент времени формируются на первом - m-м выходах n-го логического модуля.