Decomposition of Symmetric Boolean Functions

Cybernetics and Systems Analysis, Vol. 34, No. 3, 1998
DECOMPOSITION
OF SYMMETRIC
SYMMETRIC
BOOLEAN
FUNCTIONS
MONOTONE
FUNCTIONS
AND PARTIALLY
IN A B A S I S O F
UDC 519.713:681.32
L. B. Avgul' and A. S. Petrochenko
Decomposition methods for symmetric Boolean functions (SBF) and partially symmetric Boolean functions (PSBF)
are of considerable practical interest, because systems of such functions describe the operation of many standard computer
functional components. The efficiency of circuit-engineering realizations of SBF and PSBF logical diagrams (as measured by
circuit complexity and speed) is mainly determined by the analytical representation of these functions.
In this article we consider new SBF and PSBF representations using their decomposition in a basis of monotone
functions.
BASIC CONCEPTS AND DEFINITIONS
An arbitrary SBF of n variables F = F(X), X = (x t, x 2. . . . . xn) is uniquely representable by an (n + 1)-bit binary
code r(F) = (a-0, a-1. . . . . rn), where a-i is the value of F on (any) tuple of the variables x t, x 2 . . . . . x n containing exactly i
ones(0 < i < n ) [ 1 ] .
If the SBF F has working values (weights of the tuples on which F takes the value 1) a t, a 2. . . . . a r (1 < r < n +
1), then it is represented in the form F = F ala2'''ar. For r = 1, the SBF F = F a ( x ) is called a fundamental (or an
elementary) SBF (FSBF) with threshold a, 0 < a < n.
Clearly, a-i = 1 if and only if i E {a 1, a 2 . . . . . ar} and also
tl
i=0
It is easy to show that the SBF F is also representable in the form
tl
F =
v
(z)
1-0
If t, t + 1. . . . . n are the working values of the SBF F, then the function Ftn"t+l ..... n(X) = Mtn(X) is called a
monotone SBF (MSBF) with threshold t (0 _< t _< n). MSBF M n t are also called majority functiom with threshold t [2].
Here and in what follows, we assume that Mn t - 1 for t _< 0 and M n t - 0 for t > n.
SBF essentially dependent on n variables include two linear functions" addition modulo 2 Ln(J 0 = Fln '3 ..... 2]n/2[ - i ( j 0
= x I @ x 2 ~ ... (Bx n and its inverse Ln(X) = F~n' 2 ..... 2[n/Zl(x) = x t ~ x 2 ~ ... ~ X n .
D E C O M P O S I T I O N OF SBF IN A BASIS OF M O N O T O N E FUNCTIONS
L e t Gs h = (h, h . . . . .
.... Xk), Z = (Xk + l , Xk + 2 . . . . .
h) b e a tuple of length s whose elements are h E {0, 1} and G~o -= Z ; X ( Y , Z), Y = (x 1, x 2,
Xn) , k <_ n.
Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 26-40, May-June, 1998. Original article submitted May
15, 1996.
1060-0396/98/3403-0337520.00 9
Plenum Publishing Corporation
337
Xll
'
-
....
X12
X1::3
X14.
x15
S
,["
s2
iii i
-!
.......
ltll
l--~ -
L__..
Fig. 1
Then the disjunctive-conjunctive decompositions of the SBF F in k variables from Y take the form
k
(3)
~(x) = v ~,~<z) FL(y),
y=O
k
F(X) = & (~,i(Z) v .Fk](10),
1-o
(4)
.,_,,_j _~G.~, z) are the "residual" SBF; FZ(r) is an r, SBF wire ~eshold y, 0 _< j <_ k. The local codes of
where ~,/~,_, = F(~._~
the functions ~/Z) can be determined from the local code 7r(F) of the SBF F:
~(~,,~z)) = ,~(F(c, ~ j, G~, z)) = (~j, ,,~ +, ....
If k = n, expressions (3) and (4) take the form (1) and (2), respectively.
338
,,,j +,, _ ,.).
(5)
T H E O R E M 1. I f n > 2, 1 < k < n, then
{ k/21
(6)
l--0
where
2:z) =
2(so 9
1
~2l+1 (Z) = ~2l_2(Z) ~) ~21-1 (Z) ~ ~o2/(Z) (~3~21+1 (Z)
(7)
I
@j(Z) - 0 if j < 0 or j > k).
Proof. By orthogonality of the FSBF F~(Y), we rewrite (3) in the form
k
F(X) =
E S~
1-0
(8)
F/( Y)"
It is shown in [3] that FSBF may be represented in an MSBF basis by the following relationships (I = 0, [k/2]):
F~l(Y) = (M~ l(Y) ~ M~I+ 2(I/))Lk(Y)' l
F~ t+~ (~0= (M~(~ 9 M~+~(r)) L,(~, 1
e~ l-' (r) (M~ l-~
F~I(Y)
(r) ~ ~ l
(9)
(r)) L,(r),
I (y)) Zk(y), t
'-'(It) 9 M}+'+'
=
(10)
Substituting (9) in (8) and transforming, we obtain the decomposition (6) in which the "residual" SBF ~(Z) are
calculated from (7). Q.E.D.
T H E O R E M 2. If n >__ 2, 1 < k < n, then for even k
k/2
F(X) = x.0(Z)~) E Qr
l=l
M~t-l(Y) Lk(Y) ~ r'21(Z) M/~/- I (Y)) ,
(11)
and for odd k
{ kl2l
F(X) = *o(z) 9 ~ (~2t-,(Z) M~ ~-' (r) rk(r) 9 ~2r
M~ t-~ (r)) 9
(12)
l-1
9 ~,(z) M**(r),
where
xo(Z) = ~,o(Z); x, (z) = ~'x(z) 9 ~,2(z);
g21-1 (Z) = ~2l_3(Z) ~) ~o2l_2(Z) ~ ~O2l-1(Z) ~) ~o2/(Z),
l = 2, 3 . . . . .
[ k / 2 ];
tc2/(Z) = ~o2I_2(Z)~r
(13)
.
l = 1, 2 . . . . .
[k/2 ];
if k is odd, Kg(Z) = ~Ok_E(Z) 9 ~ok(Z).
The theorem is proved by substituting (10) in (8) and making appropriate transformations.
339
Example 1. For k = 6, decomposition (6) has the form
F(X) = p0(Z) 9 ~0~(Z) L6(Y) 9 ~02(Z)M~(V) 9 ~3(Z) M:(r) L6(r) 9
9 ~4(Z) M~(Y) 9 ~0s(Z)M:(r)Z~(Y) 9 V6(Z) M~(Y).
For k = 7, decomposition (12) has the form
e(x) = ~o(Z) 9 x~ ( z ) z.7()')9 ~2(z) M~ (r) 9 ~3(z) M:(Y) L7()9 9
9 k4(Z) M:(Y) 9 x5(Z) M : ( Y ) L7(Y ) (E) ~:6(Z) M:(Y) 9 ~7(Z) M:(Y).
Note that for decomposition in k = n variables, Cj and Kj are binary constants. This particular case is considered in
[3].
Denote Y/= (Xi+ 1, Xi+2 ..... Xk), i < k; F i = Fi(Yi, Z) = (diF(X)/(dxldx2 ... dxi)) is an i-th derivative of the SBF F
with respect to the variables x t, x 2 . . . . . x i.
The relationship between the "residual" functions 6flZ), KflZ) and the derivatives F / is established by the following
theorems.
T H E O R E M 3. I f n ___ 2, 1 _< k _< n, 1 _< l _< [k/2], then
~Oo(Z) = F(G ~ zg,
tpl (Z) F I (Of_ 1' Z))
2 I
0
=
~2t(z') =
F
(14)
(a~t _ z, a~ _ 2l, z ) ,
3
1
0
~'2l + 1 (Z) = F (Gil_ 2, G~-2t-I , Z)
(~(LO - 0 i f j > k).
Proof. Substituting Y = G~ in decomposition (6) for SBF F(X) = F(Y, Z), we obtain F ( G : , LO = r
Write the expressions of the first three derivatives F t, F 2, and F 3 for the SBF F represented in the form (6):
[kl2l
F(Y, Z) = ~o(Z) (3 tp1(LO Lk(Y)(~ ~ QP2/(LO M~l(Y) (~ ~'2l+1 (Z) M:l(lo Lk(lO).
1-1
Note that
dLk(lO
dx 1
dM:l(Y)
= 1; - - - - - = M:t(O, rl) 9 M:~(X, Y~ ) =
dxl
21
~,r 2l-1
= M/~-l (Yl) $ '"k-1
L-,21-1
(Yl) = ~k-1 (Y1)'
dM:l(lo Lk(lO' -- M:l( O, YI ) Lk(O, YI ) * M:l( I' Y1). Lk(l, YI ) =
dx I
21
. 21-I
-= Mi_I(YI) Lk_I(YI) (3 mk_ 1 (1"I) Lk-I(Y1) = M~k/I(Y1 );
..,2l-1
d2M:l(Y)
dx l d x 2
dl'k-I (YI)
=
dx 2
..,2l-1
,-.2/-1
. = t ' k _ I (0, Y2)(t)t'k- 1 (1, Y2)-'-
..2l-1
..21-2
..2l-I
..2/-2,
= t'k-2 ( r 2 ) 9
( I " 2 ) = / ' k - 2 (I"2)V /'k-2 (Y2);
d2M:l(y)Lk(lO
dMi21-1(Y1)
..2l-I
dxldX2
=
dx 2
= rk-2 (Y2);
340
d3M21(Y)
d /~,21-1
...2/-2
ax~ax2ax3 = 2 - ~ : ~ - 2 ( r ~ ) v ~ _ ~ ( r 2 ) ) =
21-1
21-2
21-I
,..2l-2.
= (Fi_ 2 (0, I:3) V F/~_2 (0, Y 3 ) ) 9 (F/~_ 2 (1, Y3) v r t _ 2 t l, I"3))=
.,2l-I
21-2
F2l-2
21-3
= (/'k-3 (I"3)V Fi_ 3 (I:3)) ~ ( k-3 (]"3)V Fi_ 3 (1:3))=
...21-1
21-3
= /'k-3 (]:3) V F/~_3 (]:3);
... 2l-1
d3M~I(Y) Lk(Y)
aX~ a~dx~
a1'k-2 (Y2)
-
ax~
~2l-1
,.,2l-2.
= ,-~-3 (r~) v ~ _ ~ try).
Then
[k/21
e ~(r~ , z) = ~,~ (z3 9 ~
2l-1
(,/,2t(z) F ~,-1
(r'~) 9 v,2~ + ~(z) M i ~ ( ~ ) ) ;
l-'-1
F2(y2 , Z)
=
[ k12]
:~t-I
~ (1/"2/(Z) k k-2 (Y2)
l=1
v~t'2:
t-1
k-2 I,Y2)) e ~21+1 (Z) J~k-2 (r2));
[ k/2l
F3(y3, Z) = ~ (~2/(Z) (~k/...51(Y3) V ~/_..33(Y3)),
l=I
I
For YI "- a~k-l, Y2 -" (G21-2,
F' (a~_ , , Z) = ~ (Zg, F ' @ t _ ~, a ~ ~, Z) = ~ : Z ) ,
3
1
0
F (a~t_2,Gi_2t_ ~ , Z) = '/'2t+l(Z).
Q.E.D.
T I t E O R E M 4. I f n >__ 2, 1 < k < n, 1 < l < [k/2], then
(15)
r,.o(Z") = F(G 0, Z);
,~ (zj = e 1 (Ok~ ~, z);
r21(Z) = F2(GII-2 , GO- 21, Z), l= 1, 2 . . . .
, [k/2 l;
':2t-~ (z) ---- F3(a~l_3 , a k~- 2 l , Z ) , l = 2, 3 . . . . .
[ k / 2 ];
xk(Z) = F2(Gl_2, Z) if k is odd.
The theorem is proved similarly to Theorem 3.
is the local code of the derivative F i of the SBF F(X), then we have the following
If 7r(F i) = (Troi, 7rl i , .... 7rn_i)
i
theorems.
T t t E O R E M 5. If n >_ 2, 1 < k < n, 1 < l < [k/2], then
'~(~'o(Z)) = (:~o, ~1 . . . . .
--
,
n,, - t);
9 ~ ~n-
k);
(16)
g(P2/(Z)) -'- ( 2 l - 2, g 21 - 1 . . . . .
g n2- k + 2 l - 2);
3
g(~O2/+ I (Z)) = (g23l_ 2, ;g231- 1 . . . . . ;gn - k + 2 l - 2)'
341
Proof. From Theorem 3, we directly obtain
~(~:o(Z)) = ~(F(Cff, Z)),
~(V,~ (Z)) = ~(F ~(C~_~, Z)),
~(~2~z))
:
~ ( F ~ ( ~ _ ~ , Gi-2~,
o z)),
x(~2~+~(z)): ~(F~(~_2, ai-2~-~,
o
z)).
This means that ~,flZ) are "residual" functions in disjunctive decomposition (3) of the SBF F and its derivatives F l,
F 2, and F 3. Therefore, the local codes r(~,flZ)) can be computed from (5), which proves (16).
THEOREM 6. I f n _> 2, 1 < k < n, 1 __< l < [k/2], then
~(~(z))
(~o,~I ..... ~ - i);
:
~(K I ( Z ) ) = ( ~ : , ~ ,
);
...,~n-k+l
2
~l
=
(17)
I, 2 ..... [k121;
3
1=2,3 .....
[k/21;
2
if k is odd.
The theorem is proved similarly to Theorem 5.
Theorems 5 and 6 suggest a simple algorithm to f'md the "residual" functions ffj(LD and KflZ) in decompositions (6),
(11), and (12). This algorithm can be described as follows.
Construct the trapezoidal table T(c~(n)) with four rows. The zeroth row is some binary (n + 1)-bit vector a(n) =
(uo ~ a l 0 . . . . . c~o). The elements of the three other rows are defined recursively:
r
r-I
r-1
a t =a t
~at+ 1 , r=1,2,3;
(18)
t=O,n-r.
If ce(n)
a-(F), then the first, second, and third rows of the table T(x(F)) are the local codes of the derivatives F t,
F 2, and F 3, respectively [4]. The local codes of the "residual" functions ffflZ) and KflZ) are "cut out" from the table T(a-(F))
=
using (16) and (17).
Example 2. Let the SBF F = F(X), X = (x I, x 2 . . . . . Xg), be def'med by its local code a-(F) = (a-0, ~rI . . . . . 7r9) =
(0010011010). Under the conditions of Example 1 we determine the local codes of the "residual" functions ffflZ), j = 0, 6,
and xj(Z), j = 0, 7:
r(~(~)
'I? o~ o l o ~ o~ o
~
I0 i 1 o]I o i ~ i
o11 1 oii o ~ ~
:
l
342
oio
00110
I 0
~(Wo)
=
(Uo,#q, #a, ~ )
=
(0010);
~(mo) = (#to,# q , ~2) = (00 I);
~ I ) --_ (01 lO);
~(.~ ) = (~:. =~. #l ) = (IIO);
,:(~,~) = (=o~, ,~ ~, ,~:, =~) = (~oI ~);
,~(~,~) = (,:o~, =~, =:, ,~:) = (x too);
~(.~) = (~o~, ~. ~) = (~o~);
=(~) = (~, #~, ,~:)= (~oo);
"rl:(~4)= ('zr22' :z:,~42,zr~)= (1111);
~<,~:> = ( , 4 , , q , 4 , , 4 ) = (ooo~);
~:(K4) = (#22, ~:a2, #~) = (111);
#(~I)
= (~0 I ' ~I I) ~ i '
~(~6) = (=4~, #5~,~) = (~~o);
~ ( ~ ) = ( s,
For k = n, relationships (16) and (17) respectively take the form
~'o = 0~o; ~
= 0~ ; v : l = ~ 2 ~ - ~; }
(19)
g"2t+l =zr3t-2, 1 ,r 1 ~ [n/2];
K0 -- ~0; KI = "rl:lI ;
K21 = Jr~l- 2, I 9 l 9 I n / 2 ];
(20)
~t-1
=~r23/-a, 2 9 l ~ [ n / 2 ] ;
2
Kn = ~n-2,
if n is odd.
Example 3. For the SBF F = F(X) from Example 2 we use (19) and (20) to find the decomposition coefficients of ~'7
and KT fOr k = n = 9 , j
= 0, 9"
[~01001104_ 0
"~0 10 0 110 10
~]1 1 0 1 0 1 1 1
0~10101il
r(~(r)) =
, T(#r(F))=
,NoNoVo
,Bo ,Va
,'o = "o =~, ,', = ',o '=~, ~ = C =~" ~, = ,,o ' = ~ -o= ~o = ~, -, = ,,,'=~; -, = C =~ , -~ = ,,,'=~"
~, = 4 = ~ - ~ = ~:=~. ,~, =V=,.,~, = 4=~, ,, = 4 = , . ,, = ,q=~. ,, = ,4=~.~, = ~/=~.
,,, =4=~. ~, =,,7=~.
-, =,4=~, ~, =,d=o.
Hence,
- z,(x) 9 - ~ (x~ 9 -9~(x) ~(x~ 9 - ? ( ~ o 9 - ? ( x o 9 - ? ( x o ~ ( x ~ .
LOCAL CODES AND DERIVATIVES OF PSBF
Nontrivial partial symmetry induces a partition of the variables X = (x 1, x2 . . . . . x n) of the PSBF f = fiX) into N
tuples X l, X2. . . . . XN' i < N < n, so that f is symmetric with respect to any pair of variables from the same tuple X i, i =
1 .....
N.
Let X = ( X 1 , X 2 . . . . . XN) and S i = (Xl i, x2 i, ..., ~mi), 1 <_ m i < n,
tr
~
m i --- n. Then the number of equivalence
P'I
classes of the PSBF f is given by
343
N
p = 1[-i (', + I).
i=I
Each equivalence class is characterized by the vector
A = ( a 1,a 2 . . . . .
aN) , a i e (O, I . . . . .
mi}, i = 1, N.
The local code C(f) of the PSBF f is a binary vector of length p where each component is the value of f on the
corresponding equivalence class of the tuples of its arguments.
Ordering the vectors A, we represent cO') in the form
C(y) = (C ~ 1 7 6 1 7C6o o ' " l
cOl ... mjv
....
CI0...I
I
e
9
~
9
e
l
9
9
~
Coo"" m~
C0m.z... 0 C0-h... 1
9
C I 0 . . . mjv
. . . . clm.z...o c l m r
'
e
e
e
1 ...
l
- ' '
,
C0nh ... %v
)
CI1... I
C 1 m.~ . . . m v '
'
'
....
CII...0
I
I
cOl ... o c O l . . . 1
e
"
e
I
C ,,%0
"'"
C r'hO "" na'v, C ,~ ] " .. 0 , C r,h l "'" 1 ,
'
I
e
9
9
C10... 0
CI1... m~,
)
o
"'"
~
,,lo
I C
C nall "'" nan
9
e
I
9
(21)
1
"'"
C nalm'z''" 0
P
C,,%,,h..
1
9
,
9
.
.
~
C~"2
" . .
/'tiN),
where the Boolean constant C a'a2"''aN is the value of the PSBF f on tuples of variables from X/that satisfy the condition
~
x/=a
i,
i= i,N.
1=1
This implies that Cala2..'aN -d~Olal , G l _ a l . . . . . G "
GOmN-aP"
Treating C ala2.'.aN as a vector of unit length, we define inductively for 1 < g _< N - 1:
C ~a2"'" a, = (C ~a2"'" % o, C ~a2"'" % * , ..., C ~a2"'" % %
+ 9.
Hence,
cata~...a, = C(f( G~ ,Gino1 a~,
.
.
.
.
9 Gal,, GO
m, - , , , x : + l . . . . .
xlv)).
(22)
Denote
=
z k = (XI k, x 2 . . . . .
.,
=
xk+ 2 . . . . .
XN); Z = Z Rat = (X2, X 3 . . . . .
x~);
XN) , I ~ k ~ . m 1.
Forming the disjunctive-conjunctive decomposition of the PSBF.fiX) in k variables from yk and grouping identical
"residual" functions, we obtain
k
/ ( X ) = v @s.(Z It.) F ~ ( Y * ) ,
(23)
j=O
k
/ ( X ) = & ( @ / , Z * ) V FI(Yk)),
1=o
where the "residual" PSBF are
344
(24)
(25)
%<z*) = I ( a f _ 1., a ) , z *), / = 0,~.
The local codes of the PSBF ~/Z/9 are determined by the following theorem.
T H E O R E M 7. F o r l < k _ < m 1 , 0 - < j
c(%<zk))
<--k,
= ( c j, c j + ~ . . . . .
(26)
c j + .~ - k).
Proof. Form a disjunctive decomposition (23) of the PSBF ,I,/Z e) in the variables from Xlk:
%< zk) = .~ v k%<a.~_,_,,
o
c}, z) r.~ _ k(x~5.
t=O
Using (22) and (25), we write
90
c(%<a.~_k_,,
a;. z)) = C(.f(Gt~ -i-,. G]+ t, Z)) = C TM,
where t = 0, m t -- k.
Thus, C(~/Zk))=
COROLLARY.
(C J, CJ+I ..... cJ+m,-k). Q.E.D.
For k = m t,
c09 = (c(%(z)), c(a,, (z)) . . . . .
c(%~(z)) = (c o c ~
c %.
(27)
Example 4. Some PSBF f = f(X) for n = 12, N = 2, m I = 9, m2 = 3 is defined by its local code in the form (21):
CO") = (011011011001111110(K)00010101111011000111)By (27), in particular, we have
cOO = ( c ( % ( z ) ) , c ( o t (z) . . . . . c ( % ( z ) ) ,
where
C(rI,o(Z)) = C O = (0110), C ( O 1 ( Z ) ) - C t = (1101), C(r
C(%(Z)) = c 3 = (1~11), c(o4(z)) = c 4
c(~6(z))
(looo), c(%(z)) = c s = ( o o o i ) ,
= c 6 = (01Ol), c ( ~ , 7 ( z ) ) = c 7 = (111o), c(q~s(z') ) = c 8 = (1 lOO),
c(%(z))
For k
= C 2 = (1001),
= c 9 = (o 111).
7, the local codes of the "residual" functions in the decompositions (23) and (24), according to (26), have the
form
C(,~o(ZT)) = (C ~ C l C 2) = (011011011001),
c(o~(z7)) = (c ~ c 2 c 3) = (l:O:lOOlllli),
C(~2(Z7)) - (C 2, C 3, (24) - (10011111 I000),
C(O3(Z7)) = (C 3, C a, C s) - (111110000001),
C(~4(Z7)) - (C 4 C 5 C 6) -- (100000010101)
1
1
1
c(%(zT)) = (c s, c 6, c 7) = (ooolololi 11o),
345
C(t~6(Z7))
---
(C 6, C 7, C a) --" (010111101100),
C(t~7(Z7)) __. (C 7, C 8, C 9) = (111011000111).
Denote by ]~ = f~(Z#) = (dkJ(X)/dP~ the k-th derivative of the PSBF f with respect to the variables from yk, 1 < k
< ml; by COde) = (Ck0, CkI . . . . . Ckmt -k) the local code of the PSBF f k in the form .(27).
The elements of the vector C(f #) are determined by the following theorem.
THEOREM 8. F o r l < k
< m 1,0 < t < m l - - k ,
,-, t+l
e,..,,_,,
(28)
where Co/ = CJ, O < j < m 1.
Proof. By def'mition, f/c(Zg) = f k - 1(0 ' Zk) e f k , 1(1, Zac).
Then C(fk(Zk)) = C(fk-l(0, Z~) 9 C(fk-l(1, Z~).
The functions f k - l ( 0 , Z~ and f k - l ( 1 , Zk) are "residual" in decompositions (23) and (24) of the PSBF f k - I in the
variable xk1. Thus, by (26) we write
c c f k - ~(o. z k)) = (c o_ ~ . c~ _. . . . . .
ck% T k).
_
c~f k-~ (l, z * ) ) = ( c ~ _ ~, c~_, . . . . .
~-k.+l
c,_~
).
whencec ~ k ( z k ) )
= (C~k-1 (~ 4-1 , 4-1 9 C 2k-I . . . . . C~_
ml?k 9 C~_
ml?k+l ). Q.E.D.
Note that the sign 9 denotes addition modulo 2 of corresponding bits in the local codes C~.
Thus, the PSBFf(X) is uniquely deemed by its (m I + 1)-component local code C(f) = (C ~ C 1. . . . . cm~), just like
the SBF F(X) is def'med by the (n + D-bit binary code ~r(F) = (~'0, Xl . . . . . ~'n)- The local codes of the "residual" functions
in the disjunctive-conjunctive decomposition off(X) according to (26) and the local codes of its derivatives according to (28)
can be determined similarly to the local codes of the "residual" functions of F(X) according to (5) and the local codes of its
derivatives according to (18). The mathematical apparatus developed for the SBF F(X) deemed by the code ~-(F) is thus fully
applicable to the PSBF f(X) deemed by the local code CO') if the elements 7ri, i = 0, n, are replaced with the components d ,
_
,,
i = O , m 1.
DECOMPOSITION OF PSBF IN A BASIS OF MONOTONE FUNCTIONS
We can now easily prove the following two theorems, which constitute the foundation for the decomposition of the
PSBF fiX) in a basis of monotone functions.
T t t E O R E M 9. For N >__ 2, 1 _ k < m 1, the PSBF fiX) has a decomposition of the form
t k/zl
k)
(z k) M:l(yk) Lk(rk).
(29)
l=O
where the local codes of the "residual" PSBF are deemed by the following relationships (1 <_ I _ [k/2])C ~ o ( Z k ) ) = (c ~ c ~ . . . . .
c"~-
k);
c ( ~ (z k)) = (Co, C~ ..... q.~- k);
k
co~2~(z )) = ( c i
21-2
, ci
,,-,rtvf
tqkxx
tp21t " ~ ' r 2 1 + l k~ 11---- k~3
346
21-1
(30)
, . . . , c2"~
2 C2I - 1
' 3
''''
-k+21-2
.
).
, c3mt - k + 2 1 - 2)
THEOREM 10. For N > 2, 1 __<k < m:, the PSBFfiX) has the decomposition
~:/2
I(X) = Ko(Z k) 9 ~ (K2I_l (Z k) M: 1-! (yk) Lk(yk) 9 K2/(Z k) M: l-I (yk)),
(31)
l=l
for even k and
[ k/2t.
f(X) = Ko(Zk)e ~ (K21_l (Z k) M: l-1 ( yk) Lk( yk) 9 K2/(Z k) M: l-I ( yk)) 9
(32)
/=I
9 Kk(Z k) M:(rk)),
for odd k. Here the local codes of the "residual" PSBF are determined by the following relationships:
C(Ko(Zk)) = (C0, C 1 , . . . , Gin1 - k);
,
-k+l
C(K 1(Z k)) = (CI1 CI:I. . . . . Clrnl
);
C(K21(zk)) = (C2l-2, c 2 l - I , . . . , c2ml-k+21-2),
[k/2];
C(K21_1(zk)) = (C32/-3, C~ l-2 . . . . . C3~-k+21-3) ,
l = 1,2 . . . . .
(33)
1 = 2, 3 . . . . . [k/2 l;
C(Kk(zk) ) = (C2k-2 c2k-I . . . . . C3~ - k - 2),
if k is odd.
To find the local codes of the "residual" fimctions in decompositions (29), (31), and (32), we construct the table
T(CO')) in which the zeroth row contains the local code of the PSBF fiX), and the first, second, and third rows contain the
local codes of its derivatives f l , ]2, and f3 calculated recursively from (28). The local codes of the functions ,I,I(Zt) and
K1(ZtS, 0 < j < k are "cut out" from T(C(J)) by (30) and (33).
Example 5. Find the local codes of the "residual" functions in decompositions (29) and (32) for k = 7 for the PSBF
fiX) from Example 4:
I01io
T(CO?)
,ooo
!
=
1111, 0010
o,o, ,,,o ,,| o,,,
I
i
1111 10(31 1001
C(Wo(Z 7))= (C ~ C 1 , C 2) -- (011011011001);
C(Wl (Z7))= (C~ C], <212)= (101101000110);
C(tl/2(zT)) = (C0, C12, C 2) = (I I I I00100001);
c ,3(z7)) = (c3~
c ] ) = (::o:oo:::::1);
C(W4(Z7)) - (el, Cff, C4) --- (000111101101);
347
co,s(zT)) = (c~, c~, c~) = (~1~ ~00~ ~00~0);
c(att6(z 7)) = (c24, c2: , c26) = (110111111001);
c0,7(z7)) = (c~, c], c~) = (00~00~ ~ooooo);
,o, [oloo, o1,0
o oo
oo,o
I
l lolliol ! llill loo
r(c(/')) =
0010 0110 OOO3
C(Ko(Z7)). - (C ~ C l , C 2) = (01 I01 I011001)-
c ~ (zT)) = (c~, c~, c~) = (oxoooxloolxx);
C(K2(Z7))= (C0, CI , C22) = (111100100001);
C(K3(zT)) = (C~, C], C]) = (0111XXIi0011);
C(K4(ZTI) = (C~, C~, C~) = (00011110t 1011;
C(Ks(ZTI) = (C~, C~, C~)= (0011001001101,
C(K6(ZTI) : (C~, C~, C~) : (l10Xll11100X);
C(K7(Z7)) - (C5, C6, C~) - (1111 I0011001).
For k = n, the local codes of the "residual" functions from (29), (31), and (32) are obviously identical with the local
codes of the corresponding "residual" functions in the disjunctive-conjunctive decomposition of the PSBFf and its derivatives
f l , f2, and f3 in all the variables from X 1, XI 1, X12, and XI 3, respectively.
When we form the decompositions of SBF and PSBF, the "residual" functions are in the same class of Boolean
functionsl and they are also decomposable in a basis of monotone functions. Such multilevel decomposition often leads to
simpler analytical expressions for the original SBF and PSBF.
SYNTHESIS OF COMBINATIONAL NETWORKS IN A BASIS OF
MAJORITY-VOTING ELEMENTS
The proposed decomposition methods can be efficiently applied to synthesize a wide class of digital units and produce
a whole set of Pareto-optimal designs by varying the number and the dimension of the variable tuples used in decomposition.
A specific feature of the synthesis procedure is its reliance on the VLSI design library, which in addition to the
traditional logic elements (AND/NAND, OR/NOR), contains also complex logic elements, such as majority-voting elements
with even or odd thresholds (realizing monotone functions) and multi-input rood-2 adders (realizing linear fimctions).
The synthesis of combinational networks in a basis of majority-voting elements is demonstrated by the following
example.
348
Example 6. Let us synthesize an adder for five two-bit binary numbers that executes the operation
5
i=1
where X i = 2Xli + X2i, i = i, ~5; S = 8s 3 + 4s2 + ~l + So.
Form the local codes of the PSBF s r = sr(Y, Z), r = O, 3"
Y = (Xll, Xl 2, Xl 3, Xl 4, Xl 5), Z = (x21, x22, x23, x24, x25):
C(s3) = (0000000000000000, I001, * 1 , , , , 1 , , , 111 I);
C(s2) = (0000110011111111001 I000000001 I001111);
C(s, ) = (00110011001100110011001100110011001 I);
C(so) = (010101010101010101010101010101010101).
Construct the tables T(C(sr)) and use them to determine the local codes of the "residual" functions in decomposition
(29) in k = m I = 5 variables from Y.
In particular, for the function s 2
r
1
-i,.qoo.,.1,1_ .,.,.,loo,,
Hence,
C0t~o(Z)) = (000011);
CLqu
C0t~I(Z)) = (001100);
= C0tJ4(Z)) = (111111);
c(ws(z)) = c(ws(z)) = (oooooo).
Note that the functions ,I,j(Z) are symmetrical, j = 0 . . . . . 5, and therefore C(ffj(Z)) = a-(ffj(Z)).
Clearly, 't'2(Z) = 't'4(Z) -= 1; ~I,3(Z) = ~t'5(Z) = 0. Then
;2 = %(z) 9 w, (z) is(y) s M](Y) 9 Mr
Forming the decomposition (6) of the functions ~I,o(Z) and ~I(Z) in k = m2 = 5 variables from Z and transforming,
we obtain
We similarly obtain expressions for s o and s 1"
So = gs(z); ;~ = gs(n e M](Z) ~(Z).
349
We form the disjunctive decomposition of s3 by (23) in k = m i = 5 variables from Y and transform the result to
represent the decomposition coefficients and the "residual" functions in a basis of monotone functions"
The adder synthesized on the basis of these relationships is shown in Fig. 1.
The proposed SBF and PSBF decompositions are new analytical representations of these functions. Since they use
local codes of SBF and PSBF, instead of their truth tables, the decomposition can be obtained for variable vectors of arbitrary
dimension.
The application of the proposed decompositions makes it possible to synthesize digital units with low hardware
complexity and high speed. Note that such circuit-engineering solutions are generally unattainable or very difficult to attain
by traditional logic synthesis methods.
REFERENCES
O. V. Lupanov, "An approach to control system synthesis: the local coding principle," Probl. Kibern., Nauka,
.
3.
o
Moscow, No. 14, 31-100 (1965).
D. A. Pospelov, Logic Methods of Circuit Analysis and Synthesis [in Russian], Energiya, Moscow (1974).
L. B. Avgul' and V. P. Suprun, "Circuit synthesis for symmetric Boolean functions in a basis of linear and
monotone functions," Izv. Vuzov, Priborostroenie, 38, No. 11-12, 33-36 (1995).
V. P. Suprun, "Polynomial decomposition of symmetric Boolean functions,* Izv. Akad. Nauk SSSR, Tekhn.
Kibern., No. 4, 123-127 (1985).
350