Digital Logic (Review)

Overview • Binary logic and Gates • Boolean Algebra – Basic Properties – Algebraic Manipulation

• Standard and Canonical Forms – Min and Max (Canonical forms) – SOP and POS (Standard forms)

• Karnaugh Maps (K-Maps) – 2, 3, 4, and 5 variable maps – Simplification using K-Maps

• K-Map Manipulation – Implicants: Prime, Essential – Don’t Cares

• More Logic Gates

2018/2/2

Boolean Algebra

Binary Logic • Deals with binary variables that take 2 discrete values (0 and 1), and with logic operations • Three basic logic operations: – AND, OR, NOT

• Binary/logic variables are typically represented as letters: A,B,C,…,X,Y,Z

2018/2/2

Boolean Algebra

Binary Logic Function F(vars) = expression Operators

set of binary variables

Variables

Constants

( 0, 1 ) Groupings (parenthesis)

Example: F(a,b) = a’•b + b’ G(x,y,z) = x•(y+z’) 2018/2/2

( +, •, ‘ )

Boolean Algebra

Basic Logic Operators • AND • OR • NOT

Binary Unary

• F(a,b) = a•b, F is 1 if and only if a=b=1 • G(a,b) = a+b, G is 1 if either a=1 or b=1 • H(a) = a’, H is 1 if a=0 2018/2/2

Boolean Algebra

Basic Logic Operators (cont.) • 1-bit logic AND resembles binary multiplication: 0 • 0 = 0, 1 • 0 = 0,

0 • 1 = 0, 1•1 =1

• 1-bit logic OR resembles binary addition, except for one operation: 0 + 0 = 0, 1 + 0 = 1, 2018/2/2

0 + 1 = 1, 1 + 1 = 1 (≠ 102) Boolean Algebra

Truth Tables for logic operators Truth table: tabular form that uniguely represents the relationship between the input variables of a function and its output 2-Input AND

A 0 0 1 1 2018/2/2

B F=A•B 0 0 1 0 0 0 1 1

2-Input OR

A 0 0 1 1

B F=A+B 0 0 1 1 0 1 1 1

Boolean Algebra

NOT

A F=A’ 0 1 1 0

Truth Tables (cont.) • Q: Let a function F() depend on n variables. How many rows are there in the truth table of F() ? 

n

n

A: 2 rows, since there are 2 possible binary patterns/combinations for the n variables

Boolean Algebra

Logic Gates • Logic gates are abstractions of electronic circuit components that operate on one or more input signals to produce an output signal. 2-Input AND A B

F

F = A•B 2018/2/2

2-Input OR A B

G

G = A+B Boolean Algebra

NOT (Inverter) A

H

H = A’

Timing Diagram t0 t1 t2 t3 t4 t5 t6 Input signals

Gate Output Signals

2018/2/2

B

1 0 1 0

F=A•B

1 0

G=A+B

1 0

H=A’

1 0

A

Boolean Algebra

Transitions Basic Assumption: Zero time for signals to propagate Through gates

Combinational Logic Circuit from Logic Function • Consider function F = A’ + B•C’ + A’•B’ • A combinational logic circuit can be constructed to implement F, by appropriately connecting input signals and logic gates: – Circuit input signals  from function variables (A, B, C) – Circuit output signal  function output (F) – Logic gates  from logic operations

C F

A B

2018/2/2

Boolean Algebra

Combinational Logic Circuit from Logic Function (cont.) • In order to design a cost-effective and efficient circuit, we must minimize the circuit’s size (area) and propagation delay (time required for an input signal change to be observed at the output line) • Observe the truth table of F=A’ + B•C’ + A’•B’ and G=A’ + B•C’ • Truth tables for F and G are identical  same function • Use G to implement the logic circuit (less components) 2018/2/2

Boolean Algebra

A

B

C

F

G

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

0

0

1

0

1

0

0

1

1

0

1

1

1

1

1

0

0

Combinational Logic Circuit from Logic Function (cont.) C F

A B

C B A

