close

Вход

Забыли?

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

?

Патент BY13926

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.12.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13926
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N
ПЕРЕМЕННЫХ
(21) Номер заявки: a 20090087
(22) 2009.01.26
(43) 2009.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Терешко Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY a 20080778, 2008.
BY a 20080355, 2008.
SU 1441380 A1, 1988.
BY 13926 C1 2010.12.30
(57)
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 2m + 7 - число переменных реализуемых функций, где
m = 2,3,4,…, содержащее блок вычисления полиномиальных симметрических булевых
функций семи переменных и m групп логических элементов, каждая из которых содержит
элементы И с первого по седьмой и элементы сложения по модулю два с первого по седьмой, причем выход i-го, где i = 1,7 , элемента И j-й, где j = 1, m , группы соединен с первым
входом i-го элемента сложения по модулю два j-й группы, i-й вход блока вычисления полиномиальных симметрических булевых функций семи переменных соединен с i-м
BY 13926 C1 2010.12.30
входом устройства, h-й, где h = 1,6 , выход блока вычисления полиномиальных симметрических булевых функций семи переменных соединен со вторым входом h-го элемента
сложения по модулю два первой группы и первым входом (h + 1)-го элемента И первой
группы, седьмой выход - со вторым входом седьмого элемента сложения по модулю два
первой группы и первым входом первого элемента И первой группы, выход h-го элемента
сложения по модулю два k-й, где k = 1, m − 1 , группы соединен со вторым входом h-го
элемента сложения по модулю два (k + 1)-й группы и первым входом (h + 1)-го элемента
И (k + 1)-й группы, выход седьмого элемента сложения по модулю два k-й группы соединен со вторым входом седьмого элемента сложения по модулю два (k + 1)-й группы и
первым входом первого элемента И (k + 1)-й группы, выход i-го элемента сложения по
модулю два m-й группы соединен с i-м выходом устройства, отличающееся тем, что содержит m полусумматоров, а каждая из m групп логических элементов содержит элементы И с восьмого по четырнадцатый, выход (i + 7)-го элемента И j-й группы соединен с
третьим входом i-го элемента сложения по модулю два j-й группы, s-й, где s = 1,5 , выход
блока вычисления полиномиальных симметрических булевых функций семи переменных
соединен с первым входом (s + 9)-го элемента И первой группы, шестой выход - с первым
входом восьмого элемента И первой группы, седьмой выход - с первым входом девятого
элемента И первой группы, выход s-го элемента сложения по модулю два k-й группы соединен с первым входом (s + 9)-го элемента И (k + 1)-й группы, выход шестого элемента
сложения по модулю два k-й группы соединен с первым входом восьмого элемента И
(k + 1)-й группы, выход седьмого элемента сложения по модулю два k-й группы соединен
с первым входом девятого элемента И (k + 1)-й группы, (2j + l + 5)-й, где l = 1,2, вход
устройства соединен с l-м входом j-го полусумматора, выход суммы j-го полусумматора
соединен с четвертым входом первого элемента сложения по модулю два j-й группы и
вторым входом i-го элемента И j-й группы, выход переноса j-го полусумматора соединен с
четвертым входом второго элемента сложения по модулю два j-й группы и вторым входом
(i + 7)-го элемента И j-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления полиномиальных симметрических булевых
функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов [1].
Недостатками устройства являются ограниченное число переменных реализуемых
функций, а также невозможность вычисления полиномиальных модулярных симметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функций n переменных, содержащее блок вычисления
полиномиальных симметрических булевых функций семи переменных и n-7 групп (n = 9,
10, 11, …) логических элементов, каждая из которых содержит семь элементов сложения
по модулю два и семь элементов И [2].
Недостатками устройства является низкое быстродействие, определяемое большой
глубиной схемы.
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления полиномиальных модулярных симметрических булевых функций n переменных.
2
BY 13926 C1 2010.12.30
Названный технический результат достигается путем введения в состав устройства
полусумматоров и дополнительно в каждую группу логических элементов по семь элементов И, а также изменением связей элементов в схеме устройства.
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 2m + 7 - число переменных реализуемых функций, где
m = 2, 3, 4,…, содержит блок вычисления полиномиальных симметрических булевых
функций семи переменных и m, групп логических элементов, каждая из которых содержит элементы И с первого по седьмой и элементы сложения по модулю два с первого по
седьмой.
При этом выход i-го, где i = 1,7 , элемента И j-й, где j = 1, m , группы соединен с первым входом i-го элемента сложения по модулю два j-и группы.
В устройстве i-й вход блока вычисления полиномиальных симметрических булевых
функций семи переменных соединен с i-м входом устройства, h-й, где h = 1,6 , выход блока вычисления полиномиальных симметрических булевых функций семи переменных соединен со вторым входом h-го элемента сложения по модулю два первой группы и
первым входом (h + 1)-го элемента И первой группы. Седьмой выход соединен со вторым
входом седьмого элемента сложения по модулю два первой группы и первым входом первого элемента И первой группы.
Выход h-го элемента сложения по модулю два k-й, где k = 1, m − 1 , группы соединен со
вторым входом h-го элемента сложения по модулю два (k + 1)-й группы и первым входом
(h + 1)-го элемента И (k + l)-й группы. Выход седьмого элемента сложения по модулю два
k-й группы соединен со вторым входом седьмого элемента сложения по модулю два
(k + 1)-й группы и первым входом первого элемента И (k + 1)-й группы. Выход i-го элемента сложения по модулю два m-й группы соединен с i-м выходом устройства.
В отличие от прототипа устройство содержит m полусумматоров, а каждая группа логических элементов содержит элементы И с восьмого по четырнадцатый.
Выход (i + 7)-го элемента И j-й группы соединен с третьим входом i-го элемента сложения по модулю два j-й группы.
В устройстве s-й, где s = 1,5 , выход блока вычисления полиномиальных симметрических булевых функций семи переменных соединен с первым входом (s + 9)-го элемента И
первой группы, шестой выход соединен с первым входом восьмого элемента И первой
группы, седьмой выход соединен с первым входом девятого элемента И первой группы.
Выход s-го элемента сложения по модулю два k-й группы соединен с первым входом
(s + 9)-го элемента И (k + 1)-й группы, выход шестого элемента сложения по модулю два
k-й группы соединен с первым входом восьмого элемента И (k + l)-й группы, выход седьмого элемента сложения по модулю два k-й группы соединен с первым входом десятого
элемента И (k + 1)-й группы.
В устройстве (2j + l + 5)-й, где l = 1,2, вход соединен с l-м входом j-го полусумматора.
Выход суммы j-го полусумматора соединен с четвертым входом первого элемента
сложения по модулю два j-й группы и вторым входом i-го элемента И j-й группы, выход
переноса j-го полусумматора соединен с четвертым входом второго элемента сложения по
модулю два j-й группы и вторым входом (i + 7)-го элемента И j-й группы.
На фиг. 1 представлена схема устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных при n = 2m + 7 = 13 (m = 3).
Устройство содержит блок вычисления полиномиальных симметрических булевых
функций семи переменных 1, 14m = 42 элемента И 2-43, 7m = 21 элемент сложения по модулю два 44-64, m = 3 полусумматора 65, 66 и 67, n = 2m + 7 = 13 входов 68-80 и семь выходов 81-87.
Устройство реализует семь полиномиальных модулярных симметрических булевых
функций n переменных при величине модуля p = 7.
3
BY 13926 C1 2010.12.30
Поясним принцип построения и работы устройства.
Обозначим: G sh = (h, h, …, h ) - некоторый кортеж длины s, содержащий только элеh
менты h ∈ {0,1}, и G ≡ ∅ .
0
Булева функция F = F(X), X = (x1, x2, …, xn) называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
π(F) = (π0, π1, ..., πn),
1
0
где πi = F G i , G n −i , i = 0, n .
Таким образом, вес двоичной кодовой комбинации V(X) = x1 + x2 + … + хn однозначно
определяет значение с.б.ф. F = F(X) на данном наборе переменных из X.
С.б.ф. E nj = E nj (X) , 1 ≤ j ≤ n, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга j, составленных из переменных
x1, x2, …, xn, называется полиномиальной (п.с.б.ф.).
Произвольная с.б.ф. F = F(X) от n переменных может быть однозначно представлена в
виде положительно поляризованного полиномиального разложения (полинома Жегалкина) посредством п.с.б.ф. E nj :
(
)
n
F = F(X) = γ 0 ⊕ ∑ ⊕ γ j ⋅ E nj (X) ,
(1)
j=1
где γ(F) = (γ0, γ1, …, γn) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. F.
С.б.ф. Ф = Ф(X), X = (x1, x2, …, xn), называется модулярной, если ее значение на любом
наборе переменных из X однозначно определяется весом V(X) mod p = (xl + x2 + … + xn) mod p
двоичной кодовой комбинации по модулю p, p ≤ n:
Ф G1i , G 0n − i = Ф G1j , G 0n − j ,
(
)
(
)
где i mod p = j mod p, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
М.с.б.ф. Ф = Ф(X) можно задавать p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1, …, ρp-1),
1
0
где ρ j = Ф G i , G n −i , i mod p = j , 0 ≤ i ≤ n , j = 0, p − 1.
(
)
(2)
Очевидно, что ρ(Ф) = (π0, π1, …, πp-1) и, следовательно, при p ≥ n-1 локальные коды
ρ(Ф) = π(Ф).
Необходимо отметить, что один и тот же модулярный локальный код ρ(Ф) вида (2)
могут иметь м.с.б.ф., зависящие от различного числа n переменных.
В классе с.б.ф. n переменных количество (2p) различных м.с.б.ф. определяется только
величиной модуля p и не зависит от n.
Далее будем рассматривать только модулярные симметрические булевы функции n
переменных Ф = Ф(X), X = (x1, x2, …, xn), заданные своим модулярным локальным кодом
ρ(Ф) = (ρ0, ρ1, ρ2 ρ3, ρ4, ρ5 ρ6) при величине модуля p = 7, n = 9, 10, 11, ….
Полиномиальное разложение (1) м.с.б.ф. Ф = Ф(X) при p = 7 имеет вид:
(3)
Ф = к 0 ⊕ к1 ⋅ R 1n ⊕ к 2 ⋅ R 2n ⊕ к 3 ⋅ R 3n ⊕ к 3 ⋅ R 4n ⊕ к 3 ⋅ R 5n ⊕ к 3 ⋅ R 6n ⊕ к 3 ⋅ R 7n ,
где
R in = R in (X) = ∑ ⊕ E nj (X), i = 1,6;
(4)
1≤ j≤ n
j mod 7 = i
R = R (X) =
7
n
7
n
∑ ⊕E
1≤ j≤ n
j mod 7 = 0
4
j
n
(X) .
(5)
BY 13926 C1 2010.12.30
Функции R1n , R n2 ,…, R 7n назовем полиномиальными м.с.б.ф.
При этом компоненты вектора к(Ф) = (к0, к1, к2, к3, к4, к5, к6, к7) коэффициентов полиномиального разложения м.с.б.ф. Ф = Ф(X) могут быть определены из модулярного локального кода ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4, ρ5, ρ6) следующим образом:
к 0 = ρ0 ;


