講義課件數(shù)電

1、1Digital Logic Design and ApplicationJin YanhuaLecture #9Combinational-Circuit SynthesisKarnaugh MapsUESTC, Spring 2012Jin. UESTC2Last TimeRepresentations of Logic FunctionsTruth Table Logic Function Logic CircuitProduct term, Sum-of-products expression, AND-ORSum term, Product-of-sums expression, O

2、R-ANDStandard RepresentationsMinterm and MaxtermCanonical Sum, a minterm list using the notation Canonical Product, a maxterm list using the notationAny logic function can be written as a canonical sum or a canonical product.Jin. UESTC3Last TimeAn n-variable function has _ minterm(maxterm).2n 0 1 Th

3、e product of any two different minterm is _ . The sum of any two different maxterm is _ .The sum of all minterms is _ . The product of all maxterms is _.1 0 F = A,B,C(3,5,6) = A,B,C(_)1 對(duì)于任一最小項(xiàng)，有_組變量取值可使其值為1。F = A,B,C(_)0, 1, 2, 4, 7 0, 1, 2, 4, 7 FD = A,B,C(_)1, 2, 4Jin. UESTC4Many representations

4、of digital logicTransistor-level circuit diagramsGate symbols (for simple elements)Truth tablesLogic diagrams, logic circuitsEquations, logic functionsPrepackaged building blocksVarious hardware description languagesZ = SA+SBJin. UESTC54.2 Combinational-Circuit AnalysisPurpose:Logic diagram a formal

5、 description of the functionTruth table (exhausting way)Expressions (algebraic way)Start at the circuit inputs and propagate expression through gates toward the output.Simplify the logic expressionDescribe the logic functionJin. UESTC64.3 Combinational-Circuit SynthesisDesign: from informal descript

6、ion to logic diagramSynthesis: from formal description to logic diagramCircuit Description and design defining the circuits input and output signals and specifying its functional behavior by means of truth tables and equations.select devicesMinimization or transformationCircuit Manipulations, obtain

7、 the logic circuitJin. UESTC7Normal statesAbnormal states1. Circuit Description: Inputs: Red, Yellow, Greencorrespond to the state of three lightslight1, dark0 Output: Faultnormal state0, abnormal state1Example: Design a circuit to check the state of traffic lights.Jin. UESTC8Example: Design a circu

8、it to check the state of traffic lights.0 0 00 0 10 1 00 1 11 0 0 1 0 1 1 1 0 1 1 1 RYGFTruth Table11111Normal state1. Circuit Description: Inputs: Red, Yellow, Greencorrespond to the state of three lightslight1, dark0 Output: Faultnormal state0, abnormal state1Jin. UESTC91. Circuit Description2. Wr

9、ite logic expression and minimizationF = RYG + RY + RG + YG F = (R+Y+G)(R+Y+G)(R+Y+G)( )= (RYG) (RY) (RG) (YG) 3. Circuit Manipulation four AND gates & one OR gate five NAND gates _ NOR gates0 0 00 0 10 1 00 1 11 0 0 1 0 1 1 1 0 1 1 1 RYGFTruth Table11111fourJin. UESTC10Sum-of-products form (SOPs)AN

10、D-ORNAND-NANDJin. UESTC11F = RYG + RY + RG + YG AND-OR circuit NAND-NAND circuitJin. UESTC12Product-of-sums Form (POSs)OR-ANDNOR-NORJin. UESTC134.3 Combinational-Circuit SynthesisCircuit Description Truth TableCombinational-Circuit MinimizationCircuit ManipulationsMeanings?Methods? reduce the number

11、 and size of gatesConsider the cost of circuit AND-OR circuit NAND-NAND circuitOR-AND circuit NOR-NOR circuit theoremsDeMorgans TheormsP211or Karnaugh mapJin. UESTC144.3.4 Karnaugh MapsYX0 101m0m2m1m3m0m2m6m4m1m3m7m5ZXY00 01 11 1001YZWX00000111100111100412151393715261410811K-map: a graphical represe

12、ntation of a truth tableJin. UESTC154.3.4 Karnaugh MapsK-map: a graphical representation of a truth table0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1ABCFF = (A,B,C)(3,5,6,7)00100111CAB00 01 11 10011-cell minterm0-cell maxtermJin. UESTC16Example: Draw the K-maps for the following function

13、sF1 = (A,B,C) (1,3,4,7) F2(A,B,C) = AC + BCD + B00001111CAB00 01 11 1001F1CDAB0000011110011110F21111111111000000Plot 1s corresponding to minterms of functionJin. UESTC174.3.4 Karnaugh MapsAdjacentA cell and its immediately adjacent neighbors differ only in one variable.Combining adjacent cells111ZXY

14、00 01 11 1001i literals can be eliminated from 2i adjacent cellsJin. UESTC18one literal can be eliminated from two adjacent 1-cells111111ZXY00 01 11 1001YZWX000001111001111011111111XYZ + XYZ = YZ Jin. UESTC19ABCD = ABD ZXY00 01 11 10011 1 1 11 1 0 1+ ABCD + ABCD+ ABCD + ABD = BDTwo literals can be e

15、liminated from four adjacent cells. ABCD00000111100111101111111111Jin. UESTC20ABCD00 01 11 10000111101111111111110000AD消掉既能為 0 也能為 1 的變量保留始終為0或始終為1的變量Three literals can be eliminated from eight adjacent cells.Jin. UESTC214.3.5 Minimizing Sum of ProductsExample: F = A,B,C,D ( 0, 2, 3, 5, 7, 8, 10, 11, 13 )CDAB00 01 11 10000111101111111111. Drawing map2. Circling adjacent cells area of circle: as large as possible number of circle: as few as possible cells can be reused3. Write term