close

Вход

Забыли?

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

?

Патент BY11028

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2008.08.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20070114
(22) 2007.02.06
(43) 2007.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
BY 11028 C1 2008.08.30
BY (11) 11028
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) RU 2047894 C1, 1995.
BY 2793 C1, 1999.
BY 5838 C1, 2003.
BY 5179 C1, 2003.
(57)
Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, i-й, где i = 1, 2,…, 6, вход каждого элемента из которых соединен с i-м информационным входом устройства, первый настроечный вход которого
соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены со вторым настроечным входом устройства,
третий настроечный вход которого соединен с седьмым и восьмым входами элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, а четвертый настроечный вход устройства соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и
третий входы которого соединены с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять соответственно.
BY 11028 C1 2008.08.30
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций шести переменных.
Известно устройство для вычисления фундаментальных симметрических булевых
функций n переменных, содержащее при n = 6 мажоритарный элемент с порогом четыре,
мажоритарный элемент с порогом шесть, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА
и элемент И [1].
Недостатком устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислить полиномиальные симметрические булевы
функции шести переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций шести переменных, которое содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре,
семь элементов И, шесть информационных и семь настроечных входов и выход [2].
Недостатками устройства являются большая конструктивная сложность (по числу входов логических элементов) и большое число внешних выводов.
Изобретение направлено на решение технической задачи уменьшения конструктивной
сложности и уменьшения числа внешних выводов устройства для вычисления полиномиальных симметрических булевых функций шести переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства.
В отличие от прототипа устройство дополнительно содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, i-й (i = 1, 2,…, 6) вход каждого элемента из которых соединен с i-м информационным входом устройства.
Первый настроечный вход устройства соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены со вторым настроечным входом устройства.
Третий настроечный вход устройства соединен с седьмым и восьмым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Четвертый настроечный вход устройства соединен с седьмым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, выход которого соединен с первым входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и третий входы которого соединены с
выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять соответственно.
Названный технический результат достигается путем использования новых логических элементов (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть).
На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций шести переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, шесть информационных входов 5…10, четыре настроечных входа 11…14 и один выход 15.
Устройство для вычисления полиномиальных симметрических булевых функций шести переменных работает следующим образом. На информационные входы устройства 5,
6,…, 10 поступают (в произвольном порядке) значения переменных х1, х2,…, х6, а на настроечные входы 11, 12, 13 и 14 - сигналы настройки ul, u2, u3, u4, значения которых принадлежат множеству {0, 1}. На выходе устройства 15 реализуется полиномиальная симметрическая булева функция F = F(x1, х2,…, х6), определяемая вектором настройки U = (u1,
u2, u3, u4).
2
BY 11028 C1 2008.08.30
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций шести переменных.
Известно, что произвольная симметрическая булева функция n переменных F = F(xl,
x2,…, xn) с рабочими числами a1, a2,…, ar (0 ≤ r ≤ n) принимает значение 1 на тех и только
тех наборах значений переменных X = {x1, x2,…, xn}, которые содержат ровно aj (j = 1,
2,…, r) единиц. Такая булева функция обозначается через F = Fna 1 , a 2 ,..., a r ( x1 , x 2 ,..., x n ). Если r = 1, то симметрическая булева функция F = Fna ( x1 , x 2 ,..., x n ) называется фундаментальной (или элементарной).
Симметрическая булева функция п переменных F = Fna 1 , 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 6k (X) = E 6k ( x1 , x 2 ,..., x 6 ) :
E16 (X) = F61 (X) ∨ F63 (X) ∨ F65 (X), E 62 (X) = F62 (X) ∨ F63 (X) ∨ F66 (X),
E 36 (X) = F63 (X), E 64 (X) = F64 (X) ∨ F65 (X) ∨ F66 (X), E 56 (X) = F65 (X) и E 66 (X) = F66 (X).
В таблице представлена настройка устройства на вычисление (реализацию) полиномиальных симметрических булевых функций шести переменных.
Достоинствами устройства для вычисления полиномиальных симметрических булевых функций шести переменных являются 1) низкая конструктивная сложность (по числу
входов логических элементов), равная 27; 2) небольшое число внешних выводов, равное
11. Устройство-прототип имеет 14 внешних выводов, а его сложность равна 45.
Источники информации:
1. Патент РБ 2117, МПК G 06F 7/00, 1998.
2. Патент РФ 2047894, МПК G 06F 7/00, 1995 (прототип).
u1
11
u2
12
u3
13
u4
14
F
15
1
1
1
1
E16
0
1
1
0
E 62
1
0
0
1
E 36
0
0
0
0
E 64
1
0
1
1
E 56
1
0
1
0
E 66
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
3
Документ
Категория
Без категории
Просмотров
0
Размер файла
79 Кб
Теги
by11028, патент
1/--страниц
Пожаловаться на содержимое документа