ELCT201: DIGITAL LOGIC DESIGN Prof. Dr. Eng. Tallal El-Shabrawy, tallal.el-shabrawy@guc.edu.eg

Dr. Eng. Wassim Alexan, wassim.joseph@guc.edu.eg

Lecture 4

هــ 1441محرم

Spring 2020

Following the slides of Dr. Ahmed H. Madian

COURSE OUTLINE

1. Introduction

2. Gate-Level Minimization

3. Combinational Logic

4. Synchronous Sequential Logic

5. Registers and Counters

6. Memories and Programmable Logic

2

LECTURE OUTLINE

• Combinational Logic Circuits

• Steps of Combinational Logic Design

• The XOR Function

• Half Adder

• Full Adder

• Binary Adder/Subtractor

• Binary Multiplier

3

COMBINATIONAL LOGIC

• Combinational logic circuits can have any number of inputs and outputs

• The logic states of the inputs at any given instant determine the state of the output

4

• Sequential circuits, which we will discuss later in this course, will feature circuits in which the outputs are not determined solely by the inputs at the same time

HOW TO DESIGN A COMBINATIONAL LOGIC CIRCUIT?

1. From the specifications of the circuit, determine the required number of inputs and outputs and assign a letter (symbol) to each

2. Derive the truth table that defines the required relationship between the inputs and outputs

3. Obtain the simplified Boolean functions for each output as a function of the input variables (using a K-map)

4. Sketch the logic diagram

5

6

DESIGN PROBLEM

Design a digital system whose output is defined as logically

low if the 4-bit input binary number is a multiple of 3;

Otherwise, the output will be logically high. The output is

defined if and only if the input binary number is greater

than 2

7

INPUT/OUTPUT RELATIONSHIP AND TRUTH TABLE

• Design a digital system

whose output is defined as

logically low if the 4-bit

input binary number is a

multiple of 3; otherwise, the

output will be logically high

• The output is defined if and

only if the input binary

number is greater than 2

8

BOOLEAN FUNCTION SIMPLIFICATION USING A K-MAP

9

BOOLEAN FUNCTION SIMPLIFICATION USING A K-MAP

SOP POS

𝑌𝑆𝑂𝑃 = 𝐵′𝐷′ + 𝐴′𝐶′ + 𝐴′𝐵𝐷 + 𝐵𝐶′𝐷 + 𝐴𝐵′𝐶 + 𝐴𝐶𝐷′

𝑌𝑃𝑂𝑆 = (𝐴 + 𝐵)(𝐵 + 𝐶 + 𝐷′)(𝐴 + 𝐶′ + 𝐷)(𝐴′ + 𝐵′ + 𝐶 + 𝐷)(𝐴′ + 𝐵′ + 𝐶′ + 𝐷′)

10

SKETCHING THE LOGIC DIAGRAM

THE XOR FUNCTION

The XOR symbol is denoted as ⊕

Its Boolean operation is 𝑥 ⊕ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦

The XNOR symbol is denoted as ⊙

Its Boolean operation is 𝑥 ʘ 𝑦 = 𝑥𝑦 + 𝑥′𝑦′

The identities of the XOR operation are

given by:

𝑥 ⊕ 0 = 𝑥 𝑥 ⊕ 1 = 𝑥′

𝑥 ⊕ 𝑥 = 0 𝑥 ⊕ 𝑥′ = 1

Commutative and associative:

A ⊕ 𝐵 = 𝐵 ⊕ 𝐴

(A ⊕ 𝐵) ⊕ 𝐶 = 𝐴 ⊕ (𝐵 ⊕ 𝐶) = 𝐴 ⊕ 𝐵 ⊕ 𝐶

11

Z Y X

0

1

1

0

0

1

0

1

0

0

1

1

Z Y X

1

0

0

1

0

1

0

1

0

0

1

1

XOR

XNOR

𝑥⊙𝑦 = 𝑥 ⊕ 𝑦

THE XOR IMPLEMENTATION

12

• The output analysis for the first

