close

Вход

Забыли?

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

?

Патент BY13928

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.12.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13928
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20090089
(22) 2009.01.26
(43) 2009.08.30
(71) Заявитель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY a 20060921, 2007.
BY a 20070747, 2008.
BY a 20071257, 2008.
BY 13928 C1 2010.12.30
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n = 2m - число переменных реализуемых функций, где m = 4,5,6,…, характеризующееся тем, что содержит m - 1 групп из девяти элементов ИЛИ-НЕ каждая, m-ю
группу из трех элементов ИЛИ-НЕ, элемент ИЛИ-НЕ, m элементов ИЛИ, m элементов
сложения по модулю два и m элементов И-НЕ, причем (2k + j - 2)-й, где k = 1, m , где
j = 1,2, информационный вход устройства соединен с j-м входом k-го элемента ИЛИ, j-м
входом k-го элемента сложения по модулю два и j-м входом k-го элемента И-НЕ, выход iго, где i = 1, m − 1 , элемента ИЛИ соединен с первым входом (3l - 2)-го, где l = 1,2,3, элемента ИЛИ-НЕ i-й группы, инверсный выход i-го элемента сложения по модулю два соединен с первым входом (3l - 1)-го элемента ИЛИ-НЕ i-й группы, выход i-го элемента И-НЕ
BY 13928 C1 2010.12.30
соединен с первым входом 3l-го элемента ИЛИ-НЕ i-й группы, выход m-го элемента ИЛИ
соединен с первым входом первого элемента ИЛИ-НЕ m-ой группы, инверсный выход mго элемента сложения по модулю два соединен с первым входом второго элемента ИЛИНЕ m-й группы, выход m-го элемента И-НЕ соединен с первым входом третьего элемента
ИЛИ-НЕ m-ой группы, первый настроечный вход устройства соединен со вторым входом
первого элемента ИЛИ-НЕ первой группы, вторым входом шестого элемента ИЛИ-НЕ
первой группы и вторым входом восьмого элемента ИЛИ-НЕ первой группы, второй
настроечный вход устройства соединен со вторым входом второго элемента ИЛИ-НЕ первой группы, вторым входом четвертого элемента ИЛИ-НЕ первой группы и вторым входом девятого элемента ИЛИ-НЕ первой группы, третий настроечный вход устройства
соединен со вторым входом третьего элемента ИЛИ-НЕ первой группы, вторым входом
пятого элемента ИЛИ-НЕ первой группы и вторым входом седьмого элемента ИЛИ-НЕ
первой группы, выход l-го элемента ИЛИ-НЕ t-й, где t = 1, m − 2 , группы соединен с (l + 1)м входом первого элемента ИЛИ-НЕ (t + 1)-й группы, (l + 1)-м входом шестого элемента
ИЛИ-НЕ (t + 1)-й группы и (l + 1)-м входом восьмого элемента ИЛИ-НЕ (t + 1)-й группы,
выход (l + 3)-го элемента ИЛИ-НЕ t-й группы соединен с (l + 1)-м входом второго элемента ИЛИ-НЕ (t + 1)-й группы, (l + 1)-м входом четвертого элемента ИЛИ-НЕ (t + 1)-й группы и (l + 1)-м входом девятого элемента ИЛИ-НЕ (t + 1)-й группы, выход (l + 6)-го
элемента ИЛИ-НЕ t-й группы соединен с (l + 1)-м входом третьего элемента ИЛИ-НЕ
(t + 1)-й группы, (l + 1)-м входом пятого элемента ИЛИ-НЕ (t + 1)-й группы и (l + 1)-м
входом седьмого элемента ИЛИ-НЕ (t + 1)-й группы, выход l-го элемента ИЛИ-НЕ (m - 1)й группы соединен с (l + 1)-м входом первого элемента ИЛИ-НЕ m-й группы, выход
(l + 3)-го элемента ИЛИ-НЕ (m - 1)-й группы соединен с (l + 1)-м входом второго элемента
ИЛИ-НЕ m-й группы, выход (l + 6)-го элемента ИЛИ-НЕ (m - 1)-й группы соединен с
(l + 1)-м входом третьего элемента ИЛИ-НЕ m-й группы, выход l-го элемента ИЛИ-НЕ mй группы соединен с l-м входом элемента ИЛИ-НЕ, выход которого соединен с выходом
устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления модулярных симметрических булевых функций
n переменных, содержащее n элементов HE (n = 6,7,8,… - число переменных реализуемых
функций), n групп элементов 2-2И-2ИЛИ, n информационных входов, пять настроечных
входов и один выход [1].
Устройство реализует тридцать две модулярные симметрические булевы функции n
переменных для величины модуля p = 5.
Недостатками известного устройства являются низкое быстродействие и невозможность вычисления модулярных симметрических булевых функций для величины модуля
p = 3.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее 3n-3 элементов 2-2И-2ИЛИ, n элементов HE, n информационных входов, три настроечных входа и один выход [2].
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
2
BY 13928 C1 2010.12.30
Изобретение направлено на решение задачи повышения быстродействия устройства
для вычисления модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем использования в схеме устройства элементов ИЛИ-НЕ, И-НЕ, ИЛИ и сложения по модулю два, а также изменением связей между логическими элементами.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n = 2m - число переменных реализуемых функций, где m = 4,5,6,… содержит
m-1 группу элементов ИЛИ-НЕ по девять элементов в каждой, m-ю группу элементов
ИЛИ-НЕ из трех элементов, элемент ИЛИ-НЕ, m элементов ИЛИ, m элементов сложения
по модулю два и m элементов И-НЕ.
При этом (2k + j - 2)-й, где k = 1, m , где j = 1,2, информационный вход устройства соединен с j-м входом k-го элемента ИЛИ, j-м входом k-го элемента сложения по модулю
два и j-м входом k-го элемента И-НЕ.
Выход i-го, где i = 1, m − 1 , элемента ИЛИ соединен с первым входом (3l - 2)-го, где
l = 1,2,3, элемента ИЛИ-НЕ i-й группы, инверсный выход i-го элемента сложения по модулю два соединен с первым входом (3l-1)-го элемента ИЛИ-НЕ i-й группы, выход i-го
элемента И-НЕ соединен с первым входом 3l-го элемента ИЛИ-НЕ i-й группы.
Выход m-го элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ m-й
группы, инверсный выход m-го элемента сложения по модулю два соединен с первым
входом второго элемента ИЛИ-НЕ m-й группы, выход m-го элемента И-НЕ соединен с
первым входом третьего элемента ИЛИ-НЕ i-й группы.
Первый настроечный вход устройства соединен со вторым входом первого элемента
ИЛИ-НЕ первой группы, вторым входом шестого элемента ИЛИ-НЕ первой группы и
вторым входом восьмого элемента ИЛИ-НЕ первой группы, второй настроечный вход
устройства соединен со вторым входом второго элемента ИЛИ-НЕ первой группы, вторым входом четвертого элемента ИЛИ-НЕ первой группы и вторым входом девятого элемента ИЛИ-НЕ первой группы, третий настроечный вход устройства соединен со вторым
входом третьего элемента ИЛИ-НЕ первой группы, вторым входом пятого элемента ИЛИНЕ первой группы и вторым входом седьмого элемента ИЛИ-НЕ первой группы.
Выход l-го элемента ИЛИ-НЕ t-й, где t = 1, m − 2 , группы соединен с (l + 1)-м входом
первого элемента ИЛИ-НЕ (t + 1)-й группы, (l + 1)-м входом шестого элемента ИЛИ-НЕ
(t + 1)-й группы и (l + 1)-м входом восьмого элемента ИЛИ-НЕ (t + 1)-й группы, выход
(l + 3)-го элемента ИЛИ-НЕ t-й группы соединен с (l + 1)-м входом второго элемента
ИЛИ-НЕ (t + 1)-й группы, (l + 1)-м входом четвертого элемента ИЛИ-НЕ (t + 1)-й группы
и (l + 1)-м входом девятого элемента ИЛИ-НЕ (t + 1)-й группы, выход (l + 6)-го элемента
ИЛИ-НЕ t-й группы соединен с (l + 1)-м входом третьего элемента ИЛИ-НЕ (t + 1)-й группы, (l + 1)-м входом пятого элемента ИЛИ-НЕ (t + 1)-й группы и (l + 1) -м входом седьмого элемента ИЛИ-НЕ (t + 1)-й группы.
Выход l-го элемента ИЛИ-НЕ (m-1)-й группы соединен с (l + 1)-м входом первого
элемента ИЛИ-НЕ m-й группы, выход (l + 3)-го элемента ИЛИ-НЕ (m-1)-й группы соединен с (l + 1)-м входом второго элемента ИЛИ-НЕ m-й группы, выход (l + 6)-го элемента
ИЛИ-НЕ (m-1)-й группы соединен с (l + 1)-м входом третьего элемента ИЛИ-НЕ m-й
группы. Выход l-го элемента ИЛИ-НЕ m-й группы соединен с l-м входом элемента ИЛИНЕ, выход которого соединен с выходом устройства.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных при n = 10 (m = 5).
Устройство содержит 9m - 5 = 40 элементов ИЛИ-НЕ 1-40, m = 5 элементов ИЛИ 4145, m = 5 элементов сложения по модулю два с инверсным выходом 46-50, m = 5 элемен-
3
BY 13928 C1 2010.12.30
тов И-НЕ 51-55, n = 2m = 10 информационных входов 56-65, три настроечных входа 66, 67
и 68, выход 69.
Поясним принцип построения и работы устройства для вычисления модулярных симметрических булевых функций n переменных.
Обозначим: G sh = (h , h ,…, h ) - некоторый кортеж длины s, содержащий только элементы h∈{0,1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (x1, x2, …, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
π(F) = (π0 , π1, …, πn ),
(
)
где πi = F G1i, G 0n −i , i = 0, n.
Таким образом, вес двоичной кодовой комбинации V(X) = x1 + x2 + … + xn однозначно
определяет значение с.б.ф. F = F(X) на данном наборе переменных из X.
В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м.с.б.ф.).
С.б.ф. Ф = Ф(X), X = (x1,x2, …, xn), называется модулярной, если ее значение на любом
наборе переменных из X однозначно определяется весом V(X) mod p = (xl + x2 + … + xn)
mod p двоичной кодовой комбинации по модулю p, p ≤ n:
(
) (
)
Ф G il , G 0n −i = Ф G1j, G 0n − j ,
где i mod p = j mod p, 0≤i≤n, 0≤j≤n, i≠j.
В дальнейшем рассматриваем м.с.б.ф. Ф = Ф(X) только для величины модуля p = 3.
Очевидно, что м.с.б.ф. Ф = Ф(X) можно задавать трехразрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1, ρ2),
(1)
(
)
где p j = Ф G il , G 0n −i , i mod 3 = j, 0 ≤ i ≤ n , j = 0,2.
Один и тот же модулярный локальный код ρ(Ф) вида (1) могут иметь м.с.б.ф., зависящие от различного числа n переменных. При этом в классе с.б.ф. n переменных количество (2p = 23 = 8) различных м.с.б.ф. определяется только величиной модуля p = 3 и не
зависит от n.
Пусть Ф = Ф(X), X = (x1,x2,…, хn), - некоторая м.с.б.ф. n переменных, заданная своим
модулярным локальным кодом ρ(Ф) = (ρ0, ρ1, ρ2).
М.с.б.ф. Ф = Ф(X) допускает конъюнктивное разложение по паре некоторых переменных xh и xt, 1≤h≤n. 1≤t≤n, h≠t, вида:
Ф = Ф(X ) = ((x h ∨ x t ) ∨ ϕ0 ) ⋅ x h ⊕ x t ∨ ϕ1 ⋅ x h x t ∨ ϕ2 ,
(2)
где ϕ0, ϕ1, ϕ2 - «остаточные» м.с.б.ф. от n-2 переменных.
Дизъюнктивное разложение м.с.б.ф. Ф = Ф(X) по переменным xh и xt имеет вид:
(3)
Ф = Ф(X) = x h ∨ x t ⋅ ϕ0 ∨ (x h ⊕ x t ) ⋅ ϕ1 ∨ x h x t ⋅ ϕ2 ,
Модулярные локальные коды м.с.б.ф. ϕ0, ϕ1 и ϕ2 определяются из кода ρ(Ф):
ρ(ϕ0 ) = (ρ0 , ρ1,ρ 2 ); 

