Transcript Sum-of-Product representations

Logic Synthesis
Sum of Products
Courtesy RK Brayton (UCB)
and A Kuehlmann (Cadence)
1
Representation of Boolean Functions
• Sum of Products:
•
A function can be represented by a sum of cubes (products):
f = ab + ac + bc
Since each cube is a product of literals, this is a “sum of products”
(SOP) representation
•
A SOP can be thought of as a set of cubes F
F = {ab, ac, bc}
•
A set of cubes that represents f is called a cover of f.
F1={ab, ac, bc} and F2={abc,abc,abc,abc,bc}
are covers of
f = ab + ac + bc.
2
SOP
ac
bc
= onset minterm
ab
c
b
a
•
•
Note that each onset minterm is
“covered” by at least one of the
cubes!
None of the offset minterms is
covered
Covers (SOP’s) can efficiently represent many practical logic functions
(i.e. for many, there exist small covers).
Two-level minimization seeks the minimum size cover (least number of
cubes)
3
Irredundant Cubes
•
Let F = {c1, c2, …, ck} be a cover for f, i.e.
f = ik=1 ci
A cube ci F is irredundant if F\{ci}  f
Example: f = ab + ac + bc
ac
bc
bc
Not covered
ab
c
ac
b
F\{ab}  f
a
4
Prime Cubes
•
A literal j of cube ci  F ( =f ) is prime if
(F \ {ci })  {c’i }  f
where c’i is ci with literal j of ci deleted.
•
A cube of F is prime if all its literals are prime.
F=ac + bc + a =
F \{ci }  {c’i }
Example
f = ab + ac + bc
ci = ab; c’i = a (literal b deleted)
F \ {ci }  {c’i } = a + ac + bc
bc
a
c
ac
b
Not equal to f since
offset vertex is covered
a
5
Prime and Irredundant Covers
•
Definition 1 A cover is prime (irredundant) if all its cubes are prime
(irredundant).
•
Definition 2 A prime of f is essential (essential prime) if there is a
minterm (essential vertex) in that prime that is in no other prime.
•
Definition 3 Two cubes are orthogonal if they do not have any minterm
in common
– E.g.
c1= ab
c2 = bc are orthogonal
c1= ab
c2 = bc are not orthogonal
6
Prime and Irredundant Covers
Example
f = abc + bd + cd is prime and irredundant.
abc is essential since abcdabc, but not in bd or cd or ad
abc
bd
c
b
a
d
cd
Why is abcd not an essential vertex of abc?
What is an essential vertex of abc?
What other cube is essential? What prime is not essential?
7
PLA’s - Multiple Output Functions
•
A PLA is a function f : Bn  Bm represented in SOP form:
n=3, m=3
a
a
b
b
c
Personality Matrix
c
abc
10-11
0-0
111
00-
f1
f2
f1f2f3
1 - 1 - - 1 - 1 1
- - 1
f3
8
PLA’s (cont.)
•
Each distinct cube appears just once in the AND-plane, and can be
shared by (multiple) outputs in the OR-plane, e.g., cube (abc).
•
Extensions from single output to multiple output minimization theory are
straightforward.
•
Multi-level logic can be viewed mathematically as a connection of
single output functions.
9
Shannon (Boole) Cofactors
Let f : Bn  B be a Boolean function, and x= (x1, x2, …, xn) the
variables in the support of f.
The cofactor fa of f by a literal a=xi or a=xi is
fxi (x1, x2, …, xn) = f (x1, …, xi-1, 1, xi+1,…, xn)
fxi (x1, x2, …, xn) = f (x1, …, xi-1, 0, xi+1,…, xn)
The computation of the cofactor is a fundamental operation in Boolean
reasoning!!!!
Example:
f = abc + abc
fa = bc
c
c
b
a
b
a
10
Generalized Cofactor
•
The generalized cofactor fC of f by a cube C is f with the fixed values
indicated by the literals of C, e.g. if C=xi xj, then xi =1, and xj =0.
•
if C= x1 x4 x6
fC is just the function f restricted to the subspace
where x1 =x6 =1 and x4 =0.
•
As a function, fC does not depend on x1,x4 or x6 anymore
(However, we still consider fC as a function of all n variables, it just
happens to be independent of x1,x4 and x6).
•
x1f  fx1
Example: f= ac + ac , af = ac, fa=c
11
Fundamental Theorem
Theorem: Let c be a cube and f a function. Then c  f  fc  1.
Proof. We use the fact that xfx = xf, and fx is independent of x.
If : Suppose fc  1. Then cf=fcc=c. Thus, c  f.
f
c
12
Proof (cont.)
Only if. Assume c  f
Then c  cf = cfc. But fc is independent of literals i  c.
If fc 1, then  m  Bn, fc(m)=0.
We will construct a m’ from m and c in the following manner:
mi’=mi, if xic and xic,
mi’=1, if xi  c,
mi’=0, if xi  c.
i.e. we made the literals of m’ agree with c, i.e. m’  c c(m’)=1
Also, fc is independent of literals xi,xi  c fc(m’) = fc(m) = 0
fc(m’) c(m’)= 0
C=xz
contradicting c  cfc.
m= 000
m’= 101
m
m’
13
Cofactor of Covers
Definition: The cofactor of a cover F is the sum of the cofactors of each of
the cubes of F.
Note: If F={c1, c2,…, ck} is a cover of f, then Fc= {(c1)c, (c2)c,…, (ck)c} is a
cover of fc.
Suppose F(x) is a cover of f(x), i.e.
F ( x)   ci  
Then for 1jn,
i
i
i
j
 {ci }
