LOGIC DESIGN

UNIT-II
COMBINATIONAL CIRCUITS

RAJARAO MANDA (Assistant Professor)

Dept. of Electronics and Communication
Engineering
Graphic Era Hill University, Dehradun
 UNIT - II CONTENT

Combinational Logic Circuit:

▪ Combinational circuits, Design Procedure, Analysis Procedure
▪ Binary Adder & Subtractor,
▪ Decimal Adder,
▪ Binary Multiplier,
▪ Magnitude Comparator,
▪ Multiplexer and Demultiplexer,
▪ Decoder and Encoder,
▪ Parity Generator & Checker,
▪ Programmable Array Logic,
▪ Programmable Logic Array,
▪ Code Convertors (BCD, Gray and Seven Segment Code etc.).
LOGIC CIRCUITS

▪ Logic circuits for digital systems may be combinational or sequential.

▪ Combinational circuit
▪ consists of logic gates whose outputs at any time are determined directly from the
present combination of inputs without regard to previous inputs.
▪ Ex: Adder, subtractors, MUX, De-MUX, encoder, decoder etc.

▪ Sequential circuits
▪ whose outputs are depends not only on present inputs, but also on past inputs, and the
circuit behavior must be specified by a time sequence of inputs and internal states.
(outputs are a function of the inputs and the state of the memory elements)
▪ employ memory elements (binary cells) in addition to logic gates. The state of
memory elements, in turn, is a function of previous inputs.
▪ Ex: Flip-flops, registers, counters etc.
COMBINATIONAL CIRCUIT
▪ A combinational circuit consists of input variables, logic gates, and output variables.
▪ The logic gates accept signals from the inputs and generate signals to the outputs. This
process transforms binary information from the given input data to the required output data.
▪ For n input variables, there are 2n possible combinations of binary input values. For each
possible input combination, there is one and only one possible output combination.
▪ A combinational circuit can be described by m Boolean functions, one for each output
variable. Each output function is expressed in terms of the n input variables.
DESIGN PROCEDURE

The design of combinational circuits starts from the verbal outline of the problem
and ends in a logic circuit diagram, or a set of Boolean functions from which the
logic diagram can be easily obtained.
Steps in design procedure:
1. State the problem statement. Determine the number of input and required output
variables from given specifications. Assign the letter symbols to the input and output
variables.
2. Construct the truth table that defines the required relationships between inputs and
outputs.
3. Write the Boolean function for each output (sum-of-products (SOP) form) and Simplify
these Boolean functions if possible.
4. Implement the minimized/ simplified Boolean function for outputs using minimum
number of logic gates.
DESIGN PROCEDURE CONT…

A practical design method would have to consider such constraints as

▪ minimum number of gates,

▪ minimum number of inputs to a gate,

▪ minimum propagation time of the signal through the circuit,

▪ minimum number of interconnections, and

▪ limitations of the driving capabilities of each gate

ANALYSIS PROCEDURE

The analysis of a combinational circuit is somewhat the reverse process. To

obtain the output Boolean functions from a logic diagram, proceed as follows:
1. Label all gate outputs that are a function of input variables with arbitrary
symbols. 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.
EXAMPLE
BASIC ARITHMETIC OPERATION

▪ Addition and subtraction are the two most commonly used arithmetic operations.

▪ Multiplication and division are the processes of repeated additions and

subtractions respectively.
▪ 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.
▪ A combinational circuit that performs the subtraction of two bits is called a half-
subtractor. One that performs the subtraction of three bits is a full-subtractor.
 HALF ADDER
Step 1: This circuit needs two binary inputs and two binary outputs. The input
variables designate the augend (x) and addend (y) bits; the output variables produce the
sum (S) and carry (C).
Step 2: Truth table
Step 4
Inputs Outputs
x y S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Step 3: Boolean function for each output
𝑆 = 𝑥𝑦
ҧ + 𝑥 𝑦ത = 𝑥 ⊕ 𝑦
𝐶 = 𝑥𝑦
FULL ADDER
Step 1: Needs three binary inputs (x, y and z) and two binary outputs (S and C)
Step 2: Truth table
Inputs Outputs Step 3: Boolean function and its simplification for each
x y z S C output
0 0 0 0 0
Sum: 𝑆 = 𝑥ҧ 𝑦𝑧
ത + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥 𝑦ത𝑧ҧ + 𝑥𝑦𝑧
0 0 1 1 0
0 1 0 1 0 𝑆 = 𝑥ҧ 𝑦𝑧
ത + 𝑦𝑧ҧ + 𝑥 𝑦ത𝑧ҧ + 𝑦𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧
0 1 1 0 1
Or 𝑆 = (𝑥 ⊕ 𝑦) ⊕ 𝑧
1 0 0 1 0 yz
1 0 1 0 1 Carry: 𝐶 = 𝑥𝑦𝑧
ҧ + 𝑥 𝑦𝑧
ത + 𝑥𝑦𝑧ҧ + 𝑥𝑦𝑧 x 00 01 11 10
1 1 0 0 1 0 1
𝐶 = 𝑥 ⊕ 𝑦 𝑧 + 𝑥𝑦
1 1 1 1 1
Or using K-map: 𝐶 = 𝑥𝑦 + 𝑦𝑧 + 𝑥𝑧 1 1 1 1
FULL ADDER
Step 4: Implementation with two half-adders and an OR gate

