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

Классы МПК:G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации
Автор(ы):
Патентообладатель(и):Государственное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" (RU)
Приоритеты:
подача заявки:
2007-12-25
публикация патента:

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

устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052

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

Устройство сортировки двоичных чисел, содержащее n-1 логических модулей, каждый из которых содержит m замыкающих, m размыкающих ключей, постоянное запоминающее устройство и регистр, причем в g-м устройство сортировки двоичных чисел, патент № 2383052 логическом модуле первый управляющий и k-й устройство сортировки двоичных чисел, патент № 2383052 входы образованы соответственно входом управления всех имеющихся в нем ключей и входом 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-м устройство сортировки двоичных чисел, патент № 2383052 логическом модуле (m+k)-й выход образован k-м выходом постоянного запоминающего устройства, причем устройство сортировки двоичных чисел выполняет преобразование несортированного последовательного набора m-разрядных двоичных чисел x1,устройство сортировки двоичных чисел, патент № 2383052 ,xn (m разрядов числа xjустройство сортировки двоичных чисел, патент № 2383052 , задаваемых m двоичными сигналами, подаются в j-й момент времени на (m+1)-й - (m+m)-й входы первого логического модуля, при этом на k-м входе всех логических модулей фиксируется логическая 1 в их сортированный параллельный набор х(1),устройство сортировки двоичных чисел, патент № 2383052 ,x(n)(1)устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 x(n); устройство сортировки двоичных чисел, патент № 2383052 так, что m разрядов числа x(i) в n-й момент времени формируются на (m+1)-м - (m+m)-м выходах i-го логического модуля, либо устройство сортировки двоичных чисел выполняет преобразование несортированного параллельного набора m-разрядных двоичных чисел x1,устройство сортировки двоичных чисел, патент № 2383052 ,xn (m разрядов числа xi, задаваемых m двоичными сигналами, подаются в первый момент времени на первый - m-й входы i-го логического модуля, при этом на (m+k)-м входе первого логического модуля фиксируется логический 0) в их сортированный последовательный набор х(1),устройство сортировки двоичных чисел, патент № 2383052 ,x(n) так, что m разрядов числа х(n+1-j) в j-й момент времени формируются на первом - m-м выходах n-го логического модуля.

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

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

Известны устройства сортировки двоичных чисел (см., например, фиг.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-ом устройство сортировки двоичных чисел, патент № 2383052 логическом модуле первый управляющий и k-й устройство сортировки двоичных чисел, патент № 2383052 входы образованы соответственно входом управления всех имеющихся в нем ключей и входом 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-ом устройство сортировки двоичных чисел, патент № 2383052 логическом модуле (m+k)-й выход образован k-ым выходом постоянного запоминающего устройства.

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

Устройство сортировки двоичных чисел содержит логические модули 11,устройство сортировки двоичных чисел, патент № 2383052 ,1n. Модуль 1i (iустройство сортировки двоичных чисел, патент № 2383052 {1,устройство сортировки двоичных чисел, патент № 2383052 ,n}) содержит размыкающие и замыкающие ключи 21 ,устройство сортировки двоичных чисел, патент № 2383052 ,2m и 31,устройство сортировки двоичных чисел, патент № 2383052 ,3m, постоянное запоминающее устройство 4, регистр 5, причем выход ключа устройство сортировки двоичных чисел, патент № 2383052 соединен с выходом ключа 3k и k-ым адресным входом устройства 4, k-й выход которого соединен с k-ым входом регистра 5, подсоединенного k-ым выходом и входом записи соответственно к входу ключа 2k и второму управляющему входу модуля 1, первый управляющий, k-й, (m+k)-й входы и k-й, (m+k)-й выходы которого образованы соответственно входом управления всех имеющихся в нем ключей, входом ключа 3k, (m+k)-ым адресным входом и (m+k)-ым, k-ым выходами устройства 4, k-й выход каждого предыдущего логического модуля соединен с (m+k)-ым входом последующего логического модуля, а объединенные первые и объединенные вторые управляющие входы всех логических модулей подключены соответственно к первому и второму настроечным входам устройства сортировки двоичных чисел.

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y12устройство сортировки двоичных чисел, патент № 2383052 {0,1} (фиг.2), причем длительность Т* высокого уровня сигнала y1 и период Т сигнала y2 должны удовлетворять условиям Т*>устройство сортировки двоичных чисел, патент № 2383052 t* и Т>устройство сортировки двоичных чисел, патент № 2383052 t, где устройство сортировки двоичных чисел, патент № 2383052 t*=nустройство сортировки двоичных чисел, патент № 2383052 1, устройство сортировки двоичных чисел, патент № 2383052 t=nустройство сортировки двоичных чисел, патент № 2383052 1+устройство сортировки двоичных чисел, патент № 2383052 2, а устройство сортировки двоичных чисел, патент № 2383052 1 и устройство сортировки двоичных чисел, патент № 2383052 2 есть длительности задержек, вносимых соответственно устройством 4 и регистром 5. Подлежащие сортировке m-разрядные двоичные числа x1,устройство сортировки двоичных чисел, патент № 2383052 ,x2, задаваемые двоичными сигналами, либо последовательно подаются согласно фиг.2 на модуль 11 (при этом на устройство сортировки двоичных чисел, патент № 2383052 входе всех модулей фиксируется логическая «1») либо параллельно подаются в течение времени действия высокого уровня сигнала у1 соответственно на модули 11 ,устройство сортировки двоичных чисел, патент № 2383052 ,1n: V10=x1,устройство сортировки двоичных чисел, патент № 2383052 ,Vn0=xn (при этом на (m+k)-ом входе модуля 11 фиксируется логический «0»). Если у1=1 (y1=0), то ключи 31,устройство сортировки двоичных чисел, патент № 2383052 ,3m замкнуты (разомкнуты), ключи 21 ,устройство сортировки двоичных чисел, патент № 2383052 ,2m разомкнуты (замкнуты). Загрузка данных в регистр 5 происходит по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2 ). В устройстве 4 q-я устройство сортировки двоичных чисел, патент № 2383052 ячейка с адресом устройство сортировки двоичных чисел, патент № 2383052 содержит 2 m-разрядный двоичный код d*m-1устройство сортировки двоичных чисел, патент № 2383052 d*0 dm-1устройство сортировки двоичных чисел, патент № 2383052 d0, в котором d*m-1устройство сортировки двоичных чисел, патент № 2383052 d*0=max(a*m-1устройство сортировки двоичных чисел, патент № 2383052 a*0, am-1устройство сортировки двоичных чисел, патент № 2383052 a0), dm-1устройство сортировки двоичных чисел, патент № 2383052 d0=min(a*m-1устройство сортировки двоичных чисел, патент № 2383052 a*0, am-1устройство сортировки двоичных чисел, патент № 2383052 a0). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на (m+1)-ом - (m+m)-ом и первом - m-ом выходах модуля устройство сортировки двоичных чисел, патент № 2383052 будут определяться рекуррентными выражениями

устройство сортировки двоичных чисел, патент № 2383052

где символами устройство сортировки двоичных чисел, патент № 2383052 и · обозначены операции max и min; устройство сортировки двоичных чисел, патент № 2383052 есть номер момента времени tj (фиг.2); V i0=xi, W0j=xminустройство сортировки двоичных чисел, патент № 2383052 xi либо Vi0=xmax, W 0j=xjустройство сортировки двоичных чисел, патент № 2383052 xmax. В представленных ниже табл.1 и табл.2 приведены значения выражений (1) при n=4, если соответственно Vi0=xi, W0j=xminустройство сортировки двоичных чисел, патент № 2383052 xi и V0j=xmax, W0j =xjустройство сортировки двоичных чисел, патент № 2383052 xmax. С учетом данных, приведенных в табл.1 и табл.2, нетрудно вывести непосредственные выражения для соответственно Wnj и Vin

устройство сортировки двоичных чисел, патент № 2383052

устройство сортировки двоичных чисел, патент № 2383052

где xs1устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 xsnустройство сортировки двоичных чисел, патент № 2383052 {x1,устройство сортировки двоичных чисел, патент № 2383052 xn}; устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 есть количество неповторяющихся фрагментов xs1 устройство сортировки двоичных чисел, патент № 2383052 xsj (xsiустройство сортировки двоичных чисел, патент № 2383052 xsn), определяемое как число сочетаний из n по j (по n+1-i). При j=n+1-r выражение (2) и при i=r выражение (3) совпадают с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x1,устройство сортировки двоичных чисел, патент № 2383052 ,xn} элемента x(r) заданного ранга rустройство сортировки двоичных чисел, патент № 2383052 {1,устройство сортировки двоичных чисел, патент № 2383052 ,n} (x(1)устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 устройство сортировки двоичных чисел, патент № 2383052 x(n); устройство сортировки двоичных чисел, патент № 2383052

Таким образом, при Vi0=x i, W0j=xminустройство сортировки двоичных чисел, патент № 2383052 xi (при Vi0=xmax, W 0j=xjустройство сортировки двоичных чисел, патент № 2383052 xmax) в моменты времени t1,устройство сортировки двоичных чисел, патент № 2383052 ,tn (в момент времени tn) имеем W n1=x(n),устройство сортировки двоичных чисел, патент № 2383052 ,Wnn=x(1) (V1n=x(1) ,устройство сортировки двоичных чисел, патент № 2383052 ,Vnn=x(n)), то есть предлагаемое устройство формирует сортированный последовательный (параллельный) набор m-разрядных двоичных чисел x1,устройство сортировки двоичных чисел, патент № 2383052 ,xn.

Таблица 1
V11=xmin V21=x1x2 V31=x1x3устройство сортировки двоичных чисел, патент № 2383052 x2x3 V41=x1x4устройство сортировки двоичных чисел, патент № 2383052 x2x4устройство сортировки двоичных чисел, патент № 2383052 x3x4
W11=x1 W21=x1устройство сортировки двоичных чисел, патент № 2383052 x2 W31=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3 W41=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3устройство сортировки двоичных чисел, патент № 2383052 x4
V12=xmin V22=xmin V32=x1x2x3 V42=x1x2x4устройство сортировки двоичных чисел, патент № 2383052 x1x3x4устройство сортировки двоичных чисел, патент № 2383052 x2x3x4
W12=xmin W22=x1x2 W32=x1x2устройство сортировки двоичных чисел, патент № 2383052 x1x3устройство сортировки двоичных чисел, патент № 2383052 x2x3 W42=x1x2устройство сортировки двоичных чисел, патент № 2383052 x1x3устройство сортировки двоичных чисел, патент № 2383052 x1x4устройство сортировки двоичных чисел, патент № 2383052 x2x3устройство сортировки двоичных чисел, патент № 2383052 x2x4устройство сортировки двоичных чисел, патент № 2383052 x3x4
V13=xmin V23=xmin V33=xmin V43=x1x2x3x4
W 13=xmin W23=xmin W33=x1x2x3 W43=x1x2x3устройство сортировки двоичных чисел, патент № 2383052 x1x2x4устройство сортировки двоичных чисел, патент № 2383052 x1x3x4устройство сортировки двоичных чисел, патент № 2383052 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
W 11=xmax W12=x1устройство сортировки двоичных чисел, патент № 2383052 x2 W13=x1x2устройство сортировки двоичных чисел, патент № 2383052 x3 W14=x1x2x3устройство сортировки двоичных чисел, патент № 2383052 x4
V21=xmax V22=x1x2 V23=x1x2устройство сортировки двоичных чисел, патент № 2383052 x1x3устройство сортировки двоичных чисел, патент № 2383052 x2x3 V24=x1x2x3устройство сортировки двоичных чисел, патент № 2383052 x1x2x4устройство сортировки двоичных чисел, патент № 2383052 x1x3x4устройство сортировки двоичных чисел, патент № 2383052 x2x3x4
W21=xmax W22=xmax W23=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3 W24=x1x2устройство сортировки двоичных чисел, патент № 2383052 x1x3устройство сортировки двоичных чисел, патент № 2383052 x2x3устройство сортировки двоичных чисел, патент № 2383052 x4
V31=xmax V32=xmax V33=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3 V34=x1x2устройство сортировки двоичных чисел, патент № 2383052 x1x3устройство сортировки двоичных чисел, патент № 2383052 x1x4устройство сортировки двоичных чисел, патент № 2383052 x2x3устройство сортировки двоичных чисел, патент № 2383052 x2x4устройство сортировки двоичных чисел, патент № 2383052 x3x4
W31=xmax W32=xmax W33=xmax W34=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3устройство сортировки двоичных чисел, патент № 2383052 x4
V41=xmax V42=xmax V43=xmax V44=x1устройство сортировки двоичных чисел, патент № 2383052 x2устройство сортировки двоичных чисел, патент № 2383052 x3устройство сортировки двоичных чисел, патент № 2383052 x4
W41=xmax W42=xmax W43=xmax W44=xmax

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

Класс G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации

способ и система поиска нарушений авторских прав на изображения -  патент 2515706 (20.05.2014)
медиа-процессор для организации мультимедийных данных -  патент 2487395 (10.07.2013)
интеграция рекламы и расширяемые темы для операционных систем -  патент 2473127 (20.01.2013)
устройство сортировки двоичных чисел -  патент 2445678 (20.03.2012)
устройство перепаковки потоков для ввода данных -  патент 2414742 (20.03.2011)
селектор двоичных чисел -  патент 2365975 (27.08.2009)
устройство селекции двоичных чисел -  патент 2363038 (27.07.2009)
устройство сравнения двоичных чисел -  патент 2353966 (27.04.2009)
способ и устройство для обработки графической информации, имеющейся на почтовых отправлениях -  патент 2349395 (20.03.2009)
устройство сортировки двоичных чисел -  патент 2346321 (10.02.2009)
Наверх