1

CHAPTER 4
COMBINATIONAL
LOGIC
This chapter outlines the formal procedures for
analysis and design of combinational circuits.
Adders and Code converters introduced as design
examples. Frequently used digital logic functions
such as parallel adders and subtractors, decoders,
encoders, and multiplexers are explained and use in
design of combinational circuits is illustrated.
 2

4.1 Introduction
• There are two types of Logic Circuits:
• Combinational
• Sequential

• Combinational circuits consist of logic gates whose output

at any time is function of the present inputs only.

• Sequential circuits along with logic gates use storage

elements. The value stored in these elements is due to a
previous combination of inputs. Thus the present output of
a sequential circuits depends upon the present and the
past inputs.
 3

4.2 Combinational Circuits

• A combinational circuit consists of input variables, logic gates and
output variables.

• For n input variables there will be a total of 2 n input combinations

and the pattern of m outputs w.r.t the different combination can be
listed in the form of a truth table.

• A combinational circuit can be represented by a truth table having

n inputs & m outputs or it can be represented by a Boolean
function having m equations one for each output variable.
 4

4.2 Combinational Circuits

• In Chapter 1, we learned about binary numbers and
binary codes that represent discrete quantities of
information.

• In Chapter 2, we learned Boolean Algebra as a way to

express logic functions algebraically.

• In Chapter 3, we learned how to simplify Boolean

functions to achieve economical (simpler) gate
implementations.
 5

4.2 Combinational Circuits

• In this Chapter, we will address two tasks:
• Analyze behavior of a given logic circuit
• Synthesize a circuit that will have a given behavior

• In addition to that, we will study some circuits that are

extensively used, are most important standard circuits
e.g. adders, subtractors, comparators, decoders,
encoders and multiplexers and are also now available in
single chip packages.
 6

4.3 Analysis Procedure

• The analysis starts with a given logic diagram and culminates with
• a set of Boolean functions,
• a Truth Table,
• or, possibly, an explanation of the circuit operation

• The first step in the analysis is to make sure that the given circuit
is combinational and not sequential.

• The diagram of a combinational circuit has logic gates with no

feedback paths or memory elements.

• A feedback path is a connection from the output of one gate to the

input of a second gate whose output forms part of the input to the
first gate.
 7

4.3 Contd. (Boolean Functions)

• To obtain the output Boolean functions from a logic diagram,
we proceed as follows: Illustrate with example
1. Label all gate outputs that are a function of input variables
with arbitrary symbols—but with meaningful names.
Determine the Boolean functions for each gate output.
2. Label the gates that are a function of input variables and
previously labeled gates with other arbitrary symbols. Find
the Boolean functions for these gates.
3. Repeat the process outlined in step 2 until the outputs of
the circuit are obtained.
4. By repeated substitution of previously defined functions,
obtain the output Boolean functions in terms of input
variables.
 8

4.3 Contd. (Truth Table)

• To obtain the truth table directly from the logic diagram
without going through the derivations of the Boolean
functions, we proceed as follows: Illustrate with example
1. Determine the number of input variables in the circuit.
For n inputs, form the 2n possible input combinations
and list the binary numbers from 0 to (2 n - 1) in a table.
2. Label the outputs of selected gates with arbitrary
symbols.
3. Obtain the truth table for the outputs of those gates
which are a function of the input variables only.
4. Proceed to obtain the truth table for the outputs of those
gates which are a function of previously defined values
until the columns for all outputs are determined.
 9

Solve end of chapter

problems
(Boolean Function & Truth Table
for Figures P4.1,P4.2)
 10

4.4 Design Procedure

• The design of combinational circuits starts from the
specification of the design objective and culminates in a logic
circuit diagram or a set of Boolean functions from which the
logic diagram can be obtained.
• The procedure involves the following steps:
1. From the specifications of the circuit, determine the required
number of inputs and outputs and assign a symbol to each.
2. Derive the truth table that defines the required relationship
between inputs and outputs.
3. Obtain the simplified Boolean functions for each output as a
function of the input variables.
4. Draw the logic diagram and verify the correctness of the
design (manually or by simulation).
 11

