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

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

 

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

Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку n m-разрядных двоичных чисел (см., например, патент РФ 2300136, кл. G06F 7/06, 2007 г.).

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

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

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

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения правильного распознавания переменной x1=0 при распознавании сортируемых m-разрядных двоичных чисел x1, …, xn, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».

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

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

Устройство сортировки двоичных чисел содержит постоянные запоминающие устройства 11, …, 1n-1, регистры 21, …, 2n-1 и инверторы 31, …, 32n-2, причем k-й выход устройства 1i соединен с k-м входом регистра 2i, подключенного входом сброса, входом записи и p-м выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и p-му адресному входу устройства 1i, (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+1)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход устройства 11 подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+1)-м адресным входом устройства 11, первым - m-м выходами устройства 1i и (m+2)-м - (2m+1)-м выходами устройства ln-1, вход и выход инвертора 3i соединены соответственно с (m+1)-м выходом устройства 1i и объединенными (m+1)-м входом регистра 2i, i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход инвертора подключены соответственно к (2m+2)-му выходу устройства 1l и (2m+2)-му адресному входу устройства 1l+1, а вход и выход инвертора 32n-2 соединены соответственно с (2m+2)-м выходом устройства ln-1 и n-м маркерным выходом устройства сортировки двоичных чисел.

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

где

Здесь символами ∨, · и &, * обозначены операции max, min и И, ИЛИ; есть номер момента времени tj (фиг.2); Vi0=0; W0jj≥0; vi0=w0j=0. В представленной ниже таблице 1 приведены значения выражений (1) при n=4.

Таблица 1
V11=x1 V12=x1∨x2 V13=x1∨x2∨x3 V14=x1∨x2∨x3∨x4
W11=0 W12=x1x2 W13=x1x3∨x2x3 W14=x1x4∨x2x4∨x3x4
V21=0 V22=x1x2 V23=x1x2∨x1x3∨x2x3 V24=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4
W21=0 W22=0 W23=x1x2x3 W24=x1x2x4∨x1x3x4∨x2x3x4
V31=0 V32=0 V33=x1x2x3 V34=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
W31=0 W32=0 W33=0 W34=x1x2x3x4

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

Таблица 2
j W0j V1j v1j W1j w1j V2j v2j W2j w2j V3j v3j W3j w3j
1 с с 0 0 1 0 0 0 1 0 0 0 1
2 b b 0 с 0 с 0 0 1 0 0 0 1
3 а а 0 b 0 b 0 с 0 с 0 0 1
4 b а 0 b 0 b 0 b 1 b 1 с 0

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

где хs1≠…≠хsg∈{х1, …, хn}; есть количество неповторяющихся фрагментов xs1…xsg, определяемое как число сочетаний из n по g. При g=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {х1, …, хn} элемента х(r) заданного ранга r∈{1, …, xn} (x(1)≤…≤x(n); {x(1)}∪…∪{x(n)}={x1, …, xn}). Таким образом, имеем V1n=x(n), …, V(n-1)n=x(2), W(n-1)n=x(1) то есть предлагаемое устройство выполняет сортировку m-разрядных двоичных чисел х1, …, хn. При этом согласно таблице 2 предлагаемое устройство распознает сортируемые числа по принципу «дубликат - не дубликат» (дубликат маркируется единичным маркерным битом).

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает правильное распознавание переменной х1=0 при распознавании сортируемых m-разрядных двоичных чисел x1, …, xn, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».

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



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в компьютерных системах для поиска и выявления изображений, авторские права на которые нарушены. Техническим результатом является повышение точности, качества и скорости поиска идентичных или сходных до степени смешения изображений. В способе поиска нарушений авторских прав на изображения, выполняемом на компьютерной системе, производят расчет дескриптора для изображения №1, располагающегося в блоке памяти №1. Выполняют расчет дескриптора для изображения №2, располагающегося в блоке памяти №2. Сравнивают значения дескрипторов изображений №1 и №2. Если значения дескрипторов изображений №1 и №2 равны, то выполняют сравнение изображений №1 и №2. После чего отображают результаты сравнения на устройстве для отображения информации. 6 н. и 7 з.п. ф-лы, 5 ил.

Изобретение относится к области синхронизации записей в медицинской среде. Техническим результатом является обеспечение интегрирования двух и более источников данных посредством уникального номера записи в корпоративном реестре. В способе назначают уникальный номер записи пользовательской записи; сравнивают демографическую информацию пользовательской записи с по меньшей мере одной демографической информацией другой записи в совокупности записей из по меньшей мере одного другого источника данных для расчета отношения правдоподобия для каждой сравниваемой записи; сравнивают каждое отношение правдоподобия с заданным порогом допустимости и с заданным порогом отказа, при этом идентифицируют пользовательские записи для ручного рассмотрения, если отношение правдоподобия попадает между порогом допустимости и порогом отказа; прикрепляют утверждение для сравненных пользовательских записей на основе сравнения по меньшей мере одного отношения правдоподобия; и размещают пользовательские записи, для которых должно быть выполнено ручное рассмотрение, в списке исключений и распределяют список исключений на каждый источник данных. 4 н. и 11 з.п. ф-лы, 5 ил.

