РЕАЛИЗАЦИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ЛОГИЧЕСКИМИ СХЕМАМИ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 681.325:519.713
В. П. СУПРУН, Д. А. ГОРОДЕЦКИЙ
РЕАЛИЗАЦИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ЛОГИЧЕСКИМИ СХЕМАМИ
Предлагаются новые способы представления бисимметрических булевых функций посредством фундаментальных и полиномиально-однородных симметрических булевых функций. Приводятся эффективные логические схемы, реализующие бисимметрические булевы функции, которые зависят от четырех и пяти переменных. Ключевые слова: бисимметрические булевы функции, фундаментальные симметрические булевы функции, полиномиально-однородные симметрические булевы функции, логические схемы.
Введение. При проектировании вычислительных устройств возникает задача реализации на одном логическом модуле всех булевых функций, принадлежащих определенному классу, в качестве которого часто используется класс симметрических булевых функций или некоторые его подклассы. Интерес к симметрическим булевым функциям (или функциям, обладающим свойством частичной симметрии переменных) объясняется тем, что такими булевыми функциями описываются структура и поведение многих типовых устройств вычислительной техники [1]. Например, п-входовый одноразрядный сумматор, п-операндный сумматор по модулю P, схема контроля четности (нечетности).
К настоящему времени задача вычисления (реализации) на одном логическом модуле произвольных симметрических булевых функций практически решена [2—4]. Также получены результаты по реализации на одном логическом модуле фундаментальных [5] и полиномиально-однородных [6] симметрических булевых функций, частично симметрических булевых функций [7]. Кроме того, многие устройства, разработанные одним из авторов, защищены Патентами на изобретение Республики Беларусь (см. Патенты № 1433, 1587, 2117, 2118, 2119, 2377, 2793, 2990, 5171, 5173, 5174, 5178, 5179, 5838, 5938, 6995, 7592, 7947, 8421, 8566, 8619, 8859, 8973, 9051, 9147, 10216, 10219, 10549, 11024, 11027, 11028, 11275, 11785).
В настоящей статье приводятся новые аналитические представления бисимметрических булевых функций n переменных. На основе применения приведенных здесь аналитических представлений предлагаются логические схемы устройств, предназначенных для вычисления бисимметрических булевых функций, которые зависят от четырех и пяти переменных.
Основные понятия и определения. Произвольная симметрическая булева функция n
переменных F ( X ) = F ( x1, x2 , ... , xn ) характеризуется множеством рабочих чисел A(F ) = { a1,a2 ,...,ar }. Функция F принимает единичные значения на тех и только тех наборах
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
18 В. П. Супрун, Д. А. Городецкий
значений n переменных x1, x2 , ... , xn , которые содержат ровно ai единиц, где 0 ≤ ai ≤ n ,
0 ≤ i ≤ r и 0 ≤ r ≤ n + 1 . Такая функция F обозначается как F = Fna1,a2,...,ar ( X ) .
Если r = 1 , то функция F = Fna ( X ) называется фундаментальной (или элементарной)
симметрической булевой функцией.
Симметрическая булева функция n переменных F = F (X ) называется полиномиально-
однородной, если ее полином Жегалкина содержит (все) элементарные конъюнкции, ранг ко-
торых равен k , где 0 ≤ k ≤ n . Полиномиально-однородные симметрические функции обозна-
чаются через Enk = Enk ( X ) . Из определения следует, что En0 =1, En1 = x1 ⊕ x2 ⊕ ... ⊕ xn ,
En2 = x1x2 ⊕ ... ⊕ x1xn ⊕ ... ⊕ xn−1xn , ... , Enn = x1x2 ... xn .
Произвольная симметрическая булева функция F = F ( x1, x2 ,..., xn ) взаимно однозначно
представляется (n+1) -разрядным (локальным) двоичным кодом π( F ) = (π0 , π1,..., πn ) , где
πi — значение функции F на (любом) наборе значений n переменных, содержащем i
(0 ≤ i ≤ n) единиц. Иначе, πi =1 тогда и только тогда, когда i — рабочее число функции F .
Известно, что отношение частичной симметрии переменных произвольной булевой
функции F = F (X ) разбивает (единственным образом) множество ее переменных
X = {x1, x2 , ... , xn} на классы симметрии X1, X 2 ,..., X k , где 1 ≤ k ≤ n . Если k = 1 , то функция
F является (полностью) симметрической; если k = 2 , то F — бисимметрическая булева функция; если k = n , то функция F не обладает свойством частичной симметрии перемен-
ных. Если 3 ≤ k ≤ n −1 , то функция F ( X ) = F( X1, X 2 ,..., X k ) называется частично симметрической (или полисиммерической).
Булеву функцию F = F ( X1, X 2 ) , где X1 ={ x1, x2 , ... , xr } , X 2 ={ xr+1, xr+2 , ... , xn } , при
n ≥ 4 и 2 ≤ r ≤ n − 2 , будем называть бисимметрической булевой функцией типа „ r, n − r “.
Обозначим через ℜ(n) и ℜ(r, n − r) устройства, реализующие на своем единственном
выходе (при соответствующей настройке) симметрическую булеву функцию n перемен-
ных F = F(X ) и бисимметрическую булеву функцию F = F(X1, X 2 ) типа „ r, n − r “ соот-
ветственно.
Конструктивная сложность l(ℜ(n)) и l(ℜ(r, n − r)) устройств ℜ(n) и ℜ(r, n − r) опреде-
ляется как суммарное число входов логических элементов, содержащихся в соответствующих
логических схемах. Под глубиной логических схем g(ℜ(n)) и g(ℜ(r, n − r)), как обычно, по-
нимается максимальное число элементов схемы, через которые сигнал распространяется от ее
входных полюсов к выходному.
При разработке эффективных методов синтеза логических схем устройств ℜ(n) и
ℜ(r, n − r) необходимо стремиться к построению схем, оптимальных как по сложности, так и
по глубине. Такая задача является весьма сложной и поэтому любые результаты, полученные
в этом направлении, представляют определенный интерес для теории и практики проектиро-
вания устройств вычислительной техники.
Аналитические представления функций F = F ( X1, X 2 ) . В работе [8] приведено ана-
литическое представление бисимметрической булевой функции типа „ r, n − r “ следующего
вида:
r* −1
∨F ( X1, X 2 ) = ω j Frj1 ( X1 ) Fnj−2r ( X 2 ) , j=0
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
19
где ω j ∈{ 0,1} ; Frj1 ( X1 ) — фундаментальная симметрическая булева функция, зависящая от r
переменных множества X1 , рабочее число которой равно j1 (функция Fnj−2 r (X 2 ) определяется аналогичным образом); r* = (r +1)(n−r +1) ; j = j1 (n−r +1)+ j2 и 0 ≤ j1 ≤ r , 0 ≤ j2 ≤ n − r .
Из формулы (1) следует, что бисимметрическая булева функция F = F (X1, X 2 ) взаимно
( )однозначно задается посредством r* -разрядного двоичного вектора ω( F ) = ω0 , ω1, ... , ωr*−1 .
Отсюда следует, что число различных бисимметрических булевых функций типа „ r, n − r “
равно 2(r +1)(n−r +1) .
Если к функции F = F ( X1, X 2 ) применить формулу дизъюнктивного разложения по переменным x1, x2 , ... , xr , то с учетом того, что функция F = F (X1, X 2 ) является симмет-
рической относительно каждого из множеств переменных X1 и X 2 в отдельности, получим
F ( X1, X 2 ) = Fr0 ( X1 ) G0 ( X 2 )∨ Fr1 ( X1 )G1 ( X 2 )∨ ...∨ Frr ( X1 )Gr ( X 2 ) ,
(2)
где Fr0 ( X1 ) , Fr1 ( X1 ), ..., Frr ( X1 ) — фундаментальные симметрические булевы функции r
переменных множества X1 ; G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) — некоторые симметрические бу-
левы функции, зависящие от n − r переменных множества X 2 . Непосредственно из форму-
( )лы (2) следует, что ω( F ) = ω0 , ω1, ... , ωr*−1 = (π(G0 ), π(G1 ), ... , π(Gr )) , где π(Gi ) — локаль-
ный двоичный код симметрической булевой функции n − r переменных Gi = Gi (X 2 ) и
i = 0,1,..., r .
Принимая во внимание формулу (2), можно сделать вывод о том, что существует логи-
ческая схема устройства ℜ(r, n − r) , состоящая из фундаментального симметрического мно-
гополюсника на r входов (устройства, предназначенного для одновременной реализации
всех r + 1 фундаментальных симметрических булевых функций Fr0 ( X1 ) , Fr1 ( X1 ) , ..., Frr ( X1 ) ,
зависящих от r переменных), r +1 устройств для вычисления симметрических булевых
функций n − r переменных G0 (X 2 ), G1(X 2 ), ... ,Gr (X 2 ) , r +1 двухвходовых элементов И и
одного (r+1)-входового элемента ИЛИ. Для построения более эффективной (с точки зрения оптимизации конструктивной
сложности) логической схемы ℜ(r, n − r) необходимо преобразовать формулу (2), используя
для этого следующие логические равносильности: если ab = 0 , то a ∨ b = a ⊕ b ; a = a⊕1 и
a (b⊕c) = ab⊕ac , где a,b, c ∈ {0,1}.
Тогда после несложных преобразований из формулы (2) получаем
F ( X1, X 2 ) = Er0 ( X1 ) H0 ( X 2 )⊕ Er1 ( X1 ) H1 ( X 2 )⊕ ... ⊕ Err ( X1 ) Hr ( X 2 ) ,
(3)
где Er0 ( X1 ), Er1 ( X1 ) , ..., Err ( X1 ) — полиномиально-однородные симметрические булевы
функции r переменных множества X1 ; H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) — симметрические
булевы функции n − r переменных множества X 2 , которые зависят от функций
G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
20 В. П. Супрун, Д. А. Городецкий
Для установления зависимости функций H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) от G0 ( X 2 ) , G1 ( X2 ) , ... ,Gr ( X 2 ) введем в рассмотрение два 2m -разрядных вектора-столбца gm , hm и
( )2m ×2m -матрицу трансформации Sm , где значение m вычисляется из двойного неравенства
2m−1 < r +1 ≤ 2m .
Будем считать, что gm = (G0 ,G1 , ... , Gr , 0,..., 0) и hm = ( H0 , H1 , ... , Hr , 0,..., 0) , а матрицу
трансформации
Sm
определим
рекурсивным
образом:
S0 =[ 1 ]
и
Sj
=
⎡ ⎢ ⎢⎣
S S
j j
−1 −1
0⎤
S
j−1
⎥ ⎦⎥
,
где
j = 1,2, ... , m . Тогда зависимость векторов gm и hm друг от друга выражается векторно-
матричным уравнением Sm ⊗ gm = hm , где через символ ⊗ обозначена операция сложения по
модулю два элементарных конъюнкций.
Пример 1. Пусть r = 7 , тогда m = 3 и уравнение S3 ⊗ g3 = h3 принимает вид
⎡G0 ⎤ ⎡H0 ⎤
⎡1 ⎢1 ⎢⎢⎢11 ⎢1 ⎢1 ⎢⎣⎢11
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1
0⎤ 0⎥ 00⎥⎥⎥ 0⎥ 0⎥ 10⎦⎥⎥
⊗
⎢⎢G1
⎥ ⎥
⎢⎢⎢GG32
⎥ ⎥ ⎥
⎢⎢G4
⎥ ⎥
⎢G5 ⎥
⎢⎢G6
⎥ ⎥
=
⎢ ⎢
H1
⎥ ⎥
⎢ ⎢ ⎢ ⎢ ⎢
H H H
2 3 4
⎥ ⎥ ⎥ ⎥ ⎥
.
⎢H5 ⎥
⎢ ⎢
H
6
⎥ ⎥
⎢⎣G7 ⎦⎥ ⎢⎣H7 ⎥⎦
Отсюда следует система логических уравнений, которая представляет собой зависи-
мость функций H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) от G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) :
G0 ( X 2 ) = H0 ( X2 ) ,
⎫
G0 ( X 2 )⊕G1 ( X 2 ) = H1 ( X 2 ) , G0 ( X 2 )⊕G2 ( X 2 ) = H2 ( X2 ) ,
⎪ ⎪ ⎪
G0 G0
( (
X X
2 2
)⊕ )⊕
G1 G4
( X 2 )⊕G2 ( X2 )⊕ (X2 )=H4 (X2 ),
G3
(
X
2
)
=
H3
(
X
2
)
,
⎪⎪ ⎬ ⎪
G0 ( X 2 )⊕G1 ( X 2 )⊕G4 ( X2 )⊕G5 ( X2 ) = H5 ( X 2 ), ⎪
G0 G0
( (
X X
2 2
)⊕ )⊕
G2 G1
( X 2 )⊕G4 ( X2 ( X 2 )⊕ ... ⊕G7
)⊕G6 ( X2 )
(
=
X2 )= H H7 ( X2
6( ).
X
2
)
,⎪⎪ ⎭⎪
(4)
Следует отметить, что локальные коды симметрических булевых функций H0 ( X2 ) ,
H1 ( X 2 ) , ... , Hr ( X2 ) и G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) при условии, что 2m−1 < r +1≤ 2m , связа-
ны между собой таким же образом, как и сами функции.
Логическая схема устройства ℜ(2). Из представления функции F = F ( X1, X 2 ) по-
средством формулы (3) следует, что для построения эффективных логических схем устройств
ℜ(2, 2) и ℜ(3, 2) необходимо иметь оптимальную (в определенном смысле) логическую схе-
му устройства ℜ(2) , которое предназначено для вычисления (реализации) произвольных
симметрических функций F , зависящих от двух переменных z1 и z2 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
21
На рис. 1 приведена логическая схема устройства ℜ(2), синтезированная эвристическим способом. Устройство ℜ(2) имеет три входа, на которые подается двоичный вектор настройки u(F ) = (u0 ,u1,u2 ), значения разрядов которого определяются с помощью таблицы на-
стройки.
Сигналы настройки Выход
и0 и1 &
M2 F
и0 и1 и2 π(F)
0 0 0 000
0 z1 z2 0 0 1
z1 z2
1 010
1 z1 z2 0 1 1
и2 Рис. 1
0 z1 z2 1 0 0
z1 z2
1 101
1 z1 z2 1 1 0 1 0 0 111
Сложность и глубина устройства ℜ(2) равны l(ℜ(2)) = 3 и g(ℜ(2)) = 2 . Логическая схе-
ма устройства ℜ(2), приведенная на рис. 1, является наиболее простой из всех существующих
аналогов.
Логическая схема устройства ℜ(2, 2). Для бисимметрической булевой функции
F = F ( X1, X 2 ) , где X1 ={x1, x2} и X 2 ={x3, x4} , формула (3) принимает вид
F ( X1, X 2 ) = E20 ( x1, x2 ) H0 ( x3, x4 )⊕ E12 ( x1, x2 ) H1 ( x3, x4 )⊕ E22 ( x1, x2 ) H2 ( x3, x4 )
или
F ( x1, x2 , x3, x4 ) = H0 ( x3, x4 )⊕( x1 ⊕ x2 ) H1 ( x3, x4 )⊕ x1x2 H2 ( x3, x4 ) .
(5)
Из системы уравнений (4) следует, что для формулы (5) справедливы следующие соот-
ношения: π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) и π( H2 ) = π(G0 )⊕π(G2 ) . На рис. 2 приведена логическая схема устройства ℜ(2, 2), которая синтезирована на ос-
нове применения формулы (5) с использованием схемы ℜ(2) (см. рис. 1). При этом логическая схема ℜ(2) была использована трижды.
и0
и1 & и2 и3
и4 & М2 &
и5
M2 F
х1 М2 х2
&
и6 М2 и7 & и8
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
22 В. П. Супрун, Д. А. Городецкий
Поясним метод построения вектора u ( F ) = (u0 ,u1, ... ,u8 ) — вектора настройки устройства ℜ(2, 2) на вычисление заданной функции F = F (X1, X 2 ) .
С помощью локального кода π( H0 ) из таблицы получаем значения первых трех разрядов u0 ,u1,u2 вектора u(F ). Естественно, что при этом необходимо заменить переменные z1 и
z2 на переменные x3 и x4 соответственно.
Далее с помощью локальных кодов π( H1 ) и π( H2 ) из таблицы получаем значения остальных разрядов u3,u4 ,u5 и u6 ,u7 ,u8 вектора настройки u(F ).
Пример 2. Предположим, что на выходе устройства ℜ(2, 2) (см. рис. 2) требуется реа-
лизовать бисимметрическую булеву функцию
Так как
F ( x1, x2 , x3, x4 ) = x1 x2 ( x3 ⊕ x4 )∨( x1 ∨ x2 ) x3 x4 .
( ) ( )F = x1 x2 x3 x4 ∨ x3 x4 ∨ x1 x2 ∨ x1 x2 x3x4 ∨ x1x2 x3 x4 ,
то
( )F = x1 x2G0 ( x3, x4 )∨ x1x2 ∨ x1 x2 G1 ( x3, x4 )∨ x1x2G2 ( x3, x4 ) ,
где π(G0 ) =(0,1, 0) и π(G1 ) = π(G2 ) = (0, 0,1) .
Отсюда следует, что двоичный код бисимметрической булевой функции F = F ( X1, X 2 )
равен ω( F ) =(π(G0 ), π(G1 ), π(G2 )) =(0,1, 0, 0, 0,1, 0, 0,1) .
Из системы уравнений (4) получаем π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) и
π( H2 ) = π(G0 )⊕π(G2 ) . Так как π(G0 ) =(0,1, 0) и π(G1 ) = π(G2 ) = (0, 0,1) , то π( H0 ) = (0,1,0) ,
π( H1 ) =(0,1,1) и π( H2 ) = (0,1,1) .
Принимая во внимание описанную выше процедуру построения вектора настройки
u(F ), получаем u0 = x3 , u1 = x4 , u2 = 1, u3 = 1 , u4 = x3 , u5 = x4 , u6 = 1, u7 = x3 и u8 = x4 . Первообразная функция устройства ℜ(2, 2) имеет вид
F ( x1, x2 ,u0 ,u1, ... ,u8 ) = u0 ⊕u1u2 ⊕( x1 ⊕ x2 )(u3 ⊕u4u5 )⊕ x1x2 (u6 ⊕u7u8 ) . Сложность и глубина логической схемы устройства ℜ(2, 2) составляют l(ℜ(2, 2)) = 21 и g(ℜ(2, 2)) = 4 . Кроме того, число внешних выводов схемы равно 12. Отметим, что приведенная выше логическая схема ℜ(2, 2) предназначена для реализации любой из 512 бисиммет-
рических булевых функций типа „ 2,2 “.
Логическая схема устройства ℜ(3, 2). Формула (3) применительно к бисимметриче-
ской булевой функции F = F (X1, X 2 ) , у которой X1 = {x1, x2 , x3} и X 2 = {x4 , x5}, принимает
вид
F ( X1, X 2 ) = E30 ( X1 ) H0 ( X 2 )⊕ E31 ( X1 ) H1 ( X 2 )⊕ E32 ( X1 ) H2 ( X2 )⊕ E33 ( X1 ) H3 ( X2 )
или
F ( x1, x2 , x3, x4 , x5 ) = H0 ( x4 , x5 )⊕( x1 ⊕ x2 ⊕ x3 ) H1 ( x4 , x5 )⊕
⊕ ( x1x2 ⊕ x1x3 ⊕ x2 x3 ) H2 ( x4 , x5 )⊕ x1x2 x3H3 ( x4 , x5 ) .
(6)
Из системы (4) получаем π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) , π( H2 ) = π(G0 )⊕π(G2 )
и π( H3 ) = π(G0 )⊕π(G1 )⊕π(G2 )⊕π(G3 ) .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
23
Логическая схема устройства ℜ(3, 2) , синтезированная на основе применения формулы
(6), приведена на рис. 3. Причем при ее построении была использована (четыре раза) логиче-
ская схема устройства ℜ(2).
и0
и1 & и2 и3 M2 F и4 & М2 &
и5
М2
и6 и7 & М2 & и8
х1 х2
≥2
х3
&
и9 М2 и10 & и11
Рис. 3
Настройка устройства ℜ(3, 2) осуществляется по аналогии с настройкой устройства ℜ(2, 2), рассмотренной в предыдущем разделе. Однако при построении вектора настройки u(F ) = (u0 ,u1, ... ,u11) необходимо четыре раза обратиться к таблице.
Первообразная функция логической схемы устройства ℜ(3, 2) , приведенной на рис. 3,
имеет вид
F ( x1, x2 , x3, x4 , x5 , u0 ,u1, ... , u11 ) = u0 ⊕u1u2 ⊕( x1 ⊕ x2 ⊕ x3 )(u3 ⊕u4u5 )⊕
⊕ ( x1x2 ⊕ x1x3 ⊕ x2 x3 )(u6 ⊕u7u8 )⊕ x1x2 x3 (u9 ⊕u10u11 ) . Пример 3. Предположим, что на выходе устройства ℜ(3, 2) требуется реализовать би-
симметрическую булеву функцию
F ( X1, X 2 ) = x1 x2 x3 ( x4 ∨ x5 )∨( x1x2 ∨ x1x3 ∨ x2 x3 ) x4 x5 , где X1 = {x1, x2 , x3} и X 2 = {x4 , x5}.
Так как
( )F ( x1, x2 , x3, x4 , x5 ) = x1 x2 x3 ( x4 ∨ x5 )∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 0∨
( )∨ x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 x4 x5 ∨ x1x2 x3 x4 x5 ,
то
F ( x1, x2 , x3, x4 , x5 ) = F30 ( x1, x2 , x3 )G0 ( x4 , x5 )∨ F31 ( x1, x2 , x3 )G1 ( x4 , x5 )∨
∨F32 ( x1, x2 , x3 )G2 ( x4 , x5 )∨ F33 ( x1, x2 , x3 )G3 ( x4 , x5 ) ,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
24 В. П. Супрун, Д. А. Городецкий
где π(G0 ) = (0,1,1) , π(G1 ) = (0, 0, 0) и π(G2 ) = π(G3 ) = (0, 0,1) . Двоичный код ω( F ) бисимметрической булевой функции F = F (X1, X 2 ) равен
ω( F ) =(π(G0 ), π(G1 ), π(G2 ), π(G3 )) = (0,1,1, 0, 0, 0, 0, 0,1, 0, 0,1) .
Принимая во внимание систему уравнений (4), вычисляем локальные коды симметриче-
ских булевых функций H0 ( x4 , x5 ), H1 ( x4 , x5 ), H2 ( x4 , x5 ), H3 ( x4 , x5 ) , входящих в разложе-
ние (6), согласно следующим формулам:
H 0 (x4 , x5 ) = G0 (x4 , x5 ), H1(x4, x5 ) = G0 (x4, x5 )⊕ G1(x4, x5 ) , H 2 (x4 , x5 ) = G0 (x4 , x5 )⊕ G2 (x4 , x5 ),
H3(x4 , x5 ) = G0 (x4 , x5 )⊕ G1(x4 , x5 )⊕ G2 (x4 , x5 )⊕ G3(x4 , x5 ) . Так как здесь π(G0 ) = (0,1,1) , π(G1 ) = (0, 0, 0) , π(G2 ) = π(G3 ) = (0, 0,1) , то π( H0 ) = (0,1,1) , π( H1 ) =(0,1,1) π( H2 ) = (0,1, 0) и π( H3 ) = (0,1,1) . Из таблицы настроек устройства ℜ(2) применительно к симметрическим булевым функциям H0 = H0 (x4 , x5 ) , H1 = H1(x4 , x5 ) , H 2 = H2 (x4 , x5 ) , H3 = H3(x4 , x5 ) , получаем
u0 = 1, u1 = x4 , u2 = x5 , u3 = 1 , u4 = x4 , u5 = x5 , u6 = x4 , u7 = x5 , u8 = 1, u9 = 1, u10 = x4 и
u11 = x5 .
Логическая схема устройства ℜ(3, 2) , приведенная на рис. 3, имеет сложность l(ℜ(3, 2)) = 33, глубину g(ℜ(3, 2)) = 4 и 16 внешних выводов (3 информационных и 12 на-
строечных входов, а также выход).
С помощью логической схемы устройства ℜ(3, 2) при соответствующей настройке можно реализовать любую из 4096 бисимметрических булевых функций F = F(X1, X 2 ) , где X1 = {x1, x2 , x3} и X 2 = {x4 , x5}.
Заключение. В настоящей работе приводятся логические схемы устройств ℜ(2), ℜ(2, 2) и ℜ(3, 2) , которые выгодно отличаются от всех существующих аналогов по конст-
руктивной сложности, глубине и числу внешних выводов. В частности, они превосходят по
всем параметрам логическую схему устройства ℜ(r, n − r) , описанную в работе [8]. Для построения логических схем устройств ℜ(r, n − r) , где n − r ≥ 3 , требуется разрабо-
тать (а затем использовать) эффективные логические схемы устройства ℜ(n − r).
СПИСОК ЛИТЕРАТУРЫ
1. Карцев М. А. Арифметика цифровых машин. М.: Наука, 1969. 576 с.
2. Авгуль Л. Б., Супрун В. П. Синтез быстродействующих логических схем методом каскадов // Изв. вузов. Приборостроение. 1993. Т. 36, № 3. С. 31—36.
3. Авгуль Л. Б., Супрун В. П. Синтез схем симметрических булевых функций в базисе линейной и монотонных функций // Там же. 1995. Т. 38, № 11—12. С. 33—36.
4. Супрун В. П., Седун А. М. Реализация симметрических булевых функций логическими схемами // Там же. 1998. Т. 41, № 9. С. 32—38.
5. Супрун В. П., Седун А. М. Схемная реализация фундаментальных симметрических булевых функций посредством логических устройств со сложной настройкой // Мат. IV Междунар. конф. „Автоматизация проектирования дискретных систем“. Минск, 2001. Т. 2. С. 86—91.
6. Супрун В.П. Синтез логических устройств для вычисления полиномиально-однородных симметрических булевых функций // Мат. VI Междунар. конф. „Автоматизация проектирования дискретных систем“. Минск, 2001. Т. 2. С. 146—153.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Анализ КА для синтеза частот с помощью функций целочисленного аргумента
25
7. Супрун В. П., Седун А. М. Схемная реализация частично симметрических булевых функций // „Логическое проектирование“. ИТК НАН Беларуси. 2000. Вып. 5. С. 29—37.
8. Супрун В. П., Седун А. М. Синтез устройства для вычисления бисимметрических булевых функций // Там же. 1998. Вып. 3. С. 69—77.
Валерий Павлович Супрун Данила Андреевич Городецкий
Сведения об авторах — канд. техн. наук, доцент; Белорусский государственный университет,
кафедра уравнений математической физики, Минск; E-mail: suprun@bsu.by — аспирант; Белорусский государственный университет, кафедра уравнений математической физики, Минск; E-mail: danila.gorodecky@gmail.com
Рекомендована кафедрой уравнений математической физики
Поступила в редакцию 09.11.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
УДК 681.325:519.713
В. П. СУПРУН, Д. А. ГОРОДЕЦКИЙ
РЕАЛИЗАЦИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ЛОГИЧЕСКИМИ СХЕМАМИ
Предлагаются новые способы представления бисимметрических булевых функций посредством фундаментальных и полиномиально-однородных симметрических булевых функций. Приводятся эффективные логические схемы, реализующие бисимметрические булевы функции, которые зависят от четырех и пяти переменных. Ключевые слова: бисимметрические булевы функции, фундаментальные симметрические булевы функции, полиномиально-однородные симметрические булевы функции, логические схемы.
Введение. При проектировании вычислительных устройств возникает задача реализации на одном логическом модуле всех булевых функций, принадлежащих определенному классу, в качестве которого часто используется класс симметрических булевых функций или некоторые его подклассы. Интерес к симметрическим булевым функциям (или функциям, обладающим свойством частичной симметрии переменных) объясняется тем, что такими булевыми функциями описываются структура и поведение многих типовых устройств вычислительной техники [1]. Например, п-входовый одноразрядный сумматор, п-операндный сумматор по модулю P, схема контроля четности (нечетности).
К настоящему времени задача вычисления (реализации) на одном логическом модуле произвольных симметрических булевых функций практически решена [2—4]. Также получены результаты по реализации на одном логическом модуле фундаментальных [5] и полиномиально-однородных [6] симметрических булевых функций, частично симметрических булевых функций [7]. Кроме того, многие устройства, разработанные одним из авторов, защищены Патентами на изобретение Республики Беларусь (см. Патенты № 1433, 1587, 2117, 2118, 2119, 2377, 2793, 2990, 5171, 5173, 5174, 5178, 5179, 5838, 5938, 6995, 7592, 7947, 8421, 8566, 8619, 8859, 8973, 9051, 9147, 10216, 10219, 10549, 11024, 11027, 11028, 11275, 11785).
В настоящей статье приводятся новые аналитические представления бисимметрических булевых функций n переменных. На основе применения приведенных здесь аналитических представлений предлагаются логические схемы устройств, предназначенных для вычисления бисимметрических булевых функций, которые зависят от четырех и пяти переменных.
Основные понятия и определения. Произвольная симметрическая булева функция n
переменных F ( X ) = F ( x1, x2 , ... , xn ) характеризуется множеством рабочих чисел A(F ) = { a1,a2 ,...,ar }. Функция F принимает единичные значения на тех и только тех наборах
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
18 В. П. Супрун, Д. А. Городецкий
значений n переменных x1, x2 , ... , xn , которые содержат ровно ai единиц, где 0 ≤ ai ≤ n ,
0 ≤ i ≤ r и 0 ≤ r ≤ n + 1 . Такая функция F обозначается как F = Fna1,a2,...,ar ( X ) .
Если r = 1 , то функция F = Fna ( X ) называется фундаментальной (или элементарной)
симметрической булевой функцией.
Симметрическая булева функция n переменных F = F (X ) называется полиномиально-
однородной, если ее полином Жегалкина содержит (все) элементарные конъюнкции, ранг ко-
торых равен k , где 0 ≤ k ≤ n . Полиномиально-однородные симметрические функции обозна-
чаются через Enk = Enk ( X ) . Из определения следует, что En0 =1, En1 = x1 ⊕ x2 ⊕ ... ⊕ xn ,
En2 = x1x2 ⊕ ... ⊕ x1xn ⊕ ... ⊕ xn−1xn , ... , Enn = x1x2 ... xn .
Произвольная симметрическая булева функция F = F ( x1, x2 ,..., xn ) взаимно однозначно
представляется (n+1) -разрядным (локальным) двоичным кодом π( F ) = (π0 , π1,..., πn ) , где
πi — значение функции F на (любом) наборе значений n переменных, содержащем i
(0 ≤ i ≤ n) единиц. Иначе, πi =1 тогда и только тогда, когда i — рабочее число функции F .
Известно, что отношение частичной симметрии переменных произвольной булевой
функции F = F (X ) разбивает (единственным образом) множество ее переменных
X = {x1, x2 , ... , xn} на классы симметрии X1, X 2 ,..., X k , где 1 ≤ k ≤ n . Если k = 1 , то функция
F является (полностью) симметрической; если k = 2 , то F — бисимметрическая булева функция; если k = n , то функция F не обладает свойством частичной симметрии перемен-
ных. Если 3 ≤ k ≤ n −1 , то функция F ( X ) = F( X1, X 2 ,..., X k ) называется частично симметрической (или полисиммерической).
Булеву функцию F = F ( X1, X 2 ) , где X1 ={ x1, x2 , ... , xr } , X 2 ={ xr+1, xr+2 , ... , xn } , при
n ≥ 4 и 2 ≤ r ≤ n − 2 , будем называть бисимметрической булевой функцией типа „ r, n − r “.
Обозначим через ℜ(n) и ℜ(r, n − r) устройства, реализующие на своем единственном
выходе (при соответствующей настройке) симметрическую булеву функцию n перемен-
ных F = F(X ) и бисимметрическую булеву функцию F = F(X1, X 2 ) типа „ r, n − r “ соот-
ветственно.
Конструктивная сложность l(ℜ(n)) и l(ℜ(r, n − r)) устройств ℜ(n) и ℜ(r, n − r) опреде-
ляется как суммарное число входов логических элементов, содержащихся в соответствующих
логических схемах. Под глубиной логических схем g(ℜ(n)) и g(ℜ(r, n − r)), как обычно, по-
нимается максимальное число элементов схемы, через которые сигнал распространяется от ее
входных полюсов к выходному.
При разработке эффективных методов синтеза логических схем устройств ℜ(n) и
ℜ(r, n − r) необходимо стремиться к построению схем, оптимальных как по сложности, так и
по глубине. Такая задача является весьма сложной и поэтому любые результаты, полученные
в этом направлении, представляют определенный интерес для теории и практики проектиро-
вания устройств вычислительной техники.
Аналитические представления функций F = F ( X1, X 2 ) . В работе [8] приведено ана-
литическое представление бисимметрической булевой функции типа „ r, n − r “ следующего
вида:
r* −1
∨F ( X1, X 2 ) = ω j Frj1 ( X1 ) Fnj−2r ( X 2 ) , j=0
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
19
где ω j ∈{ 0,1} ; Frj1 ( X1 ) — фундаментальная симметрическая булева функция, зависящая от r
переменных множества X1 , рабочее число которой равно j1 (функция Fnj−2 r (X 2 ) определяется аналогичным образом); r* = (r +1)(n−r +1) ; j = j1 (n−r +1)+ j2 и 0 ≤ j1 ≤ r , 0 ≤ j2 ≤ n − r .
Из формулы (1) следует, что бисимметрическая булева функция F = F (X1, X 2 ) взаимно
( )однозначно задается посредством r* -разрядного двоичного вектора ω( F ) = ω0 , ω1, ... , ωr*−1 .
Отсюда следует, что число различных бисимметрических булевых функций типа „ r, n − r “
равно 2(r +1)(n−r +1) .
Если к функции F = F ( X1, X 2 ) применить формулу дизъюнктивного разложения по переменным x1, x2 , ... , xr , то с учетом того, что функция F = F (X1, X 2 ) является симмет-
рической относительно каждого из множеств переменных X1 и X 2 в отдельности, получим
F ( X1, X 2 ) = Fr0 ( X1 ) G0 ( X 2 )∨ Fr1 ( X1 )G1 ( X 2 )∨ ...∨ Frr ( X1 )Gr ( X 2 ) ,
(2)
где Fr0 ( X1 ) , Fr1 ( X1 ), ..., Frr ( X1 ) — фундаментальные симметрические булевы функции r
переменных множества X1 ; G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) — некоторые симметрические бу-
левы функции, зависящие от n − r переменных множества X 2 . Непосредственно из форму-
( )лы (2) следует, что ω( F ) = ω0 , ω1, ... , ωr*−1 = (π(G0 ), π(G1 ), ... , π(Gr )) , где π(Gi ) — локаль-
ный двоичный код симметрической булевой функции n − r переменных Gi = Gi (X 2 ) и
i = 0,1,..., r .
Принимая во внимание формулу (2), можно сделать вывод о том, что существует логи-
ческая схема устройства ℜ(r, n − r) , состоящая из фундаментального симметрического мно-
гополюсника на r входов (устройства, предназначенного для одновременной реализации
всех r + 1 фундаментальных симметрических булевых функций Fr0 ( X1 ) , Fr1 ( X1 ) , ..., Frr ( X1 ) ,
зависящих от r переменных), r +1 устройств для вычисления симметрических булевых
функций n − r переменных G0 (X 2 ), G1(X 2 ), ... ,Gr (X 2 ) , r +1 двухвходовых элементов И и
одного (r+1)-входового элемента ИЛИ. Для построения более эффективной (с точки зрения оптимизации конструктивной
сложности) логической схемы ℜ(r, n − r) необходимо преобразовать формулу (2), используя
для этого следующие логические равносильности: если ab = 0 , то a ∨ b = a ⊕ b ; a = a⊕1 и
a (b⊕c) = ab⊕ac , где a,b, c ∈ {0,1}.
Тогда после несложных преобразований из формулы (2) получаем
F ( X1, X 2 ) = Er0 ( X1 ) H0 ( X 2 )⊕ Er1 ( X1 ) H1 ( X 2 )⊕ ... ⊕ Err ( X1 ) Hr ( X 2 ) ,
(3)
где Er0 ( X1 ), Er1 ( X1 ) , ..., Err ( X1 ) — полиномиально-однородные симметрические булевы
функции r переменных множества X1 ; H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) — симметрические
булевы функции n − r переменных множества X 2 , которые зависят от функций
G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
20 В. П. Супрун, Д. А. Городецкий
Для установления зависимости функций H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) от G0 ( X 2 ) , G1 ( X2 ) , ... ,Gr ( X 2 ) введем в рассмотрение два 2m -разрядных вектора-столбца gm , hm и
( )2m ×2m -матрицу трансформации Sm , где значение m вычисляется из двойного неравенства
2m−1 < r +1 ≤ 2m .
Будем считать, что gm = (G0 ,G1 , ... , Gr , 0,..., 0) и hm = ( H0 , H1 , ... , Hr , 0,..., 0) , а матрицу
трансформации
Sm
определим
рекурсивным
образом:
S0 =[ 1 ]
и
Sj
=
⎡ ⎢ ⎢⎣
S S
j j
−1 −1
0⎤
S
j−1
⎥ ⎦⎥
,
где
j = 1,2, ... , m . Тогда зависимость векторов gm и hm друг от друга выражается векторно-
матричным уравнением Sm ⊗ gm = hm , где через символ ⊗ обозначена операция сложения по
модулю два элементарных конъюнкций.
Пример 1. Пусть r = 7 , тогда m = 3 и уравнение S3 ⊗ g3 = h3 принимает вид
⎡G0 ⎤ ⎡H0 ⎤
⎡1 ⎢1 ⎢⎢⎢11 ⎢1 ⎢1 ⎢⎣⎢11
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1
0⎤ 0⎥ 00⎥⎥⎥ 0⎥ 0⎥ 10⎦⎥⎥
⊗
⎢⎢G1
⎥ ⎥
⎢⎢⎢GG32
⎥ ⎥ ⎥
⎢⎢G4
⎥ ⎥
⎢G5 ⎥
⎢⎢G6
⎥ ⎥
=
⎢ ⎢
H1
⎥ ⎥
⎢ ⎢ ⎢ ⎢ ⎢
H H H
2 3 4
⎥ ⎥ ⎥ ⎥ ⎥
.
⎢H5 ⎥
⎢ ⎢
H
6
⎥ ⎥
⎢⎣G7 ⎦⎥ ⎢⎣H7 ⎥⎦
Отсюда следует система логических уравнений, которая представляет собой зависи-
мость функций H0 ( X 2 ), H1 ( X2 ) , ... , Hr ( X2 ) от G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) :
G0 ( X 2 ) = H0 ( X2 ) ,
⎫
G0 ( X 2 )⊕G1 ( X 2 ) = H1 ( X 2 ) , G0 ( X 2 )⊕G2 ( X 2 ) = H2 ( X2 ) ,
⎪ ⎪ ⎪
G0 G0
( (
X X
2 2
)⊕ )⊕
G1 G4
( X 2 )⊕G2 ( X2 )⊕ (X2 )=H4 (X2 ),
G3
(
X
2
)
=
H3
(
X
2
)
,
⎪⎪ ⎬ ⎪
G0 ( X 2 )⊕G1 ( X 2 )⊕G4 ( X2 )⊕G5 ( X2 ) = H5 ( X 2 ), ⎪
G0 G0
( (
X X
2 2
)⊕ )⊕
G2 G1
( X 2 )⊕G4 ( X2 ( X 2 )⊕ ... ⊕G7
)⊕G6 ( X2 )
(
=
X2 )= H H7 ( X2
6( ).
X
2
)
,⎪⎪ ⎭⎪
(4)
Следует отметить, что локальные коды симметрических булевых функций H0 ( X2 ) ,
H1 ( X 2 ) , ... , Hr ( X2 ) и G0 ( X 2 ) ,G1 ( X2 ), ... ,Gr ( X2 ) при условии, что 2m−1 < r +1≤ 2m , связа-
ны между собой таким же образом, как и сами функции.
Логическая схема устройства ℜ(2). Из представления функции F = F ( X1, X 2 ) по-
средством формулы (3) следует, что для построения эффективных логических схем устройств
ℜ(2, 2) и ℜ(3, 2) необходимо иметь оптимальную (в определенном смысле) логическую схе-
му устройства ℜ(2) , которое предназначено для вычисления (реализации) произвольных
симметрических функций F , зависящих от двух переменных z1 и z2 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
21
На рис. 1 приведена логическая схема устройства ℜ(2), синтезированная эвристическим способом. Устройство ℜ(2) имеет три входа, на которые подается двоичный вектор настройки u(F ) = (u0 ,u1,u2 ), значения разрядов которого определяются с помощью таблицы на-
стройки.
Сигналы настройки Выход
и0 и1 &
M2 F
и0 и1 и2 π(F)
0 0 0 000
0 z1 z2 0 0 1
z1 z2
1 010
1 z1 z2 0 1 1
и2 Рис. 1
0 z1 z2 1 0 0
z1 z2
1 101
1 z1 z2 1 1 0 1 0 0 111
Сложность и глубина устройства ℜ(2) равны l(ℜ(2)) = 3 и g(ℜ(2)) = 2 . Логическая схе-
ма устройства ℜ(2), приведенная на рис. 1, является наиболее простой из всех существующих
аналогов.
Логическая схема устройства ℜ(2, 2). Для бисимметрической булевой функции
F = F ( X1, X 2 ) , где X1 ={x1, x2} и X 2 ={x3, x4} , формула (3) принимает вид
F ( X1, X 2 ) = E20 ( x1, x2 ) H0 ( x3, x4 )⊕ E12 ( x1, x2 ) H1 ( x3, x4 )⊕ E22 ( x1, x2 ) H2 ( x3, x4 )
или
F ( x1, x2 , x3, x4 ) = H0 ( x3, x4 )⊕( x1 ⊕ x2 ) H1 ( x3, x4 )⊕ x1x2 H2 ( x3, x4 ) .
(5)
Из системы уравнений (4) следует, что для формулы (5) справедливы следующие соот-
ношения: π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) и π( H2 ) = π(G0 )⊕π(G2 ) . На рис. 2 приведена логическая схема устройства ℜ(2, 2), которая синтезирована на ос-
нове применения формулы (5) с использованием схемы ℜ(2) (см. рис. 1). При этом логическая схема ℜ(2) была использована трижды.
и0
и1 & и2 и3
и4 & М2 &
и5
M2 F
х1 М2 х2
&
и6 М2 и7 & и8
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
22 В. П. Супрун, Д. А. Городецкий
Поясним метод построения вектора u ( F ) = (u0 ,u1, ... ,u8 ) — вектора настройки устройства ℜ(2, 2) на вычисление заданной функции F = F (X1, X 2 ) .
С помощью локального кода π( H0 ) из таблицы получаем значения первых трех разрядов u0 ,u1,u2 вектора u(F ). Естественно, что при этом необходимо заменить переменные z1 и
z2 на переменные x3 и x4 соответственно.
Далее с помощью локальных кодов π( H1 ) и π( H2 ) из таблицы получаем значения остальных разрядов u3,u4 ,u5 и u6 ,u7 ,u8 вектора настройки u(F ).
Пример 2. Предположим, что на выходе устройства ℜ(2, 2) (см. рис. 2) требуется реа-
лизовать бисимметрическую булеву функцию
Так как
F ( x1, x2 , x3, x4 ) = x1 x2 ( x3 ⊕ x4 )∨( x1 ∨ x2 ) x3 x4 .
( ) ( )F = x1 x2 x3 x4 ∨ x3 x4 ∨ x1 x2 ∨ x1 x2 x3x4 ∨ x1x2 x3 x4 ,
то
( )F = x1 x2G0 ( x3, x4 )∨ x1x2 ∨ x1 x2 G1 ( x3, x4 )∨ x1x2G2 ( x3, x4 ) ,
где π(G0 ) =(0,1, 0) и π(G1 ) = π(G2 ) = (0, 0,1) .
Отсюда следует, что двоичный код бисимметрической булевой функции F = F ( X1, X 2 )
равен ω( F ) =(π(G0 ), π(G1 ), π(G2 )) =(0,1, 0, 0, 0,1, 0, 0,1) .
Из системы уравнений (4) получаем π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) и
π( H2 ) = π(G0 )⊕π(G2 ) . Так как π(G0 ) =(0,1, 0) и π(G1 ) = π(G2 ) = (0, 0,1) , то π( H0 ) = (0,1,0) ,
π( H1 ) =(0,1,1) и π( H2 ) = (0,1,1) .
Принимая во внимание описанную выше процедуру построения вектора настройки
u(F ), получаем u0 = x3 , u1 = x4 , u2 = 1, u3 = 1 , u4 = x3 , u5 = x4 , u6 = 1, u7 = x3 и u8 = x4 . Первообразная функция устройства ℜ(2, 2) имеет вид
F ( x1, x2 ,u0 ,u1, ... ,u8 ) = u0 ⊕u1u2 ⊕( x1 ⊕ x2 )(u3 ⊕u4u5 )⊕ x1x2 (u6 ⊕u7u8 ) . Сложность и глубина логической схемы устройства ℜ(2, 2) составляют l(ℜ(2, 2)) = 21 и g(ℜ(2, 2)) = 4 . Кроме того, число внешних выводов схемы равно 12. Отметим, что приведенная выше логическая схема ℜ(2, 2) предназначена для реализации любой из 512 бисиммет-
рических булевых функций типа „ 2,2 “.
Логическая схема устройства ℜ(3, 2). Формула (3) применительно к бисимметриче-
ской булевой функции F = F (X1, X 2 ) , у которой X1 = {x1, x2 , x3} и X 2 = {x4 , x5}, принимает
вид
F ( X1, X 2 ) = E30 ( X1 ) H0 ( X 2 )⊕ E31 ( X1 ) H1 ( X 2 )⊕ E32 ( X1 ) H2 ( X2 )⊕ E33 ( X1 ) H3 ( X2 )
или
F ( x1, x2 , x3, x4 , x5 ) = H0 ( x4 , x5 )⊕( x1 ⊕ x2 ⊕ x3 ) H1 ( x4 , x5 )⊕
⊕ ( x1x2 ⊕ x1x3 ⊕ x2 x3 ) H2 ( x4 , x5 )⊕ x1x2 x3H3 ( x4 , x5 ) .
(6)
Из системы (4) получаем π( H0 ) = π(G0 ) , π( H1 ) = π(G0 )⊕π(G1 ) , π( H2 ) = π(G0 )⊕π(G2 )
и π( H3 ) = π(G0 )⊕π(G1 )⊕π(G2 )⊕π(G3 ) .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Реализация бисимметрических булевых функций логическими схемами
23
Логическая схема устройства ℜ(3, 2) , синтезированная на основе применения формулы
(6), приведена на рис. 3. Причем при ее построении была использована (четыре раза) логиче-
ская схема устройства ℜ(2).
и0
и1 & и2 и3 M2 F и4 & М2 &
и5
М2
и6 и7 & М2 & и8
х1 х2
≥2
х3
&
и9 М2 и10 & и11
Рис. 3
Настройка устройства ℜ(3, 2) осуществляется по аналогии с настройкой устройства ℜ(2, 2), рассмотренной в предыдущем разделе. Однако при построении вектора настройки u(F ) = (u0 ,u1, ... ,u11) необходимо четыре раза обратиться к таблице.
Первообразная функция логической схемы устройства ℜ(3, 2) , приведенной на рис. 3,
имеет вид
F ( x1, x2 , x3, x4 , x5 , u0 ,u1, ... , u11 ) = u0 ⊕u1u2 ⊕( x1 ⊕ x2 ⊕ x3 )(u3 ⊕u4u5 )⊕
⊕ ( x1x2 ⊕ x1x3 ⊕ x2 x3 )(u6 ⊕u7u8 )⊕ x1x2 x3 (u9 ⊕u10u11 ) . Пример 3. Предположим, что на выходе устройства ℜ(3, 2) требуется реализовать би-
симметрическую булеву функцию
F ( X1, X 2 ) = x1 x2 x3 ( x4 ∨ x5 )∨( x1x2 ∨ x1x3 ∨ x2 x3 ) x4 x5 , где X1 = {x1, x2 , x3} и X 2 = {x4 , x5}.
Так как
( )F ( x1, x2 , x3, x4 , x5 ) = x1 x2 x3 ( x4 ∨ x5 )∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 0∨
( )∨ x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 x4 x5 ∨ x1x2 x3 x4 x5 ,
то
F ( x1, x2 , x3, x4 , x5 ) = F30 ( x1, x2 , x3 )G0 ( x4 , x5 )∨ F31 ( x1, x2 , x3 )G1 ( x4 , x5 )∨
∨F32 ( x1, x2 , x3 )G2 ( x4 , x5 )∨ F33 ( x1, x2 , x3 )G3 ( x4 , x5 ) ,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
24 В. П. Супрун, Д. А. Городецкий
где π(G0 ) = (0,1,1) , π(G1 ) = (0, 0, 0) и π(G2 ) = π(G3 ) = (0, 0,1) . Двоичный код ω( F ) бисимметрической булевой функции F = F (X1, X 2 ) равен
ω( F ) =(π(G0 ), π(G1 ), π(G2 ), π(G3 )) = (0,1,1, 0, 0, 0, 0, 0,1, 0, 0,1) .
Принимая во внимание систему уравнений (4), вычисляем локальные коды симметриче-
ских булевых функций H0 ( x4 , x5 ), H1 ( x4 , x5 ), H2 ( x4 , x5 ), H3 ( x4 , x5 ) , входящих в разложе-
ние (6), согласно следующим формулам:
H 0 (x4 , x5 ) = G0 (x4 , x5 ), H1(x4, x5 ) = G0 (x4, x5 )⊕ G1(x4, x5 ) , H 2 (x4 , x5 ) = G0 (x4 , x5 )⊕ G2 (x4 , x5 ),
H3(x4 , x5 ) = G0 (x4 , x5 )⊕ G1(x4 , x5 )⊕ G2 (x4 , x5 )⊕ G3(x4 , x5 ) . Так как здесь π(G0 ) = (0,1,1) , π(G1 ) = (0, 0, 0) , π(G2 ) = π(G3 ) = (0, 0,1) , то π( H0 ) = (0,1,1) , π( H1 ) =(0,1,1) π( H2 ) = (0,1, 0) и π( H3 ) = (0,1,1) . Из таблицы настроек устройства ℜ(2) применительно к симметрическим булевым функциям H0 = H0 (x4 , x5 ) , H1 = H1(x4 , x5 ) , H 2 = H2 (x4 , x5 ) , H3 = H3(x4 , x5 ) , получаем
u0 = 1, u1 = x4 , u2 = x5 , u3 = 1 , u4 = x4 , u5 = x5 , u6 = x4 , u7 = x5 , u8 = 1, u9 = 1, u10 = x4 и
u11 = x5 .
Логическая схема устройства ℜ(3, 2) , приведенная на рис. 3, имеет сложность l(ℜ(3, 2)) = 33, глубину g(ℜ(3, 2)) = 4 и 16 внешних выводов (3 информационных и 12 на-
строечных входов, а также выход).
С помощью логической схемы устройства ℜ(3, 2) при соответствующей настройке можно реализовать любую из 4096 бисимметрических булевых функций F = F(X1, X 2 ) , где X1 = {x1, x2 , x3} и X 2 = {x4 , x5}.
Заключение. В настоящей работе приводятся логические схемы устройств ℜ(2), ℜ(2, 2) и ℜ(3, 2) , которые выгодно отличаются от всех существующих аналогов по конст-
руктивной сложности, глубине и числу внешних выводов. В частности, они превосходят по
всем параметрам логическую схему устройства ℜ(r, n − r) , описанную в работе [8]. Для построения логических схем устройств ℜ(r, n − r) , где n − r ≥ 3 , требуется разрабо-
тать (а затем использовать) эффективные логические схемы устройства ℜ(n − r).
СПИСОК ЛИТЕРАТУРЫ
1. Карцев М. А. Арифметика цифровых машин. М.: Наука, 1969. 576 с.
2. Авгуль Л. Б., Супрун В. П. Синтез быстродействующих логических схем методом каскадов // Изв. вузов. Приборостроение. 1993. Т. 36, № 3. С. 31—36.
3. Авгуль Л. Б., Супрун В. П. Синтез схем симметрических булевых функций в базисе линейной и монотонных функций // Там же. 1995. Т. 38, № 11—12. С. 33—36.
4. Супрун В. П., Седун А. М. Реализация симметрических булевых функций логическими схемами // Там же. 1998. Т. 41, № 9. С. 32—38.
5. Супрун В. П., Седун А. М. Схемная реализация фундаментальных симметрических булевых функций посредством логических устройств со сложной настройкой // Мат. IV Междунар. конф. „Автоматизация проектирования дискретных систем“. Минск, 2001. Т. 2. С. 86—91.
6. Супрун В.П. Синтез логических устройств для вычисления полиномиально-однородных симметрических булевых функций // Мат. VI Междунар. конф. „Автоматизация проектирования дискретных систем“. Минск, 2001. Т. 2. С. 146—153.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5
Анализ КА для синтеза частот с помощью функций целочисленного аргумента
25
7. Супрун В. П., Седун А. М. Схемная реализация частично симметрических булевых функций // „Логическое проектирование“. ИТК НАН Беларуси. 2000. Вып. 5. С. 29—37.
8. Супрун В. П., Седун А. М. Синтез устройства для вычисления бисимметрических булевых функций // Там же. 1998. Вып. 3. С. 69—77.
Валерий Павлович Супрун Данила Андреевич Городецкий
Сведения об авторах — канд. техн. наук, доцент; Белорусский государственный университет,
кафедра уравнений математической физики, Минск; E-mail: suprun@bsu.by — аспирант; Белорусский государственный университет, кафедра уравнений математической физики, Минск; E-mail: danila.gorodecky@gmail.com
Рекомендована кафедрой уравнений математической физики
Поступила в редакцию 09.11.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 5