4.4 Design Procedure

• A truth table for a combinational circuit consists of input
columns and output columns. The input columns are obtained
from the 2n binary numbers for the n input variables. The binary
values for the outputs are determined from the stated
specifications.
• The output functions specified in the truth table give the exact
definition of the combinational circuit.
• It is important that the verbal specifications be interpreted
correctly in the truth table, as they are often incomplete, and
any wrong interpretation may result in an incorrect truth table.
• The output binary functions listed in the truth table are
simplified by any available method, such as algebraic
manipulation, the map method, or a computer-based
simplification program.
 12

4.4 Design Procedure (Problems)

1. Design a 4-bit BCD to Excess-3 converter.

2. Design a 4-bit Gray-Code to Binary-Code converter.

3. Design a car buzzer that turns on whenever a door is

open or the seat belt is not buckled when the key is in
ignition. If the key is not in ignition, we shouldn’t have to
worry about seat belt.
 13

4.4 Design Procedure (Step 0)

Visualize the problem as a block diagram with inputs and
outputs only if possible.
 14

4.4 Design Procedure (Step 1)

• From the specifications of the circuit, determine the
required number of inputs and outputs and assign a
symbol to each.
 15

4.4 Design Procedure (Step 2)

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

4.4 Design Procedure (Step 3)

• Obtain the simplified Boolean functions for each output as
a function of the input variables.

• Additional Work Here (Not necessarily)

 17

4.4 Design Procedure (Step 4)

• Draw the logic diagram and verify the correctness of the
design (manually or by simulation).
 18

BCD to Excess-3 Converter Circuit

 19

G3 G2 G1 G0 B3 B2 B1 B 0
4.4 Contd.
Decimal Digit (Gray
Binary Code to Binary)
Gray Code 0 0 0 0 0 0 0 0
0 0000 0000 0 0 0 1 0 0 0 1
1 0001 0001 0 0 1 0 0 0 1 1
2 0010 0011 0 0 1 1 0 0 1 0
3 0011 0010 0 1 0 0 0 1 1 1
4 0100 0110 0 1 0 1 0 1 1 0
5 0101 0111 0 1 1 0 0 1 0 0
6 0110 0101
0 1 1 1 0 1 0 1
7 0111 0100
1 0 0 0 1 1 1 1
8 1000 1100
1 0 0 1 1 1 1 0
9 1001 1101
1 0 1 0 1 1 0 0
10 1010 1111
11 1011 1110 1 0 1 1 1 1 0 1
12 1100 1010 1 1 0 0 1 0 0 0
13 1101 1011 1 1 0 1 1 0 0 1
14 1110 1001 1 1 1 0 1 0 1 1
15 1111 1000 1 1 1 1 1 0 1 0
 20

Solve end of chapter

problems
(4.4, 4.5, 4.6)
 21

4.5 Binary Adder-Subtractor

• One of the standard operations in digital systems is the
addition and subtraction of two n-bit binary numbers.

• Designing a combinational circuit can go two ways:

1. Using design procedure (4.4) to directly form the logic circuit
2. Using already known combinational circuit blocks

• To make a general n-bit adder, we can use built-in full-

adder blocks. Also, the logic that helps us in making full-
adder circuit is an extension of the logic used in half-adder
circuit, which we will deal as our formal design problem.
 22

4.5 Contd. (Half Adder)

• Design a Half-Adder circuit i.e. Design a circuit that adds
two bits only. (Explain two bit addition on board)
Step 1: Step 2: x y S C
x S 0 0 0 0
y Half Adder C 0 1 1 0
1 0 1 0
Step 3: Two variable K-Maps 1 1 0 1
S = xy’+x’y = x⊕y
Step 4:
C=xy
 23

4.5 Contd. (Full Adder)

• Design a Full-Adder circuit i.e. Design a circuit that adds
three bits.
• Two of the bits can be considered bits of the two
numbers, while third as a carry from previous stage
(Explain three bit addition on board) x y z S C
Step 2:
0 0 0 0 0
Step 1: 0 0 1 1 0
x S 0 1 0 1 0
y Full Adder C 0 1 1 0 1
z
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
 24

