ELEC 204

Digital Design g

Lecture 5 – Combinational Logic

Dr. Ertuğrul Başar

Department of Electrical and Electronics
Engineering

Spring 2023

based on Ch. 4 of Digital Design (Mano) & & further examples from Ch. 6 of Digital Fundamentals (Floyd)
 2

OUTLINE OF CHAPTER 4

Combinational Analysis Design Binary Adder Decimal

Circuits Procedure Procedure Subtractor Adder

Binary Magnitude Decoders Encoders Multiplexers

Multiplier Comparator

11 April, 2023
4.1 COMBINATIONAL
CIRCUITS
 4

CO M B I N AT I O N A L C I R C U I T S
• Logic circuits for digital systems
– Combinational

– Sequential

• A combinational circuit
– outputs at any time are determined from the present combination
of inputs.

– Performs operation specified by a set of Boolean functions.

11 April, 2023
 5

CO M B I N AT I O N A L C I R C U I T S
• Sequential circuits
– Employ storage elements in addition to logic gates.

– Their outputs are a function of inputs and state of the storage

elements.

– Not only present values of inputs, but also on past inputs.

– Circuit behaviour must be specified by a time sequence of inputs

and internal states.

11 April, 2023
 6

CO M B I N AT I O N A L C I R C U I T S
• Combinational circuit consist of
– Input variables

– Logic gates
• Accept signals from the inputs

• Generate signals to the output

– Output variables

11 April, 2023
 7

CO M B I N AT I O N A L C I R C U I T S

Combinational
𝑛 inputs 𝑚 outputs
Circuit

• For 𝑛 input variables, there are 2! possible binary input

combinations.
• For each possible input combination there is one possible output
value.
11 April, 2023
 8

CO M B I N AT I O N A L C I R C U I T S
• Analysis
– Given a circuit, find out its function A
B
F1

?
C
A
B

– Function may be expressed as: ?

C
A
B

A
F2

• Boolean function
C

B
C

• Truth table
• Design
– Given a desired function, determine its circuit
– Function may be expressed as:
• Boolean function
• Truth table
?

11 April, 2023
4.2 ANALYSIS
PROCEDURE
 10

A N A LY S I S P R O C E D U R E
• To obtain the output Boolean functions from a logic diagram:
1. Label all gate outputs that are function of input variables
• Determine the Boolean functions for each gate output

2. Label the gates that are a function of input variables and previously
labelled gates.
• Find the Boolean function for these gates.

3. Repeat the process outlined in Step 2 until the outputs are obtained.

4. Obtain the output Boolean functions in terms of input variables.

11 April, 2023
 11

A N A LY S I S P R O C E D U R E
• Boolean expression approach
A A.B.C (A.B+A.C+B.C)‘.(A+B+C)+A.B.C
B
F1
C
A A+B+C
B (A.B+A.C+B.C)‘.(A+B+C)
C
A (A.B+A.C+B.C)'
B A.B
A A.B+A.C+B.C
C A.C F2

B
C B.C

11 April, 2023
 12

A N A LY S I S P R O C E D U R E
• T1 = A+B+C
• Boolean expression • T2 = A.B.C
• F2 = A.B+A.C+B.C
approach
• F2’ = (A’+B’).(A’+C’).(B’+C’) = (A’ + B’C’).(B’+C’)
post4b
A T2 • T3 = F2’ . T1
B
C
F1 • T3 = (A’+B’.C’).(B’+C’).(A+B+C)
A T1 • T3 = (A’+B’.C’).(A.B’+B’.C+A.C’+B.C’)
B T3 • T3 = (A’.A.B’+A’.B’.C+A’.A.C’+A’.B.C’+
C
A F2’ • A.B’.B’.C’+B’.B’.C’.C+A.B’.C’.C’+B’.B.C’.C’)
B
• T3 =A’.B’.C + A’.B.C’ + A.B’.C’ + A.B’.C’
F2
A
F2 • T3 = A’.B’.C + A’.B.C’ + A.B’.C’
C
• F1= T3+T2
B
C • F1 = A’.B’.C + A’.B.C’ + A.B’.C’ + A.B.C

11 April, 2023
 13

A N A LY S I S P R O C E D U R E
• Truth table approach
A=0 A B C F1 F2
B=0
C=0 0 0 0 0 0
0 0
F1
A=0
B=0
C=0 0 0

A=0 1
B=0 0

A=0 0 0 F2
C=0

B=0 0
C=0

11 April, 2023
 14

A N A LY S I S P R O C E D U R E
• Truth table approach
A=0 A B C F1 F2
B=0
C=1 0 0 0 0 0
0 1
F1 0 0 1 1 0
A=0
B=0
C=1 1 1

A=0 1
B=0 0

A=0 0 0 F2
C=1

B=0 0
C=1

11 April, 2023
 15

A N A LY S I S P R O C E D U R E
• Truth table approach
A=0 A B C F1 F2
B=1
C=0 0 0 0 0 0
0 1
F1 0 0 1 1 0
A=0
0 1 0 1 0
B=1
C=0 1 1

A=0 1
B=1 0

A=0 0 0 F2
C=0

B=1 0
C=0

11 April, 2023
 16

A N A LY S I S P R O C E D U R E
• Truth table approach
A=0 A B C F1 F2
B=1
C=1 0 0 0 0 0
0 0
F1 0 0 1 1 0
A=0
0 1 0 1 0
B=1
C=1 1 0 0 1 1 0 1

A=0 0
B=1 0

A=0 0 1 F2
C=1

B=1 1
C=1

11 April, 2023
 17

A N A LY S I S P R O C E D U R E
• Truth table approach
A=1 A B C F1 F2
B=0
C=0 0 0 0 0 0
0 1
F1 0 0 1 1 0
A=1
0 1 0 1 0
B=0
C=0 1 1 0 1 1 0 1
1 1 0 0 1 0
A=1
B=0 0

A=1 0 0 F2
C=0

B=0 0
C=0

11 April, 2023
 18

A N A LY S I S P R O C E D U R E
• Truth table approach
A=1 A B C F1 F2
B=0
C=1 0 0 0 0 0
0 0
F1 0 0 1 1 0
A=1
0 1 0 1 0
B=0
C=1 1 0 0 1 1 0 1
0 1 0 0 1 0
A=1
B=0 0 1 0 1 0 1

A=1 1 1 F2
C=1

B=0 0
C=1

11 April, 2023
 19

A N A LY S I S P R O C E D U R E
• Truth table approach
A=1 A B C F1 F2
B=1
C=0 0 0 0 0 0
0 0
F1 0 0 1 1 0
A=1
0 1 0 1 0
B=1
C=0 1 0 0 1 1 0 1
0 1 0 0 1 0
A=1
B=1 1 1 0 1 0 1
1 1 0 0 1
A=1 0 1 F2
C=0

B=1 0
C=0

11 April, 2023
 20

A N A LY S I S P R O C E D U R E
• Truth table approach
A=1 A B C F1 F2
B=1
C=1 0 0 0 0 0
1 1
F1 0 0 1 1 0
A=1
0 1 0 1 0
B=1
C=1 1 0 0 1 1 0 1
0 1 0 0 1 0
A=1
B=1 1 1 0 1 0 1
1 1 0 0 1
A=1 1 F2
C=1
1 1 1 1 1 1

B=1 1
C=1

11 April, 2023
 21

A N A LY S I S P R O C E D U R E

11 April, 2023
 22

