close

Вход

Забыли?

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

?

Патент BY13056

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.04.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13056
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
АДДИТИВНО БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20080351
(22) 2008.03.25
(43) 2008.10.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Терешко Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 9051 C1, 2007.
RU 2310902 C1, 2007.
SU 1559338 A1, 1990.
BY 13056 C1 2010.04.30
(57)
Устройство для вычисления полиномиальных аддитивно бисимметрических булевых
функций, содержащее два одноразрядных двоичных сумматора, элементы сложения по
модулю два с первого по шестой и одиннадцать элементов И, выход первого из которых
BY 13056 C1 2010.04.30
соединен с первым выходом устройства, (i + 1)-й выход которого, где i = 1, 5 , соединен с
выходом i-го элемента сложения по модулю два, a j-й вход k-й группы входов, где j = 1, 2,
3, k = 1, 2, соединен с j-м входом k-го одноразрядного двоичного сумматора, выход суммы
первого одноразрядного двоичного сумматора соединен с первым входом первого элемента сложения по модулю два и первым входом (j + 1)-го элемента И, выход которого соединен с первым входом (j + 1)-го элемента сложения по модулю два, выход переноса
первого одноразрядного двоичного сумматора соединен с первым входом пятого элемента
И, выход которого соединен с первым входом пятого элемента сложения по модулю два,
выход суммы второго одноразрядного двоичного сумматора соединен со вторым входом
второго элемента И, вторым входом четвертого элемента И и вторым входом пятого элемента И, выход переноса второго одноразрядного двоичного сумматора соединен со вторым входом третьего элемента И, третьим входом четвертого элемента И и третьим
входом пятого элемента И, выход шестого элемента сложения по модулю два соединен с
седьмым выходом устройства, восьмой выход которого соединен с выходом суммы второго одноразрядного двоичного сумматора и первым входом (j + 5)-го элемента И, девятый
выход устройства соединен с выходом девятого элемента И, первый вход которого соединен с выходом переноса второго одноразрядного двоичного сумматора, вторым входом
первого элемента сложения по модулю два, вторым входом шестого элемента И и первым
входом десятого элемента И, второй вход которого соединен с выходом переноса первого
одноразрядного двоичного сумматора, вторым входом третьего элемента сложения по модулю два, вторым входом седьмого элемента И, вторым входом восьмого элемента И и
первым входом одиннадцатого элемента И, второй вход которого соединен с выходом
суммы первого одноразрядного двоичного сумматора и третьим входом восьмого элемента И, выход которого соединен со вторым входом пятого элемента сложения по модулю
два, выход шестого элемента И соединен со вторым входом второго элемента сложения по
модулю два и первым входом первого элемента И, второй вход которого соединен со вторым входом девятого элемента И, выходом одиннадцатого элемента И и первым входом
шестого элемента сложения по модулю два, второй вход которого соединен с выходом
десятого элемента И, выход седьмого элемента И соединен со вторым входом четвертого
элемента сложения по модулю два.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора, двадцать четыре элемента И,
пятнадцать элементов сложения по модулю два, восемь входов и восемь выходов [1].
Недостатками устройства являются низкое быстродействие, обусловленное большой
глубиной схемы, а также невозможность вычисления полиномиальных аддитивно бисимметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два,
шесть входов и шесть выходов [2].
Недостатком устройства является невозможность вычисления полиномиальных аддитивно бисимметрических булевых функций.
Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных аддитивно бисимметрических булевых функций,
зависящих от двух кортежей попарно симметрических переменных.
2
BY 13056 C1 2010.04.30
Названный технический результат достигается путем введения в состав устройства
шестого элемента сложения по модулю два, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления полиномиальных аддитивно бисимметрических булевых
функций содержит два одноразрядных двоичных сумматора, элементы сложения по модулю два с первого по пятый и одиннадцать элементов И, выход первого из которых соединен с первым выходом устройства.
В устройстве (i + 1)-й выход, где i = 1, 5, соединен с выходом i-го элемента сложения
по модулю два, а j-й вход k-й группы входов, где j = 1, 2, 3; k = 1, 2, соединен с j-м входом
k-го одноразрядного двоичного сумматора.
Выход суммы первого одноразрядного двоичного сумматора соединен с первым входом первого элемента сложения по модулю два и первым входом (j + 1)-го элемента И,
выход которого соединен с первым входом (j + 1)-го элемента сложения по модулю два.
Выход переноса первого одноразрядного двоичного сумматора соединен с первым
входом пятого элемента И, выход которого соединен с первым входом пятого элемента
сложения по модулю два.
Выход суммы второго одноразрядного двоичного сумматора соединен со вторым входом второго элемента И, вторым входом четвертого элемента И и вторым входом пятого
элемента И.
Выход переноса второго одноразрядного двоичного сумматора соединен со вторым
входом третьего элемента И, третьим входом четвертого элемента И и третьим входом пятого элемента И.
Устройство содержит шестой элемент сложения по модулю два, выход которого соединен с седьмым выходом устройства, восьмой выход которого соединен с выходом
суммы второго одноразрядного двоичного сумматора и первым входом (j + 5)-го элемента
И.
Девятый выход устройства соединен с выходом девятого элемента И, первый вход которого соединен с выходом переноса второго одноразрядного двоичного сумматора, вторым входом первого элемента сложения по модулю два, вторым входом шестого элемента
И и первым входом десятого элемента И.
Второй вход десятого элемента И соединен с выходом переноса первого одноразрядного двоичного сумматора, вторым входом третьего элемента сложения по модулю два,
вторым входом седьмого элемента И, вторым входом восьмого элемента И и первым входом одиннадцатого элемента И.
Второй вход одиннадцатого элемента И соединен с выходом суммы первого одноразрядного двоичного сумматора и третьим входом восьмого элемента И, выход которого
соединен со вторым входом пятого элемента сложения по модулю два.
Выход шестого элемента И соединен со вторым входом второго элемента сложения по
модулю два и первым входом первого элемента И, второй вход которого соединен со вторым входом девятого элемента И, выходом одиннадцатого элемента И и первым входом
шестого элемента сложения по модулю два, второй вход которого соединен с выходом
десятого элемента И.
Выход седьмого элемента И соединен со вторым входом четвертого элемента сложения по модулю два.
На фигуре представлена схема устройства для вычисления полиномиальных аддитивно бисимметрических булевых функций.
Устройство содержит два одноразрядных двоичных сумматора 1 и 2, одиннадцать элементов И 3-13, шесть элементов сложения по модулю два 14-19, три входа первой группы
20, 21 и 22, три входа второй группы 23, 24 и 25 и девять выходов 26-34.
Предлагаемое устройство предназначено для одновременного вычисления девяти полиномиальных аддитивно бисимметрических булевых функций (а.б.с.б.ф.) Ek = Ek(X) =
3
BY 13056 C1 2010.04.30
Ek(X1, X2), k = 1, 9, зависящих от двух кортежей X1 = (x1, x2, x3) и X2 = (x4, x5, x6) попарно
симметрических переменных.
При этом произвольная а.б.с.б.ф. f = f(X) = f(X1, X2), зависящая от кортежей X1 = (x1,
x2, x3) и X2 = (x4, x5, x6), может быть однозначно представлена в виде положительно поляризованного полиномиального разложения вида:
f = f(X) = γ0 ⊕ E1(X) ⋅ γ1 ⊕ E2(X) ⋅ γ2 ⊕ E3(X) ⋅ γ3 ⊕ E4(X) ⋅ γ4 ⊕
(1)
⊕ E5(X) ⋅ γ5 ⊕ E6(X) ⋅ γ6 ⊕ E7(X) ⋅ γ7 ⊕ E8(X) ⋅ γ8 ⊕ E9(X) ⋅ γ9 ,
где Ek = Ek(X) = Ek(X1, X2) - полиномиальные а.б.с.б.ф., k = 1, 9 ;
γ1 ∈ {0, 1}, l = 0, 9, - коэффициенты полиномиального разложения.
Таким образом, а.б.с.б.ф. f = f(X) = f(X1, X2) может быть однозначно определена суммой по модулю два полиномиальных а.б.с.б.ф. согласно (1).
Отметим, что переменные кортежа X1 имеют вес, равный 21, переменные кортежа X2 вес, равный 20, а значение а.б.с.б.ф. f = f(X) = f(X1, X2) на каждом данном наборе переменных из X определяется суммой весов переменных, имеющих единичные значения.
Полиномиальные а.б.с.б.ф. Ek = Ek(X) = Ek(X1, X2), k = 1, 9, могут быть получены посредством полиномиальных симметрических булевых функций (с.б.ф.), зависящих от кортежей X1 и X2 попарно симметрических переменных:
E k = E k (X) = E k (X1 , X 2 ) =
∑ ⊕ E i3 (X1 ) ⋅ E 3j (X 2 ),
0≤i≤3
0 ≤ j≤ 3
2i + j = k
(2)
где E i3 (X1 ), E 3j (X 2 ), i = 0, 3, j = 0, 3, - полиномиальные с.б.ф. и E 30 (X1 ) ≡ 1, E 30 (X 2 ) ≡ 1.
В соответствии с (2) выражения для полиномиальных а.б.с.б.ф. Ek = Ek(X) = Ek(X1, X2),
k = 1, 9, примут вид:
E1 (X ) = E1 (X1 , X 2 ) = E13 (X 2 );
E 2 (X ) = E 2 (X1 , X 2 ) = E13 (X1 ) ⊕ E 32 (X 2 );
E 3 (X ) = E 3 (X1 , X 2 ) = E13 (X1 ) ⋅ E13 (X 2 ) ⊕ E 33 (X 2 );
E 4 (X ) = E 4 (X1 , X 2 ) = E13 (X1 ) ⋅ E 32 (X 2 ) ⊕ E 32 (X1 );
E 5 (X ) = E 5 (X1 , X 2 ) = E13 (X1 ) ⋅ E 33 (X 2 ) ⊕ E 32 (X1 ) ⋅ E13 (X 2 );
E 6 (X ) = E 6 (X1 , X 2 ) = E 32 (X1 ) ⋅ E 32 (X 2 ) ⊕ E 33 (X1 );
E 7 (X ) = E 7 (X1 , X 2 ) = E 32 (X1 ) ⋅ E 33 (X 2 ) ⊕ E 33 (X1 ) ⋅ E13 (X 2 );
E 8 (X ) = E 8 (X1 , X 2 ) = E 33 (X1 ) ⋅ E 32 (X 2 );
E 9 (X ) = E 9 (X1 , X 2 ) = E 33 (X1 ) ⋅ E 33 (X 2 ),
где
E13 (X1 ) = x1 ⊕ x 2 ⊕ x 3 ;
E 32 (X1 ) = x1x 2 ⊕ x1x 3 ⊕ x 2 x 3 = x1x 2 ∨ x1x 3 ∨ x 2 x 3 ;
E 33 (X1 ) = x1x 2 x 3 ;
E13 (X 2 ) = x 4 ⊕ x 5 ⊕ x 6 ;
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 ;
E 33 (X 2 ) = x 4 x 5 x 6 .
Заметим также, что E 33 (X1 ) = E13 (X1 ) ⋅ E 32 (X1 ) и E 33 (X 2 ) = E13 (X 2 ) ⋅ E 32 (X 2 ).
4
BY 13056 C1 2010.04.30
При этом функции E13 (X i ) = s i и E 32 (X i ) = p i , i ∈ {1, 2}, могут быть реализованы соответственно на выходе суммы и выходе переноса одноразрядного двоичного сумматора, на
вход которого поступают переменные из Xi.
Тогда можно записать:
E1 (X ) = s 2 ;