Изобретение относится к работам на месторождении. Технический результат - извлечение флюида из пластов-коллекторов в наземные установки, используя выходные данные, сгенерированные с использованием главного приложения на основании результата поиска. Технический результат достигается тем, что выполняют: извлечение контекстной информации из главного приложения; сортировку контекстной информации на совокупность аспектов релевантности, для каждого из которых генерируют профиль поиска, с использованием которого запрашивают первую совокупность поисков; прием совокупности элементов данных месторождения, определяющих атрибут объекта месторождения, полученных от первой совокупности поисков; получение меры качества; передачу элемента данных месторождения как результат поиска главному приложению, если мера качества превышает заранее определенный порог согласованности; запрос второй совокупности поисков, которую ограничивают часто используемой фразой; генерирование выходных данных на основе второго результата поиска и выполнение работы на месторождении с использованием выходных данных. 3 н. 17 з.п. ф-лы, 16 ил.

Изобретение относится к средствам динамического управления информацией списков контактов в мультимодальной системе связи. Технический результат заключается в уменьшении времени на управление списком контактов. Определяют профиль пользователя. Определяют информацию о контактах, ассоциированную с контактами, в списке контактов для пользователя. Вычисляют взвешенные коэффициенты для каждого из контактов на основе информации о контактах. Вычисляют общий вес для каждого контакта на основе взвешенных коэффициентов, ассоциированных с каждым контактом. Упорядочивают список контактов на основе общего веса каждого контакта в списке контактов. Представляют упорядоченный список контактов пользователю через дисплей устройства, ассоциированного с пользователем. Обновляют взвешенные коэффициенты в качестве реакции на изменения в информации о контактах и основываясь на обратной связи от множества ассоциированных с пользователем устройств, отображающих список контактов, на основе одной или более возможностей каждого устройства и соответствующих возможностей контактов в списке контактов. Динамически переупорядочивают список контактов на основе обновленных взвешенных коэффициентов. Настраивают и переупорядочивают список контактов для каждого из множества ассоциированных с пользователем устройств. 3 н. и 16 з.п. ф-лы, 8 ил.

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

Изобретение относится к средствам проведения поиска. Технический результат заключается в повышении релевантности результатов поиска. Получают поисковый запрос от электронного устройства, связанного с пользователем. В ответ на поисковый запрос составление ранжированного набора результатов поискового запроса, причем ранжированный набор результатов поискового запроса содержит результат общего поиска и результат вертикального поиска, каждый из результатов общего поиска и вертикального поиска получен из соответствующего поискового источника, результат вертикального поиска представлен виджетом. Определяют степень уверенности в том, что результат вертикального поиска является наиболее релевантным по отношению к поисковому запросу. В ответ на степень уверенности, находящуюся выше заранее установленного порога, инициацию отображения электронным устройством исключительно результата вертикального поиска, представленного виджетом. В ответ на степень уверенности, находящуюся ниже заранее установленного порога, инициацию отображения электронным устройством результата общего поиска и результата вертикального поиска. 4 н. и 30 з.п. ф-лы, 12 ил.

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления. Техническим результатом является обеспечение возможности выбора среднего из трех двоичных двухразрядных чисел, а также минимального или максимального из двух двоичных двухразрядных чисел. Устройство содержит шесть входов устройства, два выхода устройства, три элемента НЕ, четырнадцать элементов И, семь элементов ИЛИ. 1 ил., 2 табл.

Изобретение относится к области создания списка поисковых предложений. Технический результат – обеспечение возможности создания списка поисковых предложений. Способ создания списка поисковых предложений, выполняемый на сервере и включающий в себя получение по меньшей мере части поискового запроса от пользователя; создание ранжированного множества поисковых предложений для части поискового запроса; определение по меньшей мере частично на основе параметра связи, связано ли каждое поисковое предложение с соответствующим поисковым источником, причем параметр связи определяет степень релевантности каждого поискового предложения для каждого соответствующего поискового источника; в ответ на определение того, что поисковое предложение связано с соответствующим поисковым источником, создание группы предложений для каждого соответствующего поискового источника, причем каждая группа предложений предназначена для представления соответствующей подгруппы множества поисковых предложений, и соответствующая подгруппа включает в себя только поисковые предложения, связанные с соответствующим поисковым источником; и создание списка поисковых предложений, в котором каждая соответствующая подгруппа сгруппирована в каждой соответствующей группе предложений, причем каждая группа предложений отображается отдельно. 2 н. и 24 з.п. ф-лы, 4 ил.

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

Наверх