Canonical or Standard Forms of Functions
-SOP (Sum of Products) form
-POS (Product of Sums) form
-Relationship Between MinTerms and MaxTerms
-Converting Between Compact Forms of Functions
Minimizing (Reducing) Functions
-Karnaugh Maps (K-maps)
-Product term sharing

注脚

展开查看详情

1.Lecture 5 Topics Canonical or Standard Forms of Functions SOP (Sum of Products) form POS (Product of Sums) form Relationship Between MinTerms and MaxTerms Converting Between Compact Forms of Functions Minimizing (Reducing) Functions Karnaugh Maps (K-maps) Product term sharing 1

2.Boolean Equations

3.Obtaining a Boolean Equation In Ecotopia it’s generally illegal to use a car pool lane during weekdays if the car doesn’t have at least two occupants. However, hybrid vehicles can use the lanes any time regardless of the number of occupants. SUVs (even with two or more occupants) are never allowed to use the car pool lanes (unless they are also hybrids). Write a Boolean expression in SOP form for F(W, O, S, H) which is 1 if the car is permitted to use the car pool lane today. W is 1 if today is a weekday. O is 1 if there are two or more occupants, S is 1 if the vehicle is an SUV, H is 1 if the vehicle is a hybrid. W O S H F ---------- 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 ECOTOPIA EXAMPLE

4.Another Example: Deriving Boolean Equations A truth table is a complete, unambiguous definition of a Boolean function… But how do we get a Boolean expression from a truth table? SOP or POS X Y Z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 F = X × Y × Z + X × Y × Z + X × Y × Z 4

5.F(A,B) = F(0,0) × A × B + F(0,1) × A × B + F(1,0) × A × B + F(1,1) × A × B = 0 × A × B + 1 × A × B + 1 × A × B + 1 × A × B = 0 + A × B + A × B + A × B = A × B + A × B + A × B Another Example: Obtaining SOP Forms of Functions OR truth table A B F(A,B) 0 0 0 = F(0,0) 0 1 1 = F(0,1) 1 0 1 = F(1,0) 1 1 1 = F(1,1) Reduced Form Canonical or Standard SOP Form Standard Product Term (Minterm) A + B 5

6.Minterms and Maxterms

7.Minterms 7

8.F(A,B) = F(0,0) × A × B + F(0,1) × A × B + F(1,0) × A × B + F(1,1) × A × B = S 3 i=0 (F i × m i ) = 0 × m 0 + 1 × m 1 + 1 × m 2 + 1 × m 3 = m 1 + m 2 + m 3 = S m(1,2,3) = S (1,2,3) Compact Minterm Form OR truth table A B F(A,B) 0 0 0 = F(0,0) 0 1 1 = F(0,1) 1 0 1 = F(1,0) 1 1 1 = F(1,1) 8

9.Minterms S (3,5,6,7) 9

10.Generalized Compact Minterm Form F(X 1 , X 2 ,… X n ) = S ( minterms for 1s of the function) F(X 1 , X 2 ,… X n ) = S (minterms for 0s of the function) 10 Pay attention, this is negation of function F

11.F(A,B) = (F(0,0) + A + B) × ( F(0,1) + A + B) × (F(1,0) + A + B) × (F(1,1) + A + B) = (0 + A + B) × (0 + A + B) × (0 + A + B) × (1 + A + B) = (A + B) × (A + B) × (A + B) × (1) = (A + B) × (A + B) × (A + B) Obtaining POS Forms of Functions AND truth table A B F(A,B) 0 0 0 = F(0,0) 0 1 0 = F(0,1) 1 0 0 = F(1,0) 1 1 1 = F(1,1) Standard Sum Term (Maxterm) Canonical or Standard POS Form Reduced Form A × B 11

12.Maxterms 12

13.F(A,B) = (F(0,0) + A + B ) × ( F(0,1) + A + B ) × (F(1,0) + A + B ) × (F(1,1) + A + B ) = P 3 i=0 ( F i + M i ) = (0 + M 0 ) × (0 + M 1 ) × (0 + M 2 ) × (1 + M 3 ) = M 0 × M 1 × M 2 = P M(0,1,2) = P (0,1,2) Compact Maxterm Form AND truth table A B F(A,B) 0 0 0 = F(0,0) 0 1 0 = F(0,1) 1 0 0 = F(1,0) 1 1 1 = F(1,1) 13

14.Maxterms P (0,1,2,4) 14