2018/2/2

G

Boolean Algebra

Boolean Algebra • VERY nice machinery used to manipulate (simplify) Boolean functions • George Boole (1815-1864): “An investigation of the laws of thought” • Terminology: – Literal: A variable or its complement – Product term: literals connected by • – Sum term: literals connected by + 2018/2/2

Boolean Algebra

Boolean Algebra Properties Let X: boolean variable, 0,1: constants

1. 2. 3. 4.

2018/2/2

X + 0 = X -- Zero Axiom X • 1 = X -- Unit Axiom X + 1 = 1 -- Unit Property X • 0 = 0 -- Zero Property

Boolean Algebra

Boolean Algebra Properties (cont.) Let X: boolean variable, 0,1: constants

5. 6. 7. 8. 9. 2018/2/2

X + X = X -- Idepotence X • X = X -- Idepotence X + X’ = 1 -- Complement X • X’ = 0 -- Complement (X’)’ = X -- Involution Boolean Algebra

Duality • The dual of an expression is obtained by exchanging (• and +), and (1 and 0) in it, provided that the precedence of operations is not changed. • Cannot exchange x with x’ • Example: – Find H(x,y,z), the dual of F(x,y,z) = x’yz’ + x’y’z – H = (x’+y+z’) (x’+y’+ z)

2018/2/2

Boolean Algebra

Duality (cont’d) With respect to duality, Identities 1 – 8 have the following relationship: 1.

X+0=X

2.

X•1 =X

(dual of 1)

3.

X+1 =1

4.

X•0 =0

(dual of 3)

5.

X+X=X

6.

X • X = X (dual of 5)

7.

X + X’ = 1

8.

X • X’ = 0 (dual of 8)

2018/2/2

Boolean Algebra

More Boolean Algebra Properties Let X,Y, and Z: boolean variables X+Y=Y+X 12. X + (Y+Z) = (X+Y) + Z 14. X•(Y+Z) = X•Y + X•Z 10.

11. X

•Y=Y•X -- Commutative 13. X•(Y•Z) = (X•Y)•Z -- Associative 15. X+(Y•Z) = (X+Y) • (X+Z) -- Distributive

16.

(X + Y)’ = X’ • Y’

17.

(X • Y)’ = X’ + Y’

In general, ( X1 + X2 + … + Xn )’ = X1’•X2’ • … •Xn’, and ( X1•X2•… •Xn )’ = X1’ + X2’ + … + Xn’

2018/2/2

Boolean Algebra

-- DeMorgan’s

Absorption Property 1. x + x•y = x 2. x•(x+y) = x (dual) • Proof: x + x•y = x•1 + x•y = x•(1+y) = x•1 =x QED (2 true by duality, why?) 2018/2/2

Boolean Algebra

Power of Duality 1. 2. 3. 4. 5. 6.

x + x•y = x is true, so (x + x•y)’=x’ (x + x•y)’=x’•(x’+y’) x’•(x’+y’) =x’ Let X=x’, Y=y’ X•(X+Y) =X, which is the dual of x + x•y = x. The above process can be applied to any formula. So if a formula is valid, then its dual must also be valid. 7. Proving one formula also proves its dual. 2018/2/2

Boolean Algebra

Consensus Theorem 1.xy + x’z + yz = xy + x’z 2.(x+y)•(x’+z)•(y+z) = (x+y)•(x’+z) -- (dual) • Proof: xy + x’z + yz = xy + x’z + (x+x’)yz = xy + x’z + xyz + x’yz = (xy + xyz) + (x’z + x’zy) = xy + x’z QED (2 true by duality). 2018/2/2

Boolean Algebra

Truth Tables (revisited) • Enumerates all possible combinations of variable values and the corresponding function value • Truth tables for some arbitrary functions F1(x,y,z), F2(x,y,z), and F3(x,y,z) are shown to the right.

2018/2/2

Boolean Algebra

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

F1 0 0 0 0 0 0 0 1

F2 1 0 0 1 1 1 0 0

