close

Вход

Забыли?

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

?

Патент BY9051

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 9051
(13) C1
(19)
(46) 2007.04.30
(12)
7
(51) G 06F 7/00
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20041025
(22) 2004.11.09
(43) 2005.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 5314 C1, 2003.
BY 3031 C1, 1999.
SU 1559338 A1, 1990.
SU 1441379 A2, 1988.
SU 1444743 A1, 1988.
SU 1550507 A1, 1990.
US 4163211, 1979.
WO 91/20027 A1.
BY 9051 C1 2007.04.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элементы сложения по модулю два с первого по третий и элементы И с первого
по седьмой, причем выход первого элемента И соединен с первым выходом устройства,
Фиг. 1
BY 9051 C1 2007.04.30
отличающееся тем, что содержит четвертый и пятый элементы сложения по модулю два,
элементы И с восьмого по одиннадцатый и два одноразрядных двоичных сумматора, i-й
вход первого из которых (i = 1,2,3) соединен с i-м входом устройства, (i + 3)-й вход которого соединен с i-м входом второго одноразрядного двоичного сумматора, выход суммы
которого соединен с первым входом первого элемента И, первым входом второго элемента И, первым входом третьего элемента И, первым входом четвертого элемента И, первым
входом пятого элемента И, первым входом шестого элемента И, первым входом седьмого
элемента И и первым входом первого элемента сложения по модулю два, выход которого
соединен со вторым выходом устройства, а второй вход соединен со вторым входом первого элемента И, вторым входом третьего элемента И, вторым входом четвертого элемента И, вторым входом седьмого элемента И, первым входом восьмого элемента И, первым
входом девятого элемента И, первым входом десятого элемента И и выходом суммы первого одноразрядного двоичного сумматора, выход переноса которого соединен с первым
входом второго элемента сложения по модулю два, первым входом одиннадцатого элемента И, вторым входом второго элемента И, вторым входом шестого элемента И, вторым
входом восьмого элемента И, вторым входом десятого элемента И, третьим входом четвертого элемента И и третьим входом первого элемента И, четвертый вход которого
соединен с выходом переноса второго одноразрядного двоичного сумматора, вторым входом пятого элемента И, вторым входом девятого элемента И, вторым входом одиннадцатого элемента И, третьим входом второго элемента И, третьим входом третьего элемента
И, третьим входом десятого элемента И и вторым входом второго элемента сложения по
модулю два, третий вход которого соединен с выходом седьмого элемента И, а выход соединен с третьим выходом устройства, четвертый выход которого соединен с выходом
третьего элемента сложения по модулю два, первый вход которого соединен с выходом
пятого элемента И, второй вход соединен с выходом шестого элемента И, третий вход соединен с выходом восьмого элемента И, четвертый вход соединен с выходом девятого
элемента И, пятый выход устройства соединен с выходом четвертого элемента сложения
по модулю два, первый вход которого соединен с выходом третьего элемента И, второй
вход соединен с выходом четвертого элемента И, третий вход соединен с выходом одиннадцатого элемента И, шестой выход устройства соединен с выходом пятого элемента
сложения по модулю два, первый вход которого соединен с выходом второго элемента И,
второй вход соединен с выходом десятого элемента И.
Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления полиномиальных симметрических булевых функций шести переменных.
Известно устройство для вычисления фундаментальных симметрических булевых
функций n переменных (многовходовый логический модуль), содержащее n групп элементов 2-2И-2ИЛИ, n элементов НЕ и 2n-2 элементов И [1].
Недостатками устройства являются низкое быстродействие и невозможность вычисления полиномиальных симметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления веса двоичных кодовых
комбинаций, которое при n = 6 содержит три элемента ИЛИ-НЕ, три элемента сложения
по модулю, семь элементов И, четыре элемента 2-2И-2ИЛИ и четыре элемента 3-2И3ИЛИ [2].
Недостатком устройства также является невозможность вычисления полиномиальных
симметрических булевых функций.
Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных симметрических булевых функций шести переменных.
2
BY 9051 C1 2007.04.30
Названный технический результат достигается путем использования новых элементов,
а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления полиномиальных симметрических булевых функций, содержит элементы сложения по модулю два с первого по третий и элементы И с первого по
седьмой, причем выход первого элемента И соединен с первым выходом устройства.
В отличие от прототипа, устройство содержит четвертый и пятый элементы сложения
по модулю два, элементы И с восьмого по одиннадцатый и два одноразрядных двоичных
сумматора, i-й вход первого из которых (i = 1, 2,3) соединен с i-м входом устройства,
(i + 3) -й вход которого соединен с i-м входом второго одноразрядного двоичного сумматора. Выход суммы второго одноразрядного двоичного сумматора соединен с первым
входом первого элемента И, первым входом второго элемента И, первым входом третьего
элемента И, первым входом четвертого элемента И, первым входом пятого элемента И,
первым входом шестого элемента И, первым входом седьмого элемента И и первым входом первого элемента сложения по модулю два. Выход первого элемента сложения по модулю два соединен со вторым выходом устройства, а второй вход соединен со вторым
входом первого элемента И, вторым входом третьего элемента И, вторым входом четвертого элемента И, вторым входом седьмого элемента И, первым входом восьмого элемента
И, первым входом девятого элемента И, первым входом десятого элемента И и выходом
суммы первого одноразрядного двоичного сумматора. Выход переноса первого одноразрядного двоичного сумматора соединен с первым входом второго элемента сложения по
модулю два, первым входом одиннадцатого элемента И, вторым входом второго элемента
И, вторым входом шестого элемента И, вторым входом восьмого элемента И, вторым входом десятого элемента И, третьим входом четвертого элемента И и третьим входом первого элемента И. Четвертый вход первого элемента И соединен с выходом переноса второго
одноразрядного двоичного сумматора, вторым входом пятого элемента И, вторым входом
девятого элемента И, вторым входом одиннадцатого элемента И, третьим входом второго
элемента И, третьим входом третьего элемента И, третьим входом десятого элемента И и
вторым входом второго элемента сложения по модулю два, третий вход которого соединен с выходом седьмого элемента И, а выход соединен с третьим выходом устройства.
Четвертый выход устройства соединен с выходом третьего элемента сложения по модулю
два, первый вход которого соединен с выходом пятого элемента И, второй вход соединен
с выходом шестого элемента И, третий вход соединен с выходом восьмого элемента И,
четвертый вход соединен с выходом девятого элемента И. Пятый выход устройства соединен с выходом четвертого элемента сложения по модулю два, первый вход которого
соединен с выходом третьего элемента И, второй вход соединен с выходом четвертого
элемента И, третий вход соединен с выходом одиннадцатого элемента И. Шестой выход
устройства соединен с выходом пятого элемента сложения по модулю два, первый вход
которого соединен с выходом второго элемента И, второй вход соединен с выходом десятого элемента И.
На фиг. 1 представлена схема устройства для вычисления полиномиальных симметрических булевых функций.
Устройство содержит два одноразрядных двоичных сумматора 1 и 2, одиннадцать элементов И 3-13, пять элементов сложения по модулю два 14-18, шесть входов 19-24 и
шесть выходов 25-30.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций.
Обозначим: G sh = (h , h ,..., h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0,1}, и G 0h ≡ ∅.
Булева функция F = F(X), X = (x1, x2, ..., xn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
3
BY 9051 C1 2007.04.30
С.б.ф. F однозначно определяется своим локальным кодом π(F) = (π0, π1, ..., πn), где
πi = F(G1i , G 0n − i ), 0 ≤ i ≤ n .
С.б.ф. Fni =F ni (X), 0 ≤ i ≤ n , называется фундаментальной (ф.с.б.ф.), если
1, если x1 + x 2 + ... + x n = i;
Fni = Fni (X) =
0, если x1 + x 2 + ... + x n ≠ i; 0 ≤ i ≤ n.
Очевидно, что в локальном коде π(Fni ) ф.с.б.ф. Fni только один элемент πi = 1 (все остальные элементы πj = 0, 0≤j≤n, j≠i).
Пример 1. При n = 4 имеет место:
π(F40 ) = (1,0,0,0,0); π(F41 ) = (0,1,0,0,0); π(F42 ) = (0,0,1,0,0);
π(F43 ) = (0,0,0,1,0); π(F44 ) = (0,0,0,0,1) и
F40 = x1 x 2 x 3 x 4 ; F41 = x1 x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ∨ x1 x 2 x 3 x 4 ∨ x1 x 2 x 3x 4 ;
F42 = x1x 2 x 3 x 4 ∨ x1 x 2 x 3 x 4 ∨ x1 x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ∨ x1 x 2 x 3 x 4 ;
F43 = x1x 2 x 3 x 4 ∨ x1 x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ; F44 = x1x 2 x 3 x 4 ;
Произвольная с.б.ф. F = F(X) от n переменных может быть представлена в виде дизъюнктивного разложения посредством ф.с.б.ф:
n
F = F(X) = ∨ πi ⋅ Fni (X).
i =0
(1)
С.б.ф. E nj = E nj (X), 1 ≤ j ≤ n , представимая в виде суммы по модулю два всевозможных
попарно различных элементарных конъюнкций ранга j, составленных из переменных
(х1, х2, ..., хn), называется полиномиальной с.б.ф. (п.с.б.ф.).
Произвольная с.б.ф. F = F(X) от n переменных может быть однозначно представлена в
виде положительно поляризованного полиномиального разложения (полинома Жегалкина) посредством п. с.б.ф. E nj :
n
F = F(X) = γ 0 ⊕ ∑ ⊕ γ j ⋅ E nj (X),
j =1
(2)
где γ(F) = (γ0, γ1, …, γn) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. F.
Вектор γ(F) может быть получен из локального кода π(F) методом "треугольника" [3].
Очевидно, что в векторе γ (E nj ) коэффициентов полинома Жегалкина п. с.б.ф. E nj
только один элемент γj = 1.
Пример 2. При n = 4 имеет место:
γ (E14 ) = (0,1,0,0,0), γ (E 24 ) = (0,0,1,0,0), γ (E 34 ) = (0,0,0,1,0), γ (E 44 ) = (0,0,0,0,1) и
E14 = x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ; E 24 = x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ;
E34 = x1x 2 x 3 ⊕ x1x 3x 4 ⊕ x1x 2 x 4 ⊕ x 2 x 3x 4 ; E 44 = x1x 2 x 3x 4 .
Таким образом, как следует из (1) и (2), произвольная с.б.ф. F = F(X) от n переменных
может быть однозначно представлена в виде дизъюнкции фундаментальных с.б.ф. или
суммы по модулю два полиномиальных с.б.ф.
Пример 3. Пусть с.б.ф. F - F(X), X = (х1,х2,х3,х4) представлена в виде:
F = ( x 1 x 2 ∨ x 1 x 2 ) x 3 x 4 ∨ x 1 x 2 ( x 3 x 4 ∨ x 3 x 4 ) ∨ x 1 x 2 x 3 ∨ x 1 x 3 x 4 ∨ x1 x 2 x 4 ∨ x 2 x 3 x 4 .
Очевидно, что локальный код π(F) = (0,1,0,1,1). Из π(F) методом "треугольника" может быть найден вектор γ(F) = (0,1,0,0,1). Тогда согласно (1) и (2) можно записать:
F = F41 ∨ F43 ∨ F44 = E14 ⊕ E 44 .
Обозначим: X = (Xl,X2), Xl = (x1,x2,...,xk), X2 = (xk+1,xk+2,...,xn), 1≤k<n.
4
BY 9051 C1 2007.04.30
Полиномиальная с.б.ф. E nj = E nj (X) , 1≤j≤n, допускает декомпозиционное разложение
вида:
k
E nj (X) = E nj (X1, X 2 ) = ∑ ⊕ E kj (X1 ) ⋅ E nj−−ik (X 2 ),
(3)
i =0
где E 0n (X) ≡ 1, E nt (X) ≡ 0 при t < 0 и t > n.
Предлагаемое устройство предназначено для одновременного вычисления всех n = 6
полиномиальных с.б.ф. E 6j = E 6j (X), Х = (x1 , x 2 , x 3 , x 4 , x 5 , x 6 ), j = 1,6 , зависящих от шести
переменных, и построено на основе разложения (3) при k = 3.
Пусть Х1 = (х1,х2,х3), Х2 = (х4,х5,х6) и Х = (Х1,Х2).
Тогда согласно (3) имеем:
E16 (X) = E13 (X1 ) ⊕ E13 (X 2 ); E 62 (X) = E32 (X1 ) ⊕ E13 (X1 ) ⋅ E13 (X 2 ) ⊕ E 32 (X 2 );
E 36 (X) = E 33 (X1 ) ⊕ E32 (X1 ) ⋅ E13 (X 2 ) ⊕ E13 (X1 ) ⋅ E32 (X 2 ) ⊕ E33 (X 2 );
E 64 (X) = E 33 (X1 ) ⋅ E13 (X 2 ) ⊕ E 32 (X1 ) ⋅ E 32 (X 2 ) ⊕ E13 (X1 ) ⋅ E 33 (X 2 );
E 56 (X) = E 33 (X1 ) ⋅ E 32 (X 2 ) ⊕ E 32 (X1 ) ⋅ E 33 (X 2 ); E 66 (X) = E33 (X1 ) ⊕ E33 (X 2 ).
Заметим, что E 33 (X1 ) = E13 (X1 ) ⋅ E 32 (X1 ) и E 33 (X 2 ) = E13 (X 2 ) ⋅ E 32 (X 2 ) .
Введем обозначения:
s1 = E13 (X1 ) = x1 ⊕ x 2 ⊕ x 3 , p1 = E 32 (X1 ) = x1x 2 ⊕ x1x 3 ⊕ x 2 x 3 = x1x 2 ∨ x1x 3 ∨ x 2 x 3 ,
s 2 = E13 (X 2 ) = x 4 ⊕ x 5 ⊕ x 6 , p 2 = E 32 (X 2 ) = x 4 x 5 ⊕ x 4 x 6 ⊕ x 5 x 6 = x 4 x 5 ∨ x 4 x 6 ∨ x 5 x 6 .
Следовательно,

E16 (X) = s1 ⊕ s 2 ;


E 62 (X) = p1 ⊕ s1s 2 ⊕ p 2 ;

E 36 (X) = s1p1 ⊕ s 2 p1 ⊕ s1p 2 ⊕ s 2 p 2 ;
(4)

E 64 (X) = s1s 2 p1 ⊕ p1p 2 ⊕ s1s 2 p 2 ; 

E 56 (X) = s1p1p 2 ⊕ s 2 p1p 2 ;


6
E 6 (X) = s1s 2 p1p 2 .

Заметим, что функции E13 (X i ) = s i и E 32 (X i ) = p i , i∈{1, 2} могут быть реализованы соответственно на выходах суммы и переноса одноразрядного двоичного сумматора, на
вход которого поступают переменные из Xi.
Предлагаемое устройство для вычисления п.с.б.ф. построено в соответствии с соотношениями (4).
Устройство работает следующим образом. На входы 19-24 поступают (в произвольном порядке) двоичные переменные x1-x6. На выходах 25-30 реализуются соответственно
полиномиальные с.б.ф. E16 (X) − E 66 (X), X = ( x1 , x 2 ,..., x 6 ) .
Векторы коэффициентов полинома Жегалкина п.с.б.ф. E 6j (X), j = 1,6 , шести переменных имеют вид:
γ (E16 (X)) = (0,1,0,0,0,0,0), γ (E 62 (X)) = (0,0,1,0,0,0,0), γ (E 36 (X)) = (0,0,0,1,0,0,0),
γ (E 64 (X)) = (0,0,0,0,1,0,0), γ (E 56 (X)) = (0,0,0,0,0,1,0), γ (E 66 (X)) = (0,0,0,0,0,0,1).
Методом "треугольника" найдем их локальные коды:
5
BY 9051 C1 2007.04.30
π(E16 (X)) = (0,1,0,1,0,1,0), π(E 62 (X)) = (0,0,1,1,0,0,1), π(E 36 (X)) = (0,0,0,1,0,0,0),
π(E 64 (X)) = (0,0,0,0,1,1,1), π(E56 (X)) = (0,0,0,0,0,1,0), π(E 66 (X)) = (0,0,0,0,0,0,1).
Из локальных кодов π(E 6j (X)) может быть построена таблица (фиг. 2), устанавливающая связь между весом (числом единиц) входной двоичной кодовой комбинации и
вектором выходных сигналов устройства.
Достоинствами устройства для вычисления полиномиальных симметрических булевых функций является высокое быстродействие, простая конструкция, широкие функциональные возможности.
Источники информации:
1. А.с. СССР 1793547, МПК Н 03 М 7/22, 1993.
2. Патент РБ 5314, МПК G 06 F 7/00, 7/22, 2003 (прототип).
3. Супрун В.П. Полиномиальное разложение симметрических булевых функций // Известия АН СССР. Техническая кибернетика. - 1985. - № 4. - С. 123-127.
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
126 Кб
Теги
by9051, патент
1/--страниц
Пожаловаться на содержимое документа