15.Generalized Compact Maxterm Form F(X 1 , X 2 ,… X n ) = P ( maxterms for 0s of the function) F(X 1 , X 2 ,… X n ) = P ( maxterms for 1s of the function) 15 Canonical SOP Canonical POS negation

16.Relationship Between Minterms and Maxterms m i = M i , M i = m i S = P , P = S 16

17.Canonical SOP and POS forms using minterms and maxterms

18.An example : Given the accompanying truth table, write the compact minterm form for F for its 1s and 0s. Write the standard SOP form for each . X Y Z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 F = S (3,4,6) Compact minterm form 1s : Compact minterm form 0s : Corresponding SOP form: Corresponding SOP form: F = X × Y × Z + X × Y × Z + X × Y × Z F = S (0,1,2,5,7) F = X × Y × Z + X × Y × Z + X × Y × Z + X × Y × Z + X × Y × Z 18 This is example problem 15, page 85. Solution on page 107.

19.An example: Given the accompanying truth table, write the compact maxterm form for F for its 1s and 0s. Write the standard POS form for each. X Y Z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 Compact maxterm form 1s: Compact maxterm form 0s: Corresponding POS form: Corresponding POS form: F = P (0,1,2,5,7) F = P (3,4,6) F = (X + Y + Z) × (X + Y + Z) × (X + Y + Z) F = (X + Y + Z) × (X + Y + Z) × (X + Y + Z) × (X + Y + Z) × (X + Y + Z) 19 This uses the same truthtable as the preceding problem but asks for maxterms

20.Function Minimization : Reduce Number of Literals and Terms Simplify for Comprehension Reduce Number of Components Reduce Amount of Wiring/Routing Smaller Circuit/Board Area Lower Cost Higher Reliability 20

21.Function Minimization: Reduce Number of Literals and Terms Apply Boolean Algebra Employ Computer Algorithm Quine-McCluskey tabular algorithm Boozer McBoole Espresso and Espresso/Exact (CAD packages) Systematic Algebraic Reduction (SAR) Karnaugh Maps (K-Maps) 21

22.Karnaugh Maps

23.Karnaugh (K) Maps A graphical representation of Boolean function Easy to perform functional reduction Relies on adjacency (Gray code) of minterms Adjacent (horizontal/vertical & wrap around) cells differ in only one variable (complement) Number form and Variable form 23

24.K-Maps 2 Variable K-Map (Number Form) Gray code! Minterm numbers 24

25.K-Maps 3 Variable K-Map (Number Form) Gray code! Minterm numbers 25

26.K-Maps 4 Variable K-Map (Number Form) Gray code! Minterm numbers 26

27.K-Maps 2 Variable K-Map (Variable Form) May be more useful if plotting partially reduced functions Careful! Preserve Gray code! 27

28.K-Maps 3 Variable K-Map (Variable Form) 28

29.K-Maps 4 Variable K-Map (Variable Form) 29

30.My Preference… W W X Z Y Y 30

31.Plotting Functions in K-Maps Plot the function F1(X,Y,Z) = S (2,5,6,7) X Y Z F1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 31

32.Plotting Functions in K-Maps Plot the function F2(A,B,C,D) = S (6,7,8,14,15) Plot 0s! 32

33.Don’t Care Outputs

34.Don’t Care Outputs Output of Function Doesn’t Matter Typically impossible input condition Use X instead of 0 or 1 BCD A B C D Prime 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 X 1 0 1 1 X 1 1 0 0 X 1 1 0 1 X 1 1 1 0 X 1 1 1 1 X 0 1 2 3 4 5 6 7 8 9 . . . . . . 34

35.Don’t Care Outputs Compact Minterm and Maxterm Form F3(A,B,C) = S (2,6) + S md (3,5,7) F3(A,B,C) = S (0,1,4) + S md (3,5,7) F3(A,B,C) = P (0,1,4) × P Md (3,5,7) F3(A,B,C) = P (2,6) × P Md (3,5,7) A B C F3 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 X 1 0 0 0 1 0 1 X 1 1 0 1 1 1 1 X 35

36.Plotting K-Maps with Xs A B C F3 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 X 1 0 0 0 1 0 1 X 1 1 0 1 1 1 1 X F3(A,B,C) = S (2,6) + S md (3,5,7) 36

37.Plotting K-Maps from functions in partially reduced form F4(A,B,C,D) = A × B × C × D + B × C × D + A × B + C p 1 p 2 p 3 p 4 37 This is Sum of Products of literals, called SOP

38.Plotting K-Maps from functions in partially reduced form F4(A,B,C,D) = A × B × C × D + A × B × C × D + A × B × C r 1 r 2 r 3 38

39.K-Maps for functions of 5 variables F(V,W,X,Y,Z) m 0 through m 15 m 16 through m 31 39

40.K-Maps for functions of 5 variables F(V,W,X,Y,Z) = S (3,7,9,11,12,15,16,19,23,24,27,28,31) + S md (4,18,20,26,30) 40

41.Another type of K-Maps for functions of 5 variables 41 0 00 0 01 0 11 0 10 1 10 1 11 1 01 1 00 00 01 11 10 a,b c,d,e Axis of symmetry (of mirror for d and e)

42.Another type of K-Maps for functions of 6 variables 42 0 00 0 01 0 11 0 10 1 10 1 11 1 01 1 00 0 00 0 01 0 11 0 10 a,b,c d,e,f 1 10 1 11 1 01 1 00

43.Using K-Maps to Reduce Functions

44.Using K-Maps to Reduce Functions Assume you’ve plotted the K-map for F(X,Y,Z) as follows: 44

45.Using K-Maps to Reduce Functions You want to obtain a reduced expression for F(X,Y,Z) in SOP form 45

46.Using K-Maps to Reduce Functions Need to “cover” 1s Fewest product terms Simplest expressions (fewest variables) You want to obtain a reduced expression for F(X,Y,Z) in SOP form 46

47.Using K-Maps to Reduce Functions Circle all isolated 0-cubes Circle all 1-cubes not completely contained in a larger cube Continue for 2, 3, 4-cubes Write the product terms (prime implicants) and OR them together Write the expression for each product term 47

48.Using K-Maps to Reduce Function F in SOP form F(X,Y,Z) = p1 + p2 + p3 = X × Z + X × Z + Y 48

49.Using K-Maps to Reduce Functions F(X,Y,Z) = r1 + r2 = X × Y × Z + X × Y × Z 49

50.K-Maps (Some Terminology) Implicant : Product term of a function Prime Implicant : Product term for a cube which is not completely contained in another cube Essential Prime Implicant : Product term which provides the only covering for a given minterm and must always be used in the set of product term Optional Prime Implicant : Product term which provides an alternative covering for a given minterm and may be used in the set of product terms Redundant (Non-Essential) Prime Implicant : Product term for a cube which is completely contained in another cube (correct, but won’t lead to a minimum function) 50

51.K-Map with only essential prime implicants 51

52.K-Map with no essential prime implicants 52

53.K-Map with no essential prime implicants 53

54.K-Map with no essential prime implicants: alternative! 54

55.Covering Order is Essential 55

56.Using K-Maps to Reduce Functions Given the following K-map, which minimum SOP form of the function has the smallest literal count (the one for the 1s or the 0s)? F(W,X,Y,Z) = F(W,X,Y,Z) = 56

57.Using K-Maps to Reduce Functions F(W,X,Y,Z) = p1 + p2 + p3 = X × Z + W × Z + W × Y lc = 6 57

58.Using K-Maps to Reduce Functions F(W,X,Y,Z) = r1 + r2 + r3 = W × X × Y + W × Z + Y × Z lc = 7 58 This is POS form

59.Using K-Maps to Reduce Functions Given the following K-map, which minimum SOP form of the function has the smallest literal count (the one for the 1s or the 0s)? lc = 6 lc = 7 F(W,X,Y,Z) = r1 + r2 + r3 = W × X × Y + W × Z + Y × Z F(W,X,Y,Z) = p1 + p2 + p3 = X × Z + W × Z + W × Y 59

60.Using K-Maps to Reduce Functions Given the following K-map, which minimum SOP form of the function has the smallest literal count (the one for the 1s or the 0s)? F(W,X,Y,Z) = F(W,X,Y,Z) = Only use don’t cares to allow larger cube sizes to be covered 60

61.Using K-Maps to Reduce Functions Only use don’t cares to allow larger cube sizes to be covered F(W,X,Y,Z) = p1+p2+p3+p4 = X × Y × Z + W × X × Y + W ×Z + Y × Z lc = 10 61

62.Using K-Maps to Reduce Functions Only use don’t cares to allow larger cube sizes to be covered F(W,X,Y,Z) = r1 + r2 + r3 = W × Y × Z+ X × Z + W × Y lc = 7 62

63.K-Maps for functions of 5 variables F(V,W,X,Y,Z) = S (3,7,9,11,12,15,16,19,23,24,27,28,31) + S md (4,18,20,26,30) 63

