close

Вход

Забыли?

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

?

Патент BY13927

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.12.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N
ПЕРЕМЕННЫХ
(21) Номер заявки: a 20090088
(22) 2009.01.26
(43) 2009.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Терешко Сергей Михайлович; Усов
Геннадий Иванович (BY)
BY 13927 C1 2010.12.30
BY (11) 13927
(13) C1
(19)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY a 20080355, 2008.
BY a 20080778, 2008.
SU 1441380 A1, 1988.
(57)
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 2m + 3 - число переменных реализуемых функций, где
m = 2, 3, 4, …, содержащее блок вычисления полиномиальных симметрических булевых
функций трех переменных и m групп логических элементов, каждая из которых содержит
первый, второй и третий элементы И, первый, второй и третий элементы сложения по модулю два, причем выход i-го, где i = 1, 2, 3, элемента И j-й, где j = 1, m , группы соединен с
первым входом i-го элемента сложения по модулю два j-й группы, i-й вход блока вычисления полиномиальных симметрических булевых функций трех переменных соединен с iм входом устройства, первый выход блока вычисления полиномиальных симметрических
булевых функций трех переменных соединен со вторым входом первого элемента сложения по модулю два первой группы и первым входом второго элемента И первой группы,
второй выход – со вторым входом второго элемента сложения по модулю два первой
группы и первым входом третьего элемента И первой группы, третий выход – со вторым
входом третьего элемента сложения по модулю два первой группы и первым входом первого элемента И первой группы, выход первого элемента сложения по модулю два k-й, где
BY 13927 C1 2010.12.30
k = 1, m − 1 , группы соединен со вторым входом первого элемента сложения по модулю
два (k + 1)-й группы и первым входом второго элемента И (k + 1)-й группы, выход второго
элемента сложения по модулю два k-й группы соединен со вторым входом второго элемента сложения по модулю два (k + 1)-й группы и первым входом третьего элемента И
(k + 1)-й группы, выход третьего элемента сложения по модулю два k-й группы соединен
со вторым входом третьего элемента сложения по модулю два (k + 1)-й группы и первым
входом первого элемента И (k + 1)-й группы, выход i-го элемента сложения по модулю
два m-й группы соединен с i-м выходом устройства, отличающееся тем, что каждая из m
групп логических элементов содержит четвертый элемент сложения по модулю два, четвертый, пятый, шестой и седьмой элементы И, выход (i + 3)-го элемента И j-й группы соединен с третьим входом i-го элемента сложения по модулю два j-й группы, первый выход
блока вычисления полиномиальных симметрических булевых функций трех переменных
соединен с первым входом шестого элемента И первой группы, второй выход - с первым
входом четвертого элемента И первой группы, третий выход - с первым входом пятого
элемента И первой группы, выход первого элемента сложения по модулю два k-й группы
соединен с первым входом шестого элемента И (k + 1)-й группы, выход второго элемента
сложения по модулю два k-й группы соединен с первым входом четвертого элемента И
(k + 1)-й группы, выход третьего элемента сложения по модулю два k-й группы соединен
с первым входом пятого элемента И (k + 1)-й группы, (2j + l + 1)-й, где l = 1, 2, вход
устройства соединен с l-м входом четвертого элемента сложения по модулю два j-й группы и l-м входом седьмого элемента И j-й группы, выход четвертого элемента сложения по
модулю два j-й группы соединен с четвертым входом первого элемента сложения по модулю два j-й группы и вторым входом i-го элемента И j-й группы, выход седьмого элемента И j-й группы соединен с четвертым входом второго элемента сложения по модулю два
j-й группы и вторым входом (i + 3)-го элемента И j-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления полиномиальных симметрических булевых
функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов [1].
Недостатками устройства являются ограниченное число переменных реализуемых
функций, а также невозможность вычисления полиномиальных модулярных симметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функций n переменных, содержащее блок вычисления
полиномиальных симметрических булевых функций трех переменных и n - 3 группы
(n = 5, 6, 7, …) логических элементов, каждая из которых содержит три элемента сложения по модулю два и три элемента И [2].
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления полиномиальных модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства
дополнительно в каждую группу логических элементов по одному элементу сложения по
2
BY 13927 C1 2010.12.30
модулю два и по четыре элемента И, а также изменением межсоединений элементов в
схеме устройства.
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 2m + 3 - число переменных реализуемых функций, где
m = 2, 3, 4, ..., содержит блок вычисления полиномиальных симметрических булевых
функций трех переменных и m групп логических элементов, каждая из которых содержит
первый, второй и третий элементы И, первый, второй и третий элементы сложения по модулю два. При этом выход i-го, где I = 1, 2, 3, элемента И j-й, где j = 1, m , группы соединен с первым входом i-го элемента сложения по модулю два j-й группы, i-й вход блока
вычисления полиномиальных симметрических булевых функций трех переменных соединен с i-м входом устройства. Первый выход блока вычисления полиномиальных симметрических булевых функций трех переменных соединен со вторым входом первого
элемента сложения по модулю два первой группы и первым входом второго элемента И
первой группы, второй выход соединен со вторым входом второго элемента сложения по
модулю два первой группы и первым входом третьего элемента И первой группы, третий
выход соединен со вторым входом третьего элемента сложения по модулю два первой
группы и первым входом первого элемента И первой группы. Выход первого элемента
сложения по модулю два k-й, где k = 1, m − 1 , группы соединен со вторым входом первого
элемента сложения по модулю два (k + 1)-й группы и первым входом второго элемента И
(k + 1)-й группы, выход второго элемента сложения по модулю два k-й группы соединен
со вторым входом второго элемента сложения по модулю два (k + 1)-й группы и первым
входом третьего элемента И (k + 1)-й группы, выход третьего элемента сложения по модулю два k-й группы соединен со вторым входом третьего элемента сложения по модулю
два (k + 1)-й группы и первым входом первого элемента И (k + 1)-й группы. Выход i-го
элемента сложения по модулю два m-й группы соединен с i-м выходом устройства.
В отличие от прототипа в устройстве каждая группа логических элементов содержит
четвертый элемент сложения по модулю два, четвертый, пятый, шестой и седьмой элементы И. Выход (i + 3)-го элемента И j-й группы соединен с третьим входом i-го элемента
сложения по модулю два j-й группы. Первый выход блока вычисления полиномиальных
симметрических булевых функций трех переменных соединен с первым входом шестого
элемента И первой группы, второй выход соединен с первым входом четвертого элемента
И первой группы, третий выход соединен с первым входом пятого элемента И первой
группы. Выход первого элемента сложения по модулю два k-й группы соединен с первым
входом шестого элемента И (k + 1)-й группы, выход второго элемента сложения по модулю два k-й группы соединен с первым входом четвертого элемента И (k + 1)-й группы,
выход третьего элемента сложения по модулю два k-й группы соединен с первым входом
пятого элемента И (k + 1)-й группы. В устройстве (2j + l + 1)-й, где l = 1, 2, вход соединен
с l-м входом четвертого элемента сложения по модулю два j-й группы и l-м входом седьмого элемента И j-й группы. Выход четвертого элемента сложения по модулю два j-й
группы соединен с четвертым входом первого элемента сложения по модулю два j-й
группы и вторым входом i-го элемента И j-й группы. Выход седьмого элемента И j-й
группы соединен с четвертым входом второго элемента сложения по модулю два j-й группы и вторым входом (i + 3)-го элемента И j-й группы.
На фигуре представлена схема устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных при n = 11 (m = 4).
Устройство содержит блок вычисления полиномиальных симметрических булевых
функций трех переменных 1,7m = 28 элементов И 2-29, 4m = 16 элементов сложения по
модулю два 30-45, n = 2m + 3 = 11 входов 46-56 и три выхода 57, 58 и 59.
Поясним принцип построения и работы устройства.
3
BY 13927 C1 2010.12.30
Обозначим: G sh = (h, h, …, h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0,1}, и G 0h ≡ ∅ .
Булева функция 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 + … + xn однозначно
определяет значение с.б.ф. 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) при величине модуля p = 3, n = 5, 6, 7 и т. д.
Полиномиальное разложение (1) м.с.б.ф. Ф = Ф(X) имеет вид:
(3)
Ф = Ф(Х) = к 0 ⊕ к1 ⋅ R1n (X) ⊕ к 2 ⋅ R 2n (X) ⊕ к 3 ⋅ R 3n (X) ,
где
R1n = R1n (X) = ∑ ⊕ E nj (X) ;
(4)
1≤ j≤ n
j mod 3 = 1
R 2n
=
R 2n (X)
=
∑
⊕ E nj (X) ;
1≤ j≤ n
j mod 3 = 2
4
(5)
BY 13927 C1 2010.12.30
R 3n = R 3n (X) =
∑ ⊕ E nj (X) .
1≤ j≤ n
j mod 3 = 0
(6)
Функции R1n , R n2 и R 3n назовем полиномиальными м.с.б.ф.
При этом компоненты вектора к(Ф) = (к0, к1, к2, к3) коэффициентов полиномиального
разложения м.с.б.ф. Ф = Ф(X) могут быть определены из модулярного локального кода
ρ(Ф) = (ρ0, ρ1, ρ2) следующим образом:
к 0 = ρ0 ;

