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

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

 

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

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

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

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

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

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

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

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

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

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы у1, у2 ∈{0,1} (фиг.2), причем период Т сигнала у2 должен удовлетворять условию Т>Δt, где Δt=τ2+(n-1)τ1, a τ1 и τ2 есть длительности задержек, вносимых соответственно устройством li и регистром 2i (i∈{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-я ячейка с адресом а*m...а*0аm...а0 содержит (2m+2)-разрядный двоичный код d*m...d*0dm...d0, в котором d*m-1...d*0=min(a*m-1...a*0,am-1...a0), dm-1...d0=max(a*m-1...a*0,am-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...a0 или am=1 и а*m...а*0≤am...а0, в остальных случаях d*m=0 и dm=0. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом,...,m-м и (m+2)-м,...,(2m+1)-м выходах устройства 1i (), маркерные биты на (m+1)-м и (2m+2)-м выходах устройства 1i будут определяться соответственно рекуррентными выражениями

где

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

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

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

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

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

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

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



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наверх