close

Вход

Забыли?

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

?

Патент BY12542

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.10.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 12542
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20071257
(22) 2007.10.16
(43) 2008.06.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Терешко Сергей Михайлович
(BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) SU 1833860 A1, 1993.
BY 8464 С1, 2006.
SU 1793547 A1, 1993.
BY 12542 C1 2009.10.30
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 3 - число переменных реализуемых функций, характеризующееся тем, что
содержит блок вычисления симметрических булевых функций p - 1 переменной, где p ≤ n величина модуля, выход которого соединен с выходом устройства, а i-й информационный
BY 12542 C1 2009.10.30
вход, где i = 1, p − 1 , соединен с i-м информационным входом устройства, n - p + 1 групп
элементов 2-2И-2ИЛИ по p элементов в каждой и n - p + 1 элементов НЕ, выход j-го из которых, где j = 1, n − p + 1 , соединен с первым входом k-го, где k = 1, p , элемента 2-2И2ИЛИ j-й группы, второй вход которого соединен с входом j-го элемента НЕ и (p + j - 1)-м
информационным входом устройства, выход k-го элемента 2-2И-2ИЛИ первой группы соединен с k-м настроечным входом блока вычисления симметрических булевых функций
p - 1 переменной, выход первого элемента 2-2И-2ИЛИ (l + 1)-й группы, где l = 1, n − p , соединен с третьим входом первого элемента 2-2И-2ИЛИ l-й группы и четвертым входом pго элемента 2-2И-2ИЛИ l-й группы, выход (i + 1)-го элемента 2-2И-2ИЛИ (l + 1)-й группы
соединен с третьим входом (i + 1)-го элемента 2-2И-2ИЛИ l-й группы и четвертым входом
i-го элемента 2-2И-2ИЛИ l-й группы, первый настроечный вход устройства соединен с
третьим входом первого элемента 2-2И-2ИЛИ (n - p + 1)-й группы и четвертым входом pго элемента 2-2И-2ИЛИ (n - p + 1)-й группы, (i + 1)-й настроечный вход устройства соединен с третьим входом (i + 1)-го элемента 2-2И-2ИЛИ (n - p + 1)-й группы и четвертым
входом i-го элемента 2-2И-2ИЛИ (n - p + 1)-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных, содержащее n групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных
входов, n + 1 настроечных входов и один выход [1].
Устройство реализует симметрические (в том числе и модулярные симметрические)
булевы функции n переменных.
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций, содержащее n-входовый одноразрядный сумматор и (n + 1)-канальный мультиплексор [2]. Устройство реализует симметрические булевы функции n переменных, включая модулярные симметрические булевы функции.
Недостатком известного устройства также является высокая конструктивная сложность.
Изобретение направлено на решение задачи упрощения конструкции устройства при
вычислении модулярных симметрических булевых функций n переменных.
Названный технический результат достигается путем введения в структуру устройства
для вычисления симметрических булевых функций, зависящих от ограниченного числа
переменных (p - 1 переменной, где p ≥ 3 - величина модуля), n - p + 1 групп элементов 22И-2ИЛИ по p элементов в каждой и n - p + 1 элементов НЕ (n ≥ p - число переменных
реализуемых модулярных симметрических булевых функций).
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 3 - число переменных реализуемых функций, содержит блок вычисления
симметрических булевых функций p - 1 переменной, где p ≤ n - величина модуля, выход
которого соединен с выходом устройства, а i-й информационный вход, где i = 1, p − 1 , соединен с i-м информационным входом устройства.
Устройство содержит n - p + 1 групп элементов 2-2И-2ИЛИ по p элементов в каждой и
n - p + 1 элементов НЕ, выход j-го из которых, где j = 1, n - p + 1 , соединен с первым входом k-го, где k = 1, p , элемента 2-2И-2ИЛИ j-й группы, второй вход которого соединен с
входом j-го элемента НЕ и (р + j - 1)-м информационным входом устройства.
2
BY 12542 C1 2009.10.30
Выход k-го элемента 2-2И-2ИЛИ первой группы соединен с k-м настроечным входом
блока вычисления симметрических булевых функций.
Выход первого элемента 2-2И-2ИЛИ (l + 1)-й группы, где l = 1, n − p , соединен с третьим входом первого элемента 2-2И-2ИЛИ l-й группы и четвертым входом p-го элемента 22И-2ИЛИ l-й группы.
Выход (i + 1)-го элемента 2-2И-2ИЛИ (l + 1)-й группы соединен с третьим входом
(i + 1)-го элемента 2-2И-2ИЛИ l-й группы и четвертым входом i-го элемента 2-2И-2ИЛИ l-й
группы.
Первый настроечный вход устройства соединен с третьим входом первого элемента 22И-2ИЛИ (n - p + 1)-й группы и четвертым входом p-го элемента 2-2И-2ИЛИ (n - p + 1)-й
группы.
В устройстве (i + 1)-й настроечный вход соединен с третьим входом (i + 1)-го элемента 2-2И-2ИЛИ (n - p + 1)-й группы и четвертым входом i-го элемента 2-2И-2ИЛИ (n p + 1)-й группы.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных при n = 10 и величине модуля p = 7.
Устройство содержит блок вычисления симметрических булевых функций p - 1 = 6
переменных 1, n - p + 1 = 4 элемента НЕ 2-5, n - p + 1 = 4 группы элементов 2-2И-2ИЛИ
(p = 7 элементов первой группы 6-12, p = 7 элементов второй группы 13-19, p = 7 элементов третьей группы 20-26, p = 7 элементов четвертой группы 27-33), n = 10 информационных входов 34-43, p = 7 настроечных входов 44-50, выход 51.
Обозначим: G sh = (h , h ,K, h ) - некоторый кортеж длины s, содержащий только элементы h∈{0,1}, и G 0h ≡ ∅ .
Булева функция F = F(X), X = (х1, х2,…, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F = F(X) однозначно определяется своим локальным кодом
(1)
π(F) = (π0,π1,…,πn),
1
0
где π = F G i , G n −i , i = 0, n .
Таким образом, вес двоичной кодовой комбинации V(X) = x1 + х2 + … + хn однозначно
определяет значение с.б.ф. F = F(X) на данном наборе переменных из X.
Определение. С.б.ф. Ф = Ф(Х), X = (х1, х2,…, хn), называется модулярной, если ее значение на любом наборе переменных из X однозначно определяется весом V(X)mod p =
(x1 + х2 + … + xn)mod p двоичной кодовой комбинации по модулю p, p ≤ n:
Ô G1i , G 0n − i = Ô G1j , G 0n − j ,
(2)
где
(3)
imodp = jmodp, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном
коде π(Ф) = (π0, π1,…, πn) м.с.б.ф. Ф = Ф(Х) элементы πi = πj.
Тогда локальный код м.с.б.ф. Ф = Ф(Х) можно представить в виде




π(Ф ) =  π0 , π1 ,K, π p −1, π0 , π1,K, πp −1,K , π0 , π1,K , π p −1, π0 , π1,K, π n − kp ,
(4)
3 144244
3
144244
3

 144244
1
2
k


где k = [(n + 1)/p].
Принимая во внимание (4), м.с.б.ф. Ф = Ф(Х) можно задавать p-разрядным модулярным локальным кодом:
(5)
ρ(Ф) = (ρ0, ρ1,…, ρp-1),
(
)
(
(
)
(
)
где ρ j = Ф G il , G 0n −i , imodp = j, 0 ≤ i ≤ n, j = 0, p − 1 .
3
)
BY 12542 C1 2009.10.30
Очевидно, что ρ(Ф) = ( π0 , π1 , K , π p−1 ). Следовательно, при p ≥ n - 1 локальные коды
ρ(Ф) = π(Ф), а все с.б.ф. являются модулярными.
Необходимо также отметить, что один и тот же модулярный локальный код ρ(Ф) вида
(5) могут иметь м.с.б.ф., зависящие от различного числа n переменных.
В классе с.б.ф. n переменных количество (2p) различных м.с.б.ф. определяется только
величиной модуля p и не зависит от n.
Структура предлагаемого устройства для вычисления модулярных симметрических
булевых функций n переменных при величине модуля p содержит многофункциональный
логический модуль для реализации с.б.ф. p - 1 переменных и n - p + 1 уровней (групп) элементов 2-2И-2ИЛИ по p элементов в каждом. При этом векторном настройки (длина которого не зависит от числа переменных n) устройства на реализацию конкретной м.с.б.ф
Ф = Ф(Х) является ее p-разрядный модулярный локальный код ρ(Ф) = (ρ0, ρ1,…, ρр-1). При
настройке сигналами из множества {0,1} устройство реализует все 2p модулярных симметрических булевых функций n переменных.
Устройство для вычисления модулярных симметрических булевых функций при
n = 10 и p = 7 (фигура) работает следующим образом.
На информационные входы 34-43 подаются двоичные переменные x1 – x10 (в произвольном порядке), на настроечные входы 44-50 - соответственно компоненты ρ0 - ρ6 модулярного локального кода ρ(Ф) = (ρ0, ρ1, ρ2, ρ3, ρ4, ρ5, ρ6) м.с.б.ф. Ф = Ф(Х) = (x1, х2,…,
x10), значения которой реализуются на выходе 51 устройства.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются простая конструкция, однородная и регулярная структура.
Источники информации:
1. А.с. СССР 1742811, МПК G 06F 7/00, 1992.
2. А.с. СССР 1833860, МПК G 06F 7/00, 1993 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
181 Кб
Теги
by12542, патент
1/--страниц
Пожаловаться на содержимое документа