close

Вход

Забыли?

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

?

Патент BY12983

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.04.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 12983
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(21) Номер заявки: a 20071256
(22) 2007.10.16
(43) 2008.06.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Терешко Сергей Михайлович
(BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 5171 C1, 2003.
BY 8859 C1, 2007.
BY 7592 C1, 2005.
SU 1833860 A1, 1993.
US 4163211 A, 1979.
JP 55043612 A, 1980.
BY 12983 C1 2010.04.30
(57)
Устройство для вычисления модулярных бисимметрических булевых функций n переменных, где n≥2р, p≥3 – величина модуля, содержащее мультиплексор, выход которого соединен с выходом устройства, а i-й вход данных, где i = 1, p 2 , соединен с i-м настроечным
Фиг. 1
BY 12983 C1 2010.04.30
входом устройства, отличающееся тем, что содержит два многовходовых одноразрядных
сумматора по модулю p, j-й выход первого из которых, где j = 1, m, m = ]log 2 p[ , соединен
с j-м адресным входом мультиплексора, а l-й вход, где l = 1, k , p ≤ k < n , соединен с l-м
информационным входом устройства, (k + h)-й информационный вход которого, где
h = 1, n − k , соединен с h-м входом второго многовходового одноразрядного сумматора по
модулю p, j-й выход которого соединен с (m + j)-м адресным входом мультиплексора.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций n переменных,
содержащее n-входовый одноразрядный сумматор и (n + 1) - канальный мультиплексор [1].
Недостатком устройства являются ограниченные функциональные возможности, так
как оно не реализует модулярные бисимметрические булевы функции.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления бисимметрических булевых функций n переменных, содержащее два многовходовых одноразрядных сумматора и
мультиплексор [2]. Устройство реализует бисимметрические (в том числе и модулярные
бисимметрические) булевы функции n переменных, зависящие от двух кортежей попарно
симметрических переменных.
Недостатком известного устройства является высокая конструктивная сложность.
Изобретение направлено на решение задачи упрощения конструкции устройства при
вычислении модулярных бисимметрических булевых функций.
Названный технический результат достигается путем введения в состав устройства
двух многовходовых одноразрядных сумматоров по модулю, а также уменьшением количества каналов и адресных входов мультиплексора.
Устройство для вычисления модулярных бисимметрических булевых функций n переменных, где n ≥ 2р, р ≥ 3 - величина модуля, содержит мультиплексор, выход которого
соединен с выходом устройства, а i-й вход данных, где i = 1, p 2 соединен с i-м настроечным входом устройства.
В отличие от прототипа устройство содержит два многовходовых одноразрядных
сумматора по модулю р, j-й выход первого из которых, где j = 1, m , m = ]log2p[, соединен с
j-м адресным входом мультиплексора, а l-й вход, где l = 1, k , p ≤ k < n, соединен с l-м информационным входом устройства, (k + h)-й информационный вход которого, где
h = 1, n − k , соединен с h-м входом второго многовходового одноразрядного сумматора по
модулю р, j-й выход которого соединен с (m + j)-м адресным входом мультиплексора.
На фиг. 1 представлена схема устройства для вычисления модулярных бисимметрических булевых функций n переменных для произвольной величины модуля р, на фиг. 2 схема устройства для величины модуля р = 3.
Устройство (фиг. 1) содержит мультиплексор 1, первый 2 (k-входовый) одноразрядный сумматор по модулю р, второй 3 ((n-k)-входовый) одноразрядный сумматор по модулю р, n информационных входов 41-4n, р2 настроечных входов 51 − 5p 2 и выход 6.
Поясним принцип построения и работы предлагаемого устройства.
Обозначим: Ghs = (h,h,...,h) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0,1}, и Gh0 ≡ ∅.
Булева функция f = f(X), X1 = (х1,х2,...,хn) называется бисимметрической (б.с.б.ф.), если вектор ее переменных Х допускает разбиение на два кортежа Х1 и Х2, и при этом f сим-
2
BY 12983 C1 2010.04.30
метрична относительно любой пары переменных, принадлежащих одному и тому же кортежу Х1 и Х2.
Для определенности полагаем: X1 = (x1,x2,...,xk), X2 = (xk+1, xk+2,..., хn), 1 ≤ k < n.
При |Х1| = k, |X2| = n-k будем говорить, что б.с.б.ф. f от n переменных принадлежит
классу (k, n-k). Число различных б.с.б.ф. класса (k, n-k) равно 2L.
В классе бисимметрических булевых функций выделяется подкласс так называемых
модулярных бисимметрических булевых функций (м.б.с.б.ф.).
Пусть n ≥ 2р, p ≤ k < n и р ≥ 3 - величина модуля.
Определение. Бисимметрическая булева функция f = f(X) = f(X1, X2) называется модулярной, если ее значение на любом наборе переменных из X однозначно определяется весами двоичных кодовых комбинаций из Х1 и Х2 по модулю р:
V(X1)mod p = (x1 + x2 + ... + xk)mod p и V(X2)mod p = (xk+1 + xk+2 + ... + xn)mod p.
Тогда модулярная б.с.б.ф. f = f(X) = f(Х1, Х2) может быть однозначно задана своим р2разрядным модулярным локальным кодом
P(f) = (P00, P01,…, P0,p-1, P10, P11,…, P1,p-1,…, Pp-1,0, Pp-1,1,..., Pp-1,p-1),
(1)
где
(2)
P j1 j2 = f (G1l, G 0k − l , G1h , G 0n − k − h ) , j1 = l mod p, j2 = h mod p,
и 0 ≤ j1 ≤ p-1, 0 ≤ j2 ≤ p-1, 0 ≤ l ≤ k, 0 ≤ h ≤ n-k.
2
В классе (k, n-k) б.с.б.ф. n переменных количество (2p ) различных м.б.с.б.ф. определяется только величиной модуля р и не зависит от n и k. При этом необходимо отметить,
что один и тот же модулярный локальный код Р(f) вида (1) имеют м.б.с.б.ф., зависящие от
различного числа n переменных.
Устройство (фиг. 1) содержит два многовходовых одноразрядных сумматора по модулю. На входы 41-4k первого сумматора 2 поступают переменные х1, х2,..., xk, на входы 4k+14n второго сумматора 3 - переменные хk+1, хk+2,..., хn.
На выходе сумматора 2 формируется m-разрядный (m = ]log2p[) двоичный код числа
j1 = (х1 + х2 + ... + xk)mod p, на выходе сумматора 3 - m-разрядный двоичный код числа
j2 = (хk+1 + xk+2 + ... + xn)mod p. Эти коды подаются соответственно на старшие и младшие
адресные входы 22m-канального мультиплексора 1. Очевидно, что коды чисел j1 и j2 формируют 2m-разрядный адрес мультиплексора
(3)
A = 2mj1 + j2, 0 ≤ A ≤ 22m-1,
который подключает вход данных с номером А к выходу мультиплексора.
Следовательно, если на вход данных (канал) с номером А мультиплексора 1 подать
элемент P j1 j2 модулярного локального кода Р(f), то на выходе 6 мультиплексора 1 реализуется значение м.б.с.б.ф. f = f(X) = f(X1, X2) на данном наборе переменных из X = (Х1,Х2).
Таким образом, вектором настройки предлагаемого устройства на реализацию конкретной м.б.с.б.ф. f является ее модулярный локальный код Р(f).
Отметим также, что в общем случае 22m-р2 входов данных мультиплексора 1 не используются.
Пример.
На фиг. 2 представлена схема предлагаемого устройства для величины модуля p = 3.
Устройство содержит 16-канальный мультиплексор 1 (22m = 16, m = ]log2 p[ = 2) и два
многовходовых одноразрядных сумматора по модулю три 2 и 3.
Вектором настройки устройства является девятиразрядный (р2 = 9) модулярный локальный код Р(f) = (Р00, Р01, Р02, Р10, Р11, Р12, Р20, Р21, Р22) реализуемой м.б.с.б.ф. f, элементы которого подаются на настроечные входы 51-59 устройства (соответствующие входы
данных мультиплексора).
Из (3) непосредственно следует, что элемент Р00 подается на вход 51 данных с номером 0; элемент Р01 - на вход 52 данных с номером 1; элемент Р02 - на вход 53 данных с номером 2; элемент Р10 - на вход 54 данных с номером 4; элемент Р11 - на вход 55 данных с
3
BY 12983 C1 2010.04.30
номером 5; элемент Р12 - на вход 56 данных с номером 6; элемент Р20 - на вход 57 данных с
номером 8; элемент Р20 - на вход 58 данных с номером 9; элемент Р22 - на вход 59 данных с
номером 10.
Устройство для вычисления модулярных бисимметрических булевых функций n переменных (фиг. 1) работает следующим образом.
На информационные входы 41-4k устройства подаются (в произвольном порядке) переменные xl,x2,...,xk кортежа Х1, на информационные входы 4k+1-4n (в произвольном порядке) - переменные xk+1, xk+2,...,xn кортежа Х2, на настроечные входы 51-5p2
(соответственно) - элементы модулярного локального кода Р(f). На выходе 6 реализуется
значение м.б.с.б.ф. f = f(X) = f(X1, Х2) на данном наборе переменных из Х = (Х1,Х2).
Достоинствами устройства для вычисления модулярных бисимметрических булевых
функций n переменных являются простая конструкция и широкие функциональные возможности.
Источники информации:
1. А.с. СССР 1833860, МПК G 06F 7/00, 1993.
2. Патент РБ 5171, МПК G 06F 7/00, 2003 (прототип).
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
174 Кб
Теги
by12983, патент
1/--страниц
Пожаловаться на содержимое документа