ANALYSIS AND

DESIGN OF
COMBINATIONAL
LOGIC
Deepti S Shastrim ath
Contents
• Decoder
• Encoder
• Priority Encoder
• Digital Multiplexers
• Binary Adders
• Binary Subtractors
• Binary Comparators
Decoder
➢ A decoder is a multiple-
input, multiple output logic
circuit which converts
coded inputs into coded n-data n : 2𝑛
outputs, where the input inputs Decoder
Possible
and output codes are
different.
2𝑛 outputs
➢ The encoded information
is presented as n inputs
producing 2𝑛 possible
outputs.
➢ The 2𝑛 output values are
from 0 through 2𝑛 -1
Binary Decoder
◦ A decoder which has an n-bit binary input code and a one activated output out of 2𝑛 output code is
called Binary Decoder.
◦ A binary decoder is used when it is necessary to activate exactly one of 2𝑛 outputs based on an n-bit
input value.

Inputs Outputs
En A B 𝑌3 𝑌2 𝑌1 𝑌0
0 X X 0 0 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 0 0 0
Truth Table for a 2 to 4
decoder
Realization of Multiple Output Function
using Binary Decoder
◦ For Active High Output
◦ SOP function – OR gate
◦ POS function – NOR gate
◦ For Active Low Output
◦ POS function – AND gate
◦ SOP function – NAND gate
For Active High Output
◦ F = ∑m(1,2,3,7)
For Active High Output
◦ F= πM(1,3,5,7)
For Active Low Output
◦ F = πM(1,3,5,7)
For Active Low Output
◦ F = ∑m(1,2,5,7)
Encoders
➢ An encoder is a digital circuit that performs the inv erse operation of a decoder.
➢ An encoder is a multiple-input, multiple output logic circuit which conv erts coded inputs into coded outputs,
where the input and output codes are different.
➢ An encoder has 2𝑛 input lines and n output lines.
➢ In encoder the output lines generate the binary code corresponding to the input v alue.

2𝑛 - data 2𝑛 : 𝑛
inputs Encoder
Possible
n outputs
Priority Encoder
➢ A priority encoder is an encoder circuit that includes the priority function. In priority encoder, if two or
more inputs are equal to 1 at the same time, the input having the highest priority will take precedence.

Inputs Outputs K-map Simplification

𝑌1 = 𝐷2 + 𝐷3
𝐷0 𝐷1 𝐷2 𝐷3 𝑌1 𝑌0 V 𝑌0 = 𝐷3 + 𝐷1𝐷2′
V = 𝐷0 + 𝐷1 + 𝐷2 + 𝐷3
0 0 0 0 X X 0

1 0 0 0 0 0 1

X 1 0 0 0 1 1

X X 1 0 1 0 1

X X X 1 1 1 1
Multiplexers
➢ In Digital systems, many times it is necessary to select single data line from several data-input lines, and
the data from the selected data line should be available on the output. The digital circuit which does
this task is a multiplexers.
➢ It is a digital switch. It allows digital information from several sources to be routed onto a single output
line. The basic multiplexer has several data- input lines and a single output line.
➢ The selection of a particular input line is controlled by a set of selection lines.
➢ Since multiplexer selects one of the input and routes it to output, it is also known as Data Selector.
𝐷0
Enable Select 𝑫𝟏 𝑫𝟎 Output Y
𝐷1
Data Input 𝐷2 1 0 X 0 0
2𝑛 : 1
Lines Y(OUTPUT) 1 0 X 1 1
MUX
𝐷2𝑛 −1 1 1 0 X 0
Enable 1 1 1 X 1
input
0 X X X 0
𝑆𝑛 𝑆1 𝑆0
Truth Table of 2:1 MUX
Multiplexers as Boolean Function Generators
◦ Implement the given function using multiplexer
◦ F(X,Y,Z)=∑(0,2,6,7)
◦ Step 1: Select the multiplexer. Here, Boolean expression has 3 variables, thus we require 23 = 8: 1 𝑀𝑈𝑋
◦ Step 2: Connect inputs corresponding to the present minterms to logic 1.
◦ Step 3: Connect remaining inputs to logic 0. Logic 1
◦ Step 4: Connect input variables to select lines of MUX. 0
1
2
3 8:1
4 F
MUX
5
6
7 𝑆2 𝑆1 𝑆0

