ECE 221

Digital Logic Design

Combinational Logic (1)

Mohammed Sharaf Sayed

[email protected]
 Lecture Outline

 Introduction
 Combinational Circuits
 Analysis Procedure
 Design Procedure
 Binary Adder–Subtractor
 Carry Lookahead Logic
 Binary Subtractor
 Decoders

2
 Introduction

• Logic circuits for digital systems may be combinational or

sequential.
• A combinational circuit consists of logic gates whose outputs at
any time are determined from only the present combination of
inputs.
• A combinational circuit performs an operation that can be
specified logically by a set of Boolean functions.
• In contrast, sequential circuits employ storage elements in
addition to logic gates.
• Their outputs are a function of the inputs and the state of the
storage elements.

3
 Combinational Circuits

• The n input binary variables come from an external source; the

m output variables are produced by the internal combinational
logic circuit and go to an external destination.
• For n input variables, there are 2n possible combinations of the
binary inputs.
 A combinational circuit can be specified with a truth table
that lists the output values for each combination of input
variables.
 A combinational circuit also can be described by m Boolean
functions, one for each output variable.
4
 Analysis Procedure

• The analysis of a combinational circuit requires that we

determine the function that the circuit implements.
• This task 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.

5
 Analysis Procedure

 Example
F2 = AB + AC + BC

T1 = A + B + C
T2 = ABC
T3 = F’2T1

F1 = T3 + T2
F1 = F’2T1 + ABC = (AB + AC + BC)’(A + B + C) + ABC
= (A’ + B’)(A’ + C’)(B’ + C’)(A + B + C) + ABC
= (A’ + B’C’)(AB’ + AC’ + BC’ + B’C) + ABC
6
= A’BC’ + A’B’C + AB’C’ + ABC
 Analysis Procedure

 Example

 The truth table can be derived directly from the logic diagram
without going through the derivations of the Boolean functions

7
 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).
8
 Design Procedure

 Example: Design a circuit to convert from BCD to Excess-3

 The design process starts with building the truth table relating
the input BCD and output Excess-3 Code variables.

9
 Design Procedure

 Example
z = D’
y = CD + C’D’
= CD + (C + D)’
x = B’C + B’D + BC’D’
= B’(C + D) + B(C+D)’
w = A + BC + BD
= A + B(C + D)

10
 Design Procedure

 Example

11
 Binary Adder–Subtractor

• Simple addition consists of four possible elementary operations:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10.
• A combinational circuit that performs
the addition of two bits is called a
half adder.
S = x’y + xy’
C = xy

12
 Binary Adder–Subtractor

• One that performs the addition of three bits (two significant bits
and a previous carry) is a full adder.
• The names of the circuits stem from the fact that two half
adders can be employed to implement a full adder.
• The third input, z , represents the
carry from the previous lower
significant position.

13
 Binary Adder–Subtractor

14
 Binary Adder–Subtractor

S = z ⊕ (x ⊕ y)
= z’(xy’ + x’y) + z(xy’ + x’y)’
= z’(xy’ + x’y) + z(xy + x’y’)
= xy’z’ + x’yz’ + xyz + x’y’z
C = z(xy’ + x’y) + xy = xy’z + x’yz + xy
15
 Binary Adder–Subtractor

 Four-bit
binary ripple
carry adder:

 Example, add two binary numbers A = 1011 and B = 0011.

16
 Binary Adder–Subtractor

• Observe that the design of this circuit by the classical method

would require a truth table with 29 = 512 entries, since there are
nine inputs to the circuit.
• By using an iterative method of cascading a standard function, it
is possible to obtain a simple and straightforward
implementation.
• Since each bit of the sum output depends on the value of the
input carry, the value of Si at any given stage in the adder will be
in its steady-state final value only after the input carry to that
stage has been propagated.
• The longest propagation delay time in an adder is the time it
takes the carry to propagate through the full adders.
C 0  C 1  C 2  C 3  S3
17
 Binary Subtractor

• The subtraction A - B can be done by taking the 2’s

complement of B and adding it to A.
• The 2’s complement can be obtained by taking the 1’s
complement and adding 1 to the least significant pair of bits.
• The 1’s complement can be implemented with inverters, and a 1
can be added to the sum through the input carry.
• The addition and subtraction operations can be combined into
one circuit with one common binary adder by including an
exclusive-OR gate with each full adder.

18
 Binary Subtractor

• The mode input M controls the operation; when M = 0, the

circuit is an adder, and when M = 1, the circuit becomes a
subtractor.
19
 Carry Lookahead Logic

Gi is called a carry generate, and it produces a

Pi = Ai ⊕ Bi carry of 1 when both Ai and Bi are 1, regardless
Gi = AiBi of the input carry Ci.
Si = Pi ⊕ Ci Pi is called a carry propagate, because it
Ci+1 = Gi + PiCi determines whether a carry into stage i will
propagate into stage i + 1.
20
 Carry Lookahead Logic

C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1
= G1 + P1(G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3 = G2 + P2C2
= G2 + P2G1 + P2P1G0
+ P2P1P0C0

21
 Carry Lookahead Logic
 This circuit can add in less
time because 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 (hardware).

22
 Decoders

• A decoder is a combinational circuit that converts binary

information from n input lines to a maximum of 2n unique
output lines or fewer if the n -bit coded information has unused
combinations.
 Example, the three-to-eight-line decoder circuit.
 The three inputs are decoded into eight outputs, each
representing one of the minterms of the three input variables.

23
 Decoders

 Example: the three-to-

eight-line decoder circuit.

24
 Decoders

 Example: Two-to-four-line decoder with enable input.

 The circuit operates with complemented outputs and a complement
enable input.
 The decoder is enabled when E is equal to 0 (i.e., active-low enable).

25
 Decoders

• A decoder with enable input can function as a demultiplexer (a

circuit that receives information from a 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 selection lines.
• The decoder in the previous slide can function as a one-to-four-
line demultiplexer when E is taken as a data input line and A
and B are taken as the selection inputs.
 Example, if AB = 10, output D2 will be the same as the input
value E , while all other outputs are maintained at 1.
• Because decoder and demultiplexer operations are obtained
from the same circuit, a decoder with an enable input is referred
to as a decoder – demultiplexer.
26
 Decoders

• Decoders with enable inputs can be connected together to form

a larger decoder circuit.
 Example: two 3-to-8-line decoders with enable inputs can be
connected to form
a 4-to-16-line
decoder.
 Note: E is active-high

27
 Decoders

• Combinational Logic Implementation

 A decoder provides the 2n minterms of n input variables.
 Each asserted output of the decoder is associated with a
unique pattern of input bits.
 Since any Boolean function can be expressed in sum-of-
minterms form, a decoder that generates the minterms of
the function, together with an external OR gate that forms
their logical sum, provides a hardware implementation of the
function.
 In this way, any combinational circuit with n inputs and m
outputs can be implemented with an n-to-2n-line decoder
and m OR gates.

28
 Decoders

 Example: implement a full-adder circuit using a decoder

 Since there are three inputs and a total of eight minterms, we
need a three-to-eight-line decoder.
 From the truth table of the full adder:
S(x, y, z) = ∑(1, 2, 4, 7)
C(x, y, z) = ∑(3, 5, 6, 7)

29
 Lecture Summary
• We have discussed the following topics:
 Introduction
 Combinational Circuits
 Analysis Procedure
 Design Procedure
 Binary Adder–Subtractor
 Binary Subtractor
 Carry Lookahead Logic
 Decoders

30
 Mohammed Sharaf Sayed
[email protected]