Binary Recursion Tree.ppt

1、1,Binary Recursion Tree,The recursive Shannon expansion corresponds to a binary recursion treeExample:Path (v) to node v corresponds to cube c(v) Example: c(v) = x1 x2 x3,1,0,1,1,0,0,x1,x3,x2,1,1,1,0,0,0,x,y,y,v,(v),2,Binary Recursion Tree,The root represents the original function f. Each node v cor

2、responds to fc(v). If ever fc(v) = 1 or 0 we can terminate the tree and replace v by 1 or 0. Such a node v is a leaf.,3,Example,1,1,1,0,0,0,1,a,b,b,0,1,0,1,0,c,c,Splitting variable,4,Implicit Enumeration - Branch and Bound,Checking for tautology and many other theoretically intractable problems (co-

3、NP complete) can be effectively solved using implicit enumeration: use recursive Shannon expansion to explore Bn. In (hopefully) large subspaces of Bn, prune the binary recursion tree by exploiting properties of the node function fc(v) exploiting heuristic bounding techniques even though in the wors

4、t case the recursion tree may have 2n nodes, in practice (in many cases), we typically encounter a linear number of nodes,5,Implicit Enumeration - Branch and Bound,Thus we say that the 2n min-terms of f have been implicitly enumerated BDDs (Binary Decision Diagrams) are alternate representations in

5、which implicit enumeration is performed statically, and nodes with identical path cofactors are identified(very important - will discuss later!),6,Example,Not a tautology. In testing for tautology, we look for a cube subspace c such that fc=0. If we can find it then f is not the tautology.,1,1,1,0,0

6、,0,1,a,b,b,0,1,0,1,0,c,c,fab,7,Can rule out complete cube subspace c if fc=1Tautology can be proved by finding ci such that ci = 1 and fci 1 for all ci. We dont need that ci cj =.,C ,Means that f, in the subspace c = ac, is identically 1,8,Definition 1 A function f : Bn B is positive unate in variab

7、le xi iffThis is equivalent to monotone increasing in xi:for all min-term pairs (m-, m+) whereFor example, m-3=1001, m+3=1011(where i=3),9,Similarly for negative unate monotone decreasing:A function is unate in xi if it is either positive unate or negative unate in xi.Definition 2 A function is unat

8、e if it is unate in each variable. Definition 3 A cover f is positive unate in xi iff xi cj for all cubes cjF,10,Example 1,c,b,a,c,b,a,m+,m-,f(m-)=1 f(m+)=0,positive unate in a,b negative unate in c,11,The Unate Recursive Paradigm,In the EXPRESSO program, the key pruning technique is based on exploi

9、ting the properties of unate functions. In particular, the splitting variable is chosen so that the functions at lower nodes of the recursion tree become unate.,12,Unate covers F have many extraordinary properties: If a cover F is minimal with respect to single-cube containment, all of its cubes are

10、 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,

11、 complementation, etc.). Hence, we refer to it as the Unate Recursive Paradigm.,13,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 gi

12、ven cover F, choose the variable which occurs, both positively and negatively, most often in the cubes of F.,14,The Binate Select Heuristic,Example 2 Unate and non-unate covers:a b c dG = ac+cd 1 2 1 22 2 1 0a b c dF = ac+cd+bcd 1 2 1 22 2 0 12 1 1 0 Choose c for splitting. The binate variables of a

13、 cover are those with both 1s and 0s 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.,is unate,is not unate,15,Examples,1,1,1,0,0,2221 unate,22212 unate,21202 unate,

14、1222 2120 unate,12222 unate,12220 21201,1 2 1 2 0 F= 2 2 0 1 22 1 1 0 1,1 2 1 2 F=2 2 0 12 1 1 0,e,c,c,FC,FC,16,Tautology,Is F = 1? NOT EASY!1211211101200200F= 2201 = 1?12021220201000210012,17,Two Useful Theorems,Theorem 1Theorem 2 Let A be a unate cover matrix. Then A1 if and only if A has a row of

15、 all 2s. Proof: If. A row of all 2s is the tautology cube. Only if. Assume no row of all 2s. 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 A1.,18,Unate Reduction of Ta

16、utology Checking,Let F(x) be a cover. Let (a,x) be a partition of the variables x, and letwhere the columns of A correspond to variables a of x T is a matrix of all 2s.Theorem 3 Assume A 1. Then F1 F1,19,Example 3=,20,A1,C2,D1,B2,C1,B1,A2,Unate Reduction,Result: Only have to look at D1 to test if th

17、is is a tautology. Note: A1, A2 has no row of all 2s. Hence is a unate cover. Hence (A1, A2)1,21,End of Lecture 2,22,Proof,Theorem 1 Assume A 1. Then F1F1 Proof: if: Assume F1. Then we can replace F by all 2s. Then last row of F becomes a row of all 2s, so tautology.,A1 T=2s,23,Proof (contd),Only if

