close

Вход

Забыли?

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

?

Патент BY15642

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