close

Вход

Забыли?

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

?

Патент BY11755

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 11755
(13) C1
(19)
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ АДДИТИВНО
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(54)
(21) Номер заявки: a 20060918
(22) 2006.09.20
(43) 2007.10.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович
(BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 5171 C1, 2003.
BY 7592 C1, 2005.
(57)
Устройство для вычисления аддитивно симметрических булевых функций n переменных, характеризующееся тем, что содержит мультиплексор, выход которого соединен с
выходом устройства, а t-й вход данных соединен с t-м настроечным входом устройства,
где t = 1, L + 1 ;
N
L = ∑ 2N −i ⋅ k i ;
i =1
BY 11755 C1 2009.04.30
N - количество кортежей переменных; 1 < N < n;
BY 11755 C1 2009.04.30
N
n = ∑ k i - количество переменных аддитивно симметрических булевых функций;
i=1
ki = 1, 2, 3,…;
i = 1, N ;
l−g
многооперандный двоичный сумматор, выход которого с весом 2 ,
где l = ]log2(L + 1)[;
g = 1, l ,
соединен с адресным входом мультиплексора с весом 2 l − g , a ji-й, где ji = 1, k i , вход с весом 2N-i соединен с ji-м входом i-й группы информационных входов устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных, содержащее n-входовый одноразрядный сумматор и (n + 1)-канальный мультиплексор [1]. Устройство реализует все 2n+1 симметрические булевы функции n переменных.
Недостатком устройства являются ограниченные функциональные возможности, поскольку оно не реализует аддитивно симметрические булевы функции (а.с.б.ф.).
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления бисимметрических булевых функций n переменных, содержащее два многовходовых одноразрядных сумматора и
мультиплексор [2]. Устройство реализует частично симметрические (в том числе и аддитивно симметрические) булевы функции n переменных, зависящие от двух кортежей попарно симметрических переменных.
Недостатком известного устройства также являются ограниченные функциональные
возможности, так как оно не реализует аддитивно симметрические булевы функции n переменных, зависящие от трех и более кортежей попарно симметрических переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления аддитивно симметрических булевых функций n переменных, зависящих от произвольного числа кортежей попарно симметрических переменных.
Названный технический результат достигается путем использования для построения
устройства многооперандного сумматора и мультиплексора, соединенных между собой по
специальной схеме.
Устройство для вычисления аддитивно симметрических булевых функций n переменных содержит мультиплексор, выход которого соединен с выходом устройства, а t-й вход
N
данных соединен с t-м настроечным входом устройства, где t = 1, L + 1; L = ∑ 2 N−i ⋅ k i ;
i =1
N
N - количество кортежей переменных; 1 < N < n; n = ∑ k i - количество переменных аддиi=1
тивно симметрических булевых функций;
ki = 1, 2, 3,…; i = 1, N .
Устройство содержит также многооперандный двоичный сумматор, выход которого с
весом 2l-g, где l = ]log2(L + 1)[; g = 1, l , соединен с адресным входом мультиплексора с весом 2l-g, а ji-й, где ji = 1, k i , вход с весом 2N-1 соединен с ji-м входом i-й группы информационных входов устройства.
На фигуре представлена схема устройства для вычисления аддитивно симметрических
булевых функций n переменных при n = 12 и k1 = 3, k2 = 5, k3 = 4 (N = 3).
2
BY 11755 C1 2009.04.30
Устройство содержит многооперандный двоичный сумматор 1, мультиплексор 2,
n = 12 информационных входов (k1 = 3 информационных входа 3, 4 и 5 первой группы,
k2 = 5 информационных входов 6-10 второй группы, k3 = 4 информационных входа 11-14
N
3
i =1
i =1
третьей группы), L + 1 = ∑ 2 N−i ⋅ k i + 1 = ∑ 23−i ⋅ k i + 1 = 27 настроечных входов 15-41 и один
выход 42.
Сумматор 1 выполняет сложение k1 = 3 одноразрядных двоичных чисел х1, х2 и х3 с
весом 22, k2 = 5 одноразрядных двоичных чисел х4-x8 с весом 21 и k3 = 4 одноразрядных
двоичных чисел х9-х12 с весом 20.
На l = ]log2(L + 1)[ = 5 выходах сумматора 1 формируется позиционный двоичный код
(r4, r3, r2, r1, r0) суммы
R = 4(х1 + х2 + х3) + 2(х4 + x5 + x6 + x7 + x8) + x9 + x10 + x11 + х12 = 16r4 + 8r3 + 4r2 + 2r1 + r0.
Мультиплексор 2 имеет l = ]log2(L + l)[ = 5 адресных входов и 2l= 25 входов данных (в
качестве настроечных входов устройства используются только первые L + l = 27 входов
данных мультиплексора).
Устройство (фигура) реализует 24k1 + 2k2 + k3 + 1 = 227 аддитивно симметрических булевых
функций n = 12 переменных при настройке сигналами из множества {0, 1}.
Поясним принцип построения и работы предлагаемого устройства для вычисления
а.с.б.ф. функций n переменных в общем случае.
Пусть f = f(X) - а.с.б.ф., зависящая от N кортежей попарно симметрических переменных Х1, Х2,…, XN,
где Х = (x1, х2,..., xn) = (Х1, Х2,…, XN);
X i = ( x1i , x i2 , K, x ik i ) ;
N
∑ k i = n , 1 < N < n.
i=1
Переменные кортежей Xi, i = 1, N , имеют вес, равный 2N-1, а значение а.с.б.ф. f = f(X)
на каждом данном наборе определяется суммой весов переменных, имеющих единичные
значения на данном наборе.
Локальным кодом а.с.б.ф. f = f(X) называется двоичный вектор S(f) = (s0, s1,…, sL), в
котором элемент sR равен значению f на наборах переменных из Х1, Х2,…, XN, удовлетворяющих условию:
N ki
R = ∑ ∑ x iji ⋅ 2 N − i ; 0 ≤ R ≤ L, ji = 1, k i ,
i =1 ji =1
N
где L = ∑ k i ⋅ 2 N−i .
i =1
Многооперандный сумматор выполняет сложение двоичных переменных кортежей
Х1, Х2,…, XN с учетом их весов и тем самым определяет класс эквивалентности R, к которому принадлежит данный набор значений переменных x1, х2,..., хn.
Код двоичного представления класса эквивалентности R = (r l-1 , r l-2 ,..., r0 ),
l = ]log2(L + 1)[, поступает на адресные входы мультиплексора и коммутирует к его выходу вход данных с номером R. Входы данных мультиплексора используются в качестве настроечных, на которые подаются элементы локального кода S(f) а.с.б.ф. f = f(X). Причем
на вход данных с номером R подается элемент sR локального кода S(f), 0 ≤ R ≤ L. На выходе мультиплексора реализуется значение а.с.б.ф. f = f(X) на наборе значений переменных из X, поступающих на входы многооперандного сумматора (эти входы являются
информационными входами устройства).
Таким образом, устройство реализует 2L+1 аддитивно симметрических булевых функций n переменных при настройке сигналами из множества {0, 1}.
3
BY 11755 C1 2009.04.30
Отметим, что длина L + 1 локального кода S(f) не превышает числа 2l входов данных
мультиплексора. Поэтому 2l - L - 1 входов данных мультиплексора не используются.
Устройство для вычисления аддитивно симметрических булевых функций при n = 12
и k1 = 3, k2 = 5, k3 = 4 (фигура) работает следующим образом.
На информационные входы 3, 4 и 5 первой группы подаются двоичные переменные х1, х2
и х3 кортежа Х1 (в произвольном порядке), на информационные входы 6-10 второй группы
- двоичные переменные х4-x8 кортежа Х2 (в произвольном порядке), на информационные
входы 11-14 третьей группы - двоичные переменные х9-х12 кортежа Х3 (в произвольном
порядке), на настроечные входы 15, 16, …, 41 - соответственно компоненты s0, s1, …, s26
локального кода S(f) а.с.б.ф. f = f(X) = (Х1, Х2, Х3), значения которой реализуются на выходе 42 устройства.
Достоинствами устройства являются простая конструкция и возможность вычисления
аддитивно симметрических булевых функций произвольного числа n переменных. При
этом для построения устройства используются стандартные функциональные устройства мультиплексор и двоичный сумматор.
Источники информации:
1. А.с. СССР 1833860, МПК G 06 F 7/00, 1993.
2. Патент РБ 5171, МПК G 06 F 7/00, 2003 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
179 Кб
Теги
by11755, патент
1/--страниц
Пожаловаться на содержимое документа