close

Вход

Забыли?

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

?

Патент BY15706

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.04.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00 (2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091871
(22) 2009.12.28
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович
(BY)
BY 15706 C1 2012.04.30
BY (11) 15706
(13) C1
(19)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 7588 C1, 2005.
BY 12542 C1, 2009.
RU 2018928 C1, 1994.
RU 2373564 C2, 2009.
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 4, содержащее многовходовый одноразрядный сумматор по модулю пять,
i-й вход которого, где i = 1, n , соединен с i-м информационным входом устройства, отличающееся тем, что содержит два элемента И, три элемента ЗАПРЕТ и элемент ИЛИ, выход которого соединен с выходом устройства, а j-й вход, где j = 1, 2, 3, соединен с выходом j-го элемента ЗАПРЕТ, первый прямой вход которого соединен с j-м настроечным
входом устройства, (l + 3)-й настроечный вход которого, где l = 1, 2, соединен с первым
входом l-го элемента И, выход которого соединен с (l + 3)-м входом элемента ИЛИ, выход
младшего разряда многовходового одноразрядного сумматора по модулю пять соединен с
первым входом запрета первого элемента ЗАПРЕТ, вторым прямым входом второго элемента ЗАПРЕТ, входом запрета третьего элемента ЗАПРЕТ и вторым входом первого элемента И, выход среднего разряда многовходового одноразрядного сумматора по модулю пять
соединен со вторым входом запрета первого элемента ЗАПРЕТ, входом запрета второго
BY 15706 C1 2012.04.30
элемента ЗАПРЕТ, вторым прямым входом третьего элемента ЗАПРЕТ и третьим входом
первого элемента И, выход старшего разряда многовходового одноразрядного сумматора
по модулю пять соединен с третьим входом запрета первого элемента ЗАПРЕТ и вторым
входом второго элемента И.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления модулярных симметрических булевых функций
n переменных, содержащее n групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных входов, пять настроечных входов и один выход [1]. При настройке сигналами из
множества {0, 1} устройство реализует тридцать две модулярные симметрические булевы
функции n переменных для величины модуля p = 5.
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является многовходовый одноразрядный сумматор по модулю
пять, содержащий мажоритарные элементы с четными порогами, элементы сложения по
модулю два и элементы И [2]. На выходах сумматора формируются три модулярные симметрические булевы функции n переменных.
Недостатком известного устройства является невозможность реализации всех тридцати двух модулярных симметрических булевых функций n переменных для величины модуля p = 5.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления всех модулярных симметрических булевых функций n
переменных для величины модуля p = 5.
Названный технический результат достигается путем введения в состав устройства
двух элементов И, трех элементов ЗАПРЕТ, элемента ИЛИ, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 4, содержит многовходовый одноразрядный сумматор по модулю пять, i-й
вход которого, где i = 1, n , соединен с i-м информационным входом устройства.
В отличие от прототипа, устройство содержит два элемента И, три элемента ЗАПРЕТ
и элемент ИЛИ, выход которого соединен с выходом устройства, а j-й вход, где j = 1, 2, 3,
соединен с выходом j-го элемента ЗАПРЕТ, первый прямой вход которого соединен с j-м
настроечным входом устройства.
В устройстве (l + 3)-й настроечный вход, где l = 1, 2, соединен с первым входом l-го
элемента И, выход которого соединен с (l + 3)-м входом элемента ИЛИ.
Выход младшего разряда многовходового одноразрядного сумматора по модулю пять
соединен с первым входом запрета первого элемента ЗАПРЕТ, вторым прямым входом
второго элемента ЗАПРЕТ, входом запрета третьего элемента ЗАПРЕТ и вторым входом
первого элемента И.
Выход среднего разряда многовходового одноразрядного сумматора по модулю пять
соединен со вторым входом запрета первого элемента ЗАПРЕТ, входом запрета второго
элемента ЗАПРЕТ, вторым прямым входом третьего элемента ЗАПРЕТ и третьим входом
первого элемента И.
Выход старшего разряда многовходового одноразрядного сумматора по модулю пять
соединен с третьим входом запрета первого элемента ЗАПРЕТ и вторым входом второго
элемента И.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных.
2
BY 15706 C1 2012.04.30
Устройство содержит многовходовый одноразрядный сумматор по модулю пять l, три
элемента ЗАПРЕТ 2, 3 и 4, два элемента И 5 и 6, элемент ИЛИ 7, n информационных входов 81-8n, пять настроечных входов 9-13 и выход 14.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h, h, ..., h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0, 1}, и G 0h ≡∅.
Булева функция 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 = Ф G1j , G 0n − j ,
(
)
(
)
где i modp = j modp, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
М.с.б.ф. Ф = Ф(X) может быть задана p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1, …, ρp-1),
где ρ j = Ф(G1i , G 0n −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, если (x1 + x 2 + L + x n ) mod p ≠ j,
где p - величина модуля.
В дальнейшем будем рассматривать м.с.б.ф. Ф = Ф(X), заданные своим модулярным
локальным кодом ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4) только для величины модуля p = 5.
Произвольная м.с.б.ф. Ф = Ф(X) n переменных может быть однозначно представлена
посредством ф.м.с.б.ф в виде:
Ф(X ) = ρ 0 ⋅ Ф 0n (X ) ∨ ρ1 ⋅ Ф1n (X ) ∨ ρ 2 ⋅ Ф 2n (X ) ∨ ρ 3 ⋅ Ф 3n (X ) ∨ ρ 4 ⋅ Ф 4n (X ) .
(1)
Модулярные локальные коды ρ(Ф nj ) ф.м.с.б.ф. Ф nj = Ф nj (X ) являются унитарными и
содержат только одну единицу в j-м разряде, а именно:
ρ(Ф 0n ) = (1, 0, 0, 0, 0 );

ρ(Ф1n ) = (0, 1, 0, 0, 0 );

ρ(Ф 2n ) = (0, 0, 1, 0, 0 );
(2)

3
ρ(Ф n ) = (0, 0, 0, 1, 0 );
ρ(Ф 4n ) = (0, 0, 0, 0, 1). 
Многовходовый одноразрядный сумматор по модулю пять выполняет сложение по
модулю пять n одноразрядных двоичных чисел:
S = 4s2 + 2s1 + s0 = (x1 + x2 + … + xn) mod 5,
где s2, s1, s0 ∈ {0, 1} - значения м.с.б.ф., формируемых соответственно на выходах старшего, среднего и младшего разрядов сумматора.
Очевидно, что модулярные локальные коды функций s0 = s0(X), s1 = s1(X) и s2 = s2(X)
имеют вид:
3
BY 15706 C1 2012.04.30
ρ(s 0 ) = (0, 1, 0, 1, 0);

ρ(s1 ) = (0, 0, 1, 1, 0) ; 
(3)

ρ(s 2 ) = (0, 0, 0, 0, 1).
Из анализа (2) и (3) следует, что
ρ Ф 0n = ρ (s 0 ) & ρ(s1 ) & ρ(s 2 );

ρ Ф1n = ρ(s 0 ) & p(s1 );


2
ρ Ф n = ρ(s 0 ) & ρ(s1 );
(4)


3
ρ Ф n = ρ(s 0 ) & ρ(s1 );


ρ Ф 4n = ρ(s 2 ).

Соотношения (4) позволяют записать:
Ф 0n (X ) = s 0 (X ) ⋅ s1 (X ) ⋅ s 2 (X );

Ф1n (X ) = s 0 (X ) ⋅ s1 (X );


2
Ф n (X ) = s 0 (X ) ⋅ s1 (X );
(5)


Ф 3n (X ) = s 0 (X ) ⋅ s1 (X );

4

Ф n (X ) = s 2 (X ).

Тогда с учетом (5) дизъюнктивное разложение (1) примет вид:
Ф(X ) = ρ 0 ⋅ s 0 (X ) ⋅ s1 (X ) ⋅ s 2 (X ) ∨ ρ1 ⋅ s 0 (X ) ⋅ s1 (X ) ∨ ρ 2 ⋅ s 0 (X ) ⋅ s1 (X ) ∨
(6)
∨ ρ3 ⋅ s 0 (X ) ⋅ s1 (X ) ∨ ρ 4 ⋅ s 2 (X ).
Предлагаемое устройство построено в соответствии с выражением (6), которое и является первообразной (порождающей) функцией. При этом вектором настройки устройства
на реализацию конкретной м.с.б.ф Ф = Ф(X) является ее модулярный локальный код
ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4).
Устройство для вычисления модулярных симметрических булевых функций n переменных (фигура) работает следующим образом.
На информационные входы 81-8n подаются двоичные переменные x1-xn (в произвольном порядке), на настроечные входы 9-13 - соответственно компоненты ρ0-ρ4 модулярного
локального кода ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4) м.с.б.ф. Ф = Ф(X), значения которой реализуются
на выходе 14 устройства.
Таким образом, предлагаемое устройство при настройке сигналами из множества {0, 1}
реализует 2p = 25 = 32 модулярных симметрических булевых функций n переменных для
величины модуля p = 5.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, широкие
функциональные возможности.
(
(
(
(
(
)
)
)
)
)
Источники информации:
1. Патент РБ 11888, МПК G 06F 7/00 // Бюл. № 2 (67). - 30.04.2009.
2. Патент РБ 7588, МПК G 06F 7/49, 7/50 // Бюл. № 4 (47). - 30.12.2005 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
93 Кб
Теги
by15706, патент
1/--страниц
Пожаловаться на содержимое документа