close

Вход

Забыли?

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

?

Патент BY15775

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.04.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 15775
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091874
(22) 2009.12.28
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 11888 C1, 2009.
BY 3031 C1, 1999.
BY 9994 C1, 2007.
BY 9864 C1, 2007.
BY 15775 C1 2012.04.30
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 6, содержащее многовходовый одноразрядный сумматор по модулю семь,
i-й вход которого, где i = 1, n , соединен с i-м информационным входом устройства, шесть
элементов И и элемент сложения по модулю два, выход которого соединен с выходом
устройства, а первый вход соединен с первым настроечным входом устройства, (j + 1)-й
вход, где j = 1, 6, соединен с выходом j-го элемента И, первый вход которого соединен с
(j + 1)-м настроечным входом устройства, выход младшего разряда многовходового одноразрядного сумматора по модулю семь соединен со вторым входом первого элемента И,
вторым входом третьего элемента И и вторым входом пятого элемента И, выход среднего
разряда многовходового одноразрядного сумматора по модулю семь соединен со вторым
BY 15775 C1 2012.04.30
входом второго элемента И, третьим входом третьего элемента И и вторым входом шестого элемента И, выход старшего разряда многовходового одноразрядного сумматора по
модулю семь соединен со вторым входом четвертого элемента И, третьим входом пятого
элемента И и третьим входом шестого элемента И.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления модулярных симметрических булевых функций
n переменных, содержащее блок вычисления симметрических булевых функций p–1 переменной (p ≤ n - величина модуля), n–p + 1 групп элементов 2-2И-2ИЛИ по p элементов в
каждой, n–p + 1 элементов НЕ, n информационных входов, p настроечных входов и один
выход [1].
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее n элементов НЕ, n групп элементов
2-2И-2ИЛИ, n информационных входов, пять настроечных входов и один выход [2].
Недостатком известного устройства также является низкое быстродействие, определяемое большой глубиной схемы.
Изобретение направлено на решение задачи увеличения быстродействия устройства
для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства многовходового одноразрядного сумматора по модулю семь, шести элементов И, элемента сложения по модулю два, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 6, содержит многовходовый одноразрядный сумматор по модулю семь, i-й
вход которого, где i = 1, n , соединен с i-м информационным входом устройства. Устройство содержит также шесть элементов И и элемент сложения по модулю два, выход которого соединен с выходом устройства, а первый вход соединен с первым настроечным
входом устройства, (j + 1)-й вход, где j = 1, 6, соединен с выходом j-го элемента И, первый
вход которого соединен с (j + 1)-м настроечным входом устройства. Выход младшего разряда многовходового одноразрядного сумматора по модулю семь соединен со вторым
входом первого элемента И, вторым входом третьего элемента И и вторым входом пятого
элемента И. Выход среднего разряда многовходового одноразрядного сумматора по модулю семь соединен со вторым входом второго элемента И, третьим входом третьего элемента И и вторым входом шестого элемента И. Выход старшего разряда многовходового
одноразрядного сумматора по модулю семь соединен со вторым входом четвертого элемента И, третьим входом пятого элемента И и третьим входом шестого элемента И.
На фигуре представлена схема предлагаемого устройства для вычисления модулярных
симметрических булевых функций n переменных.
Устройство содержит многовходовый одноразрядный сумматор по модулю семь 1,
шесть элементов И 2-7, элемент сложения по модулю два 8, n информационных входов 919n, семь настроечных входов 10-16 и выход 17.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h , h , ..., h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0, 1}, и G 0h ≡∅.
2
BY 15775 C1 2012.04.30
Булева функция 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:
Ф G 1i , 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 mod p = j , 0 ≤ i ≤ n, j = 0, p − 1 .
Один и тот же модулярный локальный код ρ(Ф) могут иметь м.с.б.ф., зависящие от
различного числа n переменных. Количество различных м.с.б.ф. n переменных не зависит
от n, а определяется только величиной модуля p и равно 2p.
В дальнейшем будем рассматривать м.с.б.ф. Ф = Ф(X) только для величины модуля
p = 7.
Произвольная м.с.б.ф. Ф = Ф(X) n переменных может быть однозначно представлена в
виде полиномиального разложения:
6
Ф = Ф(X ) = κ 0 ⊕ ∑ ⊕κ j ⋅ Pnj (X ) ,
(1)
j=1
где κ(Ф) = (κ0, κ1,…, κ6) - двоичный вектор коэффициентов полиномиального разложения;
Pnj = Pnj (X ), j = 1, 6 - фундаментальные полиномиальные м.с.б.ф.
Вектор κ(Ф) может быть получен из модулярного локального кода ρ(Ф) методом "треугольника" [Полиномиальное разложение симметрических булевых функций // Известия
АН СССР. Техническая кибернетика. - 1985. - № 4. - С. 123-127]. В этом случае основанием "треугольника" будет являться вектор ρ(Ф), а левой стороной "треугольника" - вектор
κ(Ф).
В предлагаемом устройстве для формирования фундаментальных полиномиальных
м.с.б.ф. Pnj = Pnj (X ), j = 1, 6, используется многовходовый одноразрядный сумматор по модулю семь. Такой сумматор выполняет сложение по модулю семь n одноразрядных двоичных чисел (с весом 20):
S = 4s2 + 2s1 + s0 = (x1 + x2 + … + xn)mod7,
где s2, s1, s0 ∈ {0, 1} - значения м.с.б.ф., формируемых соответственно на выходах старшего, среднего и младшего разрядов сумматора.
Фундаментальные полиномиальные м.с.б.ф. Pnj = Pnj (X ), j = 1, 6, можно представить посредством функций s0 = s0(X), s1 = s1(X) и s2 = s2(X) многовходового одноразрядного сумматора по модулю семь следующим образом:

