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



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

 


Владельцы патента RU 2445678:

Закрытое акционерное общество "ИВЛА-ОПТ" (RU)

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом является расширение функциональных возможностей за счет правильного распознавания переменной 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 ил.
Наверх