E 2 (X ) = s1 ⊕ p 2 ;


E 3 (X ) = s1 ⋅ s 2 ⊕ s 2 ⋅ p 2 ;

E 4 (X ) = s1 ⋅ p 2 ⊕ p1 ;


E 5 (X ) = s1 ⋅ s 2 ⋅ p 2 ⊕ s 2 ⋅ p1 ; 
(3)

E 6 (X ) = p1 ⋅ p 2 ⊕ s1 ⋅ p1;

E 7 (X ) = s 2 ⋅ p1 ⋅ p 2 ⊕ s1 ⋅ s 2 ⋅ p1 ;

E 8 (X ) = s1 ⋅ p1 ⋅ p 2 ;


E 9 (X ) = (s1 ⋅ p1 ) ⋅ (s 2 ⋅ p 2 ).
Предлагаемое устройство (фигура) построено в соответствии с (3).
Устройство работает следующим образом.
На входы 20, 21 и 22 первой группы поступают (в произвольном порядке) переменные
x1, x2 и x3 первого кортежа X1, на входы 23, 24 и 25 второй группы - (в произвольном порядке) переменные x4, x5 и x6 второго кортежа X2.
На выходах 26, 27,…, 34 реализуются соответственно значения полиномиальных аддитивно бисимметрических булевых функций E1(X), E2(X) ,…, E9(X) на данном наборе
переменных из X = (X1, X2).
Ниже приведена таблица работы предлагаемого устройства для вычисления полиномиальных бисимметрических булевых функций, устанавливающая связь между суммой
весов переменных, имеющих единичные значения на данном наборе переменных из
X = (X1, X2), и вектором выходных сигналов устройства.
Достоинствами устройства для вычисления полиномиальных аддитивно бисимметрических булевых функций являются высокое быстродействие, простая конструкция, широкие функциональные возможности.
Значения функций на выходах устройства
3
R = ∑ (2x i + x i + 3 )
i =1
Входы
20-25
0
1
2
3
4
5
6
7
8
9
E1(X)
E2(X)
E3(X)
E4(X)
E5(X)
E6(X)
E7(X)
E8(X)
E9(X)
26
27
28
29
30
31
32
33
34
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
5
BY 13056 C1 2010.04.30
Источники информации:
1. Патент РБ 9147, МПК G 06F 7/00, 2007.
2. Патент РБ 9051, МПК G 06F 7/00, 2007.
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
179 Кб
Теги
by13056, патент
1/--страниц
Пожаловаться на содержимое документа