Pn1 (X ) = s 0 (X );

Pn2 (X ) = s1 (X );

3
Pn (X ) = s1 (X ) ⋅ s 0 (X ); 
(2)

Pn4 (X ) = s 2 (X );

Pn5 (X ) = s 2 (X ) ⋅ s 0 (X );

Pn6 (X ) = s 2 (X ) ⋅ s1 (X ). 
Тогда с учетом (2) полиномиальное разложение (1) примет вид:
Ф(X) = κ0 ⊕ κ1⋅s0(X) ⊕ κ2⋅s1(X) ⊕ κ3⋅s1(X)⋅s0(X) ⊕ κ4⋅s2(X)⊕
⊕ κ5⋅s2(X)⋅s0(X) ⊕ κ6⋅s2(X)⋅s1(X).
3
(3)
BY 15775 C1 2012.04.30
Предлагаемое устройство построено в соответствии с выражением (3), которое и является первообразной (порождающей) функцией. Из (3) непосредственно следует, что вектором настройки устройства на реализацию конкретной м.с.б.ф. Ф = Ф(X) является вектор
коэффициентов полиномиального разложения κ(Ф), компоненты которого находятся из
модулярного локального кода ρ(Ф).
Устройство для вычисления модулярных симметрических булевых функций n переменных (фигура) работает следующим образом.
На информационные входы 91-9n подаются двоичные переменные x1-xn (в произвольном порядке), на настроечные входы 10-16 - соответственно компоненты κ0-κ6 вектора коэффициентов полиномиального разложения κ(Ф) м.с.б.ф. Ф = Ф(Х), значения которой
реализуются на выходе 17 устройства.
Таким образом, предлагаемое устройство при настройке сигналами из множества
{0, 1} реализует 2p = 27 = 128 модулярных симметрических булевых функций n переменных для величины модуля p = 7.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, широкие
функциональные возможности.
Источники информации:
1. Патент РБ 12542, МПК G 06F 7/00 // Бюл. № 5 (70). - 30.10.2009.
2. Патент РБ 11888, МПК G 06F 7/00 // Бюл. № 2 (67). - 30.04.2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
114 Кб
Теги
патент, by15775
1/--страниц
Пожаловаться на содержимое документа