close

Вход

Забыли?

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

?

Патент BY15560

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.02.28
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20100021
(22) 2010.01.11
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
BY 15560 C1 2012.02.28
BY (11) 15560
(13) C1
(19)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 12542 C1, 2009.
BY a20090089, 2009.
BY a20090038, 2009.
BY a20090039, 2009.
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 14, характеризующееся тем, что содержит четырнадцать элементов И,
элемент сложения по модулю два и многовходовый одноразрядный сумматор по модулю
пятнадцать, i-й вход которого, где i = 1, n , соединен с i-м информационным входом
устройства, первый настроечный вход которого соединен с первым входом элемента сложения по модулю два, а его (j + 1)-й настроечный вход, где j = 1,14 , соединен с первым
входом j-го элемента И, выход которого соединен с (j + 1)-м входом элемента сложения по
модулю два, выход которого соединен с выходом устройства; выход разряда с весом
"единица" многовходового одноразрядного сумматора по модулю пятнадцать соединен со
вторым входом первого элемента И, вторым входом третьего элемента И, вторым входом
пятого элемента И, вторым входом седьмого элемента И, вторым входом девятого элемента И, вторым входом одиннадцатого элемента И и вторым входом тринадцатого элемента
И; выход разряда с весом "два" многовходового одноразрядного сумматора по модулю
BY 15560 C1 2012.02.28
пятнадцать соединен со вторым входом второго элемента И, третьим входом третьего
элемента И, вторым входом шестого элемента И, третьим входом седьмого элемента И,
вторым входом десятого элемента И, третьим входом одиннадцатого элемента И и вторым
входом четырнадцатого элемента И; выход разряда с весом "четыре" многовходового одноразрядного сумматора по модулю пятнадцать соединен со вторым входом четвертого
элемента И, третьим входом пятого элемента И, третьим входом шестого элемента И, четвертым входом седьмого элемента И, вторым входом двенадцатого элемента И, третьим
входом тринадцатого элемента И и третьим входом четырнадцатого элемента И; выход
разряда с весом "восемь" многовходового одноразрядного сумматора по модулю пятнадцать соединен со вторым входом восьмого элемента И, третьим входом девятого элемента И, третьим входом десятого элемента И, четвертым входом одиннадцатого элемента И,
третьим входом двенадцатого элемента И, четвертым входом тринадцатого элемента И и
четвертым входом четырнадцатого элемента И.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных, содержащее многофункциональный логический модуль с k информационными входами (k = 1,2,3,…) и k + 1 многофункциональных логических модулей с n–k
информационными входами [1]. Устройство реализует симметрические булевы функции n
переменных, включая модулярные симметрические булевы функции.
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее блок вычисления симметрических
булевых функций p–1 переменной (p ≤ n - величина модуля), n–p + 1 групп элементов
2-2И-2ИЛИ по p элементов в каждой, n–p + 1 элементов НЕ, n информационных входов, p
настроечных входов и один выход [2].
При настройке сигналами из множества {0, 1} устройство реализует 2p модулярных
симметрических булевых функций n переменных для величины модуля p.
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства
многовходового одноразрядного сумматора по модулю пятнадцать, элементов И, элемента
сложения по модулю два, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 14, содержит четырнадцать элементов И, элемент сложения по модулю
два и многовходовый одноразрядный сумматор по модулю пятнадцать, i-й вход которого,
где i = 1, n , соединен с i–м информационным входом устройства.
Первый настроечный вход устройства соединен с первым входом элемента сложения
по модулю два, (j + 1)-й настроечный вход, где j = 1,14 , соединен с первым входом j-го
элемента И, выход которого соединен с (j + 1)-м входом элемента сложения по модулю
два, выход которого соединен с выходом устройства.
Выход разряда с весом "единица" многовходового одноразрядного сумматора по модулю пятнадцать соединен со вторым входом первого элемента И, вторым входом третье2
BY 15560 C1 2012.02.28
го элемента И, вторым входом пятого элемента И, вторым входом седьмого элемента И,
вторым входом девятого элемента И, вторым входом одиннадцатого элемента И и вторым
входом тринадцатого элемента И.
Выход разряда с весом "два" многовходового одноразрядного сумматора по модулю
пятнадцать соединен со вторым входом второго элемента И, третьим входом третьего
элемента И, вторым входом шестого элемента И, третьим входом седьмого элемента И,
вторым входом десятого элемента И, третьим входом одиннадцатого элемента И и вторым
входом четырнадцатого элемента И.
Выход разряда с весом "четыре" многовходового одноразрядного сумматора по модулю пятнадцать соединен со вторым входом четвертого элемента И, третьим входом пятого
элемента И, третьим входом шестого элемента И, четвертым входом седьмого элемента И,
вторым входом двенадцатого элемента И, третьим входом тринадцатого элемента И и третьим входом четырнадцатого элемента И.
Выход разряда с весом "восемь" многовходового одноразрядного сумматора по модулю пятнадцать соединен со вторым входом восьмого элемента И, третьим входом девятого элемента И, третьим входом десятого элемента И, четвертым входом одиннадцатого
элемента И, третьим входом двенадцатого элемента И, четвертым входом тринадцатого
элемента И и четвертым входом четырнадцатого элемента И.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных.
Устройство содержит многовходовый одноразрядный сумматор по модулю пятнадцать 1, четырнадцать элементов И 2-15, элемент сложения по модулю два 16, n информационных входов 171-17n, пятнадцать настроечных входов 18-32 и выход 33.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h , h ,K, h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0, 1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (x1, x2,…, xn) называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из 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 ) ,
где imodp = jmodp, 0≤i≤n, 0 ≤ j ≤ n, i ≠ j.
М.с.б.ф. Ф = Ф(X) может быть задана p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ 0 , ρ1 ,K, ρ P −1 ) ,
где ρ j = Ф(G 1i , G 0n −i ) , imodp=j, 0≤i≤n, j = 0, p − 1 .
Один и тот же модулярный локальный код ρ(Ф) может иметь м.с.б.ф., зависящие от
различного числа n переменных. Количество различных м.с.б.ф. n переменных не зависит
от n, а определяется только величиной модуля p и равно 2p.
В дальнейшем будем рассматривать м.с.б.ф. Ф = Ф(X) только для величины модуля
p = 15.
Произвольная м.с.б.ф. Ф = Ф(X) n переменных может быть однозначно представлена в
виде полиномиального разложения:
14
Ф = Ф(X) = κ 0 ⊕ ∑ ⊕ κ j ⋅ Pnj (X) ,
(1)
j=1
где κ(Ф) = (κ0,κ1,…,κ14) - двоичный вектор коэффициентов полиномиального разложения;
Pnj = Pnj (X), j = 1, 14 - фундаментальные полиномиальные м.с.б.ф.
3
BY 15560 C1 2012.02.28
Вектор κ(Ф) может быть получен из модулярного локального кода ρ(Ф) методом "треугольника" (см. Полиномиальное разложение симметрических булевых функций//Известия АН СССР. Техническая кибернетика. 1985. - № 4. - С. 123-127). В этом
случае основанием "треугольника" будет являться вектор ρ(Ф), а левой стороной "треугольника" - вектор κ(Ф).
В устройстве для формирования фундаментальных полиномиальных м.с.б.ф.
j
Pn = Pnj (X), j = 1, 14 , используется многовходовый одноразрядный сумматор по модулю
пятнадцать. Такой сумматор выполняет сложение по модулю пятнадцать n одноразрядных
двоичных чисел (с весом 2°):
S = 8s3 + 4s2 + 2s1 + s0 = (x1 + x2 + … + xn)mod15,
где s3, s2, s1, s0 ∈ {0, 1} - значения м.с.б.ф., формируемые соответственно на выходах разрядов сумматора с весами 23, 22, 21 и 20.
Фундаментальные полиномиальные м.с.б.ф Pnj = Pnj (X), j = 1, 14 можно представить посредством функций si = si(X), i = 0, 3 , многовходового одноразрядного сумматора по модулю пятнадцать следующим образом:
Pn1 (X) = s 0 (X) ;
Pn2 (X) = s1 (X) ;
Pn3 (X) = s1 (X) ⋅ s 0 (X) ;
Pn4 (X) = s 2 (X) ;
Pn5 (X) = s 2 (X) ⋅ s 0 (X) ;
Pn6 (X) = s 2 (X) ⋅ s1 (X) ;
Pn7 (X) = s 2 (X) ⋅ s1 (X) ⋅ s 0 (X) ;
Pn8 (X) = s 3 (X) ;
Pn9 (X) = s 3 (X) ⋅ s 0 (X) ;
Pn10 (X) = s 3 (X) ⋅ s1 (X) ;
Pn11 (X) = s 3 (X) ⋅ s1 (X) ⋅ s 0 (X) ;
Pn12 (X) = s 3 (X) ⋅ s 2 (X) ;
Pn13 (X) = s 3 (X) ⋅ s 2 (X) ⋅ s 0 (X) ;
Pn14 (X) = s 3 (X) ⋅ s 2 (X) ⋅ s1 (X) .
Тогда полиномиальное разложение (1) м.с.б.ф. Ф = Ф(X) примет вид:
Ф(X) = κ0 ⊕ κ1⋅s0 ⊕ κ2⋅s1 ⊕ κ3⋅s1⋅s0 ⊕ κ4⋅s2 ⊕ κ5⋅s2⋅s0 ⊕
(2)
⊕ κ6⋅s2⋅s1 ⊕ κ7⋅s2⋅s1⋅s0 ⊕ κ8⋅s3 ⊕ κ9⋅s3⋅s0 ⊕ κ10⋅s3⋅s1 ⊕
⊕ κ11⋅s3⋅s1⋅s0 ⊕ κ12⋅s3⋅s2 ⊕ κ13⋅s3⋅s2⋅s0 ⊕ κ14⋅s3⋅s2⋅s1.
Предлагаемое устройство построено в точном соответствии с выражением (2), которое
и является первообразной (порождающей) функцией.
Из (2) непосредственно следует также, что вектором настройки устройства на реализацию конкретной м.с.б.ф Ф = Ф(X) является вектор коэффициентов полиномиального
разложения κ(Ф) = (κ0, κ1,…, κ14), компоненты которого находятся из ее модулярного локального кода ρ(Ф) = (ρ0, ρ1,…, ρ14).
Устройство для вычисления модулярных симметрических булевых функций n переменных (фиг. 1) работает следующим образом.
На информационные входы 171-17n подаются двоичные переменные x1-xn (в произвольном порядке), на настроечные входы 18-32 - соответственно компоненты κ0-κ14 век-
4
BY 15560 C1 2012.02.28
тора коэффициентов полиномиального разложения κ(Ф) м.с.б.ф. Ф = Ф(Х), значения которой реализуются на выходе 33 устройства.
Таким образом, предлагаемое устройство при настройке сигналами из множества
{0, 1} реализует 2p = 215 = 32768 модулярных симметрических булевых функций n переменных для величины модуля p = 15.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, широкие
функциональные возможности.
Источники информации:
1. Патент РБ 11757, МПК G 06F 7/00, 2009.
2. Патент РБ 12542, МПК G 06F 7/00, 2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
95 Кб
Теги
by15560, патент
1/--страниц
Пожаловаться на содержимое документа