Digital System Design

Dr. U. Saravanakumar
Professor and Head / ECE
 Logic Circuits

Logic Circuits

Combinational Sequential
Circuits (Unit 2) Circuits
UNIT 2
Synchronous
(Unit 3)

Asynchronous
(Unit 4)
 Combinational Logic Circuits
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.

From External Sources Produced by Internal Logic Gates

For n number of inputs, there are 2n possible combinations
 Combinational Logic Circuits
A combinational circuit consists of an interconnection
of logic gates.

Combinational logic gates react to the values of the

signals at their inputs and produce the value of the
output signal, transforming binary information from
the given input data to a required output data.
 Combinational Logic Circuits
For each possible input combination, there is one
possible value for each output variable.

Ex. Inputs : A, B and Outputs X, Y;

Then, Outputs can be defined as: X = f(A, B) and Y =
f(A, B)

Number of Inputs = 2; then the system has 22 = 4

That is (00, 01, 10, 11)

Thus, a combinational circuit can be specified with a truth

table that lists the output values for each combination of
input variables
 Combinational Logic Circuits - Analysis

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.
 Combinational Logic Circuits - Analysis
ANALYSIS (Boolean Expression):
F1 = (A+B+C)(AB+AC+BC)’ + ABC
T2 = ABC

T1 = A + B + C

T3 = (A + B + C)(AB + AC + BC)’

AB (AB + AC + BC)’

AC
F2 = AB + AC + BC
AB + AC + BC

BC

F1 = (A+B+C)(AB+AC+BC)’ + ABC F2 = AB + AC + BC
 Combinational Logic Circuits - Analysis
Procedure To obtain the output Boolean functions from a logic
diagram, we proceed as follows:
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
(second level).
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.
 Combinational Logic Circuits - Analysis
ANALYSIS (TT): From the logic diagram, the F1
number of inputs are 3;
Therefore, the possible input combinations are
23 = 8 (0 to 7 or 000 to 111) Primary Outputs
F2
Primary Inputs
 Combinational Logic Circuits - Analysis
Procedure To obtain the Truth Table from a logic diagram, we
proceed as follows:
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
(2n - 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.
 Combinational Logic Circuits - Design
DESIGN: Procedure

• From the specifications of the circuit, determine the

required number of inputs and outputs and assign a
symbol to each
• Derive the truth table that defines the required
relation
• Obtain the simplified Boolean functions for each
output as a function of the input variables.
• Draw the logic diagram and verify the correctness of
the design (manually or by simulation). ship between
inputs and outputs
 Combinational Logic Circuits - Design
Example: Design a Combinational Circuit that converts binary
coded decimal (BCD) to the excess-3 code for the decimal digits

Solution: Truth Table of BCD to Ex-3 Code

Combinational Logic Circuits - Design

0 0 0 0 Boolean Expression for

BC W = A + BD + BC
0 1 1 1
BD
X X X X
1 1 X X A

Boolean Expression for

X = B’C + B’D + BC’D’
Combinational Logic Circuits - Design

Y = CD + C’D’ Z = D’
Combinational Logic Circuits - Design
Note: Application of DeMorgan’s Theorem

CD + (C+D)’

B(C+D)’

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

A + B(C+D)
 Combinational Logic Circuits - Design
HALF ADDER
Example: Design a Adder to Perform 2 Single Bit Binary
Addition
Solution: 2 Single bit – 2 inputs; Assume x and y are the inputs
Addition function produces 2 outputs;
Assume S for Sum and C for Carry

X Boolean Expressions are

S
Adder S = X’Y + XY’
y C = XY
C

Name of the Circuit:

Half Adder
 Combinational Logic Circuits - Design
Problem: Design a Combinational Circuit to Perform the arithmetic
sum of three bits
Solution: Three bits: z, y and x ;
Any adder will have 2 outputs: sum (s) and carry (c)

X
S
Adder
y
C

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

 Combinational Logic Circuits - Design
Full Adder
S = x’y’z + x’yz’ + xy’z’ + xyz C = x’yz +xy’z + xyz’ + xyz
S = x’(y’z + yz’) + x (y’z’+ yz) C = z(x’y+xy’) + xy(z’+z)
S = x’(y  z) + x(y  z)’ C = z (x  y) + xy
S=xyz

Logic Diagram of the Combinational Circuit:

Name of the Circuit: Full Adder

 Combinational Logic Circuits - Design
Full Adder : Alternative Method (K-Map)

X
Y
S
z

C
 Combinational Logic Circuits - Design
Binary Adders
• A binary adder is a digital circuit that produces the
arithmetic sum of two binary numbers
• It can be constructed with full adders connected in
cascade, with the output carry from each full adder
connected to the input carry of the next full adder
in the chain
• Addition of n-bit numbers requires a chain of n full
adders or a chain of one-half adder and n-1 full
adders. In the former case, the input carry to the
least significant position is fixed at 0
 Combinational Logic Circuits - Design
Binary Adders: 4-bit binary ripple carry adder
Block Diagram

Ex. 1011 + 0011

(A)
(B)
 Combinational Logic Circuits - Design
Carry Propagation
• The addition of two binary numbers in parallel implies that all the
bits of the augend and addend are available for computation at the
same time.
• As in any combinational circuit, the signal must propagate through
the gates before the correct output sum is available in the output
terminals.
• The total propagation time is equal to the propagation delay of a
typical gate, times the number of gate levels in the circuit.
• The longest propagation delay time in an adder is the time it takes
the carry to propagate through the full adders.
• 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
 Combinational Logic Circuits - Design
Full Adder with different notation for Carry Propagation

i – position

• The signals at Pi and Gi settle to their steady-state values after they

propagate through their respective gates
• These two signals are common to all half adders and depend on only the
input augend and addend bits
• 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 four full adders in the adder, the output carry C4 would have 2 *
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
 Combinational Logic Circuits - Design
Carry Propagation
• The carry propagation time is an important attribute
of the adder because it limits the speed with which
two numbers are added.
• Although the adder—or, for that matter, any
combinational circuit—will always have some value at
its output terminals, the outputs will not be correct
unless the signals are given enough time to propagate
through the gates connected from the inputs to the
outputs
• Since all other arithmetic operations are
implemented by successive additions, the time
consumed during the addition process is critical.
 Combinational Logic Circuits - Design
Solutions to Provide Propagation Delay

• Employ faster gates with reduced delays. However,

physical circuits have a limit to their capability
• Increase the complexity of the equipment in such a
way that the carry delay time is reduced
• The most widely used technique employs the
principle of carry lookahead logic
 Combinational Logic Circuits - Design

𝑃𝑖 = 𝐴𝑖 ⊕ 𝐵𝑖 ; Gi = Ai. Bi
From the Circuit ,
Sum Si = Pi  𝐶𝑖 𝑎𝑛𝑑
𝐶𝑎𝑟𝑟𝑦 𝐶𝑖 + 1 = 𝑃𝑖𝐶𝑖 + 𝐺𝑖

• Gi is called a carry generate , and it produces a carry of 1

when both Ai and Bi are 1, regardless of the input carry Ci .
• Pi is called a carry propagate , because it determines
whether a carry into stage i will propagate into stage i + 1
 Combinational Logic Circuits - Design
Equations of carry from C0 to C3 for 4-bit Adder

Note that this circuit can add in less

time because C3 does not have to wait
for C2 and C1 to propagate; in fact, 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).
 Combinational Logic Circuits - Design
