close

Вход

Забыли?

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

?

Патент BY11785

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 11785
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20071232
(22) 2007.10.09
(43) 2008.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY а 20070114, 2007.
BY а 20061289, 2007.
BY 9051 C1, 2007.
BY 2793 C1, 1999.
BY 11785 C1 2009.04.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, i-й, где i = 1,
2,…, 8, вход которого соединен с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
четыре, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с i-м информационным входом устройства, входы, с первого по четвертый, элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены
соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
Фиг. 1
BY 11785 C1 2009.04.30
шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, причем первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым
настроечным входом устройства, третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с
девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, десятый вход которого соединен с шестым настроечным входом устройства, седьмой настроечный вход которого соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных.
Известно устройство для вычисления полиномиальных симметрических булевых
функций восьми переменных, содержащее четыре полусумматора, двадцать четыре элемента И, пятнадцать элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь входов и восемь
выходов [1].
Недостатками известного устройства являются высокая конструктивная сложность (по
числу входов логических элементов) и низкое быстродействие, определяемое глубиной
схемы.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, шесть информационных входов, четыре настроечных входа и один выход [2].
Недостатком устройства является невозможность вычисления полиномиальных симметрических булевых функций восьми переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления полиномиальных симметрических булевых функций
восьми переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть.
В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, i-й, где i = 1, 2, …, 8, вход которого соединен с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом пять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с i-м информационным входом устройства.
Входы, с первого по четвертый, элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены
со вторым настроечным входом устройства.
2
BY 11785 C1 2009.04.30
Третий настроечный вход которого соединен с двенадцатым и тринадцатым входами
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, десятый вход которого соединен с шестым настроечным входом устройства, седьмой настроечный вход которого соединен с девятым входом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Основной технический результат изобретения заключается в расширении функциональных возможностей устройства для вычисления полиномиальных симметрических булевых функций шести переменных за счет реализации (вычисления) полиномиальных
симметрических булевых функций восьми переменных. Названный эффект достигается
путем введения в логическую схему устройства-прототипа нового логического элемента
(элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь).
На чертеже (фигура) 1 представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5,
восемь информационных входов 6…13, семь настроечных входов 14…20 и выход 21.
Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На информационные входы устройства
6... 13 поступают (в произвольном порядке) значения переменных x1, x2, …, x8; на настроечные входы 14...20 - сигналы настройки u1, u2, …, u7 соответственно; на выходе 21 реализуется (вычисляется) полиномиальная симметрическая булева функция восьми переменных E 8k = E 8k (x 1 , x 2 , K , x 8 ) , определяемая вектором настройки U = (u1, u2, …, u7), где
k = 1, 2, …, 8.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций восьми переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = F(x1, x2, …, xn) с рабочими числами a1, a2, …, ar (0 ≤ r ≤ n) принимает значение 1 на тех
и только тех наборах значений переменных X = {x1, x2, …, xn}, которые содержат ровно aj
(j = 1, 2, …, r) единиц. Такая булева функция обозначается через F = Fna1,a 2 ,K,a r (x1 , x 2 , …, x n ) .
Если r = 1, то симметрическая булева функция F = Fna (x1 , x 2 , …, x n ) называется фундаментальной (или элементарной).
Симметрическая булева функция n переменных F = Fna1 ,a 2 ,K,a r (X) называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг
которых равен k, где 1 ≤ k ≤ n. Полиномиальная симметрическая булева функция n переменных обозначается через F = E kn (X) . Очевидно, что полином Жегалкина функции
F = E kn (X) содержит C kn ("число сочетаний из n по k") элементарных конъюнкций ранга
k, где k = 1, 2, …, n.
Предлагаемое устройство (фигура) 1 синтезировано на основе применения следующих
аналитических представлений полиномиальных симметрических булевых функций восьми переменных E 8k ( X ) = E 8k ( x 1 , x 2 ,K, x 8 ) :
3
BY 11785 C1 2009.04.30
E18 (X ) = F81 (X ) ∨ F83 (X ) ∨ F85 (X ) ∨ F87 (X ),
E 82 (X ) = F82 (X ) ∨ F83 (X ) ∨ F86 (X ) ∨ F87 (X ),
E 83 (X ) = F83 (X ) ∨ F87 (X ),
E 84 (X ) = F84 (X ) ∨ F85 (X ) ∨ F86 (X ) ∨ F87 (X ),
E 85 (X ) = F85 (X ) ∨ F87 (X ), E 86 (X ) = F86 (X ) ∨ F87 (X ),
E 87 (X ) = F87 (X ), E 88 (X ) = F88 (X ).
В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций восьми переменных.
Первообразная устройства для вычисления полиномиальных симметрических булевых
функций E 8k ( X ) = E 8k ( x 1 , x 2 ,K, x 8 ) имеет вид
F ( x 1 , x 2 , K , x 8 , u 1 , u 2 , K , u 7 ) = F134 ( x 1 , x 2 , K , x 8 , u 1 , u 2 , u 2 , u 3 , u 3 ) ⊕
⊕ F105 ( x 1 , x 2 , K , x 8 , u 4 , u 4 ) ⊕ F106 ( x 1 , x 2 , K , x 8 , u 5 , u 6 ) ⊕ F98 ( x 1 , x 2 , K , x 8 , u 7 ) ,
где
1, если x 1 + x 2 + K + x 8 + u 1 + 2 u 2 + 2 u 3 = 4 ;
F134 ( x 1 , x 2 , K, x 8 , u 1 , u 2 , u 2 , u 3 , u 3 ) = 
 0 − в противном случае ,
