CS Fall Combinational Implementation - 1 Combinational Logic Implementation zTwo-level logic yImplementations of two-level logic yNAND/NOR zMulti-level logic yFactored forms yAnd-or-invert gates zTime behavior yGate delays yHazards zRegular logic yMultiplexers yDecoders yPAL/PLAs yROMs

CS Fall Combinational Implementation - 2 Implementations of Two-level Logic zSum-of-products yAND gates to form product terms (minterms) yOR gate to form sum zProduct-of-sums yOR gates to form sum terms (maxterms) yAND gates to form product

CS Fall Combinational Implementation - 3 Two-level Logic using NAND Gates zReplace minterm AND gates with NAND gates zPlace compensating inversion at inputs of OR gate

CS Fall Combinational Implementation - 4 Two-level Logic using NAND Gates (contd) zOR gate with inverted inputs is a NAND gate yde Morgan's:A' + B' = (A B)' zTwo-level NAND-NAND network yInverted inputs are not counted yIn a typical circuit, inversion is done once and signal distributed

CS Fall Combinational Implementation - 5 Two-level Logic using NOR Gates zReplace maxterm OR gates with NOR gates zPlace compensating inversion at inputs of AND gate

CS Fall Combinational Implementation - 6 Two-level Logic using NOR Gates (contd) zAND gate with inverted inputs is a NOR gate yde Morgan's:A' B' = (A + B)' zTwo-level NOR-NOR network yInverted inputs are not counted yIn a typical circuit, inversion is done once and signal distributed

CS Fall Combinational Implementation - 7 OR NAND OR AND NOR AND Two-level Logic using NAND and NOR Gates zNAND-NAND and NOR-NOR networks yde Morgan's law:(A + B)'= A' B' (A B)' = A' + B' ywritten differently: A + B= (A' B') (A B) = (A' + B')' zIn other words –– yOR is the same as NAND with complemented inputs yAND is the same as NOR with complemented inputs yNAND is the same as OR with complemented inputs yNOR is the same as AND with complemented inputs

CS Fall Combinational Implementation - 8 A B C D Z A B C D Z NAND Conversion Between Forms zConvert from networks of ANDs and ORs to networks of NANDs and NORs yIntroduce appropriate inversions ("bubbles") zEach introduced "bubble" must be matched by a corresponding "bubble" yConservation of inversions yDo not alter logic function zExample: AND/OR to NAND/NAND

CS Fall Combinational Implementation - 9 Z = [ (A B)' (C D)' ]' = [ (A' + B') (C' + D') ]' = [ (A' + B')' + (C' + D')' ] = (A B) + (C D) Conversion Between Forms (contd) zExample: verify equivalence of two forms A B C D Z A B C D Z NAND

CS Fall Combinational Implementation - 10 Step 2 conserve "bubbles" Step 1 conserve "bubbles" NOR \A \B \C \D Z NOR A B C D Z Conversion Between Forms (contd) zExample: map AND/OR network to NOR/NOR network A B C D Z

