close

Вход

Забыли?

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

?

Патент BY15726

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.04.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091872
(22) 2009.12.28
(43) 2010.08.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Петроченко Андрей Сергеевич; Терешко
Сергей Михайлович (BY)
BY 15726 C1 2012.04.30
BY (11) 15726
(13) C1
(19)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 5352 C1, 2003.
BY 12542 C1, 2009.
RU 2373564 C2, 2009.
(57)
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 2, содержащее многовходовый одноразрядный сумматор по модулю три,
i-й вход которого, где i = 1, n , соединен с i-м информационным входом устройства, отличающееся тем, что содержит два элемента И и элемент сложения по модулю два, выход
которого соединен с выходом устройства, а первый вход соединен с первым настроечным
входом устройства, (j + 1)-й вход, где j = 1, 2, соединен с выходом j-го элемента И, первый
вход которого соединен с (j + 1)-м настроечным входом устройства, выход младшего разряда многовходового одноразрядного сумматора по модулю три соединен со вторым входом первого элемента И, выход старшего разряда многовходового одноразрядного
сумматора по модулю три соединен со вторым входом второго элемента И.
BY 15726 C1 2012.04.30
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления модулярных симметрических булевых функций
n переменных, содержащее 3n–3 элементов 2-2И-2ИЛИ и n элементов НЕ [1]. Устройство
реализует восемь модулярных симметрических булевых функций n переменных для величины модуля p = 3.
Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является многовходовый одноразрядный сумматор по модулю
три, содержащий элементы сложения по модулю два, элементы ЗАПРЕТ и мажоритарные
элементы с четными порогами [2]. На выходах сумматора формируются две модулярные
симметрические булевы функции n переменных.
Недостатком известного устройства является невозможность реализации всех восьми
модулярных симметрических булевых функций n переменных для величины модуля p = 3.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления всех модулярных симметрических булевых функций n
переменных для величины модуля p = 3.
Названный технический результат достигается путем введения в состав устройства
двух элементов И, элемента сложения по модулю два, а также изменением межсоединений элементов в схеме устройства.
Устройство для вычисления модулярных симметрических булевых функций n переменных, где n ≥ 2, содержит многовходовый одноразрядный сумматор по модулю три, i-й
вход которого, где i = 1, n , соединен с i-м информационным входом устройства.
В отличие от прототипа устройство содержит два элемента И и элемент сложения по
модулю два, выход которого соединен с выходом устройства, а первый вход соединен с
первым настроечным входом устройства, (j + 1)-й вход, где j = 1, 2, соединен с выходом
j-го элемента И, первый вход которого соединен с (j + 1)-м настроечным входом устройства. Выход младшего разряда многовходового одноразрядного сумматора по модулю три
соединен со вторым входом первого элемента И, выход старшего разряда многовходового
одноразрядного сумматора по модулю три соединен со вторым входом второго элемента И.
На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций n переменных.
Устройство содержит многовходовый одноразрядный сумматор по модулю три 1, два
элемента И 2 и 3, элемент сложения по модулю два 4, n информационных входов 5l-5n,
три настроечных входа 6, 7 и 8 и выход 9.
Поясним принцип построения и работы предлагаемого устройства.
Пусть G sh = (h , h , ..., h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0, 1}, и G 0h ≡ ∅.
Булева функция F = F(X), X = (x1, x2, ..., xn), называется симметрической (с.б.ф.),
если она симметрична относительно любой пары переменных из X.
С.б.ф. Ф = Ф(X), X = (x1, x2, ..., xn), называется модулярной, если ее значение на любом
наборе переменных из X однозначно определяется весом V(X)mod p = (x1 + x2 + ... + xn)mod p
двоичной кодовой комбинации по модулю p, p ≤ n:
Ф (G1i , G 0n −i ) = Ф (G1j , G 0n − j ),
где i mod p = j mod p, 0 ≤ i ≤ n, 0 ≤ j ≤ n, i ≠ j.
М.с.б.ф. Ф = Ф(X) может быть задана p-разрядным модулярным локальным кодом:
ρ(Ф) = (ρ0, ρ1, ..., ρр-1),
l
0
где ρ j = Ф(G i , G n −i ), i mod p = j, 0 ≤ i ≤ n, j = 0, p − 1 .
2
BY 15726 C1 2012.04.30
Один и тот же модулярный локальный код ρ(Ф) могут иметь м.с.б.ф., зависящие от
различного числа n переменных. Количество различных м.с.б.ф. n переменных не зависит
р
от n, а определяется только величиной модуля p и равно 2 .
В дальнейшем будем рассматривать м.с.б.ф. Ф = Ф(X) только для величины модуля
p = 3.
При p = 3 произвольная м.с.б.ф. Ф = Ф(X) n переменных может быть однозначно представлена в виде полиномиального разложения:
(1)
Ф = Ф(X) = к 0 ⊕ к1 ⋅ Pn1 (X) ⊕ к 2 ⋅ Pn2 (X),
где кj ∈ {0,1}, j = 0, 1, 2 - коэффициенты полиномиального разложения;
Pn1 = Pn1 (X) и Pn2 = Pn2 (X) - фундаментальные полиномиальные м.с.б.ф.
Коэффициенты кj полиномиального разложения (1) находятся из модулярного локального кода ρ(Ф) = {ρ0, ρ1, ρ2) согласно соотношениям
к 0 = ρ0 ;


