close

Вход

Забыли?

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

?

Патент BY15727

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.04.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 15727
(13) C1
(19)
G 06F 7/00 (2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091873
(22) 2009.12.28
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 11888 C1, 2009.
BY a20090038, 2009.
BY 12542 C1, 2009.
RU 2018928 C1, 1994.
BY 15727 C1 2012.04.30
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n = 8, 9, 10,…, содержащее блок вычисления модулярных симметрических
булевых функций k переменных, где 4 ≤ k ≤ n–4, выход которого соединен с выходом устройства, а его i-й информационный вход, где i = 1, k , соединен с i-м информационным
входом устройства, отличающееся тем, что содержит пять блоков вычисления модулярных симметрических булевых функций n–k переменных, выход j-го из которых, где
BY 15727 C1 2012.04.30
j = 1, 5 , соединен с j-м настроечным входом блока вычисления модулярных симметриче-
ских булевых функций k переменных, а t-й информационный вход, где t = 1, n − k , соединен с (k + t)-м информационным входом устройства, первый настроечный вход устройства
соединен с первым настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных, пятым настроечным входом второго блока
вычисления модулярных симметрических булевых функций n–k переменных, четвертым
настроечным входом третьего блока вычисления модулярных симметрических булевых
функций n–k переменных, третьим настроечным входом четвертого блока вычисления
модулярных симметрических булевых функций n–k переменных и вторым настроечным
входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных, второй настроечный вход устройства соединен со вторым настроечным входом
первого блока вычисления модулярных симметрических булевых функций n–k переменных, первым настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, пятым настроечным входом третьего блока
вычисления модулярных симметрических булевых функций n–k переменных, четвертым
настроечным входом четвертого блока вычисления модулярных симметрических булевых
функций n–k переменных и третьим настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных, третий настроечный вход
устройства соединен с третьим настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных, вторым настроечным входом
второго блока вычисления модулярных симметрических булевых функций n–k переменных, первым настроечным входом третьего блока вычисления модулярных симметрических булевых функций n–k переменных, пятым настроечным входом четвертого блока
вычисления модулярных симметрических булевых функций n–k переменных и четвертым
настроечным входом пятого блока вычисления модулярных симметрических булевых
функций n–k переменных, четвертый настроечный вход устройства соединен с четвертым
настроечным входом первого блока вычисления модулярных симметрических булевых
функций n–k переменных, третьим настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, вторым настроечным входом
третьего блока вычисления модулярных симметрических булевых функций n–k переменных, первым настроечным входом четвертого блока вычисления модулярных симметрических булевых функций n–k переменных и пятым настроечным входом пятого блока
вычисления модулярных симметрических булевых функций n–k переменных, пятый настроечный вход устройства соединен с пятым настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных, четвертым
настроечным входом второго блока вычисления модулярных симметрических булевых
функций n–k переменных, третьим настроечным входом третьего блока вычисления модулярных симметрических булевых функций n–k переменных, вторым настроечным входом четвертого блока вычисления модулярных симметрических булевых функций n–k
переменных и первым настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных,
содержащее многофункциональный логический модуль с k информационными входами
(k = 1, 2, 3, …) и k + 1 многофункциональных логических модулей с n–k информационными входами [1]. Устройство реализует симметрические булевы функции n переменных,
включая модулярные симметрические булевы функции.
2
BY 15727 C1 2012.04.30
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее n групп элементов 2-2И-2ИЛИ и n
элементов НЕ [2]. Устройство реализует тридцать две модулярные симметрические булевы функции n переменных для величины модуля p = 5.
Недостатком известного устройства является низкое быстродействие.
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства
пяти блоков для вычисления модулярных симметрических булевых функций, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n = 8, 9, 10,…, содержит блок вычисления модулярных симметрических булевых функций k переменных, где 4 ≤ k ≤ n–4, выход которого соединен с выходом
устройства, а его i-й информационный вход, где i = 1, k , соединен с i-м информационным
входом устройства.
В отличие от прототипа, устройство содержит пять блоков вычисления модулярных
симметрических булевых функций n–k переменных, выход j-го из которых, где j = 1, 5 ,
соединен с j-м настроечным входом блока вычисления модулярных симметрических булевых функций k переменных, а t-й информационный вход, где t = 1, n − k , соединен с
(k + t)-м информационным входом устройства.
Первый настроечный вход устройства соединен с первым настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных, пятым настроечным входом второго блока вычисления модулярных симметрических
булевых функций n–k переменных, четвертым настроечным входом третьего блока вычисления модулярных симметрических булевых функций n–k переменных, третьим настроечным входом четвертого блока вычисления модулярных симметрических булевых
функций n–k переменных и вторым настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных.
Второй настроечный вход устройства соединен со вторым настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных,
первым настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, пятым настроечным входом третьего блока вычисления
модулярных симметрических булевых функций n–k переменных, четвертым настроечным
входом четвертого блока вычисления модулярных симметрических булевых функций n–k
переменных и третьим настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных.
Третий настроечный вход устройства соединен с третьим настроечным входом первого блока вычисления модулярных симметрических булевых функций n–k переменных,
вторым настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, первым настроечным входом третьего блока вычисления
модулярных симметрических булевых функций n–k переменных, пятым настроечным входом четвертого блока вычисления модулярных симметрических булевых функций n–k переменных и четвертым настроечным входом пятого блока вычисления модулярных
симметрических булевых функций n–k переменных.
Четвертый настроечный вход устройства соединен с четвертым настроечным входом
первого блока вычисления модулярных симметрических булевых функций n–k переменных, третьим настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, вторым настроечным входом третьего блока
3
BY 15727 C1 2012.04.30
вычисления модулярных симметрических булевых функций n–k переменных, первым настроечным входом четвертого блока вычисления модулярных симметрических булевых
функций n–k переменных и пятым настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных.
Пятый настроечный вход устройства соединен с пятым настроечным входом первого
блока вычисления модулярных симметрических булевых функций n–k переменных, четвертым настроечным входом второго блока вычисления модулярных симметрических булевых функций n–k переменных, третьим настроечным входом третьего блока вычисления
модулярных симметрических булевых функций n–k переменных, вторым настроечным
входом четвертого блока вычисления модулярных симметрических булевых функций n–k
переменных и первым настроечным входом пятого блока вычисления модулярных симметрических булевых функций n–k переменных.
На фигуре представлена схема предлагаемого устройства для вычисления модулярных
симметрических булевых функций n переменных.
Устройство содержит пять блоков вычисления модулярных симметрических булевых
функций n–k переменных 1-5, блок вычисления модулярных симметрических булевых
функций k переменных 6, n информационных входов 71-7n, пять настроечных входов 8-12,
выход 13.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h , h ,K, h ) - некоторый кортеж длины s, содержащий только элементы
h∈{0, 1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (x1, x2,…, xn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. Ф = Ф(X), X = (x1, x2,…, xn), называется модулярной, если ее значение на любом
наборе переменных из 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.
М.с.б.ф. Ф = Ф(X) может быть задана p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1,…, ρp-1),
1
0
где ρ j = Ф(G i , G n −i ) , i modp = j, 0 ≤ i ≤ n, j = 0, p − 1 .
Один и тот же модулярный локальный код ρ(Ф) могут иметь м.с.б.ф., зависящие от
различного числа n переменных. Количество различных м.с.б.ф. n переменных не зависит
от n, а определяется только величиной модуля p и равно 2p.
Модулярная симметрическая булева функция n переменных Ф nj = Ф nj (X) , j = 0, p − 1 ,
называется фундаментальной (ф.м.с.б.ф.), если:
1, если ( x1 + x 2 + K + x n ) mod p = j;
Ф nj = Ф nj (X) =
0, если ( x1 + x 2 + K + x n ) mod p ≠ j,
где p - величина модуля.
В дальнейшем будем рассматривать м.с.б.ф. Ф = Ф(X), заданные своим модулярным
локальным кодом ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4) только для величины модуля p = 5.
Произвольная м.с.б.ф. Ф = Ф(X) n переменных может быть однозначно представлена
посредством ф.м.с.б.ф в виде:
Ф( X ) =
4
∨ ρ j ⋅ Ф n (X).
j
j= 0
(1)
Пусть X = (X1, X2), X1 = (x1, x2,…, xk), X2 = (xk + 1, xk + 2,…, xn), 4 ≤ k ≤ n–4.
4
BY 15727 C1 2012.04.30
Дизъюнктивное разложение м.с.б.ф. Ф = Ф(X) = Ф(X1, X2) по k переменным из X1
представим в виде:
Ф(X ) =
4
∨ Фk (X1) ⋅ ϕ j (X 2 );
j
j= 0
(2)
где ϕj = ϕj(X2), j = 0,4 - "остаточные" м.с.б.ф. от n–k переменных;
Ф kj (X1 ) - ф.м.с.б.ф. от k переменных.
Локальные коды функций ϕj(X2) могут быть определены из локального кода ρ(Ф)
м.с.б.ф. Ф = Ф(X):
ρ(ϕ0 ) = ρ(Ф) = (ρ0 , ρ1 , ρ2 , ρ3 , ρ4 );

