|
|
больше ...
Термины запроса в документе
Реферат
[RU] 1. Логическое устройство для вычисления шефферовских симметрических булевых функций пяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и мажоритарный элемент с порогом пять, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, первый вход которого соединен со вторым настроечным входом устройства, третий настроечный вход которого соединен со вторым и третьим входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, (i+3)-й вход которого, где i = 1, 2, ..., 5, соединен с (i+3)-м настроечным входом устройства и с i-м входом мажоритарного элемента с порогом пять, шестой вход которого соединен с девятым настроечным входом устройства.
Полный текст патента
(57) Реферат / Формула:
1. Логическое устройство для вычисления шефферовских симметрических булевых функций пяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и мажоритарный элемент с порогом пять, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, первый вход которого соединен со вторым настроечным входом устройства, третий настроечный вход которого соединен со вторым и третьим входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, (i+3)-й вход которого, где i = 1, 2, ..., 5, соединен с (i+3)-м настроечным входом устройства и с i-м входом мажоритарного элемента с порогом пять, шестой вход которого соединен с девятым настроечным входом устройства.
Евразийское 026000 (13) B1
патентное
ведомство
(12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ЕВРАЗИЙСКОМУ ПАТЕНТУ
(45) Дата публикации и выдачи патента 2017.02.28
(21) Номер заявки 201401170
(22) Дата подачи заявки 2014.10.06
(51) Int. Cl. G06F 7/57 (2006.01) H03K19/20 (2006.01)
(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ШЕФФЕРОВСКИХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ
(43) 2016.06.30
(96) 2014/EA/0080 (BY) 2014.10.06
(71) (73) Заявитель и патентовладелец:
БЕЛОРУССКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (БГУ) (BY)
(72) Изобретатель:
Супрун Валерий Павлович, Коробко Филипп Сергеевич (BY)
(56) SU-A1-1730616 BY-C1-11275 RU-C2-2393527 US-A-4336468
(57) Предполагаемое изобретение относится к области вычислительной техники и микроэлектроники
и предназначено для вычисления шефферовских симметрических булевых функций пяти I переменных. Устройство для вычисления шефферовских симметрических булевых функций | пяти переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, мажоритарный элемент с порогом пять, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять настроечных входов и один выход. Сложность устройства по числу входов логических элементов равна 17, а его быстродействие, определяемое глубиной схемы, составляет 2т, где т - задержка на один логический элемент. Устройство имеет 10 внешних выводов (девять входов и выход). Устройство для вычисления шефферовских симметрических булевых функций пяти переменных работает следующим образом. На настроечные входы устройства поступают переменные ub ife, U9,
значения которых принадлежат множеству {Q> bx],x\,x2,x2,x3,x3,x4,x4,xs,xs\. jja выходе устройства вычисляется (реализуется) шефферовская симметрическая булева функция F = F(xbx2,x3,x4,x5), определяемая вектором настройки u(F)=(u1, u2, u9).
Предполагаемое изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления шефферовских симметрических булевых функций пяти переменных.
Известно устройство для вычисления полиномиальных симметрических булевых функций пяти переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четыре информационных и шесть настроечных входов, выход [1]. Конструктивная сложность устройства (по числу входов логических элементов) равна 17.
Известное устройство, как и предполагаемое изобретение, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, ^+1)-й настроечный вход которого, где i = 1, 2, соединен с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а четвертый настроечный вход - с третьим и четвертым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Недостатком известного устройства являются низкие функциональные возможности, поскольку устройство не позволяет вычислять шефферовские симметрические булевы функции пяти переменных.
Наиболее близким по функциональным возможностям и конструкции техническим решением к заявляемому устройству является устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент РАВНОЗНАЧНОСТЬ, мажоритарный элемент с порогом четыре, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход [2]. Конструктивная сложность устройства, принятого за прототип, равна 19.
Устройство - прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства.
Недостатком устройства - прототипа является высокая конструктивная сложность при вычислении (реализации) шефферовских симметрических булевых функций пяти переменных.
Изобретение направлено на решение следующих технических задач: 1) понижения конструктивной сложности (по числу входов логических элементов); 2) уменьшение числа внешних выводов устройства, предназначенного для вычисления шефферовских симметрических булевых функций пяти переменных.
Устройство для вычисления шефферовских симметрических булевых функций пяти переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства.
В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и мажоритарный элемент с порогом пять, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, первый вход которого соединен со вторым настроечным входом устройства.
Третий настроечный вход устройства соединен со вторым и третьим входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, (i + 3)-й вход которого, где i = 1, 2, 5, соединен с (i + 3)-м настроечным входом устройства и с i-м входом мажоритарного элемента с порогом пять, шестой вход которого соединен с девятым настроечным входом устройства.
Названный технический результат достигается посредством удаления из схемы устройства - прототипа элемента РАВНОЗНАЧНОСТЬ, введения в схему логического элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и изменения порога мажоритарного элемента, а также путем последующего изменения соединений между элементами логической схемы.
На фиг. 1 представлена логическая схема устройства для вычисления шефферовских симметрических булевых функций пяти переменных.
Устройство для вычисления шефферовских симметрических булевых функций пяти переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, мажоритарный элемент с порогом пять 2, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 3, девять настроечных входов 4, 5, 12 и выход 13.
Устройство для вычисления шефферовских симметрических булевых функций пяти переменных работает следующим образом.
На настроечные входы 4, 5, 12 поступают сигналы ub и2, и9, значения которых принадлежат
множеству {(r)> 1'х\> хЬх2> х2> хз> хЗ> Х4> Х4*х5> х5\. На выходе 13 вычисляется шефферовская симметрическая булева функция F = F(x1, x2, х5), определяемая вектором настройки u(F)=(u1, u2, u9).
Поясним принцип построения и работы устройства для вычисления шефферовских симметрических булевых функций пяти переменных.
Произвольная булева функция n переменных F = F(x1, x2, xn) называется симметрической, если она не меняет своего значения после перестановки любой пары переменных xi и xj, где i Фj и i, j = 1, 2, n.
Симметрическая булева функция F характеризуется множеством рабочих чисел A(F)={a1, a2, ar},
где 0 Симметрическая булева функция F = F(xx, x2, xn) взаимно однозначно представляется (n+1)-разрядным двоичным вектором (локальным кодом) n(F) = (п0, п1, nn), где ni=1 тогда и только тогда, когда i - рабочее число функции F, т.е. ie A(F).
Симметрическая булева функция n переменных F называется шефферовской (или функцией шефферов-ского типа), если она не содержится ни в одном из пяти замкнутых классов Т0, Ть TL, Ts, Тм, т.е.
FtT0vTiVTLvTsuTu,
где T0 - класс булевых функций, сохраняющих константу 0, T1 - класс булевых функций, сохраняющих константу 1, TL - класс линейных булевых функций, TS - класс самодвойственных булевых функций и TM - класс монотонных булевых функций (Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1986).
Число шефферовских симметрических булевых функций п переменных вычисляется по формуле
, если п - нечетное,
2" 1 - в противном случае.
Отсюда следует, что NS(5) = 12, т.е. существует двенадцать шефферовских симметрических булевых функций пяти переменных Fb F2,F12. Функции Fb F2,Fn имеют следующие локальные коды:
x{Fx) = (100000), я{Р2)={\00010), ^(F3)=(100100), я(^4) = (101000), 7r(F5)=(l01100), л-(^) = (ЮШ0), я-(^7) = (П0000), x{F &)= (110010), л-(^9)=(110110),
л-(^10)=(Ш010), ;r(Fn)=(llll0O) и n{Fn)= (111110).
Первообразная функция устройства (фиг. 1) для вычисления шефферовских симметрических булевых функций пяти переменных имеет вид
Настройка устройства на вычисление (реализацию) булевых функций F1, F2, F12 осуществляется посредством таблицы (фиг. 2).
Рассмотрим пример настройки. Допустим, что на выходе 13 устройства требуется вычислить шеф-
феровскую симметрическую булеву функцию
F12(x) = xlvx2vx3vx4vx5, где X = {хих2,... ,х5].
В таком случае согласно таблице настроек (фиг. 2) необходимо положить u1 = 1, u2 = 0, u3 = 0, u4 = хь u5 = x2, ив = x3, u7 = X4, u8 = x5, u9 = 1, и тогда первообразная функция устройства принимает вид
F(l, 0, 0, xlt Х2, Х3, X4, X5, l) = l(c).Fg4( 0,0,0, ЛС|, х2, х3, х4, х5)ф
Ф F^ * ( Х\, Х2, Х3, х4, х$, l)= 1 Ф F$ (xj, х2 , х^, х4, Xj )ф F^ ' (-^1, х2 , Х^, х4, х^ ) - = 1 Ф/*55(Х|, Х2, Х3, Х4, Х5) = F$ ' ' (х(, Х2> Х3, Х4, х5) =
= х, v х2 v х3 v х4 v х5 = Fn (х).
Основными достоинствами заявляемого устройства являются: 1) низкая конструктивная сложность, равная 17 (сложность прототипа равна 19); 2) небольшое число внешних выводов, которое равно 10 (девять настроечных входов и выход). Устройство - прототип имеет 13 внешних выводов (двенадцать настроечных входов и выход).
Кроме того, оба устройства имеют одинаковое быстродействие, определяемое глубиной соответствующих логических схем.
Источники информации, принятые во внимание при экспертизе.
1. Заявка на патент РБ № а20130208 от 18.02.2013, БИ № 3 (92), 2013, с. 35.
2. Заявка на патент РБ № а20130130 от 01.02.2013, БИ № 3 (92), 2013, с. 34 (прототип).
ФОРМУЛА ИЗОБРЕТЕНИЯ
Логическое устройство для вычисления шефферовских симметрических булевых функций пяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и мажоритарный элемент с порогом пять, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, первый вход которо
го соединен со вторым настроечным входом устройства, третий настроечный вход которого соединен со вторым и третьим входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, ^+3)-й вход которого, где i = 1, 2, 5, соединен с ^+3)-м настроечным входом устройства и с i-м входом мажоритарного элемента с порогом пять, шестой вход которого соединен с девятым настроечным входом устройства.
Евразийская патентная организация, ЕАПВ Россия, 109012, Москва, Малый Черкасский пер., 2
026000
- 1 -
(19)
026000
- 1 -
(19)
026000
- 1 -
(19)
026000
- 1 -
(19)
026000
- 4 -
(19)
|