A N A LY S I S P R O C E D U R E
• Truth table approach A B C F1 F2
0 0 0 0 0
0 0 1 1 0
B B 0 1 0 1 0
BC BC
A 00 01 11 10 A 00 01 11 10 0 1 1 0 1
m0 m1 m3 m2 m0 m1 m3 m2 1 0 0 1 0
0 0
0 1 0 1 0 0 1 0 1 0 1 0 1
m4 m5 m7 m6 m4 m5 m7 m6 1 1 0 0 1
A 1 A 1
1 0 1 0 0 1 1 1 1 1 1 1 1

C C

F1 = A’B’C + A’BC’+ AB’C’+ ABC F2 = BC + AC + AB

11 April, 2023
4.3 DESIGN
PROCEDURE
 24

DESIGN PROCEDURE
• For a given a problem statement:
– Determine the number of inputs and outputs

– Derive the truth table

– Simplify the Boolean expression for each output

– Produce the required circuit

11 April, 2023
 25

DESIGN PROCEDURE
• A truth table for a combinational circuit consist of:
– Input columns
• Obtained from 2n binary numbers for the n input variables.

– Output columns
• Determined from the stated specifications.
• Output functions specified in the truth table give exact definition of the
combinational circuit.

11 April, 2023
 26

DESIGN PROCEDURE
• The output binary functions listed in the truth table are
simplified by any method:
– Algebraic manipulation

– The map method

– Computer – based simplification program

• There is a variety of simplified expressions from which to choose.

11 April, 2023
 27

DESIGN PROCEDURE
• Practical design must consider such constraints:
– The number of gates

– Number of inputs to a gate

– Propagation time of the signal through the gates

– Number of interconnections

– Limitations of the driving capability of each gate

– Etc.

11 April, 2023
 28

DESIGN PROCEDURE
Code conversion example

• Code converter is a circuit that makes the two systems

compatible even though each uses a different binary code.

• To convert from binary code A to binary code B;

Input: Output:
supply the bit generate the
combination of Combinational corresponding
elements specified Circuit bit combination
by code A of code B.

11 April, 2023
 29

DESIGN PROCEDURE
Example:

• Design a circuit to convert a “BCD” code to “Excess 3” code.

BCD: Excess 3:
4 – bits 4 – bits
0 – 9 values Combinational Binary Value +3
Circuit

11 April, 2023
 30

DESIGN PROCEDURE
Input BCD Output Excess-3
• Each code uses 4-bits to represent A B C D w x y z
a decimal digit. 0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
– 4 input variables 0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
• A, B, C, D 0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
– 4 output variables
0 1 1 0 1 0 0 1
• w, x, y, z 0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
– 24 = 16 bit combinations but 1 0 0 1 1 1 0 0
x x x x
only 10 have meaning in BCD. 1 0 1 0
1 0 1 1 x x x x
– Rest 6 bit combinations are 1 1 0 0 x x x x
1 1 0 1 x x x x
don’t-care combinations. 1 1 1 0 x x x x
1 1 1 1 x x x x
11 April, 2023
 31

DESIGN PROCEDURE
Input BCD Output Excess-3
A B C D w x y z w’s Karnaugh map
0 0 0 0 0 0 1 1 C
CD
0 0 0 1 0 1 0 0 AB 00 01 11 10
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0 00
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0 01 1 1 1
0 1 1 0 1 0 0 1 B
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
11 X X X X
A
1 0 0 1 1 1 0 0
1 0 1 0 x x x x 10 1 1 X X
1 0 1 1 x x x x
1 1 0 0 x x x x
D
1 1 0 1 x x x x
1 1 1 0 x x x x
w = A + BC + BD
1 1 1 1 x x x x
11 April, 2023
 32

DESIGN PROCEDURE
Input BCD Output Excess-3
A B C D w x y z x’s Karnaugh map
0 0 0 0 0 0 1 1 C
CD
0 0 0 1 0 1 0 0 AB 00 01 11 10
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0 00 1 1 1
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0 01 1
0 1 1 0 1 0 0 1 B
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
11 X X X X
A
1 0 0 1 1 1 0 0
1 0 1 0 x x x x 10 1 X X
1 0 1 1 x x x x
1 1 0 0 x x x x
D
1 1 0 1 x x x x
1 1 1 0 x x x x
x = B’C + B’D + BC’D’
1 1 1 1 x x x x
11 April, 2023
 33

DESIGN PROCEDURE
Input BCD Output Excess-3
A B C D w x y z y’s Karnaugh map
0 0 0 0 0 0 1 1 C
CD
0 0 0 1 0 1 0 0 AB 00 01 11 10
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0 00 1 1
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0 01 1 1
0 1 1 0 1 0 0 1 B
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
11 X X X X
A
1 0 0 1 1 1 0 0
1 0 1 0 x x x x 10 1 X X
1 0 1 1 x x x x
1 1 0 0 x x x x
D
1 1 0 1 x x x x
1 1 1 0 x x x x
y = CD + C’D’
1 1 1 1 x x x x
11 April, 2023
 34

DESIGN PROCEDURE
Input BCD Output Excess-3
A B C D w x y z z’s Karnaugh map
0 0 0 0 0 0 1 1 C
CD
0 0 0 1 0 1 0 0 AB 00 01 11 10
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0 00 1 1
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0 01 1 1
0 1 1 0 1 0 0 1 B
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
11 X X X X
A
1 0 0 1 1 1 0 0
1 0 1 0 x x x x 10 1 X X
1 0 1 1 x x x x
1 1 0 0 x x x x
D
1 1 0 1 x x x x
1 1 1 0 x x x x
z = D’
1 1 1 1 x x x x
11 April, 2023
 35

DESIGN PROCEDURE
• w = A + BC + BD = A + B (C + D) A
w

B
• x = B’C + B’D + BC’D’ = B’ (C+D) + C+D
B(C+D)

BC’D’ B’
B’(C+D)
C+D

x = B’ (C + D) + B (C+D)’ x
B
y = CD + C’D’ = CD + (C + D)’
B
• B(C+D)’

C+D (C+D)’

• z = D’ CD + (C+D)’
y

Simpler implementation!
C
• CD

SOP: 7 AND & 3 OR gates D D’

z

11 April, 2023
 36

DESIGN PROCEDURE
7 segment decoder a
• a, b, c, d, e, f, g are the outputs.
• Outputs are in segments. f b
g
• Each segment is turned on based
on the input number.
• Ex:
e c
• If BCD 5 is entered, then segments
(outputs) a, f, g, c, d should be d
turned on.

11 April, 2023
 37

DESIGN PROCEDURE
a

f b
a
b g
w 7 segment c
x d
decoder
y
z
e
f
e c
g

