Spring 2000 EECS150 Page 1Review - Canonical Forms• Standard form for a Boolean expression -unique algebraic expression from a TT.• Two Types:ϕ Sum of Productsκ Product of Sums• Sum of Products (disjunctive normalform, minterm expansion). Example:minterms a b c f f’a’b’c’ 0 0 0 0 1a’b’c 0 0 1 0 1a’bc’ 0 1 0 0 1a’bc 0 1 1 1 0ab’c’ 1 0 0 1 0ab’c 1 0 1 1 0abc’ 1 1 0 1 0abc 1 1 1 1 0One product (and) term for each 1 in f:f = a’bc + ab’c’ + ab’c +abc’ +abcf’ = a’b’c’ + a’b’c + a’bc’Spring 2000 EECS150 Page 2Canonical Forms• Product of Sums (conjunctive normal form,maxterm expansion). Example:maxterms a b c f f’a+b+c 0 0 0 0 1a+b+c’ 0 0 1 0 1a+b’+c 0 1 0 0 1a+b’+c’ 0 1 1 1 0a’+b+c 1 0 0 1 0a’+b+c’ 1 0 1 1 0a’+b’+c 1 1 0 1 0a’+b’+c’ 1 1 1 1 0One sum (or) term for each 0 in f:f = (a+b+c)(a+b+c’)(a+b’+c)f’ =(a+b’+c’)(a’+b+c)(a’+b+c’)(a’+b’+c)(a+b+c’)Mapping from one form to the other:Derive TT then proceed.Spring 2000 EECS150 Page 3Two-level Logic SimplicationKey tool: The Uniting Theorem x (y’ + y) = x (1) = xa b f f = ab’ + ab = a(b’+b) = a0 0 0 b values change within0 1 0 the on-set rows 1 0 1 a values don’t change1 1 1 b is eliminated, a remainsa b g g = a’b’+ab’ = (a’+a)b’ =b’0 0 1 b values stay the same0 1 0 a values changes1 0 11 1 0 b’ remains, a eliminatedSpring 2000 EECS150 Page 4Boolean CubesVisual technique for identifying when theUniting Theorem can be applied1-cube0 1x2-cube01 1100 10xy011 111110001000 100010101yxz3-cube• Sub-cubes of on nodes can be used forsimplification.– On-set - filled in nodes, off-set - empty nodesa b f g0 0 0 10 1 0 01 0 1 11 1 1 001 1100 10fbaa asserted & unchangedb varies ab + ab' = aSpring 2000 EECS150 Page 53-variable cube exampleFA carry out:a b c cout0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1011 111110001000 100010101bac(a' + a)bcab(c'+c)a(b+b')ccout = bc + ab + ac011 111110001000 100010101bacab’c’ + ab’c + abc’ + abc ac’ + ac + ab = a + ab = a• Both b & c change, a isasserted & remainsconstant.What about larger sub-cubes?Spring 2000 EECS150 Page 6Karnaugh Map Method• K-map is an alternative method ofrepresenting the TT and to help visual theadjacencies.0 101abcab00 01 11 1001abcd 00 01 11 10000111105 & 6 variable k-maps possibleg = b'0 101abcab00 01 11 10010 101abcab00 01 11 10010 10 1f = a0 0 1 00 1 1 1cout = ab + bc + ac1 10 00 0 1 10 0 1 1f = aExamples:Spring 2000 EECS150 Page 7K-maps (cont.)cab00 01 11 10011 0 0 10 0 1 1f = b'c' + acabcd 00 01 11 10000111101 0 0 10 1 0 01 1 1 11 1 1 1f = c + a'bd + b'd'(bigger groups are better)Circling Zerosabcd 00 01 11 10000111101 0 000 0111 1 1 11111f = (b' + c + d)(a' + c + d')(b + c + d')Spring 2000 EECS150 Page 8BCD incrementer examplea b c d w x y z0 0 0 0 0 0 0 10 0 0 1 0 0 1 00 0 1 0 0 0 1 10 0 1 1 0 1 0 00 1 0 0 0 1 0 10 1 0 1 0 1 1 00 1 1 0 0 1 1 10 1 1 1 1 0 0 01 0 0 0 1 0 0 11 0 0 1 0 0 0 01 0 1 0 - - - -1 0 1 1 - - - -1 1 0 0 - - - -1 1 0 1 - - - -1 1 1 0 - - - -1 1 1 1 - - - -00 01 110001111011abcd00 01 110001111011abcd00 01 110001111011abcd00 01 110001111011abcdw xy z0000 00000000000 00 000 0 0 00 011 11111 11 11 1 11 1--- ------ ---------------w = x =y = z =Spring 2000 EECS150 Page 9Higher Dimensional K-maps00 01 11 1000101110bcdea = 100 01 11 1000101110a = 000 01 11 1000101110cdefab = 1000 01 11 1000101110ab = 1100 01 11 1000101110ab = 0100 01 11 1000101110ab = 00Spring 2000 EECS150 Page 10Katz Chapter 3 - Multi-levelCombinational LogicŸ Example: reduced sum-of-products formx = adf + aef + bdf + bef + cdf + cef + gŸ implementation in 2-levels with gates:cost: 7-input OR, 6 3-input AND 50 transistors + 25 wires(19 linteral plus 6 internal)delay: 3-input AND gate delay + 7-input OR gate delayŸ Factored form:x = (a + b +c)(d + e)f + gcost: 1 3-input OR, 2 2-input OR, 1 3-input ANDdelay: 3-input OR + 3-input AND + 2-input ORWhich is faster?In general: Using multiple levels (more than 2) willreduce the cost. Sometimes also delay.Sometime a tradeoff between cost and delay.adfabcdefgxSpring 2000 EECS150 Page 11Multi-level Combinational LogicExample:F = abc + abd +a’c’d’ + b’c’d’let x = ab y = c+df = xy + x’y’Example: “result” output functions from 4-bitadder• No convenient hand methods for multi-levellogic simplication:1 CAD Tools, example misII (UCB)2 exploit some special structure, example adderabcabdacdbcdabcdfxySpring 2000 EECS150 Page 12NAND-NAND & NOR-NORNetworksDeMorgan’s Law:(a + b)’ = a’ b’ (a b)’ = a’ + b’ b + b = (a’ b’)’ (a b) = (a’ + b’)’push bubbles or introduce in pairs or remove pairs.Mapping from AND/OR to NAND/NAND= ===abcda)b)c) d)Spring 2000 EECS150 Page 13NAND-NAND & NOR-NORNetworks• Mapping AND/OR to NOR/NOR• Mapping OR/AND to NOR/NOR• OR/AND to NAND/NANDa) b)c)abcdabcdabcda) b)c)paira'b'c'd'Spring 2000 EECS150 Page 14Multi-level NetworksF = a(b + cd) + bc’Convert to NANDs (note fanout)cdbabc'fabcdSpring 2000 EECS150 Page 15EXOR FunctionParity, addition mod 2x y xor xnor0 0 0 1 x xor y = x’y + xy’0 1 1 01 0 1 01 1 0 1Another approach:x'yxy'xy01yxif x=0 then y else
View Full Document
Unlocking...