ρ(ϕ1 ) = (ρ1 , ρ2,ρ0 ); 
(4)

ρ(ϕ2 ) = (ρ2 , ρ0,ρ1 ).
((
)
)(
)
В свою очередь, к «остаточным» м.с.б.ф. ϕ0, ϕ1 и ϕ2 также можно применить разложения
видов (2) и (3) и так далее, вплоть до получения вырожденных «остаточных» функций
(констант нуля или единицы), которыми будут являться элементы модулярного локального кода ρ(Ф).
4
BY 13928 C1 2010.12.30
Таблица локальных кодов м.с.б.ф. Ф = Ф(X) при n = 10 и p = 3
Вектор настройки ρ(Ф) = (ρ0, ρ1, ρ2)
Локальные коды реализуемых на выходе 69
м.с.б.ф.
ρ0/66
ρ1/67
ρ2/68
π(Ф) = (π0,π1, …, π10)
0
0
0
π(Ф) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
0
0
1
π(Ф) = (0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0)
0
1
0
π(Ф) = (0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1)
0
1
1
π(Ф) = (0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1)
1
0
0
π(Ф) = (1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0)
1
0
1
π(Ф) = (1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0)
1
1
0
π(Ф) = (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1)
1
1
1
π(Ф) = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Предлагаемое устройство строится на основе чередования конъюнктивного (2) и
дизъюнктивного (3) разложений м.с.б.ф. Ф = Ф(X) последовательно по парам переменных
(x1,x2), (x3,x4), …, (xn-1,xn) и группирования тождественных «остаточных» функций на
каждом уровне разложения с учетом их модулярных локальных кодов (4).
При таком чередовании разложений (2) и (3) в схеме устройства соседними будут являться уровни элементов И-ИЛИ и ИЛИ-И. В результате «слияния» соседних уровней логических элементов от схемы И-ИЛИ-ИЛИ-И переходим к схеме И-ИЛИ-И. Далее,
применяя закон двойного отрицания, переходим от схемы с уровнями И-ИЛИ к схеме на
элементах ИЛИ-НЕ.
При этом вектором настройки устройства на реализацию конкретной м.с.б.ф. Ф = Ф(X)
будет являться ее модулярный локальный код ρ(Ф) = (ρ0, ρ1, ρ2).
Устройство для вычисления модулярных симметрических булевых функций при
n = 10 (фигура) работает следующим образом.
На информационные входы 56-65 подаются двоичные переменные x1,x2, …, x10 (в произвольном порядке), на настроечные входы 66, 67 и 68 - соответственно компоненты ρ0, ρ1
и ρ2 модулярного локального кода ρ(Ф) = (ρ0, ρ1, ρ2) м.с.б.ф. Ф = Ф(X) = (x1,x2, …, x10),
значения которой реализуются на выходе 69 устройства.
Локальные коды π(Ф) = (π0,π1, …, π10) м.с.б.ф. Ф = Ф(X), реализуемых устройством
(фигура), представлены в таблице.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, однородная и регулярная структура.
Источники информации:
1. Патент РБ 11888, МПК G 06F 7/00, 2009.
2. Патент РБ 11758, МПК G 06F 7/00, 2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
1
Размер файла
119 Кб
Теги
патент, by13928
1/--страниц
Пожаловаться на содержимое документа