CS Fall Combinational Implementation - 11 Z = { [ (A' + B')' + (C' + D')' ]' }' = { (A' + B') (C' + D') }' = (A' + B')' + (C' + D')' = (A B) + (C D) Conversion Between Forms (contd) zExample: verify equivalence of two forms A B C D Z NOR \A \B \C \D Z

CS Fall Combinational Implementation - 12 ABCDEFGABCDEFG X Multi-level Logic zx = A D F + A E F + B D F + B E F + C D F + C E F + G yReduced sum-of-products form – already simplified y6 x 3-input AND gates + 1 x 7-input OR gate (may not exist!) y25 wires (19 literals plus 6 internal wires) zx = (A + B + C) (D + E) F + G yFactored form – not written as two-level S-o-P y1 x 3-input OR gate, 2 x 2-input OR gates, 1 x 3-input AND gate y10 wires (7 literals plus 3 internal wires)

CS Fall Combinational Implementation - 13 Level 1Level 2Level 3Level 4 original AND-OR network A C D B B \C F introduction and conservation of bubbles A C D B B \C F redrawn in terms of conventional NAND gates A C D \B B \C F Conversion of Multi-level Logic to NAND Gates zF = A (B + C D) + B C'

CS Fall Combinational Implementation - 14 Level 1Level 2Level 3Level 4 A C D B B \C F original AND-OR network introduction and conservation of bubbles A C D B B \C F redrawn in terms of conventional NOR gates \A \C \D B \B C F Conversion of Multi-level Logic to NORs zF = A (B + C D) + B C'

CS Fall Combinational Implementation - 15 A X B C D F (a) original circuit A X B C D F (b) add double bubbles at inputs \D A \X B C F (c) distribute bubbles some mismatches \D A X B C F \X (d) insert inverters to fix mismatches Conversion Between Forms zExample

CS Fall Combinational Implementation - 16 & & + 2x2 AOI gate symbol & & + 3x2 AOI gate symbol NAND Invert possible implementation A B C D Z AND ORInvert logical concept A B C D Z AND-OR-Invert Gates zAOI function: three stages of logicAND, OR, Invert yMultiple gates "packaged" as a single circuit block

CS Fall Combinational Implementation A B & & + A' B' A B F Conversion to AOI Forms zGeneral procedure to place in AOI form yCompute complement of the function in sum-of-products form yBy grouping the 0s in the Karnaugh map zExample: XOR implementation––A xor B = A' B + A B' yAOI form:F = (A' B' + A B)'

CS Fall Combinational Implementation - 18 each implemented in a single 2x2 AOI gate Examples of using AOI gates zExample: yF = B C' + A C' + A B yF' = A' B' + A' C + B' C yImplemented by 2-input 3-stack AOI gate yF = (A + B) (A + C') (B + C') yF' = (B' + C) (A' + C) (A' + B') yImplemented by 2-input 3-stack OAI gate zExample: 4-bit equality function yZ = (A0B0+A0'B0')(A1B1+A1'B1')(A2B2+A2'B2')(A3B3+A3'B3') C B A

CS Fall Combinational Implementation - 19 high if A0 B0 low if A0 = B0 if all inputs are low then Ai = Bi, i=0,...,3 output Z is high conservation of bubbles Examples of Using AOI Gates (contd) zExample: AOI implementation of 4-bit equality function

CS Fall Combinational Implementation - 20 Summary for Multi-level Logic zAdvantages yCircuits may be smaller yGates have smaller fan-in yCircuits may be faster zDisadvantages yMore difficult to design yTools for optimization are not as good as for two-level yAnalysis is more complex

CS Fall Combinational Implementation - 21 Time Behavior of Combinational Networks zWaveforms yVisualization of values carried on signal wires over time yUseful in explaining sequences of events (changes in value) zSimulation tools are used to create these waveforms yInput to the simulator includes gates and their connections yInput stimulus, that is, input signal waveforms zSome terms yGate delaytime for change at input to cause change at output xMin delay–typical/nominal delay–max delay xCareful designers design for the worst case yRise timetime for output to transition from low to high voltage yFall timetime for output to transition from high to low voltage yPulse widthtime an output stays high or low between changes

CS Fall Combinational Implementation - 22 F is not always 0 pulse 3 gate-delays wide D remains high for three gate delays after A changes from low to high F ABCD Momentary Changes in Outputs zCan be usefulpulse shaping circuits zCan be a problemincorrect circuit operation (glitches/hazards) zExample: pulse shaping circuit yA' A = 0 ydelays matter in function

CS Fall Combinational Implementation - 23 initially undefined close switch open switch + resistor A B C D Oscillatory Behavior zAnother pulse shaping circuit

CS Fall Combinational Implementation - 24 Hazards/Glitches zHazards/glitches: unwanted switching at the outputs yOccur when different paths through circuit have different propagation delays xAs in pulse shaping circuits we just analyzed yDangerous if logic causes an action while output is unstable xMay need to guarantee absence of glitches zUsual solutions y1) Wait until signals are stable (by using a clock): preferable (easiest to design when there is a clock – synchronous design) y2) Design hazard-free circuits: sometimes necessary (clock not used – asynchronous design)

CS Fall Combinational Implementation Types of Hazards zStatic 1-hazard yInput change causes output to go from 1 to 0 to 1 zStatic 0-hazard yINput change causes output to go from 0 to 1 to 0 zDynamic hazards yInput change causes a double change from 0 to 1 to 0 to 1 OR from 1 to 0 to 1 to 0

CS Fall Combinational Implementation - 26 F A B S S' F hazard static-0 hazardstatic-1 hazard A S B S' Static Hazards zDue to a literal and its complement momentarily taking on the same value yThru different paths with different delays and reconverging zMay cause an output that should have stayed at the same value to momentarily take on the wrong value zExample: multiplexer

CS Fall Combinational Implementation - 27 B2 A C B1 F hazard dynamic hazards B3 A C B F Dynamic Hazards zDue to the same versions of a literal taking on opposite values yThru different paths with different delays and reconverging zMay cause an output that was to change value to change 3 times instead of once zExample:

