close

Вход

Забыли?

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

?

Патент BY16357

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.10.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ЧЕТЫРЕХ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20101194
(22) 2010.08.05
(43) 2011.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
BY 16357 C1 2012.10.30
BY (11) 16357
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 10219 C1, 2008.
BY 2119 C1, 1998.
BY 3031 C1, 1999.
BY 7947 C1, 2006.
SU 1683000 A1, 1991.
(57)
Устройство для вычисления полусимметрических булевых функций четырех переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен
с выходом устройства, первый настроечный вход которого соединен с первым входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА; с первого по пятый элементы И, i-й вход первого из которых, где i = 1, 2, соединен с i-м информационным входом устройства, с i-м
инверсным входом второго элемента И, с i-м входом третьего элемента И и с i-м инверсным входом четвертого элемента И, а выход соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с третьего по шестой соединены
соответственно с выходами второго, третьего, четвертого и пятого элементов И, первый
вход последнего из которых соединен с третьими входами третьего и четвертого элементов И и с третьим информационным входом устройства, (i + 1)-й настроечный вход которого соединен с третьим входом i-го элемента И; (i + 3)-й настроечный вход устройства
соединен с четвертым входом (i + 2)-го элемента И, а шестой настроечный вход устройства соединен со вторым входом пятого элемента И.
BY 16357 C1 2012.10.30
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полусимметрических булевых функций четырех переменных.
Известно устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать
настроечных входов и один выход [1].
Известное устройство, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный
вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять (реализовать) полусимметрические булевы
функции четырех переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, девять информационных входов и один выход [2].
Устройство-прототип предназначено для вычисления произвольных симметрических
булевых функций четырех переменных. Конструктивная сложность устройства (по числу
входов логических элементов) равна 16, а быстродействие составляет 2τ, где τ - задержка
на один логический элемент.
Устройство-прототип, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный
вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы
функции четырех переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления симметрических булевых функций четырех переменных
за счет реализации полусимметрических булевых функций четырех переменных.
Устройство для вычисления полусимметрических булевых функций четырех переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с
выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Устройство также содержит с первого по пятый элементы И, i-й вход первого из которых, где i = 1, 2, соединен с i-м информационным входом устройства, с i-м инверсным
входом второго элемента И, с i-м входом третьего элемента И и с i-м инверсным входом
четвертого элемента И.
Выход первого элемента И соединен со вторым входом элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, входы которого с третьего по шестой соединены соответственно с выходами второго, третьего, четвертого и пятого элементов И, первый вход последнего из которых соединен с третьими входами третьего и четвертого элементов И и с третьим
информационным входом устройства.
Причем (i + 1)-й настроечный вход устройства соединен с третьим входом i-го элемента И, (i + 3)-й настроечный вход устройства соединен с четвертым входом (i + 2)-го
элемента И, а шестой настроечный вход устройства соединен со вторым входом пятого
элемента И.
Названный технический результат достигается с помощью введения в логическую
схему устройства новых элементов (элементов И) с последующим изменением соединений между логическими элементами схемы.
2
BY 16357 C1 2012.10.30
На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных.
Устройство для вычисления полусимметрических булевых функций четырех переменных содержит пять элементов И 1…5, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6,
три информационных входа 7, 8 и 9, шесть настроечных входов 10…15 и выход 16.
Устройство для вычисления полусимметрических булевых функций четырех переменных работает следующим образом.
На информационные входы устройства 7, 8 и 9 поступают значения переменных x1, x2,
x4, на настроечные входы 10…15 - сигналы настройки u0, u1,…, u5, значения которых принадлежат множеству 0, 1, x 3 , x 3 .
На выходе устройства 16 вычисляется полусимметрическая булева функция
F = F(X1, x4), где X1 = {x1, x2, x3}, определяемая вектором настройки u(F) = (uo, u1,…, u5).
Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций четырех переменных.
Булева функция n переменных F = F(x1, x2,…, xn) называется симметрической, если
она не меняет своего значения после перестановки любой пары переменных x1 и xj, где
i ≠ j и i, j = 1, 2,…, n.
Симметрическая булева функция F = F(x1, x2,…, xn) определяется множеством рабочих
чисел A(F) = {a1, a2,…, ar]. Функция F принимает единичные значения на тех и только тех
наборах значений переменных x1, x2,…, xn, которые содержат ровно ai единиц, где 0≤ai≤n,
1≤i≤r и 0≤r≤n + 1.
Симметрическая булева функция F = F(x1, x2,…, xn) взаимно однозначно представляется (n + 1)-разрядным двоичным вектором (локальным кодом) π(F) = (π0, π1,…, πn), где
πi - значение функции F на (любом) наборе значений n переменных, содержащем i (0≤i≤n)
единиц, т.е. πi = 1 тогда и только тогда, когда i - рабочее число F.
Булева функция n переменных F = F(x1, x2,..., xn) называется полусимметрической, если булевы функции F0 = F(xn = 0) = F0(X1, 0) и F1 = F(xn = 1) = F1(X1, 1) являются симметрическими, зависящими от n-1 переменных множества X1 = {x1, x2,..., xn-1}, где n≥3. Такая
булева функция обозначается через F = F(X1, xn).
Любая симметрическая булева функция n переменных F = F(X) является полусимметрической, а обратное утверждение - не всегда верно. Другими словами, симметрические булевы
функции F = F(X) являются частным случаем полусимметрических функций F = F(X1, xn).
Для булевой функции F = F(X1, xn) имеет место формула дизъюнктивного разложения
по переменной xn вида
(1)
F(X1 , x n ) = x n F0 ∨ x n F1 .
Симметрические булевы функции n-1 переменных F0 = F0(Xl), F1 = F1(X1) задаются посредством n-разрядных двоичных векторов π(F0 ) = (f 00 , f10 ,K, f n0−1 ) и π(F1 ) = (f 01 , f11 ,K, f n1−1 )
соответственно.
Если для компонент векторов π(F0) и π(F1) выполняется условие f j0 = f j1−1 , где
{
}
j = 1, 2,…, n-1, то полусимметрическая булева функция F = F(X1, xn) является симметрической, зависящей от n переменных.
Двоичный вектор ω(F) = (π(F0), π(F1)) является локальным кодом булевой функции
F = F(X1, xn). Так как вектор ω(F) имеет 2n разрядов, то число различных функций вида
F = F(X1, xn) равно 22n = 4n (число симметрических булевых функций n переменных
F = F(X) равно 2n+1).
Если в формуле (1) заменить x n = x n ⊕ 1 , то
F(X1 , x n ) = x n F0 ⊕ x n F1 = (x n ⊕ 1)F0 ⊕ x n F1 = F0 ⊕ x n (F0 ⊕ F1 ), т.е.
3
BY 16357 C1 2012.10.30
F(X1 , x n ) = G 0 ⊕ x n G1 ,
(2)
где G0(X1) = F0(X1), G1(X1) = F0(X1)⊕F1(X1), π(G 0 ) = (g , g ,K, g ) и π(G1 ) = (g , g11 ,..., g1n −1 ) .
На фигуре приведена логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных F = F(X1, x4). Первообразная функция логической схемы имеет вид
F(u 0 , u1 ,K, u 5 , x1 , x 2 , x 4 ) = x1 ⋅ x 2 ⋅ u 0 ⊕ x1 ⋅ x 2 ⋅ u1 ⊕ u 2 ⊕
(3)
⊕ x1 ⋅ x 2 ⋅ u 3 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ u 4 ⋅ x 4 ⊕ u 5 ⋅ x 4 .
Поясним алгоритм настройки устройства (фигура) на вычисление произвольно заданной функции F = F(Xl, x4).
Если n = 4, то формулы (1) и (2) принимают вид
(4)
F(X1 , x 4 ) = x 4 ⋅ F0 ∨ x 4 ⋅ F1 ,
0
0
0
1
0
n −1
1
0
F(X1 , x 4 ) = G 0 ⊕ x 4 ⋅ G1 ,
(5)
где G0(x1, x2, x3) = F0(x1, x2, x3) и G1(x1, x2, x3) = F0(x1, x2, x3)⊕F1(x1, x2, x3).
Представим функцию F = F(X1,x4) посредством формул (4), (5) и последовательно вычислим значения векторов π(F0 ) = (f 00 , f10 , f 20 , f 30 ) , π(F1 ) = (f 01 , f11 , f 21 , f 31 ) , π(G 0 ) = (g 00 , g10 , g 02 , g 30 ) ,
π(G1 ) = (g10 , g11 , g12 , g13 ) , где g i0 = f i0 , g1i = f i0 ⊕ f i1 и i = 0, 1, 2, 3.
Посредством таблицы (таблица), применительно к векторам π(G k ) = (g 0k , g1k , g k2 , g 3k ) , вычислим значения векторов (u3k, u3k+1, u3k+2), где k = 0, 1. Полученные при этом вектора (u0, u1, u2),
(u3, u4, u5) являются составными частями искомого вектора настройки u(F) = (u0, u1,..., u5).
Двоичный код симметрической булевой
Вектор настройки
функции Gk = Gk(x1, x2, x3)
u(F) = (u0, u1, u2, u3, u4, u5)
π(G k ) = (g 0k , g1k , g k2 , g 3k ) ,
u3k
u3k+1
u3k+2
0000
0
0
0
0001
x3
0
0
0010
1
x3
x3
0011
x3
x3
x3
0100
x3
1
x3
0101
1
1
x3
0110
x3
x3
1
0111
0
x3
1
1000
0
x3
0
1001
1010
1011
x3
1
x3
x3
1
1
0
x3
x3
1100
x3
x3
x3
1101
1110
1111
1
x3
0
x3
0
0
x3
1
1
Пример 1.
Допустим, что на выходе 16 устройства (фигура) требуется вычислить полусимметрическую булеву функцию
F(X1, x4) = x1x2x3⊕x4.
4
BY 16357 C1 2012.10.30
F(X , x ) = x x x ⋅ x ∨ (x ∨ x ∨ x )⋅ x , то F = x x x
Так как
0
1 2 3 и F1 = x1 ∨ x 2 ∨ x 3 ,
1
4
1 2 3
4
1
2
3
4
π(Fo) = (0, 0, 0, 1) и π(F1) = (1, 1, 1, 0). В таком случае π(G0) = π(F0) = (0, 0, 0, 1) и
π(G1) = π(F0)⊕π(F1) = (1, 1, 1, 1).
Если обратиться (дважды) к таблице (таблица), то получим (u0,u1,u2) = (x3, 0, 0) и
(u3, u4, u5) = (0, 0,1), т.е. u(F) = (x3, 0, 0, 0, 0, 1).
Следовательно, для вычисления на выходе 16 устройства функции F(X1, x4) = x1x2x3⊕x4
необходимо на настроечный 10 подать значение x3, на настроечные входы 11, 12, 13 и 14 значение "0", на настроечный вход 15 - значение "1".
В качестве проверки подставим в формулу (3) значения вектора настройки
u(F) = (х3, 0, 0, 0, 0, 1), тогда первообразная функция устройства будет иметь вид
F(X1 , x 4 ) = x1 ⋅ x 2 ⋅ x 3 ⊕ x1 ⋅ x 2 ⋅ 0 ⊕ 0 ⊕ x1 ⋅ x 2 ⋅ 0 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ 0 ⋅ x 4 ⊕ 1 ⋅ x 4 = x1x 2 x 3 ⊕ x 4 .
Пример 2.
Предположим, что на выходе 16 устройства требуется вычислить полусимметрическую булеву функцию
F(X1 , x 4 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 .
Так как F0 = x1 ⋅ x 2 ⋅ x 3 и F1 = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 , то π(F0) = (1, 0, 0, 0),
π(F1) = (0, 0, 1, 0), π(G0) = (1, 0, 0, 0) и π(G1) = (1, 0, 1, 0).
С помощью таблицы (таблица) получаем (u 0 , u1 , u 2 ) = 0, x 3 , 0 и (u3, u4, u5) = (1, 1, x3),
(
(
)
)
т.е. u (F) = 0, x 3 , 0, 1, 1, x 3 .
Следовательно, для того чтобы на выходе 16 устройства реализовать заданную полусимметрическую булеву функцию F = F(X1, x4), необходимо на настроечные входы 10 и 12
подать значения "0", на настроечный вход 11 - значение x 3 , на настроечные входы 13 и
14 - значение "1" и на настроечный вход 15 - значение x3.
В таком случае первообразная функция (3) принимает вид
f (X1 , x 4 ) = x1 ⋅ x 2 ⋅ 0 ⊕ x1 ⋅ x 2 ⋅ x 3 ⊕ 0 ⊕ x1 ⋅ x 2 ⋅ 1 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ 1 ⋅ x 4 ⊕ x 3 ⋅ x 4 =
(
)
(
)
= x1 ⋅ x 2 ⋅ x 3 ⊕ x1 ⋅ x 2 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ x 4 ⊕ x 3 ⋅ x 4 = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⊕ x 4 ⊕ x1 ⋅ x 2 ⋅ x 3 ⊕ x 3 ⋅ x 4 ⊕
(
)
(
)
⊕ x1 ⋅ x 2 ⋅ x 3 ⊕ x 3 ⋅ x 4 ⊕ x1 ⋅ x 2 ⊕ x1 ⋅ x 2 ⊕ x1 ⋅ x 2 ⊕ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 =
= x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⊕ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 =
= x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 .
Основным достоинством заявляемого устройства являются широкие функциональные
возможности. Устройство реализует любую из 256 полусимметрических булевых функций, зависящих от переменных x1, x2, x3, x4.
Отметим, что устройство-прототип ориентировано на вычисление только симметрических булевых функций четырех переменных x1, x2, x3, x4, число которых равно 32.
При этом заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы.
Источники информации:
1. Патент РБ 8619, МПК G 06F 7/00, 2006.
2. Патент РБ 10219, МПК G 06F 7/00, 2008 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
102 Кб
Теги
by16357, патент
1/--страниц
Пожаловаться на содержимое документа