18、: Assume F 1. Then there is a minterm m2 such that F(m2)=0, i.e. m2cube of F. Similarly, m1 exists where A(m1)=0, i.e. m1cube of A. Now the minterm (m1,m2) in the full space satisfies F(m1,m2)=0 since m1m2 AX and m1m2TF. (a, x) is any row of first parta(m1) x(m2)=0 x(m2)=0 (t,f) is any row of the la

19、st part t(m1) f(m2)=t(m1) 0 = 0 So m1m2 is not in any cube of F.,24,Unate Reduction for Tautology,Procedure TAUTOLOGY(F, C) / C is a cube returned if F 1. Then C / contains a minterm m where F(m)=0T SPECIAL_CASES(F)if (T -1) return TF UNATE_REDUCTION(F)if (F=) print C; return 0;j BINATE_SELECT(F)T T

20、AUTOLOGY(Fxj , C xj if(T=0) print (C xj ), return 0T TAUTOLOGY(Fxj , C xj if(T=0) print (C xj ), return 0return 1end,25,Unate Reduction for Tautology,Notes. T=1(0) if F is a tautology (is empty), else T=-1SPECIAL_CASES: (T=-1 unless) T=1 : F contains a cube with no literals (all 2s) T=0 : F contains

21、 same literal in every cube T=0 if number of minterms in onset is 2n,26,x1,x1,x2,x2,x3,x4,x4,x3,Unate reduction,No tautology(case 2),No tautology(case 2),No tautology(case 2),tautology(case 1),tautology(case 1),tautology(case 1),27,Unate Recursive Paradigm,Create cofactoring tree stopping at unate c

22、overs choose, at each node, the “most binate” variable for splitting recurse 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.Main Ide

23、a “Operation” on unate leaf is easy Operations: complement, simplify,tautology,generate-primes,.,merge,28,Operations on a Unate Cover: Complement,Map cube matrix M into Boolean matrix Ba b c d e= BThus non-2 12 0,29,Complement of a Unate Cover,Find all minimal column covers of B. (A column cover is

24、a set of columns J such that for each row i, jJ such that Bij = 1)Example 4 1,4 is a minimal column cover forAll rows “covered” by at least one 1.,30,Complement of a Unate Cover,For each minimal column cover create a cube with opposite column literal from M.Example 5 1,4 ad is a cube of f,31,Complem

25、ent of a Unate Cover,The set of all minimal column covers = cover of f.Example 6(1,4), (2,3), (2,5), (4,5) is the set of all minimal covers. This translates into:,32,Unate Complement Theorem,Theorem 4 Let M be a unate cover of f. The set of cubes associated with the minimal column covers of BM is a

26、cube cover off.Proof. We first show that any such cube c generated is in the offset of f, by showing that the cube c is orthogonal (has empty intersection) with any cube of M. Note, the literals of c are the complemented literals of M. (Since M is a unate cover, the literals of M are just the union

27、of the literals of each cube of M). For each cube miM, jJ 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 .,33,We now show that any minterm f is contained in some cube c generated. First must be orthogonal to each cube of M

28、. So for each row of M, there is at least one literal of that conflicts with that row. The union of all columns (literals) where this happens is a column cover of BM; hence this union contains at least one minimal cover and the associated cube contains .,34,Complement of a Unate Cover,The set of all

29、 minimal column covers = cover of f. Example 6M=(1,4), (2,3), (2,5), (4,5) is the set of all minimal covers. This translates into:f =ad +bc +be +de A minimal column cover is (1,4) ad ad f =bd +cd + abe +ac e,BM,35,Consider min-term abcde f . It conflicts in literals a,c,d,e . Thus 1,3,4,5 is a colum

30、n cover. It contains 1,4 and 4,5. Thus abcde ad de,36,Unate Covering,Definition 4 The problem, given a Boolean matrix B, find a minimum column cover, is called a unate covering problem. The problem of unate complementation was our first example of the unate covering problem and we will see it often

31、in this course. Unate Covering Problem:Given B, Bij0,1 find x, xi0,1 such that Bx1and j xj is minimum. Sometimes we want to minimize j cjxjwhere cj is a cost associated with column j.,37,Quine-McCluskey Procedure (Exact),Given G and D (covers for F = (f,d,r) and d), find a minimum cover G of primes

32、where: f G f+d (G is a prime cover of F ) Q-M Procedure 1. Generate all the primes of F , Pj (i.e. primes of (f+d)=G+D) 2. Generate all the minterms of f=GD, mi 3. Build Boolean matrix B where Bij = 1 if mi Pj= 0 otherwise 4. Solve the minimum column covering problem for B (unate covering problem),3

33、8,Difficulty,Note: Can be 2n minterms 3n/n primesThus O(2n) rows and O(3n/n ) columns AND minimum covering problem is NP-complete. (Hence can probably be double exponential in size of input, i.e. difficulty is O(23n),0,1,0,0,1,0,3n/n,minterms,primes,2n,39,Example 8Primes: y + w + xz Covering Table S

34、olution: 1,2 y + w is minimum prime cover. (also w+ xz),xy,xy,xy,xy,zw,zw,zw,zw,xz,y,w,Karnaugh map,40,Covering Table,Definition 5 An essential prime is any prime that uniquely covers a minterm of f.,Primes of f+d,Minterms of f,Essential prime,Row singleton (essential minterm),41,Covering Table,Row

35、Equality: In practice, many rows are identical. That is there exist minterms that are contained in the same set of primes.m1 0101101m2 0101101 Any row can be associated with a cube - called the signature cube.e.g. m1 m2 P2P4P5P7,42,Row and Column Dominance,Definition 6 A row i1 whose set of primes i

36、s contained in the set of primes of row i2 is said to dominate i2.Example 9i1 011010i2 011110i1 dominates i2We can remove row i2 , because we have to choose a prime to cover i1, and any such prime also covers i2. So i2 is automatically covered.,43,Row and Column Dominance,Definition 7 A column j1 wh

37、ose rows are a superset of another column j2 is said to dominate j2.Example 10j1 dominates j2We can remove column j2 since j1 covers all those rows and more. We would never choose j2 in a minimum cover since it can always be replaced by j1.,j1 j2 1 0 0 0 1 1 0 0 1 1,44,Pruning the Covering Table,1.

38、Remove all rows covered by essential primes (columns in row singletons). Put these primes in the cover G. 2. Group identical rows together and remove dominated rows. 3. Remove dominated columns. For equal columns, keep one prime to represent them. 4. Newly formed row singletons define n-ary essentia

39、l primes. 5. Go to 1 if covering table decreased. The resulting reduced covering table is called the cyclic core. This has to be solved (unate covering problem). A minimum solution is added to G - the set of n-ary essential primes. The resulting G is a minimum cover.,45,Example,n-ary Essential Prime

40、 and Column Dominance G=P1 + P3,Essential Prime and Column Dominance G=P1,Row dominance,Cyclic Core,46,Solving the Cyclic Core,Best known method (for unate covering) is branch and bound with some clever bounding heuristics. Independent Set Heuristic: Find a maximum set of “independent” rows I. Two r

41、ows Bi1 ,Bi2 are independent if j such that Bi1j =Bi1j=1. (They have no column in common) Example 11 Covering matrix B rearranged with independent sets first.,Independent set = I of rows,B=,47,Lemma 1 |Solution of Covering| |I|,48,Heuristic,Let I=I1, I2, , Ik be the independent set of rows choose j

42、Ii which covers the most rows of A. Put j J eliminate all rows covered by column j I IIi go to 1 if |I| 0 If B is empty, then done (in this case we have the guaranteed minimum solution - IMPORTANT) If B is not empty, choose an independent set of B and go to 1Can you think of some improved heuristics

43、?,49,Generating Primes,We use the unate recursive paradigm. The following is how the merge step is done. (Assumption: we have just generated all primes of and .)Theorem 5 p is a prime of f iff p is maximal among the set consisting of P = xiq, q is a prime of , P = xir, r is a prime of , P = qr, q is

44、 a prime of , r is a prime of,50,End of lecture 3,51,Generating Primes,Example 12 Assume q = abc is a prime of . Form p=xiabc. Suppose r=ab is a prime of . Then is an implicant of fThus abc and xiab are implicants, so xiabc is not prime. Note: abc is prime because if not, ab fx (or ac or bc) contrad

45、icting abc prime of Note: xiab is prime, since if not then either ab f or xia f . The first contradicts abc prime of and the second contradicts ab prime of,52,New Exact Methods,For 40 years, Q-M method remained basically unchanged. In 1992, two fundamentally new methods developed: McGeers Method (Mc

46、Geer, Sanghavi, et al) generate all essential signature cubes (ESC) (if c is a cube, ( c ) is the intersection of all primes containing c; an essential signature cube is a maximal cube of (mi) where mi is a minterm of the onset.) generate only those primes that contain an essential signature cube (E

47、SP) form covering tables ESC vs ESP and solve. (This initial covering table is like the original with a single step of row and column dominance)Note: Covering table is smaller, of size|ESC| x |ESP|,53,New Exact Methods,Implicit Q-M based on BDDs (Coudert and Madre, McGeer, Swamy, Brayton) form chara

48、cteristic BDD of all primes form characteristic BDD of all minterms of f (F=(f,d,r) formulate row dominance and column dominance elimination as BDD operations iterate dominance and prime/minterm elimination until no further decrease generate covering table (cyclic core at this point) and solve,54,New Exact Methods,GREAT RESULTS! In both cases, superior to ESPRESSO-EXACT (both in speed and in number of problems solved)ESPRESSO has a suite of about 130 examples, of which ESPRESSO-EXACT can solve about 110. The others solve almost all of the 130.,