close

Вход

Забыли?

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

?

Патент BY16242

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.08.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ШЕСТИ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20101154
(22) 2010.07.29
(43) 2011.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
BY 16242 C1 2012.08.30
BY (11) 16242
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 8973 C1, 2007.
BY a20090420, 2009.
BY a20090335, 2009.
BY 7947 C1, 2006.
RU 2047892 C1, 1995.
(57)
Устройство для вычисления бисимметрических булевых функций шести переменных,
содержащее четыре элемента ИЛИ и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход
которого соединен с выходом первого элемента ИЛИ, первый вход которого соединен со
вторым настроечным входом устройства, третий, четвертый и пятый настроечные входы
которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ
соответственно, отличающееся тем, что содержит второй, третий, четвертый и пятый
элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с
первого по седьмой элементы И, выход первого из которых соединен с третьим входом
первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с
выходом второго элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, i-й вход которого, где i = 1, 2, 3, соединен с i-м информационным входом устройства, с i-м входом мажоритарного элемента с порогом два и
BY 16242 C1 2012.08.30
с i-м входом третьего элемента И, выход которого соединен с пятым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шестой вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом мажоритарного элемента с
порогом два, а второй вход соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй входы которого соединены соответственно с выходом третьего элемента ИЛИ и с выходом пятого элемента И, а третий вход соединен с шестым
настроечным входом устройства, седьмой настроечный вход которого соединен с первым
входом первого элемента И, j-й вход которого, где j = 2, 3, соединен с (j + 2)-м информационным входом устройства, с j-м входом первого, второго, третьего и четвертого элементов ИЛИ и с (j-1)-м входом пятого, шестого и седьмого элементов И, третьи входы
которых соединены соответственно с восьмым, девятым и десятым настроечными входами устройства, одиннадцатый настроечный вход которого соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и третий входы которого
соединены соответственно с выходом второго элемента ИЛИ и с выходом шестого элемента И, а выход соединен со вторым входом второго элемента И; двенадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО
МОДУДЮ ДВА, второй и третий входы которого соединены соответственно с выходом
четвертого элемента ИЛИ и с выходом седьмого элемента И, а выход соединен с четвертым входом третьего элемента И.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления бисимметрических булевых функций шести переменных.
Известно устройство для вычисления симметрических булевых функций шести переменных, которое содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, семь элементов И,
шесть информационных и семь настроечных входов, выход [1].
Известное устройство, как и заявляемое, содержит семь элементов И, мажоритарный
элемент с порогом два и два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого
из которых соединен с выходом устройства, первый настроечный вход которого соединен
с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого со
второго по пятый соединены с выходами первого, второго, третьего и четвертого элементов И.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять (реализовать) бисимметрические булевы
функции шести переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций шести переменных, которое содержит два полных одноразрядных сумматора, пятнадцать элементов ИЛИ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
шесть информационных и шестнадцать настроечных входов, выход [2].
Устройство-прототип, как и предлагаемое устройство, содержит четыре элемента
ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, первый настроечный вход которого соединен с первым входом элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого
элемента ИЛИ, первый вход которого соединен со вторым настроечным входом устройства, третий, четвертый и пятый настроечные входы которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ соответственно.
Недостатком устройства-прототипа является большое число внешних выводов, равное
23 (двадцать два входа и выход).
2
BY 16242 C1 2012.08.30
Изобретение направлено на решение технической задачи: уменьшение числа внешних
выводов устройства для вычисления бисимметрических булевых функций шести переменных.
Устройство для вычисления бисимметрических булевых функций шести переменных
содержит четыре элемента ИЛИ и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Второй вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом
первого элемента ИЛИ, первый вход которого соединен со вторым настроечным входом
устройства, третий, четвертый и пятый настроечные входы которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ соответственно.
В отличие от прототипа устройство содержит второй, третий, четвертый и пятый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с первого по седьмой элементы И, выход первого из которых соединен с третьим входом первого
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Четвертый вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, i-й вход которого, где i = 1, 2, 3, соединен с i-м информационным входом устройства, с i-м входом мажоритарного элемента с порогом два и с
i-м входом третьего элемента И.
Выход третьего элемента И соединен с пятым входом первого элемента СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, шестой вход которого соединен с выходом четвертого элемента И,
первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй входы которого соединены соответственно с выходом третьего элемента
ИЛИ и с выходом пятого элемента И, а третий вход соединен с шестым настроечным входом устройства.
Седьмой настроечный вход устройства соединен с первым входом первого элемента
И, j-й вход которого, где j = 2, 3, соединен с (j + 2)-м информационным входом устройства, с j-м входом первого, второго, третьего и четвертого элементов ИЛИ и с (j-1)-м входом пятого, шестого и седьмого элементов И, третьи входы которых соединены
соответственно с восьмым, девятым и десятым настроечными входами устройства.
Одиннадцатый настроечный вход устройства соединен с первым входом четвертого
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и третий входы которого соединены
соответственно с выходом второго элемента ИЛИ и с выходом шестого элемента И, а выход соединен со вторым входом второго элемента И.
Двенадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУДЮ ДВА, второй и третий входы которого соединены соответственно с выходом четвертого элемента ИЛИ и с выходом седьмого элемента И, а выход
соединен с четвертым входом третьего элемента И.
Названный технический результат достигается посредством введения в логическую
схему устройства новых логических элементов (элементы И и мажоритарный элемент с
порогом два) с последующим изменением соединений между элементами схемы.
На фигуре представлена логическая схема устройства для вычисления бисимметрических булевых функций шести переменных.
Устройство для вычисления бисимметрических булевых функций содержит семь элементов И 1...7, четыре элемента ИЛИ 8...11, мажоритарный элемент с порогом два 12, пять
элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 13... 17, пять информационных входов
18...22, двенадцать настроечных входов 23...34 и выход 35.
Устройство для вычисления бисимметрических булевых функций шести переменных
работает следующим образом. На информационные входы устройства 18...22 поступают
3
BY 16242 C1 2012.08.30
значения переменных x1, x2, x3, x4, x5 соответственно, на настроечные входы 23...34 - сигналы настройки u0, u1,...,u11, значения которых принадлежат множеству {0, 1, x6, x 6 }. На
выходе устройства 35 вычисляется (реализуется) бисимметрическая булева функция
F = F(X1, X2), где X1 = {x1, x2, x3} и X2 = {x4, x5, x6}, определяемая вектором настройки
u(F) = (u0, u1,..., u11).
Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций шести переменных.
Произвольная симметрическая булева функция n переменных F = F(x1, x2,..., xn) характеризуется множеством рабочих чисел A(F) = {a1, a2,..., ar}. Функция F принимает единичные значения на тех и только тех наборах значений переменных x1, x2,..., xn, которые
содержат ровно ai единиц, где 0 ≤ ai ≤ n, 0 ≤ 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(x1, x2,..., xn) взаимно однозначно представляется (n + 1)-разрядным двоичным кодом (вектором) π(F) = (π0, π1,..., πn), где πi - значение
функции F на (любом) наборе значений n переменных, содержащем i (0 ≤ i ≤ n) единиц.
Другими словами, πi = 1 тогда и только тогда, когда i - рабочее число функции F.
Если произвольная булева функция n переменных F = F(x) не меняет своего значения
после перестановки любой пары переменных xi и xj (где i ≠ j и i, j = 1, 2,..., n), то функция F
является симметрической. Если функция F = f(X) не меняет своего значения после перестановки некоторых пар переменных xi и xj, то булева функция F = F(X) обладает свойством частичной симметрии переменных.
Известно, что отношение частичной симметрии разбивает (единственным образом)
множество переменных X = {x1, x2,..., xn} на классы симметрии X1, X2,..., Xk, где 1 ≤ k ≤ n.
Если k = 1, то функция F является (полностью) симметрической; если k = 2, то F - бисимметрическая булева функция; если k = n, то функция F не обладает свойством частичной симметрии переменных.
Бисимметрическая булева функция обозначается F(X) = F(Xl, X2), где X1, X2 - классы
симметрии.
Для булевой функции F(Х) = F(X1, X2), где X1 = {x1, x2, x3} и X2 = {x4, x5, x6}, имеет
место формула
F(X1 , X 2 ) = F30 (X1 ) ⋅ G 0 (X 2 ) ∨ F31 (X1 ) ⋅ G l (X 2 ) ∨ F32 (X1 ) ⋅ G 2 (X 2 ) ∨ F33 (X1 ) ⋅ G 3 (X 2 )
или
F(X1, X2) F30 (X1)⋅G0(X2) ⊕ F31 (X1)⋅G1(X2) ⊕ F32 (X1)⋅G2(X2) ⊕ F33 (X1)⋅G3(X2)
(1)
где
F30 ( x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ,
F31 ( x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ,
F32 ( x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x1 ∨ x 2 ⋅ x 3 ,
F33 ( x1 , x 2 , x 3 ) = x1x 2 x 3 .
В формуле (1) булевы функции G0 = G0(x4, x5, x6), G1 = G1(x4, x5, x6), G2 = G2(x4, x5, x6),
G3 = G3(x4, x5, x6) являются симметрическими, каждая из которых задается посредством
четырехразрядного двоичного вектора π(G k ) = (g 0k , g1k , g k2 , g 3k ) , где k = 0, 1, 2, 3.
Если в формуле (1) заменить x1 = x1 ⊕ 1, x 2 = x 2 ⊕ 1 и x 3 = x 3 ⊕ 1 , то после несложных преобразований получим
4
BY 16242 C1 2012.08.30
F(X1 , X 2 ) = H 0 (X 2 ) ⊕ ( x1 ⊕ x 2 ⊕ x 3 ) ⋅ H1 (X 2 ) ⊕
(2)
⊕ ( x1x 2 ⊕ x1x 3 ⊕ x 2 x 3 ) ⋅ H 2 (X 2 ) ⊕ x1x 2 x 3 ⋅ H 3 (X 2 ),
где симметрические булевы функции H0(X2), H1(X2), H2(X2), H3(X2) вычисляются по формулам
H0(X2) = G0(X2), H1(X2) = G0(X2) ⊕ G1(X2),
H2(X2) = G0(X2) ⊕ G2(X2), H3(X2) = G0(X2) ⊕ G1(X2) ⊕ G2(X2) ⊕ G3(X2).
Следовательно, значения компонент двоичных векторов π(G k ) = (g 0k , g1k , g k2 , g 3k ) и
π(H k ) = (h 0k , h1k , h k2 , h 3k ) связаны между собой следующими соотношениями (k = 0, 1, 2, 3):
(3)
h i0 = g10 , h1i = g i0 ⊕ g1i , h i2 = g i0 ⊕ g i2 , h 3i = g i0 ⊕ g1i ⊕ g i2 ⊕ g 3i
где i = 0, 1, 2, 3.
Поясним метод построения вектора настройки u(F) = (u0, u1,..., u11) заявляемого
устройства (фигура) на вычисление произвольно заданной би-симметрической булевой
функции F = F(X1, X2).
1. Представим функцию F = F(X1, X2) посредством формулы (1) и вычислим значения
компонент векторов π(G k ) = (g 0k , g1k , g k2 , g 3k ) для симметрических булевых функций
Gk = Gk(x4, x5, x6), где k = 0, 1, 2, 3.
2. Определим по формулам (3) значения компонент двоичных векторов
π(H k ) = (h 0k , h1k , h k2 , h 3k ) для симметрических булевых функций Hk = Hk(x4, x5, x6), входящих в представление функции F = F(X1, X2) посредством формулы (2), где k = 0, 1, 2, 3.
3. Построим вектор настройки u(F) = (u0, u1,..., u11) следующим образом: для каждого из
двоичных векторов π(H 0 ) = (h 00 , h10 , h 02 , h 03 ) , π(H1 ) = (h10 , h11 , h12 , h13 ) , π(H 2 ) = (h 02 , h12 , h 22 , h 32 )
и π(H 3 ) = (h 30 , h13 , h 32 , h 33 ) вычислим с помощью таблицы настроек (таблица) значения векторов (u0, u1, u2), (u3, u4, u5), (u6, u7, u8) и (u9, u10, u11) соответственно.
Первообразная функция заявляемого устройства для вычисления бисимметрических
булевых функций шести переменных (фигура) имеет вид
F(x1, x2, x3, x4, x5, u0, u1,..., u11) = x4x5u0 ⊕ (x4 ∨ x5 ∨ u1) ⊕ u2 ⊕
⊕ (x1 ⊕ x2 ⊕ x3)⋅(x4x5u3 ⊕ (x4 ∨ x5 ∨ u4) ⊕ u5) ⊕
(4)
⊕ (x1x2 ⊕ x1x3 ⊕ x2x3)⋅(x4x5u6 ⊕ (x4 ∨ x5 ∨ u7) ⊕ u8) ⊕
⊕ x1x2x3⋅(x4x5u9 ⊕ (x4 ∨ x5 ∨ u10) ⊕ u11).
Рассмотрим три примера построения вектора настройки u(F) = (u0, u1,..., u11) для вычисления (реализации) на выходе 35 устройства бисимметрических булевых функций
F = F(X1, X2).
Пример 1
Предположим, что на выходе устройства 35 требуется вычислить бисимметрическую
булеву функцию
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ ( x 4 ∨ x 5 ∨ x ) ∨ x1x 2 x 3 x 4 x 5 x 6 .
Так как формула (1), применительно к данной функции, принимает вид
F(X1 , X 2 ) = F30 (X1 ) ⋅ G 0 (X 2 ) ∨ F31 (X1 ) ⋅ G1 (X 2 ) ∨ F32 (X1 ) ⋅ G 2 (X 2 ) ∨
∨ F33 (X1 ) ⋅ G 3 (X 2 ) = F30 (X1 ) ⋅ G 0 (X 2 ) ⊕ F31 (X1 ) ⋅ G1 (X 2 ) ⊕
⊕ F32 (X1 ) ⋅ G 2 (X 2 ) ⊕ F33 (X1 ) ⋅ G 3 (X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ ( x 4 ∨ x 5 ∨ x 6 ) ⊕
⊕ ( x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ) ⋅ 0 ⊕
⊕ ( x 1 ⋅ x 2 ⋅ x 3 ∨ x 1 ⋅ x 2 ⋅ x 3 ∨ x 1 ⋅ x 2 ⋅ x 3 ) ⋅ 0 ⊕ x 1x 2 x 3 x 4 x 5 x 6 ,
то π(G0) = (0, 1, 1, 1), π(G1) = π(G2) = (0, 0, 0, 0) и π(G3) = (0, 0, 0, 1).
Если представить функцию F = F(X1, X2) формулой (2), то
F(X1, X2) = H0(X2) ⊕ (x1 ⊕ x2 ⊕ x3)⋅H1(X2) ⊕ (x1x2 ⊕ x1x3 ⊕ x2x3)⋅H2(X2) ⊕ x1x2x3⋅H3(X2),
5
BY 16242 C1 2012.08.30
где
π(H0) = π(G0) = (0,1,1,1),
π(H1) = π(G0) ⊕ π(G1) = (0,1,1,1) ⊕ (0,0,0,0) = (0,1,1,1),
π(H2) = π(G0) ⊕ π(G2) = (0,1,1,1) ⊕ (0,0,0,0) = (0,1,1,1) и
π(H3) = π(G0) ⊕ π(G1) ⊕ π(G2) ⊕ π(G3) =(0,1,1,1) ⊕ (0,0,0,0) ⊕ (0,0,0,0) ⊕ (0,0,0,1) = (0,1,1,0).
Если π(H0) = π(H1) = π(H2) = (0,1,1,1) и π(H3) = (0,1,1,0), то из таблицы настроек (таблица) получаем u0 = 0, ul = x6, u2 = 0, u3 = 0, u4 = x6, u5 = 0, u6 = 0, u7 = x6, u8 = 0, u9 = x6,
u10 = x6 и u11 = 0.
Следовательно, для вычисления на выходе 35 устройства (фигура) бисимметрической
булевой функции
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ ( x 4 ∨ x 5 ∨ x 6 ) ∨ x1x 2 x 3 x 4 x 5 x 6
необходимо на настроечные входы 23, 25, 26, 28, 29, 31 и 34 подать значение "0", а на
настроечные входы 24, 27, 30, 32 и 33 - значение x6.
Если u0 = u2 = u3 = u5 = u6 = u8 = u11 = 0 и u1 = u4 = u7 = u9 = u10 = x6, то первообразная
функция (4) заявляемого устройства принимает вид
F(x1, x2, x3, x4, x5, u0, u1,..., u11) = x4x5⋅0 ⊕ (x4 ∨ x5 ∨ x6) ⊕ 0 ⊕
⊕ (x1 ⊕ x2 ⊕ x3)⋅(x4x5⋅0 ⊕ (x4 ∨ x5 ∨ x6) ⊕ 0) ⊕
⊕ (x1x2 ⊕ x1x3 ⊕ x2x3)⋅(x4x5⋅0 ⊕ (x4 ∨ x5 ∨ x6) ⊕ 0) ⊕
⊕x1x2x3⋅(x4x5x6 ⊕ (x4 ∨ x5 ∨ x6) ⊕ 0) =
= (1 ⊕ x1 ⊕ x2 ⊕ x3 ⊕ x1x2 ⊕ x1x3 ⊕ x2x3 ⊕ x1x2x3)⋅(x4 ∨ x5 ∨ x5) ⊕
⊕ x1x2x3⋅(x4x5x6 ⊕ 0) = x1 ⋅ x 2 ⋅ x 3 ⋅(x4 ∨ x5 ∨ x6) ⊕ x1x2x3x4x5x6 =
= x1 ⋅ x 2 ⋅ x 3 ⋅(x4 ∨ x5 ∨ x6) ∨ x1x2x3x4x5x6.
Пример 2.
Предположим, требуется вычислить бисимметрическую булеву функцию
F(X1 , X 2 ) = ( x1x 2 ∨ x1x 3 ∨ x 2 x 3 ) ⋅ ( x 4 ∨ x 5 ∨ x 6 ) ∨ x1x 2 x 3 x 4 x 5 x 6 .
Так как
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ 0 ⊕ ( x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ) ⋅ 0 ⊕
⊕ ( x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ) ⋅ ( x 4 ∨ x 5 ∨ x 6 ) ⊕
⊕ x1x 2 x 3 ⋅ (( x 4 ∨ x 5 ∨ x 6 ) ⊕ x 4 x 5 x 6 ),
то π(G0) = π(G1) = (0,0,0,0), π(G2) = (1,1,1,0) и π(G3) = (1,1,1,1).
Если представить функцию F = F(X1, X2) формулой (2), то
F(X1, X2) = H0(X2) ⊕ (x1 ⊕ x2 ⊕ x3)⋅H1(X2) ⊕
⊕ (x1x2 ⊕ x1x3 ⊕ x2x3)⋅H2(X2) ⊕ x1x2x3⋅H3(X2),
где
π(H0) = π(G0) = (0,0,0,0),
π(H1) = π(G0) ⊕ π(G1) = (0,0,0,0) ⊕ (0,0,0,0) = (0,0,0,0),
π(H2) = π(G0) ⊕ π(G2) = (0,0,0,0) ⊕ (1,1,1,0) = (1,1,1,0) и
π(H3) = π(G0) ⊕ π(G1) ⊕ π(G2) ⊕ π(G3) =
= (0,0,0,0) ⊕ (0,0,0,0) ⊕ (1,1,1,0) ⊕ (1,1,1,1) = (0,0,0,1).
Если π(H0) = π(H1) = (0,0,0,0), π(H2) = (1,1,1,0) и π(H3) = (0,0,0,1), то из таблицы
настроек (таблица) получаем u0 = 0, u1 = 1, u2 = 1, u3 = 0, u4 = 1, u5 = 1, u6 = x6, u7 = 1, u8 = 0,
u9 = x6, u10 = 1 и u11 = 1.
Значит, для вычисления на выходе 35 устройства булевой функции F = F(X1, X2) необходимо на настроечные входы 23, 26, 31 подать значение "0", на настроечные входы 24,
25, 27, 28, 30, 33 и 34 - значение "1", на настроечные входы 29 и 32 - значение x6.
Если u0 = u3 = u8 = 0, u1 = u2 = u4 = u5 = u7 = u10 = u11 = 1 и u6 = u9 = x6, то первообразная
функция (4) заявляемого устройства принимает вид
6
BY 16242 C1 2012.08.30
F(xl, x2, x3, x4, x5, u0, u1,..., u11) = x4x5⋅0 ⊕ (x4 ∨ x5 ∨ 1) ⊕ 1 ⊕
⊕ (x1 ⊕ x2 ⊕ x3)⋅(x4x5⋅0 ⊕ (x4 ∨ x5 ∨ 1) ⊕ 1) ⊕
⊕(x1x2 ⊕ x1x3 ⊕ x2x3)⋅(x4x5x6 ⊕(x4 ∨ x5 ∨ 1) ⊕ 0) ⊕
⊕ x1x2x3⋅(x4x5x6 ⊕ (x4 ∨ x5 ∨ 1) ⊕ 1) =
= (x1x2 ⊕ x1x3 ⊕ x2x3)⋅(x4x5x6 ⊕ 1) ⊕ x1x2x3x4x5x6 =
= (x1x2 ∨ x1x3 ∨ x2x3)⋅( x 4 ∨ x 5 ∨ x 6 ) ∨ x1x2x3x4x5x6.
Пример 3
Допустим, на выходе 35 устройства требуется вычислить бисимметрическую булеву
функцию
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨
∨ x 1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 ⋅ x 6 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 ⋅ x 6 ,
которая в качестве примера была рассмотрена в [2].
Принимая во внимание формулу (1), нетрудно установить, что π(G0) = (0,0,0,1),
π(G1) = (0,0,0,0), π(G2) = (1,1,1,1) и π(G3) = (1,0,0,0).
Для симметрических булевых функций H0(X2),..., H3(X2) из разложения (2) с помощью
формул (3) получаем π(H0) = π(H1) = (0,0,0,1), π(H2) = (1,1,1,0) и π(H3) = (0,1,1,0).
Используя таблицу настроек (таблица), формируем вектор настройки устройства
на реализацию заданной бисимметрической функции шести переменных
u(F) = (x6, 1, 1, x6, 1, 1, x6, 1, 0, x6, x6, 0).
В таком случае для вычисления на выходе 35 устройства бисимметрической булевой
функции, приведенной в [2], необходимо на настроечные входы 23, 26, 29, 32 и 33 подать
значение переменной х6, на настроечные входы 24, 25, 27, 28 и 30 - значение "1", на
настроечные входы 31 и 34 - значение "0".
Основным достоинством заявляемого устройства для вычисления бисимметрических
булевых функций шести переменных является небольшое число внешних выводов, равное
18 (пять информационных и двенадцать настроечных входов, выход). Устройствопрототип имеет 23 внешних вывода (шесть информационных и шестнадцать настроечных
входов, выход).
Дополнительным достоинством устройства для вычисления бисимметрических булевых функций шести переменных является относительно небольшая конструктивная сложность (по числу входов логических элементов), равная 53. Сложность устройствапрототипа составляет 75 (при этом предполагается, что полный одноразрядный сумматор
содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом
два и его сложность равно 6).
Источники информации:
1. Патент РФ 2047894, МПК G 06F 7/00, 1995.
2. Патент РБ 8973, МПК G 06F 7/00, 2007 (прототип).
7
BY 16242 C1 2012.08.30
Двоичный код симметрической булевой функции
Hk = Hk(x4, x5, x6)
π(H k ) = (h 0k , h1k , h k2 , h 3k )
0000
0001
0010
u3k
0
x6
1
0011
x6
x6
x6
0100
0101
0110
0111
1000
1001
1010
x6
1
x6
0
0
x6
1
0
0
x6
x6
x6
x6
0
x6
x6
0
0
1
1
x6
1011
x6
0
x6
1100
x6
x6
x6
1101
1110
1111
1
x6
0
x6
1
1
x6
0
0
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
8
Вектор настройки
u(F) = (u0, u1,..., u11)
u3k+1
u3k+2
1
1
1
1
x6
x6
Документ
Категория
Без категории
Просмотров
0
Размер файла
200 Кб
Теги
by16242, патент
1/--страниц
Пожаловаться на содержимое документа