к1 = ρ0 ⊕ ρ1; 
(7)

к 2 = ρ 0 ⊕ ρ 2 ;
к 3 = ρ1 ⊕ ρ 2 . 
Пример 1.
При n = 8 полиномиальные м.с.б.ф. в разложении (3) согласно (4), (5) и (6) могут быть
представлены посредством полиномиальных с.б.ф. следующим образом:
R18 = R18 (X) = E18 (X) ⊕ E84 (X) ⊕ E87 (X) ;
R 82 = R 82 (X) = E82 (X) ⊕ E85 (X) ⊕ E88 (X) ;
R 83 = R 83 (X) = E83 (X ) ⊕ E86 (X) .
Пример 2.
Пусть π(Ф) = (π0, π1, …, π15) = (0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0) - локальный код функции
младшего разряда пятнадцативходового одноразрядного сумматора по модулю три.
В соответствии с (2) модулярный локальный код этой функции имеет вид:
ρ(Ф) = (ρ0, ρ1, ρ2) = (π0, π1, π2) = (0,1,0).
Из локального кода ρ(Ф) согласно (7) определим коэффициенты полиномиального
разложения:
к(Ф) = (к0, к1, к2, к3) = (0,1,0,1).
Тогда полиномиальное разложение (3) для рассматриваемой функции можно записать
в виде:
3
Ф = Ф(X) = R115 (X ) ⊕ R15
(X) .
Предлагаемое устройство реализует три полиномиальные м.с.б.ф. R nj (X) ; X = (x1, x2,
…, xn), j = 1, 2, 3, зависящие от произвольного числа n переменных для величины модуля
p = 3.
Устройство построено согласно следующим соотношениям:
R1n + 2 (X, x n +1, x n + 2 ) = R1n (X) ⊕ ( x n +1 ⊕ x n + 2 ) ⊕ ( x n +1 ⊕ x n + 2 ) ⋅ R 3n (X ) ⊕ x n +1 x n + 2 ⋅ R 2n (X);