к1 = ρ 0 ⊕ ρ1 ;


к 2 = ρ0 ⊕ ρ2 ;

к 3 = ρ 0 ⊕ ρ1 ⊕ ρ 2 ⊕ ρ3 ;

(6)

к 4 = ρ0 ⊕ ρ4 ;


к 5 = ρ 0 ⊕ ρ1 ⊕ ρ 4 ⊕ ρ 5 ;

к 6 = ρ0 ⊕ ρ 2 ⊕ ρ 4 ⊕ ρ 6 ;

к 7 = ρ1 ⊕ ρ 2 ⊕ ρ3 ⊕ ρ 4 ⊕ ρ 5 ⊕ ρ 6 .
Пример 1.
При n = 15 полиномиальные м.с.б.ф. в разложении (3) согласно (4) и (5) могут быть
представлены посредством полиномиальных с.б.ф.:
8
R 115 = R 115 (X) = E115 (X) ⊕ E15
(X) ⊕ E15
15 (X );
2
2
2
9
R 15
= R 15
(X) = E15
(X) ⊕ E15
(X);
3
3
3
R 15
= R 15
(X) = E15
(X) ⊕ E10
15 (X );
4
4
4
R 15
= R 15
(X) = E15
(X) ⊕ E11
15 ( X );
5
5
5
R 15
= R 15
(X) = E15
(X) ⊕ E12
15 (X );
6
6
6
R 15
= R 15
(X) = E15
(X) ⊕ E13
15 ( X );
7
7
7
R 15
= R 15
(X) = E15
(X) ⊕ E14
15 ( X ).
Пример 2.
Пусть π(Ф) = (π0, π1, …, π15) = (0,0,1,1,0,0,1,0,0,1,1,0,0,1,0,0) - локальный код функции
среднего разряда пятнадцативходового одноразрядного сумматора по модулю семь.
В соответствии с (2) модулярный локальный код этой функции имеет вид:
ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4, ρ5, ρ6) = (π0, π1, π2, π3, π4, π5, π6) = (0,0,1,1,0,0,1).
Из ρ(Ф) согласно (6) определим полиномиальный локальный код:
к(Ф) = (к0, к1,…, к7) = (0,0,1,0,0,0,0,1).
Тогда полиномиальное разложение (3) можно записать в виде:
2
7
Ф = Ф(X) = R 15
(X) ⊕ R 15
(X).
Устройство реализует семь полиномиальных м.с.б.ф. R nj (X) ; X = (x1, x2, …, xn),
j = 1,7 ; зависящие от произвольного числа n переменных для величины модуля p = 7, и
построено согласно следующим соотношениям:
5
BY 13926 C1 2010.12.30
R 1n + 2 (X, x n +1 , x n + 2 ) = R 1n (X ) ⊕ s ⊕ s ⋅ R 7n (X ) ⊕ p ⋅ R 6n (X ); 

