Digital Circuit Design

18B11EC215
Lecture 7
Implementation using Logic Gates and
Standard forms

1
Outline
▪ Universal Gates: NAND and NOR
▪ Implementation using NAND Gates
▪ Implementation using NOR Gates
▪ Standard Forms
▪ Minterm & Maxterm
▪ Canonical Form
 SOP
 POS
 Conversion between canonical forms

2
Universal Gates: NAND and NOR[1,3]
 AND/OR/NOT gates are sufficient for building any Boolean
functions.
 We call the set {AND, OR, NOT} a complete set of logic.
 However, other gates are also used because:
(i) usefulness
(ii) economical on transistors
(iii) self-sufficient

NAND/NOR: economical, self-sufficient

XOR: useful (e.g. parity bit generation)

3
NAND Gate
 NAND gate is self-sufficient (can build any logic circuit with it).
 Therefore, {NAND} is also a complete set of logic.
 Can be used to implement AND/OR/NOT.
 Implementing an inverter using NAND gate:

x x'

(x.x)' = x' (T1: idempotency)

4
 NAND Gate[2]
 Implementing AND using NAND gates:

(x.y)'
x ((xy)'(xy)')' = ((xy)')' idempotency
x.y
y = (xy) involution

Implementing OR using NAND gates:

x'
x ((xx)'(yy)')' = (x'y')' idempotency
x+y = x''+y'' DeMorgan
= x+y involution
y
y'

5
NOR Gate[2]
 NOR gate is also self-sufficient.
 Therefore, {NOR} is also a complete set of logic
 Can be used to implement AND/OR/NOT.
 Implementing an inverter using NOR gate:

x x'

(x+x)' = x' (T1: idempotency)

6
 NOR Gate[2]
Implementing AND using NOR gates:
x'
x
x.y
((x+x)'+(y+y)')'=(x'+y')' idempotency
y
y' = x''.y'' DeMorgan
= x.y involution

Implementing OR using NOR gates:

(x+y)'
x
x+y
y
((x+y)'+(x+y)')' = ((x+y)')' idempotency
= (x+y) involution

7
Implementation using NAND
gates[1,2,3]
 Possible to implement any Boolean expression using NAND gates.
