close

Вход

Забыли?

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

?

Патент BY13268

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.06.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13268
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N
ПЕРЕМЕННЫХ
(21) Номер заявки: a 20080778
(22) 2008.06.13
(43) 2008.12.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 9147 C1, 2007.
SU 1441380 A1, 1988.
SU 1559338 A1, 1990.
(57)
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 9, 10, 11,…, характеризующееся тем, что содержит блок
вычисления полиномиальных симметрических булевых функций семи переменных, i-й
вход которого, где i = 1,7 , соединен с i-м входом устройства и n – 7 групп элементов, j-я из
BY 13268 C1 2010.06.30
которых, где j = 1, n − 7 , содержит семь элементов сложения по модулю два и семь элементов И, причем выход i-го элемента И j-й группы соединен с первым входом i-го элемента сложения по модулю два j-й группы, (j + 7)-й вход устройства соединен с первым
BY 13268 C1 2010.06.30
входом i-го элемента И j-й группы и вторым входом первого элемента сложения по модулю два j-й группы, первый выход блока вычисления полиномиальных симметрических
булевых функций семи переменных соединен с третьим входом первого элемента сложения по модулю два первой группы и вторым входом второго элемента И первой группы, lй выход, где l = 1,5 , соединен со вторым входом l-го элемента сложения по модулю два
первой группы и вторым входом (l + 1)-го элемента И первой группы, седьмой выход соединен со вторым входом седьмого элемента сложения по модулю два первой группы и
вторым входом первого элемента И первой группы, выход первого элемента сложения по
модулю два k-й группы, где k = 1, n − 8 , соединен с третьим входом первого элемента сложения по модулю два (k + 1)-й группы и вторым входом второго элемента И (k + 1)-й
группы, выход l-го элемента сложения по модулю два k-й группы соединен со вторым
входом l-го элемента сложения по модулю два (k + 1)-й группы и вторым входом (l + 1)-го
элемента И (k + 1)-й группы, выход седьмого элемента сложения по модулю два k-й группы соединен со вторым входом седьмого элемента сложения по модулю два (k + 1)-й
группы и вторым входом первого элемента И (k + 1)-й группы, выход i-го элемента сложения по модулю два (n - 7)-й группы соединен с i-м выходом устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления полиномиальных симметрических булевых
функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов [1].
Недостатками устройства являются ограниченное число переменных реализуемых
функций, а также невозможность вычисления полиномиальных модулярных симметрических булевых функций.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора,
двадцать четыре элемента И, пятнадцать элементов сложения по модулю два, восемь входов и восемь выходов [2].
Недостатками устройства также являются ограниченное число переменных реализуемых функций и невозможность вычисления полиномиальных модулярных симметрических булевых функций.
Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных модулярных симметрических булевых функций
произвольного числа n переменных.
Названный технический результат достигается путем введения в состав устройства n-7
групп логических элементов, каждая из которых содержит семь элементов сложения по
модулю два и семь элементов И, а также изменением межсоединений элементов в схеме
устройства.
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций n переменных, где n = 9 ,10, 11,…, содержит блок вычисления полиномиальных
симметрических булевых функций семи переменных, i-й вход которого, где i = 1,7 , соединен с i-м входом устройства.
Устройство содержит также n-7 групп элементов, j-я из которых, где j = 1, n − 7 , содержит семь элементов сложения по модулю два и семь элементов И. При этом выход i-го
2
BY 13268 C1 2010.06.30
элемента И j-й группы соединен с первым входом i-го элемента сложения по модулю два
j-й группы.
В устройстве (j + 7)-й вход соединен с первым входом i-го элемента И j-й группы и
вторым входом первого элемента сложения по модулю два j-й группы.
Первый выход блока вычисления полиномиальных симметрических булевых функций
семи переменных соединен с третьим входом первого элемента сложения по модулю два
первой группы и вторым входом второго элемента И первой группы, l-й выход, где l = 1,5 ,
соединен со вторым входом l-го элемента сложения по модулю два первой группы и вторым входом (l + 1)-го элемента И первой группы, седьмой выход соединен со вторым входом седьмого элемента сложения по модулю два первой группы и вторым входом первого
элемента И первой группы.
Выход первого элемента сложения по модулю два k-й группы, где k = 1, n − 8 , соединен с третьим входом первого элемента сложения по модулю два (k + 1)-й группы и вторым входом второго элемента И (k + 1)-й группы, выход l-го элемента сложения по
модулю два k-й группы соединен со вторым входом l-го элемента сложения по модулю
два (k + 1)-й группы и вторым входом (l + 1)-го элемента И (k + 1)-й группы, выход седьмого элемента сложения по модулю два k-й группы соединен со вторым входом седьмого
элемента сложения по модулю два (k + 1)-й группы и вторым входом первого элемента И
(k + 1)-й группы.
Выход i-го элемента сложения по модулю два (n - 7)-й группы соединен с i-м выходом
устройства.
На фигуре представлена схема устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных при n = 12.
Устройство содержит блок вычисления полиномиальных симметрических булевых
функций семи переменных 1,7n-49 = 35 элементов И 2-36 (элементы 2-8 первой группы;
элементы 9-15 второй группы; элементы 16-22 третьей группы; элементы 23-29 четвертой
группы; элементы 30-36 пятой группы), 7n-49 = 35 элементов сложения по модулю два 3771 (элементы 37-43 первой группы; элементы 44-50 второй группы; элементы 51-57 третьей группы; элементы 58-64 четвертой группы; элементы 65-71 пятой группы), n= 12 входов 72-83 и семь выходов 84-90.
Устройство реализует семь полиномиальных модулярных симметрических булевых
функций n переменных при величине модуля p = 7.
Поясним принцип построения и работы устройства.
Обозначим: G sh = (h, h,K, h ) - некоторый кортеж длины s, содержащий только элементы h ∈{0,1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (x1, x2,…, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
π(F) = (π0 , π1 , ..., π n ),
(
)
где πi = F G il , G 0n −i , i = 0, n.
Таким образом, вес двоичной кодовой комбинации V(X) = х1 + х2 +…+ хn однозначно
определяет значение с.б.ф. F = F(X) на данном наборе переменных из X.
С.б.ф. E nj = E nj (X ) , 1≤j≤n, представимая в виде суммы по модулю два всевозможных
попарно различных элементарных конъюнкций ранга j, составленных из переменных xl,
x2,…, xn, называется полиномиальной (п.с.б.ф.).
Произвольная с.б.ф. F = F(X) от n переменных может быть однозначно представлена в
виде положительно поляризованного полиномиального разложения (полинома Жегалкина) посредством п.с.б.ф. E nj :
3
BY 13268 C1 2010.06.30
(1)
n
F = F(X ) = γ 0 ⊕ ∑ ⊕ γ j ⋅ E nj (X ),
j=1
где γ (F) = (γ0, γ1,…, γn) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. F.
С.б.ф. Ф = Ф(X), X = (х1, х2,…, хn), называется модулярной, если ее значение на любом
наборе переменных из X однозначно определяется весом V(X) mod p = (x1 + 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.
М.с.б.ф. Ф = Ф(Х) можно задавать p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1,…, ρр-1),
1
0
где ρ j = Ф G i , G n −i , i mod p = j, 0 ≤ i ≤ n , j = 0, p − 1.
(
)
(2)
Очевидно, что ρ(Ф) = (π0, π1,…, πр-1) и, следовательно, при p≥n-1 локальные коды
ρ(Ф) = π(Ф).
Необходимо отметить, что один и тот же модулярный локальный код ρ(Ф) вида (2)
могут иметь м.с.б.ф., зависящие от различного числа n переменных.
В классе с.б.ф. n переменных количество (2p) различных м.с.б.ф. определяется только
величиной модуля p и не зависит от n.
Далее будем рассматривать только модулярные симметрические булевы функций n
переменных Ф = Ф(Х), X = (х1, х2,…, хn), заданные своим модулярным локальным кодом
ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4, ρ5, ρ6) при величине модуля p = 7, n = 9, 10,11,…
Полиномиальное разложение (1) м.с.б.ф. Ф = Ф(Х) при p = 7 имеет вид:
Ф = κ 0 ⊕ κ1 ⋅ R 1n ⊕ κ 2 ⋅ R 2n ⊕ κ3 ⋅ R 3n ⊕ κ3 ⋅ R 4n ⊕ κ3 ⋅ R 5n ⊕ κ3 ⋅ R 6n ⊕ κ3 ⋅ R 7n ,
(3)
где
R in = R in (X ) = ∑ ⊕ E nj (X ), i = 1,6;
(4)
1≤ j≤ n
j mod 7 = i
R 7n = R 7n (X)
∑ ⊕ E (X ) .
1≤ j≤ n
j mod 7 = 0
j
n
(5)
Функции R 1n , R 2n ,L, R 7n назовем полиномиальными м.с.б.ф.
При этом компоненты вектора κ(Ф) = (κ0, κ1, κ2, κ3, κ4, κ5, κ6, κ7) коэффициентов полиномиального разложения м.с.б.ф. Ф = Ф(Х) могут быть определены из модулярного локального кода ρ(Ф) = (ρ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) могут быть
представлены посредством полиномиальных с.б.ф.:
4
BY 13268 C1 2010.06.30
8
(X ) ⊕ E15
R115 = R115 (X ) = E115 (X ) ⊕ E15
15 (X );
2
2
2
9
R15
(X ) = E15
(X ) ⊕ E15
(X );
= R15
3
3
3
R15
(X ) = E15
(X ) ⊕ E10
= R15
15 (X );
4
4
4
(X ) = E15
(X ) ⊕ E11
R15
= R15
15 (X );
5
5
5
(X ) = E15
(X ) ⊕ E12
R15
= R15
15 (X );
6
6
6
(X ) = E15
(X ) ⊕ E13
R15
= R15
15 (X );
7
7
7
R15
= R15
(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 ) = R15
(X ) ⊕ R15
(X ).
(
)
Устройство реализует семь полиномиальных м.с.б.ф. R nj (X ); X = x1 , x 2 ,L, x n ; j = 1,7 ,
зависящих от произвольного числа n переменных для величины модуля p = 7, и построено
согласно следующим соотношениям.
Таблица работы устройства при n = 12.
j
Полиномиальные м.с.б.ф. R12
(X ), j = 1,7
12
V(X ) = ∑ x i
i =1
Входы 72-83
0
1
2
3
4
5
6
7
8
9
10
11
12
R112 / 84
0
1
0
1
0
1
0
1
1
0
1
0
1
2
R12
/ 85
0
0
1
1
0
0
1
1
0
1
1
0
0
3
R12
/ 86
0
0
0
1
0
0
0
1
0
0
1
0
0
5
4
R12
/ 87
0
0
0
0
1
1
1
1
0
0
0
1
1
5
R12
/ 88
0
0
0
0
0
1
0
1
0
0
0
0
1
6
R12
/ 89
0
0
0
0
0
0
1
1
0
0
0
0
0
7
R12
/ 90
0
0
0
0
0
0
0
1
0
0
0
0
0
BY 13268 C1 2010.06.30
R1n +1 (X, x n +1 ) = R1n (X ) ⊕ x n +1 ⊕ x n +1 ⋅ R 7n (X );


R 2n +1 (X, x n +1 ) = R 2n (X ) ⊕ x n +1 ⋅ R1n (X );

R 3n +1 (X, x n +1 ) = R 3n (X ) ⊕ x n +1 ⋅ R 2n (X );


R 4n +1 (X, x n +1 ) = R 4n (X ) ⊕ x n +1 ⋅ R 3n (X );
(7)


5
5
4
R n +1 (X, x n +1 ) = R n (X ) ⊕ x n +1 ⋅ R n (X );


6
6
5
R n +1 (X, x n +1 ) = R n (X ) ⊕ x n +1 ⋅ R n (X );

7
7
6

R n +1 (X, x n +1 ) = R n (X ) ⊕ x n +1 ⋅ R n (X ).

Укажем, что при n = 7 полиномиальные м.с.б.ф. совпадают с полиномиальными с.б.ф.
- R 7j (X ) = E 7j (X ); j = 1,7.
В устройстве блок вычисления полиномиальных симметрических булевых функций
семи переменных 1 реализует полиномиальные м.с.б.ф. R 7j (x1 , x 2 ,K, x 7 ), j = 1,7 , а каждая
группа из семи элементов сложения по модулю два и семи элементов И обеспечивает увеличение числа обрабатываемых переменных на единицу согласно (7).
Устройство для вычисления полиномиальных модулярных симметрических булевых
функций при n = 12 (фигура) работает следующим образом.
На входы 72-83 подаются двоичные переменные x1, x2,…, х12 (в произвольном порядке), на выходах 84, 85,…, 90 реализуются значения полиномиальных м.с.б.ф.
2
2
7
7
R112 = R112 (X), R12
= R12
(X ),K, R12
= R12
(X ) соответственно, X = (x1, x2,…, x12).
Соответствие между весом (числом единиц) V(X) = х1 + х2 +…+ х12 входной двоичной
кодовой комбинации и вектором выходных сигналов устройства приведено в таблице.
Достоинствами устройства для вычисления полиномиальных модулярных симметрических булевых функций n переменных являются простая конструкция, однородная и регулярная структура.
Источники информации:
1. Патент РБ 9051, МПК G 06F 7/00, 2007.
2. Патент РБ 9147, МПК G 06F 7/00, 2007.
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
227 Кб
Теги
by13268, патент
1/--страниц
Пожаловаться на содержимое документа