EECS150Section 5Simplification and State MinimizationFall 2001EECS150 - Fall 2001 1-2SimplificationFinding a minimal sum of products or product of sums realizationExploit don't care information in the processAlgebraic simplificationNot an algorithmic/systematic procedureHow do you know when the minimum realization has been found?Computer-aided design toolsPrecise solutions require very long computation times, especially for functions with many inputs (> 10)Heuristic methods employed – "educated guesses" to reduce amount of computation and yield good if not best solutionsHand methods still relevantTo understand automatic tools and their strengths and weaknessesAbility to check results (on small examples)EECS150 - Fall 2001 1-3ABF001010101110B has the same value in both on-set rows–B remainsA has a different value in the two rows– A is eliminatedF = A'B'+AB' = (A'+A)B' = B'The Uniting TheoremKey tool to simplification: A (B' + B) = AEssence of simplification of two-level logicFind two element subsets of the ON-set where only one variable changes its value – this single varying variable can be eliminated and a single product term used to represent both elementsEECS150 - Fall 2001 1-41-cubeX01Boolean cubesVisual technique for indentifying when the uniting theorem can be appliedn input variables = n-dimensional "cube"2-cubeXY110001103-cubeXYZ0001111014-cubeWXYZ0000011111111000EECS150 - Fall 2001 1-5ABF001010101110ON-set = solid nodesOFF-set = empty nodestwo faces of size 0 (nodes) combine into a face of size 1(line)A varies within face, B does notthis face represents the literal B'Mapping truth tables onto cubesUniting theorem combines two "faces" of a cube into a larger "face"Example:AB11000110FEECS150 - Fall 2001 1-6ABCin Cout000 0001 001 0 001 1 1100 0101 1110 1111 1Cout = BCin+AB+ACinA(B+B')Cinthe on-set is completely covered by the combination (OR) of the subcubes of lower dimensionality - note that “111”is covered three timesThree variable exampleBinary full-adder carry-out logicABC000111101(A'+A)BCinAB(Cin'+Cin)EECS150 - Fall 2001 1-7F(A,B,C) = Σm(4,5,6,7)A is asserted (true) and unchangedB and C varyHigher dimensional cubesSub-cubes of higher dimension than 2ABC000111101100001010011110on-set forms a squarei.e., a cube of dimension 2represents an expression in one variable i.e., 3 dimensions – 2 dimensionsThis subcube represents theliteral AEECS150 - Fall 2001 1-8m-dimensional cubesIn a 3-cube (three variables):0-cube, i.e., a single node, yields a term in 3 literals1-cube, i.e., a line of two nodes, yields a term in 2 literals2-cube, i.e., a plane of four nodes, yields a term in 1 literal3-cube, i.e., a cube of eight nodes, yields a constant term "1"In general,m-subcube within an n-cube (m < n) yields a term with n – m literalsEECS150 - Fall 2001 1-9ABF00101 0101110Karnaugh mapsFlat map of Boolean cubeWrap–around at edgesHard to draw and visualize for more than 4 dimensionsVirtually impossible for more than 6 dimensionsAlternative to truth-tables to help visualize adjacenciesGuide to applying the uniting theoremOn-set elements with only one variable changing value are adjacent unlike the situation in a linear truth-table021301AB011001EECS150 - Fall 2001 1-10Karnaugh maps (cont’d)Numbering scheme based on Gray–codee.g., 00, 01, 11, 10Only a single bit changes in code for adjacent map cells021300 01ABC01647511 10CBA02136475CBA041512 813 9DA372615 1114 10CB13 = 1101= ABC’DEECS150 - Fall 2001 1-11Adjacencies in Karnaugh mapsWrap from first to last columnWrap top row to bottom row000 010001 011110 100111 101CBAABC000111101100001010011110EECS150 - Fall 2001 1-12obtain thecomplementof the function by covering 0swith subcubesKarnaugh map examplesF =Cout =f(A,B,C) = Σm(0,4,6,7) 00011011CinBA1100BA10000111CBAB’ABAC+ ACin+BCin+ B’C’+ AB’EECS150 - Fall 2001 1-13F(A,B,C) = Σm(0,4,5,7)F'(A,B,C) = Σm(1,2,3,6)F' simply replace 1's with 0's and vice versaG(A,B,C) = More Karnaugh map examples00001111CBA10000111CBA01111000CBAA= AC + B’C’= BC’ + A’CEECS150 - Fall 2001 1-14C + B’D’find the smallest number of the largest possiblesubcubes to cover the ON-set(fewer terms with fewer inputs per term)Karnaugh map: 4-variable exampleF(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15)F =DABABCD00001111100001111001010011111111C+ A’BDEECS150 - Fall 2001 1-15+ B’C’DKarnaugh maps: don’t caresf(A,B,C,D) = Σ m(1,3,5,7,9) + d(6,12,13) without don't caresf = 0011X0X1DA110X0000BCA’DEECS150 - Fall 2001 1-16Karnaugh maps: don’t caresf(A,B,C,D) = Σ m(1,3,5,7,9) + d(6,12,13)f = A'D + B'C'D without don't caresf = with don't caresdon't cares can be treated as1s or 0sdepending on which is more advantageous0011X0X1DA110X0000BCby using don't care as a "1"a 2-cube can be formed rather than a 1-cube to coverthis nodeA'D + C'DEECS150 - Fall 2001 1-17we'll need a 4-variable Karnaugh map for each of the 3 output functionsExample: two-bit comparatorblock diagramLTEQGTA B < C DA B = C DA B > C DABCDN1N2ABCD LTEQGT0000 0 1 001 1 0 010 1 0 011 1 0 001 00 0 0 101 0 1 010 1 0 011 1 0 01 000 0 0 101 0 0 110 0 1 011 1 0 01100 0 0 101 0 0 110 0 0 111 0 1 0andtruth tableEECS150 - Fall 2001 1-18A' B' D + A' C + B' C DB C' D' + A C' + A B D'LT =EQ =GT =K-map for EQK-map for LT K-map for GTExample: two-bit comparator00100000DA11110100BC10010000DA00001001BC01001111DA00000010BC= (A xnor C) • (B xnor D)LT and GT are similar (flip A/C and B/D)A'B'C'D' + A'BC'D + ABCD + AB'CD’EECS150 - Fall 2001 1-19two alternativeimplementations of EQwith and without XORXNOR is implemented with at least 3 simple gatesABCDEQEQExample: two-bit comparatorEECS150 - Fall 2001 1-20block diagramandtruth table4-variable K-mapfor each of the 4output functionsA2 A1 B2 B1 P8 P4 P2 P10000 0 0 0 001 000010000011 000001 00 0 0 0 001 000110 0 0 1 011 0 0 1 11 000 0 0 0 001 0 0 1 010 0 1 0 01101101100 0 0 0 001 0 0 1 110011011 1 001Example: 2x2-bit multiplierP1P2P4P8A1A2B1B2EECS150 - Fall 2001 1-21K-map for P8K-map for P4K-map for P2 K-map for P1Example: 2x2-bit multiplier00000000B1A200000111A1B200010010B1A201001000A1B200000011B1A201010110A1B200000000B1A200001000A1B2P8 = A2A1B2B1P1 = A1B1P2 = A2'A1B2+ A1B2B1'+ A2B2'B1+ A2A1'B1P4 = A2B2B1'+ A2A1'B2EECS150 - Fall 2001 1-22I8 I4 I2 I1 O8 O4 O2 O1000000010001 001 0001 0001 10011010001 0001 0101 01 01 1
View Full Document
Unlocking...