j
F ( x) x j   (ci ) x j
is a cover of fxj(x)
i
14
Cofactor of Cubes
Definition: The cofactor Cxj of a cube C with respect to a literal xj is
• C if xj and xj do not appear in C
• C\{xj} if xj appears positively in C, i.e. xjC
•  if xj appears negatively in C, i.e. xjC
Example:
C = x1 x4 x6,
Cx2 = C
(x2 and x2 do not appear in C )
Cx1 = x4 x6 (x1 appears positively in C)
Cx4 = 
(x4 appears negatively in C)
15
Cofactor of Cubes (cont.)
Example
F = abc + bd + cd
Fb = ac + cd
(Just drop b everywhere and throw away cubes containing literal b)
16
Shannon Expansion
f : Bn  B
Shannon Expansion:
f  xi f xi  xi f xi
Theorem: F is a cover of f. Then
F  x i Fx i  x i Fx i
We say that f (F) is expanded about xi.
xi is called the splitting variable.
17
Shannon Expansion (cont.)
Example
F  ab  ac  bc
F  aFa  aFa  a(b  c  bc)  a(bc)
 ab  ac  abc  abc
ac
bc
ab
c
c
b
a
Cube bc got split into two cubes
b
a
18
List of Cubes (Cover Matrix)
We often use a matrix notation to represent a cover:
Example: F = ac + cd =
a b c d
ac 1 2 1 2
cd 2 2 0 1
•
•
•
•
or
a b c d
1 - 1 - - 0 1
Each row represents a cube
1 means that the positive literal appears in the cube
0 means that the negative literal appears in the cube
The 2 (or -) here represents that the variable does not appear in the
cube. It implicitly represents both 0 and 1 values.
19
Operations on Lists of Cubes
•
AND operation:
– take two lists of cubes
– computes pair-wise AND between individual cubes and put result on new
list
– represent cubes as pairs of computer words
– set operations are implemented as bit-vector operations
Algorithm AND(List_of_Cubes C1,List_of_Cubes C2) {
C = 
foreach c1 C1 {
foreach c2 C2 {
c = c1 c2
C = C  c
}
}
return C
}
20
Operations on Lists of Cubes
•
OR operation:
– take two lists of cubes
– computes union of both lists
•
Naive implementation:
Algorithm OR(List_of_Cubes C1, List_of_Cubes C2) {
return C1 C2
}
•
On-the-fly optimizations:
– remove cubes that are completely covered by other cubes
• complexity is O(m2); m is length of list
– conjoin adjacent cubes
– remove redundant cubes?
• complexity is O(2n); n is number of variables
• too expensive for non-orthogonal lists of cubes
21
Operations on Lists of Cubes
• Simple trick:
– keep cubes in lists orthogonal
– check for redundancy becomes O(m2)
– but lists become significantly larger (worst case: exponential)
Example:
01-0
01-0
0-11-01
OR
=
1-01
1-11
0010111
1-11
22
Operations on Lists of Cubes
•
Adding cubes to orthogonal list:
Algorithm ADD_CUBE(List_of_Cubes C, Cube c) {
if(C = ) return {c}
c’ = TOP(C)
Cres = c-c’
/* chopping off minterms */
foreach cres Cres {
C = ADD_CUBE(C\{c’},cres) {c’}
}
return C
}
•
•
How can the above procedure be further improved?
What about the AND operation, does it gain from orthogonal cube lists?
23
Operation on Lists of Cubes
• Naive implementation of COMPLEMENT operation
– apply De’Morgan’s law to SOP
– complement each cube and use AND operation
– Example:
Input
non-orth.
01-10 =>
1----0-----0----1
orthogonal
=> 1---00--01-001-11
• Naive implementation of TAUTOLOGY check
– complement function using the COMPLEMENT operator and check
for emptiness
• We will show that we can do better than that!!
24
A Possible Solution?
•
Let A be an orthogonal cover matrix. Let all cubes of A be pair-wise
distinguished by at least two literals (this can be achieved by an on-thefly resolution of cube pairs that are distinguished by only literal).
Does the following conjecture hold?
A  1  A has a row of all “-”s
?
This would dramatically simplify the tautology check!!!
25
Generic Tautology Check
Algorithm CHECK_TAUTOLOGY(List_of_Cubes C) {
if(C == )
return FALSE;
if(C == {-...-})return TRUE; // cube with all ‘-’
xi = SELECT_VARIABLE(C)
C0 = COFACTOR(C,^Xi)
if(CHECK_TAUTOLOGY(C0) == FALSE) {
print xi = 0
return FALSE;
}
C1 = COFACTOR(C,Xi)
if(CHECK_TAUTOLOGY(C1) == FALSE) {
print xi = 1
return FALSE;
}
return TRUE;
}
26
Improvements
•
Variable ordering:
– pick variable that minimizes the two sub-cases (“-”s get replicated
into both cases)
•
Quick decision at leaf:
– return TRUE if C contains at least one complete “-” cube among
others (case 1)
– return FALSE if number of minterms in onset is < 2n (case 2)
– return FALSE if C contains same literal in every cube (case 3)
27
Example
-1-0
--10
1-11
0---
^x1
x1
-1-0
--10
--11
^x2
x2
---0
--10
--11
^x3
--10
--11
---0
x3
---0
---1
-1-0
--10
----
x4
tautology(case 1)
No tautology(case 3)
No tautology(case 3)
---- tautology(case 1)
28
^x4
---- tautology(case 1)
Some Special Functions
Definition: A function f : Bn  B is symmetric with respect to variables xi
and xj iff
f(x1,…,xi,…,xj,…,xn) = f(x1,…,xj,…,xi,…,xn)
Definition: A function f : Bn  B is totally symmetric iff any permutation of
the variables in f does not change the function
Symmetry can be exploited in searching the binary decision tree
because:
f xi x j  f xi x j
- That means we can skip one of four sub-cases
- used in automatic variable ordering for BDDs
29
Some Special Functions
Definition: A function f : Bn  B is positive unate in variable xi iff
f xi  f xi
This is equivalent to monotone increasing in xi:
f (m  )  f (m  )
for all min-term pairs (m-, m+) where
m j  m j , j  i
mi  0
mi  1
For example, m-3=1001, m+3=1011(where i=3)
30
Some Special Functions
Similarly for negative unate
monotone decreasing:
f xi  f xi
f (m  )  f (m  )
A function is unate in xi if it is either positive unate or negative unate in xi.
Definition: A function is unate if it is unate in each variable.
Definition: A cover F is positive unate in xi iff xi  cj for all cubes cjF
31
Example
f  ab  bc  ac
m+
c
f(m-)=1  f(m+)=0
b
a
positive unate in a,b
negative unate in c
m-
32
The Unate Recursive Paradigm
•
Key pruning technique is based on exploiting the properties of unate
functions
– based on the fact that unate leaf cases can be solved efficiently
•
New case splitting heuristic
– splitting variable is chosen so that the functions at lower nodes of
the recursion tree become unate
33
The Unate Recursive Paradigm
Unate covers F have many extraordinary properties:
– If a cover F is minimal with respect to single-cube containment, all
of its cubes are essential primes.
– In this case F is the unique minimum cube representation of its
logic function.
– A unate cover represents the tautology iff it contains a cube with no
literals, i.e. a single tautologous cube.
This type of implicit enumeration applies to many sub-problems (prime
generation, reduction, complementation, etc.). Hence, we refer to it as
the Unate Recursive Paradigm.
34
Unate Recursive Paradigm
•
•
•
Create cofactoring tree stopping at unate covers
– choose, at each node, the “most binate” variable for splitting
– recure till no binate variable left (unate leaf)
“Operate” on the unate cover at each leaf to obtain the result for that leaf.
Return the result
At each non-leaf node, merge (appropriately) the results of the two
children.
a
b
•
•
c
merge
Main idea: “Operation” on unate leaf is computationally less complex
Operations: complement, simplify,tautology,generate-primes,...
35
The Binate Select Heuristic
Tautology and other programs based on the unate recursive paradigm use
a heuristic called BINATE_SELECT to choose the splitting variable in
recursive Shannon expansion. The idea is for a given cover F, choose
the variable which occurs, both positively and negatively, most often in
the cubes of F.
36
The Binate Select Heuristic
Example Unate and non-unate covers:
a b c d
G = ac+cd
1 - 1 - - 1 0
F = ac+cd+bcd
a
1
-
b
1
c
1
0
1
d
1
0
is unate
is not unate
=> Choose c for splitting!
•
•
The binate variables of a cover are those with both 1’s and 0’s in the
corresponding column.
In the unate recursive paradigm, the BINATE_SELECT heuristic
chooses a (most) binate variable for splitting, which is thus eliminated
from the sub-covers.
37
Example
f  ab  cd  bcd
c
1
1---1-0
unate
0
FC
FC
---1
unate
1 - 1 F= - - 0 1
- 1 1 0
f  abe  cd  bcde
c
1
1---0
-1-01
e
1
-1-0unate
0
---1unate
0
1 - 1 - 0
F= - - 0 1 - 1 1 0 1
1---unate
38
Two Useful Theorems
Theorem:
F  1  ( Fx j  1)  ( Fx j  1)
Theorem: Let A be a unate cover matrix.
Then A1 if and only if A has a row of all “-”s.
Proof:
If.
A row of all “-”s is the tautology cube.
Only if. Assume no row of all “-”s. Without loss of generality, suppose
function is positive unate. Then each row has at least one “1” in it.
Consider the point (0,0,…,0). This is not contained in any row of A.
Hence A1.
39
Unate Reduction
Let F(x) be a cover. Let (a,x’) be a partition of the variables x, and let
A
F 
T
X