Procedure:
(i) Obtain sum-of-products Boolean expression:
e.g. F3 = xy'+x'z
(ii) Use DeMorgan theorem to obtain expression using 2-
level NAND gates
e.g. F3 = xy'+x'z
= (xy'+x'z)' ' involution
= ((xy')' . (x'z)')' DeMorgan

8
Implementation using NAND gates
contd.
x (xy')'
y'
F3
x'
z (x'z)'

F3 = ((xy')'.(x'z)') ' = xy' + x'z

9
 Implementation using NOR
gates[1,2,3]
 Possible to implement any Boolean expression using NOR gates.
Procedure:
(i) Obtain product-of-sums Boolean expression:
e.g. F6 = (x+y').(x'+z)
(ii) Use DeMorgan theorem to obtain expression using 2-level
NOR gates.
e.g. F6 = (x+y').(x'+z)
= ((x+y').(x'+z))' ' involution
= ((x+y')'+(x'+z)')' DeMorgan

10
Implementation using NOR gates
contd.
x (x+y')'
y'
F6
x'
z (x'+z)'

F6 = ((x+y')'+(x'+z)')' = (x+y').(x'+z)

11
Standard Forms

 Two Standard Forms:

 Sum-of-Products and Product-of-Sums
 Literals: A variable and its complemented form
 x, x' , y, y'
 Product Term: A single literal or a Product of several literals

 x, x.y.z', A'.B, A.B

 Sum Term: A single literal or a Sum of several literals

x, x+y+z', A'+B, A+B

SOP and POS

Sum-of-Products (SOP) Product-of-Sums (POS)

Expression: Expression:

A product term or a logical sum (OR) A sum term or a logical product

of several product terms. (AND) of several sum terms.

x, x,
x.(y+z'),
x+y.z',
(x+y').(x'+y+z),
x.y'+x’.y.z,
(A+B).(A'+B')
A.B+A'.B'

Every Boolean expression can either be expressed as SOP or POS expression.

 Example
SOP
1. x.y + x.y + x.y.z

2. (x + y).(x + y).(x + z) POS

3. x + y + z or x.y.z
Both
4. x.(w + y.z) or z + w.x.y + v.(x.z + w)
Neither

 SOP circuits can easily be implemented using NAND Gate

 POS circuits can easily be implemented using NOR Gate

 Minterm & Maxterm [1,2]

 Consider two binary variables x, y.

 Each variable may appear as itself or in complemented form as literals (i.e.
x, x' & y, y' )
 For two variables, there are four possible combinations with the AND
operator, namely:
x'.y', x'.y, x.y', x.y
■ Minterm: a product term in which all the variables appear exactly once,
either complemented or uncomplemented
 These product terms are called the minterms.

 A minterm of n variables is the product of n literals from the different

variables.
Minterm & Maxterm [1,2]

 In general, n variables can give 2n minterms.

 In a similar fashion, a maxterm of n variables is the sum of n literals
from the different variables.
Examples: x'+y', x'+y, x+y',x+y
 Maxterm: a sum term in which all the variables appear exactly once,
either complemented or uncomplemented
 In general, n variables can give 2n maxterms.
Canonical Form: Sum of Minterms[1]
 What is a canonical/normal form?
 A unique form for representing something.

■ Any Boolean function F( ) can be expressed as a unique sum of

minterms and a unique product of maxterms (under a fixed
variable ordering).

■ In other words, every function F() has two canonical forms:

■ Canonical Sum-Of-Products (sum of minterms)
■ Canonical Product-Of-Sums (product of maxterms)
Conversion of SOP from standard to
canonical form [1]
■ Expand non-canonical terms by inserting equivalent of 1 in each
missing variable x:
(x + x’) = 1
■ Remove duplicate minterms
■ 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’
= m1+m6+m2+m4
Canonical Form: Product of Maxterms [1]

 Maxterms are sum terms.

 For Boolean functions, the maxterms of a function are the terms for
which the result is 0.
 Boolean functions can be expressed as Products-of-Maxterms.
 Conversion of POS from standard to
canonical form
■ Expand noncanonical terms by adding 0 in terms of missing variables
(e.g., x.x’ = 0) and using the distributive law

■ Remove duplicate maxterms

■ 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’)
Conversion Between Canonical
Forms [1]
■ 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
= ∑m(1,2,4,6)
= ∏M(0,3,5,7)
= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)
Implementation of SOP
Expressions[1]
 Sum-of-Products expressions can be implemented using:
 2-level AND-OR logic circuits
 2-level NAND logic circuits
 AND-OR logic circuit

A
B F = AB + CD + E
C
F
D

22
 Implementation of SOP Expressions
contd.
 NAND-NAND circuit (by circuit
transformation) A
a) add double bubbles B
b) change OR-with- C
inverted-inputs to NAND F
D
& bubbles at inputs to
their complements E

A
B
C
F
D

E'

23
Implementation of POS
Expressions[1]
 Product-of-Sums expressions can be implemented using:
 2-level OR-AND logic circuits
 2-level NOR logic circuits
 OR-AND logic circuit

A
B G = (A+B).(C+D).E
C
G
D

24
Implementation of POS Expressions
contd.

 NOR-NOR circuit (by circuit A

transformation): B
a) add double bubbles C
b) changed AND-with- G
D
inverted-inputs to NOR
& bubbles at inputs to E
their complements

A
B
C
G
D

E'

25
References

[1] M. Morris Mano and Michael D. Ciletti, “Digital Design with an

Introduction to the Verilog HDL,” 5th Edition, Pearson Education,2013.

[2] Reshu Gupta, Amit Gupta ,Atul Kumar Sharma “ Switching

Theory(Digital Electronics)”, Tech India Publication Series, Satya
Prakashan, New Delhi.

[3] R. P. Jain, “Modern Digital Electronics,” 4th Edition, Tata McGraw-Hill

Education, 2009.

26