11 April, 2023
 38

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g a
0 0 0 0 1 1 1 1 1 1 0 0
0 0 0 1 0 1 1 0 0 0 0 1
0 0 1 0 1 1 0 1 1 0 1 2
3 f b
0 0 1 1
0 1 0 0
1
0
1
1
1
1
1
0
0
0
0
1
1
1 4 g
0 1 0 1 1 0 1 1 0 1 1 5
0 1 1 0 1 0 1 1 1 1 1 6
0 1 1 1
1 0 0 0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
7
8
e c
1 0 0 1 1 1 1 1 0 1 1 9
1 0 1 0 X X X X X X X
1 0 1 1
1 1 0 0
X
X
X
X
X
X
X
X
X
X
X
X
X
X
d
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
1 1 1 1 X X X X X X X
11 April, 2023
 39

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g a’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
a = w + y + x z + x’ z’
1 1 1 1 X X X X X X X
11 April, 2023
 40

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g b’s karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
b = w + w’x’ + y z + y’ z’
1 1 1 1 X X X X X X X
11 April, 2023
 41

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g c’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
c = w + x + z + y’
1 1 1 1 X X X X X X X
11 April, 2023
 42

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g d’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
d = w + yz’ + x’ y + x y’z + x’z’
1 1 1 1 X X X X X X X
11 April, 2023
 43

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g e’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
e = yz’ + x’z’
1 1 1 1 X X X X X X X
11 April, 2023
 44

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g f’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
f = w + xy’ + x z’ + y’z’
1 1 1 1 X X X X X X X
11 April, 2023
 45

DESIGN PROCEDURE
Input BCD 7 - segment
w x y z a b c d e f g g’s Karnaugh map
0 0 0 0 1 1 1 1 1 1 0 y
yz
0 0 0 1 0 1 1 0 0 0 0 wx 00 01 11 10
0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1 00 1 1
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 01 1 1 1
0 1 1 0 1 0 1 1 1 1 1 x
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
11 X X X X
w
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X 10 1 1 X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
z
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
g = w + xy’ + x z’ + x’y
1 1 1 1 X X X X X X X
11 April, 2023
4.4 BINARY ADDER -
SUBTRACTOR
 47

B I N A R Y A D D E R - S U BT R AC TO R
• The most basic arithmetic operation is the addition of two binary digits.

• Simple addition consists of 4 possible elementary operations:

– 0+0=0

– 0+1=1

– 1+0=1

– 1 + 1 = 10

• First 3 operations produce a sum of one digit.

• In the 4th operation, the binary sum consists of two digits.

11 April, 2023
 48

B I N A R Y A D D E R - S U BT R AC TO R
• The higher significant bit is called a carry.

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

half adder.

• One that performs the addition of three bits (two significant bits and a
previous carry) is a full adder.
• Two half adders can be employed to implement a full adder.

11 April, 2023
 49

B I N A R Y A D D E R - S U BT R AC TO R
Half Adder x y C S
0 0 0 0
• Adds 2 bits
0 1 0 1
– 2 inputs
1 0 0 1
– 2 outputs
1 1 1 0
• Produces SUM and CARRY.
S = x’y + xy’
C = xy
x SUM (S)
HA
y CARRY (C)

11 April, 2023
 50

B I N A R Y A D D E R - S U BT R AC TO R
Half Adder
x
S = x’y + xy’ y’

C = xy S
x
S
y
x’
y
C

x
C
y (b) S = x⊕y, C = xy

(a) S = xy’+x’y, C = xy

11 April, 2023
 51

B I N A R Y A D D E R - S U BT R AC TO R
Full Adder x y z C S
0 0 0 0 0
• Adds 3 bits
0 0 1 0 1
– 3 inputs
0 1 0 0 1
– 2 outputs
0 1 1 1 0
• Produces SUM and CARRY. 1 0 0 0 1
x 1 0 1 1 0
SUM (S)
y FA
z CARRY (C) 1 1 0 1 0
1 1 1 1 1
S = x’y’z + x’yz’ + xy’z’ + xyz
C = x’yz + xy’z + xyz’ + xyz

11 April, 2023
 52

B I N A R Y A D D E R - S U BT R AC TO R
S = x’y’z + x’yz’ + xy’z’ + xyz C = x’yz + xy’z + xyz’ + xyz

S = x ⊕y ⊕ z

yz y yz y
x 00 01 11 10 x 00 01 11 10
m0 m1 m3 m2 m0 m1 m3 m2
0 0
1 1 1
m4 m5 m7 m6 m4 m5 m7 m6
x 1 x 1
1 1 1 1 1

z z
C = xy + xz + yz

11 April, 2023
 53

B I N A R Y A D D E R - S U BT R AC TO R
Full adder implementation: x’
y’
z

• S = x’y’z + x’yz’ + xy’z’ + xyz x’

y
z’

S = x ⊕y ⊕ z
x
•
S
x
y S
y’
z’ S

• C = x’yz + xy’z + xyz’ + xyz

z

x x
y
y x
C = xy + xz + yz
z

•
x
z y y

x
z
x
y C
z

x
C y
z
z
C

11 April, 2023
 54

B I N A R Y A D D E R - S U BT R AC TO R
• Implementation of Full Adder with Two Half Adders and an OR gate

11 April, 2023
 55

B I N A R Y A D D E R - S U BT R AC TO R
Binary Adder:

• Digital circuit that produces the arithmetic sum of two binary numbers.

• It can be constructed with full adders connected in cascade.

• The output carry from each full adder connected to the input carry of
the next full adder in the chain. x3x2x1x0 y3y2y1y0

c3 c2 c1 .
+ x3 x2 x1 x0 Cy Binary Adder C0
+ y3 y2 y1 y0
────────
Cy S3 S2 S1 S0 S3S2S1S0
11 April, 2023
 56

B I N A R Y A D D E R - S U BT R AC TO R
Binary Adder: 4-bit Ripple Carry Adder

x3 x2 x1 x0
y3 y2 y1 y0
0

FA FA FA FA

C4 C3 C2 C1
S3 S2 S1 S0
MSB LSB
11 April, 2023
 57

B I N A R Y A D D E R - S U BT R AC TO R
• The S outputs generate the required sum bits.

• An n-bit adder requires n full adders with each output carry connected
to the input carry of the next higher-order full adder.

• Example: A = 1011 and B = 0011.

Subscript i: 3 2 1 0
Input carry 0 1 1 0 Ci
Augend 1 0 1 1 Ai
Addend 0 0 1 1 Bi
Sum 1 1 1 0 Si
Output Carry 0 0 1 1 Ci+1

11 April, 2023
 58

B I N A R Y A D D E R - S U BT R AC TO R
Binary Adder: 4-bit Ripple Carry Adder

1 0 1 1
0 0 1 1
0

FA FA FA FA

0 0 1 1
1 1 1 0
MSB LSB
11 April, 2023
 59

B I N A R Y A D D E R - S U BT R AC TO R

11 April, 2023
 60

B I N A R Y A D D E R - S U BT R AC TO R

11 April, 2023
 61

B I N A R Y A D D E R - S U BT R AC TO R

11 April, 2023
 62

B I N A R Y A D D E R - S U BT R AC TO R
Carry propagation
• The addition of two binary numbers in parallel implies that all the bits of the
augend and addend are available at the same time.
• Signals must propagate through the gates before the correct output sum is
available in the output terminals.
• The total propagation time
= propagation delay of a typical gate x the number of gate levels in the circuit.

• Longest propagation delay time in an adder is the time it takes the

carry to propagate through the full adders.

11 April, 2023
 63

B I N A R Y A D D E R - S U BT R AC TO R
Carry propagation

• Since each bit of the sum output depends on the value of the input
carry, the value of Si in any given stage in the adder will in its steady
state final value only after the input carry to that stage has been
propagated.

11 April, 2023
 64

B I N A R Y A D D E R - S U BT R AC TO R
• Consider output S3. Inputs A3 and B3 are available as soon as
input signals are applied to the adder.
• However, input carry C3 does not settle to its final value until C2 is
available from the previous stage.
• Similarly, C2 has to wait for C1 and so on down to C0.
• Thus, only after the carry propagates and ripples through all
stages will the last output S3 and carry C4 settle to their final
correct value.

