close

Вход

Забыли?

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

?

Патент BY15907

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.06.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 15907
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20100081
(22) 2010.01.22
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович;
Петроченко Андрей Сергеевич; Терешко Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 9147 C1, 2007.
BY 9051 С1, 2007.
BY a 20080777, 2008.
BY 15907 C1 2012.06.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций n
переменных, где n = 4, 5, 6,…, характеризующееся тем, что содержит n - k элементов И,
где k = ]log2(n + 1)[, и многовходовый одноразрядный сумматор, i-й вход которого, где
j-1
i = 1, n , соединен с i-м входом устройства, 2 -й выход которого, где j = 1, k , соединен с выходом многовходового одноразрядного сумматора, имеющим вес, равный 2j-1, l-й выход
устройства, где 3≤l≤n и l ≠ 2j-1, соединен с выходом соответствующего элемента И, входы
которого соединены с выходами многовходового одноразрядного сумматора, имеющими
веса, равные 2j-1, где lj-1 = 1, где (lk-1, lk-2,…,l0) - двоичное представление l.
BY 15907 C1 2012.06.30
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления полиномиальных симметрических булевых
функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов [1].
Недостатком устройства является ограниченное число переменных реализуемых полиномиальных симметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора,
двадцать четыре элемента И, пятнадцать элементов сложения по модулю два, восемь входов и восемь выходов [2].
Недостатком устройства также является ограниченное число переменных реализуемых полиномиальных симметрических булевых функций.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет реализации полиномиальных симметрических булевых функций,
зависящих от произвольного числа n переменных.
Названный технический результат достигается путем введения в состав устройства
многовходового одноразрядного сумматора и элементов И.
Устройство для вычисления полиномиальных симметрических булевых функций n
переменных, где n = 4, 5, 6, …, содержит n - k элементов И, где k = ]log2(n + l)[, и многовходовый одноразрядный сумматор, i-й вход которого, где i = 1, n , соединен с i-м входом
устройства.
В устройстве 2j-1-й выход, где j = 1, k , соединен с выходом многовходового одноразрядного сумматора, имеющим вес, равный 2j-1, а l-й выход, где 3≤l≤n и l≠2j-1, соединен с
выходом соответствующего элемента И, входы которого соединены с выходами многовходового одноразрядного сумматора, имеющими веса, равные 2j-1, где lj-1 = 1, где (lk-1, lk-2,
..., l0) - двоичное представление l.
На фигуре представлена схема устройства для вычисления полиномиальных симметрических булевых функций при n = 14.
Устройство содержит многовходовый одноразрядный сумматор 1, n - k = 10 элементов
И 2-11 (k = ]log2(n + l)[ = 4), n = 14 входов 12-25 и n = 14 выходов 26-39.
Булева функция F = F(X), X = (x1, x2,..., xn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. E in = E in (X) , i = 1, n , представимая в виде суммы по модулю два всевозможных
попарно различных элементарных конъюнкций только ранга i, составленных из переменных x1, x2,..., xn, называется полиномиальной.
В предлагаемом устройстве полиномиальные с.б.ф. n переменных формируются из
с.б.ф., реализуемых многовходовым (n-входовым) одноразрядным сумматором.
В общем случае такой сумматор выполняет сложение n одноразрядных двоичных чисел (с весом 20):
k
S = x1 + x 2 + K + x n = ∑ s j−1 ⋅ 2 j−1 ,
j=1
где sj-1∈{0,1} - значение с.б.ф. sj-1(X), X = (x1, x2,..., xn), реализуемой на выходе разряда
многовходового одноразрядного сумматора, имеющего вес, равный 2j-1, j = 1, k ,
k = ]log2(n + l)[.
Полиномиальные с.б.ф. E in = E in (X) могут быть получены из функций sj-1=sj-1(X),
j = 1, k согласно следующему соотношению:
2
BY 15907 C1 2012.06.30
E in (X) =
^
i j−1 =1
s j−1 (X) ,
(1)
где (ik-1, ik-2, …, i0) - двоичное представление i, i = 1, n .
Как непосредственно следует из (1), k полиномиальных с.б.ф. совпадают с соответствующими функциями многовходового одноразрядного сумматора, а именно:
j−1
E 2n (X ) = s j −1 ( X) , j = 1, k .
Предлагаемое устройство построено в точном соответствии с выражением (1).
Пример
i
i
При n = 14 согласно (1) выражения для полиномиальных с.б.ф. E14
= E14
(X) , i = 1, 14 ,
примут вид:

E114 (X) = s 0 (X);

2
E14
(X) = s1 (X);


3
E14 (X) = s1 (X) ⋅ s 0 (X);

4

E14 (X) = s 2 (X);

5
E14
(X) = s 2 (X) ⋅ s 0 (X);


6
E14 (X) = s 2 (X) ⋅ s1 (X);

(2)
7
E14 (X) = s 2 (X) ⋅ s1 (X) ⋅ s 0 (X); 

8
E14
(X) = s 3 (X);


9
E14 (X) = s 3 (X) ⋅ s 0 (X);

10

E14 (X) = s 3 (X) ⋅ s1 (X);

E11
14 ( X ) = s 3 ( X ) ⋅ s1 (X ) ⋅ s 0 ( X ); 

E12
14 ( X ) = s 3 ( X ) ⋅ s 2 ( X );


E13
(
X
)
s
(
X
)
s
(
X
)
s
(
X
);
=
⋅
⋅
14
3
2
0


E14
(
X
)
s
(
X
)
s
(
X
)
s
(
X
).
=
⋅
⋅
14
3
2
1
Схема устройства при n = 14 (фигура) построена согласно (2).
Устройство для вычисления полиномиальных симметрических булевых функций при
n = 14 (фигура) работает следующим образом.
На входы 12-25 поступают (в произвольном порядке) двоичные переменные xl - x14. На
2
выходах 26, 27,..., 39 реализуются соответственно полиномиальные с.б.ф. E114 (X) , E14
(X) ,
14
…, E14 (X) , X = (x1, x2, …, x14).
Достоинствами устройства для вычисления полиномиальных симметрических булевых функций n переменных являются высокое быстродействие, простая конструкция и
широкие функциональные возможности.
Источники информации:
1. Патент РБ 9051, МПК G 06F 7/00 // Бюл. № 2 (55). - 30.04.2007.
2. Патент РБ 9147, МПК G 06F 7/00 // Бюл. № 2 (55). - 30.04.2007 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
3
Документ
Категория
Без категории
Просмотров
0
Размер файла
74 Кб
Теги
by15907, патент
1/--страниц
Пожаловаться на содержимое документа