Half adder
FULL ADDER
Step 4: Implementation in sum-of-products form
BINARY PARALLEL ADDER

▪ A binary parallel adder is a digital function that produces the arithmetic sum
of two binary numbers in parallel.
BINARY PARALLEL ADDER

▪ It consists of full-adders connected in cascade. with the output carry from one
full-adder connected to the input carry of the next full-adder.

In the parallel adder the carry input of each

stage is depends on the carry output of the
previous stage. This processes leads to
time delay (propagation delay) in addition.

▪ This causes a unstable factor on carry bit, and produces a longest propagation delay.
▪ The signal from Ci to the output carry Ci+1, propagates through an AND and OR gates, so, for
an n-bit adder, there are 2n gate levels for the carry to propagate from input to output.
CARRY LOOK AHEAD ADDER

▪ Because the propagation delay will affect the output signals on different
time, so the signals are given enough time to get the precise and stable
outputs.
▪ The most widely used technique employs the principle of carry look-ahead to
improve the speed of the algorithm.
 Pi = Ai ⊕ Bi steady state value
Gi = AiBi steady state value
Output sum and carry
Si = Pi ⊕ Ci
Ci+1 = Gi + PiCi
Gi : carry generate Pi : carry propagate C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
Fig: Logic diagram of a look-ahead carry generator
Fig: 4-bit full-adders with carry look-ahead
 HALF SUBTRACTOR
Step 1: Two binary inputs and two binary outputs. The input variables designate the
minuend (x) and subtrahend (y) bits; the output variables produce the difference (D) and
borrow (B).
Step 2: Truth table
Step 4:
Inputs Outputs
x y D B x 𝑆
0 0 0 0 y
0 1 1 1
1 0 1 0
B
1 1 0 0
Step 3: Boolean function for each output
𝑆 = 𝑥𝑦
ҧ + 𝑥 𝑦ത = 𝑥 ⊕ 𝑦
𝐵 = 𝑥𝑦 ҧ
FULL SUBTRACTOR
Step 1: Needs three binary inputs (x, y and z) and two binary outputs (D and B)
Step 2: Truth table
Step 3: Boolean function and its simplification for each
Inputs Outputs
x y z D B output
0 0 0 0 0 Sum: D = 𝑥ҧ 𝑦𝑧
ത + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦ത 𝑧ҧ + 𝑥𝑦𝑧
0 0 1 1 1
0 1 0 1 1 𝑆 = 𝑥ҧ 𝑦𝑧
ത + 𝑦𝑧ҧ + 𝑥 𝑦ത𝑧ҧ + 𝑦𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧
0 1 1 0 1 Or 𝑆 = (𝑥 ⊕ 𝑦) ⊕ 𝑧
1 0 0 1 0 yz
Borrow: B = 𝑥ҧ 𝑦𝑧
ത + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦𝑧
ҧ + 𝑥𝑦𝑧
1 0 1 0 0 x 00 01 11 10
1 1 0 0 0 𝐵 = 𝑥ҧ 𝑦 ⊕ 𝑧 + 𝑦𝑧 0 1 1 1
1 1 1 1 1
Or B = 𝑥 ⊕ 𝑦 𝑧 + 𝑥𝑦
ҧ 1 1
Or using K-map: B = 𝑥𝑦
ҧ + 𝑥𝑧
ҧ + 𝑦𝑧
FULL SUBTRACTOR
Step 5: Implementation with two half-subtractors and an OR gate

x
y
D
z

