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

Формула изобретения

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

Описание изобретения к патенту

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

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

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем логический модуль, который содержит регистр, особенность заключается в том, что в него введены аналогичные упомянутому 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 x 4	W21 =x1x 2x 4	W31 =x1x 2x 3x 4
W 12=x1x4	W22=x1 x2x 1x4x 2x4	W32=x1x 2x 1x3x 1x4x 2x3x 3x4
W13=0	W23=x1x 2x4	W 33=x1x2x 3x 1x2x 4x 1x3x 4x 2x3x 4
W14 =0	W24=0	W34=x1x 2x3x4

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