Презентация Two-Level Logic Minimization Algorithms. Lecture 3 онлайн

Содержание слайда: Lecture 3 Two-Level Logic Minimization Algorithms Hai Zhou ECE 303 Advanced Digital Design Spring 2002

Содержание слайда: Outline CAD Tools for 2-level minimization Quine-McCluskey Method ESPRESSO Algorithm READING: Katz 2.4.1, 2.4.2, Dewey 4.5

Содержание слайда: Two-Level Simplification Approaches

Содержание слайда: Review of Karnaugh Map Method

Содержание слайда: Example of Karnaugh Map Method

Содержание слайда: Quine-McCluskey Method

Содержание слайда: Quine-McCluskey Method

Содержание слайда: Quine Mcluskey Method

Содержание слайда: Quine McCluskey Method (Contd)

Содержание слайда: Quine-McCluskey Method (Contd)

Содержание слайда: Finding the Minimum Cover We have so far found all the prime implicants The second step of the Q-M procedure is to find the smallest set of prime implicants to cover the complete on-set of the function This is accomplished through the prime implicant chart Columns are labeled with the minterm indices of the onset Rows are labeled with the minterms covered by a given prime implicant Example a prime implicant (-1-1) becomes minterms 0101, 0111, 1101, 1111, which are indices of minterms m5, m7, m13, m15

Содержание слайда: Prime Implicant Chart

Содержание слайда: Prime Implicant Chart

Содержание слайда: Prime Implicant Chart (Contd)

Содержание слайда: Prime Implicant Chart (Contd)

Содержание слайда: Second Example of Q-M Method

Содержание слайда: Second Example (Contd)

Содержание слайда: Prime Implicant Chart for Second Example

Содержание слайда: Essential Primes for Example

Содержание слайда: Delete Columns Covered by Essential Primes

Содержание слайда: Resultant Minimum Cover

Содержание слайда: ESPRESSO Method

Содержание слайда: Boolean Space The notion of redundancy can be formulated in Boolean space Every point in a Boolean space corresponds to an assignment of values (0 or 1) to variables. The on-set of a Boolean function is set of points (shown in black) where function is 1 (similarly for off-set and don’t--care set)

Содержание слайда: Boolean Space If g and h are two Boolean functions such that on-set of g is a subset of on-set of h, then we write g C h Example g = x1 x2 x3 and h = x1 x2 In general if f = p1 + p2 + ….pn, check if pi C p1 + p2 + …p I-1 + pn

Содержание слайда: Redundancy in Boolean Space x1 x2 is said to cover x1 x2 x3 Thus redundancy can be identified by looking for inclusion or covering in the Boolean space While redundancy is easy to observe by looking at the product terms, it is not always the case If f = x2 x3 + x1 x2 + x1 x3, then x1 x2 is redundant Situation is more complicated with multiple output functions f1 = p11 + p12 + … + p1n f2 = …. Fm = pm1 + pm2 + … p mn

Содержание слайда: Minimizing Two Level Functions Sometimes just finding an irredundant cover may not give minimal solution Example: Fi = b c + a c + a bc (no cube is redundant) Can perform a reduction operation on some cubes Fi = a b c + a c + a bc (add a literal a to b c ) Now perform an expansion of some cubes Fi = a b + a c + a bc(remove literal c from a b c ) Now perform irredundant cover Fi = a b + a c (remove a b c ) At each step need to make sure that function remains same, I.e. Boolean equivalence

Содержание слайда: Espresso Algorithm

Содержание слайда: Details of ESPRESSO Algorithm Procedure ESPRESSO ( F, D, R) /* F is ON set, D is don’t care, R OFF * R = COMPLEMENT(F+D); /* Compute complement */ F = EXPAND(F, R) ; /* Initial expansion */ F = IRREDUNDANT(F,D); /* Initial irredundant cover */ F = ESSENTIAL(F,D) /* Detecting essential primes */ F = F - E; /* Remove essential primes from F */ D = D + E; /* Add essential primes to D */ WHILE Cost(F) keeps decreasing DO F = REDUCE(F,D); /* Perform reduction, heuristic which cubes */ F = EXPAND(F,R); /* Perform expansion, heuristic which cubes */ F = IRREDUNDANT(F,D); /* Perform irredundant cover */ ENDWHILE; F = F + E; RETURN F; END Procedure;

Содержание слайда: Need for Iterations in ESPRESSO

Содержание слайда: ESPRESSO Example

Содержание слайда: Example of ESPRESSO Input/Output

Содержание слайда: Two-Level Logic Design Approach

Содержание слайда: SOP and POS Two-Level Logic Forms We have looked at two-level logic expressions Sum of products form F = a b c + b c d + a b d + a c This lists the ON sets of the functions, minterms that have the value 1 Product of sums form (another equivalent form) F = ( a + b + c ) . ( b + c + d ) . ( a + b + d ) . ( a + c) This lists the OFF sets of the functions, maxterms that have the value 0 Relationship between forms minimal POS form of F = minimal SOP form of F minimal SOP form of F = minimal POS form of F

Содержание слайда: SOP and POS Forms

Содержание слайда: Product of Sums Minimization For a given function shown as a K-map, in an SOP realization one groups the 1s Example: For the same function in a K-map, in a POS realization one groups the 0s Example: F(A,B,C,D) = (C.D) + (A.B.D) + (A.B.C) With De Morgan’s theorem F = (C + D) . (A + B + D) . (A + B + C) Can generalize Quine McCluskey and ESPRESSO techniques for POS forms as well

Содержание слайда: Two Level Logic Forms

Содержание слайда: Summary CAD Tools for 2-level minimization Quine-McCluskey Method ESPRESSO Algorithm NEXT LECTURE: Combinational Logic Implementation Technologies READING: Katz 4.1, 4.2, Dewey 5.2, 5.3, 5.4, 5.5 5.6, 5.7, 6.2