11 April, 2023
 65

B I N A R Y A D D E R - S U BT R AC TO R
Carry propagation

• The number of gate levels for the carry propagation can be found from
the circuit of the full adder.

Ai Pi
Bi Si

Gi
Ci+1
Ci

11 April, 2023
 66

B I N A R Y A D D E R - S U BT R AC TO R
Carry propagation
• The signal from the input carry Ci to the output carry Ci+1, propagates
through
– an AND gate and an OR gate,
– which constitute two gate levels.

• If there are 4 full adders in the adder, the output carry C4 would have
– 2 x 4 = 8 gate levels from C0 to C4.

• For an n-bit adder, there are 2n gate levels for the carry to
propagate from input to output.

11 April, 2023
 67

B I N A R Y A D D E R - S U BT R AC TO R
• The carry propagation time is a limiting factor on the speed with which
two numbers are added.

• Since all other arithmetic operations are implemented by successive

additions, the time consumed during the addition process is very critical.

• Reduce the carry propagation delay

– Employ faster gates

– Look-ahead carry (more complex mechanism, yet faster)

11 April, 2023
 68

B I N A R Y A D D E R - S U BT R AC TO R
• Consider • Two new variables:

– Pi = Ai ⊕ Bi
Ai Pi
Bi Si

Gi
– Gi = Ai . Bi
Ci+1

• Sum = Pi ⊕ Ci
Ci

• Carry = Gi + Pi . Ci

11 April, 2023
 69

B I N A R Y A D D E R - S U BT R AC TO R
• Gi is called carry generate
– Produces a carry of 1 when both Ai and Bi are 1, regardless of the
input carry.

• Pi . Ci is called a carry propagate

– It is the term associated with the propagation of the carry from Ci to
Ci + 1.

11 April, 2023
 70

B I N A R Y A D D E R - S U BT R AC TO R
• Boolean functions for the carry outputs of each stage:
– C0 = input carry

– C1 = G0 + P0 . C0

– C2 = G1 + P1. C1 = G1 + P1 (G0 + P0 . C0)

= G1 + P1 . G0 + P1 . P0 . C0

– C3 = G2 + P2 . C2 = G2 + P2 (G1 + P1 . G0 + P1 . P0 . CO)

= G2 + P2 . G1 + P2 . P1 . G0 + P2 . P1 . P0 . C0

11 April, 2023
 71

B I N A R Y A D D E R - S U BT R AC TO R
• Carry Lookahead Generator

• C3 does not have to wait for C2 and

C1 to propagate.
• C3 is propagated at the same time as
C1 and C2.
• This gain in speed of operation is
achieved at the expense of
additional complexity

11 April, 2023
 72

B I N A R Y A D D E R - S U BT R AC TO R
• 4-Bit Adder with Carry Lookahead Generator
• Each sum output requires two XOR gates.
• First XOR gate generates the Pi
• AND gate generates the Gi variable.
• Carries are propagated through CLA Gen.
and applied as an input to the second
XOR gate.
• All output carries are generated after a
delay though two levels of gates. S1
through S3 have equal propagating delay
times.
11 April, 2023
 73

B I N A R Y A D D E R - S U BT R AC TO R
Binary Subtractor
• The subtraction of unsigned binary numbers can be done most
conveniently by means of complements.

• A – B can be performed by taking 2’s complement of B and adding it to A.

• 2’s complement can be done by taking 1’s complement and adding 1.

• 1’s complement can be implemented with inverters.

11 April, 2023
 74

B I N A R Y A D D E R - S U BT R AC TO R
Binary Subtractor
• Circuit of subtractor consist of:
– An adder
– Inverters

• The input carry C0 = 1 when performing subtraction

• The operation performed becomes:
– A + 1’s complement of B + 1 = A + 2’s complement of B.
– A – B = A + (-B) = A +B’ + 1.
• For unsigned numbers,
– A – B if A ≥ B or 2’s complement of (B – A) if A < B.

11 April, 2023
 75

B I N A R Y A D D E R - S U BT R AC TO R
• XOR gate combines addition and
B3 A3 B2 A2 B1 A1 B0 A0 subtraction into one circuit with
common binary adder.
M

• Mode input M controls the

C
C4
FA
C3
FA
C2
FA
C1
FA
C0 operation.
– M = 0 = Addition.

V
S3 S2 S1 S0 – M = 1 = Subtraction.

11 April, 2023
 76

B I N A R Y A D D E R - S U BT R AC TO R
• When M = 0 (Addition).
B3 A3 B2 A2 B1 A1 B0 A0 – B ⊕ 0 = B.
M – Full adders receive the value of B

– C0 = 0.

– Circuit performs A + B.
C4 C3 C2 C1 C0
C FA FA FA FA
• When M = 1 (Subtraction).

S3 S2
– B ⊕ 1 = B’.
S1 S0
V
– C0 = 1.

– Circuit performs A + B’ + 1
XOR with output V is for detecting an overflow.

11 April, 2023
 77

B I N A R Y A D D E R - S U BT R AC TO R
Overflow (if the sum of two n digit numbers à occupies n+1 digits)

1 n=1 1-bit register

+ 1 n=1 1-bit register
1 0 n=2 2-bit register
• There is a need for an overflow detection.
• The detection of an overflow after addition of two binary numbers depends
on whether the number is to be:
– Signed
– Unsigned

11 April, 2023
 78

B I N A R Y A D D E R - S U BT R AC TO R
Overflow
• Signed

– Left most bit represents the sign bit.

– Negative numbers are in 2’s complement format.

– Sign bit treated as part of the number and the end carry does not
indicate an overflow.

11 April, 2023
 79

B I N A R Y A D D E R - S U BT R AC TO R
Overflow
• Unsigned
– When added, overflow is detected from the end carry out of the most
significant position.

• Overflow cannot occur if positive and negative numbers are added.

• Overflow occurs if both numbers are positive or negative.

11 April, 2023
 80

B I N A R Y A D D E R - S U BT R AC TO R
Overflow
• Ex: +70 , +80 in 8-bit registers.

• 8-bit register = 28 = 256.

– (-128) to (+127)

0 1 0 0 0 0 0 0
+70 0 1 0 0 0 1 1 0
+ +80 0 1 0 1 0 0 0 0
+150 1 0 0 1 0 1 1 0

11 April, 2023
 81

B I N A R Y A D D E R - S U BT R AC TO R
Overflow
0 1 0 0 0 0 0 0
+70 0 1 0 0 0 1 1 0
+ +80 0 1 0 1 0 0 0 0
+150 1 0 0 1 0 1 1 0

• 8-bit result that should have been positive has a negative sign bit and vice versa.
• If carry out of sign bit is taken as the sign bit of the result then the 9-bit answer will be
correct.
• Since it can not be accommodated within 8-bit register, then there is an overflow.

11 April, 2023
 82

B I N A R Y A D D E R - S U BT R AC TO R
• Overflow can be detected by:
– Observing the carry into the sign bit.

– Observing the carry out of the sign bit.

• If they are not equal, an overflow has occurred.

• If two carries are applied to an XOR gate overflow is detected.

• When the output is 1.

11 April, 2023
 83

B I N A R Y A D D E R - S U BT R AC TO R
B3 A3 B2 A2 B1 A1 B0 A0

• If two binary numbers are unsigned M

– the C bit detects

C4 C3 C2 C1 C0
C
a carry after addition or
FA FA FA FA