к1 = ρ 0 ⊕ ρ1; 
(2)
к 2 = ρ0 ⊕ ρ 2 . 
В устройстве для формирования фундаментальных полиномиальных м.с.б.ф.
1
Pn = Pn1 (X) и Pn2 = Pn2 (X) используется многовходовый одноразрядный сумматор по модулю три. Такой сумматор выполняет сложение по модулю три n одноразрядных двоичных
чисел (с весом 20):
S = 2s1 + s0 = (x1 + x2 + ... + xn)mod 3,
где s1, s0 ∈ {0,1} - значения м.с.б.ф., формируемых соответственно на выходах старшего и
младшего разрядов сумматора.
Фундаментальные полиномиальные м.с.б.ф. Pn1 = Pn1 (X) и Pn2 = Pn2 (X) совпадают с
функциями s0 = s0(X) и s1 = s1(X) многовходового одноразрядного сумматора по модулю
три, а именно:
Pn1 (X) = s 0 (X); 
(3)

Pn2 (X) = s1 (X). 
Тогда с учетом (3) полиномиальное разложение (1) примет вид:
(4)
Ф(X) = к0 ⊕ к1 ⋅ s0(X) ⊕ к2 ⋅ s1(X).
Предлагаемое устройство построено в соответствии с выражением (4), которое и является первообразной (порождающей) функцией.
Из (4) непосредственно следует, что вектором настройки устройства на реализацию
конкретной м.с.б.ф Ф = Ф(X) является вектор коэффициентов полиномиального разложения к(Ф) = (к0, к1, к2), компоненты которого находятся из модулярного локального кода
ρ(Ф) согласно (2).
Устройство для вычисления модулярных симметрических булевых функций n переменных (фигура) работает следующим образом.
На информационные входы 51-5n подаются двоичные переменные x1-xn (в произвольном порядке), на настроечные входы 6, 7 и 8 - соответственно компоненты к0, к1 и к2 вектора коэффициентов полиномиального разложения к(Ф) м.с.б.ф. Ф = Ф(X), значения
которой реализуются на выходе 9 устройства.
Таким образом, при настройке сигналами из множества {0, 1} предлагаемое устройство
реализует восемь модулярных симметрических булевых функций n переменных для величины модуля p = 3.
Достоинствами устройства для вычисления модулярных симметрических булевых
функций n переменных являются высокое быстродействие, простая конструкция, широкие
функциональные возможности.
3
BY 15726 C1 2012.04.30
Источники информации:
1. Патент РБ 11758, МПК G 06F 7/00, 2009.
2. Патент РБ 5352, МПК G 06F 7/49, 7/50, 2003 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
84 Кб
Теги
патент, by15726
1/--страниц
Пожаловаться на содержимое документа