University of Anbar Subject / Digital Techniques

College of Engineering Second Stage / 1st Semester

Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬

Karnaugh Map POS Minimization

In this section, we will focus on POS expressions instead of SOP. The
approaches are much the same except that with POS expressions, 0’s representing
the standard sum terms are placed on the karnaugh map instead of 1’s.
Example: Map the following POS expression on a karnaugh map.
(A + B + C + D)(A + B + C + D)(A + B + C + D)(A + B + C + D)(A + B + C + D)
1100 1011 0010 1111 0011

00 01 11 10
CD CD CD CD CD
AB

00 AB 0 0

01 AB A+ B +C + D

11 AB 0 0 A+ B +C + D
10 AB 0

Example: Use a karnaugh map to minimize the POS expression:

( A + B + C )(A + B + C )(A + B + C )(A + B + C )(A + B + C )

Out = A( B + C ) C C

keep in mind that this minimum POS expression AB 0 0

is equivalent to the original standard POS expression AB 0 0
A
grouping the 1’s as shown yields a SOP expression
AB 0 1
that is equivalent to grouping the 0’s . AC
AB 1 1

AC + AB = A( B + C )

Review Questions:
1. Use a Karnaugh map to minimize the POS expression:

55
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
( B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)
2. Map the following SOP expression on a karnaugh map:
BC + AB + AB C + ABC D + ABCD + ABCD
3. What is the difference in mapping a POS expression and an SOP expression?
4. What is the standard sum term for a 0 in cell 1011?
5. What is the standard product term for a 1 in cell 0010?
6. Determine the minimum expression for each K-map in figure below:

CD CD CD CD CD CD CD CD

AB 1 1 1 1 AB 1 0 1 1

AB 1 1 0 0 AB 1 0 0 1
AB 0 0 0 1 AB 0 0 0 0

AB 0 1 1 0 AB 1 0 1 1

7. Use a K-map to simplify each expression to a minimum SOP form:

(a) ABC + ABC + ABC + AB C Ans : No Simplifica tion

(b) AC [ B + B ( B + C )] Ans : AC

(c) DE F + DE F + D E F Ans : D F + E F
8. Reduce the function specified in the truth table in figure below to its
minimum SOP form by using K-map. A B C X
0 0 0 1
0 0 1 1
Ans: B + C
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

56
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬

9. Use a k-map to simplify each expression to a minimum POS form:

(a) ( A + B + C + D)( A + B + C + D)( A + B + C + D)

(b) ( X + Y )(W + Z )( X + Y + Z )(W + X + Y + Z )

10. Simplify the following equation: f ( A, B, C , D) = ∑ (1,3,7,11,15) .

11. Simplify the following equation:
f ( A, B, C , D) = ∑ (1,5,6,11,14,15)
dm(2,3,7) where dm is denoted for don' t care.

Implementation of Logic Circuit:

In this section, several general examples are used to illustrate how to
implement a logic circuit from a Boolean expression or a truth table.
1- From Boolean Expression to a Circuit:
The following expression is the first in the series of examples that will be
considered:- X=AB+CDE
This expression is composed of two terms, AB and CDE, with a total of five
variables. The first term is formed by ANDing A with B, and the second term is
formed by ANDing C,D, and E. The two terms are then ORed to form the output
X. These operations are indicated in the structure of the expression as follows:

AND A
B
X= AB + CDE X
C
D
OR E
57
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬

Example: Implement the following expression: X = AB (C D + EF )

AND A
B X
NOT
OR C
D
X= AB (C D + EF ) C D + EF
E
AND F

Example: Draw the circuit diagram that implements the expression: X = AB + BC

A
B

2- From Truth Table to a Circuit:

Beginning with a truth table, we will write the SOP expression from the truth
table and then implement the logic circuit. The table below specifies a logic
function. The expression is obtained from a truth table by ORing the product
terms for all occurrences of X=1. The expression is: X = ABC + ABC
Input Output
A B C X
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1

58
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
1 0 1 0
The logic gates required to implement this
1 1 0 0 expression are as follows:
Three inverters to form the A, B and C
1 1 1 0
variables; two 3-input AND gates to form
the term ABC and ABC ; and one 2-input
OR gate
Example: Reduce the combinational logic to form
circuit in the finalbelow
Figure output.to a minimum

form: A ABC A
A BC
B B X
X
C C

The expression for the output of the circuit is: X = ( A BC )C + A BC + D

Applying DeMorgan’s theorem and Boolean algebra:

X = ( A + B + C )C + A + B + C + D
= AC + BC + CC + A + B + C + D = AC + BC + C + A + B + C + D
= C ( A + B + 1 + 1) + A + B + D = A + B + C + D
Hence, the simplified circuit is a 4-input OR gate.
Universal Property of NAND and NOR Gates:
Up to this point, combinational circuits implemented with AND gates, OR
gates and inverters have been studied. In this section, the universal property of the
NAND gate and the NOR gate is introduced. the universality of the NAND gate
means that it can be used as an inverter and that combinations of NAND gates can
be used to implement the AND, OR and NOR operations. Similarly, the NOR gate
can be used to implement the inverter, AND, OR and NAND operations.
1- Using NAND Gate:

A A

A
AB
B

A 59
A+ B
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬

2- Using NOR Gate:

A A

A
A+ B
B

A
AB
B

A
AB
B

Example: Design using NAND gates the following expression: X = AB + CD

OR Gate
A
B
X
C
D
AND Gate

60
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬

After eliminating
double inversion

A
B
X
C
D

Example: Design Z = AC + AB using NAND gates only:

Z = AC + AB = AC . AB (Conversion to Product form)

