close

Вход

Забыли?

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

?

Патент BY13665

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.10.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13665
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20090041
(22) 2009.01.14
(43) 2009.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 11027 C1, 2008.
BY 8619 C1, 2006.
BY 5179 C1, 2003.
SU 1725214 A1, 1992.
UA 60507 A, 2003.
BY 13665 C1 2010.10.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций четырех переменных, содержащее два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый из которых выполнен с порогом четыре, и элемент ИЛИ, выход которого соединен с выходом
устройства, а первый вход соединен с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ
с порогом четыре, первый вход которого соединен с первым настроечным входом устройства, отличающееся тем, что второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ также выполнен с
порогом четыре, выход которого соединен со вторым входом элемента ИЛИ, а i-й, где
i = 1,2,3,4, вход соединен с (i + 1)-м входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре и с i-м информационным входом устройства, второй настроечный вход
которого соединен с пятым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
четыре, шестой и седьмой входы которого соединены с третьим настроечным входом
устройства.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций четырех переменных.
Известно устройство для вычисления симметрических булевых функций четырех переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом четыре и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА [1]. Известное
BY 13665 C1 2010.10.30
устройство, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре.
Недостатком известного устройства являются большая конструктивная сложность (по
числу входов логических элементов) и большое число внешних выводов.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,
элемент ИЛИ, семь настроечных входов и выход [2]. Устройство-прототип, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемент ИЛИ, выход которого соединен с выходом устройства, а первый вход с выходом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Недостатком устройства является сложная настройка на вычисление (реализацию) полиномиальных симметрических булевых функций четырех переменных.
Изобретение направлено на решение технической задачи упрощения настройки
устройства на вычисление полиномиальных симметрических булевых функций четырех
переменных.
Устройство для вычисления полиномиальных симметрических булевых функций четырех переменных содержит два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый из которых
выполнен с порогом четыре, и элемент ИЛИ.
Выход элемента ИЛИ соединен с выходом устройства, а первый вход соединен с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, первый вход которого соединен с первым настроечным входом устройства.
В отличие от прототипа второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ также выполнен с
порогом четыре, выход которого соединен со вторым входом элемента ИЛИ, a i-й, где
i = 1,2,3,4, вход соединен с (i + 1)-м входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре и с i-м информационным входом устройства.
Второй настроечный вход устройства соединен с пятым входом второго элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, шестой и седьмой входы которого соединены
с третьим настроечным входом устройства.
Названный технический результат достигается путем введения в логическую схему
устройства четырех информационных и трех настроечных входов, а также изменением
порога второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и способа настройки устройства на вычисления полиномиальных симметрических булевых функций.
На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций четырех переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1 и 2, элемент ИЛИ 3,
четыре информационных входа 4, 5, 6 и 7, три настроечных входа 8, 9 и 10, один выход 11.
Устройство для вычисления полиномиальных симметрических булевых функций четырех переменных работает следующим образом. На информационные входы 4, 5, 6, 7 поступают (в произвольном порядке) значения переменных х1, х2, х3, х4, на настроечные
входы 8, 9, 10 - сигналы настройки u1, u2, u3, значения которых принадлежат множеству
{0,l}.
На выходе устройства 11 реализуется полиномиальная симметрическая булева функция F = F(xl,x2,x3,x4), определяемая вектором настройки U(F) = (u1,u2,u3).
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций четырех переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = F(xl,x2,...,xn) с рабочими числами а1,а2,...,аr (0≤r≤n) принимает значение 1 на тех и только тех наборах значений переменных X = {xl,x2,...,xn}, которые содержат ровно
2
BY 13665 C1 2010.10.30
аj(j = 1,2,...,r) единиц. Такая булева функция обозначается через F = Fna1 ,a 2 ,…,a r ( x 1 , x 2 ,…, x n ) .
Если r = 1, то симметрическая булева функция F = Fna ( x1 , x 2 ,…, x n ) называется фундаментальной (или элементарной).
Симметрическая булева функция n переменных F = Fna1 ,a 2 ,…,a r (X) называется полиномиальной, если ее полином Жегалкина содержит все элементарные конъюнкции, ранг которых равен k, где 1≤k≤n. Такая полиномиальная симметрическая булева функция n
переменных обозначается через F = E kn (X) . Очевидно, что полином Жегалкина функции
F = E kn (X) содержит C nk ("число сочетаний из n по k") элементарных конъюнкций ранга k,
где k = 1,2,…,n.
Устройство (фигура) синтезировано на основе применения следующих аналитических
представлений полиномиальных симметрических булевых функций четырех переменных
E k4 (X) = E k4 ( x1, x 2 , x 3 , x 4 ) :
E14 (X) = F41 (X) ∨ F43 (X) , E 24 (X) = F42 (X) ∨ F43 (X) ,
E 34 (X) = F43 (X ) и E 44 (X) = F44 (X) .
Посредством таблицы представлена настройка устройства на вычисление (реализацию) полиномиальных симметрических булевых функций четырех переменных.
Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций четырех переменных имеет вид
F(x1, x 2 , x 3 , x 4 , u1, u 2 , u 3 ) = F74 ( x1, x 2 , x 3 , x 4 , u1, u 2 , u 3 ) ∨ F54 ( x1, x 2 , x 3 , x 4 , u 3 ) .
Рассмотрим пример настройки. Допустим, что требуется вычислить на выходе устройства
полиномиальную
симметрическую
булеву
функцию
2
E 4 ( x1, x 2 , x 3 , x 4 ) = x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 .
Для этого, согласно таблице настроек (таблица), необходимо на настроечный вход 8
подать значение u1= 0, а на настроечные входы 9, 10 - значения u2 = u3 = 1. В таком случае
первообразная функция устройства принимает вид
F(x1 , x 2 , x 3 , x 4 , 0, 1, 1) = F74 ( x1 , x 2 , x 3 , x 4 ,0,1,1) ∨ F54 ( x1 , x 2 , x 3 , x 4 , 1) =
= F42 (x1 , x 2 , x 3 , x 4 ) ∨ F43 ( x1 , x 2 , x 3 , x 4 ) = E 24 ( x1 , x 2 , x 3 , x 4 ).
Устройство для вычисления полиномиальных симметрических булевых функций
Сигналы настройки
Выход
u1
u2
u3
F
8
9
10
11
1
1
1
E1
0
1
1
1
0
1
0
0
0
4
E 42
E 34
E 44
Достоинством устройства для вычисления полиномиальных симметрических булевых
функций четырех переменных является простая настройка на вычисление полиномиальных симметрических булевых функций четырех переменных. При этом сложность, быстродействие и число внешних выводов предлагаемого устройства и устройства-прототипа
совпадают.
3
BY 13665 C1 2010.10.30
Источники информации:
1. Патент РБ 10219, МПК G 06 F 7/00, 2008.
2. Патент РБ 11027, МПК G 06 F 7/00, 2008 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
85 Кб
Теги
by13665, патент
1/--страниц
Пожаловаться на содержимое документа