|
|
(21), (22) Заявка: 2004118087/09, 15.06.2004
(24) Дата начала отсчета срока действия патента:
15.06.2004
(45) Опубликовано: 20.11.2005
(56) Список документов, цитированных в отчете о
поиске:
САВЧЕНКО Ю.Г., ХМЕЛЕВА А.В. О методах последовательной реализации симметричных булевых функций, в: “Автоматика и вычислительная техника”, 1974, №3, стр.24-29. RU 2050583 C1, 20.12.1995. RU 2095850 C1, 10.11.1997. SU 1783511 A1, 23.12.1992. SU 1647562 A1, 07.05.1991. US 3740538 А, 19.06.1973.
Адрес для переписки:
432027, г.Ульяновск, ул. Северный Венец, 32, ГОУ ВПО “Ульяновский государственный технический университет”, Проректору по научной работе
|
(72) Автор(ы):
Андреев Д.В. (RU)
(73) Патентообладатель(и):
Государственное образовательное учреждение высшего профессионального образования “Ульяновский государственный технический университет” (RU)
|
(54) УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ
(57) Реферат:
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления. Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения сортировки n (n 2) m-разрядных двоичных чисел, задаваемых двоичными сигналами. Устройство содержит (n-1) логических модулей, каждый из которых содержит регистр, замыкающие и размыкающие ключи, постоянное запоминающее устройство. 2 ил. 
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сортировки двоичных чисел, относится ограниченные функциональные возможности, обусловленные тем, что не выполняется сортировка n(n2) m-разрядных двоичных чисел, задаваемых двоичными сигналами.
2) одноразрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится ограниченные функциональные возможности, обусловленные тем, что не выполняется сортировка n(n2) m-разрядных двоичных чисел, задаваемых двоичными сигналами.
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения сортировки n(n2) поразрядных двоичных чисел, задаваемых двоичными сигналами.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем логический модуль, который содержит регистр, особенность заключается в том, что в него введены аналогичные упомянутому n-2 логических модуля и в каждый логический модуль,. кроме первого, дополнительно введены m замыкающих, m размыкающих ключей и постоянное запоминающее устройство, а в первый логический модуль дополнительно введены 2m замыкающих, 2m размыкающих ключей и постоянное запоминающее устройство, причем в i-ом  логическом модуле первый управляющий и k-ый  входы образованы соответственно входом управления всех имеющихся в нем ключей и входом k-го замыкающего ключа, выход которого соединен с выходом k-го размыкающего ключа и k-ый адресным входом постоянного запоминающего устройства, подсоединенного k-ый выходом к k-му входу регистра, k-ый выход и вход записи которого соединены соответственно с входом k-го размыкающего ключа и вторым управляющим входом i-го логического модуля, подсоединенного k-ый выходом к (m+k)-му выходу постоянного запоминающего устройства, в первом логическом модуле (m+k)-ый вход образован входом (m+k)-го замыкающего ключа, выход которого соединен с (m+k)-ым адресным входом постоянного запоминающего устройства и выходом (m+k)-го размыкающего ключа, подсоединенного входом к шине нулевого потенциала, а в каждом логическом модуле, кроме первого, (m+k)-ый вход образован (m+k)-ым адресным входом постоянного запоминающего устройства, k-ый выход каждого предыдущего логического модуля подключен к (m+k)-му входу последующего логического модуля, а k-ый выход (n-1)-го логического модуля является k-ым выходом устройства сортировки двоичных чисел, первый и второй настроечные входы которого образованы соответственно объединенными первыми и объединенными вторыми управляющими входами всех логических модулей.
На фиг.1 и фиг.2 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы сигналов настройки.
Устройство сортировки двоичных чисел содержит логические модули 11,…, 1n-1. Каждый логический модуль содержит размыкающие и замыкающие ключи 21,…, 2m и 31,…, 3m (модуль 11 дополнительно содержит размыкающие и замыкающие ключи 2m+1,…, 2m+m+ и 3m+1,…, 3m+m), постоянное запоминающее устройство 4, регистр 5, причем в модуле 1i первый управляющий и k-ый  входы образованы соответственно входом управления всех имеющихся в нем ключей и входом ключа 3k выход которого соединен с выходом ключа 2k и k-ым адресным входом устройства 4, подсоединенного k-ым выходом к k-му входу регистра 5, k-ый выход и вход записи которого соединены соответственно с входом ключа 2k и вторым управляющим входом модуля 1i подсоединенного k-ым выходом к (m+k)-му выходу устройства 4, в модуле 11(m+k)-ый вход образован входом ключа 3m+k, выход которого соединен с (m+k)-ым адресным входом устройства 4 и выходом ключа 2m+k подсоединенного входом к шине нулевого потенциала, а в каждом логическом модуле, кроме первого, {m+k)-ый вход образован (m+k)-ым адресным входом устройства 4, k-ый выход каждого предыдущего модуля подключен к (m+k)-му входу последующего модуля, а k-ый выход модуля 1i является k-ым выходом устройства сортировки двоичных чисел, первый и второй настроечные входы которого образованы соответственно объединенными первыми и объединенными вторыми управляющими входами всех логических модулей.
Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно сигналы у1, у2  {0,1} (фиг.2). На первый,…, k-ый входы модуля 1i, и (m+1)-ый,…, (m+m)-ый входы модуля 11 подаются произвольные двоичные сигналы, задающие m-разрядные двоичные числа xi и хn соответственно. Длительность  t** высокого уровня сигнала у1 и период Т сигнала у2 должны удовлетворять условиям t**>t* и Т>t, где t*=(n-i) 1, t=(n-i)1+2, a 1 и 2 есть длительности задержек, вносимых соответственно устройством 4 и регистром 5. При у1=1(у1=0) ключи 31,…, 3m+m замкнуты (разомкнуты), ключи 21,…, 2m+m разомкнуты (замкнуты). Загрузка данных в регистр 5 происходит по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала у2). В устройстве 4 q-ая  ячейка с адресом а*m-1…а*0аm-1…а0 содержит 2m-разрядный двоичный код d* m-1…d* 0dm-1…d0, в котором d*m-1…d*0=max(а*m-1…а*0,аm-1…а0). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом,…, m-ом и (m+1)-ом,…, (m+m)-ом выходах устройства 4 в модуле 1i , будут определяться соответственно рекуррентными выражениями
и
где символами  и · обозначены операции max и min;  есть номер момента времени tj (фиг.2); Vi0=xi; W01=xn; W02=…=W0n=0. Поскольку согласно (1.1) имеем
Vi(j-1)=Vi(j-2)W(i-1)(j-1)=Vi(j-4)Wi(j-1)(j-3)W(i-1)(j-2)W(i-1)(j-1)=
=Vi0W(i-1)1…W(i-1)(j-1)=xiW(j-1)1…W(i-1)(j-1),
то с учетом (1.2) получим
В представленной ниже таблице приведены значения выражения (2) при n=4.
| W11=x1x4 |
W21=x1x2x4 |
W31=x1x2x3x4 |
| W12=x1x4 |
W22=x1x2x1x4x2x4 |
W32=x1x2x1x3x1x4x2x3x3x4 |
| W13=0 |
W23=x1x2x4 |
W33=x1x2x3x1x2x4x1x3x4x2x3x4 |
| W14=0 |
W24=0 |
W34=x1x2x3x4 |
С учетом данных, приведенных в таблице, нетрудно вывести непосредственное выражение для W(n-i)j
где xS1  … хsj (х1,…, хn);  есть количество неповторяющихся фрагментов хs1…xsj, определяемое как число сочетаний из n по j. При j=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр. 117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x1,…, xn} элемента х(r) заданного ранга  . Таким образом, при  предлагаемое устройство будет воспроизводить операцию
сортировки m-разрядных двоичных чисел х1,…, хn,.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел, задаваемых двоичными сигналами, обладает более широкими по сравнению с прототипом функциональными возможностями, так как выполняет сортировку n(n2) отразрядных двоичных чисел.
Формула изобретения
Устройство сортировки двоичных чисел, содержащее логический модуль, который содержит регистр, отличающееся тем, что в него введены аналогичные упомянутому n-2 логических модуля и в каждый логический модуль, кроме первого, дополнительно введены m замыкающих, m размыкающих ключей и постоянное запоминающее устройство, а в первый логический модуль дополнительно введены 2m замыкающих, 2m размыкающих ключей и постоянное запоминающее устройство, причем в i-м  логическом модуле первый управляющий и k-й  входы образованы соответственно входом управления всех имеющихся в нем ключей и входом k-го замыкающего ключа, выход которого соединен с выходом k-го размыкающего ключа и k-м адресным входом постоянного запоминающего устройства, подсоединенного k-м выходом к k-му входу регистра, k-й выход и вход записи которого соединены соответственно с входом k-го размыкающего ключа и вторым управляющим входом i-го логического модуля, подсоединенного k-м выходом к (m+k)-мy выходу постоянного запоминающего устройства, в первом логическом модуле (m+k)-й вход образован входом (m+k)-го замыкающего ключа, выход которого соединен с (m+k)-м адресным входом постоянного запоминающего устройства и выходом (m+k)-го размыкающего ключа, подсоединенного входом к шине нулевого потенциала, а в каждом логическом модуле, кроме первого, (m+k)-й вход образован (m+k)-м адресным входом постоянного запоминающего устройства, k-й выход каждого предыдущего логического модуля подключен к (m+k)-му входу последующего логического модуля, а k-й выход (n-1)-го логического модуля является k-м выходом устройства сортировки двоичных чисел, первый и второй настроечные входы которого образованы соответственно объединенными первыми и объединенными вторыми управляющими входами всех логических модулей.
РИСУНКИ
MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 16.06.2006
Извещение опубликовано: 20.11.2007 БИ: 32/2007
|
|