•
• a borrow after subtraction. V
S3 S2 S1 S0

• If the numbers are signed, then the V bit detects an overflow.

– If V = 0 for addition/substraction, then no overflow.
• The n-bit result is correct.

– If V = 1, then result contains n+1 bits only the right most n-bits of the number.
– Overflow has occurred. The (n+1)th bit is the actual sign and has been shifted out
of position.

11 April, 2023
4.5 DECIMAL
ADDER
 85

DECIMAL ADDER
• Computers or calculators that perform arithmetic operations
directly in the decimal number system à represent decimal
numbers in binary coded form.

• An adder for such a computer à must employ arithmetic circuits

that accept coded decimal numbers and present results in the
same code.

• A decimal adder requires a minimum of 9 inputs and 5 outputs,

since 4 bits are required to code each decimal digit and the
circuit must have an input and output carry.

11 April, 2023
 86

DECIMAL ADDER
• Decimal adder for the BCD code à BCD Adder

• Consider the arithmetic addition of two decimal digits in BCD

and an input carry.

• In BCD each input digit does not exceed 9

• Output sum cannot be greater than 9 + 9 + 1 = 19.

– 1 is an input carry.

11 April, 2023
 87

DECIMAL ADDER
• Suppose:
– Two BCD digits applied to a 4-bit binary adder.
c3 c2 c1 .
+ x3 x2 x1 x0
+ y3 y2 y1 y0
────────
Cy S3 S2 S1 S0

– The output produces a result that ranges from 0 through 19.

11 April, 2023
 88

DECIMAL ADDER
X +Y x3 x2 x1 x0 y3 y2 y1 y0 Sum Cy S3 S2 S1 S0
0+0 0 0 0 0 0 0 0 0 =0 0 0 0 0 0
0+1 0 0 0 0 0 0 0 1 =1 0 0 0 0 1
0+2 0 0 0 0 0 0 1 0 =2 0 0 0 1 0

0+9 0 0 0 0 1 0 0 1 =9 0 1 0 0 1
1+0 0 0 0 1 0 0 0 0 =1 0 0 0 0 1
1+1 0 0 0 1 0 0 0 1 =2 0 0 0 1 0

1+8 0 0 0 1 1 0 0 0 =9 0 1 0 0 1
1+9 0 0 0 1 1 0 0 1 =A 0 1 0 1 0 Invalid Code
2+0 0 0 1 0 0 0 0 0 =2 0 0 0 1 0

9+9 1 0 0 1 1 0 0 1 = 18 1 0 0 1 0 Wrong BCD Value

11 April, 2023 0001 1000

 89

DECIMAL ADDER
X +Y x3 x2 x1 x0 y3 y2 y1 y0 Sum Cy S3 S2 S1 S0 Required BCD Output Value

9+0 1 0 0 1 0 0 0 0 =9 0 1 0 0 1 0 0 0 0 1 0 0 1 =9
9+1 1 0 0 1 0 0 0 1 = 10 0 1 0 1 0 0 0 0 1 0 0 0 0 = 16 û
9+2 1 0 0 1 0 0 1 0 = 11 0 1 0 1 1 0 0 0 1 0 0 0 1 = 17 û
9+3 1 0 0 1 0 0 1 1 = 12 0 1 1 0 0 0 0 0 1 0 0 1 0 = 18 û
9+4 1 0 0 1 0 1 0 0 = 13 0 1 1 0 1 0 0 0 1 0 0 1 1 = 19 û
9+5 1 0 0 1 0 1 0 1 = 14 0 1 1 1 0 0 0 0 1 0 1 0 0 = 20 û
9+6 1 0 0 1 0 1 1 0 = 15 0 1 1 1 1 0 0 0 1 0 1 0 1 = 21 û
9+7 1 0 0 1 0 1 1 1 = 16 1 0 0 0 0 0 0 0 1 0 1 1 0 = 22 û
9+8 1 0 0 1 1 0 0 0 = 17 1 0 0 0 1 0 0 0 1 0 1 1 1 = 23 û
9+9 1 0 0 1 1 0 0 1 = 18 1 0 0 1 0 0 0 0 1 1 0 0 0 = 24 û
+6
11 April, 2023
 90

DECIMAL ADDER
• The problem is to find a rule by which the binary sum is to be
converted to the correct BCD digit representation of the number
in the BCD sum.

• Binary sum à BCD sum

11 April, 2023
 91

DECIMAL ADDER

K: binary sum
carry,
C: BCD sum
(output) carry

Add binary 6 (0110)

for correction

11 April, 2023
 92

DECIMAL ADDER
• In examining the contents of the table;
– When the binary SUM ≤ 1001, the corresponding BCD number is
identical.
– When the binary SUM >1001, the BCD number is invalid.
– The addition of 6 (0110) is required.
– Correction is needed when K = 1.
– Correction is needed from 1010 – 1111.
• 𝑍! = 1,
• Either 𝑍" or 𝑍# must = 1 to distinguish 1000 and 1001

11 April, 2023
 93

DECIMAL ADDER
Z8 Z4 Z2 Z1 Err 𝑍!
Z2Z0
0 0 0 0 0 Z8Z4 00 01 11 10
. . 00
. .
. . 01

1 0 0 0 0 𝑍"

1 0 0 1 0
11 1 1 1 1
𝑍#
1 0 1 0 1 10 1 1
1 0 1 1 1
1 1 0 0 1
Z0
1 1 0 1 1
1 1 1 0 1 Err = Z8Z4 + Z8Z2
1 1 1 1 1
Output Carry C= K + Z8Z4+ Z8Z2
11 April, 2023
 94

DECIMAL ADDER
• When Output carry = 0,
– Nothing is added.

• When Output carry = 1,

– add 0110 to the binary sum.
– provide an output carry for the
next stage.
– K=1 à C=1
– Ignore the carry of the bottom
adder.

11 April, 2023 Output Carry C= K + Z8Z4+ Z8Z2

4.6 BINARY
MULTIPLIER
 96

B I N A R Y M U LT I P L I E R
• Consider two 2-bit numbers
Multiplicand
bits
x Multiplier
bits
First partial product
(AND gate)
+ Second partial product
(AND gate)
Product

11 April, 2023
 97

B I N A R Y M U LT I P L I E R
• For more bits;
– A bit of multiplier is ANDed with each bit of multiplicand in as many
levels as there are bits.

– The binary output of AND gate in each level is added with the partial
product of previous level.

– For J multiplier bits and K multiplicand bits we need

• J x K AND gates

• J – 1 K-bit adders

11 April, 2023
 98

B I N A R Y M U LT I P L I E R
• A multiplier circuit multiplies a binary number with four bits
(B3B2B1B0) by a number represented by three bits (A2A1A0).

J x K=3 x 4=12 AND gates

J -1 = 2 K-bit (4-bit) adders

11 April, 2023
4.7 MAGNITUDE
COMPARATOR
 100

M AG N I T U D E CO M PA R ATO R
• Compare two numbers (A and B)

• 3 outputs <, =, >

– A > B, A = B, A<B

• Consider comparison of a 4-bit number to another 4-bit number

A3A2A1A0 B3B2B1B0
– A = A3 A2 A1 A0

– B = B3 B2 B1 B0 Magnitude
Comparator

A>B A=B A<B

11 April, 2023
 101