circuit is very easy!

• The output at each of the NAND

gates for the second circuit is as

follows:

• At L1: 𝑥𝑦 = 𝑥′ + 𝑦′

L1

L2

L3

L4

THE XOR IMPLEMENTATION

13

• The output analysis for the first

circuit is very easy!

• The output at each of the NAND

gates for the second circuit is as

follows:

• At L1: 𝑥𝑦 = 𝑥′ + 𝑦′

• At L2:

𝑥(𝑥′ + 𝑦′) = 𝑥𝑥′ + 𝑥𝑦′ = 𝑥𝑦′ = 𝑥′ + 𝑦

• At L3:

𝑦(𝑥′ + 𝑦′) = 𝑥′𝑦 + 𝑦𝑦′ = 𝑥′𝑦 = 𝑥 + 𝑦′

L1

L2

L3

L4 𝒙′ + 𝒚′

𝒙

𝒙′ + 𝒚′

𝒚

𝒙′ + 𝒚

𝒙 + 𝒚′

THE XOR IMPLEMENTATION

14

• The output analysis for the first

circuit is very easy!

• The output at each of the NAND

gates for the second circuit is as

follows:

• At L1: 𝑥𝑦 = 𝑥′ + 𝑦′

• At L2:

𝑥(𝑥′ + 𝑦′) = 𝑥𝑥′ + 𝑥𝑦′ = 𝑥𝑦′ = 𝑥′ + 𝑦

• At L3:

𝑦(𝑥′ + 𝑦′) = 𝑥′𝑦 + 𝑦𝑦′ = 𝑥′𝑦 = 𝑥 + 𝑦′

• At L4:

L1

L2

L3

L4

(𝑥′+𝑦)(𝑥 + 𝑦′) = (𝑥′ + 𝑦) + (𝑥 + 𝑦′) = 𝑥𝑦′ + 𝑥′𝑦 = 𝑥 ⊕ 𝑦

15

ARITHMETIC CIRCUITS

• We will continue with the design of digital logic circuits

• One of the famous digital logic circuits is the calculator

• How to design it?

16

ARITHMETIC CIRCUITS

• An arithmetic circuit is a combinational circuit that performs arithmetic operations such as: • Addition

• Subtraction

• Multiplication

• Division

• A combinational circuit that performs the addition of two bits is called a Half Adder

outputs one digit

outputs two digits!

carry sum

So, we need two binary outputs to

represent the addition block

(carry & sum)

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10

17

HALF ADDER

It is required to design a combinational circuit that adds two binary numbers and produces the output in the form of two bits, sum and carry

Solution:

1. We need to determine the inputs and output of the system and give letters for all of them: Our system has two inputs (x, y) and two outputs (S, C)

Half Adder

x

y C

S

18

HALF ADDER

2. Derive the truth table according to the given relation between inputs and outputs

Outputs Inputs

S C y x

0

1

1

0

0

0

0

1

0

1

0

1

0

0

1

1

19

HALF ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

𝐶 = 𝑥𝑦 𝑆 = 𝑥𝑦′ + 𝑥′𝑦

= 𝑥 ⊕ 𝑦

20

HALF ADDER

4. Sketch the logic diagram

21

FULL ADDER

It is required to design a combinational circuit that adds three binary numbers and produces the output in the form of two bits, sum and carry

Solution:

1. We need to determine the inputs and outputs of the system and give letters for all of them: Our system has three inputs (x, y, z) and two outputs (S, C)

Full Adder y

S

C z

x

22

FULL ADDER

2. Derive the truth table according to the given relation between the inputs and outputs

Decimal

Equivalent

Outputs Inputs

S C z y x

0

1

1

2

1

2

2

3

0

1

1

0

1

0

0

1

0

0

0

1

0

1

1

1

0

1

0

1

0

1

0

1

0

0

1

1

0

0

1

1

0

0

0

0

1

1

1

1

23

FULL ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

𝑆 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ + 𝑥𝑦𝑧

Remember that:

𝑥⊙𝑦 = 𝑥 ⊕ 𝑦, 𝑥 ⊕ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦, 𝑥⊙𝑦 = 𝑥𝑦 + 𝑥′𝑦′

24

FULL ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

𝑆 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ + 𝑥𝑦𝑧

= 𝑧 𝑥′𝑦′ + 𝑥𝑦 + 𝑧′ 𝑥′𝑦 + 𝑥𝑦′

= 𝑧(𝑥′𝑦 + 𝑥𝑦′) + 𝑧′(𝑥′𝑦 + 𝑥𝑦′)

Remember that:

𝑥⊙𝑦 = 𝑥 ⊕ 𝑦, 𝑥 ⊕ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦, 𝑥⊙𝑦 = 𝑥𝑦 + 𝑥′𝑦′

25

FULL ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

𝑆 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ + 𝑥𝑦𝑧

= 𝑧 𝑥′𝑦′ + 𝑥𝑦 + 𝑧′ 𝑥′𝑦 + 𝑥𝑦′

= 𝑧(𝑥′𝑦 + 𝑥𝑦′) + 𝑧′(𝑥′𝑦 + 𝑥𝑦′)

= 𝑧 𝑥 ⊕ 𝑦 + 𝑧′ 𝑥 ⊕ 𝑦

Remember that:

𝑥⊙𝑦 = 𝑥 ⊕ 𝑦, 𝑥 ⊕ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦, 𝑥⊙𝑦 = 𝑥𝑦 + 𝑥′𝑦′

26

FULL ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

Remember that:

𝑥⊙𝑦 = 𝑥 ⊕ 𝑦, 𝑥 ⊕ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦, 𝑥⊙𝑦 = 𝑥𝑦 + 𝑥′𝑦′

𝑆 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ + 𝑥𝑦𝑧

= 𝑧 𝑥′𝑦′ + 𝑥𝑦 + 𝑧′ 𝑥′𝑦 + 𝑥𝑦′

= 𝑧(𝑥′𝑦 + 𝑥𝑦′) + 𝑧′(𝑥′𝑦 + 𝑥𝑦′)

= 𝑧 𝑥 ⊕ 𝑦 + 𝑧′ 𝑥 ⊕ 𝑦

= 𝒛 ⊕ 𝒙 ⊕ 𝒚

= 𝒙 ⊕ 𝒚 ⊕ 𝒛

27

FULL ADDER

3. Obtain the simplified Boolean functions for each output as a function of the input variables using a K-map

𝐶 = 𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧

28

FULL ADDER

4. Sketch the logic diagram

𝑆 = 𝑥′𝑦′𝑧 + 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ + 𝑥𝑦𝑧

𝑆 = 𝑥 ⊕ 𝑦 ⊕ 𝑧

𝐶 = 𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧

29

FULL ADDER

• The logic circuit for the full adder could also be sketched using two half adders and a single OR gate

𝐶 = 𝑥 ⊕ 𝑦 𝑧 + 𝑥𝑦

= 𝑥𝑦′ + 𝑥′𝑦 𝑧 + 𝑥𝑦

= 𝑥𝑦′𝑧 + 𝑥′𝑦𝑧 + 𝑥𝑦

𝑆 = 𝑥 ⊕ 𝑦 ⊕ 𝑧

Half adder Half adder

Compare the obtained Boolean expression

for 𝐶 here and the one obtained in slide 28

30

FULL ADDER

• The logic circuit for the full adder could also be sketched using two half adders and a single OR gate

𝑆 = 𝑥 ⊕ 𝑦 ⊕ 𝑧

Half adder Half adder

Compare the obtained Boolean expression

for 𝐶 here and the one obtained in slide 28

𝐶 = 𝑥𝑦′𝑧 + 𝑥′𝑦𝑧 + 𝑥𝑦

𝐶 = 𝑥(𝑦 + 𝑦′𝑧) + 𝑥′𝑦𝑧

𝐶 = 𝑥(𝑦 + 𝑧) + 𝑥′𝑦𝑧