64.Parallel Adder Design

65.Let us remind the Unsigned Binary (UB) Addition Examples (4-bit word) 1011 0110 + 1 1 1 10001 0010 0110 + 1 1 1000 Overflow 2 + 6 2 + 6 8 11 + 6 17 11 + 6 17 > 2 4 -1 65

66.The parallel Ripple Carry Adder is built from Full Adders Consider a circuit to add two 4-bit numbers: A3 A2 A1 A0 + B3 B2 B1 B0 CO4 S3 S2 S1 S0 Truth table would have 8 inputs (2 8 = 256 rows) and 5 outputs, requiring 5 minimized functions (5 8-variable K-maps). But operation at each bit position (after A0/B0) is identical: CO i A i + B i CO i+1 S i “bit slice” 66 We iterate the Full Adder several times

67.Full Adder Truth Table CI A B CO S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 67

68.Parallel Adder Design (Iterative Circuit) S 0 S 1 S 2 S 3 A 0 A 1 B 0 C 0 A 3 B 3 C 3 A 2 B 2 C 2 B 1 C 1 C 4 The same full adder repeated 4 times in an iterative circuit. This one is called Ripple Carry Adder Least significant bits are here Most significant bits are here

69.Ripple Carry Adder A1 A0 + B1 B0 CO2 S1 S0 69 Least significant bits are here Most significant bits are here This is Ripple Carry Adder for two bits. Adds numbers with two bits each. The Ripple Carry Adder below is for four bits. Adds numbers A and B with four bits each.

70.Subtractor Design This can be a problem in final exam. Based on your knowledge of negative numbers in two-complement, design a parallel subtractor similar to the parallel adder from last slides. Combine the design of the above subtractor and the parallel adder to a single circuit with control signal X that controls subtraction or addition of two numbers, A and B. If X=0 the circuit should add A and B. If X=1 the circuit should do the subtraction A-B. Repeat the above problems for sign-magnitude systems. Repeat the above problems for one’s-complement system.

71.ECOTOPIA REVISITED In Ecotopia it’s generally illegal to use a car pool lane during weekdays if the car doesn’t have at least two occupants. However, hybrid vehicles can use the lanes any time regardless of the number of occupants . SUVs (even with two or more occupants) are never allowed to use the car pool lanes (unless they are also hybrids). Write a Boolean expression in SOP form for F(W, O, S, H) which is 1 if the car is permitted to use the car pool lane today. W is 1 if today is a weekday. O is 1 if there are two or more occupants, S is 1 if the vehicle is an SUV, H is 1 if the vehicle is a hybrid. W O S H F ---------- 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 “1” if car is permitted to use pool today W is 1 if today is a weekday. O is 1 if there are two or more occupants S is 1 if the vehicle is an SUV, H is 1 if the vehicle is a hybrid

72.ECOTOPIA REVISITED “1” if car is permitted to use pool today W is 1 if today is a weekday. O is 1 if there are two or more occupants S is 1 if the vehicle is an SUV, H is 1 if the vehicle is a hybrid Car is permitted to use pool if it is a hybrid or it is not a hybrid and it is not a weekday or it is not a hybrid and there are more than two occupants

73.Circuits with Multiple Outputs Product Term Sharing

74.Circuits with Multiple Outputs Product Term Sharing 74 x 1 x 2 x 3 x 4 f 1 f 2 This is SOP

75.Product Term Sharing 75 May Result in K-Maps Different from Optimizing Separate Functions

76.BR 2/1/99 76 Look for Shared Terms AB 01 0 0 0 0 00 CD 00 0 0 0 0 01 11 10 1 0 1 0 1 1 1 0 11 10 F1 =  m(11,12,13,14,15) = AB + ACD AB 01 0 0 0 0 00 00 1 1 0 0 01 11 10 1 0 1 0 1 1 0 0 11 10 F2=  m(3,7,11,12,13,15) = A’CD + ABC’ + ACD AB 01 0 0 0 0 00 CD 00 1 1 0 0 01 11 10 1 0 1 0 1 0 1 0 11 10 F3=  m(3,7,12,13,14,15) = A’CD + AB Minimize separately

77.BR 2/1/99 77 Implementation with Shared Terms A B A C D A B C’ A’ C D F1 = AB + ACD F2= A’CD + ABC’ + ACD F3= A’CD + AB

78.BR 2/1/99 77 Implementation with Shared Terms A B A C D A B C’ A’ C D F1 = AB + ACD F2= A’CD + ABC’ + ACD F3= A’CD + AB

