УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ Российский патент 2010 года по МПК G06F7/06 

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

Известны устройства сортировки двоичных чисел (см., например, фиг.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 V₁₁=x_min V₂₁=x₁x₂ V₃₁=x₁x₃∨x₂x₃ V₄₁=x₁x₄∨x₂x₄∨x₃x₄ W₁₁=x₁ W₂₁=x₁∨x₂ W₃₁=x₁∨x₂∨x₃ W₄₁=x₁∨x₂∨x₃∨x₄ V₁₂=x_min V₂₂=x_min V₃₂=x₁x₂x₃ V₄₂=x₁x₂x₄∨x₁x₃x₄∨x₂x₃x₄ W₁₂=x_min W₂₂=x₁x₂ W₃₂=x₁x₂∨x₁x₃∨x₂x₃ W₄₂=x₁x₂∨x₁x₃∨x₁x₄∨x₂x₃∨x₂x₄∨x₃x₄ V₁₃=x_min V₂₃=x_min V₃₃=x_min V₄₃=x₁x₂x₃x₄ W₁₃=x_min W₂₃=x_min W₃₃=x₁x₂x₃ W₄₃=x₁x₂x₃∨x₁x₂x₄∨x₁x₃x₄∨x₂x₃x₄ V₁₄=x_min V₂₄=x_min V₃₄=x_min V₄₄=x_min W₁₄=x_min W₂₄=x_min W₃₄=x_min W₄₄=x₁x₂x₃x₄

Таблица 2 V₁₁=x₁ V₁₂=x₁x₂ V₁₃=x₁x₂x₃ V₁₄=x₁x₂x₃x₄ W₁₁=x_max W₁₂=x₁∨x₂ W₁₃=x₁x₂∨x₃ W₁₄=x₁x₂x₃∨x₄ V₂₁=x_max V₂₂=x₁x₂ V₂₃=x₁x₂∨x₁x₃∨x₂x₃ V₂₄=x₁x₂x₃∨x₁x₂x₄∨x₁x₃x₄∨x₂x₃x₄ W₂₁=x_max W₂₂=x_max W₂₃=x₁∨x₂∨x₃ W₂₄=x₁x₂∨x₁x₃∨x₂x₃∨x₄ V₃₁=x_max V₃₂=x_max V₃₃=x₁∨x₂∨x₃ V₃₄=x₁x₂∨x₁x₃∨x₁x₄∨x₂x₃∨x₂x₄∨x₃x₄ W₃₁=x_max W₃₂=x_max W₃₃=x_max W₃₄=x₁∨x₂∨x₃∨x₄ V₄₁=x_max V₄₂=x_max V₄₃=x_max V₄₄=x₁∨x₂∨x₃∨x₄ W₄₁=x_max W₄₂=x_max W₄₃=x_max W₄₄=x_max

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

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

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