X Y Z
2. Implement the Boolean function
represented by the given truth table using
MUX
A B C Y
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Implement the following Boolean function
using 4:1 MUX
F(A,B,C)=∑m(1,3,5,6)
◦ Step 1: Connect least significant variables as a select inputs of multiplexer. Here, connect C to 𝑆0 and B
to 𝑆1.
◦ Step 2: Derive inputs for multiplexer using implementation table.
Implement the following Boolean function
using 8:1 MUX
F(A,B,C,D)=A’BD’+ACD+B’CD+A’C’D
◦ Step 1: convert to standard SOP form and express Boolean function in the minterm form.
◦ F(A,B,C,D)=∑m(1,3,4,5,6,11,15)
Implement f(a,b,c,d) = ∑(0,1,5,6,7,9,10,15) using
8:1 MUX with a,b,c as select lines
4:1 MUX with a, b as select lines
Binary Adders
◦ This simple addition consists of four possible elementary operations
◦ 0+0=0
◦ 0+1=1
◦ 1+0=1
◦ 1 + 1 = 102
◦ The logic circuit which performs this operation is called a Half Adder.
◦ The logic circuit which performs addition of three bits (two significant bits and a previous carry) is a Full
Adder.
Half Adder
◦ The half adder operation needs two binary inputs: Augend and Addend bits;
and two binary outputs: Sum and Carry.

A Sum
Half
Inputs Adder Outputs
B Carry

B B
0 1 0 1
A A
0 0 0 0 0 1

0 1 1 0
1 1

Carry = AB Sum = AB’ + A’B

Limitations of Half Adder:
◦ Limitations of Half Adder: In multidigit addition we have to add two bits along
with the carry of previous digit addition. Effectively such addition requires
addition of three bits. This is not possible with half-adder. Hence half-adders
are not used in practice.
Full Adder
◦ A full-adder is a combinational circuit that forms the arithmetic sum of three input bits. It consists of three
inputs and two outputs. 𝐶𝑖𝑛
◦ 𝐵𝐶𝑖𝑛
Inputs Outputs
A
Full
A B 𝐶𝑖𝑛 Sum Carry Sum
Adder
B
0 0 0 0 0
𝐵𝐶𝑖𝑛
0 0 1 1 0 00 01 Carry
A 11 10
0 1 0 1 0 0 0 0 1 0
0 1 1 0 1 1 0 1 1 1
1 0 0 1 0 C𝑎𝑟𝑟𝑦 = 𝐴𝐵 + 𝐴𝐶𝑖𝑛 + 𝐵𝐶𝑖𝑛 𝐵𝐶𝑖𝑛
A 00 01 11 10
1 0 1 0 1
0 0 1 0 1
1 1 0 0 1
1 1 0 1 0
1 1 1 1 1 ′
Sum = 𝐴′ 𝐵 ′ 𝐶𝑖𝑛 + 𝐴′ 𝐵𝐶𝑖𝑛 + 𝐴𝐵 ′𝐶𝑖𝑛′ + 𝐴𝐵𝐶𝑖𝑛
Full Adder Cont…
Subtractors
◦ The subtraction consists of four possible elementary operations, namely
◦ 0–0=0
◦ 0 – 1 = 1 with 1 borrow
◦ 1–0=1
◦ 1–1=0
◦ In all operations, each subtrahend bit is subtracted from the minuend bit. In case of second operation
the minuend bit is smaller than the subtrahend bit, hence 1 is borrowed.
Half Subtractor
◦ A half- subtractor is a combinational circuit that subtracts two-bits and produces their difference. It also
has an output to specify if a 1 has been borrowed.
◦ Let A be minuend bit and B be subtrahend bit.
◦ Half subtractor has two input variables and two output variables.

Inputs Outputs B B
A 0 1 A 0 1
A B Difference Borrow 0 0 1 0 0 1

0 0 0 0 1 0 1 0 0
1
0 1 1 1 𝐷𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑐𝑒 = 𝐴𝐵 ′ + 𝐴′ 𝐵 Borrow = A’B

1 0 1 0

1 1 0 0
Limitation of Half- subtractor:
◦ In multidigit subtraction, we have to subtract two bits along with the
borrow of the previous digit subtraction. Effectively such subtraction
requires subtraction of three bits.
◦ Full-Subtractor
◦ A full-subtractor is a combinational circuit that performs a subtraction
between two bits, taking into account borrow of the lower significant
stage.
◦ This circuit has three inputs and two outputs.
◦ The three inputs are A, B and 𝐵𝑖𝑛 , denote the minuend, subtrahend and
previous borrow respectively.
◦ The two outputs, D and 𝐵𝑜𝑢𝑡 , represent the difference and output
borrow respectively.
Full-Subtractor cont…
𝐵𝐵𝑖𝑛 𝐵𝐵𝑖𝑛
Inputs Outputs A 00 01 11 10 00 01 11 10
A
A B 𝐵𝑖𝑛 D 𝐵𝑜𝑢𝑡 0 0 1 0 1 0 0 1 1 1