M AG N I T U D E CO M PA R ATO R
• A = B if:
– A3 = B3 AND A2 = B2 AND A1 = B1 AND A0 = B0
Ai Bi xi (A = B) x3 = A3’ . B3’ + A3 . B3
0 0 1
x2 = A2’ . B2’ + A2 . B2
0 1 0
x1 = A1’ . B1’ + A1 . B1
1 0 0
1 1 1 x0 = A0’ . B0’ + A0 . B0

xi = Ai’ . Bi’ + Ai . Bi
x = x3 . x2 . x1 . x0 = (A = B) à equal to 1 if all pairs of digits are equal!
11 April, 2023
 102

M AG N I T U D E CO M PA R ATO R
• A > B if
– Ai = 1 and Bi = 0 start from the MSB
Ai Bi yi (A > B) y3 = A3 . B3’
0 0 0
y2 = x3 . A2 . B2’
0 1 0
y1 = x3 . x2 . A1 . B1’
1 0 1
1 1 0 y0 = x3 . x2 . x1 . A0 . B0’

yi = Ai . Bi’
y = y3 + y2 + y1 + y0 = (A > B)
11 April, 2023
 103

M AG N I T U D E CO M PA R ATO R
• A < B if
– Ai = 0 and Bi = 1
Ai Bi zi (A < B) z3 = A3’ . B3
0 0 0
z2 = x3 . A2’ . B2
0 1 1
z1 = x3 . x2 . A1’ . B1
1 0 0
1 1 0 z0 = x3 . x2 . x1 . A0’ . B0

zi = Ai’ . Bi
z = z3 + z2 + z1 + z0 = (A < B)
11 April, 2023
 10
4

M AG N I T U D E CO M PA R ATO R

Complement düzelt
11 April, 2023
 105

M AG N I T U D E CO M PA R ATO R

11 April, 2023
4.8 DECODERS
 107

D E CO D E R S
• Discrete quantities of information are represented in digital
systems by binary codes.

• A binary code of n bits is capable of representing up to 2n distinct

elements of coded information.

• A decoder is a combinational circuit that converts binary

information from n input lines to a maximum of 2n unique
output lines.

11 April, 2023
 108

D E CO D E R S
Only one lamp
• Example: 2-bit binary number
will turn on!

1
0
x0 10 0
1
Binary
0
1
x1 10 Decoder
0
1

11 April, 2023
 109

D E CO D E R S
• 2-to-4 Line Decoder à generates minterms D3
D3

Decoder
A D2 D2
Binary D1
B D0 D1

A B D0 D1 D2 D3 D0
0 0 1 0 0 0 D0= A’B’
0 1 0 1 0 0 D1= A’B A
1 0 0 0 1 0 D2= AB’ B
1 1 0 0 0 1 D3= AB
11 April, 2023
 110

D E CO D E R S
• 3-to-8 Line Decoder (Binary to Octal Conversion)
x y z D0 D1 D2 D3 D4 D5 D6 D7
D7
0 0 0 1 0 0 0 0 0 0 0
D6
0 0 1 0 1 0 0 0 0 0 0
Decoder D5
0 1 0 0 0 1 0 0 0 0 0
x D4
Binary

0 1 1 0 0 0 1 0 0 0 0
y D3
1 0 0 0 0 0 0 1 0 0 0
z D2
1 0 1 0 0 0 0 0 1 0 0
D1
1 1 0 0 0 0 0 0 0 1 0
D0
1 1 1 0 0 0 0 0 0 0 1
11 April, 2023
 111

D E CO D E R S
• 3-to-8 Line Decoder (Binary to Octal Conversion)
x y z D0 D1 D2 D3 D4 D5 D6 D7
0 0 0 1 0 0 0 0 0 0 0 D0= x’ y’ z’
0 0 1 0 1 0 0 0 0 0 0 D1= x’ y’ z
0 1 0 0 0 1 0 0 0 0 0 D2= x’ y z’
0 1 1 0 0 0 1 0 0 0 0 D3= x’ y z
1 0 0 0 0 0 0 1 0 0 0 D4= x y’ z’
1 0 1 0 0 0 0 0 1 0 0 D5= x y’ z
1 1 0 0 0 0 0 0 0 1 0 D6= x y z’
1 1 1 0 0 0 0 0 0 0 1 D7 = x y z

11 April, 2023
 112

D E CO D E R S
• 3-to-8 Line Decoder (Binary to Octal Conversion)
D7 D7 = x y z
D6 D6= x y z’
D5 D5= x y’ z
D4 D4= x y’ z’
D3 D3= x’ y z
D2 D2= x’ y z’
D1 D1= x’ y’ z
D0 D0= x’ y’ z’

x
y
z
11 April, 2023
 113

D E CO D E R S
• Some decoders are with NAND gates.

• NAND becomes more economical to generate the decoder

minterms in their complemented form.

• Decoders include one or more ENABLE inputs to control the

circuit operation.

11 April, 2023
 114

D E CO D E R S
• 2-to-4 Line Decoder with ENABLE input à E=1 enables outputs
D3

Decoder
A D2
D3
B Binary D1 D2
E D0
D1
E A B D0 D1 D2 D3
0 X X 0 0 0 0 D0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0 A
B
1 1 1 0 0 0 1 E
11 April, 2023
 115

D E CO D E R S
• 2-to-4 line decoder with ENABLE input can function as a
demultiplexer.

• A demultiplexer is a circuit that receives information from single

line and directs it to one of 2n possible output lines.

• The selection of a specific output is controlled by the bit

combination of n selected lines.

11 April, 2023
 11
6

D E CO D E R S
• The decoder can function as D3

1-to-4 line demultiplexer. D2

– E is taken as a data input line.
D1
– A and B are taken as the selection
inputs. D0
E A B D0 D1 D2 D3
1/0 0 0 E 0 0 0
1/0 0 1 0 E 0 0 A
B
1/0 1 0 0 0 E 0
E
1/0 1 1 0 0 0 E

11 April, 2023
 117

D E CO D E R S
• Decoders with enable inputs can be connected together to form a larger
decoder circuit.

• 3-to-8 line decoders with enable inputs can be connected to form a 4-to-
16 line decoder.

11 April, 2023
 11
8

D E CO D E R S
• When w = 0, top decoder
enabled and other disabled. x
3x8
y D0 t o D7
Decoder

• The bottom decoder outputs all z

0’s. w

• The top eight outputs generate

minterms 0 to 7. 3x8
D8 t o D15
Decoder

• When w = 1, bottom decoder

enabled and other disabled.

• We obtain minterms 8 to 15.

11 April, 2023
 119

D E CO D E R S
Active – High Active – Low D3

D3 D3

Decoder

Decoder
A A D2
D2 D2
Binary

Binary
D1 D1 D1
B D0 B D0
D0
A B D0 D1 D2 D3 A B D0 D1 D2 D3
0 0 1 0 0 0 0 0 0 1 1 1 A
B
0 1 0 1 0 0 0 1 1 0 1 1
1 0 0 0 1 0 1 0 1 1 0 1
1 1 0 0 0 1 1 1 1 1 1 0
11 April, 2023
 120

D E CO D E R S
• A decoder provides the 2n minterms of n input variables.

• Since any Boolean function can be expressed in sum of minterms

– Use decoder to generate the minterms
– An external OR gate to form the logical sum.

• Any combinational circuit with n inputs and m outputs can be

implemented with an n-to-2n line decoder and m OR gates.

11 April, 2023
 12
1

D E CO D E R S
Example: Full Adder

S(x, y, z) = ∑(1, 2, 4, 7)

