close

Вход

Забыли?

вход по аккаунту

?

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

код для вставки
РОССИЙСКАЯ ФЕДЕРАЦИЯ
RU
(19)
(11)
2 300 136
(13)
C1
(51) МПК
G06F 7/06
(2006.01)
ФЕДЕРАЛЬНАЯ СЛУЖБА
ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ,
ПАТЕНТАМ И ТОВАРНЫМ ЗНАКАМ
(12)
ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ
(21), (22) За вка: 2005140505/09, 23.12.2005
(72) Автор(ы):
Андреев Дмитрий Васильевич (RU)
(24) Дата начала отсчета срока действи патента:
23.12.2005
(45) Опубликовано: 27.05.2007 Бюл. № 15
результатом вл етс уменьшение аппаратурных
затрат. Устройство содержит n-1 посто нных
запоминающих устройств, n-1 регистров, два
настроечных
входа,
n
групп
выходов,
информационные входы. 1 табл., 2 ил.
R U
2 3 0 0 1 3 6
(57) Реферат:
Изобретение относитс к вычислительной
технике и может быть использовано дл построени средств автоматики, функциональных
узлов
систем
управлени .
Техническим
Страница: 1
RU
C 1
C 1
(54) УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ
2 3 0 0 1 3 6
Адрес дл переписки:
432027, г.Уль новск, Северный Венец, 32, ГОУ
ВПО "Уль новский государственный технический
университет", Проректору по научной работе
R U
(56) Список документов, цитированных в отчете о
поиске: RU 2264645 C1, 20.11.2005. RU 2050583
С1, 20.12.1995. RU 2095850 C1, 10.11.1997. SU
1783511 А1, 23.12.1992. SU 1647562 A1,
07.05.1991. US 3740538 A, 19.06.1973.
(73) Патентообладатель(и):
Государственное образовательное учреждение
высшего профессионального образовани "Уль новский государственный технический
университет" (RU)
RUSSIAN FEDERATION
RU
(19)
(11)
2 300 136
(13)
C1
(51) Int. Cl.
G06F 7/06
(2006.01)
FEDERAL SERVICE
FOR INTELLECTUAL PROPERTY,
PATENTS AND TRADEMARKS
(12)
ABSTRACT OF INVENTION
(21), (22) Application: 2005140505/09, 23.12.2005
(72) Inventor(s):
Andreev Dmitrij Vasil'evich (RU)
(24) Effective date for property rights: 23.12.2005
Mail address:
432027, g.Ul'janovsk, Severnyj Venets, 32,
GOU VPO "Ul'janovskij gosudarstvennyj
tekhnicheskij universitet", Prorektoru po
nauchnoj rabote
R U
2 3 0 0 1 3 6
C 1
C 1
(57) Abstract:
FIELD: computer science, possible use for
building automatic devices, functional units of
control systems.
SUBSTANCE: device contains n-1 constant
memorizing devices, n-1 registers, two adjustment
inputs, n groups of outputs, information inputs.
EFFECT: decreased hardware resource costs.
2 dwg, 1 tbl
Страница: 2
EN
2 3 0 0 1 3 6
(54) DEVICE FOR SORTING BINARY NUMBERS
R U
(73) Proprietor(s):
Gosudarstvennoe obrazovatel'noe uchrezhdenie
vysshego professional'nogo obrazovanija
"Ul'janovskij gosudarstvennyj tekhnicheskij
universitet" (RU)
(45) Date of publication: 27.05.2007 Bull. 15
RU 2 300 136 C1
5
10
15
20
25
30
35
Изобретение относитс к вычислительной технике и может быть использовано дл построени средств автоматики, функциональных узлов систем управлени и др.
Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами,
выполн ющие сортировку n (n?2) одноразр дных двоичных чисел (см., например, рис.2 в
статье Савченко Ю.Г., Хмелева А.В. О методах последовательной реализации
симметричных булевых функций // Автоматика и вычислительна техника. 1974. №3. С.2429.).
К причине, преп тствующей достижению указанного ниже технического результата при
использовании известных устройств сортировки двоичных чисел, относитс ограниченные
функциональные возможности, обусловленные тем, что не выполн етс сортировка 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-м выходом и входом
40
45
50
сброса, входом записи соответственно к 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 информационных входов предлагаемого устройства последовательно
Страница: 3
DE
RU 2 300 136 C1
5
подаютс соответственно первый и второй, ..., n-й наборы m произвольных двоичных
сигналов, задающие m-разр дные двоичные числа x1 и х2, ..., xn соответственно (фиг.2).
Обнуление выходных сигналов регистра 2i и загрузка в него данных происход т
соответственно по высокому уровню сигнала на входе сброса (сигнала y1) и по
положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2). В
чейка с адресом
содержит 2mустройстве 1i q- , в котором
разр дный двоичный код
10
. Тогда m-разр дные двоичные числа, задаваемые двоичными сигналами на первом, ..., m, будут определ тьс м и (m+1)-м, ..., (2m)-м выходах устройства 1i
соответственно рекуррентными выражени ми
15
где символами ? и ? обозначены операции max и min;
есть номер момента
времени tj (фиг.2); Vi0=0; W0j=хj. В представленной ниже таблице приведены значени выражений (1) при n=4.
20
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
W21=0
W22=0
V24=x1x2?x1x3?x1x4?
?x2x3?x2x4?x3x4
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
25
С учетом данных, приведенных в таблице, нетрудно вывести непосредственное
выражение, определ ющее m-разр дное двоичное число, задаваемое двоичными
группе m выходов предлагаемого устройства при j=n:
сигналами на g-й
30
где хs1?...?xsg ?{x1,...,xn};
35
есть количество неповтор ющихс фрагментов хs1...xsg, определ емое как число сочетаний из n по g. При g=n+1-r выражение
(2) совпадает с видом поисковой функции (функци (6.7) на стр. 117 в книге Левин В.И.
Бесконечнозначна логика в задачах кибернетики. М.: Радио и св зь, 1982 г.), котора реализует алгоритм выбора из множества {x1,...,xn} элемента х (r) заданного ранга r?{1,...,n}
Таким образом, предлагаемое устройство
будет воспроизводить операцию
40
45
50
сортировки m-разр дных двоичных чисел х1, ..., хn.
Вышеизложенные сведени позвол ют сделать вывод, что предлагаемое устройство
сортировки двоичных чисел выполн ет сортировку n (n?2) m-разр дных двоичных чисел,
задаваемых двоичными сигналами, и обладает меньшими по сравнению с прототипом
аппаратурными затратами, так как не содержит имеющиес в прототипе nm размыкающих и
nm замыкающих ключей.
Формула изобретени Устройство сортировки двоичных чисел, содержащее n-1 посто нных запоминающих
Страница: 4
CL
RU 2 300 136 C1
устройств и n-1 регистров, причем k-й
5
10
выход 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)-го
посто нных запоминающих устройств.
15
20
25
30
35
40
45
50
Страница: 5
RU 2 300 136 C1
Страница: 6
DR
Документ
Категория
Без категории
Просмотров
0
Размер файла
156 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа