close

Вход

Забыли?

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

?

15776

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.04.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 15776
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091875
(22) 2009.12.28
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 11304 C1, 2008.
BY a 20090038, 2009.
BY 11752 C1, 2009.
BY 7590 C1, 2005.
BY 15776 C1 2012.04.30
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ p–1, где p ≥ 3 - величина модуля, содержащее блок вычисления веса двоичных кодовых комбинаций по модулю p, i-й вход которого, где i = 1, n , соединен с i-м
информационным входом устройства, элемент ИЛИ и p элементов И, первый вход j-го из
которых, где j = 1, p , соединен с выходом "равно j–1 по модулю p" блока вычисления веса
двоичных кодовых комбинаций по модулю p, второй вход - с j-м настроечным входом
устройства, а выход - с j-м входом элемента ИЛИ, выход которого соединен с выходом
устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления модулярных симметрических булевых функций n
переменных, содержащее блок вычисления симметрических булевых функций p–1 переменной (p ≤ n - величина модуля), n–p + 1 групп элементов 2-2И-2ИЛИ по p элементов в каждой,
n–p + 1 элементов НЕ, n информационных входов, p настроечных входов и один выход [1].
BY 15776 C1 2012.04.30
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления веса двоичных кодовых
комбинаций по модулю семь, содержащее блок формирования унитарного двоичного кода, k групп элементов 3-2И-3ИЛИ по семь элементов в каждой, k элементов И, k элементов сложения по модулю два и k элементов ИЛИ-НЕ (k = 1, 2, 3, …; n = 2k + 6 разрядность входного слова) [2]. На выходах устройства формируются фундаментальные
модулярные симметрические булевы функции n переменных.
Недостатком известного устройства является невозможность реализации произвольных модулярных симметрических булевых функций n переменных для различных значений модуля p.
Изобретение направлено на решение задачи расширения функциональных возможностей
устройства для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства
элемента ИЛИ и p элементов И, а также изменением межсоединений элементов в схеме
устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ p–1, где p ≥ 3 - величина модуля, содержит блок вычисления веса двоичных кодовых комбинаций по модулю p, i-й вход которого, где i = 1, n , соединен с i-м
информационным входом устройства. Устройство содержит также элемент ИЛИ и p элементов И. Первый вход j-го элемента И, где j = 1, p , соединен с выходом "равно j–1 по модулю p" блока вычисления веса двоичных кодовых комбинаций по модулю p, второй вход
соединен с j-м настроечным входом устройства, а выход соединен с j-м входом элемента
ИЛИ. Выход элемента ИЛИ соединен с выходом устройства.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных.
Устройство содержит блок вычисления веса двоичных кодовых комбинаций по модулю p (n ≥ p–1, p ≥ 3) 1, p элементов И 21-2p, элемент ИЛИ 3, n информационных входов 414n, p настроечных входов 51-5p и выход 6.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h , h ,..., h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0, 1}, и G 0h ≡∅.
Булева функция F = F(X), X = (x1, x2, …, xn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
(1)
π(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.
С.б.ф. Ф = Ф(X), X = (x1, x2, …, xn), называется модулярной (м.с.б.ф.), если ее значение
на любом наборе переменных из X однозначно определяется весом V(X)mod p =
= (x1 + x2 + … + xn)mod p двоичной кодовой комбинации по модулю p, p ≤ n:
Ф G 1i , G 0n −i = Ф G1j , G 0n − j ,
(2)
где
(3)
i mod p = j mod p, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном
коде π(Ф) = (π0, π1, …, πn) м.с.б.ф. Ф = Ф(X) элементы πi = πj.
(
)
(
)
2
BY 15776 C1 2012.04.30
Тогда локальный код м.с.б.ф. Ф = Ф(X) можно представить в виде:
π(Ф ) = (π 0 , π1 ,..., π p−1 , π 0 , π1 ,..., π p−1 ,..., π 0 , π1 ,..., π p−1 , π 0 , π1 ,..., π n −kp ) ,
142
4 43
4 142
4 43
4
142
4 43
4
1
2
(4)
k
где k = [(n+1)/p].
Принимая во внимание (4), м.с.б.ф. Ф = Ф(X) можно задавать p-разрядным модулярным локальным кодом:
(5)
ρ(Ф) = (ρ0, ρ1, …, ρp-1),
1
0
где ρ j = Ф(G i , G n −i ), i mod p = j , 0 ≤ i ≤ n, j = 0, p − 1 .
Очевидно, что ρ(Ф) = (π0, π1, …, πp-1), и, следовательно, при p ≥ n–1 локальные коды
ρ(Ф) = π(Ф). Кроме того, один и тот же модулярный локальный код ρ(Ф) вида (5) могут
иметь м.с.б.ф., зависящие от различного числа n переменных.
В классе с.б.ф. n переменных количество (2p) различных м.с.б.ф. определяется только
величиной модуля p и не зависит от n.
Модулярная симметрическая булева функция n переменных Ф nj = Ф nj (X ), 0 ≤ j ≤ 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) n переменных может быть однозначно
представлена посредством ф.м.с.б.ф. в виде:
Ф(X ) = ρ 0 ⋅ Ф 0n (X ) ∨ ρ1 ⋅ Ф1n (X ) ∨ ... ∨ ρ p−1 ⋅ Ф pn−1 (X).
(6)
Предлагаемое устройство построено согласно выражению (6).
Отметим, что ф.м.с.б.ф. Ф nj = Ф nj (X ) , 0 ≤ j ≤ p–1 реализуется на выходе "равно j–1 по
модулю p" блока вычисления веса двоичных кодовых комбинаций по модулю p, на входы
которого подаются двоичные переменные из X.
Из (6) непосредственно следует, что вектором настройки устройства на реализацию
конкретной м.с.б.ф Ф. = Ф(X) является ее модулярный локальный код ρ(Ф).
Устройство для вычисления модулярных симметрических булевых функций n переменных (фигура) работает следующим образом.
На информационные входы 41-4n подаются двоичные переменные x1-xn (в произвольном порядке), на настроечные входы 51-5p - соответственно компоненты ρ0-ρp-1 модулярного локального кода ρ(Ф) = (ρ0, ρ1, …, ρp-1) м.с.б.ф. Ф = Ф(X), значения которой
реализуются на выходе 6 устройства.
Таким образом, предлагаемое устройство при настройке сигналами из множества
{0, 1} реализует 2p модулярных симметрических булевых функций n переменных для произвольной величины модуля p.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, широкие
функциональные возможности.
Источники информации:
1. Патент РБ 12542, МПК G 06F 7/00, 2009.
2. Патент РБ 11304, МПК G 06F 7/00, Н 03М 7/00, 2008 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
3
Документ
Категория
Без категории
Просмотров
0
Размер файла
78 Кб
Теги
15776
1/--страниц
Пожаловаться на содержимое документа