C(x, y, z) = ∑(3, 5, 6, 7)

11 April, 2023
 12
2

D E CO D E R S
• Draw a logic diagram constructing a 3x8 decoder with enable function
(active-high), using a pair of 2x4 decoders; also draw a truth table for
this.

11 April, 2023
 12
3

D E CO D E R S

11 April, 2023
4.9 ENCODERS
 125

E N CO D E R S
• An encoder is a digital circuit that performs the inverse operation
of a decoder.

• An encoder has 2n (or fewer) input lines and n output lines.

• The output lines generate the binary code corresponding to the

input value.

11 April, 2023
 126

E N CO D E R S
• Example: 4-to-2 Binary Encoder
Only one switch should be
activated at a time
x1
x4 x3 x2 x1 y1 y0
y1
x2 0 0 0 1 0 0
Binary y0
0 0 1 0 0 1
x3 Encoder
0 1 0 0 1 0
x4
1 0 0 0 1 1

11 April, 2023
 127

E N CO D E R S
• Example: Octal-to-Binary Encoder
D7 D6 D5 D4 D3 D2 D1 D0 Y2 Y1 Y0
Y2= D7 +D6 +D5 +D4
0 0 0 0 0 0 0 1 0 0 0
Y1= D7 +D6 +D3 +D2
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0 Y0= D7 +D5 +D3 +D1
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1
11 April, 2023
 128

E N CO D E R S
• Example: Octal-to-Binary Encoder

D7
D7
D6 D6 Y2
D5 Y2= D7 +D6 +D5 +D4 D5
Y2
Encoder
D4
Binary

D4
Y1 Y1= D7 +D6 +D3 +D2 Y1
D3 D3
Y0 D2
D2 Y0= D7 +D5 +D3 +D1 D1
D1 D0 Y0
D0

11 April, 2023
 129

E N CO D E R S
• The encoder defined here has the limitation that only one input
can be active at any given time.

• If two inputs are active simultaneously, the output produces an

undefined combination.

• If D3 and D6 are 1 simultaneously, the output of the encoder will

be 111 à does not represent either binary 3 or binary 6.
Y2= D7 +D6 +D5 +D4

• Input priority can be considered. Y1= D7 +D6 +D3 +D2

Y0= D7 +D5 +D3 +D1

11 April, 2023
 130

E N CO D E R S
4-Input Priority Encoder

• Encoder circuit that includes the priority function.

• If two or more inputs are equal 1 at the same time,

– The input having the highest priority will take precedence.
Inputs Outputs
D3 V
D3 D2 D1 D0 x y V
Encoder
Priority

D2 0 0 0 0 X X 0
x 0 0 0 1 0 0 1
D1 y 0 0 1 X 0 1 1
D0 0 1 X X 1 0 1
1 X X X 1 1 1
11 April, 2023
 131

E N CO D E R S
4-Input Priority Encoder
Inputs Outputs
D3 D2 D1 D0 x y V Valid output = 1, when one or more inputs =1
0 0 0 0 X X 0
0 0 0 1 0 0 1
0 0 1 X 0 1 1
0 1 X X 1 0 1
1 X X X 1 1 1
• X’s in the output represent don’t care conditions.
• X’s in the input are useful for representing a truth table in
condensed form.

11 April, 2023
 13
2

E N CO D E R S

4-Input Priority Encoder • Truth table uses an X to

represent either 1 or 0.
Inputs Outputs
D3 D2 D1 D0 x y V • Example: X100 represents two
0 0 0 0 X X 0
0 0 0 1 0 0 1 minterms 0100 and 1100.
0 0 1 X 0 1 1
0 1 X X 1 0 1
1 X X X 1 1 1

11 April, 2023
 13
3

E N CO D E R S

4-Input Priority Encoder • According to the table:

– Higher the subscript number, the
Inputs Outputs
D3 D2 D1 D0 x y V higher the priority of the input.
0 0 0 0 X X 0 – Input D3 has the highest priority.
0 0 0 1 0 0 1
0 0 1 X 0 1 1 – When D3 = 1, the xy is 11 (binary 3),
0 1 X X 1 0 1 regardless of the values of the
1 X X X 1 1 1
other inputs.
– When D3 = 0 and D2 = 1, than the
output is 10 regardless of D1 and
D0.

11 April, 2023
 134

E N CO D E R S
4-Input Priority Encoder

• When each X in a row is replaced first by 0 and then by 1

– We obtain all 16 possible input combinations.

• 001X = 0010 and 0011

• 01XX = 0100 and 0101 and 0110 and 0111

• 1XXX = 1000 and 1001 and 1010 and 1011 and 1100 and 1101
and 1110 and 1111

11 April, 2023
 135

E N CO D E R S
4-Input Priority Encoder x’s K-MAP
Inputs Outputs D1D0 D1
D3 D2 D1 D0 x y V D3D2 00 01 11 10
0 0 0 0 X X 0
00 X 0 0 0
0 0 0 1 0 0 1
0 0 1 X 0 1 1 01 1 1 1 1
0 1 X X 1 0 1 D2
1 X X X 1 1 1 11 1 1 1 1
D3
10 1 1 1 1

D0

x = D2 + D3
11 April, 2023
 136

E N CO D E R S
4-Input Priority Encoder y’s K-MAP
Inputs Outputs D1D0 D1
D3 D2 D1 D0 x y V D3D2 00 01 11 10
0 0 0 0 X X 0
00 X 0 1 1
0 0 0 1 0 0 1
0 0 1 X 0 1 1 01 0 0 0 0
0 1 X X 1 0 1 D2
1 X X X 1 1 1 11 1 1 1 1
D3
10 1 1 1 1

D0

y = D 3 + D 1 D2 ’
11 April, 2023
 137

E N CO D E R S
4-Input Priority Encoder
Inputs Outputs
D3 D2 D1 D0 x y V
0 0 0 0 X X 0
0 0 0 1 0 0 1 V = D0 + D1 + D2 + D3
0 0 1 X 0 1 1
0 1 X X 1 0 1
1 X X X 1 1 1

11 April, 2023
 138

E N CO D E R S
4-Input Priority Encoder

• x = D2 + D3

• y = D3 + D1 D2 ’

• V = D0 + D1 + D2 + D3

11 April, 2023
 13
9

E N CO D E R S
Binary Binary
Encoder Decoder

D7 D7
D6 D6
D5 X D5
X D4
D4 Y
Y D3
D3 Z
Z D2
D2
D1 D1
D0 D0

11 April, 2023
 14
0

E N CO D E R S

11 April, 2023
 14
1

E N CO D E R S

11 April, 2023
4.10 MULTIPLEXERS
 14
3

M U LT I P L E X E R S
• A multiplexer (MUX) is a
combinational circuit that selects
binary information from one of A
B

MUX
many input lines and directs it to a QQ==B
CD
A
C
single output line.
D
• The selection of a particular input
line is controlled by a set of
S0 S1
selection lines. 1
0 01
• Normally, there are 2n input lines
and n selection lines.

11 April, 2023
 144

M U LT I P L E X E R S
• Consider 2-to-1 MUX
S0 A B Q A
AB
0 0 0 0 S0 00 01 11 10
A 0
MUX
Q==BA
Q m0 m1 m3 m2
B 1 0 0 1 0 0
0 0 1 1
0 1 0 1 m4 m5 m7 m6
S0 S0 1
0 1 1 1 0 1 1 0
1
0
1 0 0 0
B
1 0 1 1
1 1 0 0 Q = S0’ A + S0 B
1 1 1 1

