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

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

 

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

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

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем n-1 постоянных запоминающих устройств и n-1 регистров, k-й выход i-го постоянного запоминающего устройства соединен с 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 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие принцип его работы.

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

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы 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-разрядные двоичные числа x1 и х2, ..., xn соответственно (фиг.2). Обнуление выходных сигналов регистра 2i и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала y1) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2). В устройстве 1i q-я ячейка с адресом содержит 2m-разрядный двоичный код , в котором . Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, ..., m-м и (m+1)-м, ..., (2m)-м выходах устройства 1i , будут определяться соответственно рекуррентными выражениями

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

V11=x1V12=x1∨x2V13=x1∨x2∨x3V14=x1∨x2∨x3∨x4
W11=0W12=x1x2W13=x1x3∨x2x3W14=x1x4∨x2x4∨x3x4
V21=0V22=x1x2V23=x1x2∨x1x3∨x2x3V24=x1x2∨x1x3∨x1x4
W21=0W22=0W23=x1x2x3∨x2x3∨x2x4∨x3x4
W24=x1x2x4∨x1x3x4∨x2x3x4
V31=0V32=0V33=x1x2x3V34=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4
W31=0W32=0W33=0W34=x1x2x3x4

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

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

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

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

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



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наверх