D e p a r t m e n t o f C o m p u t e r S y s t e m s Espresso Explained How espresso works and what is behind this espresso two level Boolean function minimizer Center for Electronic Systems Design UC Berkeley https ptolemy berkeley edu projects embedded pubs downloads espresso Previously UC Berkeley Design Technology Warehouse Local web page slightly modified http mini pld ttu ee lrv espresso Exact and heuristic minimization of Boolean functions Multi Valued Logic Data encoding and main operations Giovanni De Micheli Synthesis and Optimization of Digital Circuits McGraw Hill Peeter Ellervee cad espresso 1 D e p a r t m e n t o f C o m p u t e r S y s t e m s Set of Boolean Functions Black box model of a combinational circuit Defined based on Boolean algebra B B 0 1 Logic functions Boolean functions can be with multiple outputs set of functions partially defined incomplete f Bn 0 1 m f Bn B also and depends how functions are used e g impossible input combinations f Bn Bm f Bn 0 1 m ON set Ff the domain of a function where f is true OFF set Rf the domain of a function where f is false DC set Df the domain of a function where f is undefined don t care Defined for every component in a set of functions Peeter Ellervee cad espresso 2 D e p a r t m e n t o f C o m p u t e r S y s t e m s Definitions and Representations abc xy 000 10 001 11 101 11 110 10 111 10 variable literal variable and its inversion product cube conjunction multiplication of literals implicant interval conjunction defining the value of a function usually 1 minterm implicant containing all input hypercube variables a vertice node in hyper cube truth table list of all minterms implicant table interval table cover set of implicants sufficient to define a function c 1 1 1 1 1 1 b a x hyper cube abc xy 00 10 01 11 1 1 10 11 10 y Peeter Ellervee cad espresso 3 D e p a r t m e n t o f C o m p u t e r S y s t e m s Definitions Cover a cover with the smallest number of implicants global optimum Minimum cover Minimal cover Irredundant cover a cover not contained in any other cover it is not possible to remove any of the implicants local optimum Prime implicant not contained in any other implicant Prime cover a cover of prime implicants Essential prime implicant there is a minterm cover by only this implicant Peeter Ellervee cad espresso 4 essential implicants x y D e p a r t m e n t o f C o m p u t e r S y s t e m s 1 1 1 1 1 1 1 1 1 1 1 1 c b a c b a c b a x x x y y y 1 1 1 1 1 1 prime cover minimum cover prime cover minimal cover prime cover Peeter Ellervee cad espresso 5 D e p a r t m e n t o f C o m p u t e r S y s t e m s Logic Function Minimization often impossible for large functions Exact methods e g Quine McCluskey method will find minimum cover s Heuristic methods MINI PRESTO ESPRESSO will find minimal covers can find minimum cover Quine s theorem minimum cover is prime cover prime implicants are enough to find minimum cover Quine McCluskey method main steps 1 find all prime implicants 2 find minimum cover Prime implicant table chart exponential size up to 2n minterms can be grouped up to 3n n prime implicants some functions have less Peeter Ellervee cad espresso 6 D e p a r t m e n t o f C o m p u t e r S y s t e m s Finding Prime Implicants Quine method f a d a b a b a c d f a b c d 0 2 4 5 6 7 8 9 10 11 13 minterms are initial prime implicants implicants are combined pair wise covered and duplicated implicants are removed combining implicants and removing covered ones this is continued until no more new implicants is generated start abcd 0000 0010 0100 0101 0110 0111 1000 1001 1010 1011 1101 1st phase abcd abcd 000 0000 0010 0 10 010 0100 010 0101 01 0 0110 0111 100 10 0 1000 01 1 1001 101 1010 011 1011 10 1 1101 1 01 00 0 101 0 00 2nd phase abcd abcd 10 1 00 0 1 01 0 00 101 000 0 0 0 10 0 0 010 0 0 010 0 0 01 0 01 100 01 10 0 10 01 1 10 101 011 result abcd 101 1 01 0 0 0 0 01 10 Peeter Ellervee cad espresso 7 D e p a r t m e n t o f C o m p u t e r S y s t e m s Finding Prime Implicants Quine McCluskey method Constraints when finding prime implicants minterms are grouped by the number of 1 s only implicants from neighboring groups can be combined compare the number of 1 s implicants covering don t cares only have special notation e g the notation spreads when combining two implicants with the same notation a hint an implicant covering only don t cares is not needed in the implicant cover irrelevant inputs can be taken into account when combining implicants only implicants depending on the same variables can be combined Finding the minimal minimum cover of prime implicants simplifying the task by identifying the essential primes and removing from the table identifying duplicated minterms covered by the same primes and removing them too Peeter Ellervee cad espresso 8 D e p a r t m e n t o f C o m p u t e r S y s t e m s Finding Prime Implicants f a d a b a b a c d f a b c d 0 2 4 5 6 7 8 9 10 11 13 minterms 2nd stage gr abcd gr abcd 0 0 0 C 0 0000 0 0 D 1 0010 1 01 E 0100 10 F 1000 2 0101 0110 1001 1010 3 0111 1011 1101 1st stage gr abcd 0 00 0 0 00 000 1 0 10 010 010 01 0 100 10 0 2 01 1 101 A 011 10 1 1 01 B 101 is covered Peeter Ellervee cad espresso 9 d E c 1 0 0 1 C 1 1 1 1 0 1 0 0 1 1 1 1 D A B F b a D e p a r t m e n t o f C o m p u t e r S …