CS Fall Combinational Implementation - 28 multiplexerdemultiplexer4x4 switch control Making Connections zDirect point-to-point connections between gates yWires we've seen so far zRoute one of many inputs to a single output --- multiplexer zRoute a single input to one of many outputs --- demultiplexer

CS Fall Combinational Implementation - 29 Mux and Demux zSwitch implementation of multiplexers and demultiplexers yCan be composed to make arbitrary size switching networks yUsed to implement multiple-source/multiple-destination interconnections A B Y Z A B Y Z

CS Fall Combinational Implementation - 30 multiple input sources multiple output destinations MUX A B Sum Sa Ss Sb B0 MUX DEMUX Mux and Demux (cont'd) zUses of multiplexers/demultiplexers in multi-point connections B1A0A1 S0S1

CS Fall Combinational Implementation - 31 two alternative forms for a 2:1 Mux truth table functional form logical form AZ0I01I1AZ0I01I1 I1I0AZ I1I0AZ Z = A' I 0 + A I 1 Multiplexers/Selectors zMultiplexers/Selectors: general concept y2 n data inputs, n control inputs (called "selects"), 1 output yUsed to connect 2 n points to a single point yControl signal pattern forms binary index of input connected to output

CS Fall Combinational Implementation I0 I1 I2 I3 I4 I5 I6 I7 A B C 8:1 mux Z I0 I1 I2 I3 A B 4:1 mux Z I0 I1 A 2:1 mux Z k=0 n Multiplexers/Selectors (cont'd) z2:1 mux:Z = A' I0 + A I1 z4:1 mux:Z = A' B' I0 + A' B I1 + A B' I2 + A B I3 z8:1 mux:Z = A'B'C'I0 + A'B'CI1 + A'BC'I2 + A'BCI3 + AB'C'I4 + AB'CI5 + ABC'I6 + ABCI7 zIn general, Z = (m k I k ) yin minterm shorthand form for a 2 n :1 Mux

CS Fall Combinational Implementation - 33 Gate Level Implementation of Muxes z2:1 mux z4:1 mux

CS Fall Combinational Implementation - 34 control signals B and C simultaneously choose one of I0, I1, I2, I3 and one of I4, I5, I6, I7 control signal A chooses which of the upper or lower mux's output to gate to Z alternative implementation C Z A B 4:1 mux 2:1 mux I4 I5 I2 I3 I0 I1 I6 I7 8:1 mux Cascading Multiplexers zLarge multiplexers implemented by cascading smaller ones Z I0 I1 I2 I3 A I4 I5 I6 I7 B C 4:1 mux 2:1 mux 8:1 mux

CS Fall Combinational Implementation - 35 C AB S2 8:1 MUX S1S0 F Multiplexers as General-purpose Logic z2 n :1 multiplexer implements any function of n variables yWith the variables used as control inputs and yData inputs tied to 0 or 1 yIn essence, a lookup table zExample: yF(A,B,C) = m0 + m2 + m6 + m7 = A'B'C' + A'BC' + ABC' + ABC = A'B'(C') + A'B(C') + AB'(0) + AB(1)

CS Fall Combinational Implementation - 36 ABCF ABCF C' C' 0 1 AB S1S0 F :1 MUX C' C' 0 1 F C AB S2 8:1 MUX S1S0 Multiplexers as General-purpose Logic (contd) z2 n-1 :1 mux can implement any function of n variables yWith n-1 variables used as control inputs and yData inputs tied to the last variable or its complement zExample: yF(A,B,C) = m0 + m2 + m6 + m7 = A'B'C' + A'BC' + ABC' + ABC = A'B'(C') + A'B(C') + AB'(0) + AB(1)

CS Fall Combinational Implementation - 37 n-1 mux control variables single mux data variable four possible configurations of truth table rows can be expressed as a function of I n choose A,B,C as control variables multiplexer implementation I 0 I 1...I n-1 I n F I n I n '1 Multiplexers as General-purpose Logic (contd) zGeneralization zExample: F(A,B,C,D) implemented by an 8:1 MUX C AB D01DDDD1D01DDDD S2 8:1 MUX S1S D A B C

CS Fall Combinational Implementation :2 Decoder: O0 = G S O1 = G S 2:4 Decoder: O0 = G S1 S0 O1 = G S1 S0 O2 = G S1 S0 O3 = G S1 S0 3:8 Decoder: O0 = G S2 S1 S0 O1 = G S2 S1 S0 O2 = G S2 S1 S0 O3 = G S2 S1 S0 O4 = G S2 S1 S0 O5 = G S2 S1 S0 O6 = G S2 S1 S0 O7 = G S2 S1 S0 Demultiplexers/Decoders zDecoders/demultiplexers: general concept ySingle data input, n control inputs, 2 n outputs yControl inputs (called selects (S)) represent binary index of output to which the input is connected yData input usually called enable (G)

CS Fall Combinational Implementation - 39 active-high enable active-low enable active-high enable active-low enable O0 G S O1 O0 \G S O1 Gate Level iImplementation of Demultiplexers z1:2 Decoders z2:4 Decoders

CS Fall Combinational Implementation - 40 demultiplexer generates appropriate minterm based on control signals (it "decodes" control signals) Demultiplexers as General-purpose Logic zn:2 n decoder implements any function of n variables yWith the variables used as control inputs yEnable inputs tied to 1 and yAppropriate minterms summed to form the function A'B'C' A'B'C A'BC' A'BC AB'C' AB'C ABC' ABC C AB S2 3:8 DEC S1S0 1

CS Fall Combinational Implementation - 41 F1 F2 F3 Demultiplexers as General-purpose Logic (contd) zF1 = A' B C' D + A' B' C D + A B C D zF2 = A B C' D + A B C zF3 = (A' + B' + C' + D') AB 0A'B'C'D' 1A'B'C'D 2A'B'CD' 3A'B'CD 4A'BC'D' 5A'BC'D 6A'BCD' 7A'BCD 8AB'C'D' 9AB'C'D 10AB'CD' 11AB'CD 12ABC'D' 13ABC'D 14ABCD' 15ABCD 4:16 DEC Enable CD

CS Fall Combinational Implementation A'B'C'D'E' S2 3:8 DEC S1S0 AB S1 2:4 DEC S0 F 0 1 2A'BC'DE' S2 3:8 DEC S1S0 E CD 0AB'C'D'E' AB'CDE Cascading Decoders z5:32 decoder y1x2:4 decoder y4x3:8 decoders 3:8 DEC ABCDE E CD S2S1S0S2 3:8 DEC S1S0

CS Fall Combinational Implementation - 43 inputs AND array outputs OR array product terms Programmable Logic Arrays zPre-fabricated building block of many AND/OR gates yActually NOR or NAND yPersonalized" by making or breaking connections among gates yProgrammable array block diagram for sum of products form

CS Fall Combinational Implementation - 44 example: F0 = A + B' C' F1 = A C' + A B F2 = B' C' + A B F3 = B' C + A personality matrix 1 = uncomplemented in term 0 = complemented in term – = does not participate 1 = term connected to output 0 = no connection to output input side: output side: productinputsoutputs termABCF0F1F2F3 AB11–0110 B'C– AC'1–00100 B'C'– A1––1001 reuse of terms Enabling Concept zShared product terms among outputs

CS Fall Combinational Implementation - 45 Before Programming zAll possible connections available before "programming" yIn reality, all AND and OR gates are NANDs

CS Fall Combinational Implementation - 46 After Programming zUnwanted connections are "blown" yFuse (normally connected, break unwanted ones) yaAnti-fuse (normally disconnected, make wanted connections)

CS Fall Combinational Implementation - 47 notation for implementing F0 = A B + A' B' F1 = C D' + C' D AB+A'B' CD'+C'D AB A'B' CD' C'D ABCD Alternate Representation for High Fan-in Structures zShort-hand notation--don't have to draw all the wires ySignifies a connection is present and perpendicular signal is an input to gate

CS Fall Combinational Implementation - 48 ABCF1F2F3F4F5F full decoder as for memory address bits stored in memory Programmable Logic Array Example zMultiple functions of A, B, C yF1 = A B C yF2 = A + B + C yF3 = A' B' C' yF4 = A' + B' + C' yF5 = A xor B xor C yF6 = A xnor B xnor C

CS Fall Combinational Implementation - 49 a given column of the OR array has access to only a subset of the possible product terms PALs and PLAs zProgrammable logic array (PLA) yWhat we've seen so far yUnconstrained fully-general AND and OR arrays zProgrammable array logic (PAL) yConstrained topology of the OR array yInnovation by Monolithic Memories yFaster and smaller OR plane

CS Fall Combinational Implementation X X X X 0 0 X X D A B C minimized functions: W = A + B D + B C X = B C' Y = B + C Z = A'B'C'D + B C D + A D' + B' C D' ABCDWXYZ –––––11––––––ABCDWXYZ –––––11–––––– 0 0 X X X X 0 1 X X D A B C K-map for WK-map for X 0 1 X X X X 1 1 X X D A B C K-map for Y PALs and PLAs: Design Example zBCD to Gray code converter K-map for Z 0 0 X X X X 1 0 X X D A B C

CS Fall Combinational Implementation - 51 not a particularly good candidate for PAL/PLA implementation since no terms are shared among outputs however, much more compact and regular implementation when compared with discrete AND and OR gates minimized functions: W = A + B D + B C X = B C' Y = B + C Z = A'B'C'D + B C D + A D' + B' C D' PALs and PLAs: Design Example (contd) zCode converter: programmed PLA

CS Fall Combinational Implementation product terms per each OR gate AB CD PALs and PLAs: Design Example (contd) zCode converter: programmed PAL

CS Fall Combinational Implementation - 53 PALs and PLAs: Design Example (contd) zCode converter: NAND gate implementation yLoss or regularity, harder to understand yHarder to make changes

CS Fall Combinational Implementation - 54 PALs and PLAs: Another Design Example zMagnitude comparator D A B C D A B C D A B C D A B C K-map for EQ K-map for NE K-map for GT K-map for LT

CS Fall Combinational Implementation - 55 decoder 0n-1 Address 2 -1 n word[i] = 0011 word[j] = 1010 bit lines (normally pulled to 1 through resistor – selectively connected to 0 by word line controlled switches) j i internal organization word lines (only one is active – decoder is just right for this) Read-only Memories zTwo dimensional array of 1s and 0s yEntry (row) is called a "word" yWidth of row = word-size yIndex is called an "address" yAddress is input ySelected word is output

CS Fall Combinational Implementation - 56 F0 = A' B' C + A B' C' + A B' C F1 = A' B' C + A' B C' + A B C F2 = A' B' C' + A' B' C + A B' C' F3 = A' B C + A B' C' + A B C' truth table ABCF0F1F2F block diagram ROM 8 words x 4 bits/word addressoutputs ABCF0F1F2F3 ROMs and Combinational Logic zCombinational logic implementation (two-level canonical form) using a ROM

CS Fall Combinational Implementation - 57 ROM Structure zSimilar to a PLA structure but with a fully decoded AND array yCompletely flexible OR array (unlike PAL) n address lines inputs decoder 2 n word lines outputs memory array (2 n words by m bits) m data lines

CS Fall Combinational Implementation - 58 ROM vs. PLA zROM approach advantageous when yDesign time is short (no need to minimize output functions) yMost input combinations are needed (e.g., code converters) yLittle sharing of product terms among output functions zROM problems ySize doubles for each additional input yCan't exploit don't cares zPLA approach advantageous when yDesign tools are available for multi-output minimization yThere are relatively few unique minterm combinations yMany minterms are shared among the output functions zPAL problems yConstrained fan-ins on OR plane

CS Fall Combinational Implementation - 59 Regular Logic Structures for Two-level Logic zROM – full AND plane, general OR plane yCheap (high-volume component) yCan implement any function of n inputs yMedium speed zPAL – programmable AND plane, fixed OR plane yIntermediate cost yCan implement functions limited by number of terms yHigh speed (only one programmable plane that is much smaller than ROM's decoder) zPLA – programmable AND and OR planes yMost expensive (most complex in design, need more sophisticated tools) yCan implement any function up to a product term limit ySlow (two programmable planes)

CS Fall Combinational Implementation - 60 Regular Logic Structures for Multi-level Logic zDifficult to devise a regular structure for arbitrary connections between a large set of different types of gates yEfficiency/speed concerns for such a structure yXilinx field programmable gate arrays (FPGAs) are just such programmable multi-level structures xProgrammable multiplexers for wiring xLookup tables for logic functions (programming fills in the table) xMulti-purpose cells (utilization is the big issue) zUse multiple levels of PALs/PLAs/ROMs yOutput intermediate result yMake it an input to be used in further logic

CS Fall Combinational Implementation - 61 Combinational Logic Implementation Summary zMulti-level Logic yConversion to NAND-NAND and NOR-NOR networks yTransition from simple gates to more complex gate building blocks yReduced gate count, fan-ins, potentially faster yMore levels, harder to design zTime Response in Combinational Networks yGate delays and timing waveforms yHazards/glitches (what they are and why they happen) zRegular Logic yMultiplexers/decoders yROMs yPLAs/PALs yAdvantages/disadvantages of each