R 2n + 2 (X, x n +1 , x n + 2 ) = R 2n (X ) ⊕ s ⋅ R 1n (X) ⊕ p ⊕ p ⋅ R 7n (X );

R 3n + 2 (X, x n +1 , x n + 2 ) = R 3n (X ) ⊕ s ⋅ R 2n (X) ⊕ p ⋅ R 1n (X);


R 4n + 2 (X, x n +1 , x n + 2 ) = R 4n (X ) ⊕ s ⋅ R 3n (X) ⊕ p ⋅ R 2n (X);


5
5
4
3
R n + 2 (X, x n +1 , x n + 2 ) = R n (X ) ⊕ s ⋅ R n (X) ⊕ p ⋅ R n (X);


6
6
5
4
R n + 2 (X, x n +1 , x n + 2 ) = R n (X ) ⊕ s ⋅ R n (X) ⊕ p ⋅ R n (X);

7
7
6
5

R n + 2 (X, x n +1 , x n + 2 ) = R n (X ) ⊕ s ⋅ R n (X) ⊕ p ⋅ R n (X),

(7)
где s = xn+1 ⊕ xn+2; p = xn+1xn+2.
Укажем, что при n = 7 полиномиальные м.с.б.ф. совпадают с полиномиальными с.б.ф. j
R 7 (X) = E 7j (X); j = 1,7 .
В устройстве блок вычисления полиномиальных симметрических булевых функций
семи переменных 1 реализует полиномиальные м.с.б.ф. R 7j ( x1 , x 2 ,..., x 7 ), j = 1,7 ; а каждая
группа из полусумматора, семи элементов сложения по модулю два и четырнадцати элементов И обеспечивает увеличение числа обрабатываемых переменных на две переменные согласно (7).
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций при n = 13 (фиг. 1) работает следующим образом.
На входы 68-80 подаются двоичные переменные х1, x2, …, x13 (в произвольном порядке), на выходах 81, 82,…, 87 реализуются значения полиномиальных м.с.б.ф.
2
2
7
7
R 113 = R 113 (X), R 13
= R 13
(X), ..., R 13
= R 13
(X) соответственно X = (х1, х2,…, x13).
Достоинствами устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных являются высокое быстродействие, простая конструкция, однородная и регулярная структура.
Источники информации
1. Патент РБ 9051, МПК G 06F 7/00, 2007.
2. BY а20080778, 2008 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
207 Кб
Теги
by13926, патент
1/--страниц
Пожаловаться на содержимое документа