B Z

Example: Design Z = AC + AB using NOR gates only:

Z = AC + AB = ( A + C ) + ( A + B) (Conversion to Sum form)

A A+ B

B
Z

C
A+C

61
 University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
Example: Implement the following expression with NAND gates only:
ABC + DE
OR Gate
A A
B B
C C
X X
D D
E E
AND Gate

Example: Implement the logic circuit that has the expression

X = AB .(C + D ) using only one NAND and NOR gate.

C C+D
D X
B
A

Example: Implement a circuit having the output expression Z = A + B + C using

only one NAND and an inverter gate.
A
B Z
Z = A + B + C can be written as :
Z = A.B.C = A.B.C C
Review Questions:
8. Implement the following logic expressions:
(a) X = ABC + AB + AC (b) X = AB (C + DE )

(c) X = B(C DE + EFG )( AB + C ) (d) X = ABC + B( EF + G )

9. Use NAND gates to implement::
(a) X = A + B (b) X = AB

10. Implement the expression X = ( A + B + C ) DE by using NAND logic.

11. Implement the expression X = A BC + ( D + E ) with NOR logic.

62
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
12. Design a logic circuit to implement the operation specified in the truth table
indicated by Table (a):
13. Minimize the combinational logic circuit shown in Fig. (a):
14. Implement the logic circuit in Fig. (b) using only NAND gates. Repeat the
design using only NOR gates.

Table (a)
A
Input Output
B
A B C X C
A
0 0 0 0 B
0 0 1 0 C
D
X
0 1 0 0 A
B
0 1 1 1 C
1 0 0 0 D Fig. (a)
A
1 0 1 1 B
1 1 0 1 C
D
1 1 1 0

A
B

X
C

Fig. (b)
15. Show how the following expression can be implemented as stated using only
NAND gates:
(a) X = ABC (b) X = ABC
(c) X = A + B (d) X = A + B + C
(e) X = AB + CD (f) X = ( A + B)(C + D)

(g) X = AB[C ( DE + AB ) + BCE ]

16. Implement each function by using only NAND gates:
(a) X = AB + AB (b) X = A[ BC ( A + B + C + D)]

63
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
17. Minimize the gates required to implement the function in SOP form:
(a) X = AB + AB (b) X = ABC + B( EF + G )

(c) X = A[ BC ( A + B + C + D)] (d) X = B(C DE + EFG )( AB + C )

18. Design a minimal circuit to detect 31-day months, coded in 8-4-2-1 binary.
19. Obtain a minimal SOP for the function below then implement using NAND
gates only: f ( A, B, C , D) = ∑ (0,7,8,10,12 ) + d (2,6,11) .
20. Using a karnaugh map, convert the following standard POS expression into
a minimum POS expression, a standard SOP expression and a minimum SOP
expression:
f ( A, B, C , D)   (1,2,3,4,9,12) where  is denoted for POS

Basic Adders:
Adders are important not only in computers, but in many types of digital
systems in which numerical data are processed. An understanding of the basic
adder operation is fundamental to the study of digital systems. In this section, the
half-adder and the full-adder are introduced.
3- The Half-Adder (H.A):
Recall the basic rules for binary addition as stated in the previous lectures:

64
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
00  0
These operations are performed by a logic circuit called a
0 1  1 half-adder. The half-adder accepts two binary digits on its
1 0  1 inputs and produces two binary digits on its outputs, a Sum bit
1  1  10 and a Carry bit.

A B Cout S
A S Sum
0 0 0 0
H.A
0 1 0 1
B Cout Carry
1 0 0 1
1 1 1 0

Sum
S  A B
Cout  AB
A
Carry
B

4- The Full-Adder(F.A):
The second basic category of adder is the Full-adder. The full-adder accepts
three inputs including an input carry and generates a Sum output and output
carry.

A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0

65
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
1 0 0 0 1
A S Sum
B
1 0 1 1 0
F.A 1 1 0 1 0
Carry in Cin Cout Carry out 1 1 1 1 1

From the truth table:-

Cout  ABCin  A BCin  AB Cin  ABC in
 ( AB  A B )Cin  AB
Cout  ( A  B )Cin  AB ...........Eq.(1)

S  A BCin  ABCin  A BCin  ABC in

 A BCin  ( AB  A B ) Cin  ABC in .........Eq.(2)

But A BCin  ABC in  ( A B  AB ) Cin

 ( A  B )( A  B ) Cin
 ( A B  B A) Cin .........Eq.(3)
Substituting Eq.3 in Eq.2
S  ( AB  A B )Cin  ( AB  A B )Cin  A  B  Cin

B
Sum (S)
Cin

Carry (Cout)

66
University of Anbar Subject / Digital Techniques
College of Engineering Second Stage / 1st Semester
Dept. of Electrical Engineering (2017 – 2018)
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
Example: Arrange two half-adders to form full-adder.

A A B Sum (S)
H.A H.A
B
( A  B) Cin

Input Carry
AB Carry (Cout)

Parallel Binary Adders:

Adders that are available in integrated circuits form are parallel binary
adders. As you saw in the previous section, a single full-adder is capable of adding
two 1-bit numbers and an input carry. To add binary numbers with more than one
bit, additional full-adders must be employed. To implement the addition of binary
numbers, a full-adder is required for each bit in the numbers. So, for 2-bit numbers,
two adders are needed; for 4-bit numbers, four adders are used; and so on.

A2 B2 A1 B1
A2A1
+ B 2B 1

Σ3 Σ2 Σ1 F.A F.A

(MSB)Σ3 Σ2 Σ1 (LSB)

67