0 0 0 0 0 1 0 1 0 0 0 1 0
1 1
0 0 1 1 1 𝐵𝑜𝑢𝑡 = 𝐴′𝐵𝑖𝑛 + A’B + B𝐵𝑖𝑛
𝐷 = 𝐴′𝐵 ′𝐵𝑖𝑛 + 𝐴′𝐵𝐵𝑖𝑛 ′ +
0 1 0 1 1 𝐴𝐵 ′𝐵𝑖𝑛 ′ +AB𝐵𝑖𝑛

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1
Cascading Full Adders (Parallel Adder)

▪ In order to add binary numbers with more than one bit, additional full adders must be
employed.
• A n-bit, parallel adder can be constructed using number of full adder circuits in parallel.
• From the figure it is seen that, the carry output of each adder is connected to the carry input
of the next higher order adder.

Note: Either a half-adder can be used for the least significant position or the carry input of a full
adder is made 0 because there is no carry into the least significant position.
Parallel Subtractor

• The subtraction of binary numbers can be done most conveniently by means of complements.
(2’s complement).
• The 2’s complement can be obtained by taking the 1’s complement and adding one to the
least significant pair of bits.
• The 1’s complement can be implemented with inverters and a one can be added to the sum
through the input carry.
Parallel Adder / Subtractor

The addition and subtraction operations can be combined into one circuit with one common
binary adder. This is done by including an Ex-OR gate with each full adder.
The mode M controls the operation of the circuit. When M = 0, the circuit is an adder, and when
M = 1, the circuit becomes a subtractor.
The parallel adder is ripple carry adder in which the carry output of each full -adder stage is
connected to the carry input of the next higher order stage.
Therefore, the sum and carry outputs of any stage cannot be produced until the input carry
occurs, this leads to a time delay in addition process. This delay is known as Carry Propagation
Delay.
Look-Ahead Carry Adder
◦ One method of speeding up this process by eliminating inter stage carry delay is called Look-Ahead
Carry Addition.
◦ This method utilizes logic gates to look at the lower-order bits of the augend and addend to see if a
higher order carry is to be generated.
◦ It uses two functions: Carry Generate and Carry Propagate.

◦ Considering the circuit of the full adder

◦ The outputs Sum and Carry can be expressed as

Look-Ahead Carry Adder Cont…
◦ 𝐺𝑖 is called a carry generate, it produces on carry when both A and B are one, regardless of the input
carry.
◦ 𝑃𝑖 is called a carry propagate because it is a term associated with the propagation of the carry from 𝐶𝑖
to 𝐶𝑖+1.
◦ Now the Boolean function for the carry output of each stage can be written as follows.

◦ 𝐶2 = 𝐺1 + 𝑃1 𝐶1
◦ 𝐶3 = 𝐺2 + 𝑃2 𝐶2 = 𝐺2 + 𝑃2 (𝐺1 + 𝑃1 𝐶1) = 𝐺2 + 𝑃2 𝐺1 + 𝑃2 𝑃1𝐶1
◦ 𝐶4 = 𝐺3 + 𝑃3 𝐶3 = 𝐺3 + 𝑃3 (𝐺2 + 𝑃2 𝐺1 + 𝑃2 𝑃1𝐶1) = 𝐺3 + 𝑃3 𝐺2 + 𝑃3 𝑃2 𝐺1 + 𝑃3 𝑃2 𝑃1 𝐶1
◦ From the above Boolean function it can be seen that 𝐶4 does not have to wait for 𝐶3 and 𝐶2 to
propagate; in fact 𝐶4 is propagated at the same time as 𝐶2 and 𝐶3.
Look-Ahead Carry Adder Cont…
◦ The Boolean functions for each output carry are expressed in SOP form, thus they can be implemented
using AND-OR logic or NAND-NAND logic.
Binary Comparator

• A comparator is a special combinational circuit

designed primarily to compare the relative
magnitude of two binary numbers.
• It receives two n-bit numbers A and B as inputs and
the outputs are A>B, A=B and A<B.
• Depending upon the relative magnitudes of the two
number, one of the outputs will be high.
1-Bit Comparator

Inputs Outputs
𝑌𝐴=𝐵 𝑌𝐴>𝐵 𝑌𝐴<𝐵
0 0 1 0 0

0 1 0 0 1

1 0 0 1 0

1 1 1 0 0
1Inputs Outputs
𝐴1
0
𝐴0
0
𝐵1
0
𝐵0
0
A>B
0
A=B
1
A<B
0
2-Bit Comparator
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0