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

(54) УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ

(57) Реферат:

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

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

Известны устройства сортировки двоичных чисел (см., например, фиг.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-1d*₀ d_m-1d₀, в котором d*_m-1d*₀=max(a*_m-1a*₀, a_m-1a₀), d_m-1d₀=min(a*_m-1a*₀, a_m-1a₀). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на (m+1)-ом – (m+m)-ом и первом – m-ом выходах модуля будут определяться рекуррентными выражениями

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

где x_s1x_sn{x₁,x_n}; есть количество неповторяющихся фрагментов x_s1x_sj (x_six_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_minx_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=x1x3x2x3	V41=x1x4x2x4x3x4
W11=x1	W21=x1x2	W31=x1x2x3	W41=x1x2x3x4
V12=xmin	V22=xmin	V32=x1x2x3	V42=x1x2x4x1x3x4x2x3x4
W12=xmin	W22=x1x2	W32=x1x2x1x3x2x3	W42=x1x2x1x3x1x4x2x3x2x4x3x4
V13=xmin	V23=xmin	V33=xmin	V43=x1x2x3x4
W13=xmin	W23=xmin	W33=x1x2x3	W43=x1x2x3x1x2x4x1x3x4x2x3x4
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=x1x2	W13=x1x2x3	W14=x1x2x3x4
V21=xmax	V22=x1x2	V23=x1x2x1x3x2x3	V24=x1x2x3x1x2x4x1x3x4x2x3x4
W21=xmax	W22=xmax	W23=x1x2x3	W24=x1x2x1x3x2x3x4
V31=xmax	V32=xmax	V33=x1x2x3	V34=x1x2x1x3x1x4x2x3x2x4x3x4
W31=xmax	W32=xmax	W33=xmax	W34=x1x2x3x4
V41=xmax	V42=xmax	V43=xmax	V44=x1x2x3x4
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-го логического модуля.

РИСУНКИ