close

Вход

Забыли?

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

?

Патент BY14010

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2011.02.28
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 14010
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(21) Номер заявки: a 20090038
(22) 2009.01.13
(43) 2009.06.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Терешко Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY a20070747, 2008.
BY a20060921, 2007.
BY a20071257, 2008.
BY 14010 C1 2011.02.28
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n = 2m, а m = 4, 5, 6, … , характеризующееся тем, что содержит m–2 группы элементов 3-2И-3ИЛИ, по пять элементов в каждой, (m–1)-ю группу элементов 3-2И-3ИЛИ из
трех элементов, элемент 3-2И-3ИЛИ, m элементов ИЛИ-НЕ, m элементов сложения по модулю два и m элементов И, при этом (2k + j – 2)-й, где k = 1, m , где j = 1, 2, информационный
BY 14010 C1 2011.02.28
вход устройства соединен с j-м входом k-го элемента ИЛИ-НЕ, j-м входом k-го элемента
сложения по модулю два и j-м входом k-го элемента И, выход h-го, где h = 1, m − 2 , элемента ИЛИ-НЕ соединен с первым входом l-го, где l = 1,5 , элемента 3-2И-3ИЛИ h-й группы, второй вход которого соединен с выходом h-го элемента сложения по модулю два,
третий вход соединен с выходом h-го элемента И, выход (m–1)-го элемента ИЛИ-НЕ соединен с первым входом s-го, где s = 1, 2, 3, элемента 3-2И-3ИЛИ (m–1)-й группы, второй
вход которого соединен с выходом (m–1)-го элемента сложения по модулю два, третий
вход соединен с выходом (m–1)-го элемента И, выход m-го элемента ИЛИ-НЕ соединен с
первым входом элемента 3-2И-3ИЛИ, второй вход которого соединен с выходом m-го
элемента сложения по модулю два, третий вход соединен с выходом m-го элемента И,
первый настроечный вход устройства соединен с четвертым входом первого элемента 32И-3ИЛИ первой группы, шестым входом четвертого элемента 3-2И-3ИЛИ первой группы и пятым входом пятого элемента 3-2И-3ИЛИ первой группы, второй настроечный вход
устройства соединен с пятым входом первого элемента 3-2И-3ИЛИ первой группы, четвертым входом второго элемента 3-2И-3ИЛИ первой группы и шестым входом пятого
элемента 3-2И-3ИЛИ первой группы, (s + 2)-й настроечный вход устройства соединен с
шестым входом s-го элемента 3-2И-3ИЛИ первой группы, пятым входом (s + 1)-го элемента 3-2И-3ИЛИ первой группы и четвертым входом (s + 2)-го элемента 3-2И-3ИЛИ
первой группы, выход первого элемента 3-2И-3ИЛИ i-й, где i = 1, m − 3 , группы соединен
с четвертым входом первого элемента 3-2И-3ИЛИ (i + 1)-й группы, шестым входом четвертого элемента 3-2И-3ИЛИ (i + 1)-й группы и пятым входом пятого элемента 3-2И3ИЛИ (i + 1)-й группы, выход второго элемента 3-2И-3ИЛИ i-й группы соединен с пятым
входом первого элемента 3-2И-3ИЛИ (i + 1)-й группы, четвертым входом второго элемента 3-2И-3ИЛИ (i + 1)-й группы и шестым входом пятого элемента 3-2И-3ИЛИ (i + 1)-й
группы, выход (s + 2)-го элемента 3-2И-3ИЛИ i-й группы соединен с шестым входом s-го
элемента 3-2И-3ИЛИ (i + 1)-й группы, пятым входом (s + 1)-го элемента 3-2И-3ИЛИ
(i + 1)-й группы и четвертым входом (s + 2)-го элемента 3-2И-3ИЛИ (i + 1)-й группы, выход первого элемента 3-2И-3ИЛИ (m–2)-й группы соединен с четвертым входом первого
элемента 3-2И-3ИЛИ (m–1)-й группы, выход второго элемента 3-2И-3ИЛИ (m–2)-й группы соединен с пятым входом первого элемента 3-2И-3ИЛИ (m–1)-й группы и четвертым
входом второго элемента 3-2И-3ИЛИ (m–1)-й группы, выход третьего элемента
3-2И-3ИЛИ (m–2)-й группы соединен с шестым входом первого элемента 3-2И-3ИЛИ
(m–1)-й группы, пятым входом второго элемента 3-2И-3ИЛИ (m–1)-й группы и четвертым
входом третьего элемента 3-2И-3ИЛИ (m–1)-й группы, выход четвертого элемента
3-2И-3ИЛИ (m–2)-й группы соединен с шестым входом второго элемента 3-2И-3ИЛИ
(m–1)-й группы и пятым входом третьего элемента 3-2И-3ИЛИ (m–1)-й группы, выход пятого элемента 3-2И-3ИЛИ (m–2)-й группы соединен с шестым входом третьего элемента
3-2И-3ИЛИ (m–1)-й группы, выход s-го элемента 3-2И-3ИЛИ (m–1)-й группы соединен с
(s + 3)-m входом элемента 3-2И-3ИЛИ, выход которого соединен с выходом устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных, содержащее n групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных
входов, n + 1 настроечных входов и один выход [1].
Устройство реализует все симметрические (в том числе и модулярные симметрические) булевы функции n переменных.
Недостатком известного устройства является высокая конструктивная сложность.
2
BY 14010 C1 2011.02.28
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее 5n–10 элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных входов, пять настроечных входов и один выход [2].
Недостатком известного устройства является низкое быстродействие, определяемое
большой глубиной схемы.
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем применения в схеме устройства
новых типов логических элементов (элементы 3-2И-3ИЛИ, ИЛИ-НЕ, И, сложение по модулю два), а также изменением межсоединений логических элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных содержит m–2, где m = 4, 5, 6, …, где n = 2m - число переменных реализуемых
функций, группы элементов 3-2И-3ИЛИ, по пять элементов в каждой, (m–1)-ю группу
элементов 3-2И-3ИЛИ из трех элементов, элемент 3-2И-3ИЛИ, m элементов ИЛИ-НЕ, m
элементов сложения по модулю два и m элементов И.
При этом (2k + j – 2)-й, где k = 1, m , где j = 1, 2, информационный вход устройства соединен с j-м входом k-го элемента ИЛИ-НЕ, j-м входом k-го элемента сложения по модулю два и j-м входом k-го элемента И.
Выход h-го, где h = 1, m − 2 , элемента ИЛИ-НЕ соединен с первым входом l-го, где
l = 1, 5 , элемента 3-2И-3ИЛИ h-й группы, второй вход которого соединен с выходом h-го
элемента сложения по модулю два, третий вход соединен с выходом h-го элемента И.
Выход (m–1)-го элемента ИЛИ-НЕ соединен с первым входом s-го, где s = 1, 2, 3, элемента 3-2И-3ИЛИ (m–1)-й группы, второй вход которого соединен с выходом (m–1)-го
элемента сложения по модулю два, третий вход соединен с выходом (m–1)-го элемента И.
Выход m-го элемента ИЛИ-НЕ соединен с первым входом элемента 3-2И-3ИЛИ, второй вход которого соединен с выходом m-го элемента сложения по модулю два, третий
вход соединен с выходом m-го элемента И.
Первый настроечный вход устройства соединен с четвертым входом первого элемента
3-2И-3ИЛИ первой группы, шестым входом четвертого элемента 3-2И-3ИЛИ первой
группы и пятым входом пятого элемента 3-2И-3ИЛИ первой группы.
Второй настроечный вход устройства соединен с пятым входом первого элемента
3-2И-3ИЛИ первой группы, четвертым входом второго элемента 3-2И-3ИЛИ первой группы и шестым входом пятого элемента 3-2И-3ИЛИ первой группы.
В устройстве (s + 2)-й настроечный вход соединен с шестым входом s-го элемента
3-2И-3ИЛИ первой группы, пятым входом (s + 1)-го элемента 3-2И-3ИЛИ первой группы
и четвертым входом (s + 2)-го элемента 3-2И-3ИЛИ первой группы.
Выход первого элемента 3-2И-3ИЛИ i-й, где i = 1, m − 3 , группы соединен с четвертым
входом первого элемента 3-2И-3ИЛИ (i + 1)-й группы, шестым входом четвертого элемента 3-2И-3ИЛИ (i + 1)-й группы и пятым входом пятого элемента 3-2И-3ИЛИ (i + 1)-й
группы.
Выход второго элемента 3-2И-3ИЛИ i-й группы соединен с пятым входом первого
элемента 3-2И-3ИЛИ (i + 1)-й группы, четвертым входом второго элемента 3-2И-3ИЛИ
(i + 1)-й группы и шестым входом пятого элемента 3-2И-3ИЛИ (i + 1)-й группы.
Выход (s + 2)-го элемента 3-2И-3ИЛИ i-й группы соединен с шестым входом s-го элемента 3-2И-3ИЛИ (i + 1)-й группы, пятым входом (s + 1)-го элемента 3-2И-3ИЛИ (i + 1)-й
группы и четвертым входом (s + 2)-го элемента 3-2И-3ИЛИ (i + 1)-й группы.
Выход первого элемента 3-2И-3ИЛИ (m–2)-й группы соединен с четвертым входом
первого элемента 3-2И-3ИЛИ (m–1)-й группы.
3
BY 14010 C1 2011.02.28
Выход второго элемента 3-2И-3ИЛИ (m–2)-й группы соединен с пятым входом первого элемента 3-2И-3ИЛИ (m–1)-й группы и четвертым входом второго элемента 3-2И3ИЛИ (m–1)-й группы.
Выход третьего элемента 3-2И-3ИЛИ (m–2)-й группы соединен с шестым входом первого элемента 3-2И-3ИЛИ (m–1)-й группы, пятым входом второго элемента 3-2И-3ИЛИ
(m–1)-й группы и четвертым входом третьего элемента 3-2И-3ИЛИ (m–1)-й группы.
Выход четвертого элемента 3-2И-ЗИЛИ (m–2)-й группы соединен с шестым входом
второго элемента 3-2И-3ИЛИ (m–1)-й группы и пятым входом третьего элемента 3-2ИЗИЛИ (m–1)-й группы.
Выход пятого элемента 3-2И-3ИЛИ (m–2)-й группы соединен с шестым входом третьего элемента 3-2И-3ИЛИ (m–1)-й группы.
Выход s-го элемента 3-2И-3ИЛИ (m–1)-й группы соединен с (s + 3)-м входом элемента
3-2И-3ИЛИ, выход которого соединен с выходом устройства.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных при n = 12 (m = 6) и величине модуля p = 5.
Устройство (фигура) содержит 5m–6 = 24 элементов 3-2И-3ИЛИ 1-24, m = 6 элементов
ИЛИ-НЕ 25-30, m = 6 элементов сложения по модулю два 31-36, m = 6 элементов И 37-42,
n = 12 информационных входов 43-54, p = 5 настроечных входов 55-59 и выход 60.
Обозначим: G sh = (h , h , …, h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0, 1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (х1, х2, …, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
π (F) = (π0, π1, …, πn),
l
0
где πi = F G i , G n − i , i = 0, n.
Таким образом, вес двоичной кодовой комбинации V(X) = xl + x2 + … + xn однозначно
определяет значение с.б.ф. F = F(X) на данном наборе переменных из X.
С.б.ф. Ф = Ф(X), X = (х1, х2, …, хn), называется модулярной (м.с.б.ф.), если ее значение
на любом наборе переменных из X однозначно определяется весом V(X)mod p = (x1 + x2 +
+… + xn)mod p двоичной кодовой комбинации по модулю p, р≤n:
Ф G il , G 0n − i = Ф G lj , G 0n − j ,
(
)
(
)
(
)
где i mod p = j mod p, 0≤i≤n, 0≤j≤n, i≠j.
Очевидно, что при величине модуля p = 5 м.с.б.ф. Ф = Ф(X) можно задавать пятиразрядным модулярным локальным кодом
p(Ф) = (p0, p1, p2, p3, p4),
l
0
где p j = Ф G i , G n −i , i mod 5 = j, 0≤i≤n, j = 0, 4 .
При этом один и тот же модулярный локальный код p(Ф) могут иметь м.с.б.ф., зависящие от различного числа n переменных, а в классе с.б.ф. n переменных количество
(2p = 25 = 32) различных м.с.б.ф. определяется только величиной модуля p = 5 и не зависит
от n.
Предлагаемое устройство в общем случае при настройке сигналами из множества
{0, 1} реализует тридцать две модулярные симметрические булевы функции n переменных для величины модуля p = 5.
Устройство для вычисления модулярных симметрических булевых функций при
n = 12 (фигура) работает следующим образом.
На информационные входы 43-54 подаются двоичные переменные х1-х12 (в произвольном порядке), на настроечные входы 55-59 - соответственно компоненты p0-p4 моду-
(
)
4
BY 14010 C1 2011.02.28
лярного локального кода p(Ф) = (p0, p1, p2, p3, p4) м.с.б.ф. Ф = Ф(X) = Ф(х1, х2, …, х12), значения которой реализуются на выходе 60 устройства.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, однородная и регулярная структура.
Источники информации:
1. А.с. СССР 1742811, МПК G 06F 7/00, 1992.
2. Патент РБ 11888, МПК G 06F 7/00, 2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
100 Кб
Теги
патент, by14010
1/--страниц
Пожаловаться на содержимое документа