6.004-4 Canonical forms; synthesis, simplification

MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L04 -Logic Synthesis 1 6.004 – Spring 20092/12/09Synthesis of Combinational Logic Lab 1 is due Thursday 2/19Quiz 1 is a week from Friday (in section) ABmodified 2/12/09 10:01 L04 -Logic Synthesis 2 6.004 – Spring 20092/12/09Functional Specifications There are many ways of specifying the function of a combinational device, for example:ABYIf C is 1 then copy B to Y, otherwise copy A to Y CConcise alternatives: truth tables are a concise description of the combinational system’s function. Boolean expressions form an algebra in whose operations are AND (multiplication), OR (addition), and inversion(overbar). Any combinational (Boolean) function can be specified as a truth table or an equivalent sum-of-productsBoolean expression! Argh… I’m tired of word gamesCBAY00000011010001111000101011011111Truth Table CBAACBBACABCY+++=L04 -Logic Synthesis 3 6.004 – Spring 20092/12/09Here’s a Design Approach 1) Write out our functional spec as a truth table 2) Write down a Boolean expression with terms covering each ‘1’ in the output: 3) Wire up the gates, call it a day, and declare success! This approach will always give us Boolean expressions in a particular form: SUM-OF-PRODUCTSCBAY00000011010001111000101011011111Truth Table -it’s systematic! -it works! -it’s easy! -are we done yet???CBAACBBACABCY+++=L04 -Logic Synthesis 4 6.004 – Spring 20092/12/09Straightforward Synthesis We can implementSUM-OF-PRODUCTSwith just three levels of logic.INVERTERS/AND/ORPropagation delay --No more than 3 gate delays(assuming gates with an arbitrary number of inputs) ABCABCABCABCYL04 -Logic Synthesis 5 6.004 – Spring 20092/12/09Basic Gate Repertoire Are we sure we have all the gates we need? Just how many two-input gates are there? ABY000010100111ANDABY000011101111ORABY001011101110NANDABY001010100110NOR2 = 24 = 1622Hmmmm… all of these have 2-inputs (no surprise) … each with 4 combinations, giving 22 output cases How many ways are there of assigning 4 outputs? ________________ L04 -Logic Synthesis 6 6.004 – Spring 20092/12/09There are only so many gates There are only 16 possible 2-input gates … some we know already, others are just silly INPUTABZEROANDA>BAB>ABXORORNORXNORNOT‘B’A<=BNOT‘A’B<=ANANDONE000000000011111111010000111100001111100011001100110011110101010101010101How many of these gates can be implemented using a single CMOS gate? CMOS gates are inverting; we can always respond positively to positive transitions by cascaded gates. But suppose our logic yielded cheap positive functions, while inverters were expensive… L04 -Logic Synthesis 7 6.004 – Spring 20092/12/09Logic Geek Party Games You have plenty of ANDs and ORs, but only 2 inverters. Can you invert more than 2 independent inputs? CHALLENGE: Come up with a combinational circuit using ANDs, ORs, and at most 2 inverters that inverts A, B, and C ! Such a circuit exists. What does that mean? -If we can invert 3 signals using 2 inverters, can we use 2 of the pseudo-inverters to invert 3 more signals? -Do we need only 2 inverters to make ANY combinational circuit? Hint: there’s a subtle difference between our 3-inv device and three combinational inverters! ABCABC3-invIs our 3-inv device LENIENT?L04 -Logic Synthesis 8 6.004 – Spring 20092/12/09Fortunately, we can get by with a few basic gates… How many different gates do we really need? ABY000011100110B>AAByABY000011101110XORABYAND, OR, and NOT are sufficient…(cf Boolean Expressions): AByAB=A+B That is just DeMorgan’sTheorem!AB=A+B A+B = AB ABYL04 -Logic Synthesis 9 6.004 – Spring 20092/12/09One will do!NANDs and NORs are universal:Ah!, but what if we want more than 2-inputs ======L04 -Logic Synthesis 10 6.004 – Spring 20092/12/09Stupid Gate Tricks Suppose we have some 2-input XOR gates: And we want an N-input XOR: A0011B0101C0110tpd = 1 tcd = 0 tpd = O( ___ ) --WORST CASE. output = 1 iff number of 1s input is ODD (“ODD PARITY”)Can we compute N-input XOR faster? NA1A3A4ANA2ABCL04 -Logic Synthesis 11 6.004 – Spring 20092/12/09I think that I shall never see a circuit lovely as... N-input TREE has O( ______ ) levels... Signal propagation takes O( _______ ) gate delays.Question: Can EVERY N-Input Boolean function be implemented as a tree of 2-input gates?log Nlog N21222log2NA1A2A4A3ANL04 -Logic Synthesis 12 6.004 – Spring 20092/12/09Are Trees Always Best? Alternate Plan: Large Fan-in gatesN pulldowns with complementary pullupsOutput HIGH if any input is HIGH = “OR”Propagation delay:O(N) since each additional MOSFET adds C ...NtpdO(log N)O(N)~4Don’t be mislead by the “big O” stuff…the constants in this case can be much smaller… so for small N this plan might be the best. L04 -Logic Synthesis 13 6.004 – Spring 20092/12/09AB=A+B Practical SOP Implementation NAND-NANDNOR-NORCABYCABYzyxxyz++++==CABYyxyx==++CABYCABYAB=A+B “Pushing Bubbles” CABYYou might think all these extra inverters would make this structure less attractive. However, quite the opposite is true. L04 -Logic Synthesis 14 6.004 – Spring 20092/12/09Logic Simplification Can we implement the same function with fewer gates? Before trying we’ll add a few more tricks in our bag. BOOLEAN ALGEBRA: OR rules:a + 1 = 1, a + 0 = a, a + a = a AND rules:a1 = a, aO = 0, aa = a Commutative:a + b = b + a, ab = ba Associative:(a + b) + c = a + (b + c), (ab)c = a(bc) Distributive:a(b+c) = ab + ac, a + bc = (a+b)(a+c) Complements:Absorption:Reduction:DeMorgan’s Law: 0aa1,aa====++babaaa,aba++==++==++abb)aa(a,b)a(a==++==++bb)ab)((ab,baab==++++==++baba,abba++====++L04 -Logic Synthesis 15 6.004 – Spring 20092/12/09Boolean Minimization: An Algebraic Approach BACCBAACBABCY+++=Lets (again!) simplify Using the identity =+AABACCBAACBABCY+++=CBACY+=BACCBABCY++=Can’t he come up with a newexample???For any expression and variable A: Hey, I could write Aprogram to do That! L04 -Logic Synthesis 16 6.004 – Spring 20092/12/09A Case for Non-Minimal SOP ABCBACY++++==ACBYNOTE: The steady state behavior of these circuits is identical. They differ in their transient behavior. Y(1)C(1)Y=CA+CBA(1)B(1)tCD = 1 nS tPD = 2nS 001C BAY00000011010001111000101011011111CACBBAABCYThat’s what we call a “glitch” or “hazard” ABCYNow it’s LENIENT! L04 -Logic Synthesis 17 6.004 – Spring 20092/12/09Truth Tables with “Don’t Cares” C BAY00000011010001111000101011011111CACBBAC BAY0--000--1110--011--1--000--111One way to reveal the opportunities for a more compact implementation is to rewrite the truth table using “don’t cares” (--) to indicate when the value of a particular input is irrelevant in determining the value of the output.L04 -Logic Synthesis 18 6.004 – Spring 20092/12/09We’ve been designing a “mux” D0D1S010101S0101S0101SD00D01D10D11S0 S1… and implemented as a tree of smaller MUXes: 00011011D00D10D11S0S1YD01MUXes can be generalized to 2k data inputs and k select inputs … 2-input Multiplexer YCBAY00000011010001111000101011011111Truth Table YL04 -Logic Synthesis 19 6.004 – Spring 20092/12/09Systematic Implementations of Combinational Logic Consider implementation of some arbitrary Boolean function, F(A,B,C) ... using a MULTIPLEXER as the only circuit element: ABCinCout00000010010001111000101111011111Full-Adder Carry Out Logic 01234567A,B,CinCout00010111L04 -Logic Synthesis 20 6.004 – Spring 20092/12/09General Table Lookup Synthesis MUXLogic ABFn(A,B) Generalizing: In theory, we can build any 1-output combinational logic block with multiplexers. For an N-input function we need a _____ input mux. BIG Multiplexers? How about 10-input function? 20-input? ABFn(A,B)0000111011102NMuxes are UNIVERSAL! In future technologies muxes might be the “natural gate”. 0101S10AYA Y =0101S0BAY0101SB1AY==ABYABY0101SBBAYWhat does that one do? L04 -Logic Synthesis 21 6.004 – Spring 20092/12/09A New Combinational Device kD1D2DNDECODER: k SELECT inputs, N = 2k DATA OUTPUTs. Selected Dj HIGH;all others LOW. NOW, we are well on our way to building a general purpose table-lookup device. We can build a 2-dimensional ARRAY of decoders and selectors as follows ... Have I mentioned that HIGH is a synonym for ‘1’ and LOW means the same as ‘0’ L04 -Logic Synthesis 22 6.004 – Spring 20092/12/09Read-only memories (ROMs) COUTS000001010011100101110111ABCINABCiSCo0000000110010100110110010101011100111111FA ABCoCiSFull Adder For K inputs, decoder produces 2K signals, only 1 of which is asserted at a time --think of it as one signal for each possible product term. Each column is large fan-in “OR” as described on slide #12. Note location of pulldowns correspond to a “1” output in the truth table! Shared decoder One selector for each output L04 -Logic Synthesis 23 6.004 – Spring 20092/12/09Read-only memories (ROMs) ABCiSCo0000000110010100110110010101011100111111FA ABCoCiSFull Adder LONG LINES slow down propagation times… The best way to improve this is to build square arrays, using some inputs to drive output selectors (MUXes):000110110101ABCINCOUTS2D Addressing: Standard for ROMs, RAMs, logic arrays… L04 -Logic Synthesis 24 6.004 – Spring 20092/12/09Logic According to ROMs ROMsignore the structure of combinational functions ... • Size, layout, and design are independent of function • Any Truth table can be “programmed” by minor reconfiguration: -Metal layer (masked ROMs) -Fuses (Field-programmable PROMs) -Charge on floating gates (EPROMs) ... etc. Model: LOOK UP value of function in truth table... Inputs: “ADDRESS” of a T.T. entry ROM SIZE = # TT entries... ... for an N-input boolean function, size = __________ 2N x #outputs ROMs tend to generate “glitchy” outputs. WHY? L04 -Logic Synthesis 25 6.004 – Spring 20092/12/09Summary •Sum of products •Any function that can be specified by a truth table or, equivalently, in terms of AND/OR/NOT (Boolean expression) •“3-level” implementation of any logic function •Limitations on number of inputs (fan-in) increases depth •SOP implementation methods •NAND-NAND, NOR-NOR •Muxes used to build table-lookup implementations •Easy to change implemented function --just change constants •ROMs•Decoder logic generates all possible product terms •Selector logic determines which p’terms are or’ed together