F '
where
• the columns of A correspond to variables a of x
• T is a matrix of all “-”s.
Theorem: Assume A 1. Then F1  F’1
40
Example
A
F 
T
X

F '
1





1



0
1
1


1
0
1
0
1
1


1
0
1
We pick for the partitioning unate variables because it is easy to decide that A1
41
Unate Reduction
A1
0 1
1 0
B1
C2
      
C1
          
           1
D
A2
0
0
1
1
0
1
B2
Result: Only have to look at D1 to test if this is a tautology.
Note:
A1, A2 has no row of all “-”s.
Hence is a unate cover.
Hence (A1, A2)1
42
Proof
A
F 
T
X

F '
A1
T=“-”s
Theorem: Assume A 1. Then F1F’1
Proof:
if: Assume F’1. Then we can replace F’ by all -’s. Then last row of F
becomes a row of all “-”s, so tautology.
43
Proof (contd)
Only if:
Assume F’ 1. Then there is a minterm m2 such that F’(m2)=0, i.e.
m2cube of F’. Similarly, m1 exists where A(m1)=0, i.e. m1cube of A.
Now the minterm (m1,m2) in the full space satisfies F(m1,m2)=0 since
m1m2 AX and m1m2TF’.
(a, x’) is any row of first part
a(m1) ^ x’(m2)=0 ^ x’(m2)=0
(t,f’) is any row of the last part
t(m1) ^ f’(m2)=t(m1) ^ 0 = 0
So m1m2 is not in any cube of F.
44
Improved Tautology Check
Algorithm CHECK_TAUTOLOGY(List_of_Cubes C) {
if(C == )
return FALSE;
if(C == {-...-})return TRUE; // cube with all ‘-’
C = UNATE_REDUCTION(C)
xi = BINATE_SELECT(C)
C0 = COFACTOR(C,^xi)
if(CHECK_TAUTOLOGY(C0) == FALSE) {
return FALSE;
}
C1 = COFACTOR(C,xi)
if(CHECK_TAUTOLOGY(C1) == FALSE) {
return FALSE;
}
return TRUE;
}
45
Previous Example
-1-0
--10
1-11
0---
Unate reduction
0--No tautology(case 2)
^x1
x1
-1-0
--10
--11
^x2
x2
---0
--10
--11
^x3
--10
--11
---0
x3
---0
---1
-1-0
--10
----
x4
tautology(case 1)
No tautology(case 3)
No tautology(case 3)
---- tautology(case 1)
46
^x4
---- tautology(case 1)
Recursive Complement Operation
•
•
•
We have shown how tautology check (SAT check) can be implemented
recursively using the Binary Decision Tree
Similarly, we can implement Boolean operations recursively
Example COMPLEMENT operation:
Theorem:
Proof:
f  x  fx  x  fx
g  x  fx  x  fx
f  x  fx  x  fx
f  g  0
 g  f