F3 1 1 1 1 0 0 0 1

Truth Tables (cont.) • Truth table: a unique representation of a Boolean function • If two functions have identical truth tables, the functions are equivalent (and vice-versa). • Truth tables can be used to prove equality theorems. • However, the size of a truth table grows exponentially with the number of variables involved, hence unwieldy. This motivates the use of Boolean Algebra.

2018/2/2

Boolean Algebra

Boolean expressions-NOT unique • Unlike truth tables, expressions representing a Boolean function are NOT unique. • Example: – F(x,y,z) = x’•y’•z’ + x’•y•z’ + x•y•z’ – G(x,y,z) = x’•y’•z’ + y•z’

• The corresponding truth tables for F() and G() are to the right. They are identical. • Thus, F() = G()

2018/2/2

Boolean Algebra

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

F 1 0 1 0 0 0 1 0

G 1 0 1 0 0 0 1 0

Algebraic Manipulation • Boolean algebra is a useful tool for simplifying digital circuits. • Why do it? Simpler can mean cheaper, smaller, faster. • Example: Simplify F = x’yz + x’yz’ + xz. F = x’yz + x’yz’ + xz = x’y(z+z’) + xz = x’y•1 + xz = x’y + xz 2018/2/2

Boolean Algebra

Algebraic Manipulation (cont.) • Example: Prove x’y’z’ + x’yz’ + xyz’ = x’z’ + yz’ • Proof: x’y’z’+ x’yz’+ xyz’ = x’y’z’ + x’yz’ + x’yz’ + xyz’ = x’z’(y’+y) + yz’(x’+x) = x’z’•1 + yz’•1 = x’z’ + yz’ QED. 2018/2/2

Boolean Algebra

Complement of a Function • The complement of a function is derived by interchanging (• and +), and (1 and 0), and complementing each variable. • Otherwise, interchange 1s to 0s in the truth table column showing F. • The complement of a function IS NOT THE SAME as the dual of a function.

2018/2/2

Boolean Algebra

Complementation: Example • Find G(x,y,z), the complement of F(x,y,z) = xy’z’ + x’yz • G = F’ = (xy’z’ + x’yz)’ = (xy’z’)’ • (x’yz)’ DeMorgan = (x’+y+z) • (x+y’+z’) DeMorgan again • Note: The complement of a function can also be derived by finding the function’s dual, and then complementing all of the literals 2018/2/2

Boolean Algebra

Canonical and Standard Forms • We need to consider formal techniques for the simplification of Boolean functions. – Identical functions will have exactly the same canonical form. – Min and Max – Sum-of-Min and Product-of- Max – Product and Sum – Sum-of-Products (SOP) and Product-of-Sums (POS)

2018/2/2

Boolean Algebra

Definitions • • • •

Literal: A variable or its complement Product term: literals connected by • Sum term: literals connected by + Minterm: a product term in which all the variables appear exactly once, either complemented or uncomplemented • Maxterm: a sum term in which all the variables appear exactly once, either complemented or uncomplemented 2018/2/2

Boolean Algebra

Minterm • Represents exactly one combination in the truth table. • Denoted by mj, where j is the decimal equivalent of the minterm’s corresponding binary combination (bj). • A variable in mj is complemented if its value in bj is 0, otherwise is uncomplemented. • Example: Assume 3 variables (A,B,C), and j=3. Then, bj = 011 and its corresponding minterm is denoted by mj = A’BC

2018/2/2

Boolean Algebra

Maxterm • Represents exactly one combination in the truth table. • Denoted by Mj, where j is the decimal equivalent of the maxterm’s corresponding binary combination (bj). • A variable in Mj is complemented if its value in bj is 1, otherwise is uncomplemented. • Example: Assume 3 variables (A,B,C), and j=3. Then, bj = 011 and its corresponding maxterm is denoted by Mj = A+B’+C’

2018/2/2

Boolean Algebra

Truth Table notation for Min and Max • Min and x Max are easy 0 to denote using a 0 truth table. 0 • Example: 0 Assume 3 variables1 x,y,z 1 (order is fixed) 1

