Report

Chapter 2 EGR 270 – Fundamentals of Computer Engineering 1 Reading Assignment: Chapter 2 in Logic and Computer Design Fundamentals, 4th Edition by Mano Simplification of Boolean functions There are 3 common methods: 1. Boolean algebra – The basis for all methods – Difficult to see the best path to take and to know when you are finished 2. Karnaugh maps – Fast and easy for 2 – 6 variables – Pictorial approach based on recognition of patterns – Difficult for large numbers of variables 3. Tabulation methods – Tedious to perform by hand, but well suited to computer implementation – No limit on the number of variables – Examples: Quine-McCluskey, Expresso-II by UC Berkeley – Discussed in online supplement (not covered in this course) Chapter 2 EGR 270 – Fundamentals of Computer Engineering 2 Karnaugh Maps (K-maps) • Essentially a 2D truth table arranged in a table or map so that adjacent cells in the map differ in only one bit position. • Each cell in the map corresponds to a minterm. • Combining 1’s in the Kmap into groups of 1, 2, 4, 8, etc. can yield a quick minimization of a Boolean function. • Kmaps are most commonly used for functions involving 2-6 variables. 2-variable K-maps The K-map has 22 = 4 cells. y MSB x 0 1 0 m m 0 2 1 m m 1 3 Example: Use a K-map to minimize the function f(x,y) = x’y + xy’ + xy EGR 270 – Fundamentals of Computer Engineering Chapter 2 3-variable K-maps The K-map has 23 = 8 cells. yz MSB x 0 1 00 m 0 m 4 01 m 1 m 5 11 m 3 m 7 10 m 2 m 6 Note the strange ordering Example: Use a K-map to minimize each function below. 1. yz 00 01 11 10 0 0 0 1 1 1 1 0 0 1 x Answer: f(x,y,z) = x’y + xz’ Group is x’y (x = 0 and y = 1) “Wraparound” group is xz’ (x = 1 and z = 0) 3 Chapter 2 EGR 270 – Fundamentals of Computer Engineering 2. f(x, y, z) = (0, 1, 5, 7) 3. f(x, y, z) = xyz + x’yz + x’y’z’ + y’z 4. f(a, b, c) = ab’ + ac + ab + b 4 Chapter 2 EGR 270 – Fundamentals of Computer Engineering 5 4-variable K-maps The K-map has 24 = 16 cells. CD A = MSB AB 00 01 11 10 00 m 01 m 11 m 10 m m m m m 0 m m 4 12 8 1 m m 5 13 9 3 m m Note the strange ordering 2 7 m 15 m 11 6 14 10 Example: Use a K-map to minimize each function below. 1. CD 2. CD 00 01 11 10 0 1 1 0 AB 00 01 0 0 0 1 11 0 0 0 10 1 1 1 AB 00 00 01 11 10 1 1 0 1 01 1 1 0 0 0 11 0 0 0 1 1 10 1 1 0 1 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Group size vs. number of literals: Note how the number of literals in a term is reduced by one each time the size of grouping is doubled. For the 4-variable K-map: Size of Grouping 1 2 4 8 6 Number of Literals 4 3 2 1 Example: Use a K-map to minimize each function below. 1. f(A, B, C, D) = A’B’C’ + A’CD + B’CD’ + ABD + AB’D + AB’C’D’ 2. f(A, B, C, D) = B’D’ + C’D + BD’ + A’D + BC Chapter 2 EGR 270 – Fundamentals of Computer Engineering Prime Implicants Prime Implicant – a product term which cannot be combined with other terms to yield a term with fewer literals. Hint: A prime implicant corresponds to a maximal grouping in a Kmap. Essential Prime Implicant – a prime implicant that covers at least one minterm of the function that is not covered by any other prime implicant. A good way to approach finding minimal expressions in Karnaugh maps is to find essential prime implicants first. Once those groups have been drawn on the map, it is easier to see what other groupings would most efficiently cover the rest of the minterms. In general, a function can be expressed as: F = sum of essential prime implicants + (some combination of non-essential prime implicants) Example: Identify all prime implicants and all essential prime implicants in f(A, B, C, D) = (0, 1, 3, 4, 5, 7, 11, 15) 7 EGR 270 – Fundamentals of Computer Engineering Chapter 2 Example: Use a K-map to minimize each function below. Identify the essential prime implicants in each problem. 1. CD 00 01 11 10 00 0 1 1 0 01 1 1 0 11 1 0 10 1 0 AB 2. CD 00 01 11 10 00 1 1 0 1 1 01 1 1 1 0 1 0 11 0 1 1 1 1 1 10 1 1 0 1 AB 8 Chapter 2 EGR 270 – Fundamentals of Computer Engineering 9 5-variable K-maps The K-map has 25 = 32 cells. Note odd arrangement of the variables ABCDE. This arrangement results in the left half of the K-map having the same minterm ordering as a 4-variable map. Note that groups combine as if the left map was over the top of the right map (like 3D chess). These two groups combine to form B’DE’ BC ADE 000 001 011 010 1 00 101 111 110 00 m0 m1 m3 m2 m16 m17 m19 m18 01 m4 m5 m7 m6 m20 m21 m23 m22 11 m12 m13 m15 m14 m28 m29 m31 m30 10 m8 m9 m11 m10 m24 m25 m27 m26 These two groups do NOT combine! Chapter 2 EGR 270 – Fundamentals of Computer Engineering 10 5-variable K-maps (alternate minterm ordering) Shown below is an alternate arrangement for the variables A, B, C, D and E. Note that changing the arrangement of the variables changes the ordering of the minterms. CDE AB 000 001 011 010 00 m0 m1 m3 m2 01 m8 m9 m11 m10 1 00 101 111 110 m4 m5 m7 m6 m12 m13 m15 m14 11 m24 m25 m27 m26 m28 m29 m31 m30 m16 m17 m19 m18 m20 m21 m23 m21 10 These 8 minterms combine to form AE’ (A = 1 and E = 0) Chapter 2 EGR 270 – Fundamentals of Computer Engineering Example: Use a K-map to minimize the function below. Carefully consider how to label A, B, C, D, and E on the K-map. F(A, B, C, D, E) = (1, 2, 5, 6, 8, 10, 12, 14, 17, 18, 21, 22, 24, 26, 28, 30) 000 001 011 010 00 01 11 10 1 00 101 111 110 11 EGR 270 – Fundamentals of Computer Engineering Chapter 2 12 SOP and POS Expressions from K-maps The examples so far have all generated minimal SOP expressions. POS expressions can be formed as follows: 1. Group 0’s in the K-map instead of 1’s (these groupings correspond to F’). 2. Find a minimal SOP expression for F’. 3. Find F from F’ by applying DeMorgan’s theorem. This yields a minimal POS expression. Example: Determine a POS expression for F(A, B, C, D) = (1 - 3, 6, 9 - 11). Draw the corresponding circuit. CD Solution : 00 01 11 10 0 1 1 1 F AB C D BD 01 0 0 0 1 F AB C D BD 11 0 0 0 0 F AB C D BD 10 0 1 1 1 AB 00 F A B C D B D With practice it is easy to go straight from the first to the last step. EGR 270 – Fundamentals of Computer Engineering Chapter 2 Example: Determine SOP and POS expressions for f(A, B, C, D) = (0, 2, 4-9, 13-15). Draw the corresponding circuits. CD AB 00 00 01 11 10 CD AB 00 01 01 11 11 10 10 00 01 11 10 13 EGR 270 – Fundamentals of Computer Engineering Chapter 2 14 Example: Determine SOP and POS expressions for f(A, B, C, D) = (0-2, 4-5, 8-10,14). Draw the corresponding circuits. CD AB 00 00 01 11 10 CD AB 00 01 01 11 11 10 10 00 01 11 10 Note: We cannot in general predict whether the minimal SOP expression or minimal POS expression will result in the fewest gates. It is often useful to check both expressions to see which gives the best result. Chapter 2 EGR 270 – Fundamentals of Computer Engineering “Don’t Care” conditions There are often unused input combinations or input combinations that are illegal and should never occur. In such cases, we often “don’t care” what the output is since the input should never occur anyway. We typically represent “don’t cares” in a K-map using either “d” or “X”. Rule: Include a “don’t care” in a grouping only if it helps to make for larger groupings. It is not necessary to include all “don’t cares” in groupings. Example: Find a minimal SOP expression for f(A, B, C, D) = (1, 8, 9 ) + d(0, 6, 10, 11). CD 00 01 11 10 X 1 0 0 01 0 0 0 X 11 0 0 0 0 10 1 1 X X AB 00 Solution: F = B’C’ (Note that AB’ and A’BCD’ are both unnecessary) 15 EGR 270 – Fundamentals of Computer Engineering Chapter 2 16 Example: BCD inputs are used to represent the digits 0 – 9, so the input codes corresponding to 10 – 15 are illegal inputs. Find both minimal SOP and POS expressions for f(A, B, C, D) = (0, 2-5, 7) + d(10-15). CD AB 00 01 11 10 00 01 11 10 EGR 270 – Fundamentals of Computer Engineering Chapter 2 17 Recognizing XOR and XNOR functions from K-maps First a review of the various ways to express the outputs of XOR and XNOR gates: x F x y x y xy y x y F x y x y x y x y x y x y Note: Diagonal or staggered groupings in K-maps often indicate that using XOR gates will yield a simpler solution than either SOP or POS form. Example: Minimize each function shown below. Make use of XOR gates as much as possible. Compare the number of gates using XOR’s to the number that would be required in SOP form. 1. yz x 2. 00 01 11 10 yz x 00 01 11 10 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 EGR 270 – Fundamentals of Computer Engineering Chapter 2 18 Example: Minimize each function shown below. Make use of XOR gates as much as possible. Compare the number of gates using XOR’s to the number that would be required in SOP form. 3. CD AB 00 01 11 10 4. CD AB 00 01 11 10 5. CD AB 00 01 11 10 00 1 0 1 0 00 0 0 1 1 00 0 0 0 1 01 0 1 0 1 01 1 1 0 0 01 0 0 1 0 11 1 0 1 0 11 0 0 1 1 11 0 1 0 0 10 0 1 0 1 10 1 1 0 0 10 1 0 0 0 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Cost Criteria We need some sort of measure that will indicate how efficiently logic expressions can be implemented. Different methods include: 1) Literal cost 2) Number of logic gates 3) Gate input cost 4) Number of gate delays Literal cost – defined earlier as the number of literal appearances in a logic expression. A literal is any complemented or uncomplemented variable. Example: F = AB + A’B’ + AC has 6 literals 19 Chapter 2 EGR 270 – Fundamentals of Computer Engineering 20 Propagation delay – the amount of time for the output of a gate to respond to a change in the input. Example: tp = 10 ns Number of gate delays – The number of gate delays for the longest path through a logic circuit. For example, in the logic diagram below: • If D changes, there is only 1 gate delay before F responds • If C changes, there are 2 gate delays before F responds • If A or B change, there are 3 gate delays before F responds (the path for signal A is highlighted in green) • So the number of gate delays (longest path) = 3 A B C F D Chapter 2 EGR 270 – Fundamentals of Computer Engineering 21 Gate Input Cost Gate input cost is simply the number of inputs to all gates if the implementation corresponds exactly to the expression given. Note that input inverters are typically not counted as inputs are often available in complemented or uncomplemented form. Example: Find the gate input cost for the circuit below. It is easy! Just count the inputs (numbered 1-6 below) A 1 B 2 Gate input cost = 6 3 C 4 5 F D 6 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Example: Evaluate each expression using various cost criteria. F = ABCD + A’B’C’D’ Literal cost: __________ Number of gates: _______ Gate input cost: __________ Number of gate delays: __________ F = (A’+B)(B’+C)(C’+D)(D’+A) Literal cost: __________ Number of gates: _______ Gate input cost: __________ Number of gate delays: __________ 22 Which method is best? Gate input cost is considered to be a better measure than literal cost of the number of logic gates. Gate input cost is a good measure for contemporary logic implementations since it is proportional to the number of transistors and wires used in implementing a logic circuit. However, the number of gate delays is also important as it relates to the speed of the circuit. There is often a tradeoff between these two. Gate input cost (area or size of the circuit) tradeoff Number of gate delays (speed of the circuit) Chapter 2 EGR 270 – Fundamentals of Computer Engineering Multiple-Level Circuit Optimization Recall that SOP and POS expressions are both two-level circuit implementations. Although these implementations may result in the shortest propagation delay, other implementations may have lower gate input cost. Example: (Refer to Figure 2-26 from the text shown below) G = ABC + ABD + E + ACF + ADF see Fig a below. Gate input cost = ______ G = AB(C+D) + E + AF(C+D) see Fig b below. Gate input cost = ______ G = (AB+AF)(C+D) + E see Fig c below. Gate input cost = ______ G = A(B+F)(C+D) + E see Fig d below. Gate input cost = ______ 23 Chapter 2 EGR 270 – Fundamentals of Computer Engineering 24 Transformations for Multiple-Level Circuit Optimization As seen in the last example, the circuit cost can sometimes be reduced through algebraic manipulation (or transformations). As with Boolean algebra, there are no specific rules for these transformations, but five types of transformations can be defined as follows: 1) Factoring – finding a factored form of a SOP or POS expression 2) Decomposition – expression of a function as a set of new functions 3) Extraction – expression of multiple functions as a set of new functions (decomposing multiple functions to extract common subexpressions) 4) Substitution – substituting function G into function F is when F is expressed as a function of G and some or all of the original variables of F 5) Elimination – the inverse of substitution in which function G in an expression for function F is replaced by the expression for G. Elimination is also called flattening or collapsing. Chapter 2 EGR 270 – Fundamentals of Computer Engineering Example - Factoring Reduce circuit cost through factoring for the function G below: G = AC’E + AC’F + AD’E + AD’F + BCDE’F’ Original expression Gate input cost: ________ Number of gate delays: ________ Factored expression Gate input cost: ________ Number of gate delays: ________ 25 26 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Example - Decomposition Function G was factored in the previous example as follows: G = AC’E + AC’F + AD’E + AD’F + BCDE’F’ G = A(C’+D’)(E+F) + BCDE’F’ Now introduce two new functions, X1 and X2 (note their complements): X1 = CD X2 = E + F Next rewrite G in terms of X1 and X2 (i.e., decompose G in terms of X1 and X2). Draw the circuit also. G= Original expression Gate input cost: ________ Number of gate delays: ________ Factored expression Gate input cost: ________ Number of gate delays: ________ Note: Decomposition is more useful Decomposed expression when there are two or more outputs Gate input cost: ________ that may share gates or functions (as Number of gate delays: ________ in the next example) 27 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Example - Extraction Extraction is the process of decomposing multiple expressions to extract common subexpressions. First consider the original expressions for functions G and H: G = AC’E + AC’F + AD’E + AD’F + BCDE’F’ H = A’BCD + ABE + ABF + BCE + BCF (expression in the text is incorrect) Next factor the functions as follows: G = A(C’+D’)(E+F) + BCDE’F’ H = B(A’CD + (A+C)(E+F)) Now introduce three new functions, X1, X2 and X3 as follows: X1 = CD X2 = E + F X3 = A + C Next extract X1, X2 and X3 from G and H: (see circuits on the following two pages) G= H= Original expressions for G and H Gate input cost: ________ Expressions for G and H with X1, X2 and X3 extracted Gate input cost: ________ Chapter 2 EGR 270 – Fundamentals of Computer Engineering Original expressions for functions G and H (label the output of each gate): G = AC’E + AC’F + AD’E + AD’F + BCDE’F’ H = A’BCD + ABE + ABF + BCE + BCF Original expressions for G and H Gate input cost: ________ Number of gate delays: ________ 28 Chapter 2 EGR 270 – Fundamentals of Computer Engineering Reduced expressions for G and H using extraction (label the output of each gate): X1 = CD X2 = E + F X3 = A + C G = AX1’X2 + BX1X2’ H = B(A’X1 + X3X2) = BA’X1 + BX3X2 Reduced expressions for G and H Gate input cost: ________ Number of gate delays: ________ End of Test #1 material 29