close

Вход

Забыли?

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

?

Патент BY11758

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(21) Номер заявки: a 20060921
(22) 2006.09.20
(43) 2007.10.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович
(BY)
BY 11758 C1 2009.04.30
BY (11) 11758
(13) C1
(19)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) SU 1742811 A1, 1992.
BY a 20040080, 2004.
SU 1793547 A1, 1993.
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, содержащее первый, второй и третий элементы 2-2И-2ИЛИ, n - 2, где n = 3, 4, 5, … число переменных реализуемых функций, группы элементов 2-2И-2ИЛИ по три элемента
в каждой и n элементов НЕ, выход первого из которых соединен с первым входом первого
элемента 2-2И-2ИЛИ, второй вход которого соединен с первым информационным входом
устройства и входом первого элемента НЕ, третий вход соединен с выходом второго элемента 2-2И-2ИЛИ, четвертый вход соединен с выходом третьего элемента 2-2И-2ИЛИ, а
выход соединен с выходом устройства, выход второго элемента НЕ соединен с первым
входом второго элемента 2-2И-2ИЛИ и первым входом третьего элемента 2-2И-2ИЛИ,
второй вход которого соединен со вторым входом второго элемента 2-2И-2ИЛИ, вторым
информационным входом устройства и входом второго элемента НЕ, третий вход второго
элемента 2-2И-2ИЛИ соединен с выходом первого элемента 2-2И-2ИЛИ первой группы,
четвертый вход соединен с выходом второго элемента 2-2И-2ИЛИ первой группы и
третьим входом третьего элемента 2-2И-2ИЛИ, четвертый вход которого соединен с
Фиг. 1
BY 11758 C1 2009.04.30
выходом третьего элемента 2-2И-2ИЛИ первой группы, выход (i + 2)-го, где i = 1, n − 2 ,
элемента НЕ соединен с первым входом j-го, где j = 1, 2, 3, элемента 2-2И-2ИЛИ i-й группы, второй вход которого соединен с (i + 2)-м информационным входом устройства и входом (i + 2)-го элемента НЕ, выход первого элемента 2-2И-2ИЛИ (t + 1)-й, где t = 1, n − 3 ,
группы соединен с третьим входом первого элемента 2-2И-2ИЛИ t-й группы, выход второго элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с третьим входом второго элемента
2-2И-2ИЛИ t-й группы и четвертым входом первого элемента 2-2И-2ИЛИ t-й группы, выход третьего элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с третьим входом третьего
элемента 2-2И-2ИЛИ t-й группы и четвертым входом второго элемента 2-2И-2ИЛИ t-й
группы, первый настроечный вход устройства соединен с третьим входом первого элемента 2-2И-2ИЛИ (n - 2)-й группы, второй настроечный вход устройства соединен с
третьим входом второго элемента 2-2И-2ИЛИ (n - 2)-й группы и четвертым входом первого элемента 2-2И-2ИЛИ (n - 2)-й группы, третий настроечный вход устройства соединен с
третьим входом третьего элемента 2-2И-2ИЛИ (n - 2)-й группы и четвертым входом второго элемента 2-2И-2ИЛИ (n - 2)-й группы, отличающееся тем, что выход первого элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с четвертым входом третьего элемента 2-2И2ИЛИ t-й группы, первый настроечный вход устройства соединен с четвертым входом
третьего элемента 2-2И-2ИЛИ (n - 2)-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных, содержащее n-входовый одноразрядный сумматор и (n + 1) - канальный мультиплексор [1]. Устройство реализует симметрические булевы функции n переменных, включая
модулярные симметрические булевы функции.
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций, содержащее n групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных
входов, n + 1 настроечных входов и один выход [2].
Устройство реализует симметрические (в том числе и модулярные симметрические)
булевы функции n переменных.
Недостатком известного устройства также является высокая конструктивная сложность.
Изобретение направлено на решение задачи упрощения устройства при вычислении
модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем изменения межсоединений логических элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных содержит первый, второй и третий элементы 2-2И-2ИЛИ, n-2, где n = 3, 4, 5, … число переменных реализуемых функций, группы элементов 2-2И-2ИЛИ по три элемента
в каждой и n элементов НЕ. Выход первого элемента НЕ соединен с первым входом первого
элемента 2-2И-2ИЛИ, второй вход которого соединен с первым информационным входом
устройства и входом первого элемента НЕ, третий вход соединен с выходом второго элемента 2-2И-2ИЛИ, четвертый вход соединен с выходом третьего элемента 2-2И-2ИЛИ, а
выход соединен с выходом устройства. Выход второго элемента НЕ соединен с первым
входом второго элемента 2-2И-2ИЛИ и первым входом третьего элемента 2-2И-2ИЛИ,
второй вход которого соединен со вторым входом второго элемента 2-2И-2ИЛИ, вторым
информационным входом устройства и входом второго элемента НЕ. Третий вход второго
элемента 2-2И-2ИЛИ соединен с выходом первого элемента 2-2И-2ИЛИ первой группы,
2
BY 11758 C1 2009.04.30
четвертый вход соединен с выходом второго элемента 2-2И-2ИЛИ первой группы и
третьим входом третьего элемента 2-2И-2ИЛИ, четвертый вход которого соединен с выходом третьего элемента 2-2И-2ИЛИ первой группы. Выход (i + 2)-го, где i = 1, n − 2 , элемента НЕ соединен с первым входом j-го, где j = 1, 2, 3, элемента 2-2И-2ИЛИ i-й группы,
второй вход которого соединен с (i + 2)-м информационным входом устройства и входом
(i + 2)-го элемента НЕ. Выход первого элемента 2-2И-2ИЛИ (t + 1)-й, где t = 1, n − 3 , группы соединен с третьим входом первого элемента 2-2И-2ИЛИ t-й группы. Выход второго
элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с третьим входом второго элемента 2-2И2ИЛИ t-й группы и четвертым входом первого элемента 2-2И-2ИЛИ t-й группы. Выход
третьего элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с третьим входом третьего элемента 2-2И-2ИЛИ t-й группы и четвертым входом второго элемента 2-2И-2ИЛИ t-й группы. Первый настроечный вход устройства соединен с третьим входом первого элемента
2-2И-2ИЛИ (n-2)-й группы. Второй настроечный вход устройства соединен с третьим входом второго элемента 2-2И-2ИЛИ (n - 2)-й группы и четвертым входом первого элемента
2-2И-2ИЛИ (n-2)-й группы. Третий настроечный вход устройства соединен с третьим входом третьего элемента 2-2И-2ИЛИ (n - 2)-й группы и четвертым входом второго элемента
2-2И-2ИЛИ (n - 2)-й группы.
В отличие от прототипа, выход первого элемента 2-2И-2ИЛИ (t + 1)-й группы соединен с четвертым входом третьего элемента 2-2И-2ИЛИ t-й группы, а первый настроечный
вход устройства соединен с четвертым входом третьего элемента 2-2И-2ИЛИ (n - 2)-й
группы.
На фиг. 1 представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных при n = 8.
Устройство содержит 3n-3 = 21 элемент 2-2И-2ИЛИ 1-21 (первый элемент 2-2И-2ИЛИ 1,
второй элемент 2-2И-2ИЛИ 2, третий элемент 2-2И-2ИЛИ 3, три элемента 2-2И-2ИЛИ первой группы 16, 17 и 18, три элемента 2-2И-2ИЛИ второй группы 13, 14 и 15, три элемента
2-2И-2ИЛИ третьей группы 10, 11 и 12, три элемента 2-2И-2ИЛИ четвертой группы 7, 8 и
9, три элемента 2-2И-2ИЛИ пятой группы 4, 5 и 6, три элемента 2-2И-2ИЛИ шестой группы 1, 2 и 3), n = 8 элементов НЕ 22-29, n = 8 информационных входов 30-37, три настроечных входа 38, 39 и 40, выход 41.
Поясним принцип построения и работы устройства для вычисления модулярных симметрических булевых функций n переменных.
Обозначим: Ghs = (h, h, …, h) - некоторый кортеж длины s, содержащий только элементы h ∈ {0, 1}, и Gh0 ≡ ∅.
Булева функция F - F(X), X = (х1, х2, …, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
π(F) = (π0, π1, …, πn),
(1)
где πi = F(G1i , G 0n −i ) , i = 0, n.
Таким образом, вес двоичной кодовой комбинации V(X) = x1 + х2 + ... + xn однозначно
определяет значение с.б.ф. F – F(X) на данном наборе переменных из X.
В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м. с.б.ф.).
Определение. С.б.ф. Ф = Ф(Х), X = (х1, х2, …, хn), называется модулярной, если ее значение на любом наборе переменных из X однозначно определяется весом
V(X)mod p = (x1 + x2 + … + xn)mod p двоичной кодовой комбинации по модулю p, p ≤ n:
(
)
Ф(G1i , G 0n −i ) = Ф G1j , G 0n − j ,
3
(2)
BY 11758 C1 2009.04.30
где
(3)
i mod p = j mod p, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
В дальнейшем рассматриваем м.с.б.ф. Ф = Ф(X) только для величины модуля p = 3.
Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном
коде π(Ф) = (π0, π1, …, πn) м.с.б.ф. Ф = Ф(Х) элементы πi = πj.
Тогда локальный код м.с.б.ф. Ф = Ф(Х) можно представить в виде:


