Патент на изобретение №2300136
|
||||||||||||||||||||||||||||||||
(54) УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ
(57) Реферат:
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления. Техническим результатом является уменьшение аппаратурных затрат. Устройство содержит n-1 постоянных запоминающих устройств, n-1 регистров, два настроечных входа, n групп выходов, информационные входы. 1 табл., 2 ил.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др. Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку n (n К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сортировки двоичных чисел, относится ограниченные функциональные возможности, обусловленные тем, что не выполняется сортировка n (n Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство сортировки двоичных чисел (патент РФ 2264645, кл. G06F 7/06, 2005 г.), которое содержит n-1 постоянных запоминающих устройств, n-1 регистров и выполняет сортировку n (n К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится большие аппаратурные затраты. Техническим результатом изобретения является уменьшение аппаратурных затрат при сохранении функциональных возможностей прототипа. Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем n-1 постоянных запоминающих устройств и n-1 регистров, k-й На фиг.1 и фиг.2 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие принцип его работы. Устройство сортировки двоичных чисел содержит постоянные запоминающие устройства 11, …, 1n-1 и регистры 21, …, 2n-1, причем k-й Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y1, y2
где символами
С учетом данных, приведенных в таблице, нетрудно вывести непосредственное выражение, определяющее m-разрядное двоичное число, задаваемое двоичными сигналами на g-й
где хs1
сортировки m-разрядных двоичных чисел х1, …, хn. Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел выполняет сортировку n (n
Формула изобретения
Устройство сортировки двоичных чисел, содержащее n-1 постоянных запоминающих устройств и n-1 регистров, причем k-й
РИСУНКИ
MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 24.12.2007
Извещение опубликовано: 20.05.2009 БИ: 14/2009
|
||||||||||||||||||||||||||||||||
выход i-го 
постоянного запоминающего устройства соединен с k-м входом i-го регистра, подключенного входом записи к второму настроечному входу устройства сортировки двоичных чисел, а (m+k)-й выход каждого предыдущего постоянного запоминающего устройства подключен к (m+k)-му адресному входу последующего постоянного запоминающего устройства, особенность заключается в том, что k-й выход и вход сброса i-го регистра соединены соответственно с k-м адресным входом i-го постоянного запоминающего устройства и первым настроечным входом устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого – m-го выходов которого образованы соответственно (m+k)-м адресным входом первого, первым – m-м выходами i-го и (m+1)-м – (2m)-м выходами (n-1)-го постоянных запоминающих устройств.
выход устройства 1i 
соединен с k-м входом регистра 2i, подключенного k-м выходом и входом сброса, входом записи соответственно к k-му адресному входу устройства 1i и первому, второму настроечным входам устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого – m-го выходов которого образованы соответственно (m+k)-м адресным входом устройства 11, первым – m-м выходами устройства 1i и (m+1)-м – (2m)-м выходами устройства 1n-1, а (m+k)-й выход каждого предыдущего постоянного запоминающего устройства подключен к (m+k)-му адресному входу последующего постоянного запоминающего устройства.
{0,1} (фиг.2), причем период Т сигнала y2 должен удовлетворять условию T>
t, где 
2+(n-1)
ячейка с адресом 
содержит 2m-разрядный двоичный код 
, в котором 
. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, …, m-м и (m+1)-м, …, (2m)-м выходах устройства 1i 
, будут определяться соответственно рекуррентными выражениями
и · обозначены операции max и min; 
есть номер момента времени tj (фиг.2); Vi0=0; W0j=хj. В представленной ниже таблице приведены значения выражений (1) при n=4.
группе m выходов предлагаемого устройства при j=n:
…
есть количество неповторяющихся фрагментов хs1…xsg, определяемое как число сочетаний из n по g. При g=n+1-r выражение (2) совпадает с видом поисковой функции (функция (6.7) на стр. 117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x1,…,xn} элемента х(r) заданного ранга r
выход 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)-го постоянных запоминающих устройств.