𝐵
BINARY SUBTRACTOR
▪ The subtraction of unsigned binary numbers can be done most conveniently by
means of complements.
▪ That is 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 circuit for subtracting A - B consists of an adder with inverters placed between
each data input B and the corresponding input of the full adder. The input carry C0
must be equal to 1 when subtraction is performed. The operation thus performed
becomes A , plus the 1’s complement of B , plus 1. This is equal to A plus the 2’s
complement of B .
BINARY ADDER/SUBTRACTOR

When M = 0, we have 𝐵 ⊕ 0 = B. The full adders receive the value of B , the input
carry is 0, and the circuit performs A plus B . When M = 1, we have 𝐵 ⊕ 1 = 𝐵ത and
C0 = 1.
DECIMAL ADDER

▪ Computers or calculators that perform arithmetic operations directly in the

decimal number system represent decimal numbers in binary-coded form.
▪ A decimal adder requires a minimum of nine inputs and five outputs, since four
bits are required to code each decimal digit and the circuit must have an input
carry and output carry.
▪ There is a wide variety of possible decimal adder circuits, depending upon the
code used to represent the decimal digits.
BCD ADDER

▪ In digital system, the decimal number is represented in the form of binary coded
decimal (BCD).The ten digit (0-9) decimal numbers are represented by the binary
digits. The circuit which add the two BCD number is called BCD adder.
▪ When the binary sum is greater than 1001 or 9, we obtain a non-valid BCD
representation.
▪ The addition of 6 = (0110)2 to the binary sum converts it to the correct digit and
also produces a carry as required.
BCD ADDITION

Procedure for BCD addition

▪ Add two BCD numbers using ordinary binary addition.

▪ If four bit sum is less than or equal to zero, then correction is needed.

▪ If the four bit sum is greater than 9 or if carry is generated then add 0110.

Implementation:

▪ Requires 4-bit binary adder for initial addition,

▪ Logic circuit to detect sum greater than 9, and second 4 bit binary adder to
add 0110
 BCD ADDER

▪ Since 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.
▪ For two BCD digits to a 4-bit
binary adder may produce a
range from 0 to 19.
 K-map for carry/ to detect the sum is greater than 9

Z2Z1 C = K + Z8Z4 + Z8Z2

Z4Z8 00 01 11 10
0 1 3 2
00

4 5 7 6
01
Z4Z8
12 13 15 14
11 1 1 1 1

8 9 11 10
10 1 1

Z4Z2
IMPLEMENTATION OF BCD ADDER

▪ A decimal parallel
adder that adds n
decimal digits needs n
BCD adder stages.

▪ The output carry from

one stage must be
connected to the input
carry of the next
higher-order stage.
BINARY MULTIPLIER

▪ The multiplication of binary numbers is done in the same manner as the

multiplication of decimal numbers. The process is actually simpler because the
multiplier digits are either 0 or 1 and so we are always multiplying by 0 or 1 and
no other digits.
Binary multiplier
Four-bit by three-bit binary multiplier
MAGNITUDE COMPARATOR
▪ The magnitude comparator is a combinational circuit that compares two numbers.
The outcome of the comparison is specified by three binary variables that indicate
whether A > B, A = B. or A < B.
▪ Consider two numbers, A and B, with four digits each. Write the coefficients of the
numbers with descending significance as follows:
A = A3A2A1A0
B = B 3B 2B 1 B 0
▪ The two numbers are equal if all pairs of significant digits are equal i.e., if A3 = B3 and
A2 = B2 and A1 = B1 and A0 = B0. This can be expressed logically with an equivalence
function (Exclusive-NOR function) :
𝑥𝑖 = 𝐴𝑖 𝐵𝑖 + 𝐴𝑖 𝐵ഥ𝑖
where xi = 1 only if the pair of bits in position i are equal, i.e., if both are 1’s or both are 0’s.
That is the AND ing operation of all variables is equal to 1 only if all pairs of digits of the
two numbers are equal (A = B) = x3 x2 x1 x0
MAGNITUDE COMPARATOR
▪ If A is greater than or less than B, inspect the relative magnitudes of pairs of
significant digits starting from the MSB.
▪ If the two digits are equal, compare the next LSB pair of digits. This 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 that A < B.
▪ The sequential comparison can be expressed logically by the following two Boolean
functions:
𝐴 > 𝐵 = 𝐴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 𝐴0 𝐵0
▪ the symbols (A > B) and (A < B) are binary output variables which are equal to
1 when A > B or A < B, respectively
MULTIPLEXER (MUX)