π(Ф ) =  π 0 , π1 , π 2 , π 0 , π1 , π 2 ,..., π 0 , π1 , π 2 , π 0 ,..., π n −3k ,

 1424
3 1424
3 1424
3
1
2
k


(4)
где k = [(n + 1)/3].
Принимая во внимание (4), м.с.б.ф. Ф = Ф(Х) можно задавать трехразрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1, ρ2),
(5)
где ρ j = Ф(G1i , G 0n −i ) , i mod 3 = j, 0 ≤ i ≤ n , j = 0, 2.
Один и тот же модулярный локальный код ρ(Ф) вида (5) могут иметь м.с.б.ф., зависящие от различного числа n переменных.
В классе с.б.ф. n переменных количество (2p = 23 = 8) различных м.с.б.ф. определяется
только величиной модуля p = 3 и не зависит от n.
Пусть Ф = Ф(X), X = (x1, x2, …, xn), - некоторая м.с.б.ф. n переменных, заданная своим
модулярным локальным кодом ρ(Ф) = (ρ0, ρ1, ρ2).
М.с.б.ф. Ф = Ф(X) допускает дизъюнктивное разложение по некоторой переменной xt,
1 ≤ t ≤ n, вида:
Ф = x t ⋅ ϕ 0 ∨ x t ⋅ ϕ1 ;
(6)
где ϕ0 и ϕ1 - "остаточные" м.с.б.ф. от n - 1 переменной.
Модулярные локальные коды м.с.б.ф. ϕ0 и ϕ1 определяются из кода ρ(Ф):
ρ(φ 0 ) = ρ(Ф) = (ρ 0 , ρ1 , ρ 2 );


