close

Вход

Забыли?

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

?

Патент BY11837

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 11837
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ АДДИТИВНО
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20070746
(22) 2007.06.18
(43) 2008.02.28
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович;
Кряжев Виктор Иванович; Терешко
Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) SU 1793542 A1, 1993.
SU 1520505 A1, 1989.
BY 11837 C1 2009.04.30
(57)
Устройство для вычисления аддитивно симметрических булевых функций, характеризующееся тем, что содержит одиннадцать элементов 3-2И-3ИЛИ, три элемента И, три элемента сложения по модулю два и три элемента ИЛИ-НЕ, первый вход первого из которых
BY 11837 C1 2009.04.30
соединен с первым информационным входом устройства, первым входом первого элемента сложения по модулю два и первым входом первого элемента И, а его второй вход соединен со вторым информационным входом устройства, вторым входом первого элемента
сложения по модулю два и вторым входом первого элемента И, а его выход соединен с
первым входом первого элемента 3-2И-3ИЛИ, второй вход которого соединен с выходом
первого элемента сложения по модулю два, а его третий вход соединен с выходом первого
элемента И, а его четвертый вход соединен с выходом второго элемента 3-2И-3ИЛИ, а его
пятый вход соединен с выходом третьего элемента 3-2И-3ИЛИ, а его шестой вход соединен с выходом четвертого элемента 3-2И-3ИЛИ, а его выход соединен с выходом устройства, первый вход второго элемента ИЛИ-НЕ соединен с третьим информационным
входом устройства, первым входом второго элемента сложения по модулю два и первым
входом второго элемента И, а его второй вход соединен с четвертым информационным
входом устройства, вторым входом второго элемента сложения по модулю два и вторым
входом второго элемента И, а его выход соединен с первым входом второго элемента
3-2И-3ИЛИ, первым входом третьего элемента 3-2И-3ИЛИ и первым входом четвертого
элемента 3-2И-3ИЛИ, второй вход которого соединен с выходом второго элемента сложения по модулю два, вторым входом второго элемента 3-2И-3ИЛИ и вторым входом
третьего элемента 3-2И-3ИЛИ, а его третий вход соединен с выходом второго элемента И,
третьим входом второго элемента 3-2И-3ИЛИ и третьим входом третьего элемента 3-2И3ИЛИ, четвертый вход второго элемента 3-2И-3ИЛИ соединен с выходом пятого элемента
3-2И-3ИЛИ, а его пятый вход соединен с выходом шестого элемента 3-2И-3ИЛИ, пятый
вход третьего элемента 3-2И-3ИЛИ соединен с выходом седьмого элемента 3-2И-3ИЛИ,
пятый вход четвертого элемента 3-2И-3ИЛИ соединен с выходом восьмого элемента
3-2И-3ИЛИ, а его шестой вход соединен с выходом девятого элемента 3-2И-3ИЛИ, первый вход третьего элемента ИЛИ-НЕ соединен с пятым информационным входом устройства, первым входом третьего элемента сложения по модулю два и первым входом
третьего элемента И, а его второй вход соединен с шестым информационным входом устройства, вторым входом третьего элемента сложения по модулю два и вторым входом
третьего элемента И, а его выход соединен с первым входом пятого элемента 3-2И-3ИЛИ,
первым входом шестого элемента 3-2И-3ИЛИ, первым входом седьмого элемента 3-2И3ИЛИ, первым входом восьмого элемента 3-2И-3ИЛИ и первым входом девятого элемента 3-2И-3ИЛИ, второй вход которого соединен с выходом третьего элемента сложения по
модулю два, вторым входом пятого элемента 3-2И-3ИЛИ, вторым входом шестого элемента 3-2И-3ИЛИ, вторым входом седьмого элемента 3-2И-3ИЛИ и вторым входом восьмого элемента 3-2И-3ИЛИ, а его третий вход соединен с выходом третьего элемента И,
третьим входом пятого элемента 3-2И-3ИЛИ, третьим входом шестого элемента 3-2И3ИЛИ, третьим входом седьмого элемента 3-2И-3ИЛИ и третьим входом восьмого элемента 3-2И-3ИЛИ, четвертый вход пятого элемента 3-2И-3ИЛИ соединен с первым настроечным входом устройства, а его пятый вход соединен со вторым настроечным входом
устройства, пятый вход шестого элемента 3-2И-3ИЛИ соединен с третьим настроечным
входом устройства, пятый вход седьмого элемента 3-2И-3ИЛИ соединен с четвертым настроечным входом устройства, пятый вход восьмого элемента 3-2И-3ИЛИ соединен с пятым настроечным входом устройства, пятый вход девятого элемента 3-2И-3ИЛИ соединен
с шестым настроечным входом устройства, а его шестой вход соединен с седьмым настроечным входом устройства, первый вход десятого элемента 3-2И-3ИЛИ соединен с первым
входом одиннадцатого элемента 3-2И-3ИЛИ и выходом третьего элемента ИЛИ-НЕ, а его
второй вход соединен со вторым входом одиннадцатого элемента 3-2И-3ИЛИ и выходом
третьего элемента сложения по модулю два, а его третий вход соединен с третьим входом
одиннадцатого элемента 3-2И-3ИЛИ и выходом третьего элемента И, а его выход соединен с шестым входом второго элемента 3-2И-3ИЛИ и четвертым входом третьего элемента 3-2И-3ИЛИ, шестой вход которого соединен с выходом одиннадцатого элемента 3-2И2
BY 11837 C1 2009.04.30
3ИЛИ и четвертым входом четвертого элемента 3-2И-3ИЛИ, восьмой настроечный вход
устройства соединен с шестым входом пятого элемента 3-2И-3ИЛИ и четвертым входом
шестого элемента 3-2И-3ИЛИ, девятый настроечный вход устройства соединен с шестым
входом шестого элемента 3-2И-3ИЛИ и четвертым входом десятого элемента 3-2И-3ИЛИ,
пятый вход которого соединен с десятым настроечным входом устройства, одиннадцатый
настроечный вход устройства соединен с шестым входом десятого элемента 3-2И-3ИЛИ и
четвертым входом седьмого элемента 3-2И-3ИЛИ, двенадцатый настроечный вход устройства соединен с шестым входом седьмого элемента 3-2И-3ИЛИ и четвертым входом
одиннадцатого элемента 3-2И-3ИЛИ, пятый вход которого соединен с тринадцатым настроечным входом устройства, четырнадцатый настроечный вход устройства соединен с
шестым входом одиннадцатого элемента 3-2И-3ИЛИ и четвертым входом восьмого элемента 3-2И-3ИЛИ, пятнадцатый настроечный вход устройства соединен с шестым входом
восьмого элемента 3-2И-3ИЛИ и четвертым входом девятого элемента 3-2И-3ИЛИ.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций, содержащее
n групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных входов, n + 1 настроечных входов и один выход [1].
Недостатком устройства являются ограниченные функциональные возможности, поскольку оно не реализует аддитивно симметрические булевы функции.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций, которое при n = 6 содержит три элемента И, три элемента сложения по модулю
два, три элемента ИЛИ-НЕ и девять элементов 3-2И-3ИЛИ [2].
Недостатком известного устройства также является невозможность реализации аддитивно симметрических булевых функций.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления аддитивно симметрических булевых функций.
Названный технический результат достигается путем использования элементов 3-2И3ИЛИ и изменением связей между элементами устройства.
Устройство для вычисления аддитивно симметрических булевых функций содержит
одиннадцать элементов 3-2И-3ИЛИ, три элемента И, три элемента сложения по модулю
два и три элемента ИЛИ-НЕ. Первый вход первого элемента ИЛИ-НЕ соединен с первым
информационным входом устройства, первым входом первого элемента сложения по модулю два и первым входом первого элемента И, второй вход соединен со вторым информационным входом устройства, вторым входом первого элемента сложения по модулю
два и вторым входом первого элемента И, а выход соединен с первым входом первого
элемента 3-2И-3ИЛИ. Второй вход первого элемента 3-2И-3ИЛИ соединен с выходом
первого элемента сложения по модулю два, третий вход соединен с выходом первого элемента И, четвертый вход соединен с выходом второго элемента 3-2И-3ИЛИ, пятый вход
соединен с выходом третьего элемента 3-2И-3ИЛИ, шестой вход соединен с выходом четвертого элемента 3-2И-3ИЛИ, а выход соединен с выходом устройства. Первый вход второго элемента ИЛИ-НЕ соединен с третьим информационным входом устройства, первым
входом второго элемента сложения по модулю два и первым входом второго элемента И,
второй вход соединен с четвертым информационным входом устройства, вторым входом
второго элемента сложения по модулю два и вторым входом второго элемента И, а выход
соединен с первым входом второго элемента 3-2И-3ИЛИ, первым входом третьего элемента 3-2И-3ИЛИ и первым входом четвертого элемента 3-2И-3ИЛИ. Второй вход четвертого элемента 3-2И-3ИЛИ соединен с выходом второго элемента сложения по модулю
3
BY 11837 C1 2009.04.30
два, вторым входом второго элемента 3-2И-3ИЛИ и вторым входом третьего элемента
3-2И-3ИЛИ, третий вход соединен с выходом второго элемента И, третьим входом второго элемента 3-2И-3ИЛИ и третьим входом третьего элемента 3-2И-3ИЛИ. Четвертый вход
второго элемента 3-2И-3ИЛИ соединен с выходом пятого элемента 3-2И-3ИЛИ, пятый
вход соединен с выходом шестого элемента 3-2И-3ИЛИ. Пятый вход третьего элемента
3-2И-3ИЛИ соединен с выходом седьмого элемента 3-2И-3ИЛИ. Пятый вход четвертого
элемента 3-2И-3ИЛИ соединен с выходом восьмого элемента 3-2И-3ИЛИ, а его шестой
вход соединен с выходом девятого элемента 3-2И-3ИЛИ. Первый вход третьего элемента
ИЛИ-НЕ соединен с пятым информационным входом устройства, первым входом третьего элемента сложения по модулю два и первым входом третьего элемента И, второй вход
соединен с шестым информационным входом устройства, вторым входом третьего элемента сложения по модулю два и вторым входом третьего элемента И, а выход соединен с
первым входом пятого элемента 3-2И-3ИЛИ, первым входом шестого элемента 3-2И3ИЛИ, первым входом седьмого элемента 3-2И-3ИЛИ, первым входом восьмого элемента
3-2И-3ИЛИ и первым входом девятого элемента 3-2И-3ИЛИ. Второй вход девятого элемента 3-2И-3ИЛИ соединен с выходом третьего элемента сложения по модулю два, вторым входом пятого элемента 3-2И-3ИЛИ, вторым входом шестого элемента 3-2И-3ИЛИ,
вторым входом седьмого элемента 3-2И-3ИЛИ и вторым входом восьмого элемента 3-2И3ИЛИ, третий вход соединен с выходом третьего элемента И, третьим входом пятого элемента 3-2И-3ИЛИ, третьим входом шестого элемента 3-2И-3ИЛИ, третьим входом седьмого элемента 3-2И-3ИЛИ и третьим входом восьмого элемента 3-2И-3ИЛИ. Четвертый
вход пятого элемента 3-2И-3ИЛИ соединен с первым настроечным входом устройства,
пятый вход соединен со вторым настроечным входом устройства. Пятый вход шестого
элемента 3-2И-3ИЛИ соединен с третьим настроечным входом устройства. Пятый вход
седьмого элемента 3-2И-3ИЛИ соединен с четвертым настроечным входом устройства.
Пятый вход восьмого элемента 3-2И-3ИЛИ соединен с пятым настроечным входом устройства. Пятый вход девятого элемента 3-2И-3ИЛИ соединен с шестым настроечным входом устройства, шестой вход соединен с седьмым настроечным входом устройства.
Первый вход десятого элемента 3-2И-3ИЛИ соединен с первым входом одиннадцатого
элемента 3-2И-3ИЛИ и выходом третьего элемента ИЛИ-НЕ, второй вход соединен со
вторым входом одиннадцатого элемента 3-2И-3ИЛИ и выходом третьего элемента сложения по модулю два, третий вход соединен с третьим входом одиннадцатого элемента
3-2И-3ИЛИ и выходом третьего элемента И, а выход соединен с шестым входом второго
элемента 3-2И-3ИЛИ и четвертым входом третьего элемента 3-2И-3ИЛИ. Шестой вход
третьего элемента 3-2И-3ИЛИ соединен с выходом одиннадцатого элемента 3-2И-3ИЛИ и
четвертым входом четвертого элемента 3-2И-3ИЛИ. Восьмой настроечный вход устройства соединен с шестым входом пятого элемента 3-2И-3ИЛИ и четвертым входом шестого
элемента 3-2И-3ИЛИ. Девятый настроечный вход устройства соединен с шестым входом
шестого элемента 3-2И-3ИЛИ и четвертым входом десятого элемента 3-2И-3ИЛИ, пятый
вход которого соединен с десятым настроечным входом устройства. Одиннадцатый настроечный вход устройства соединен с шестым входом десятого элемента 3-2И-3ИЛИ и
четвертым входом седьмого элемента 3-2И-3ИЛИ. Двенадцатый настроечный вход устройства соединен с шестым входом седьмого элемента 3-2И-3ИЛИ и четвертым входом
одиннадцатого элемента 3-2И-3ИЛИ, пятый вход которого соединен с тринадцатым настроечным входом устройства. Четырнадцатый настроечный вход устройства соединен с
шестым входом одиннадцатого элемента 3-2И-3ИЛИ и четвертым входом восьмого элемента 3-2И-3ИЛИ. Пятнадцатый настроечный вход устройства соединен с шестым входом
восьмого элемента 3-2И-3ИЛИ и четвертым входом девятого элемента 3-2И-3ИЛИ.
На фигуре представлена схема устройства для вычисления аддитивно симметрических
булевых функций.
4
BY 11837 C1 2009.04.30
Устройство содержит три элемента ИЛИ-НЕ 1, 2 и 3, три элемента сложения по модулю два 4, 5 и 6, три элемента И 7, 8 и 9, одиннадцать элементов 3-2И-3ИЛИ 10-20, шесть
информационных входов 21-26, пятнадцать настроечных входов 27-41 и один выход 42.
Поясним принцип построения и работы предлагаемого устройства.
Обозначим: G sh = (h , h , K, h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0, 1}, и G 0h ≡ ∅.
Нетривиальная частичная симметрия индуцирует разбиение вектора переменных
X = (х1, х2, …, хn) частично симметрической булевой функции (ч.с.б.ф.) f = f(X) на N кортежей Х1, Х2, …, XN, 1 < N < n. При этом f симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу Хi, 1 ≤ i ≤ N.
В классе ч.с.б.ф. выделяется подкласс функций, обладающих так называемой аддитивной симметрией.
Пусть f = f(X) - ч.с.б.ф., зависящая от N кортежей попарно симметрических перемен-
(
) ∑ k i = n , 1 < N < n.
ных X1, X2, …, XN и X = (Х1, Х2, …, XN), X i = x1i , x i2 , K, x ik i ,
N
i =1
Определение 1. Частично симметрическая булева функция f = f(X) обладаeт аддитивной симметрией, если и только если при
N
N
i =1
i =1
∑ a i ⋅ 2 N−i = ∑ bi ⋅ 2 N −i , 0 ≤ ai ≤ki, 0 ≤ bi ≤ ki, и для
i1≠i2, 1 ≤ i1 ≤ N, 1 ≤ i2 ≤ N, есть a i1 ≠ bi1 и a i 2 ≠ b i 2 такие, что имеет место:
f (G 0k1 −a1 , G1a1 , G 0k 2 −a 2 , G1a 2 ,K, G 0k N − a N , G1a N ) = f (G 0k1 −b1 , G1b1 , G 0k 2 − b 2 , G1b 2 ,K, G 0k N − b N , G1b N ).
Таким образом, переменные кортежей Xi, i = 1, N , имеют вес, равный 2N-i, а значение
а.с.б.ф. f = f(X) на каждом данном наборе определяется суммой весов переменных, имеющих единичные значения на данном наборе.
Определение 2. Свернутым локальным кодом а.с.б.ф. f = f(X) называется двоичный
вектор S(f) = (s0, s1,…, sL), в котором элемент sR равен значению f на наборах переменных
из Х1, Х2, ..., XN, удовлетворяющих условию:
N ki
∑ ∑ x iji ⋅ 2 N − i = R ; 0 ≤ R ≤ L, ji= 1, k i ,
(1)
i =1 ji =1
N
где L = ∑ k i ⋅ 2 N − i .
i =1
Предлагаемое устройство реализует 2L+1 = 215 = 32768 аддитивно симметрических
булевых функций f = f(X) = f(X1, Х2, Х3) шести переменных (три пары попарно симметрических переменных Х1 = (x1, х2), Х2 = (х3, х4), Х3 = (х5, х6) и N = 3, k1 = k2 = k3 = 2) при настройке сигналами из множества {0, 1}.
Вектором настойки устройства на реализацию конкретной а.с.б.ф. f = f(X) является ее
свернутый локальный код S(f) = (s0, s1, …, s14).
Согласно (1), некоторый элемент sR, 0 ≤ R ≤ 14, локального кода S(f) равен значению
а.с.б.ф. f на наборах переменных из Х1, Х2, Х3 при условии:
4х1 + 4х2 + 2х3 + 2х4 + х5 + х6 = R.
Устройство для вычисления аддитивно симметрических булевых функций (фигура)
работает следующим образом.
На информационные входы 21 и 22 подаются двоичные переменные х1 и х2 кортежа
Х1 (в произвольном порядке), на информационные входы 23 и 24 - двоичные переменные
х3 и х4 кортежа Х2 (в произвольном порядке), на информационные входы 25 и 26 - двоичные переменные х5 и х6 кортежа Х3 (в произвольном порядке), на настроечные входы 27,
5
BY 11837 C1 2009.04.30
28, …, 41 - соответственно компоненты s0, s1,…, s14 локального кода S(f) а.с.б.ф.
f = f(X) = (X1, X2, X3), значения которой реализуются на выходе 42 устройства.
Достоинствами устройства для вычисления аддитивно симметрических булевых функций являются простая конструкция, высокое быстродействие и широкие функциональные
возможности.
Источники информации:
1. А.с. СССР 1742811, МПК G 06F 7/00, 1992.
2. А.с. СССР 1793542, МПК Н 03K 19/094, 1993 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
230 Кб
Теги
by11837, патент
1/--страниц
Пожаловаться на содержимое документа