f  g  1
47
COMPLEMENT Operation
Algorithm COMPLEMENT(List_of_Cubes C) {
if(C contains single cube c) {
Cres = complement_cube(c) // generate one cube per
return Cres
// literal l in c with ^l
}
else {
xi = SELECT_VARIABLE(C)
C0 = COMPLEMENT(COFACTOR(C,^xi)) ^xi
C1 = COMPLEMENT(COFACTOR(C,xi)) xi
return OR(C0,C1)
}
}
48
Complement of a Unate Cover
• Complement of a unate cover can be computed more efficiently
• Idea:
– variables appear only in one polarity on the original cover
(ab + bc + ac) = (a+b)(b+c)(a+c)
– when multiplied out, a number of products are redundant
aba + abc + aca + acc + bba + bbc + bca + bcc =
ab + ac + bc
– we just need to look at the combinations for which the variables
cover all original cubes
– this works independent of the polarity of the variables because of
symmetry to the (1,1,1,…,1) case
49
Complement on a Unate Cover
•
Map cube matrix F into Boolean matrix B
a


1
1
b
1

1

c

0

0
d
0
0


e

1
1
1
a
0
0
1
1
b
1
0
1
0
c
0
1
0
1
d
1
1
0
0
e
0
1
1
1
convert: “0”,”1” to “1” (literal is present)
“-” to “0”
(literal is not present)
50
Complement of a Unate Cover
Find all minimal column covers of B.
• A column cover is a set of columns J such that for each row i, jJ
such that Bij = 1
Example: {1,4} is a minimal column cover for
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
1
All rows “covered” by at least one 1.
51
Complement of a Unate Cover
•
For each minimal column cover create a cube with opposite column
literal from F.
Example: {1,4}
a