y

z

Minterm

Maxterm

0

0

x’y’z’ = m0

x+y+z = M0

0

1

x’y’z = m1

x+y+z’ = M1

1

0

x’yz’ = m2

x+y’+z = M2

1

1

x’yz = m3

x+y’+z’= M3

0

0

xy’z’ = m4

x’+y+z = M4

0

1

xy’z = m5

x’+y+z’ = M5

1

0

xyz’ = m6

x’+y’+z = M6

1

1

1

xyz = m7

x’+y’+z’ = M7

2018/2/2

Boolean Algebra

Canonical Forms (Unique) • Any Boolean function F( ) can be expressed as a unique sum of min and a unique product of max (under a fixed variable ordering). • In other words, every function F() has two canonical forms: – Canonical Sum-Of-Products (sum of min) – Canonical Product-Of-Sums (product of max)

2018/2/2

Boolean Algebra

Canonical Forms (cont.) • Canonical Sum-Of-Products: The min included are those mj such that F( ) = 1 in row j of the truth table for F( ). • Canonical Product-Of-Sums: The max included are those Mj such that F( ) = 0 in row j of the truth table for F( ).

2018/2/2

Boolean Algebra

Example • Truth table for f1(a,b,c) at right a • The canonical sum-of-products form for f1 0 is f1(a,b,c) = m1 + m2 + m4 + m6 0 = a’b’c + a’bc’ + ab’c’ + abc’ 0 • The canonical product-of-sums form for f1 is 0 f1(a,b,c) = M0 • M3 • M5 • M7 = (a+b+c)•(a+b’+c’)• 1 (a’+b+c’)•(a’+b’+c’). 1 • Observe that: mj = Mj’

b 0 0 1 1 0 0 1 1 1 1

2018/2/2

Boolean Algebra

c 0 1 0 1 0 1 0 1

f1 0 1 1 0 1 0 1 0

Shorthand: ∑ and ∏ • f1(a,b,c) = ∑ m(1,2,4,6), where ∑ indicates that this is a sum-of-products form, and m(1,2,4,6) indicates that the min to be included are m1, m2, m4, and m6. • f1(a,b,c) = ∏ M(0,3,5,7), where ∏ indicates that this is a product-of-sums form, and M(0,3,5,7) indicates that the max to be included are M0, M3, M5, and M7. • Since mj = Mj’ for any j, ∑ m(1,2,4,6) = ∏ M(0,3,5,7) = f1(a,b,c) 2018/2/2

Boolean Algebra

Conversion Between Canonical Forms • Replace ∑ with ∏ (or vice versa) and replace those j’s that appeared in the original form with those that do not. • Example: f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’ = m1 + m2 + m4 + m6 = ∑(1,2,4,6) = ∏(0,3,5,7) = (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)

2018/2/2

Boolean Algebra

Standard Forms (NOT Unique) • Standard forms are “like” canonical forms, except that not all variables need appear in the individual product (SOP) or sum (POS) . • Example: f1(a,b,c) = a’b’c + bc’ + ac’ is a standard sum-of-products form • f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’) is a standard product-of-sums form. 2018/2/2

Boolean Algebra

Conversion of SOP from standard to canonical form • Expand non-canonical by inserting equivalent of 1 in each missing variable x: (x + x’) = 1 • Remove duplicate min • f1(a,b,c) = a’b’c + bc’ + ac’ = a’b’c + (a+a’)bc’ + a(b+b’)c’ = a’b’c + abc’ + a’bc’ + abc’ + ab’c’ = a’b’c + abc’ + a’bc + ab’c’ 2018/2/2

Boolean Algebra

Conversion of POS from standard to canonical form • Expand noncanonical by adding 0 in of missing variables (e.g., xx’ = 0) and using the distributive law • Remove duplicate max • f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’) = (a+b+c)•(aa’+b’+c’)•(a’+bb’+c’) = (a+b+c)•(a+b’+c’)•(a’+b’+c’)• (a’+b+c’)•(a’+b’+c’) = (a+b+c)•(a+b’+c’)•(a’+b’+c’)•(a’+b+c’) 2018/2/2

