close

Вход

Забыли?

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

?

Патент BY13992

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2011.02.28
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20090335
(22) 2009.03.10
(43) 2009.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Супрун Валерий Павлович;
Городецкий Данила Андреевич
(BY)
BY 13992 C1 2011.02.28
BY (11) 13992
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 3031 C1, 1999.
BY 3300 C1, 2000.
BY 5171 C1, 2003.
BY 8973 C1, 2007.
SU 1684792 A1, 1991.
(57)
Устройство для вычисления бисимметрических булевых функций четырех переменных, содержащее пять элементов И, полусумматор и первый элемент СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход соединен
с первым настроечным входом устройства, второй настроечный вход которого соединен с
первым входом первого элемента И, выход которого соединен со вторым входом первого
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом
второго элемента И, первый вход которого соединен с выходом суммы полусумматора,
первый и второй входы которого соединены с первым и вторым информационными входами устройства, а выход переноса соединен с первым входом третьего элемента И, выход
которого соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, первые входы четвертого и пятого элементов И соединены соответственно с третьим и четвертым настроечными входами устройства, отличающееся тем, что дополнительно содержит второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход
второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым входом второго
элемента И, а первый вход соединен с пятым настроечным входом устройства, шестой
настроечный вход которого соединен со вторым входом первого элемента И, а седьмой
настроечный вход устройства соединен со вторым входом четвертого элемента И, выход
BY 13992 C1 2011.02.28
которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
восьмой настроечный вход устройства соединен со вторым входом пятого элемента И,
выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с девятым настроечным входом устройства, а
выход - со вторым входом третьего элемента И.
Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций четырех переменных.
Известно устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять входов и
один выход [1]. Известное устройство, как и предлагаемое, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислить (реализовать) бисимметрические булевы
функции четырех переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является многофункциональный логический модуль, который содержит два полусумматора, восемь элементов И, элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, четыре информационных и девять настроечных входов, один выход [2].
Многофункциональный логический модуль предназначен для вычисления бисимметрических булевых функций четырех переменных. Конструктивная сложность модуля (по
числу входов логических элементов) равна 37, а быстродействие составляет 3τ, где τ задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит пять элементов И, полусумматор и элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, выход которого соединен с выходом устройства.
Недостатками устройства-прототипа являются: а) высокая конструктивная сложность;
б) большое число внешних выводов.
Изобретение направлено на решение следующих технических задач: снижение конструктивной сложности и уменьшение числа внешних выводов устройства для вычисления бисимметрических булевых функций четырех переменных.
Устройство для вычисления бисимметрических булевых функций четырех переменных содержит пять элементов И, полусумматор и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход соединен с
первым настроечным входом устройства.
Второй настроечный вход устройства соединен с первым входом первого элемента И,
выход которого соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И.
Первый вход второго элемента И соединен с выходом суммы полусумматора, первый
и второй входы которого соединены с первым и вторым информационными входами
устройства, а выход переноса соединен с первым входом третьего элемента И.
Выход третьего элемента И соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первые входы четвертого и пятого элементов И соединены соответственно с третьим и четвертым настроечными входами устройства.
В отличие от прототипа устройство дополнительно содержит второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым входом второго элемента И, а первый вход соединен с
пятым настроечным входом устройства, шестой настроечный вход которого соединен со
вторым входом первого элемента И.
2
BY 13992 C1 2011.02.28
Седьмой настроечный вход устройства соединен со вторым входом четвертого элемента И, выход которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА.
Восьмой настроечный вход устройства соединен со вторым входом пятого элемента
И, выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с девятым настроечным входом устройства,
а выход - со вторым входом третьего элемента И.
Названный технический результат достигается с помощью 1) введения в логическую
схему устройства дополнительно двух элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА; 2)
удаления из схемы одного полусумматора и трех элементов И; 3) изменения соединений
логических элементов в схеме.
На чертеже (фигура) представлена логическая схема устройства для вычисления бисимметрических булевых функций четырех переменных.
Устройство для вычисления бисимметрических булевых функций четырех переменных содержит пять элементов И 1…5, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6, 7
и 8, полусумматор 9, два информационных входа 10 и 11, девять настроечных входов
12…20 и выход 21.
Устройство для вычисления бисимметрических булевых функций четырех переменных работает следующим образом.
На информационные входы устройства 10 и 11 поступают (в произвольном порядке)
значения переменных x1 и x2, на настроечные входы 12…20 - сигналы настройки u0, u1, …,
u8, значения которых принадлежат множеству 0, 1, x 3 , x 3 , x 4 , x 4 . На выходе устройства 21
вычисляется (реализуется) бисимметрическая булева функция F = F(X1, X2), где X1 = {x1,
x2} и X2 = {x3, x4}, определяемая вектором настройки u(F) = (u0, u1, …, u8).
Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций четырех переменных.
Произвольная симметрическая булева функция n переменных F = F(x1, x2, …, хn) характеризуется множеством рабочих чисел A(F) = {a1, a2, …, ar}. Функция F принимает
единичные значения на тех и только тех наборах значений переменных x1, x2, …, xn, которые содержат ровно ai единиц, где 0 ≤ ai ≤ n, 1 ≤ i ≤ r и 0 ≤ r ≤ n + 1. Функция F обозначается как F = Fna1 , a 2 ,…,a r (X) где X = {x1, x2, …, xn}.
{
}
Если r = 1, то функция F = Fna (X) называется фундаментальной (или элементарной)
симметрической булевой функцией.
Произвольная симметрическая булева функция F = F(xl, x2, …, xn) взаимно однозначно
представляется (n + 1)-разрядным (локальным) двоичным кодом π(F) = (π0, π1, …, πn), где
πi - значение функции F на (любом) наборе значений n переменных, содержащем
i (0 ≤ i ≤n) единиц. Иначе, πi = 1 тогда и только тогда, когда i - рабочее число F.
Известно, что отношение частичной симметрии произвольной булевой функции n переменных F = F(X) разбивает (единственным образом) множество переменных X = {x1, x2, …, xn}
на классы симметрии, X1, X2, …, Xk, где l ≤ k≤n.
Если k = l, то функция F является (полностью) симметрической; если k = 2, то
F - бисимметрическая булева функция; если k = n, то функция F не обладает свойством
частичной симметрии переменных.
Для бисимметрической булевой функции F = F(X1, X2), где X1 = {x1, x2} и X2 = {x3,
x4}, имеет место формула:
F(X1 , X 2 ) = F20 (x1 , x 2 ) ⋅ G 0 (x 3 , x 4 ) ∨
∨ F21 (x1 , x 2 ) ⋅ G1 (x 3 , x 4 ) ∨ F22 (x1 , x 2 ) ⋅ G 2 (x 3 , x 4 )
или
3
BY 13992 C1 2011.02.28
F(X1, X 2 ) = F20 (X1 ) ⋅ G 0 (X 2 ) ⊕ F21 (X1 ) ⋅ G1 (X 2 ) ⊕ F22 (X1 ) ⋅ G 2 (X 2 ),
(1)
где F20 (x1, x 2 ) = x1 ⋅ x 2 , F21 (x1, x 2 ) = x1 ⋅ x 2 ∨ x1 ⋅ x 2 , F22 (x1, x 2 ) = x1, x 2 и G 0 = G 0 (x 3 , x 4 ),
G1 = G1 (x 3 , x 4 ), G 2 = G 2 (x 3 , x 4 ) - симметрические булевы функции, зависящие от переменных х3, х4.
Двоичный вектор ω(F) = (π(G 0 ), π(G1 ), π(G 2 )) = (ω0 , ω1 ,…, ω8 ) называется двоичным кодом бисимметрической булевой функции F = F(X1,X2).
Если в формуле (1) заменить x1 = x1 ⊕ 1 и x 2 = x 2 ⊕ 1, то
F(Xl,X2) = H0(X2)⊕(x1⊕x2)⋅Hl(X2) ⊕xlx2⋅H2(X2),
где
H0(X2) = G0(X2), Hl(X2) = G0(X2) ⊕Gl(X2),
H2(X2) = G0(X2)⊕G2(X2).
Обозначим γ(F) = (π(H0), π(H1), π(H2)) = (γ0, γ1, …, γ8). Векторы ω(F) и γ(F) связаны
между собой следующими соотношениями:
(2)
γi = ωi, γi+3 = ωi⊕ωi+3, γi+6 = ωi⊕ωi+6,
где i = 0, 1, 2.
Поясним метод построения вектора u(F) = (u0,u1, …, u8) - вектора настройки устройства (фигура) на вычисление некоторой заданной бисимметрической булевой функции
F = F(X1,X2).
С помощью локальных кодов π(H0) = (γ0, γ1, γ2), π(H1) = (γ3, γ4, γ5) и π(Н2) = (γ6, γ7, γ8) из
таблицы настройки (таблица) получаем значения векторов (u0, u1, u2),(u3, u4, u5) и (u6, u7, u8),
являющихся составными частями вектора настройки u(F) = (u0, u1, …, u8).
Первообразная функция устройства для вычисления бисимметрических булевых
функций четырех переменных (фигура) имеет вид:
(3)
F(x1, x2, u0, u1, …, u8) = u0⊕u1,u2⊕(x1⊕x2)⋅(u3⊕u4u5)⊕x1x2⋅(u6⊕u7u8).
Пример.
Предположим, что на выходе 21 устройства (фигура) требуется реализовать бисимметрическую булеву функцию
F(x1, x 2 , x 3 , x 4 ) = x1 ⋅ x 2 ⋅ (x 3 ⊕ x 4 ) ∨ (x1 ∨ x 2 ) ⋅ x 3x 4 .
(
) (
)
Так как F = x1 ⋅ x 2 ⋅ x 3x 4 ∨ x 3 x 4 ∨ x1x 2 ∨ x1 x 2 ⋅ x 3x 4 ∨ x1x 2 x 3x 4 , то формула (1) принимает вид
F = x1 ⋅ x 2 ⋅ G 0 (x 3 , x 4 ) ∨ x1x 2 ∨ x1 x 2 ⋅ G1 (x 3 , x 4 ) ∨ x1x 2 ⋅ G 2 (x 3 , x 4 ),
где π(G0) = (0,1,0) и π(Gl) = π(G2) = (0,0,1).
Отсюда следует, что двоичный код бисимметрической булевой функции F = F(X1,X2)
равен
ω(F) = (π(G0), π(G1), π(G2)) = (0,1,0,0,0,1,0,0,1).
(
u3i
0
0
х3
1
)
Сигналы настройки
u3i + 1
u3i + 2
0
0
x3
x4
х4
1
x3
x4
Выход
π(Hi) = (γ3i, γ3i + 1, γ3i + 2)
000
001
010
011
0
x3
x4
100
x3
1
1
x4
х3
0
1
x4
0
101
110
111
4
BY 13992 C1 2011.02.28
Используя формулы (2), получаем γ(F) = (0,1,0,0,1,1,0,1,1), т.е. π(H0) = (0,1,0),
π(H1) = (0,1,1) и π(H2) = (0,1,1).
Принимая во внимание описанную выше процедуру построения вектора настройки
u(F) = (u0, u1, …, u8), получаем u0 = x3,u1 = x4, u2 = 1, u3 = 1, u 4 = x 3 , u 5 = x 4 , u6 = 1,
u 7 = x3 и u8 = x 4.
Следовательно, для вычисления на выходе 21 устройства (фигура) функции
F(x1, x 2 , x 3 , x 4 ) = x1 x 2 ⋅ (x 3 ⊕ x 4 ) ∨ (x1 ∨ x 2 ) ⋅ x 3x 4 необходимо на настроечные входы подать значения u0 = x3, u1 = x4, u2 = u3 = u6 = 1, u 4 = u 7 = x 3 и u 5 = u8 = x 4 .
В таком случае первообразная функция (3) устройства для вычисления бисимметрических булевых функций четырех переменных принимает вид:
F(X1, X 2 ) = x 3 ⊕ x 4 ⋅ 1 ⊕ (x1 ⊕ x 2 ) ⋅ 1 ⊕ x 3 ⋅ x 4 ⊕ x1x 2 ⋅ 1 ⊕ x 3 ⋅ x 4 =
(
= x 3 ⊕ x 4 ⊕ (x1 ⊕ x 2 ⊕ x1x 2 ) ⋅ (x 3 ∨ x 4 ) =
)
(
)
= x 3 ⊕ x 4 ⊕ (x1 ⊕ x 2 ⊕ x1x 2 ) ⋅ (x 3 ⊕ x 4 ⊕ x 3x 4 ) =
= (1 ⊕ x1 ⊕ x 2 ⊕ x1x 2 ) ⋅ (x 3 ⊕ x 4 ) ⊕ (x1 ⊕ x 2 ⊕ x1x 2 ) ⋅ x 3x 4 =
= x1 ⋅ x 2 ⋅ (x 3 ⊕ x 4 ) ∨ (x1 ∨ x 2 ) ⋅ x 3x 4 .
Основными достоинствами заявляемого устройства для вычисления бисимметрических булевых функций четырех переменных являются:
небольшая конструктивная сложность, равная 22 (с учетом того что сложность полусумматора равна 4);
небольшое число внешних выводов (два информационных и девять настроечных входов, выход).
Отметим, что сложность устройства-прототипа равна 37, а число внешних выводов - 14.
Источники информации:
1. Патент РБ 10219, МПК G 06 F 7/00, 2008.
2. Патент РБ 3031, МПК G 06 F 7/00, 1999 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
103 Кб
Теги
патент, by13992
1/--страниц
Пожаловаться на содержимое документа