устройство сортировки двоичных чисел
Классы МПК: | G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации |
Автор(ы): | Андреев Дмитрий Васильевич (RU) |
Патентообладатель(и): | Государственное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" (RU) |
Приоритеты: |
подача заявки:
2007-12-25 публикация патента:
27.02.2010 |
Устройство сортировки двоичных чисел предназначено для сортировки 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-разрядных двоичных чисел x1, ,xn (m разрядов числа xj , задаваемых m двоичными сигналами, подаются в j-й момент времени на (m+1)-й - (m+m)-й входы первого логического модуля, при этом на k-м входе всех логических модулей фиксируется логическая 1 в их сортированный параллельный набор х(1), ,x(n) (х(1) x(n); так, что m разрядов числа x(i) в n-й момент времени формируются на (m+1)-м - (m+m)-м выходах i-го логического модуля, либо устройство сортировки двоичных чисел выполняет преобразование несортированного параллельного набора m-разрядных двоичных чисел x1, ,xn (m разрядов числа xi, задаваемых m двоичными сигналами, подаются в первый момент времени на первый - m-й входы i-го логического модуля, при этом на (m+k)-м входе первого логического модуля фиксируется логический 0) в их сортированный последовательный набор х(1), ,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-ом логическом модуле первый управляющий и 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 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие принцип его работы.
Устройство сортировки двоичных чисел содержит логические модули 11, ,1n. Модуль 1i (i {1, ,n}) содержит размыкающие и замыкающие ключи 21 , ,2m и 31, ,3m, постоянное запоминающее устройство 4, регистр 5, причем выход ключа соединен с выходом ключа 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)-ым входом последующего логического модуля, а объединенные первые и объединенные вторые управляющие входы всех логических модулей подключены соответственно к первому и второму настроечным входам устройства сортировки двоичных чисел.
Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y1,у2 {0,1} (фиг.2), причем длительность Т* высокого уровня сигнала y1 и период Т сигнала y2 должны удовлетворять условиям Т*> t* и Т> t, где t*=n 1, t=n 1+ 2, а 1 и 2 есть длительности задержек, вносимых соответственно устройством 4 и регистром 5. Подлежащие сортировке m-разрядные двоичные числа x1, ,x2, задаваемые двоичными сигналами, либо последовательно подаются согласно фиг.2 на модуль 11 (при этом на входе всех модулей фиксируется логическая «1») либо параллельно подаются в течение времени действия высокого уровня сигнала у1 соответственно на модули 11 , ,1n: V10=x1, ,Vn0=xn (при этом на (m+k)-ом входе модуля 11 фиксируется логический «0»). Если у1=1 (y1=0), то ключи 31, ,3m замкнуты (разомкнуты), ключи 21 , ,2m разомкнуты (замкнуты). Загрузка данных в регистр 5 происходит по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2 ). В устройстве 4 q-я ячейка с адресом содержит 2 m-разрядный двоичный код d*m-1 d*0 dm-1 d0, в котором d*m-1 d*0=max(a*m-1 a*0, am-1 a0), dm-1 d0=min(a*m-1 a*0, am-1 a0). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на (m+1)-ом - (m+m)-ом и первом - m-ом выходах модуля будут определяться рекуррентными выражениями
где символами и · обозначены операции max и min; есть номер момента времени tj (фиг.2); V i0=xi, W0j=xmin xi либо Vi0=xmax, W 0j=xj xmax. В представленных ниже табл.1 и табл.2 приведены значения выражений (1) при n=4, если соответственно Vi0=xi, W0j=xmin xi и V0j=xmax, W0j =xj xmax. С учетом данных, приведенных в табл.1 и табл.2, нетрудно вывести непосредственные выражения для соответственно Wnj и Vin
где xs1 xsn {x1, xn}; есть количество неповторяющихся фрагментов xs1 xsj (xsi xsn), определяемое как число сочетаний из n по j (по n+1-i). При j=n+1-r выражение (2) и при i=r выражение (3) совпадают с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x1, ,xn} элемента x(r) заданного ранга r {1, ,n} (x(1) x(n);
Таким образом, при Vi0=x i, W0j=xmin xi (при Vi0=xmax, W 0j=xj xmax) в моменты времени t1, ,tn (в момент времени tn) имеем W n1=x(n), ,Wnn=x(1) (V1n=x(1) , ,Vnn=x(n)), то есть предлагаемое устройство формирует сортированный последовательный (параллельный) набор m-разрядных двоичных чисел x1, ,xn.
Таблица 1 | |||
V11=xmin | V21=x1x2 | V31=x1x3 x2x3 | V41=x1x4 x2x4 x3x4 |
W11=x1 | W21=x1 x2 | W31=x1 x2 x3 | W41=x1 x2 x3 x4 |
V12=xmin | V22=xmin | V32=x1x2x3 | V42=x1x2x4 x1x3x4 x2x3x4 |
W12=xmin | W22=x1x2 | W32=x1x2 x1x3 x2x3 | W42=x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 |
V13=xmin | V23=xmin | V33=xmin | V43=x1x2x3x4 |
W 13=xmin | W23=xmin | W33=x1x2x3 | W43=x1x2x3 x1x2x4 x1x3x4 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 x2 | W13=x1x2 x3 | W14=x1x2x3 x4 |
V21=xmax | V22=x1x2 | V23=x1x2 x1x3 x2x3 | V24=x1x2x3 x1x2x4 x1x3x4 x2x3x4 |
W21=xmax | W22=xmax | W23=x1 x2 x3 | W24=x1x2 x1x3 x2x3 x4 |
V31=xmax | V32=xmax | V33=x1 x2 x3 | V34=x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 |
W31=xmax | W32=xmax | W33=xmax | W34=x1 x2 x3 x4 |
V41=xmax | V42=xmax | V43=xmax | V44=x1 x2 x3 x4 |
W41=xmax | W42=xmax | W43=xmax | W44=xmax |
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает преобразование несортированного последовательного набора задаваемых двоичными сигналами n m-разрядных двоичных чисел в их сортированный параллельный набор либо преобразование несортированного параллельного набора указанных чисел в их сортированный последовательный набор.
Класс G06F7/06 устройства для сортировки, выборки, подборки или сравнения данных на отдельных носителях информации