31

FULL ADDER

• The logic circuit for the full adder could also be sketched using two half adders and a single OR gate

𝑆 = 𝑥 ⊕ 𝑦 ⊕ 𝑧

Half adder Half adder

Compare the obtained Boolean expression

for 𝐶 here and the one obtained in slide 28

𝐶 = 𝑥𝑦 + 𝑥𝑧 + 𝑥′𝑦𝑧

𝐶 = 𝑥𝑦 + 𝑧(𝑥 + 𝑥′𝑦)

𝐶 = 𝑥𝑦 + 𝑧(𝑥 + 𝑦)

32

FULL ADDER

• The logic circuit for the full adder could also be sketched using two half adders and a single OR gate

𝑆 = 𝑥 ⊕ 𝑦 ⊕ 𝑧

Half adder Half adder

Compare the obtained Boolean expression

for 𝐶 here and the one obtained in slide 28

𝑪 = 𝒙𝒚 + 𝒙𝒛 + 𝒚𝒛

33

4-BIT BINARY RIPPLE CARRY ADDER

• Connecting n full adders in cascade allows us to add n-bit binary numbers together

• Example:

Connecting 4 full adders in cascade allows us to add 1011 to 0011.

𝐴 = 𝐴3𝐴2𝐴1𝐴0 = 1 0 1 1 𝐵 = 𝐵3𝐵2𝐵1𝐵0

= 0 0 1 1

34

4-BIT BINARY RIPPLE CARRY ADDER 𝑨𝟎 = 𝟏

𝑪𝟎 = 𝟎

𝑺𝟎 = 𝟎 𝑪𝟒 = 𝟎

𝟏 𝟏 𝟎

𝑨𝟏 = 𝟏 𝑨𝟐 = 𝟎 𝑨𝟑 = 𝟏 𝑩𝟎 = 𝟏 𝑩𝟏 = 𝟏 𝑩𝟐 = 𝟎 𝑩𝟑 = 𝟎

𝑺𝟏 = 𝟏 𝑺𝟐 = 𝟏 𝑺𝟑 = 𝟏

This adder is extremely

slow, as each stage must

wait for the previous one to

get the carry from it!

35

BINARY SUBTRACTOR

• The subtraction of binary numbers can be easily done using complements

• The subtraction 𝐴 − 𝐵 is done by taking the 2’s complement of 𝐵 and adding it to 𝐴

• The 2’s complement can be obtained by taking the 1’s complement and adding 1 to the least significant bit (LSB)

• The 1’s complement can be implemented easily with an inverter gate

• We can add 1 to the sum by making the initial input carry of

the parallel adder equal to 1

SUBTRACTION EXAMPLE

1 0 1

− 0 1 1

36

1 0 1

+ 1 0 0

+ 0 0 1

1 0 1

+ 1 0 0

1 0 0 1

+ 0 0 1

1 𝟎 𝟏 𝟎

1’s Complement

2’s Complement

37

BINARY ADDER/SUBTRACTOR

• Subtractor

• Adder/Subtractor

FA

FA

𝑆

𝐶𝑜𝑢𝑡

𝐴

𝐶𝑖𝑛 = 1

𝐵

𝐵 𝐴

𝑆

𝐶𝑜𝑢𝑡

This is equivalent

to 𝐴 plus the 2’s

complement of 𝐵

Remember that 𝐵 ⊕ 0 = 𝐵

and 𝐵 ⊕ 1 = 𝐵′

If 𝐶𝑖𝑛 = 0, circuit acts as an Adder

If 𝐶𝑖𝑛 = 1, circuit acts as a Subtractor

𝐶𝑖𝑛

38

BINARY MULTIPLIER

2 bits × 2 bits = max 4 bits

(11)2× (11)2= (1001)2

(3)10× (3)10= (9)10

𝑀3 𝑀2 𝑀1 𝑀0 𝑀3 𝑀2 𝑀1 𝑀0

𝑆 𝐶 𝐶 𝑆