close

Вход

Забыли?

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

?

Патент BY13240

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.06.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13240
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20080356
(22) 2008.03.25
(43) 2008.10.30
(71) Заявитель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 7592 C1, 2005.
BY 8973 C1, 2007.
BY 3300 C1, 2000.
SU 1683001 A1, 1991.
JP 2001034598 A, 2001.
(57)
Устройство для вычисления бисимметрических булевых функций n переменных, содержащее m + 1 группу элементов И, где m = 1, 2, 3…, причем первая группа содержит nm элементов И, где n > m, (i + 1)-я группа, где (i = 1, m) , содержит p элементов И, где p = n
- m + 1, первый вход j-го элемента И первой группы, где j = 1, n − m , соединен с j-м на-
BY 13240 C1 2010.06.30
строечным входом устройства, первый вход k-го элемента И (i + 1)-й группы, где k = 1, p ,
Фиг. 1
BY 13240 C1 2010.06.30
соединен с (i ⋅ p + k - 1)-м настроечным входом устройства, а также два блока вычисления
полиномиальных симметрических булевых функций и элемент сложения по модулю два,
выход которого соединен с выходом устройства, а первый вход соединен с p ⋅ (m + 1)-м
настроечным входом устройства, выход j-го элемента И первой группы соединен с (j + 1)м входом элемента сложения по модулю два, выход k-го элемента И (i + 1)-й группы соединен с (i ⋅ p + k)-м входом элемента сложения по модулю два, i-й вход первой группы
информационных входов устройства соединен с i-м входом первого блока вычисления полиномиальных симметрических булевых функций, j-й вход второй группы информационных входов устройства соединен с j-м входом второго блока вычисления полиномиальных
симметрических булевых функций, i-й выход первого блока вычисления полиномиальных
симметрических булевых функций соединен со вторым входом k-го элемента И (i + 1)-й
группы, j-й выход второго блока вычисления полиномиальных симметрических булевых
функций соединен со вторым входом j-го элемента И первой группы и третьим входом
(j + 1)-го элемента И (i + 1)-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления бисимметрических булевых функций n переменных, содержащее два многовходовых одноразрядных сумматора и мультиплексор [1].
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления бисимметрических булевых функций n переменных, содержащее два блока вычисления веса двоичных кодовых
комбинаций, L = (m + 1)(n - m + 1) элементов И (m = 1,2,3,…;n > m), элемент ИЛИ, n информационных входов и L настроечных входов [2].
Недостатком известного устройства также является высокая конструктивная сложность.
Изобретение направлено на решение задачи упрощения конструкции устройства для
вычисления бисимметрических булевых функций n переменных.
Названный технический результат достигается путем использования блоков вычисления полиномиальных симметрических булевых функций и элемента сложения по модулю
два, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления бисимметрических булевых функций n переменных содержит m + 1 группу элементов И, где m = 1,2,3,…, причем первая группа содержит n-m
элементов И, где n>m, (i + 1)-я группа, где i = 1, m, содержит p элементов И, где p = n m + 1.
Первый вход j-го элемента И первой группы, где j = 1, n − m, соединен с j-м настроечным входом устройства. Первый вход k-го элемента И (i + 1)-й группы, где k = 1, p, соединен с (i ⋅ p + k - 1)-м настроечным входом устройства.
Устройство содержит также два блока вычисления полиномиальных симметрических
булевых функций и элемент сложения по модулю два, выход которого соединен с выходом устройства, а первый вход соединен с p ⋅ (m + 1)-м настроечным входом устройства.
Выход j-го элемента И первой группы соединен с (j + 1)-м входом элемента сложения
по модулю два, выход k-го элемента И (i + 1)-й группы соединен с (i ⋅ p + k)-м входом
элемента сложения по модулю два.
В устройстве i-й вход первой группы информационных входов соединен с i-м входом
первого блока вычисления полиномиальных симметрических булевых функций, j-й вход
второй группы информационных входов соединен с j-м входом второго блока вычисления
2
BY 13240 C1 2010.06.30
полиномиальных симметрических булевых функций, i-й выход первого блока вычисления
полиномиальных симметрических булевых функций соединен со вторым входом k-го
элемента И (i + 1)-й группы, j-й выход второго блока вычисления полиномиальных симметрических булевых функций соединен со вторым входом j-го элемента И первой группы и третьим входом (j + 1)-го элемента И (i + 1)-й группы.
На фиг. 1 представлена схема устройства для вычисления бисимметрических булевых
функций n переменных при n = 7 и m = 4.
Устройство содержит первый 1 и второй 2 блоки вычисления полиномиальных симметрических булевых функций, m + 1 = 5 групп элементов И (n - m = 3 элемента И 3, 4 и 5
первой группы; p = n - m + 1 = 4 элемента И 6-9 второй группы; p = n - m + 1 = 4 элемента
И 10-13 третьей группы; p = n - m + 1 = 4 элемента И 14-17 четвертой группы; p = n m + 1 = 4 элемента И 18-21 пятой группы), элемент сложения по модулю два 22, m = 4 информационных входа 23-26 первой группы, n - m = 3 информационных входа 27, 28 и 29
второй группы, (m + 1)(n - m + 1) = 20 настроечных входов 30-49, выход 50.
Поясним принцип работы устройства для вычисления бисимметрических булевых
функций n переменных.
Обозначим: G sh = (h , h ,..., h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0,1} и G 0h ≡ ∅.
Булева функция F = F(X), X = (x1,x2,…,xn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F однозначно определяется своим локальным кодом π(F) = (π0,π1,…,πn), где
πi = F G1i , G 0n − i , 0 ≤ i ≤ n.
(
)
= E nj (X ), 1 ≤ j ≤ n, представимая в виде суммы по модулю два всевозможных
С.б.ф.
попарно различных элементарных конъюнкций ранга j, составленных из переменных
xl,x2,…,xn, называется полиномиальной.
Булева функция f = f(X) называется бисимметрической (б.с.б.ф.), если вектор ее переменных X допускает разбиение на два кортежа X1 и X2, и при этом f симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу X1 и X2.
Для определенности полагаем: X1 = (x1,x2,…,xm), X2 = (xm+1,xm+2,…,xn), 1 ≤ m < n. При
X1 = m, X 2 = n − m будем говорить, что б.с.б.ф. f от n переменных принадлежит классу
(m, n-m).
Б.с.б.ф. f = f(X) = f(X1, X2), принадлежащая классу (m, n-m), однозначно определяется
своим локальным кодом C(f), который представляет собой булев вектор длины
L = (m + 1)(n-m + 1) бит:
C(f) = (C00,C01,…,C0,n-m,C10,C11,…,C1,n-m,…,Cm0,Cm1,…,Cm,n-m),
(1)
1
0
1
0
где C ij = f G i , G m − i , G j , G n − m − j , 0 ≤ i ≤ m, 0 ≤ j ≤ n-m.
Число б.с.б.ф. класса (m, n-m) равно 2L.
Бисимметрическая булева функция f = f(X) = f(X1,X2) класса (m,n-m) может быть однозначно представлена в виде положительно поляризованного полиномиального разложения:
E nj
(
)
f = f (X ) = f (X1 , X 2 ) =
m
n −m
i =0
j= 0
∑⊕ ∑
⊕ E im (X1 ) ⋅ E nj − m (X 2 ) ⋅ γ ij ,
(2)
где E im (X1 ), E nj − m (X 2 ), i = 0, m, j = 0, n − m - полиномиальные с.б.ф. и E 0m (X1 ) ≡ 1,
E 0n − m (X 2 ) ≡ 1 ;
Г(f) = (γ00,γ01,…,γ0,n-m,γ10,γ11,…,γ1,n-m,…,γm0,γm1,…,γm,n-m) - двоичный вектор коэффициентов полиномиального разложения, γij ∈ {0,1}.
3
BY 13240 C1 2010.06.30
Вектор Г(f) может быть найден из локального кода C(f) б.с.б.ф. f = f(X1, X2) методом,
изложенным в статье: полиномиальное разложение булевых функций с частичной симметрией на основе принципа локального кодирования //Автоматика и вычислительная
техника. - 1997. -№ 5. - С. 17-28.
Пример 1
При n = 7 и m = 4 полиномиальное разложение (2) бисимметрической булевой функции f = f(X) = f(X1, X2) примет вид:
f = f (X ) = f (X1 , X 2 ) = γ 00 ⊕ E13 (X 2 ) ⋅ γ 01 ⊕ E 32 (X 2 ) ⋅ γ 02 ⊕ E 33 (X 2 ) ⋅ γ 03 ⊕
⊕ E14 (X1 ) ⋅ γ10 ⊕ E14 (X1 ) ⋅ E13 (X 2 ) ⋅ γ11 ⊕ E14 (X1 ) ⋅ E 32 (X 2 ) ⋅ γ12 ⊕ E14 (X1 ) ⋅ E 33 (X 2 ) ⋅ γ13 ⊕
⊕ E 24 (X1 ) ⋅ γ 20 ⊕ E 24 (X1 ) ⋅ E13 (X 2 ) ⋅ γ 21 ⊕ E 24 (X1 ) ⋅ E 32 (X 2 ) ⋅ γ 22 ⊕ E 24 (X1 ) ⋅ E 33 (X 2 ) ⋅ γ 23 ⊕
(3)
⊕ E 34 (X1 ) ⋅ γ 30 ⊕ E 34 (X1 ) ⋅ E13 (X 2 ) ⋅ γ 31 ⊕ E 34 (X1 ) ⋅ E 32 (X 2 ) ⋅ γ 32 ⊕ E 34 (X1 ) ⋅ E 33 (X 2 ) ⋅ γ 33 ⊕
⊕ E 44 (X1 ) ⋅ γ 40 ⊕ E 44 (X1 ) ⋅ E13 (X 2 ) ⋅ γ 41 ⊕ E 44 (X1 ) ⋅ E 32 (X 2 ) ⋅ γ 42 ⊕ E 44 (X1 ) ⋅ E 33 (X 2 ) ⋅ γ 43 ,
где X1 = (x1,x2,x3,x4); X2 = (x5,x6,x7);
E14 (X1 ) = x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ; E 24 (X1 ) = x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ;
E 34 (X1 ) = x1x 2 x 3 ⊕ x1x 3 x 4 ⊕ x1x 2 x 4 ⊕ x 2 x 3 x 4 ; E 44 (X1 ) = x1x 2 x 3 x 4 ;
E13 (X 2 ) = x 5 ⊕ x 6 ⊕ x 7 ; E 32 (X 2 ) = x 5 x 6 ⊕ x 5 x 7 ⊕ x 6 x 7 ; E 33 (X 2 ) = x 5 x 6 x 7 .
Устройство для вычисления бисимметрических булевых функций n переменных построено в точном соответствии с разложением (2). Схема устройства при n = 7 и m = 4,
приведенная на чертеже (фиг. 1), описывается выражением (3).
Из (2) непосредственно следует, что вектором настройки устройства на реализацию
конкретной б.с.б.ф. f = f(X) = f(X1,X2) является вектор Г(f).
Устройство при n = 7 и m = 4 (фиг. 1) работает следующим образом.
На информационные входы 23-26 первой группы поступают (в произвольном порядке)
переменные x1 - x4 первого кортежа X1, на информационные входы 27-29 второй группы - (в
произвольном порядке) переменные x5 - x7 второго кортежа X2, на настроечные входы 30-49 сигналы настройки соответственно γ00, γ01, γ02, γ03, γ10, γ11, γ12, γ13, γ20, γ21, γ22, γ23, γ30, γ31, γ32, γ33,
γ40, γ41, γ42, γ43.
На выходе 50 реализуется б.с.б.ф. f = f(X) = f(X1,X2), определяемая вектором настройки Г(f).
Пример 2
Найдем вектор настройки устройства при n = 7 и m = 4 (фиг. 1) на реализацию бисимметрической булевой функции:
f = x 1 x 2 x 3 x 4 ⋅ (x 5 ⊕ x 6 ⊕ x 7 ) ∨ x 1 x 2 ⋅ (x 3 ⊕ x 4 ) ⋅ x 5 x 6 x 7 ∨ (x 1 ⊕ x 2 ) ⋅ x 3 x 4 x 5 x 6 x 7 ∨
∨ x1x 2 x 3 x 4 x 5 x 6 x 7 .
Очевидно, что локальный код (1) данной функции имеет вид:
C(f) = (C00,C01,C02,C03,C10,C11,C12,C13,C20,C21,C22,C23,C30,C31,C32,C33,C40,C41,C42,C43) =
= (0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0).
По локальному коду C(f) найдем вектор Г(f) коэффициентов полиномиального разложения реализуемой устройством б.с.б.ф. f. С этой целью построим таблицу локальных кодов производных б.с.б.ф. f (фиг. 2), из которой и определим элементы вектора Г(f):
Г(f) = (γ00,γ01,γ02,γ03,γ10,γ11,γ12,γ13,γ20,γ21,γ22,γ23,γ30,γ31,γ32,γ33,γ40,γ41,γ42,γ43) =
= (0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,1,1).
Таким образом, для реализации устройством (фиг. 1) б.с.б.ф. f сигнал логической единицы необходимо подать на настроечные входы 31, 35, 39, 43, 45, 46, 48 и 49, а сигнал логического нуля - на настроечные входы 30, 32, 33, 34, 36, 37, 38, 40, 41, 42, 44 и 47.
4
BY 13240 C1 2010.06.30
Отметим, что с учетом найденного вектора Г(f) выражение (3) для рассматриваемой
функции примет вид:
f = E13 (X 2 ) ⊕ E14 (X1 ) ⋅ E13 (X 2 ) ⊕ E 24 (X1 ) ⋅ E13 (X 2 ) ⊕ E 34 (X1 ) ⋅ E13 (X 2 ) ⊕
⊕ E 34 (X1 ) ⋅ E 33 (X 2 ) ⊕ E 44 (X1 ) ⊕ E 44 (X1 ) ⋅ E 32 (X 2 ) ⊕ E 44 (X1 ) ⋅ E 33 (X 2 ).
Достоинствами устройства для вычисления бисимметрических булевых функций n
переменных являются простая конструкция и высокое быстродействие.
Источники информации:
1. Патент РБ 5171, МПК G 06F 7/00, 2003.
2. Патент РБ 7592, МПК G 06F 7/00, H 03M 7/22, 2005.
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
287 Кб
Теги
by13240, патент
1/--страниц
Пожаловаться на содержимое документа