УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ Российский патент 2005 года по МПК G06F7/06 

Описание патента на изобретение RU2264645C1

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

Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку восьми одноразрядных двоичных чисел (см., например, рис.8.12 на стр.479 в книге Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь, 1990; рис.1 и рис.2 в статье Музыченко О.Н. Однородные и регулярные структуры для реализации симметричных функций алгебры логики // Автоматика и телемеханика. 1998. №4. С.152-165).

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем логический модуль, который содержит регистр, особенность заключается в том, что в него введены аналогичные упомянутому 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)τ12, 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...а*0m-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=x1∨x4W21=x1∨x2∨x4W31=x1∨x2∨x3∨x4W12=x1x4W22=x1x2∨x1x4∨x2x4W32=x1x2∨x1x3∨x1x4∨x2x3∨x3x4W13=0W23=x1x2x4W33=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4W14=0W24=0W34=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(n≥2) отразрядных двоичных чисел.

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

название год авторы номер документа
УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ 2007
  • Андреев Дмитрий Васильевич
RU2383052C2
УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ 2005
  • Андреев Дмитрий Васильевич
RU2300136C1
УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ 2007
  • Андреев Дмитрий Васильевич
  • Коннов Сергей Юрьевич
RU2346321C1
УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ 2011
  • Андреев Дмитрий Васильевич
  • Гринберг Исаак Павлович
RU2445678C1
ЛОГИЧЕСКИЙ ПРОЦЕССОР 2004
  • Андреев Д.В.
RU2260205C1
ЛОГИЧЕСКИЙ ВЫЧИСЛИТЕЛЬ 2007
  • Андреев Дмитрий Васильевич
RU2353967C1
УСТРОЙСТВО ФОРМИРОВАНИЯ ГРУППОВОГО СИГНАЛА 1998
  • Белый В.В.
  • Берест П.А.
  • Игнатов В.В.
  • Нестеренко А.Г.
  • Рашич В.О.
  • Скоропад А.В.
RU2144266C1
ЛОГИЧЕСКИЙ ВЫЧИСЛИТЕЛЬ 2007
  • Андреев Дмитрий Васильевич
RU2336555C1
Устройство для сортировки чисел 1981
  • Барашев Карп Сергеевич
  • Архипов Александр Васильевич
  • Мусорин Игорь Викторович
  • Сычев Владимир Яковлевич
SU960800A1
ЛОГИЧЕСКИЙ ВЫЧИСЛИТЕЛЬ 2004
  • Андреев Д.В.
RU2260837C1

Иллюстрации к изобретению RU 2 264 645 C1

Реферат патента 2005 года УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ

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

Формула изобретения RU 2 264 645 C1

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

Документы, цитированные в отчете о поиске Патент 2005 года RU2264645C1

САВЧЕНКО Ю.Г., ХМЕЛЕВА А.В
О методах последовательной реализации симметричных булевых функций, в: "Автоматика и вычислительная техника", 1974, №3, стр.24-29
УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ 1992
  • Хуторцев Валерий Владимирович
  • Строцев Андрей Анатольевич
RU2050583C1
ВЫЧИСЛИТЕЛЬ РАНГОВ 1994
  • Козлов А.И.
  • Черепов Е.И.
  • Эпов А.Е.
RU2095850C1
Устройство для сортировки двоичных чисел 1990
  • Кишенский Сергей Жанович
  • Вдовиченко Николай Степанович
  • Надобных Евгений Николаевич
  • Христенко Ольга Юрьевна
SU1783511A1
Устройство для сортировки двоичных чисел 1989
  • Решетняк Виктор Николаевич
  • Карелин Владимир Петрович
  • Гузик Вячеслав Филиппович
SU1647562A1
US 3740538 А, 19.06.1973.

RU 2 264 645 C1

Авторы

Андреев Д.В.

Даты

2005-11-20Публикация

2004-06-15Подача