ρ(φ1 ) = (ρ1 , ρ 2 , ρ 0 ) .
(7)
В свою очередь к м.с.б.ф. ϕ0 и ϕ1 также можно применить разложение вида (6)
и так далее, вплоть до получения вырожденных "остаточных" функций (констант нуля или
единицы), которыми будут являться элементы модулярного локального кода ρ(Ф).
Пример. Пусть n = 5 и p = 3. Выполним последовательное дизъюнктивное разложение
(6) м.с.б.ф. Ф = Ф(X), заданной своим модулярным локальным кодом ρ(Ф) = (ρ0, ρ1, ρ2), по
переменным х1, х2, …, х5:
Ф(X) = x1 ( x 2 ( x 3 ( x 4 ( x 5 ρ 0 ∨ x 5ρ1 ) ∨ x 4 ( x 5 ρ1 ∨ x 5ρ 2 )) ∨
∨ x 3 ( x 4 ( x 5 ρ1 ∨ x 5 ρ 2 ) ∨ x 4 ( x 5ρ 2 ∨ x 5ρ 0 ))) ∨
∨ x 2 ( x 3 ( x 4 ( x 5 ρ1 ∨ x 5 ρ 2 ) ∨ x 4 ( x 5 ρ 2 ∨ x 5 ρ 0 )) ∨
∨ x 3 ( x 4 ( x 5 ρ 2 ∨ x 5 ρ 0 ) ∨ x 4 ( x 5 ρ 0 ∨ x 5ρ1 )))) ∨
∨ x1 ( x 2 ( x 3 ( x 4 ( x 5 ρ1 ∨ x 5 ρ 2 ) ∨ x 4 ( x 5 ρ 2 ∨ x 5 ρ 0 )) ∨
∨ x 3 ( x 4 ( x 5 ρ 2 ∨ x 5 ρ 0 ) ∨ x 4 ( x 5 ρ 0 ∨ x 5ρ1 ))) ∨
∨ x 2 ( x 3 ( x 4 ( x 5 ρ 2 ∨ x 5 ρ 0 ) ∨ x 4 ( x 5 ρ 3 ∨ x 5 ρ1 )) ∨
∨ x 3 ( x 4 ( x 5 ρ 0 ∨ x 5 ρ1 ) ∨ x 4 ( x 5 ρ1 ∨ x 5ρ 2 ))))).
4
(8)
BY 11758 C1 2009.04.30
Предлагаемое устройство строится на основе дизъюнктивного разложения (6) м.с.б.ф
Ф = Ф(Х) последовательно по всем переменным х1, х2, …, хn и группирования тождественных "остаточных" функций на каждом уровне разложения с учетом их модулярных локальных кодов (7). При этом вектором настройки устройства на реализацию конкретной
м.с.б.ф Ф = Ф(X) является ее модулярный локальный код ρ(Ф).
Так, например, структура устройства при n = 5 описывается выражением (8).
В общем случае устройство при настройке сигналами из множества {0, 1} реализует
восемь модулярных симметрических булевых функций n переменных для величины модуля p = 3.
Устройство для вычисления модулярных симметрических булевых функций при n = 8
(фиг. 1) работает следующим образом.
На информационные входы 30-37 подаются двоичные переменные х1, х2, …, х8 (в произвольном порядке), на настроечные входы 38, 39 и 40 - соответственно компоненты ρ0, ρi
и ρ2 модулярного локального кода ρ(Ф) = (ρ0, ρ1, ρ2) м.с.б.ф.
Ф = Ф(Х) = (х1, х2, …, х8), значения которой реализуются на выходе 41 устройства.
Локальные коды π(Ф) = (π0, π1, π2, π3, π4, π5, π6, π7, π8) м.с.б.ф. Ф = Ф(X), реализуемых
устройством (фиг. 1), представлены в таблице (фиг. 2).
Обозначим: ϕij - сигнал на выходе j-го элемента 2-2И-2ИЛИ i-й группы, i = 1, n - 2 ;
j = 1, 2, 3 .
Тогда структура предлагаемого устройства может быть описана следующей системой
рекуррентных соотношений:
ϕ0n −2 = x n ρ 0 ∨ x n ρ1 ; 

ϕ1n −2 = x n ρ1 ∨ x n ρ 2 ; 

ϕ n2 −2 = x n ρ 2 ∨ x n ρ 0 ;
ϕ0n −t −2 = x n − t ϕ 0n −t −1 ∨ x n − t ϕ1n − t −1 ;
ϕ1n −t −2
ϕ n2 −t −2


= x n − t ϕ1n −t −1 ∨ x n − t ϕ n2 − t −1 ;


= x n − t ϕ n2 −t −1 ∨ x n − t ϕ 0n − t −1 , t = 1, n − 3;
Ф = x1 (x 2 ϕ10 ∨ x 2 ϕ11 ) ∨ x 1 (x 2 ϕ11 ∨ x 2 ϕ12 ) .
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются простая конструкция, однородная и регулярная структура.
Источники информации:
1. А.с. СССР 1833860, МПК G 06F 7/00, 1993.
2. А.с. СССР 1742811, МПК G 06F 7/00, 1992 (прототип).
5
BY 11758 C1 2009.04.30
Таблица локальных кодов м.с.б.ф. Ф = Ф(Х) при n = 8, p = 3
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
112 Кб
Теги
by11758, патент
1/--страниц
Пожаловаться на содержимое документа