Boolean Algebra

Karnaugh Maps • Karnaugh maps (K-maps) are graphical representations of boolean functions. • One map cell corresponds to a row in the truth table. • Also, one map cell corresponds to a minterm or a maxterm in the boolean expression • Multiple-cell areas of the map correspond to standard . 2018/2/2

Boolean Algebra

Two-Variable Map x1 0

x2

0

1

0

1

m0 2

1

x1

m1

OR

1

0

0

3

m2

0

x2

2

m0 1

m3

1

m2 3

m1

m3

NOTE: ordering of variables is IMPORTANT for f(x1,x2), x1 is the row, x2 is the column. Cell 0 represents x1’x2’; Cell 1 represents x1’x2; etc. If a minterm is present in the function, then a 1 is placed in the corresponding cell. 2018/2/2

Boolean Algebra

Two-Variable Map (cont.) • Any two adjacent cells in the map differ by ONLY one variable, which appears complemented in one cell and uncomplemented in the other. • Example: m0 (=x1’x2’) is adjacent to m1 (=x1’x2) and m2 (=x1x2’) but NOT m3 (=x1x2)

2018/2/2

Boolean Algebra

2-Variable Map -- Example • f(x1,x2) = x1’x2’+ x1’x2 + x1x2’ = m0 + m1 + m2 = x1’ + x2’ • 1s placed in K-map for specified min m0, m1, m2 • Grouping (ORing) of 1s allows simplification • What (simpler) function is represented by each dashed rectangle? – x1’ = m0 + m1 – x2’ = m0 + m2 • Note m0 covered twice 2018/2/2

Boolean Algebra

x2

x1

0

1

0

0

1

1 2

1

1 3

1

0

Minimization as SOP using K-map • Enter 1s in the K-map for each product term in the function • Group adjacent K-map cells containing 1s to obtain a product with fewer variables. Group size must be in power of 2 (2, 4, 8, …) • Handle “boundary wrap” for K-maps of 3 or more variables. • Realize that answer may not be unique 2018/2/2

Boolean Algebra

Three-Variable Map yz

00

x 0

0

1

m0 4

1

01 3

m1 5

m4

11 2

m3 7

m5

10 m2 6

m7

m6

-Note: variable ordering is (x,y,z); yz specifies column, x specifies row. -Each cell is adjacent to three other cells (left or right or top or bottom or edge wrap) 2018/2/2

Boolean Algebra

Three-Variable Map (cont.)

minterm

The types of structures that are either min or are generated by repeated application of the minimization theorem on a three variable map are shown at right. Groups of 1, 2, 4, 8 are possible. group of 2 group of 4 2018/2/2

Boolean Algebra

Simplification • Enter min of the Boolean function into the map, then group • Example: f(a,b,c) = a’c + abc + bc’ • Result: f(a,b,c) = a’c+ b a bc

1

2018/2/2

1

1

1

1 Boolean Algebra

1

1

1

1

1

More Examples yz X

• f1(x, y, z) = ∑ m(2,3,5,7) 

f1(x, y, z) = x’y + xz

• f2(x, y, z) = ∑ m (0,1,2,3,6) f2(x,

2018/2/2

y, z) = x’+yz’

Boolean Algebra

00

01

0

1

1

1

1

11

10

1

1

1

1

1 1

Four-Variable Maps

YZ WX

00

01

11

10

00 m0

m1

m3

m2

01

m4

m5

m7

m6

11

m12

m13

m15

m14

10

m8

m9

m11

m10

• Top cells are adjacent to bottom cells. Left-edge cells are adjacent to right-edge cells. • Note variable ordering (WXYZ). 2018/2/2

Boolean Algebra

