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

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

 

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

Известны устройства сортировки двоичных чисел (см., например, фиг.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)-ым входом последующего логического модуля, а объединенные первые и объединенные вторые управляющие входы всех логических модулей подключены соответственно к первому и второму настроечным входам устройства сортировки двоичных чисел.

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y12∈{0,1} (фиг.2), причем длительность Т* высокого уровня сигнала y1 и период Т сигнала y2 должны удовлетворять условиям Т*>Δt* и Т>Δt, где Δt*=nτ1, Δt=nτ12, а τ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); Vi0=xi, W0j=xmin≤xi либо Vi0=xmax, W0j=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=xi, W0j=xmin≤xi (при Vi0=xmax, W0j=xj≤ xmax) в моменты времени t1,…,tn (в момент времени tn) имеем Wn1=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
W13=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
W11=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-разрядных двоичных чисел в их сортированный параллельный набор либо преобразование несортированного параллельного набора указанных чисел в их сортированный последовательный набор.

Устройство сортировки двоичных чисел, содержащее 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, располагающегося в блоке памяти №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 ил.
Наверх