1
1
b
1

1

ad is a cube of f
c

0

0
d
0
0


e

1
1
1
a
0
0
1
1
b
1
0
1
0
c
0
1
0
1
d
1
1
0
0
e
0
1
1
1
52
Complement of a Unate Cover
The set of all minimal column covers = cover of f.
Example:
a


1
1
b
1

1

c

0

0
d
0
0


e

1
1
1
a
0
0
1
1
b
1
0
1
0
c
0
1
0
1
d
1
1
0
0
e
0
1
1
1
{(1,4), (2,3), (2,5), (4,5)} is the set of all minimal covers. This translates into:
f  ad  bc  be  de
53
Unate Complement Theorem
Theorem:
Let F be a unate cover of f. The set of cubes associated with the minimal
column covers of BF is a cube cover off.
Proof:
We first show that any such cube c generated is in the offset of f, by showing
that the cube c is orthogonal with any cube of F.
– Note, the literals of c are the complemented literals of F.
• Since F is a unate cover, the literals of F are just the union of the
literals of each cube of F).
– For each cube miF, jJ such that Bij=1.
• J is the column cover associated with c.
– Thus, (mi)j=xj cj= xj and (mi)j= xj  cj=xj. Thus mic = . Thus c  f .
54
Unate Complement Theorem
Proof (cont.):
We now show that any minterm mf is contained in some cube c
generated:
•
•
•
First m must be orthogonal to each cube of F.
– For each row of F, there is at least one literal of m that conflicts with
that row.
The union of all columns (literals) where this happens is a column cover
of BF
Hence this union contains at least one minimal cover and the
associated cube contains m.
55
Unate Covering Problem
Definition:
• The problem, given a Boolean matrix B, find a minimum column cover,
is called a unate covering problem.
• The unate complementation is one application that is based on the
unate covering problem.
Unate Covering Problem:
Given B, Bij{0,1} find x, xi{0,1} such that
Bx1 and j xj is minimum.
•
Sometimes we want to minimize
j cjxj
where cj is a cost associated with column j.
56
Incompletely Specified Functions
F = (f, d, r) : Bn  {0, 1, *}
where * represents “don’t care”.
•
•
•
f = onset function r = offset function d = don’t care function -
f(x)=1  F(x)=1
r(x)=1  F(x)=0
d(x)=1  F(x)=*
(f,d,r) forms a partition of Bn. i.e.
• f + d + r = Bn
• fd = fr = dr =  (pairwise disjoint)
57
Incompletely Specified Functions
A completely specified function g is a cover for F=(f,d,r) if
f g  f+d
(Thus gr = ). Thus, if xd (i.e. d(x)=1), then g(x) can be 0 or 1, but if xf,
then g(x)=1 and if xr, then g(x)=0.
(We “don’t care” which value g has at xd)
58
Primes of Incompl. Spec. Functions
Definition: A cube c is prime of F=(f,d,r) if cf+d (an implicant of f+d), and
no other implicant (of f+d) contains c, i.e.
c~, c~  f  d , c  c~
(i.e. it is simply a prime of f+d)
Definition: Cube cj of cover F={ci} is redundant if f F\{cj}.
Otherwise it is irredundant.
Note that cf+d  cr = 
59
Example:Logic Minimization
Consider F(a,b,c)=(f,d,r), where f={abc, abc, abc} and d ={abc, abc}, and
the sequence of covers illustrated below:
F1= abc + abc+ abc
Expand abca
on
off
Don’t care
F2= a+abc + abc
abc is redundant
a is prime
F3= a+abc
Expand abc  bc
F4= a+bc
60
Checking for Prime and Irredundant
Let G={ci} be a cover of F=(f,d,r). Let D be a cover for d.
• ciG is redundant iff
(1)
ci (G\{ci})D  Gi
(Since ci Gi and fGf+d then ci  cif+cid
and cif G\{ci}. Thus f G\{ci}.)
•
•
A literal l  ci is prime if (ci\{ l }) ( = (ci)l ) is not an implicant of F.
A cube ci is a prime of F iff all literals l  ci are prime.
(2)
Literal l  ci is not prime  (ci)l  f+d
Note: Both tests (1) and (2) can be checked by tautology:
•
•
(Gi)ci  1
(FD)(ci)l  1
(implies ci redundant)
(implies l not prime)
61