Four-bit adder with carry lookahead

• Each sum output requires two

exclusive-OR gates.
• The output of the first Ex-OR gate
generates the Pi variable, and the
AND gate generates the Gi variable.
• The carries are propagated through
the carry lookahead generator and
applied as inputs to the second Ex-
OR gate.
• All output carries are generated
after a delay through two levels of
gates.
• Thus, outputs S1 through S3 have
equal propagation delay times.
 Combinational Logic Circuits - Design
BCD Adder
Consider the arithmetic addition of two decimal digits in BCD,
together with an input carry from a previous stage
• Each input digit does not exceed 9, the output sum cannot be
greater than 9 + 9 + 1 = 19, the 1 in the sum being an input
carry
• Suppose we apply two BCD digits to a four-bit binary adder,
the adder will form the sum in binary and produce a result
that ranges from 0 through 19
 Combinational Logic Circuits - Design
A correction is needed when the
binary sum has an output carry
K = 1.

The other six combinations from

1010 through 1111 that need
a correction have a 1 in position
Z8.

To distinguish them from binary

1000 and 1001, which also have
a 1 in position Z8, we specify
further that either Z4 or Z2 must
have a 1.

• The condition for a correction and an output carry can be expressed by the
Boolean Function: C = K + Z8Z4 + Z8Z2
• When C = 1, it is necessary to add 0110 to the binary sum and provide an
output carry for the next stage.
Combinational Logic Circuits - Design
 Combinational Logic Circuits - Design
Magnitude Comparator

• The comparison of two numbers is an operation that

determines whether one number is greater than, less than,
or equal to the other number.
• A magnitude comparator is a combinational circuit that
compares two numbers A and B and determines their
relative magnitudes.
• The outcome of the comparison is specified by three binary
variables that indicate whether A > B, A = B, or A < B.
• The circuit for comparing two n -bit numbers has 𝟐𝟐𝒏
entries in the truth table
 Combinational
Magnitude Comparator
Logic Circuits - Design
• When the numbers are binary, the digits are either 1 or 0, and the
equality of each pair of bits can be expressed logically with an
exclusive-NOR function as
xi = AiBi + Ai’ Bi’ for i = 0, 1, 2, 3
• where xi = 1 only if the pair of bits in position i are equal
• To determine whether A is greater or less than B , we inspect the
relative magnitudes of pairs of significant digits, starting from the
most significant position. If the two digits of a pair are equal, we
compare the next lower significant pair of digits.
• The comparison continues until a pair of unequal digits is reached.
If the corresponding digit of A is 1 and that of B is 0, we conclude
that A > B. If the corresponding digit of A is 0 and that of B is 1, we
have A < B.
 Combinational Logic Circuits - Design
Magnitude Comparator
Block Diagram
 Combinational Logic Circuits - Design
Decoder
• Discrete quantities of information are represented in
digital systems by binary codes
• A binary code of n bits is capable of representing up to 2𝑛
distinct elements of coded information.
• A decoder is a combinational circuit that converts binary
information from n input lines to a maximum of 𝟐𝒏
unique output lines. If the n -bit coded information has
unused combinations, the decoder may have fewer than
2𝑛 outputs
• The name decoder is also used in conjunction with other
code converters, such as a BCD-to-seven-segment
decoder
 Combinational Logic Circuits - Design
Example: 3 to 8 Decoder (Truth Table)
 Combinational Logic Circuits - Design
Example: 3 to 8 Decoder
(Logic Diagram: Drawn straight away from T.T)
 Combinational Logic Circuits - Design
Example: 2 to 4 Decoder
(Logic Diagram: Drawn straight away from T.T)
• Some decoders are constructed with NAND gates
• Decoders include one or more enable inputs to
control the circuit operation