Chapter 2 - Part 4 - PPT - Mano & Kime - 2nd Ed

SYEN 3330 Digital Systems Chapter 2 Part 4 SYEN 3330 Digital Systems Jung H. Kim Chapter 2-4 1 Standard Forms Standard Sum-of-Products (SOP) form: equations are written as "AND" terms summed with "OR" operators. Standard Product-of-Sums (POS) form: equations are written as "OR" terms, all "ANDed" together. Examples: SOP: A B C+AB C + B POS: (A + B) (A+B +C) (C) These "Mixed" forms are not SOP or POS Wrong: (A B + C) (A + C) or A BC +A C (A + B) SYEN 3330 Digital Systems Chapter 2-4 2 Standard Sum-of-Products (SOP) A Sum of Minterms form for n variables can be written

down directly from a truth table. Implementation of this form is a two-level network of gates such that: The first level consists of n-input AND gates, and The second level is a single OR gate (with fewer n than 2 inputs). This form: is usually not a minimum literal expression, and leads to a more expensive implementation (in terms of two levels of AND and OR gates) than needed. SYEN 3330 Digital Systems Chapter 2-4 3 Standard Sum-of-Products (SOP) T h e r e f o r e , w e lite r a l c o s t e x p im p le m e n ta tio E x a m p l e : F ( A S im p lif y in g F = A B C = A B (C + A B = A B + = A B +

= A (B + = A + B tr y to c o m b in e te r m s to g e t a lo w e r r e s s io n , le a d in g to a le s s e x p e n s iv e n . Note term A B C , B , C ) (1 ,4 ,5 ,6 ,7 ) A B C + A C ) + A B + A B C A B (C + C ) A B + B C B ) + B C C + + C SYEN 3330 Digital Systems duplicated B C + A B C + A B C The Canonical SumC + A B C of-Minterms form has (5 * 3) = 15

+ (A + A ) B C literals and 5 terms. The reduced SOP form has 3 literals and 2 terms. Chapter 2-4 4 AND/OR Two-level Implementation of SOP Expression The two implementations for F are shown below: (Which is simpler?) A F B C SYEN 3330 Digital Systems Chapter 2-4 5 Standard Product-of-Sums (POS) A Product of Maxterms form for n variables can be

written down directly from a truth table. Implementation of this form is a two-level network of gates such that: The first level consists of n-input OR gates, and The second level is a single AND gate (with fewer than 2n inputs). This form: is usually not a minimum literal expression, and leads to a more expensive implementation (in terms of two levels of AND and OR gates) than needed. SYEN 3330 Digital Systems Chapter 2-4 6 Standard Product-of-Sums (POS) We can use Boolean algebra to minimize the literal cost of an expression for POS forms. Example: F ( 0, 2 , 3) Becomes: (Note duplicate term)