▪ A multiplexer is a combinational circuit that selects data line (binary

information) from one of many input data lines and directs it to a single
output line. A multiplexer is also called a data selector
▪ The selection of a particular input line is controlled by a set of
selection/control lines.
▪ Normally, there are 2n input lines and n selection lines whose bit
combinations determine which input is selected.
▪ Ex: MP-3 player, television tuner, radio tuner, or audio from a DVD.
▪ The switch selects one of the electronic signals from one of these four
sources and sends it to the power amplifier and speakers
 I0

I1
MUX

IN-1

Selection/control lines
TWO-TO-ONE-LINE MULTIPLEXER

The 2 × 1 MUX has two data input lines, one output Select line (S) Output (Y)
line, and one selection line S . 0 I0
When S = 0, I0 has a path to the output. When S = 1, I1
has a path to the output. 1 I1
𝑌 = 𝐼0 𝑆ҧ + 𝐼1 𝑆

Block diagram Logic diagram

 FOUR-TO-ONE-LINE MULTIPLEXER

The 4 × 1 MUX has four data input lines, one output line, and two selection line S0 and S1 .

Select line Output (Y)

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

𝑌 = 𝐼0 𝑆ഥ1 𝑆0 + 𝐼1 𝑆ഥ1 𝑆0 + 𝐼2 𝑆1 𝑆0 + 𝐼1 𝑆1 𝑆0
MUX WITH ENABLE INPUT

Another type of multiplexer has an additional input called an enable. The enable
signal E is connected to the each of the AND gates.
For positive logic if E = 0, Y= 0 independent of the gate inputs and if E = 1, then
the MUX functions as an ordinary multiplexer.
For negative logic if E = 0, then the MUX functions as an ordinary multiplexer and
if E=1, Y=0
Quad Two-input MUX (74ALS157/HC157
Eight-input MUX (74ALS157/HC157
LARGE SIZE MUX

The larger size multiplexers can be implemented using the smaller size multiplexers
If 2n input lines in the available MUX and 2m is the number of input lines in the
desired MUX then the number of required MUXs = 2m-n
Example: 8x1 MUX implementation using 4x1 MUX and 2x1 MUX
 I0
I1 4x1
I2 MUX

I3 𝐸ത 𝑆1 𝑆0
𝑆2
𝑆1 I0 2x1
𝑆0 Y
I1 MUX
𝑆
I4 𝐸ത 𝑆1 𝑆0

I5 4x1 𝑆2
I6 MUX

I7
BOOLEAN FUNCTION IMPLEMENTATION USING MUX

▪ The minterms of a function are generated in a multiplexer by the circuit

associated with the selection inputs.
▪ The individual minterms can be selected by the data inputs, thereby providing
a method of implementing a Boolean function of n variables with a
multiplexer that has n selection inputs and 2n data inputs, one for each
minterm.
▪ The Boolean function of n variables can be implement efficiently 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.
 EXAMPLE
F (x, y, z) = Ʃ(1, 2, 6, 7)

This function of three variables can be implemented with a four-to-one-line multiplexer

The two variables x and y are applied to the selection lines in

that order; x is connected to the S1 input and y to the S0 input
EXAMPLE
F (A, B, C, D) = Ʃ(1, 3, 4, 11, 12, 13, 14, 15)
EXAMPLE
F (A, B, C) = Ʃ(1, 3, 5, 6)

Implementation table
Alternate Implementation for F(A,B,C) = Σ (1,3,5,6,)
EXAMPLE

Implement the following function with a multiplexer:

F(A, B, C, D) = Σ(0, 1, 3, 4, 8, 9, 15)
DEMULTIPLEXER (DE-MUX)

▪ It is a combinational circuit that performs the reverse process of MUX.

▪ Receives the information from a single line and directs it to one of N = 2n possible
outputs.
▪ The selection of a specific output is controlled by the bit combination of n-selection
lines

O0
O1
.
1x2n
I .
De-MUX
.
.
𝑆𝑛−1 . . . 𝑆1 𝑆0 ON
1X4 DE-MUX

I
O0

Selection Outputs O1
lines
S1 S0 O0 O1 O 2 O3 O2
0 0 I 0 0 0
0 1 0 I 0 0
O3
1 0 0 0 I 0
1 1 0 0 0 I

S1 S0
Reference Text Book:
1. M. Morris Mano, “Digital Logic and Computer Design,” Pearson
Education Limited, 2016.
2. Charles H. Roth, “Fundamentals of Logic Design,” 7th Edition, Cengage
Learning, Inc., 2021
3. Neal S. Widmer, Gregory L. Moss , Digital Systems: Principles and
Applications, 12th Edition, Pearson Education Limited, 2018
Thank you