EE219BLogicSynthesis

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,EE219BLogic Synthesis,R. K. Brayton,University of California,Berkeley,Spring 2000,1,Introduction,Motivation,Commercial success - used almost everywhere VLSI is done,But more general ,Generally - discrete functions of discrete valued variables,Body of useful and general techniques,can be applied to other areas,2,Applications,Foundation,for,Combinational and sequential logic synthesis,Automatic test vector generation,Timing and false paths analysis,Formal verification,Asynchronous synthesis,Automata theory,Optimal clocking schemes,Hazard analysis,Power estimation,General combinatorial problems,3,Outline of Class,Class notes: (see class web page),Introduction,Logic functions and their representation,Unate recursive paradigm,Two Level logic minimization (ESPRESSO),Quine McCluskey method,Midterm,Multi-level logic synthesis,Introduction (Boolean networks, factored forms),Division,Simplification,Full_simplify,Testing,Technology mapping,Advanced technology mapping,4,Outline of Class,Multi-level logic synthesis (contd.),Delay analysis (true and false paths),Timing optimization,Constant delay paradigm (sizing),midterm,Sequential logic synthesis,Introduction (FSM networks),Retiming and resynthesis,Asynchronous synthesis,Node minimization?,* State minimization *,Final project presentations and report,5,The Boolean n-cube B,n,B = 0,1,B,2,= 0,1 X 0,1 = 00, 01, 10, 11,B,0,B,1,B,2,B,3,B,4,6,Boolean Functions,f,(x) : B,n,B,B = 0, 1, x = (x,1, x,2, , x,n,),x,1, x,2, are,variables,x,1, x,1, x,2, x,2, are,literals,each vertex of B,n,is mapped to 0 or 1,the,onset,of,f,is,x|,f,(x)=1 =,f,1,=,f,-1,(1),the,offset,of,f,is,x|,f,(x)=0 =,f,0,=,f,-1,(0),if,f,1,= B,n,f,is the,tautology, i.e.,f, 1,if,f,0,= B,n,(,f,1,=,),f,is,not satisfiable,if f(x) = g(x) for all x,B,n, then f and g are,equivalent,We write simply,f,instead of,f,1,7,Literals,A literal is a variable or its negation,y, y,It represents a,logic function,Literal x,1,represents the logic function f, where,f,= x| x,1,= 1,f = x,1,f = x,1,x,1,x,1,Literal x,1,represents logic function g where,g,= x| x,1,= 0,8,Boolean Formulas,Boolean formulas,can be represented by formulas defined as catenations of,parentheses ( , ),literals x, y, z, x, y, z,Boolean operators,(OR),X,(AND),complementation, e.g. x + y,Examples,f = x,1,X,x,2,+ x,1,X,x,2,= (x,1,+x,2,),X,(x,1,+x,2,),h = a + b X c = a,X,(b + c),We usually replace,X,by catenation, e.g. a,X,b,ab,9,Logic functions,There are 2,n,vertices in input space B,n,There are 2,2,n,distinct logic,functions,.,Each subset of vertices is a distinct logic function:,f,B,n,111,000,x,3,x,1,x,2,000,1,001,0,010,1,011,0,100,1,101,0,110,1,111,0,“truth table”,10,Logic Functions,However, there are infinite number of logic,formulas,f = x + y,= xy + xy + xy,= xx + xy + y,= (x + y)(x + y) + xy,Synthesis = Find the best formula (or “representation”),11,Boolean Operations - AND, OR, COMPLEMENT,f : B,n,B,g : B,n,B,AND - fg = h such that,h = x| f(x)=1 and g(x)=1,OR - f + g = h such that,h = x| f(x)=1 or g(x)=1,COMPLEMENT - f = h such that,h = x| f(x) = 0,12,Cubes,The AND of a set of literal functions (“conjunction” of literals) is a,cube,C = xy,is a cube,C = (x=1)(y=0),x =1,y =0,xy,z,y,x,13,Cubes,If C, f, C a cube, then C is an,implicant,of f.,If C, B,n, and C has k literals, then |,C,| has,2,n-k,vertices.,Example 1,C = x y B,3,.,k = 2 , n = 3.,C,= 100, 101.,|,C,| = 2 = 2,3-2.,If k=n, the cube is a,minterm.,14,Representation of Boolean functions,The truth table of a function f : B,n,B is a tabulation of its value at each of the 2,n,vertices of B,n,.,For,f = abcd + abcd + abcd + abcd + abcd + abcd + abcd + abcd,the truth table is,This is intractable for large n,(but,canonical,),Canonical means that if two functions are the same, then the canonical representations of each are isomorphic.,abcd f,0 0000 0,1 0001 1,2 0010 0,3 0011 1,4 0100 0,5 0101 1,6 0110 0,7 0111 0,abcd f,8 1000 0,9 1001 1,10 1010 0,11 1011 1,12 1100 0,13 1101 1,14 1110 1,15 1111 1,15,Sum-of-Products Representation - SOP,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” representation,A SOP can be thought of as a set of cubes F,F = ab, ac, bc = C,A set of cubes that represents f is called a,cover,of f. F=ab, ac, bc is a cover of f = ab + ac + bc.,16,SOP,Covers (SOPs) can efficiently represent many logic functions (i.e. for many, there exist small covers).,Two-level minimization seeks the minimum size cover (least number of cubes),bc,ac,ab,c,a,b,= onset minterm,Note that each onset,minterm is “covered”,by at least one,of the cubes, and,covers no offset minterm,.,17,Irredundant,Let F = c,1, c,2, , c,k, be a cover for f.,f =,i,k,=1,c,i,A cube c,i, F is,irredundant,if F,c,i, f,Example 2:,f = ab + ac + bc,bc,ac,ab,c,a,b,bc,ac,Not covered,Fab, f,18,Prime,A,literal,j,of cube,c,i,F,( =,f,),is,prime,if,(,F,c,i,),c,i,f,where,c,i,is,c,i,with literal,j,of,c,i,deleted.,A,cube,of F is prime if all its literals are,prime,.,Example 3,f = ab + ac + bc,c,i,= ab; c,i,= a (literal b deleted),F c,i, ,c,i, = a + ac + bc,bc,ac,a,c,a,b,Not equal to f since,offset vertex is covered,F=ac + bc + a =,F c,i, ,c,i,19,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 but in no other prime.,20,Prime and Irredundant Covers,Example 4,f = abc + bd + cd is prime and irredundant.,abc is,essential,since abcd,abc, but not in bd or cd or ad,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?,abc,bd,cd,d,a,c,b,21,PLAs - Multiple Output Boolean Functions,A PLA is a function f : B,n,B,m,represented in SOP form:,a,a,a,a,a,b,c,d,b,b,b,b,c,c,c,c,d,d,d,d,f2,f3,f1,n=4, m=3,22,PLAs (contd),Each distinct cube appears just once in the AND-plane, and can be shared by (multiple) outputs in the OR-plane, e.g., cube abcd.,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.,23,Shannon (Boole) cofactors,Let,f : B,n,B be a Boolean function, and x=,(x,1, x,2, , x,n,) the variables in the support of f. The cofactor f,a,of f by a literal a=x,i,or a=x,i,is,f,x,i,(x,1, x,2, , x,n,) = f (x,1, , x,i-1, 1, x,i+1, x,n,),f,x,i,(x,1, x,2, , x,n,) = f (x,1, , x,i-1, 0, x,i+1, x,n,),24,Shannon (Boole) Cofactor,The,cofactor,f,C,of f by a,cube,C is just f with the fixed values indicated by the literals of C, e.g. if C=x,i,x,j, then x,i,=1, and x,j,=0.,If C= x,1,x,4,x,6, f,C,is just the function f restricted to the subspace where x,1,=x,6,=1 and x,4,=0.,As a function, f,C,does not depend on x,1,x,4,or x,6,(However, we still consider f,C,as a function of all,n,variables, it just happens to be independent of x,1,x,4,and x,6,).,x,1,f, f,x,1,Example:,f= ac + a c, af = ac, f,a,=c,25,Fundamental Theorem,Theorem 1,Let c be a cube and f a function. Then c, f f,c, 1.,Proof,. We use the fact that xf,x,= xf, and f,x,is independent of x.,If:,Suppose f,c, 1. Then cf=f,c,c=c. Thus,c, f.,f,c,26,Proof (contd),Only if.,Assume c, f,Then c, cf = cf,c,. But f,c,is independent of literals l c. If f,c,1, then m B,n, f,c,(m)=0.,Let m,i,=m,i, if x,i,c and x,i,c.,or if m,i,=0, x,i, c,or m,i,=1, x,i, c.,m,i,=m,i,otherwise.,i.e. we make the literals of m agree with c, i.e. m c. But then f,c,(m) =,f,c,(m) = 0,Hence, c(m)=1,and f,c,(m) c(m)= 0,contradicting,c, cf,c,.,m= 000,m= 101,m,m,C=xz,27,End of Lecture 1,28,Cofactor of Covers,Definition 3,The,cofactor of a cover,F is the sum of the cofactors of each of the cubes of F.,Note:,If F=c,1, c,2, c,k, is a cover of f, then F,c,= (c,1,),c, (c,2,),c, (c,k,),c, is a cover of f,c,.,Suppose F(x) is a cover of f(x), i.e.,Then for 1,jn,is a cover of f,x,j,(x),29,Definition 4,The cofactor C,x,j,of a cube C,with respect to a literal x,j,is,C if x,j,and x,j,do not appear in C,Cx,j, if x,j,appears positively in C, i.e. x,j,C,if x,j,appears negatively in C, i.e. x,j,C,Example 5,If C = x,1,x,4,x,6,C,x,2,= C (x,2,and x,2,do not appear in C ),C,x,1,= x,4,x,6,(x,1,appears positively in C),C,x,4,=, (,x,4,appears negatively in C),30,Example 6,F = abc + bd + cd,F,b,= ac + cd,(Just drop b everywhere and throw away cubes containing literal,b),31,Shannon Expansion,f : B,n,B,Theorem 2,Theorem 3,F is a cover of f. Then,We say that f (F) is,expanded about,x,i,. x,i,is called the,splitting variable,.,32,Example 7,=,Cube,bc,got split into two cubes,c,a,b,c,a,b,bc,33,Cover Matrix,We sometimes use matrix notation to represent a cover:,Example 8,F = ac +,cd =,a b c da b c d,ac, 1 2 1 2 or 1 - 1 -,cd 2 2 0 1 - - 0 1,Each row represents a cube. 1 means that the positive literal appears in the cube, 0 the negative. The 2 (or -) here represents that the variable does,not appear,in the cube. It also represents both 0 and 1 values.,34,Example 9,a,c = 1 2 0 2 = 1, 0,1, 0, 0,1,= 1000, 1100, 1001, 1101,2 is sometimes called “input dont care”, but this is confusing so we wont use the term.,35,Incompletely Specified Functions,F,= (f, d, r) : B,n,0, 1, *,where * represents “dont care”. (Sometimes we use 2 in place of *),f = onset function - f(x)=1,F,(x)=1,r = offset function - r(x)=1,F,(x)=0,d = dont care function - d(x)=1,F,(x)=*,(f,d,r) forms a,partition,of B,n,. i.e.,f + d + r = B,n,fd =,fr = dr =, (pairwise disjoint),36,A completely specified function g is a,cover,for,F,=(f,d,r) if,f, g f+d,(,Thus gr = ,). Thus, if xd (i.e. d(x)=1), then g(x) can be 0 or 1, but if xf, then g(x)=1 and if xr, then g(x)=0.,(We “dont care” which value g has at xd),37,Primes of Incompletely Specified Functions,Definition 5,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.,(i.e. it is simply a prime of f+d),Definition 6,Cube c,j,of cover F=c,i, is,redundant,if f Fc,j,. Otherwise it is,irredundant,.,Note,that cf+d cr = ,38,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:,F,1,=,abc + abc+ abc,abc is redundant,a is prime,F,3,= a+,abc,Expand,abc,bc,Expand abc,a,F,2,= a+,abc + abc,F,4,= a,+bc,off,on,Dont care,39,Checking for Prime and Irredundant,Let G=c,i, be a cover of,F,=(f,d,r). Let D be a cover for d.,c,i,G is,redundant,iff,c,i,(G,c,i,)D G,i,(1),(Since,c,i, G,i,and fGf+d then,c,i,c,i,f+,c,i,d,and,c,i,f G,c,i,. Thus f G,c,i,.),A literal l ,c,i,is,prime,if (,c,i, l ),( = (,c,i,),l,),is not an implicant of,F,.,A cube,c,i,is a prime of,F,iff all literals l ,c,i,are prime.,Literal l ,c,i,is not prime (,c,i,),l, f+d,(2),40,Note:,Both tests,(1),and,(2),can be checked by,tautology,:,(,G,i,),c,i, 1 (implies c,i,redundant),(FD),(,c,i,),l, 1 (implies l not prime),41,Example,F=,abc, abc, abc,D=ac,R=ab,ac,Expand abc ab= (c,i,),l,= (abc),c,Check ab f+d (f+d),ab,= 1,(f+d),ab,= c +c 1,OK,Expand ab, a. Check a f+d,(f+d),a,= bc + bc +c 1,OK,F= a + abc + abc,Check if abc is redundant,abc a+ abc + ac = Fabc D,(a+ abc + ac ),abc,= 1,OK,42,Cover is now F = a +,abc,and D =,ac,Check if,abc is redundant,abc a+ ac = Fabc D,(a+ ac ),abc,=,NOT REDUNDANT,43,