Four-variable Map Simplification • One square represents a minterm of 4 literals. • A rectangle of 2 adjacent squares represents a product term of 3 literals. • A rectangle of 4 squares represents a product term of 2 literals. • A rectangle of 8 squares represents a product term of 1 literal. • A rectangle of 16 squares produces a function that is equal to logic 1. 2018/2/2

Boolean Algebra

Example • Simplify the following Boolean function (A,B,C,D) = ∑m(0,1,2,4,5,7,8,9,10,12,13). • First put the function g( ) into the map, and then group as many 1s as possible. ab

cd

1

1

1

1

1

1

1

1

1 1

1

1

1

1

1

1

1

1

1

1 1

g(A,B,C,D) = c’+b’d’+a’bd 2018/2/2

Boolean Algebra

1

Don't Care Conditions • There may be a combination of input values which – will never occur – if they do occur, the output is of no concern.

• The function value for such combinations is called a don't care. • They are denoted with x or –. Each x may be arbitrarily assigned the value 0 or 1 in an implementation. • Don’t cares can be used to further simplify a function

2018/2/2

Boolean Algebra

Minimization using Don’t Cares • Treat don't cares as if they are 1s to generate PIs. • Delete PI's that cover only don't care min. • Treat the covering of remaining don't care min as optional in the selection process (i.e. they may be, but need not be, covered).

2018/2/2

Boolean Algebra

cd ab 00 01 11 10

Example

00 0 01 1

• Simplify the function f(a,b,c,d) whose K-map is shown at the right. • f = a’c’d+ab’+cd’+a’bc’ or • f = a’c’d+ab’+cd’+a’bd’

1

0

1

1

0

1

11 0 0 x x 10 1 1 x x 0

1

0

1

1

1

0

1

0 0 x x

1

1

x x

0

1

0

1

1

1

0

1

0 0 x x 1 2018/2/2

Boolean Algebra

1

x x

Another Example • Simplify the function g(a,b,c,d) whose K-map is shown at right. • g = a’c’+ ab or • g = a’c’+b’d

cd ab

x

1

0 0

1

x 0 x

1

x x

1

0 x x 0 x

1

0 0

1

x 0 x

1

x x

1

0 x x 0 x

1

0 0

1

x 0 x

1

x x

1

0 x x 0 2018/2/2

Boolean Algebra

Algorithmic minimization • What do we do for functions with more variables? • You can “code up” a minimizer (ComputerAided Design, CAD) – Quine-McCluskey algorithm – Iterated consensus

• We won’t discuss these techniques here

2018/2/2

Boolean Algebra

More Logic Gates • NAND and NOR Gates – NAND and NOR circuits – Two-level Implementations – Multilevel Implementations

• Exclusive-OR (XOR) Gates – Odd Function – Parity Generation and Checking

2018/2/2

Boolean Algebra

- 60

More Logic Gates • We can construct any combinational circuit with AND, OR, and NOT gates

• Additional logic gates are used for practical reasons

2018/2/2

Boolean Algebra

- 61

BUFFER, NAND and NOR

2018/2/2

Boolean Algebra

- 62

NAND Gate • Known as a “universal” gate because ANY digital circuit can be implemented with NAND gates alone. • To prove the above, it suffices to show that AND, OR, and NOT can be implemented using NAND gates only.

2018/2/2

Boolean Algebra

- 63

NAND Gate Emulation X

X Y

F = (X•X)’ = X’+X’ = X’

X

F = ((X•Y)’)’ = (X’+Y’)’ = X’’•Y’’ = X•Y

2018/2/2

F X•Y

X

X Y

X Y

F = X’

F = (X’•Y’)’ = X’’+Y’’ = X+Y

Boolean Algebra

F = X+Y Y

- 64

NAND Circuits • To easily derive a NAND implementation of a boolean function: – – – –

Find a simplified SOP SOP is an AND-OR circuit Change AND-OR circuit to a NAND circuit Use the alternative symbols below

2018/2/2

Boolean Algebra

- 65

AND-OR (SOP) Emulation Using NANDs

Two-level implementations a) b)

2018/2/2

Original SOP Implementation with NANDs Boolean Algebra

