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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y1, y 2устройство сортировки двоичных чисел, патент № 2300136 {0,1} (фиг.2), причем период Т сигнала y 2 должен удовлетворять условию T>устройство сортировки двоичных чисел, патент № 2300136 t, где устройство сортировки двоичных чисел, патент № 2300136 t=устройство сортировки двоичных чисел, патент № 2300136 2+(n-1)устройство сортировки двоичных чисел, патент № 2300136 1, a устройство сортировки двоичных чисел, патент № 2300136 1 и устройство сортировки двоичных чисел, патент № 2300136 2 есть длительности задержек, вносимых соответственно устройством 1i и регистром 2i (iустройство сортировки двоичных чисел, патент № 2300136 {1, ..., n-1}). Синхронно с передним фронтом импульса сигнала y1 и передними фронтами первого, ..., (n-1)-го импульсов сигнала y2 на m информационных входов предлагаемого устройства последовательно подаются соответственно первый и второй, ..., n-й наборы m произвольных двоичных сигналов, задающие m-разрядные двоичные числа x1 и х2, ..., xn соответственно (фиг.2). Обнуление выходных сигналов регистра 2 i и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала y 1) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2). В устройстве 1i q-я устройство сортировки двоичных чисел, патент № 2300136 ячейка с адресом устройство сортировки двоичных чисел, патент № 2300136 содержит 2m-разрядный двоичный код устройство сортировки двоичных чисел, патент № 2300136 , в котором устройство сортировки двоичных чисел, патент № 2300136 устройство сортировки двоичных чисел, патент № 2300136 . Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, ..., m-м и (m+1)-м, ..., (2m)-м выходах устройства 1i устройство сортировки двоичных чисел, патент № 2300136 , будут определяться соответственно рекуррентными выражениями

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

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

V11=x 1V12=x 1устройство сортировки двоичных чисел, патент № 2300136 x2V 13=x1устройство сортировки двоичных чисел, патент № 2300136 x2устройство сортировки двоичных чисел, патент № 2300136 x3V 14=x1устройство сортировки двоичных чисел, патент № 2300136 x2устройство сортировки двоичных чисел, патент № 2300136 x3устройство сортировки двоичных чисел, патент № 2300136 x4
W11=0W 12=x1x2 W13=x1 x3устройство сортировки двоичных чисел, патент № 2300136 x2x3 W14=x1x 4устройство сортировки двоичных чисел, патент № 2300136 x2x4устройство сортировки двоичных чисел, патент № 2300136 x3x4
V21=0 V22=x1x 2V23=x 1x2устройство сортировки двоичных чисел, патент № 2300136 x1x3устройство сортировки двоичных чисел, патент № 2300136 x2x3 V24=x1x 2устройство сортировки двоичных чисел, патент № 2300136 x1x3устройство сортировки двоичных чисел, патент № 2300136 x1x4устройство сортировки двоичных чисел, патент № 2300136
W21 =0W22=0 W23=x1x 2x3устройство сортировки двоичных чисел, патент № 2300136 x2x3устройство сортировки двоичных чисел, патент № 2300136 x2x4устройство сортировки двоичных чисел, патент № 2300136 x3x4
    W24=x 1x2x4устройство сортировки двоичных чисел, патент № 2300136 x1x3x 4устройство сортировки двоичных чисел, патент № 2300136 x2x3x 4
V31 =0V32=0 V33=x1x 2x3V 34=x1x2x 3устройство сортировки двоичных чисел, патент № 2300136 x1x2x 4устройство сортировки двоичных чисел, патент № 2300136 x1x3x 4устройство сортировки двоичных чисел, патент № 2300136 x2x3x 4
W31 =0W32=0 W33=0W 34=x1x2x 3x4

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

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

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

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

сортировки m-разрядных двоичных чисел х 1, ..., хn.

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

Класс 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)
Наверх