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

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

 

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

Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку восьми одноразрядных двоичных чисел (см., например, рис.8.12 на стр.479 в книге Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь, 1990; рис.1 и рис.2 в статье Музыченко О.Н. Однородные и регулярные структуры для реализации симметричных функций алгебры логики // Автоматика и телемеханика. 1998. №4. С.152-165).

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сортировки двоичных чисел (рис.2 в статье Савченко Ю.Г., Хмелевая А.В. О методах последовательной реализации симметричных булевых функций // Автоматика и вычислительная техника. 1974. №3. С.24-29), содержащее логический модуль, который содержит регистр, и выполняющее сортировку n(n≥2) одноразрядных двоичных чисел, задаваемых двоичными сигналами.

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

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

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

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

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

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

и

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

V_i(j-1)=V_i(j-2)W_(i-1)(j-1)=V_i(j-4)W_i(j-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_(j-1)1...W_(i-1)(j-1),

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

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

W11=x1∨x4	W21=x1∨x2∨x4	W31=x1∨x2∨x3∨x4
W12=x1x4	W22=x1x2∨x1x4∨x2x4	W32=x1x2∨x1x3∨x1x4∨x2x3∨x3x4
W13=0	W23=x1x2x4	W33=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
W14=0	W24=0	W34=x1x2x3x4

С учетом данных, приведенных в таблице, нетрудно вывести непосредственное выражение для W_(n-i)j

где x_S1 ≠...≠ х_sj ∈(х₁,..., х_n); есть количество неповторяющихся фрагментов х_s1...x_sj, определяемое как число сочетаний из n по j. При j=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр. 117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x₁,..., x_n} элемента х^(r) заданного ранга . Таким образом, при предлагаемое устройство будет воспроизводить операцию

сортировки m-разрядных двоичных чисел х₁,..., х_n,.

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

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