SYEN 3330 Digital Systems F= F= = = = (A+B+C)(A+B'+C)(A+B'+C') (A+C+B)(A+C+B')(A+B'+C)(A+B'+C') ((A+C)+BB')((A+B')+CC') ((A+C)+0)((A+B')+0) (A+C)(A+B') Chapter 2-4 7 Standard Product-of-Sums (POS) Therefore, we try to combine terms to get a lower literal cost expression, leading to a less expensive implementation. Note term A B C Example: F ( 0 , 2 , 3 ) duplicated Simplifying

F= F= = = = (A + B + C)(A +B + C)(A +B +C) (A + C + B)(A + C +B)(A+B + C)(A +B +C) ((A + C) + BB)((A +B) + CC) The Canonical Product((A + C) + 0)((A +B) + 0) of-Maxterms form had (3 (A + C)(A +B) * 3) = 9 literals and 3 terms. The reduced POS form had 4 literals and 2 SYEN 3330 Digital Systems Chapter 2-4 8 terms. OR/AND Two-level Implementation The two implementations for F are shown below: (Which is simpler?) SYEN 3330 Digital Systems Chapter 2-4

9 SOP and POS Observations The previous examples show several things: Canonical Forms (Sum-of-minterms, Product-ofMaxterms), or other standard forms (SOP, POS) can differ in literal cost. Boolean algebra can be used to manipulate equations into simpler forms. Simpler equations lead to simpler two-level implementations Questions: How can we attain a minimum literal expression? Is there only one minimum cost circuit? SYEN 3330 Digital Systems Chapter 2-4 10 Equivalent Cost Circuits Given: F( A, B, C) ( 0, 2, 3,4,5,7 ) F = A'B'C'+A'BC'+A'BC+AB'C' +AB'C+ ABC = A'C'B'+A'C'B+AB'C+AB'C' +A'BC+ ABC = A'C'(B+B')+AB'(C+C')+(A+A')BC

= A'C' + AB' + BC By pairing terms differently at the start: F = AB'C+ ABC+A'BC'+A'BC +AB'C'+A'B'C' We arrive at: F = AC + A'B + B'C' BOTH HAVE THE SAME LITERALS COUNTS AND NUMBER OF TERMS !! SYEN 3330 Digital Systems Chapter 2-4 11 Boolean Function Simplification Reducing the literal cost of a Boolean Expression leads to simpler networks. Simpler networks are less expensive to implement. Boolean Algebra can help us minimize literal cost. When do we stop trying to reduce the cost? Do we know when we have a minimum? We will introduce a systematic way to arrive a a minimum cost, two-level POS or SOP network. SYEN 3330 Digital Systems Chapter 2-4 12

Karnaugh Maps (K-map) Diagram is a collection of squares Each square represents a minterm Collection of squares is a graphical representation of the Boolean function Adjacent squares differ in one variable Pattern recognition is used to derive alternative algebraic expressions for the same function The Karnaugh Map can be viewed as an extension of the truth table The Karnaugh Map can be viewed as a topologically warped Venn diagram as used to visualize sets SYEN 3330 Digital Systems Chapter 2-4 13 Uses of Karnaugh Maps Provide a means for finding optimum: Simple SOP and POS standard forms, and Small two-level AND/OR and OR/AND circuits Visualize concepts related to manipulating Boolean expressions Demonstrate concepts used by computeraided design programs to simplify large

circuits SYEN 3330 Digital Systems Chapter 2-4 14 Two Variable Maps A Two variable Karnaugh Map: Note that minterm m0 and minterm m1 are "adjacent" and differ in the value of the variable y. Similarly, minterm m0 and minterm m2 differ in the x variable. Note that m1 and m3 differ in the x variable as well. Minterms m2 and m3 differ in the value of the variable y SYEN 3330 Digital Systems y=0 y=1 x=0 m0 = m1 = x y x y

x=1 m2 m3 =x y =xy Chapter 2-4 15 K-Map and Function Tables The K-Map is just a different form of the function table. For two variables, both are shown below. We choose a,b,c and d from the set {0,1} to implement a particular function, F(x,y). Function Table Input Values (x,y) Function Value F(x,y) 00 01 10 11

a b c d SYEN 3330 Digital Systems K-Map x=0 x=1 y=0 a c y=1 b d Chapter 2-4 16 K-Map Function Representations Examples F(x,y) = x F=x y=0 y=1

G(x,y) = x+y G=x+y y=0 y=1 x=0 0 0 x=0 0 1 x=1 1 1 x=1 1 1

For function F(x,y), the two adjacent cells containing 1s can be combined using the Minimization Theorem: F ( x , y ) x y x y x For G(x,y), two pairs of adjacent cells containing 1s can be combined using the Minimization Theorem: G( x, y ) x y x y xy x y x y SYEN 3330 Digital Systems Duplicate x y Chapter 2-4 17 Three Variable Maps A three variable Karnaugh Map is shown below: yz=00 yz=01 yz=11 yz=10 x=0 m0 m1 m3

m2 x=1 m4 m5 m7 m6 Where each minterm corresponds to the product terms below: yz=00 yz=01 yz=11 yz=10 x=0 xyz xy z x y z x yz x=1 xyz xyz x yz

xy z Note that if the binary value for an index differs in one bit position, the minterms are adjacent on the Karnaugh Map SYEN 3330 Digital Systems Chapter 2-4 18 Example Functions By convention, we represent the minterms by a "1" in the map and leave the other terms blank. A function table would also show the "0" terms. yz=00 yz=01 yz=11 yz=10 Example: m(2,3,4,5) x=0 x=1 1 1 1 1

yz=00 yz=01 yz=11 yz=10 Example: m(3,4,6,7) SYEN 3330 Digital Systems x=0 x=1 1 1 1 1 Chapter 2-4 19 Combining Squares By combining squares, we reduce the representation for a term, reducing the number of literals in the Boolean equation. On a three-variable K-Map: One square represents a minterm with three variables Two adjacent squares represent a product term with two variables

Four adjacent terms represent a product term with one variable Eight adjacent terms is the function of all ones (no variables) = 1. SYEN 3330 Digital Systems Chapter 2-4 20 Combining Squares Example Example: Let F = m(2,3,6,7) F yz=00 yz=01 yz=11 yz=10 x=0 1 1

x=1 1 1 Applying the Minimization Theorem three times: F( x , y , z ) x y z x y z x y z x y z yz yz y Thus the four terms that form a 2 2 square correspond to the term "y". SYEN 3330 Digital Systems Chapter 2-4 21 Alternate K-Map Diagram There are many ways to draw a three variable K-Map. Three common ways are shown below: y m0 m1 m3 m2 x m4 m5 m7 m6 z x

x yz 00 01 11 10 0 m0 m1 m3 m2 1m m m m 4 5 7 6 y yz 00 01 11 10 0 m0 m1 m3 m2 x 1m m m m 4 5 7 6 SYEN 3330 Digital Systems

Chapter 2-4 z 22

Recently Viewed Presentations

• ECO290E: Game Theory Lecture 1 Introduction and Motivation What is Game Theory? Game theory is a field of Mathematics, analyzing strategically inter-dependent situations in which the outcome of your actions depends also on the actions of others.
• 3.4 Marginal Functions in Economics Marginal Analysis Marginal analysis is the study of the rate of change of economic quantities. An economist is not merely concerned with the value of an economy's gross domestic product (GDP) at a given time...
• an mxn matrix is mxn. The plural of matrix is matrices. A square matrix . is a matrix with the same number of rows and columns. Example 1. The matrix is a . 3 x 2 matrix. A matrix with...
• Decline in Geography candidates at GCSE 2000-2006 Now 8th most popular subject at GCSE in England and Wales (though 5th in Wales itself) Decline in A level Geography Candidates 1989 - 2006 The 9th most popular at A2 But it...
• [fig 6.8] Phylum Annelida- Class Oligochaeta: close-up of intestine w/ typhlosole. [fig 6.8] Phylum Annelida- Class Oligochaeta: note longitudinal & circular muscles, nephridium, and the coelom. [fig 6.8] Phylum Annelida- Class Oligochaeta. Earthworm dissection[fig 6.7] View of both preserved organism...
• ยง3.3.1 Sturm-Liouville theorem: orthogonal eigenfunctions Christopher Crawford PHY 416 2014-10-27 Outline Review of eigenvalue problem Linear function spaces: Sturm-Liouville theorem Review of rectangular BVP in term of vectors / eigenstuff Separation of Cartesian variables: Plane waves: exponentials * ` `...
• "A student who successfully completes all these math courses will be fully prepared to enrol in Advanced Functions (MHF 4U0) in his/her 4. th. year at SLSS." "MFM 1H0 is a two week transition course in math. This transition does...
• What is the word that names a shape with ten sides and ten angles? decagon. a polygon with ten sides and ten angles. What is the word that names the contest athletes compete in which requires skill and training in...