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

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

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

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

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

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

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

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

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сортировки двоичных чисел (патент РФ 2300136, кл. G06F 7/06, 2007 г.), которое содержит два настроечных входа, m информационных входов, n групп первого - m-го выходов и выполняет сортировку n (nустройство сортировки двоичных чисел, патент № 2346321 2) m-разрядных двоичных чисел, задаваемых двоичными сигналами.

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

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

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

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

Устройство сортировки двоичных чисел содержит n-1 постоянных запоминающих устройств 1 1,...1n-1, каждое из которых имеет объем (2m+2)×22m+2 бит, n-1 регистров 21,...2n-1, каждый из которых имеет разрядность m+1 бит, маркерный вход 3, m информационных входов 4, два настроечных входа 51, 5 2, n групп 61, ..., 6 n первого - m-го выходов, маркерные выходы 7 1, ..., 7n, причем k-й (устройство сортировки двоичных чисел, патент № 2346321 ) выход устройства 1i (устройство сортировки двоичных чисел, патент № 2346321 ) соединен с k-м входом регистра 2i , подключенного входом записи к входу 52 устройства сортировки двоичных чисел, a (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства подключен к (m+k+1)-му адресному входу последующего постоянного запоминающего устройства, k-й выход и вход сброса регистра 2 i соединены соответственно с k-м адресным входом постоянного запоминающего устройства 1i и входом 5 1 устройства сортировки двоичных чисел, (2m+2)-й адресный вход устройства 11 подключен к входу 3 устройства сортировки двоичных чисел, а (m+1)-й выход устройства li и (2m+2)-й выход устройства 1 n-1 подключены соответственно к выходам 7 i и 7n устройства сортировки двоичных чисел, l-й (устройство сортировки двоичных чисел, патент № 2346321 ) информационный вход, группы 6i и 6n первого - m-го выходов которого соединены соответственно с (m+l+1)-м адресным входом устройства 1 1, первым - m-м выходами устройства 1i и (m+2)-м - (2m+1)-м выходами устройства 1n-1 .

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы у 1, у2 устройство сортировки двоичных чисел, патент № 2346321 {0,1} (фиг.2), причем период Т сигнала у 2 должен удовлетворять условию Т>устройство сортировки двоичных чисел, патент № 2346321 t, где устройство сортировки двоичных чисел, патент № 2346321 t=устройство сортировки двоичных чисел, патент № 2346321 2+(n-1)устройство сортировки двоичных чисел, патент № 2346321 1, a устройство сортировки двоичных чисел, патент № 2346321 1 и устройство сортировки двоичных чисел, патент № 2346321 2 есть длительности задержек, вносимых соответственно устройством li и регистром 2i (iустройство сортировки двоичных чисел, патент № 2346321 {1,...n-1}). Синхронно с передним фронтом импульса сигнала у1 и передними фронтами первого,...,(n-1)-го импульсов сигнала у2 на m информационных входов предлагаемого устройства последовательно подаются соответственно первый и второй,...,n-й наборы m произвольных двоичных сигналов, задающие m-разрядные двоичные числа х1 и x2,...хn соответственно (фиг.2). Синхронно с передним фронтом импульса сигнала у 1 и передними фронтами первого,...,(n-1)-го импульсов сигнала у2 на маркерный вход предлагаемого устройства последовательно подаются соответственно первый и второй,...,n-й двоичные сигналы, задающие единичные маркерные биты. Обнуление выходных сигналов регистра 2i и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала у1) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала у 2). В устройстве 1i q-я устройство сортировки двоичных чисел, патент № 2346321 ячейка с адресом а* m...а* 0а m...а0 содержит (2m+2)-разрядный двоичный код d* m ...d* 0d m...d0, в котором d * m-1...d* 0=min(a* m-1...a* 0,a m-1...a0), dm-1 ...d0=max(a* m-1...a* 0,a m-1...a0), d* m=1 при a* m=1 и a* m...a * 0m...а 0 или am=1 и а* m...а* 0m...а0 , dm=1 при a* m=1 и а* m...a * 0>am...a 0 или am=1 и а* m...а* 0устройство сортировки двоичных чисел, патент № 2346321 am...а0, в остальных случаях d* m =0 и dm=0. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом,...,m-м и (m+2)-м,...,(2m+1)-м выходах устройства 1i (устройство сортировки двоичных чисел, патент № 2346321 ), маркерные биты на (m+1)-м и (2m+2)-м выходах устройства 1i будут определяться соответственно рекуррентными выражениями

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

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

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

Здесь символами устройство сортировки двоичных чисел, патент № 2346321 , · и &, * обозначены операции max, min и И, ИЛИ; j=устройство сортировки двоичных чисел, патент № 2346321 есть номер момента времени tj (фиг.2); Vi0=0; W0j j; устройство сортировки двоичных чисел, патент № 2346321 i0=0; w0j=1. В представленной ниже таблице 1 приведены значения выражений (1) при n=4

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

В таблице 2 приведены значения выражений (1) и (2), когда x1=с, х2 =b, х3=а, x4=b и а>b>с.

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

С учетом данных, приведенных в таблице 1, нетрудно вывести непосредственное выражение, определяющее m-разрядное двоичное число, задаваемое двоичными сигналами на g-й (g=устройство сортировки двоичных чисел, патент № 2346321 ) группе m выходов предлагаемого устройства при j=n:

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

где хs1устройство сортировки двоичных чисел, патент № 2346321 ...устройство сортировки двоичных чисел, патент № 2346321 xsgустройство сортировки двоичных чисел, патент № 23463211...,хn}; устройство сортировки двоичных чисел, патент № 2346321 есть количество неповторяющихся фрагментов x s1...xsg, определяемое как число сочетаний из n по g. При g=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x 1,...,хn} элемента х (r) заданного ранга rустройство сортировки двоичных чисел, патент № 2346321 {1,...,n} (х(1)устройство сортировки двоичных чисел, патент № 2346321 ...устройство сортировки двоичных чисел, патент № 2346321 х(n); {x(1) }устройство сортировки двоичных чисел, патент № 2346321 ...устройство сортировки двоичных чисел, патент № 2346321 {x(n)}={x1,...,x n}). Таким образом, предлагаемое устройство будет воспроизводить операцию

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

сортировки m-разрядных двоичных чисел x 1,...,xn. При этом согласно таблице 2 предлагаемое устройство выполняет распознавание дубликатов сортируемых чисел (дубликат маркируется нулевым маркерным битом).

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

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

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