11 April, 2023
 145

M U LT I P L E X E R S
• Consider 2-to-1 MUX

A 0
MUX
Q
B 1

S0
0

Q = S0’ A + S0 B

11 April, 2023
 146

M U LT I P L E X E R S
• 4-to-1 Multiplexer
A
S1 S0 Q
A
0 0 A B
B
MUX
Q
Q == B
CD
A
C 0 1 B C
Y

D 1 0 C
D
1 1 D
S1 S0
1
0 01

S1 S0

11 April, 2023
 147

M U LT I P L E X E R S
• Quadruple 2-to-1-line MUX A3
D3
A0 I0 A2

MUX
B0 D0 D2
I1
A1
S E D1
A1 A0
I0
MUX D0
B1 D1
I1
B3
S E
Multiple bit
A2 I0 B2
selection logic
MUX

B2 D2
I1
B1
S E
Selects one of
A3 I0 B0 two 4-bit sets.
MUX

B3 D3
I1 S=0 à select A
S
S=1 à select B
E S E
11 April, 2023
 148

M U LT I P L E X E R S
• Example: F(x, y) = ∑ (0, 1, 3)

x y F 1 I0
0 0 1 1 I1

MUX
D F
0 1 1 0 I2

1 0 0 1 I3
S1 S0
1 1 1
xy

11 April, 2023
 149

M U LT I P L E X E R S
• Boolean function implementation
– We have seen that a decoder can be used to implement Boolean
functions by employing external OR gates.

– Multiplexer is essentially a decoder that includes the OR gate within

the unit.

– The minterms of a function are generated in multiplexer by the

circuit associated with the selection inputs.

11 April, 2023
 150

M U LT I P L E X E R S
• Boolean function implementation
– This provides a method of implementing a Boolean function of n
variables with a multiplexer that has n – 1 selection inputs.

– The first n – 1 variables of the function are connected to the

selection inputs of the multiplexer.

– The remaining single variable of the function is used for the data
inputs.

11 April, 2023
 151

M U LT I P L E X E R S
• Example: F(x, y, z) = ∑(1, 2, 6, 7), implement with 8-to-1-line MUX.
x y z F 0 I0
0 0 0 0 1 I1
0 0 1 1 1 I2
0 I3
0 1 0 1
0 I4 MUX F
0 1 1 0
0 I5
1 0 0 0 1 I6
1 0 1 0 1 I7
1 1 0 1
S2 S1 S0
1 1 1 1
x y z
11 April, 2023
 152

M U LT I P L E X E R S
• Example: F(x, y, z) = ∑(1, 2, 6, 7), implement with 4-to-1-line MUX.
x y z F First n – 1 variables are connected to the selection

0 0 0 0 inputs of MUX. Remaining variable is used for data

0 0 1 1
F=z inputs.

0 1 0 1
z I0
0 1 1 0
F = z’ z’ I1 MUX
I2 F
0 4x1
1 0 0 0
F=0 1 I3
1 0 1 0 S1 S0
1 1 0 1
F=1
1 1 1 1 x y
11 April, 2023
 153

M U LT I P L E X E R S
• Example: F(A, B, C, D) = ∑(1,3,4,11,12,13,14,15)
A B C D F
0 0 0 0 0
F=D D I0
0 0 0 1 1
0 0 1 0 0
F=D
D I1
0 0 1 1 1
0 1 0 0 1 D’ I2
F = D’
0 1 0 1 0
0 I3 MUX
0 1 1 0 0
F=0 F
0
1
1
0
1
0
1
0
0
0
0 I4 8x1
F=0
1
1
0
0
0
1
1
0
0
0
D I5
1 0 1 1 1 F=D 1 I6
1 1 0 0 1
1 1 0 1 1 F=1 1 I7
1 1 1 0 1 S2 S1 S0
F=1
1 1 1 1 1
A B C
11 April, 2023
 154

M U LT I P L E X E R S
• 8-to-1 MUX using Dual 4-to-1 MUX
I0 I0
I1 I1
I2 I2 MUX Y
I3 I3 S1 S0
I0
MUX Y Y
I1 S
I4 I0
I5 I1
I6 I2 MUX Y
I7 I3 S1 S0

S2 S1 S0
1 0 0
11 April, 2023
 15
5

D E M U LT I P L E X E R S
Y3 Y3
Y2
I DeMUX Y
1 Y2
S1 S0 Y0 I
Y1

Y0
S1 S0 Y3 Y2 Y1 Y0
0 0 0 0 0 I
0 1 0 0 I 0
1 0 0 I 0 0 S1
1 1 I 0 0 0 S0

11 April, 2023
 15
6

D E M U LT I P L E X E R
Y3 D3

Decoder
Y2 A D2

Binary
I DeMUX Y1 B D1
Y0 E D0
S1 S0 Conceptual
similarity E A B Y3 Y2 Y1 Y0
S1 S0 Y3 Y2 Y1 Y0 0 X X 0 0 0 0

0 0 0 0 0 I 1 0 0 0 0 0 1

0 1 0 0 I 0 1 0 1 0 0 1 0

1 0 0 I 0 0 1 1 0 0 1 0 0

1 1 I 0 0 0 1 1 1 1 0 0 0

11 April, 2023
 157

M U LT I P L E X E R S
• A multiplexer can be constructed with three – state gates.
• A three – state gate is a digital circuit that exhibits three states.
• Two of the states are signals equivalent to logic 1 and 0.
• The third state is high – impedance state.
• High – impedance state behaves like an open circuit.
– The output appears to be disconnected.
– The circuit has no logic significance.
– The circuit connected to the output is not affected by inputs to the gate.

11 April, 2023
 158

M U LT I P L E X E R S
• Three – state gates may perform any conventional logic such as AND or
NAND.

• The most commonly used is the buffer gate.

• The high – impedance state of a three – state gate provides a special

feature not available in other gates.
• Large number of three – state gate outputs can be connected with wires
to form a common line without endangering loading effects.

11 April, 2023
 159

M U LT I P L E X E R S
• Three state gates
– Tri-state buffer C A Y
0 x Hi-Z
A Y
1 0 0
1 1 1
C

– Tri-state inverter
A Y

C
11 April, 2023
 160

M U LT I P L E X E R S
• Three state gates
A C D Y
Y 0 0 Hi-Z
C
B 0 1 B
Outputs can be 1 0 A
D connected togeter
1 1 ?
A
C A if C = 1
Y= Not Allowed
B if C = 0
B
C: select
2-to-1 MUX
11 April, 2023
 16
1

M U LT I P L E X E R S
• 4-to-1 MUX
I3

I2
Y

No more than one I1

buffer may be active
at any given time I0
Y3

Decoder
S1 I1 Binary Y2
S0 I0 Y1
E E Y0

11 April, 2023
 16
2

M U LT I P L E X E R S

11 April, 2023
 16
3

H O M E WO R K 3
1) For the parallel adder in Figure, determine the complete sum by analysis of
the logical operation of the circuit. Verify your result by longhand addition of the
two input numbers.

11 April, 2023
 16
4

H O M E WO R K 3
2) Implement the Boolean function F(A,B,C)= ∑(2, 3, 4, 7) with a 4-to-1-line
multiplexer.

3) A 7-segment decoder/driver drives the display given below. If the waveforms

are applied as indicated, determine the sequence of digits that appears on the
display

11 April, 2023