ρ(ϕ1 ) = (ρ1 , ρ2 , ρ3 , ρ4 , ρ0 );

ρ(ϕ2 ) = (ρ2 , ρ3 , ρ4 , ρ0 , ρ1 );
(3)


ρ(ϕ3 ) = (ρ3 , ρ4 , ρ0 , ρ1 , ρ2 );


ρ(ϕ4 ) = (ρ4 , ρ0 , ρ1 , ρ2 , ρ3 ).
Первообразной функцией многофункционального логического модуля называется логическое (булево) выражение, устанавливающее связь между реализуемой на выходе модуля булевой функцией и элементами вектора входных переменных и вектора настройки.
Многофункциональные логические модули, реализующие только все 2p м.с.б.ф. n переменных (для рассматриваемой величины модуля p), назовем модулярными. Такие модули являются универсальными в классе м.с.б.ф. и имеют n информационных входов и p
настроечных входов.
Модулярные логические модули, вектором настройки которых на реализацию конкретной м.с.б.ф. Ф = Ф(X) является ее локальный код ρ(Ф) = (ρ0, ρ1,…, ρр-1), назовем модулями ρ-типа.
Пусть Сn(Х, ρ(F)) = Сn(X, ρ0, ρ1, ρ2, ρ3, ρ4) - первообразная функция модуля ρ-типа,
реализующего все м.с.б.ф. n переменных при p = 5.
При описании модулей ρ-типа как "черных ящиков" в качестве первообразной функции Сn(X, ρ(F)) может выступать выражение (1), т.е.:
Cn (X, ρ(F)) =
4
∨ ρ j ⋅ Фn (X).
j
j= 0
(4)
Первообразные функции всех модулей ρ-типа, независимо от их конкретной структуры (схемотехнической реализации), путем тождественных преобразований могут быть
сведены к виду (4), поскольку м.с.б.ф. Ф = Ф(X) однозначно определяется вектором ρ(Ф).
Из анализа выражений (1), (2) и (4) следует, что произвольная м.с.б.ф. n переменных
Ф = Ф(X) может быть реализована на выходе модуля ρ-типа, имеющего k информационных входов (на них подаются двоичные переменные x1-xk из X1) и пять настроечных входов, на которые в качестве сигналов настройки должны подаваться значения "остаточных"
м.с.б.ф. ϕ0(X2)-ϕ4(X2) на соответствующих наборах переменных из X2.
В связи с этим первообразную функцию модуля ρ-типа с n информационными входами можно представить посредством первообразной функции модуля ρ-типа с k информационными входами:
(5)
Сn(X, ρ(F)) = Ck(X1, ϕ0(X2), ϕ1(X2), ϕ2(X2), ϕ3(X2), ϕ4(X2)).
Тогда, принимая во внимание (3), каждую м.с.б.ф. ϕj = ϕj(X2), j = 0, 4 , можно реализовать модулем ρ-типа с n–k информационными входами, а именно:
ϕ0 (X2 ) = Cn − k (X2 , ρ(ϕ0 )) = Cn − k (X2 , ρ0 , ρ1, ρ2 , ρ3 , ρ4 ) =
ρ0 ⋅ Ф0n − k (X2 ) ∨ ρ1 ⋅ Ф1n − k (X2 ) ∨ ρ2 ⋅ Ф2n − k (X2 ) ∨ ρ3 ⋅ Ф3n − k (X2 ) ∨ ρ4 ⋅ Ф4n − k (X2 );
5
BY 15727 C1 2012.04.30
ϕ1 (X 2 ) = C n − k (X 2 , ρ(ϕ1 )) = Cn − k (X 2 , ρ1 , ρ2 , ρ3 , ρ4 , ρ0 ) =
ρ1 ⋅ Ф 0n − k (X 2 ) ∨ ρ2 ⋅ Ф1n − k (X 2 ) ∨ ρ3 ⋅ Ф 2n − k (X 2 ) ∨ ρ4 ⋅ Ф 3n − k (X 2 ) ∨ ρ0 ⋅ Ф 4n − k (X 2 );
ϕ2 (X 2 ) = C n − k (X 2 , ρ(ϕ2 )) = Cn − k (X 2 , ρ2 , ρ3 , ρ4 , ρ0 , ρ1 , ) =
ρ2 ⋅ Ф 0n − k (X 2 ) ∨ ρ3 ⋅ Ф1n − k (X 2 ) ∨ ρ4 ⋅ Ф 2n − k (X 2 ) ∨ ρ0 ⋅ Ф 3n − k (X 2 ) ∨ ρ1 ⋅ Ф 4n − k (X 2 );
ϕ3 (X 2 ) = Cn − k (X 2 , ρ(ϕ3 )) = C n − k (X 2 , ρ3 , ρ4 , ρ0 , ρ1 , ρ2 ) =
ρ3 ⋅ Ф 0n − k (X 2 ) ∨ ρ4 ⋅ Ф1n − k (X 2 ) ∨ ρ0 ⋅ Ф 2n − k (X 2 ) ∨ ρ1 ⋅ Ф 3n − k (X 2 ) ∨ ρ2 ⋅ Ф 4n − k (X 2 );
ϕ4 (X 2 ) = C n − k (X 2 , ρ(ϕ4 )) = Cn − k (X 2 , ρ4 , ρ0 , ρ1 , ρ2 , ρ3 ) =
ρ4 ⋅ Ф 0n − k (X 2 ) ∨ ρ0 ⋅ Ф1n − k (X 2 ) ∨ ρ1 ⋅ Ф 2n − k (X 2 ) ∨ ρ2 ⋅ Ф3n − k (X 2 ) ∨ ρ3 ⋅ Ф 4n − k (X 2 ).
Следовательно, с учетом (5) первообразная функция примет вид:
Сn(X, ρ(Ф)) = Сk(X1, Сn–k(X2, ρ(ϕ0)), Сn–k(X2, ρ(ϕ1)), …, Сn–k(X2, ρ(ϕ4))) (6)
Таким образом, согласно (6) устройство для вычисления м.с.б.ф. n переменных (модулярный логический модуль ρ-типа с n информационными входами) может быть построено
по двухуровневой каскадной схеме, а именно:
первый уровень - модулярный логический модуль ρ-типа с k информационными входами (на них подаются переменные кортежа X1), выход которого соединен с выходом устройства;
второй уровень - пять модулярных логических модулей ρ-типа с n–k информационными входами (на них подаются переменные кортежа X2), выходы которых соединены
соответственно с настроечными входами модуля первого уровня.
При этом настроечные входы устройства в целом организуются путем отождествления
настроечных входов модулей второго уровня в соответствии с (3).
Устройство построено в соответствии с первообразной функцией (6) и при настройке
сигналами из множества {0, 1} реализует тридцать две м.с.б.ф. n переменных при величине модуля p = 5. Вектором настройки устройства на реализацию конкретной м.с.б.ф
Ф = Ф(X) является ее модулярный локальный код ρ(Ф).
Устройство для вычисления модулярных симметрических булевых функций (фигура)
работает следующим образом.
На информационные входы 71-7n подаются двоичные переменные х1-хn (в произвольном порядке), на настроечные входы 8-12 - соответственно компоненты ρ0-ρ4 модулярного
локального кода ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4) м.с.б.ф. Ф = Ф(X), значения которой реализуются
на выходе 13 устройства.
Рассмотренный принцип построения устройств для вычисления м.с.б.ф. n переменных
позволяет строить многоуровневые структуры модулярных логических модулей ρ-типа.
При этом количество модулей на каждом уровне постоянно и равно величине модуля, а
отождествление настроечных входов модулей на каждом уровне осуществляется аналогично, как и для двухуровневой структуры.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, возможность увеличения числа переменных, реализуемых функций.
Источники информации:
1. Патент РБ 11757, МПК G 06F 7/00 // Бюл. № 2 (67). - 30.04.2009
2. Патент РБ 11888, МПК G 06F 7/00 // Бюл. № 2 (67). - 30.04.2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
223 Кб
Теги
патент, by15727
1/--страниц
Пожаловаться на содержимое документа