4.5 Contd. (Full Adder)

• Design a Full-Adder circuit i.e. Design a circuit that adds
three bits.
Step 3:
 25

4.5 Contd. (Full Adder)

• Design a Full-Adder circuit i.e. Design a circuit that adds
three bits.
Step 4:
 26

4.5 Contd. (Full Adder)

• Can a full adder be realized by half adders?
• S=x’y’z+x’yz’+xy’z’+xyz=x’(y’z+yz’)+x(y’z’+yz) =x’(y⊕z)
+x(y⊕z)’=x⊕y⊕z
• C=m3+m5+m6+m7=x’yz+xy’z+xyz’+xyz=z(x’y+xy’)+xy(z’+z)
=z(x⊕y)+xy

x x⊕y w w⊕z
y Half Adder xy z Half Adder wz
 27

4.5 Contd. (Full Adder)

• Can a full adder be realized by half adders?
• S=x’y’z+x’yz’+xy’z’+xyz=x’(y’z+yz’)+x(y’z’+yz) =x’(y⊕z)
+x(y⊕z)’=x⊕y⊕z
• C=m3+m5+m6+m7=x’yz+xy’z+xyz’+xyz=z(x’y+xy')+xy(z’+z)
=z(x⊕y)+xy

Full-Adder
 28

Revise through today’s

lecture
 29

4.5 Contd. (Binary Adder)

• Can we design an adder for two 4-bit numbers using only
Full Adder circuits? (Manually write subscript for numbers)
• Procedure?
 30

4.5 Contd. (Binary Adder)

• Can we design an adder for two 4-bit numbers using only
Full Adder circuits?
• Input lines? Output lines? Realize as a block diagram.
• Full Adder Functionality? (Conversion to 4-bit Adder)

Full-Adder 4-bit
Full-Adder Adder
Full-Adder Full-Adder
 31

4.5 Contd. (Binary Adder)

• N-bit adder using Full-Adders?

• Limitations: Ripple Carry Addition, for correct result we

have to designate a time after settling the inputs.

• The bigger the size of the adder (n-bits), the more we

have to wait for correct outputs.

• Solution: Carry Look Ahead Adder.

 32

4.5 Contd. (Carry Propagation)

• Pi=Ai⊕Bi; Gi=AiBi;
• Si=Ai⊕Bi⊕Ci = Pi⊕Ci ;
• Ci+1=Ci(Ai⊕Bi)+AiBi = PiCi+Gi
 33

4.5 Contd. (Carry Propagation)

• Ci+1=Ci(Ai⊕Bi)+AiBi = PiCi+Gi where Pi=Ai⊕Bi and Gi=AiBi

• Now, given inputs, all the bits of numbers A and B i.e. Ai and Bi and input
carry=C0, we can calculate all Pi , all Gi but not all Ci.

• To generate the Sum results for all the position, we require all the carries
to be present or calculated (pre-calculated or through previous full adders)

• Pre-calculation, for i=0, C0+1=C1=G0+P0C0 ; All of G0, P0 & C0 can be

generated from the inputs

• For i=1, C1+1=C2=G1+P1C1 =G1+P1(G0+P0C0)= G1+P1G0+P1P0C0;

• For i=2, C2+1=C3=G2+P2C2 = G2+P2(G1+P1G0+P1P0C0)

=G2+P2G1+P2P1G0+P2P1P0C0
 34

4.5 Contd. (Carry Propagation)

 35

4.5 Contd. (Binary Subtractor)

• A-B=A+(2’sC of B)= A+(1’sC of B + 1)=A+(1’sC of B)+1
• 1’s C of B= complement of very bit of B.

?
 36

4.6 Decimal Adder (BCD Adder)

 37

4.6 Decimal Adder (BCD Adder)

 38

4.6 Decimal Adder (BCD Adder)

C=K+Z8Z4+Z8Z2
 39

Revise through today’s

lecture
 40

4.7 Binary Multiplier

Two by Two Bit Multiplier
 41

4.7 Binary Multiplier

• For general multiplier circuits, consider 4 by 3 – bit
Multiplication.

• B: Multiplicand : B3B2B1B0 (4-bits: K=4)

• A: Multiplier : A2A1A0 (3-bits: J=3) Multiply Manually

 42

4.7 Binary Multiplier

Cx P3 P2 P1 P0 C0
 43

4.7 Binary Multiplier

Cx P3 P2 P1 P0 A0B0
 44

Cx P3 P2 P1 P0
 45

4.7 Binary Multiplier

• For general multiplier circuits, consider 4 by 3 – bit
Multiplication.

• B: Multiplicand : B3B2B1B0 (4-bits: K=4)

• A: Multiplier : A2A1A0 (3-bits: J=3)

• JxK AND Gates

• (J-1) K-bit Adders
• (J+K) bits at output
 46

4.8 Magnitude Comparator

′ ′ ′
𝑥𝑖 =( 𝐴 ⨁ 𝐵 ) =( 𝐴𝑖 𝐵 + 𝐴 𝐵𝑖 )′
𝑖 𝑖

( 𝐴= 𝐵)=𝑥3 𝑥 2 𝑥1 𝑥0

( 𝐴> 𝐵 )= 𝐴 3 𝐵′3 + 𝑥 3 𝐴 2 𝐵′2 + 𝑥 3 𝑥 2 𝐴 1 𝐵′1+ 𝑥 3 𝑥 2 𝑥 1 𝐴0 𝐵′0

( 𝐴< 𝐵 )= 𝐴′3 𝐵3 + 𝑥 3 𝐴′2 𝐵2 + 𝑥 3 𝑥 2 𝐴 ′1 𝐵1+ 𝑥 3 𝑥 2 𝑥 1 A ′0 B 0
 47
A’3B3
′ ′ ′
𝑥𝑖 =( 𝐴 ⨁ 𝐵 ) =( 𝐴𝑖 𝐵𝑖 + 𝐴𝑖 𝐵𝑖 )′
A3B’3
x3
( 𝐴= 𝐵)=𝑥3 𝑥 2 𝑥1 𝑥0
A’2B2 A’2B2

A2B’2
A’3B3
4-bit Magnitude
A’1B1
x2
x3

Comparator
A1B’1
x2 x3
A’0B0 x1

A0B’o

′ ′ ′ ′
(( 𝐴<
𝐴>𝐵𝐵))=
=𝐴𝐴′ 3𝐵
𝐵3++𝑥𝑥 3 𝐴
𝐴′ 2𝐵
𝐵2+ +𝑥𝑥 3 𝑥𝑥 2 𝐴
𝐴′1 𝐵
𝐵1+ 𝑥3 𝑥
+𝑥 𝑥2 𝑥
𝑥1 A
𝐴′0 B𝐵0
3 3 3 2 2 3 2 1 1 3 2 1 0 0
 48

4.9 Decoders
• A decoder is a combinational circuit that converts binary
information from n input lines to a maximum of 2n output
lines. i.e. 3 to 8 line decoders, 4 to 16 line decoders

• If the n-bit coded information has unused combinations,

the decoder may have fewer than 2n outputs e.g. BCD to
7-Segment Decoder.

• Normally, every output represents the corresponding

minterm. Since, n input variables make 2n minterms, thus
normally we have n to 2n line decoder.
 49

4.9 Decoders (3 to 8 line decoder)

Inputs Outputs
x y z D0 D1 D2 D3 D4 D5 D6 D7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1

Logic Diagram?
 50

4.9 Contd (2 to 4 line with Enable Input)

Inverted Outputs!
Inputs Outputs
E A B D0 D1 D2 D3
1 X X 1 1 1 1
0 0 0 0 1 1 1
0 0 1 1 0 1 1
0 1 0 1 1 0 1
0 1 1 1 1 1 0
 51

4.9 Decoders
• Design a 4x16 decoder using two 3x8 decoders with
enable input. (4 inputs, 16 outputs) 3x8 Decoder:
E=1 (Enabled)
Output: Minterm

?
 52

4.9 Contd. (Combinational Logic Implementation)

• Design a combinational circuit using a decoder.
• Full Adder, S(x,y,z)=∑(1,2,4,7), C(x,y,z)=∑(3,5,6,7)
• 3 input variables, 3x8 decoder.

I
N
P
U
T
S
?
?
Sum of Minterms?
 53

Revise through today’s

lecture
 54

4.10 Encoders
• 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, as an aggregate, generate the binary

code corresponding to the input value.

• An Octal-to-Binary encoder has eight inputs (one-hot

code) and three outputs that generate the corresponding
binary number.
 55

4.10 Encoders

If D3 & D6 1 simultaneously,
then xyz=111 (7), doesn’t
represent 3 or 6.
 56

4.10 Contd. (Priority Encoders)

*D3 : Highest Priority

K-Map for ‘x’: Manual Illustration

 57

4.10 Contd. (Priority Encoders)

 58

4.10 Contd. (Priority Encoders)

 59

4.11 Multiplexers
• A multiplexer is a combinational circuit that selects binary
information from one of many input lines and directs it to a
single output line.

• The selection of a particular input line is controlled by a

set of selection lines.

• Normally, there are 2n lines and n selection lines whose bit

combinations determine which input is to be selected.

• A two-to-one-line multiplexer connects one of two 1-bit

sources to a common destination.
 60

4.11 Multiplexers (2 to 1 MUX)

Block Diagram Logic Diagram

S Y
0 I0
1 I1 Inputs by themselves will also
be binary i.e. I0=0/1
 61

4.11 Multiplexers (4 to 1 MUX)

S1 S0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3
 62

4.11 Contd (Quadruple 2 to 1 MUX)

Block Diagram
(with enable)
E S Y (4-bit)
1 X All 0’s
0 0 Select A
0 1 Select B
 63

4.11 Multiplexers (Extension)

S2 S1 S0 Y
0 0 0 0 I0
1
2 4 by 1 Y 0 0 1 I1
3 MUX 0 1 0 I2
0 1 1 I3
S0 S1 0
1 2 by 1 Y 1 0 0 I4
MUX I5
1 0 1
0 1 1 0 I6
S0
1 1 1 1 I7
2 4 by 1 Y
3 MUX

S0 S1 Manual Illustration
 64

Revise through today’s

lecture
 65

4.11 Contd. (Combinational Logic Implementation)

• F(x,y,z) = ∑(1,2,6,7)

x y z F
0 0 0 0
z
0 0 1 1
0 1 0 1
z’
0 1 1 0
1 0 0 0
0
1 0 1 0
1 1 0 1
1 1 1 1
1
 66

A B C D F
0 4.11
0 Contd.
0 0 0 (Combinational Logic Implementation)
D
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1 D
0 1 0 0 1
0 1 0 1 0 D’
0 1 1 0 0
0 1 1 1 0 0
1 0 0 0 0
1 0 0 1 0 0
1 0 1 0 0
1 0 1 1 1 D
1 1 0 0 1
1 1 0 1 1 1
1 1 1 0 1
1 1 1 1 1
1
 67

A B C D F
0 4.11
0 Contd.
0 0 0 (Combinational Logic Implementation)
0 0 0 1 1
0 0 1 0 0 D
0 0 1 1 1
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0 C’D’
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0 CD
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1
1 1 1 1 1
 68

4.11 Contd. (De-Multiplexing)

Storage space scanning…
1 0 ?
0
0 1 A
?
1 2 4 by 1 Y B Decoder 1
3 MUX 2 ?
1 3
?
S0 S1 E

Inputs Outputs
E A B D0 D1 D2 D3
0 X X 0 0 0 0
S1/A 1 0 0 1 0 0 0
1 0 1 0 1 0 0
S0/B
1 1 0 0 0 1 0
1 1 1 0 0 0 1
 69

Quiz Already Announced

Solve end of chapter problems

for practice

END OF CHAPTER 4