- 66

AND-OR (SOP) Emulation Using NANDs (cont.)

: (a) G = WXY + YZ (b) G = ( (WXY)’ • (YZ)’ )’ = (WXY)’’ + (YZ)’’ = WXY + YZ 2018/2/2

Boolean Algebra

- 67

SOP with NAND

(a) (b) (c) 2018/2/2

Original SOP Double inversion and grouping Replacement with NANDs Boolean Algebra

AND-NOT NOT-OR - 68

Two-Level NAND Gate Implementation - Example F (X,Y,Z) = m(0,6) 1. Express F in SOP form: F = X’Y’Z’ + XYZ’ 2. Obtain the AND-OR implementation for F. 3. Add bubbles and inverters to transform ANDOR to NAND-NAND gates.

2018/2/2

Boolean Algebra

- 69

Example (cont.)

Two-level implementation with NANDs F = X’Y’Z’ + XYZ’ 2018/2/2

Boolean Algebra

- 70

Multilevel NAND Circuits Starting from a multilevel circuit: 1. Convert all AND gates to NAND gates with AND-NOT graphic symbols. 2. Convert all OR gates to NAND gates with NOT-OR graphic symbols. 3. Check all the bubbles in the diagram. For every bubble that is not counteracted by another bubble along the same line, insert a NOT gate or complement the input literal from its original appearance.

2018/2/2

Boolean Algebra

- 71

Example Use NAND gates and NOT gates to implement Z=E’F(AB+C’+D’)+GH AB AB+C’+D’ E’F(AB+C’+D’) E’F(AB+C’+D’)+GH

2018/2/2

Boolean Algebra

- 72

Yet Another Example!

2018/2/2

Boolean Algebra

- 73

NOR Gate • Also a “universal” gate because ANY digital circuit can be implemented with NOR gates alone. • This can be similarly proven as with the NAND gate.

2018/2/2

Boolean Algebra

- 74

NOR Circuits • To easily derive a NOR implementation of a boolean function: – – – –

2018/2/2

Find a simplified POS POS is an OR-AND circuit Change OR-AND circuit to a NOR circuit Use the alternative symbols below

Boolean Algebra

- 75

Two-Level NOR Gate Implementation - Example F(X,Y,Z) = m(0,6) 1. Express F’ in SOP form: 1. F’ = m(1,2,3,4,5,7) = X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XY’Z + XYZ 2. F’ = XY’ + X’Y + Z

2. Take the complement of F’ to get F in the POS form: F = (F’)' = (X'+Y)(X+Y')Z' 3. Obtain the OR-AND implementation for F. 4. Add bubbles and inverters to transform OR-AND implementation to NOR-NOR implementation. 2018/2/2

Boolean Algebra

- 76

Example (cont.)

Two-level implementation with NORs F = (F’)' = (X'+Y)(X+Y')Z' 2018/2/2

Boolean Algebra

- 77

XOR and XNOR XOR: “not-equal” gate X Y

F

XNOR: “equal” gate X

F

Y 2018/2/2

Boolean Algebra

X

Y

F = XY

0

0

0

0

1

1

1

0

1

1

1

0

X

Y

F = XY

0

0

1

0

1

0

1

0

0

1

1

1 - 78

Exclusive-OR (XOR) Function • XOR (also ) : the “not-equal” function • XOR(X,Y) = X  Y = X’Y + XY’ • Identities: – – – –

X0=X X  1 = X’ XX=0 X  X’ = 1

• Properties: – XY=YX – (X  Y)  W = X  ( Y  W) 2018/2/2

Boolean Algebra

- 79

XOR function implementation • XOR(a,b) = ab’ + a’b • Straightforward: 5 gates – 2 inverters, two 2-input ANDs, one 2-input OR – 2 inverters & 3 2-input NANDs

• Nonstraightforward: – 4 NAND gates

2018/2/2

Boolean Algebra

- 80

XOR circuit with 4 NANDs

2018/2/2

Boolean Algebra

- 81