1, если x 1 + x 2 + K + x 8 + 2 u 4 = 5 ;
F105 ( x 1 , x 2 , K , x 8 , u 4 , u 4 ) = 
 0 − в противном случае ,
1, если x 1 + x 2 + K + x 8 + u 5 + u 6 = 6 ;
F106 ( x 1 , x 2 , K , x 8 , u 5 , u 6 ) = 
 0 − в противном случае ,
1, если x 1 + x 2 + K + x 8 + u 7 = 8 ;
F98 ( x 1 , x 2 , K, x 8 , u 7 ) = 
 0 − в противном случае.
Пример
Допустим, на выходе устройства требуется реализовать полиномиальную симметрическую булеву функцию
E 82 (x 1 , x 2 , K , x 8 ) = x 1x 2 ⊕ x 1x 3 ⊕ x 1x 4 ⊕ x 1x 5 ⊕ x 1 x 6 ⊕ x 1x 7 ⊕ x 1x 8 ⊕
⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 2 x 5 ⊕ x 2 x 6 ⊕ x 2 x 7 ⊕ x 2 x8 ⊕ x 3x 4 ⊕ x 3x 5 ⊕ x 3x 6 ⊕
⊕ x 3x 7 ⊕ x 3x8 ⊕ x 4 x 5 ⊕ x 4 x 6 ⊕ x 4 x 7 ⊕ x 4 x8 ⊕ x 5 x 6 ⊕ x 5x 7 ⊕ x 5x8 ⊕
⊕ x6x7 ⊕ x6x8 ⊕ x7x8.
Для этого, согласно таблице настроек (таблица), необходимо
u1 = u3 = u5 = u6 = 0 и u2 = u4 = u7 = 1.
В таком случае первообразная устройства принимает следующий вид:
положить
4
(x1 , x 2 ,K, x 8 ,0,1,1,0,0 ) ⊕
F(x 1 , x 2 ,K , x 8 ,0,1,0,1,0,0,1) = F13
5
(x1 , x 2 ,K, x 8 ,1,1) ⊕ F106 (x1 , x 2 , K, x 8 ,0,0 ) ⊕ F98 (x1 , x 2 ,K, x 8 ,1) =
⊕ F10
= F82 (x 1 , x 2 ,K , x 8 ) ⊕ F83 (x 1 , x 2 ,K , x 8 ) ⊕ F86 (x 1 , x 2 ,K , x 8 ) ⊕ F87 (x 1 , x 2 ,K , x 8 ) =
= F82 (x 1 , x 2 ,K , x 8 ) ∨ F83 (x 1 , x 2 ,K , x 8 ) ∨ F86 (x 1 , x 2 ,K, x 8 ) ∨ F87 (x 1 , x 2 , K, x 8 ) =
= E 82 (x 1 , x 2 ,K , x 8 ).
Дополнительным достоинством устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является небольшая конструктивная
4
BY 11785 C1 2009.04.30
сложность, которая (по числу входов логических элементов) равна 46. Также отметим высокое быстродействие устройства, которое равно 2τ, где τ - усредненная задержка на один
логический элемент.
Источники информации:
1. Патент РБ 9147, МПК G 06F 7/00, 2007.
2. Патент РБ 11028, МПК G 06F 7/00, 2008 (прототип).
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
2
Размер файла
100 Кб
Теги
патент, by11785
1/--страниц
Пожаловаться на содержимое документа