R 2n + 2 (X, x n +1, x n + 2 ) = R 2n (X) ⊕ ( x n +1 ⊕ x n + 2 ) ⋅ R1n (X ) ⊕ x n +1 x n + 2 ⊕ x n +1 x n + 2 ⋅ R 3n (X);


R 3n + 2 (X, x n +1, x n + 2 ) = R 3n (X) ⊕ ( x n +1 ⊕ x n + 2 ) ⋅ R 2n (X ) ⊕ x n +1 x n + 2 ⋅ R1n (X).

(8)
В устройстве блок вычисления полиномиальных симметрических булевых функций
трех переменных 1 реализует полиномиальные м.с.б.ф. R 3j ( x1, x 2 , x 3 ) , j = 1, 2, 3, а каждая
группа из четырех элементов сложения по модулю два и семи элементов И обеспечивает
увеличение числа обрабатываемых переменных на две переменные согласно (8).
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций при n = 11 (фигура) работает следующим образом.
5
BY 13927 C1 2010.12.30
На входы 46-56 подаются двоичные переменные x1, x2, ..., x11 (в произвольном порядке), на выходах 57, 58 и 59 реализуются значения полиномиальных м.с.б.ф. R111 = R111 (X) ,
2
2
3
3
R11
(X) и R11
= R11
= R11
(X) соответственно, X = (x1, x2, …, x11).
Достоинствами устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных являются высокое быстродействие, простая конструкция, однородная и регулярная структура.
Источники информации:
1. Патент РБ 9051, МПК G 06F 7/00, 2007.
2. BY a 20080355, 2008 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
1
Размер файла
139 Кб
Теги
патент, by13927
1/--страниц
Пожаловаться на содержимое документа