79.BR 2/1/99 77 Implementation with Shared Terms A B A C D A B C’ A’ C D F1 = AB + ACD F2= A’CD + ABC’ + ACD F3= A’CD + AB

80.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 80 two alternative implementations of EQ with and without XOR XNOR is implemented with at least 3 simple gates A B C D EQ EQ Design example: two-bit comparator (cont’d)

81.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 80 two alternative implementations of EQ with and without XOR XNOR is implemented with at least 3 simple gates A B C D EQ EQ Design example: two-bit comparator (cont’d)

82.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 80 two alternative implementations of EQ with and without XOR XNOR is implemented with at least 3 simple gates A B C D EQ EQ Design example: two-bit comparator (cont’d)

83.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 83 block diagram and truth table 4-variable K-map for each of the 4 output functions A2 A1 B2 B1 P8 P4 P2 P1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 Design example: 2x2-bit multiplier P1 P2 P4 P8 A1 A2 B1 B2

84.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 84 K-map for P8 K-map for P4 K-map for P2 K-map for P1 Design example: 2x2-bit multiplier (cont’d) 0 0 0 0 0 0 0 0 B1 A2 0 0 0 0 0 1 1 1 A1 B2 0 0 0 1 0 0 1 0 B1 A2 0 1 0 0 1 0 0 0 A1 B2 0 0 0 0 0 0 1 1 B1 A2 0 1 0 1 0 1 1 0 A1 B2 0 0 0 0 0 0 0 0 B1 A2 0 0 0 0 1 0 0 0 A1 B2 P8 = A2A1B2B1 P4 = A2B2B1 + A2A1B2 P2 = A2A1B2 + A1B2B1 + A2B2B1 + A2A1B1 P1 = A1B1

85.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 85 I8 I4 I2 I1 O8 O4 O2 O1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X 1 1 0 0 X X X X 1 1 0 1 X X X X 1 1 1 0 X X X X 1 1 1 1 X X X X block diagram and truth table 4-variable K-map for each of the 4 output functions O1 O2 O4 O8 I1 I2 I4 I8 Design example: BCD increment by 1

86.III - Working with Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 85 I8 I4 I2 I1 O8 O4 O2 O1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X 1 1 0 0 X X X X 1 1 0 1 X X X X 1 1 1 0 X X X X 1 1 1 1 X X X X block diagram and truth table 4-variable K-map for each of the 4 output functions O1 O2 O4 O8 I1 I2 I4 I8 Design example: BCD increment by 1

87.K-Maps: Caveats ! Empty K-Map must be constructed correctly Gray Code: Adjacent cells differ in only one variable K-Map must be plotted correctly Minterms from truth table or compact form Minterms from partially reduced expressions K-Map must be circled correctly Start with smallest cubes first! Remember that K-Maps “wrap” at edges Use 1s for F , 0s for F 87

88.Short List of Rules for Exor Logic A  A = 0 A  A’ = 1 A  1= A’ A’  1= A A  0= A A  B= B  A A B = B A A(B  C) = AB  AC A+B = A  B  AB A+B = A  B when AB = 0 A  (B  C) = ( A  B)  C ( A B) C = A ( B C) A+B = A  B  AB = A  B(1  A) = A  BA’ These rules are sufficient to minimize Exclusive Sum of Product expression for small number of variables We will use these rules in the class for all kinds of reversible, quantum, optical, etc. logic. Try to remember them or put them to your “creepsheet”.

89.Chess Patterns W Y 1 1 1 1 1 1 1 1 0 0 0 0 W Y W X  Y  Z 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1

90.Chess Patterns Y  Z 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 W X W X  Y  Z 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 W X  Y  Z  1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0

91.Chess Patterns for functions of 5 variables 01 00 DE 00 01 11 10 11 10 AB 11 00 DE 10 01 11 10 01 00 AB mirror 0 01 1 0 1 0 00 CDE 0 00 1 0 1 0 01 11 10 1 0 1 0 1 0 1 0 0 11 0 10 AB 1 11 0 1 0 1 1 10 0 1 0 1 0 1 0 1 0 1 0 1 1 01 1 00 E D D  E

92.0 1 0 0 EXOR Patterns WX  Y 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 W X 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 W X  YZ 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 W X  Y Z

93.Example of Application in Quantum Computing

94.Use of Toffoli Gate x 1 x 2 w x 1 x 2 w  x 1 x 2 (x 1 x 2 w)x 3 y (x 1 x 2 w)x 3 y  w x 3

95.Example of Application in Robotics

96.Another Example: Braitenberg Vehicles and Quantum BV

97.Braitenberg Vehicles

98.Braitenberg Vehicles Instead of only analog components we can have binary components such as logic gates and circuits. We can use analog-to-digital converters for sensors and digital-to-analog converters for motors and lights.

99.Essence of logic synthesis approach to learning

100.Example of Logical Synthesis in Machine Learning John Dave Mark Jim Alan Nick Mate Robert

101.A - size of hair C - size of beard D - color of eyes B - size of nose Dave Jim John Mark Good guys Alan Nick Mate Robert Bad guys

102.Good guys John Mark Dave Jim C - size of beard D - color of eyes A - size of hair B - size of nose A’ BCD A’ BCD’ A’ B’CD A’ B’CD 00 01 11 10 00 - 1 - 01 – 1 1 11 - – - - 10 - - - - AB CD - -

103.C - size of beard D - color of eyes A - size of hair B - size of nose A’ BC’D’ AB’C’D ABCD A’ B’C’D 00 01 11 10 00 - 1 - 01 0 1 1 11 - – 0 - 10 - 0 - - AB CD - 0 Alan Nick Mate Robert Bad guys A’C

104.C - size of beard D - color of eyes A - size of hair B - size of nose 00 01 11 10 00 - 1 - 01 0 1 1 11 - – 0 - 10 - 0 - - AB CD - 0 A’C Generalization 1: Bald guys with beards are good Generalization 2: All other guys are no good

105.Example of Application in Machine Learning: Decision Trees

106.a=0 a=1 c=1 c=0 1 0 Using Kmaps to illustrate cofactoring or splitting a*c c=1 c=0 1 a*c b=1 b=0 0 a*c d *b*d THIS METHOD ASSUMES NO PRUNNING The same as a*c a*c + SOLUTION a*c *b*d +

107.a=0 a=1 c=1 c=0 1 0 Using Kmaps to illustrate cofactoring or splitting a*c c=1 c=0 1 a*c 0 a*c *b*d THIS METHOD ASSUMES PRUNNING when there is more ones than zeros in a cofactor group or more zeros than ones The same as In this cofactor a*c we have more zeros than ones so we prune to constant 0 + SOLUTION

108.Conclusion on Prunning a*c a*c + SOLUTION without PRUNNING a*c *b*d + a*c a*c + SOLUTION with PRUNNING These are two different functions. PRUNNING OR NO PRUNNING CAN LEAD TO OVERFITTING

109.PROJECT EXAMPLE Full Adder in VERILOG YOU WILL HAVE A PROJECT

110.Schematic of a circuit Various specifications of combinational circuits Truth Table Karnaugh Map Natural Language Specification Verilog Code Hypercube Logic Equations

111.Verilog Dataflow Example: Full Adder CI A B CO S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 111

112.Verilog Structural Example: Full Adder 112

113.Verilog Structural Example: Full Adder 113

114.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 114 COLLECTION OF PROBLEMS FOR MIDTERM (with partial solutions)

115.115 Problem 1: Minimize Function F as SOP Given is function from Fig. 3.17. Synthesize minimum SOP and draw the circuit.

116.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 116 f’ = z’ + wy’ Complement of f f = z(w’ + y) Product of Sums f = w’z + yz Sum of Products Problem 2: Minimize Function F as POS Given is function from Figure above. Synthesize minimum POS and draw the circuit. f = w’x ’ + yz Another sum of products In this example there are two solutions for SOP with the same cost of literals. Cost of inputs to gates is different.

117.NAND Implementations of AND, OR, and NOT Gates NOT Gate AND Gate OR Gate x x x y y f f f f = x’ f = ((xy)’)’ = xy f = (x’y’)’ = x + y Problem 3: Realize NOT , AND and OR functions using only NAND gates. Draw schematics of circuits realizing NOT, AND and OR Gates using only NAND gates. Repeat this problem using only logic operators that realize function f= x’a + xb

118.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 118 NOR Implementations of AND, OR, and NOT Gates x x y x y f f f NOT Gate AND Gate OR Gate f = x’ f = (x’ + y’)’ = xy f = ((x + y)’)’ = x + y Problem 4: Realize NOT, OR and AND functions using NOR gates only Draw schematics of circuits realizing NOT, AND and OR Gates using only NOR gates. Repeat this problem using only logic operators that realize function f = ( x’+a ) * ( x+b )

119.XOR gates have the following interesting properties: x  0 = x x  1 = x ’ x  x = 0 x  x ’ = 1 x  y ’ = x ’  y = ( x  y )’ x  y = y  x x  y  z = ( x  y )  z = x  ( y  z ) Problem 5: Write basic logic formulas related to EXOR gate Write formulas for exor of x and 0, x and 1 and other similar formulas for EXOR gate. Prove that they are true using truth tables.

120.Two-Input XOR Implementation Using AND, OR, and NOT Gates x y x  y Problem 6: Draw schematics of EXOR gate from AND, OR and NOT gates Draw logic diagram for EXOR gate using AND, OR and NOT gates. There are several solutions not shown above.

121.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 121 Two-Input XOR Implementation Using NAND Gates x y x  y Problem 7: Realize EXOR gate using only four NAND gates and no other gates. Draw logic diagram for EXOR gate using only four NAND gates. How many NOR gates you need to realize EXOR? Try to minimize this circuit.

122.Problem 8: Minimize Parity functions of 4 variables Using the truth tables of parity functions from the left, realize both of them in a circuit with minimum number of arbitrary gates AND, OR, EXOR and NOT

123.Karnaugh Maps for Four-Input XOR and XNOR Gates Realize these maps with the minimum number of EXOR gates and no other gates. You may use constants.

124.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 124 Example of XOR Extraction Given a Boolean function f , is it possible to simplify this complex sum of products function using XOR and XNOR gates? Consider the following Karnaugh Map: NOTE: This Boolean function uses six terms in sum of products form. Problem 9: Minimize Function using only two EXOR, one NOT and one AND gates Realize these maps with the minimum number of EXOR, AND and NOT gates and no other gates. You may use constants. Draw the schematic.

125.Example of XOR Extraction XNOR XOR

126.Example of XNOR Extraction Simplifying… Arguably, this simplified expression using two XOR gates will require fewer total gates to implement the function

127.Example of Reuse of Intermediate Nodes Consider the following functions f 1 and f 2 : f 1 = x + y f 2 = xz + yz = ( x + y ) z A more advanced solution is the following: x y z f 2 f 1 Problem 10: Realize functions f1 and f2 from equations below using minimum number of gates AND and OR Realize functions f1 and f2 using only AND and OR gates. Repeat this problem using only NAND gates. Repeat this these problem using only NOR gates. Draw the schemata.

128.Example of Analyzing a Combinational Circuit NOTE: Step 1 adds labels T 1 , T 2 , T 4 , T 5 , and T 6 to to the diagram. Step 2 is repeated to label F 2 , F ’ 2 , T 3 , and F 1 in order. Step 4 is performed to find the Boolean functions in terms of inputs. T 4 T 5 T 6 Problem 11: Analyze the function from the circuit given below

129.Determining the Boolean Functions The combinational circuit on the previous slide contains two outputs that need to be expressed as Boolean functions of the three inputs To express these functions, Boolean functions for each intermediate node ( T 1 , T 2 , T 3 , T 4 , T 5 , T 6 , and F ’ 2 ) must be determined

130.Determining the Boolean Functions for Each Logic Gate F 1 = T 2 T 3 F 2 = T 4 + T 5 + T 6 T 1 = A + B + C T 2 = ABC T 3 = T 1 F ’ 2 T 4 = AB T 5 = AC T 6 = BC F ’ 2 = ( F 2 )’

131.Determining the Boolean Function for F 1 F 1 = T 2 + T 3 = ABC + T 1 F ’ 2 = ABC + ( A + B + C )( F 2 )’ = ABC + ( A + B + C )( T 4 + T 5 + T 6 )’ = ABC + ( A + B + C )( AB + AC + BC )’ = ABC + ( A + B + C )(A’ + B’)(A’ + C’)(B’ + C’) = ABC + ( A ’ B + A ’ C + AB ’ + B ’ C )( A ’ B ’ + B ’ C ’ + A ’ C ’) = ABC + A ’ B ’ C + A ’ BC ’ + AB ’ C ’

132.Determining the Boolean Function for F 2 F 2 = T 4 + T 5 + T 6 = AB + AC + BC Question: What combinational circuit is shown in this example? Answer: The combinational circuit implements a 1-bit full adder: A and B are single-bit inputs and C is the carry-in F 1 is the sum and F 2 is the carry-out

133.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 133 Full Adder Truth Table A full adder circuit performs 1-bit addition The truth table shown to the right describes a 1-bit addition circuit The inputs to the circuit are A, B, and C (carry-in) The outputs of the circuit are F 1 (sum) and F 2 (carry-out) A B C F 1 F 2 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Problem 11: Draw truth table of a full adder Draw the truth table. Using the truth table, draw a Kmap . Using Kmap , find the realization using the minimum number of EXOR gates and other gates such as NOT, AND and OR. Draw the schemata. Repeat this problem using only NAND gates. Repeat this these problem using only NOR gates. Draw the schemata.

134.May-30-17 Lecture Notes - SE 141: Digital Circuits and Systems 134 Textbook Example Design a combinational circuit to convert from BCD code to Excess-3 code Step 1: Determine the inputs and outputs of the circuit Four inputs labelled A , B , C , and D Four outputs labelled w , x , y , and z The label names were chosen arbitrarily in this case Problem 12: Convert from BCD code to Excess-3 code

135.Step 2: Truth Table Input BCD Code Output Excess-3 Code A B C D w x y z 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0

136.Step 3: Boolean Simplification

137.Step 4: Logic Diagram

138.Problem 13. Design of The Half Adder and Full Adder A B C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Half Adder (HA) B A C S NOTE: From the truth table, it can be seen that S = A  B and C = AB Design full adder from half adders and in other variant directly.

139.Implementations of the Half Adder Implementation 1 S = AB ’ + A ’ B C = AB Implementation 2 S = A  B C = AB A A’ A B’ B B B S C S C A B A B

140.The Full Adder A i B i C i C i +1 S i 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Full Adder (FA) B i A i C i C i +1 S i

141.The Full Adder Recall that a full adder can be built as follows: NOTE: A i = A B i = B C i = C S i = F 1 C i +1 = F 2

142.The Full Adder A i B i C i C i +1 S i 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Half Adder (HA) B i A i C i +1 S i Half Adder (HA) C i However, the full adder can also be built as follows:

143.Questions and EXAM Problems (1) Explain how to derive Boolean Equations from a Truth Table. Explain how to derive Boolean Equations from a circuit schematic. What are minterms . How to obtain an equation based on minterms from a Truth Table? How to obtain a circuit based on minterms ? What is SOP form? What is POS form? Write an equation for a function that is not in POS and not in SOP form. Show circuit. What are maxterms ? How they are used in logic synthesis? Generalized Compact Minterm Form, give examples . Generalized Compact Maxterm Form, give examples. Draw Kmap for a function of two variables in two different ways. Draw Kmap for a function of three variables in two different ways . Draw Kmap for a function of four variables in two different ways . Draw Kmap for a function of five variables in two different ways.

144.Questions and EXAM Problems (2) 16. What is an Implicant ? How to find it on Kmap ? 17. What is a Prime Implicant . How to find it on Kmap ? 18. What is an Essential Prime Implicant . How to find it on Kmap ? 19. What is Optional Prime Implicant . How to find it on Kmap ? 20. What is Redundant (Non-Essential) Prime Implicant . How to find it on Kmap ? 21. Give example of a function that is composed only from essential prime implicants . 22. Give example of a function in which the largest prime implicant will be not included in the minimal solution. 23. What is a don’t care? What is an incompletely specified function? 24. Give example of POS circuit with term sharing.

145.Questions and EXAM Problems (3) 25. What are chess patterns? 26. Show chess pattern a b on Kmap of three variables and next on Kmap of 4 variables. 27 . Show chess pattern a b on Kmap of 5 variables. 28. Show chess pattern a b  c on Kmap of 5 variables. 29. What are exor patterns? 30. Show exor pattern ae bc  d on Kmap of 5 variables. 31. Show exor pattern a  e  b  c  ad on Kmap of 5 variables .

146.EXOR Patterns 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 Questions and EXAM Problems (4) Minimize functions above using only EXOR and AND gates and literals. 0 0 0 0 1 0 1 1

147.Challenge Problems for ambitious students Problem 1. Express function AB+CD+A’C using only EXORs and AND gates Problem 2 . Prove that (A+B)’ = A  B  AB 1 Problem 3 . Prove that A+B = A  B when AB = 0 without using Kmaps or truth tables. Problem 4. Given are three functions of three inputs: A = NOT(a), B = NOT(b), C = NOT(c). You have only two inverters. You can have an arbitrary large set of two-input AND and OR gates. Realize these three functions with the gates that you have at your disposal. You cannot use other gates. You can use only two inverters. Draw the schematic of the solution

148.Sources Prof. Mark G. Faust John Wakerly Caetano Boriello Morris Mano