Chapter 3

Combinational Circuits
LEARNING OBJECTIVES

 Combinational logic design  Code converter

 Arithmetic circuit  Decoder
 Half adder  Designing high order decoders from lower order
 Full adder decoder
 Half subtractor  Combinational logic implementation
 Full subtractor  Encoders
 n-bit comparator  Multiplexer
 Parity bit generator and parity bit checker  Demultiplexer

introduCtion aritHMetiC CirCuits

Combinational logic is a type of logic circuit whose output is a Arithmetic circuits are the circuits that perform arithmetic opera-
function of the present input only. tion. The most basic arithmetic operation is addition.

Inputs Combinational Outputs Half Adder

X circuits Z = F (X ) Addition is an arithmetic operation, and here to implement addi-
tion in digital circuits we have to implement by logical gates. So
the addition of binary numbers will be represented by the logical
expressions. Half adder is an arithmetic circuit which performs
the addition of two binary bits, and the result is viewed in two
CoMBinational loGiC desiGn outputsum and carry.
The design of combinational circuit starts from the problem, state- The sum ‘S’ is the X-OR of ‘A’ and ‘B’ where A and B are
ment and ends with a gate level circuit diagram. inputs.
The design procedure involves the following steps:
∴ S = AB + BA = A ⊕ B
1. Determining the number of input variables and output
variables required, from the specifications. The carry ‘C’ is the AND of A and B.
2. Assigning the letter symbols for input and output. ∴ C = AB
3. Deriving the truth table that defines the required relationship
between input and output. Table 1 Truth Table
4. Obtaining the simplified Boolean function for each output Inputs Outputs
by using K-map or algebraic relations. A B S C
5. Drawing the logic diagram for simplified expressions. 0 0 0 0
We will discuss combinational circuits under the following 0 1 1 0
categories: 1 0 1 0

• Arithmetic circuits 1 1 0 1
• Code converters So, half adder can be realized by using one X-OR gate and
• Data processing circuits one AND gate.
1.36 | Unit 1  •  Digital Logic

A A
S S
B B Full adder
C out
C in

C Figure 1  Block diagram

Table 2  Truth Table
Half adder can also be realized by universal logic such as
A B Cin S Cout
only NAND gate or only NOR gate as given below.
0 0 0 0 0
0 0 1 1 0
NAND logic 0 1 0 1 0
0 1 1 0 1
S = AB + AB 1 0 0 1 0
= AB + AA + AB + BB 1 0 1 0 1
1 1 0 0 1
= A( A + B ) + B( A + B ) 1 1 1 1 1

S = ABCin + ABCin + AB Cin + ABCin

= AAB ⋅ B AB
= A ⊕ B ⊕ Cin
C = AB = A ⋅ B
Cout = ABCin + ABCin + ABCin + ABCin
= AB + (A ⊕ B) Cin
A A·B
S = AB + A Cin + B Cin
B
Full adder can also be realized using universal logic gates,
i.e., either only NAND gates or only NOR gates as explained
below.
C
AB C out = (A ⊕ B )C in + AB
A
Half adder using NAND logic HA A⊕B
B S = A ⊕ B ⊕ C in
(NC) HA
NoR logic C in

S = A ⋅ B + AB Figure 2  Block diagram of full adder by using Half adder

= AB + AA + AB + BB A S + A ⊕ B ⊕ C in
= A( A + B ) + B( A + B ) B

= ( A + B) ( A + B ) (A ⊕ B)C in + AB
= A + B + ( A + B) C out
C = A⋅ B = A ⋅ B = A + B
C in

C
Figure 3  Logic diagram of full adder
A S
B NAND logic
A ⊕ B = AAB B AB
Half adder using NOR logic So A ⊕ B ⊕ Cin
Let A ⊕ B = x then s = X ⋅ XCin Cin X ⋅ Cin
Full Adder = X ⊕ Cin
Full adder is an arithmetic circuit that performs addition of
two bits with carry input. The result of full adder is given by
two outputssum and carry. The full adder circuit is used A
S
in parallel adder circuit as well as in serial adder circuit. B
For full adder, if total number of 1’s is odd at input lines,
the sum output is equal to logic 1, and if total number of C in
C out
1’s at input lines are more than or equal to 2, then the carry
output is logic 1. Figure 4  Logic diagram of a full adder using only 2-input NAND gates
 Chapter 3  •  Combinational Circuits  |  1.37

NOR logic nor logic

Full adder outputs
Sum = a ⊕ b ⊕ c, carry = ab + bc + ac are self dual d = A⊕ B
functions = AB + AB
∴
[ A function is called as self dual if its dual is same as
= AB + BB + AB + AA
the function itself f D = f ]
For self dual functions, the number of NAND gates are = B ( A + B) + A( A + B)
same as number of NOR gates. = B + A+ B + A+ A+ B
By taking the dual for above NAND gate implementa-
tion, all gates will become NOR gates, and the output is b = AB
dual of the sum and carry, but they are self dual (f D = f ). = A( A + B)
So, output remain same, and only 9 NOR gates are required for
full adder, structure similar to NAND gate circuit. = A ( A + B)
= A + ( A + B)
Half Subtractor
Half subtractor is an arithmetic circuit which performs subtrac-
A+A+B
tion of one bit (subtrahend) from other bit (minuend), and the b
result gives difference and borrow each of one bit. The borrow
A
output is logic 1 only if there is any subtraction of 1 from 0. d
B
When a bit ‘B’ is subtracted from another bit ‘A’, a dif-
ference bit (d) and a borrow bit (b) result according to the
rule given below. B+A+B

Table 3  Truth Table Figure 6  logic diagram of half subtractor using NOR gate

A B d b
0 0 0 0
1 0 1 0 full Subtractor
1 1 0 0 Full subtractor is an arithmetic circuit similar to half sub-
0 1 1 1 tractor but it performs subtraction with borrow, it involves
subtraction of three bitsminuend, subtrahend and borrow-
d = AB + BA in, and two outputsdifference and borrow. The subtrac-
=A⊕B tion of 1 from 0 results in borrow to become logic 1. The
b = AB presence of odd number of 1’s at input lines make difference
A as logic 1.
d
B
Table 4  Truth Table

A B bi d b
b
0 0 0 0 0
0 0 1 1 1
Figure 5  Logic diagram of a half subtractor
0 1 0 1 1
A half subtractor can also realized using universal logic either
using only NAND gates or only NOR gates as explained below. 0 1 1 0 1
1 0 0 1 0
NAND logic 1 0 1 0 0
d=A⊕B 1 1 0 0 0
= AAB ⋅ B AB 1 1 1 1 1

b = AB = B( A + B ) = B( AB) = B ⋅ AB
d = ABbi + AB bi + AB bi + ABbi
A · AB
= bi ( AB + AB ) + bi ( AB + AB)
A d
B = bi ( A ⊕ B) + bi ( A ⊕ B)
b = A ⊕ B ⊕ bi
B · AB
1.38 | Unit 1  •  Digital Logic

and Four bit parallel adder the output carry from each full adder
b = A Bbi + ABbi + ABbi is connected to the input carry of next full adder.
The bits are added with full adders, starting from the
= AB + ( A ⊕ B)bi LSB position to form the sum bit and carry bit.
A The longest propagation delay time in parallel adder
d = A ⊕ B ⊕ bi is the time it takes the carry to propagate through the full
B
adders.
bi For n-bit parallel adders consider tpds is the propagation
delay for sum of each full adder and tpdc is the propagation
b delay of carry.
The total time required to add all n-bits at the nth full
adder is
NAND logic TS = tpds + (n – 1)tpdc
d = A ⊕ B ⊕ bi So propagation delay increases with number of bits. To
overcome this difficulty we use look ahead carry adder,
= ( A ⊕ B)( A ⊕ B)bi bi ( A ⊕ B)bi
which is the fastest carry adder.
b = AB + bi ( A ⊕ B)
Ai Pi
Pi ⊕ Ci
= AB + bi ( A ⊕ B) Bi Si

= AB bi ( A ⊕ B)
Gi Pi Ci + Gi
= B( A + B ) bi bi + ( A ⊕ B) Ci + 1

Ci

A
B d
Consider the full adder circuit for ith stage, in parallel adder,
with two binary variables Ai, Bi, input carry Ci are:
bi Carry propagate (Pi) and carry generate (Gi)
b Pi = Ai ⊕ Bi
Gi = Ai ⋅ Bi
Figure 7  Logic diagram of a full subtractor using NAND logic
The output sum and carry can be expressed as

NOR logic Si = Pi ⊕ Ci
Output of full subtractor is also self dual in nature. So, same Ci + 1 = Pi Ci + Gi
circuit, with all NAND gates, replaced by NOR gates gives Now, the Boolean functions for each stage can be calculated
the NOR gate full subtractor. 9 NOR gates required. as substitute i = 0
Example 1: How many NAND gates are required for C0 is input carry
implementation of full adder and full subtractor respectively? C1 = G0 + P0 C0
(A) 11, 10 (B) 11, 11 (C) 9, 9 (D) 9, 10 Substitute i = 1, 2 …
Solution: (C) C2 = G1 + P1C1 = G1 + P1 (G0 + P0C0)
From the circuit diagrams in the previous discussion, full = G1 + P1 G0 + P1 P0 C0
adder requires 9 NAND gates and full subtractor requires
9 NAND gates. C3 = G2 + P2 C2 = G2 + P2 (G1 + P1 G0 + P1 P0 C0)
= G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0
Binary Adder Since the Boolean function for each output carry is
A binary adder is a digital circuit that produces the arithme- expressed in SOP form, each function can be implemented
tic sum of two binary numbers. with AND–OR form or two level NAND gates.
B 3 A3 B 2 A2 B 1 A1 B 0 A0 From the above equations we can conclude that this cir-
cuit can perform addition in less time as C3 does not have to
C3 C2 C1 wait for C2 and C1 to propagate. C3, C2, C1 can have equal
F ·A F ·A F ·A F ·A C in
time delays.
The gain in speed of operation is achieved at the expense
Cout S3 S2 S1 S0 of additional complexity (hardware).
 Chapter 3  •  Combinational Circuits  |  1.39

n-bit Comparator 1 0 1 1 1 0 0
The comparison of two numbers is an operation that deter- 1 1 0 0 0 0 1
mines whether one number is greater than, less than, or 1 1 0 1 0 0 1
equal to the other number. 1 1 1 0 0 0 1
A magnitude comparator is a combinational circuit that 1 1 1 1 0 1 0
compares two input numbers A and B, and specifies the out-
put with three variables, A > B, A = B, A < B: (a < b) = S(1, 2, 3, 6, 7, 11)
(a > b) = S(4, 8, 9, 12, 13, 14)
A L A<B
(a = b) = S(0, 5, 10, 15)
b 1b 0
Magnitude 00 01 11 10
E A=B a1a 0
comparator
B A>B 00 1 1 1
G

01 1 1

a L a<b 11
1-bit
E a=b 00 1
Comparator
b G a>b
a < b = a1′a0′b0 + a0′b1b0 + a1′b1

Figure 8  1-bit comparator will have only 1 bit input a, b.

L = a1 b1 + ( a1  b1 ) a0 b0
Similarly, a > b = a0b1′b0′ + a1a0b0′ + a1b1′
a b a<b a=b a>b
0 0 0 1 0 G = a1 b1 + ( a1  b1 ) a0 b0
0 1 1 0 0 a = b is possible when a1 = b1, a0 = b0
1 0 0 0 1
So (=a b= ) ( a1  b1 )( a0  b0 )
1 1 0 1 0
A3
By considering minterms for each output. A2
A1 L A<B
(a < b) = a′b
A0
(a = b) = a′b′ + ab = a ⊙ b 4-bit
E A=B
(a > b) = ab′ B3 Comparator
B2
G A>B
B1
a1 L a<b B0
a0
2-bit
E a=b
b1 Comparator Figure 10  4-bit comparator will compare 2 input numbers each of
b0 4-bits A3 A2 A1 A0 and B3 B2 B1 B0 (A = B) output will be 1 when each
G a>b
bit of input A is equal to corresponding bit in input B.

Figure 9  2-bit comparator will have 2-bit inputs a1 a0 and b1 b0. So we can write (A = B) = (A3 ⊙ B3) (A2 ⊙ B2) (A1 ⊙ B1)
(A0 ⊙ B0).
L E G To determine whether A is greater or less than B, we
a1 a0 b1 b0 a<b a=b a>b inspect the relative magnitudes of pairs of significant bits,
0 0 0 0 0 1 0 starting from MSB. If the two bits of a pair are equal, we
0 0 0 1 1 0 0 compare the next lower significant pair of bits. The com-
0 0 1 0 1 0 0 parison continues until a pair of unequal bits is reached.
0 0 1 1 1 0 0 for A < B, A = 0, B = 1
0 1 0 0 0 0 1 for A > B, A = 1, B = 0
0 1 0 1 0 1 0 A < B = A3′B3 + (A3 ⊙ B3) A2′B2 + (A3 ⊙ B3)(A2 ⊙ B2)
0 1 1 0 1 0 0 × A1′B1 + (A3 ⊙ B3)(A2 ⊙ B2) (A1 ⊙ B1) A0′B0
0 1 1 1 1 0 0 A>B=A  3B3′ + (A3 ⊙ B3) A2B2′ + (A3 ⊙ B3) (A2 ⊙ B2)
1 0 0 0 0 0 1 × A1B1′ + (A3 ⊙ B3)(A2 ⊙ B2) (A1 ⊙ B1) A0B0′
1 0 0 1 0 0 1 4-bit comparator will have total 8 inputs and 28 = 256 input
1 0 1 0 0 1 0 combinations in truth table.
1.40 | Unit 1  •  Digital Logic

For 16 combinations (A = B) = 1, and for 120 combina- Decimal B2 B1 B0 G2 G1 G0

tions A < B = 1. 0 0 0 0 0 0 0
For remaining 120 combination A > B = 1 1 0 0 1 0 0 1
2 0 1 0 0 1 1
Parity Bit Generator and Parity Bit Checker
3 0 1 1 0 1 0
When digital information is transmitted, it may not be 4 1 0 0 1 1 0
received correctly by the receiver. To detect one bit error at 5 1 0 1 1 1 1
receiver we can use parity checker.
6 1 1 0 1 0 1
For detection of error an extra bit, known as parity bit, is
7 1 1 1 1 0 0
attached to each code word to make the number of 1’s in the
code even (in case of even parity) or odd (in case of odd parity). For conversion we have to find out minimized functions of
For n-bit data, we use n-bit parity generator at the trans- G2(B2, B1, B0) = ∑m(4, 5, 6, 7)
mitter end. With 1 parity bit and n-bit data, total n + 1 bit G1(B2, B1, B0) = ∑m(2, 3, 4, 5)
will be transmitted. At the receiving end n + 1 parity checker G0(B2, B1, B0) = ∑m(1, 2, 5, 6)
circuit will be used to check correctness of the data. B2
For even parity transmission, parity bit will be made 1 B0B1 00 01 11 10
or 0 based on the data, so that total n + 1 bits will have 0 1 1
even number of 1’s. For example, if we want to transmit data 1
1 1
1011 by even parity transmission, then we will use parity bit
as 1, so data will have even number of 1’s, i.e., data trans- G0(B2, B1, B0) = B′1B0+ B1B′0= B1 ⊕ B0
mitted will be 11011. At the receiving end this data will be
B2
received and checked for even number of ones. B0B1 00 01 11 10
To transmit data B3B2B1B0 using even parity, we will 0 1 1
transmit sequence P B3B2B1B0, where P = B3 ⊕ B2 ⊕ B1 ⊕ B0. 1 1 1
(Equation for parity generator)
G1(B2, B1, B0) = B′1B2+ B1B′2= B2 ⊕ B1
At the receiving end we will check data received
PB3B2B1B0 for error, E = P ⊕ B3 ⊕ B2 ⊕ B1 ⊕ B0 (equation B2
for parity checker). If E = 0 (no error), or if E = 1 (1 bit error). B0B1 00 01 11 10
0
We use EX-OR gates for even parity generator/checker
1 1 1 1 1
as EX-OR of bits gives output 1 if there are odd number of
1’s else EX-OR output is 0. G2(B2, B1, B0) = B2
Odd parity generator/checker is complement of even B2 G2
parity generator/checker. Odd parity circuits check for pres-
ence of odd number of 1’s in data.
G1
B1
Code Converters
There are many situations where it is desired to convert G0
B0
from one code to another within a system. For example, the
In similar fashion we can derive n-bit binary to gray code
information from output of an analog to digital converter is
conversion as
often in gray code, before it can be processed in arithmetic
Gn = Bn
unit, conversion to binary is required.
Gn-1 = Bn-1 ⊕ Bn
Let us consider simple example of 3-bit binary to gray
Gi-1 = Bi-1 ⊕ Bi
code converter. This will have input lines supplied by binary
codes and output lines must generate corresponding bit com- Thus conversion can be implemented by n - 1 X-OR gates
bination in gray code. The combination circuit code con- for n-bits.
verter performs this transformation by means of logic gates. For reverse conversion of gray to binary, by following
The output logic expression derived for code converter similar standard principle of conversion, we will get
can be simplified by using the usual techniques including B0 = G0 ⊕ G1 ⊕ G2, B1 = G1 ⊕ G2, B2 = G2
‘don’t-care’ if any present. For example, BCD code uses
G0
only codes from 0000 to 1001 and remaining combinations B0
are treated as don’t-care combinations. Similarly, EXS-3
uses only combinations from 0011 to 1100 and remaining
G1
combinations are treated as don’t-care. B1
The relationship between the two codes is shown in the
following truth table: G2 B2
 Chapter 3  •  Combinational Circuits  |  1.41

In general for n-bit gray to binary code conversion Y0

Bi = Gn ⊕ Gn-1 ⊕ Gn-2 …⊕ Gi-1 ⊕ Gi B1 2×4 Y1
B0 Decoder Y2
Bn = Gn (MSB is same in gray and binary). It also requires
Y3
n-1 X-OR gates for n-bits.
Example 2:  Design 84-2-1 to XS-3 code converter. EN

Solution:  Both 84-2-1 and XS-3 are BCD codes, each needs Figure 11  2 × 4 decoder
4-bits to represent. The following table gives the relation
between these codes. 84-2-1 is a weighted code, i.e., each Table 5  Truth Table
position will have weight as specified. XS-3 is non-weighted EN B1 B0 Y3 Y2 Y1 Y0
code; the binary code is 3 more than the digit in decimal. 0 X X 0 0 0 0
84-2-1 XS-3 1 0 0 0 0 0 1
Decimal B3B2B1B0 X3X2X1X0 1 0 1 0 0 1 0
0 0000 0011 1 1 0 0 1 0 0
1 0111 0100 1 1 1 1 0 0 0
2 0110 0101
3 0101 0110
Y 0 = EN · A · B
4 0100 0111
5 1011 1000
Y 1 = EN · A · B
6 1010 1001 A
7 1001 1010
8 1000 1011 B Y 2 = EN · A · B
9 1111 1100 EN
Y 3 = EN · A · B
We will consider minterm don’t-care combinations as 1, 2, 3,
12, 13, 14. For these combinations 84-2-1 code will not exist
Figure 12  2 × 4 decoder
and the remaining minterms can be found from truth table.
X0(B3, B2, B1, B0) = ∑m(0, 4, 6, 8, 10) Decoder outputs are implemented by AND gates, but reali-
+ ∑ Φ(1, 2, 3, 12, 13, 14) = B0 zation of AND gates at circuit level is done by the NAND
gates (universal gates). So, the decoders available in IC form
X1(B3, B2, B1, B0) = ∑m(0, 4, 5, 8, 9, 15) are implemented with NAND gates, i.e., the outputs are in
+ ∑ Φ(1, 2, 3, 12, 13, 14) = B1 complemented form and outputs are maxterms of the inputs
rather than minterms of inputs as in AND gate decoders.
X2(B3, B2, B1, B0) = ∑m(4, 5, 6, 7, 15) Furthermore, decoders include one or more enable inputs
+ ∑Φ(1, 2, 3, 12, 13, 14) = B2 to control the circuit operation. Enable can be either active
X3(B3, B2, B1, B0) = ∑m(8, 9, 10, 11, 15) low/high input.
+ ∑Φ(1, 2, 3, 12, 13, 14) = B3
EN

Decoder 2×4
Y 0 = EN + B1 + B0
A binary code of n-bits is capable of representing up to 2n B1 Decoder Y 1 = EN + B1 + B0
elements of distinct elements of coded information. B0 with NAND Y 2 = EN + B1 + B0
gates
The three inputs are decoded into eight outputs, each rep- Y 3 = EN + B1 + B0
resenting one of the minterms of the three input variables.
A decoder is a combinational circuit that converts binary Figure 13  Active low 2 × 4 decoder
information from n input lines to a maximum 2n unique out-
put lines. Table 6  Truth Table
A binary decoder will have n inputs and 2n outputs. EN B1 B0 Y3 Y2 Y1 Y0
EN 1 X X 1 1 1 1
0 0 0 1 1 1 0
2n
Outputs 0 0 1 1 1 0 1
n n × 2n
Inputs Decoder 0 1 0 1 0 1 1
0 1 1 0 1 1 1
1.42 | Unit 1  •  Digital Logic

The block diagram shown here is 2 × 4 decoder with Designing High Order Decoders from Lower
active low output and active low enable input. Order Decoders
The logic diagram is similar to the previous 2 × 4 decoder,
Decoder with enable input can be connected together to
except, all AND gates are replaced by NAND gates and EN
form larger decoder circuit.
will have inverter, EN is connected to all NAND inputs, as
The following configuration shows 3 × 8 decoder with
EN is active low input for this circuit.
2 × 4 decoders.
The decoder is enabled when EN is equal to 0.
As shown in the truth table, only one output can be equal B2
to 0 at any given time, all other outputs are equal to 1. The EN Y0
output whose value is equal to 0 represents the minterm B1 2×4 Y1
selected by inputs, enable. B0 Decoder Y2
Y3
Consider a 3–8 line decoder

Table 7  Truth Table Y4

EN
Inputs Outputs B1 2×4 Y5
A B C D0 D1 D2 D3 D4 D5 D6 D7 B0 Decoder Y6
Y7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
When B2 = 0, top decoder is enabled and other is disa-
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0 bled, for 000–011 inputs, outputs are Y0–Y3, respectively,
1 0 0 0 0 0 0 1 0 0 0 and other outputs are 0.
1 0 1 0 0 0 0 0 1 0 0 For B2 = 1, the enable conditions are reversed.
1 1 0 0 0 0 0 0 0 1 0 The bottom decoder outputs generates minterms 100–
1 1 1 0 0 0 0 0 0 0 1
111, while the outputs of top decoder are all 0’s. 5 × 32
A 3–8 decoder has 3 input lines and 8 output lines, based decoder with 3 × 8 decoders, 2 × 4 decoders
on the combination of inputs applied for the 3 inputs, one of
the 8 output lines will be made logic 1 as shown in the truth EN Y0
table. So, each output will have only one minterm. B2 3×8
B1 Dec
B0 Y7
A
B
C
D 7 = ABC EN Y8
EN B2 3×8
B1 Dec
B4 B0 Y 15
D6 = ABC 2×4
B3 Decoder

EN Y 16
B2 3×8
D5 = ABC
B1 Dec
B0 Y 23

D4 = ABC
EN Y 24
B2 3×8
B1 Dec
D 3 = ABC B0 Y 31

5 × 32 decoder will have 5 inputs B4 B3 B2 B1 B0. 3 × 8 decoder

will have 8 outputs, so 5 × 32 requires four 3 × 8 decoders, and
D2 = ABC
we need one of the 2 × 4 decoders to select one 3 × 8 decoders
and the connections are as shown in the circuit above.

D1 = ABC
Combinational Logic Implementation
An n × 2n decoder provides 2n minterms of n input variables.
Since any Boolean function can be expressed in sum-of-
D0 = ABC
minterms form, a decoder that generates the minterms of
 Chapter 3  •  Combinational Circuits  |  1.43

the function, together with an external OR gate that forms (A) PQ + PR (B)
P + QR
their logical sum, provides a hardware implementation of
the function. (C) P (Q + R) (D)
Q ( P + R)
Similarly, any function with n inputs and m outputs can
be implemented with n × 2n decoders and m OR gates. 0
Example 3:  Implement full adder circuit by using 2 × 4 R B2 1
decoder. 2
Sum = S (1, 2, 4, 7), Carry = S (3, 5, 6, 7) Q B1
3×8 3 F (P, Q, R)
Decoder 4
0 5
A B2 1 Sum P 6
B0
2 7
3×8 3
B B1
Decoder 4
5 Solution: (C)
C B0 6 Carry The outputs of decoder are in normal form. 0, 2, 3, 4, 6
7 outputs are connected to NOR gate to form F(P, Q, R)
So F = Y0 + Y2 + Y3 + Y4 + Y6
Figure 14  Implementation of full adder circuit with decoder
= Y0 ⋅ Y2 ⋅ Y3 ⋅ Y4 ⋅Y6
The 3 × 8 decoder generates the 8 minterms for A, B, and
C. The OR gate for output sum forms the logical sum of Y0, Y1,…, Y7 indicate minterms, whereas Y0 , Y1 , , Y7 are
minterms 1, 2, 4 and 7. The OR gate for output carry forms maxterms.
the logical sum of minterms 3, 5, 6 and 7. So F = p (0, 2, 3, 4, 6)
Here, from the decoder circuit MSB is R, LSB is P.
Example 4:  The minimized SOP form of output F(x, y, z) is
By using K-map
(A) x′ y + z′ (B) x′ y′ + z′
(C) x′ y′ + z′ (D) x′ + y′ z
QP
R 00 01 11 10
0 0 0 0
0
x B2 1 1 0 0
2
3×8 3 F F ( P , Q , R) = P ( R + Q )
y B1
Decoder 4
5
z B0 6 Encoders
7 It is a digital circuit that performs the inverse operation of
a decoder.
An encoder has 2n (or fewer) input lines and n output
Solution: (C) lines.
The outputs of decoder are in active low state. So, we can It is also known as an octal to binary converter.
express outputs as Y7 , Y6  Y0 Consider an 8–3 line encoder:
Outputs 0, 1, 3, 5, 7 are connected to NAND gate to form
function F(x, y, z) Table 8  Truth Table

So F = Y0 ⋅ Y1 ⋅ Y3 ⋅Y5 ⋅Y7 Inputs Outputs

=Y0 + Y1 + Y3 + Y5 + Y7 D0 D1 D2 D3 D4 D5 D6 D7 A B C
=S(0, 1, 3, 5, 7) 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
By using K-maps
yz 0 0 1 0 0 0 0 0 0 1 0
x 00 01 11 10
0 0 0 1 0 0 1 0 0 1 1
0 1 1 1
0 0 0 0 1 0 0 1 1 0 0
1 1 1
0 0 0 0 0 1 0 0 1 0 1
F = z + x′y′ 0 0 0 0 0 0 1 0 1 1 0
Example 5.  The minimal POS form of output function f(P, 0 0 0 0 0 0 0 1 1 1 1
Q, R) is
1.44 | Unit 1  •  Digital Logic

Octal inputs The MUX has several data input lines and a single output
line. It also has data select inputs that permits digital data
D1 D2 D3 D4 D5 D6 D7
on any one of the inputs to be switched to the output line.
Binary outputs Depending upon the binary code applied at the selection
C = D1 + D3 + D5 + D 7 inputs, one (out of 2n) input will be gated to single output.
It is one of the most widely used standard logic circuits in
digital design. The applications of multiplexer include data
B = D2 + D 3 + D6 + D 7 selection, data routing, operation sequencing, parallel to
serial conversion, and logic function generation.
A = D4 + D5 + D6 + D 7 2n inputs will be controlled by n selection lines and mul-
tiplexer will have 1 output, we denote it as 2n × 1 multi-
plexer (data selector).
Figure 15  Logic diagram
In other words, a multiplexer selects 1 out of n input data
sources and transmits the selected data to a single output
Priority Encoder channel, this is called as multiplexing.
A priority encoder is an encoder circuit that includes the
priority function. Basic 2 × 1 Multiplexer
When two or more inputs are present, the input with The figure shows 2 × 1 multiplexer block diagram; it will
higher priority will be considered. have 2 inputsI0 and I1, one selection line S, and one output
Consider the 4 × 2 priority encoder. Y. The function table is as shown here.
I0 B1 EN S Y
I1 4×2 B0 0 x 0
I2 Encoder
I3 V 1 0 I0
1 1 I1
I3 I2 I1 I0 B1 B0 V
1 X X X 1 1 1
0 1 X X 1 0 1
EN
0 0 1 X 0 1 1 I0 Y
0 0 0 1 0 0 1 2×1
0 0 0 0 X X 0 MUX
I1
I3-I0 are inputs and B1 B0 are binary output bits, valid (V) S
output is set to 1, when at least one input is present at input
(I3 - I0).
When there is no input present, (I3 - I0 = 0000) then V = 0,
for this combination the output B1B0 will not be considered. The output equation of 2 × 1 multiplexer is
The higher the subscript number, the higher the priority Y = EN ( I 0 S + I1S ).
of the input. Input I3 has the highest priority, I2 has the next When enable is 1, the multiplexer will work in normal
priority level. Input I0 has lowest priority level. The Boolean mode, else the multiplexer will be disabled.
expressions for output B1 B0 are Sometimes enable input will be active low enable EN ,
then Y = EN ( I 0 S + I1S ).
B1 = I 3 + I 3 I 2
= I3 + I2 The 4 × 1 Multiplexer
B0 = I 3 + I 3 I 2 I1
D0
= I 3 + I 2 I1 D1 Output
4×1
V = I3 + I2 + I1 + I0 D2 MUX y
D3
Data input’s
Multiplexer
A multiplexer (MUX) is a device that allows digital infor- S1 S0
mation from several sources to be converted on to a single
Selected
line for transmission over that line to a common destination. lines
 Chapter 3  •  Combinational Circuits  |  1.45

If a binary zero S1 = 0 and S0 = 0 as applied to the data select Solution:  Y = ( I 0 S + I1S ) = A. It Implements NOT gate.
line the data input D0 appear on the data output line and so on.
S1 S0 y Example 7:  What should be the connections to implement
0 0 D0
NAND gate by using 2 × 1 MUX?
0 1 D1 Solution:  Y = AB = A + B = A + AB = 1 ⋅ A + B ⋅ A
1 0 D2
By considering I0 = 1, I1 = B, S = A, we can implement
1 1 D3
NAND gate, or by interchanging A and B also we can get
the same answer.
y = S1 S0 D0 + S1S0 D1 + S1S0 D2 + S1S0 D3
S0
1 I0 Y
S1 0 I1
4×1
0 I2 MUX
D0
1 I3
S1 S2

D1
A B
y
For the above 4 × 1 multiplexer Y = AB + AB = X-NOR gate,
D2 similarly to implement 2 input gates by using 4 × 1 multiplexer,
the inputs I0, I1, I2, I3 should be same as the terms in the truth
table of that gate.
D3
Logic Function Implementation
Figure 16  Logic diagram by Using Multiplexer
Let us consider a full subtractor circuit (borrow) to be
For 8 × 1 multiplexer with 8 inputs from I0–I7 based on
implemented by using multiplexer.
selection inputs S2 S1 S0, the equation for output
Full subtractor borrow (B) is a function of 3 inputs X, Y,
Y = I 0 S2 S1S0 + I1 S2 S1S0 + I 2 S2 S1 S0 + I 3 S2 S1S0 Z. The truth table is
+ I 4 S2 S1S0 + I 5 S2 S1S0 + I 6 S2 S1 S0 + I 7 S2 S1S0 X Y Z B 4 × 1 MUX 2 × 1 MUX
From multiplexer equation, we can observe, each input is 0 0 0 0
B=Z
associated with its minterm (in terms of selection inputs). 0 0 1 1
B=Y+Z
0 1 0 1
Basic Gates by Using MUX B=1
0 1 1 1

B I0 1 0 0 0
Y B=0
1 0 1 0
2×1 B = YZ
MUX 1 1 0 0
B I1 B=Z
1 1 1 1
S
To implement borrow by using 8 × 1 multiplexer, connect
the three variables X, Y, Z directly to selection lines of the
A multiplexer, and connect the corresponding values of B to
inputs, i.e., for I0 = 0, I1 = 1, I2 = 1, etc. as per above truth table.
Figure 17  X-OR gate by using 2 × 1 MUX
To implement borrow by using 4 × 1 multiplexer, con-
Y = AB + AB = X-OR gate, we can interchange inputs A nect any two variables to selection lines (in this case X, Y)
and B also, and write output (B) in terms of other variable, for XY = 00,
By interchanging inputs I0 and I1, Y = A B + AB, X-NOR output B is same as Z, so connect I0 = Z, similarly 1, 0, Z for
gate. remaining inputs.
Similarly, we can build all basic gates by using 2 × 1 To implement the function by using 2 × 1 multiplexer,
multiplexer. connect 1 variable as selection line (in this case consider X)
Example 6:  If I0 = 1, I1 = 0, S = A, then Y is and write output (B) in terms of other variables, for X = 0,
1.46 | Unit 1  •  Digital Logic

output B is varies as B = Y + Z, so connect I0 = Y + Z. For X In a similar fashion, to design 4 × 1 MUX, we require 3, 2 × 1

= 1, output B varies as B = YZ, connect I1 = YZ. multiplexers, and to design 8 × 1 multiplexer, we require 7,
N–variable function can be implemented by using 2N-1 × 2 × 1 multiplexers.
1 multiplexer without any extra hardware.
Demultiplexer
Implementation of Higher Order The demultiplexer [DeMUX] basically serves opposite of
Multiplexer by Using Lower the multiplexing function. It takes data from one line and
Order Multiplexers distributes them to a given number of output lines.
By using lower order multiplexers, we can implement higher The other name for demultiplexer is data distributor, as it
order multiplexers, for example by using 4 × 1 multiplexer, receives information on a single line and distributes it to a
we can implement 8 × 1 MUX or 16 × 1 MUX or other possible 2n output lines, where n is the number of selection
higher order multiplexers. lines, and value of n selects the line.
Let us consider implementation of 16 × 1 MUX by using D0
4 × 1 MUX. 16 × 1 MUX will have inputs I0–I15 and selec-
D1
tion lines S0–S3, whereas 4 × 1 MUX will have only 4 input E
1×4
lines, and 2 selection lines, so we require four 4 × 1 MUX DEMUX D2
input
to consider all inputs I0–I15, and again to select one of the D3
four outputs of these four multiplexers one more 4 × 1 mul-
tiplexer is needed (for which we will connect higher order
selection lines S2 and S3). So, total of 5, 4 × 1 multiplexers
S1 S0
are required to implement 16 × 1 MUX.
Multiplexer S1 S0 D3 D2 D1 D0
I0 S1 D 0 0 0 0 0 E
0 1 0 0 E 0
1 0 0 E 0 0
I3 S4
C1 C2 1 1 E 0 0 0

When S1S0 = 10; D2 will be same as input E, and other

S0 S1
outputs will be maintained at zero (0).
Multiplexer E
D 0 = ES 1S 0
I4 S1 D

D 1 = ES 1S 0
Multiplexer
I7 S4
C1 C2 S1 D
D 2 = ES 1S 0

S0 S1
Multiplexer S4 D 3 = ES 1S 0
I8 S1 D C1 C2
S1 S0
S2 S3 Figure 17  Logic diagram
I 11 S4
C1 C2
Solved Examples
S0 S1
Example 1:  The multiplexer shown in the figure is a 4 : 1
Multiplexer multiplexer. The output z is
I 12 S1 D
I3
C
I2 MUX
I 15 S4 Z
I1 4×1
C1 C2 C
I0
S1 S0
S0 S1

Figure 18  Realization of 16 x 1 multiplexer by using 4 x 1 multiplexers A B

 Chapter 3  •  Combinational Circuits  |  1.47

Solution: = A + CB
A1 B0 Z
= A + C + B = ABC
0 0 C \  NAND Gate
0 1 C
Example 4:  In the TTL circuit in figure, S2–S0 are select
1 0 C
lines and x7–x0 are input lines. S0 and X0 are LSBs. The
1 1 C output Y is

1
∴ Z = A BC + ABC + ABC + AB C
0

= B( AC + AC ) + B( AC + AC ) X0 X1 X2 X3 X4 X5 X6 X7
0 S2
= ( AC + AC )( B + B)( x + x = 1) A 8 : 1 MUX y
∴ = AC + AC = A ⊕ C B S1

C S0
Example 2:  The logic circuit shown in figure implements
D0
Solution:  S2 = A, S1 = B, S0 = C
C I0 D1
D2 S2(A) S1(B) S0(C) Y
I1 3 to 8 D3
B 0 0 0 1
Decoder
D4
0 0 1 0
A I2 D5
0 1 0 0
D6
D7 0 1 1 1
1 0 0 0
D 1 0 1 1
1 1 0 1
1 1 1 0
Solution:  z = D( A B C + A BC + ABC + AB C + ABC )

= D( A B(C + C ) + BC ( A + A) + AB C ) Y = A B C + ABC + ABC + ABC

× D( B A + B C + BC ) = C ( A B + AB) + C ( AB + AB )
= D( B Θ C + AB) Y = C ( A ⊕ B) + C ( A ⊕ B) = A ⊕ B  C

Example 3.  The network shown in figure implements Example 5:  The logic realized by the adjoining circuit is

A 0
A 1 MUX
f2 1 MUX
F
1 0 2
Select
S0 A 3 lines
S1 S0

MSB
B 1 MUX
B C
f1

0 0 Solution:  F = B CA + BCA + BC A + BC A
S0 × C ( BA + B A) + C ( BA + B A)
× AB + AB(C + C ) = A ⊕ B
c
Example 6:  Consider the following multiplexer, where I0,
Solution:  f1 = C 0 + CB = CB, f1 = CB I1, I2, I3 are four date input lines selected by two address
F2 = f1 + f1 A = A ⋅ CB + CB line combinations AIA0 = 00, 01, 10, 11, respectively and f
1.48 | Unit 1  •  Digital Logic

is the output of the multiplexer. EN is the enable input, the Solution:  A1 = y ⋅ A0 = z , EN = z

function f (x, y, z) implemented by the below circuit is
A1 A0 S I
x I0 0 0 x
(yz )
I1
0 1 (y z) x
y I2
1 0 (y z ) y
4×1 F (x, y, z)
I3
MUX
A1 1 1 (yz) y
z A0
EN
f ( x, y, z ) = S.I = ( xy + 0 + yz ) ⋅ EN
= xy ⋅ z

Exercises
Practice Problems 1 (A) are high; and G, G2 are low
Directions for questions 1 to 21:  Select the correct alterna- (B) are high; and G is low G2 is high
tive from the given choices. (C) are high; and G, G2 are high
(D) are high; and G is high G2 is low
1. The binary number 110011 is to be converted to gray
code. The number of gates and type required are 5. The MUX shown in figure is 4 × 1 multiplexer the
(A) 6, AND (B) 6, X-NOR output z is
(C) 6, X-OR (D) 5, X-OR
2. The number of 4-to 16-line decoder required to make
an 8- to 256-line decoder is C I0
(A) 16 (B) 17 I1 MUX
(C) 32 (D) 64 Z
I2 4×1
3. f (x2, x1, x0) = ?
I3
S1 S0
D0
x0 I0 D1
D2 +5 V A B
x1 I1 3 to 8 D3 f
Decoder
D4 (A) A B C
x2 I2 D5 (B) A⊕B⊕C
D6 (C) A Q B Q C
D7
(D) A+B+C

(A) p(1, 2, 4, 5, 7) (B) Σ(1, 2, 4, 5, 7) 6. If a 4 to 1 MUX (shown below) realizes a three vari-
(C) Σ(0, 3, 6) (D) p(0, 2, 3, 6) able function f ( x, y, z ) = xy + xz then which of the
following is correct?
4. A 3-to-8 decoder is shown below

8
I0
3 7
6 I1 4 to 1
F(x, y, z)
5 Output I2 MUX
Input 2
4
I3
3 S1 S0
1
2
(MSB)
G2 G 1
Y Z

Enable Signal I0 = X, I1 = 0, I2 = X, I3 = X
(A)
decoder decoder I0 = 0, I1 = 1, I2 = Y1, I3 = X
(B)
I0 = X, I1 = 1, I2 = 0, I3 = X
(C)
All the output lines of the chip will be high except pin
8, when all the inputs 1, 2, and 3 I0 = X, I1 = 0, I2 = X, I3 = Z
(D)
 Chapter 3  •  Combinational Circuits  |  1.49

7. The circuit shown in the figure is same as (C) AB + BC + AC

(D) AB + BC + AC
I0 4:1 11. Find the function implemented.
I1
y
I2 P I3
P I2
I3
Q 4×1 Z
S1 S0
a P I1
b I0
P
c S1 S2
Q
(A) two input NAND gate with a and c inputs
(B) two input NOR gate with a and c inputs R S
(C) two input X-OR gates with a and b inputs
(D) two input X-NOR gate with b and c inputs PQ + PS + Q RS
(A)
PQ + PQR + PQS
(B)
8. If the input x3, x2, x1, x0 to the ROM in the figure are
8421 BCD numbers, then the outputs y3, y2, y1, y0 are PQ R + PQR + PQRS + Q RS
(C)
x3 x2 x1 x0 (D) PQR + PQRS + PQRS + Q R S
12. Which function is represented by the given circuit?
A
B x
ROM

C y
BCD to Decimal decoder
(A) Full adder (B) Full subtractor
(C) Comparator (D) Parity generator
D0 D1 D8 D9
13. Which of the following represents octal to binary
y3 encoder?
y2 D0
(A) D1 D2 D3 D4 D5 D6 D7
y1
y0 A2

A1
(A) gray code numbers (B) 2421 BCD
(C) Excess – 3 code numbers (D) 84–2–1 A0
9. A 4-bit parallel full adder without input carry requires
(A) 8 HA, 4 OR gates (B) 8 HA, 3 OR gates D0 D1 D2 D3 D4 D5 D6 D7
(B)
(C) 7 HA, 4 OR gates (D) 7 HA, 3 OR gates
10. In the circuit find X.
A2

0 I0 0 I0 A1

1 I1 1 I1
4×1 y 4×1 y x A0
1 I2 1 I2

0 I3 0 I3 D0 D1
(C) D2 D3 D4 D5 D6 D7
S1 S0 S1 S0

A2
A B C
A1
ABC + ABC + ABC + ABC
(A)
A0
(B) ABC + ABC + ABC + ABC
1.50 | Unit 1  •  Digital Logic

D0 D1
(D) D2 D3 D4 D5 D6 D7 X = A′BC′ + B′C′, y = A + B
(A)
X = A′C′ + B′C′, y = 1
(B)
A2
=
(C) X A=
, y 0
A1 =
(D) X A=
, y 1
18. A relay is to operate with conditions that it should be on
A0 when the input combinations are 0000, 0010, 0101, and
0111. The states 1000, 1001, 1010 don’t occur. For
14. For a MUX to function as a full adder what should be rest of the status, relay should be off. The minimized
the input provided to the I0, I1, I2, I3 if the A and B are the Boolean expression notifying the relationship is
select lines? (A) BC + ACD
(B) BD + ABD
I0
(C) BD + AC
I1
4×1 F (D) AB + CD
I2
19. If a function has been implemented using MUX as
I3
S1 S0 shown, implement the same function with a and c as
the select lines
A B
a
(A) I =
0 I=1 Cin ; I=
2 I=
3 Cin 0
4×1 y
1
I=
(B) 0 I=1 Cin ; I=
2 I=
3 Cin a

I=
(C) 0 I=
3 Cin ; I=
1 I=
2 Cin
b c
(D) I=
0 I=
3 Cin ; I=
1 I=
2 Cin
15. The given circuit act as (A)
b
(B) 0
b 1
4×1 4×1
c 1 0 b
MUX y1 0 b
c 0
S0
a 1
y0 a c a c
MUX
a 0
S0 S0
c 1 (C) (D)
MUX y2 b 1
b b 0 b 1
4×1
4×1 1
1
0 1
(A) Full adder (B) Half adder
(C) Full subtractor (D) Half subtractor a c a c
16. For a 4 × 16 decoder circuit, the outputs of decoder
(y0, y1, y4 . y5 . y10 . y11 . y14 . y15) are connected to 8 input 20. The circuit is used to convert one code to another.
NOR gate, the expression of NOR gate output is Identify it.
(A) A ⊕ D (B) A⊙D
A3 B3
(C) A ⊙ C (D) A⊕C
17. The function implemented by decoder is B2
A2
D0
A D1 A1 B1
X
D2
3 to 8 D3 A0 B0
B
Decoder
D4
C D5 Y
(A) Binary to gray
D6 (B) Gray to binary
D7 (C) Gray to XS–3
(D) Gray to 8421
 Chapter 3  •  Combinational Circuits  |  1.51

21. The Boolean function realised by logic circuit is F = Σm(0, 1, 3, 5, 9, 10, 14)
(A)
F = Σm(2, 3, 5, 7, 8, 12, 13)
(B)
C I0
F = Σm(1, 2, 4, 5, 11, 14, 15)
(C)
D I1 4:1
MUX Y F(A, B, C, D) (D) F = Σm(2, 3, 5, 7, 8, 9, 12)
I2
I3
S1 S0

A B

Practice Problems 2 C I0
Directions for questions 1 to 21:  Select the correct alterna- C I1
tive from the given choices. 4:1 F
C I2 MUX
1. For a binary half subtractor having two input A and B,
the correct set of logical expression for the outputs D C I3
S0 S1
= (A minus B) and X (borrow) are
B
D = AB + AB, X = AB
(A) A
D = AB + AB +, AB, X = AB
(B)
(A) AB + BC + CA + BC (B) A ⊕ B ⊕ C
D = AB + AB, X = AB
(C) (C) A ⊕ B (D) B⊕C
(D) D = AB + A B, X = AB 5. Full subtractor can be implemented by using
2. The function ‘F’ implemented by the multiplexer chip
(A) 3-to-8 line decoder only
shown in the figure is (B) 3-to-8 line decoder and one OR gate
0 1 0 1 (C) 3-to-8 line decoder and two OR gates
(D) None
I0 I1 I2 I3 6. What are the difference and borrow equations for the
A S1 above circuit?
Y F (A) D = x Q y Q z, B = x′y + yz + zx′
B S0
(B) D = X ⊕ y ⊕ z, B = xy + yz + zx
(C) D = x ⊕ y ⊕ z, B = x′y + yz + zx′
(A) A (B) B (D) A and C both
(C) (D) 7. Combinational circuits are one in which output depends
AB AB + AB
_________, whereas sequential circuit’s output depends
3 The following multiplexer circuit is equal to _________
(A) only on present input, only on past input
0 4:1 (B) only on present input, only on past and future input
MUX
1 (C) only on present input, only on present input and
y past output
2
(D) on present input, on past and present output
3
S1 S0 8. The sum output of the half adder is given by (assume A
a
b
and B as inputs)
c S = ( A + B) AB
S = AB( A + B) (B)
(A)
S = ( A + B )( AB )
S = ( A + B)( AB) (D)
(C)
(A) implementation of sum equation of full adder
(B) implementation of carry equation of full adder 9. MUX implements which of the following logic?
(C) implementation of borrow equation of full (A) NAND–XOR (B) AND–OR
substractor (C) OR–AND (D) XOR–NOT
(D) all of the above 10. A DeMUX can be used as a
4 The output ‘F’ of the multiplexer circuit shown in the (A) Comparator (B) Encoder
figure will be (C) Decoder (D) Adder
1.52 | Unit 1  •  Digital Logic

11. If we have inputs as A, B and C and output as S and D. (C) a 0 (D)

a 0
We are given that S = A ⊕ B ⊕ C. D = BC + AB + AC .
Which of the circuit is represented by it?
Y F A F A
1 1

X
A B A B A B A B s c s c
C D C D C D C
S S S S 16. Identify the circuit.
Y1
D A
B Y2
Output
(A) 4-bit adder giving X + Y
(B) 4-bit subtractor giving X - Y
(C) 4-bit subtractor giving Y - X Y3
(D) 4-bit adder giving X + Y + S
12. The Boolean function f implemented in the figure using (A) Half adder
two input multiplexers is (B) Full adder
(C) 1-bit magnitude comparator
D 0 1 0 (D) Parity generator
f
17. In order to implement n variable function (without any
C 1 B 1 extra hardware) the minimum order of MUX is
S0 S0
(A) 2n × 1 (B) 2n × 1
(C) (2n - 1) × 1 (D) (2n - 1) × 1
A
18. A full adder circuit can be changed to full subtractor by
(A) AC + AD + DC + ABD + ABC adding a
(B) A + AC + AD + DC (A) NOR gate (B) NAND gate
B + AC + AD + DC
(C) (C) Inverter (D) AND gate
(D) AC + AD + A + B 19. The half adder when implemented in terms of NAND
13. The carry generate and carry propagate function of the logic is expressed as
look ahead carry adder is (A) A ⊕ B (B) A⋅ AB ⋅ B ⋅ AB
(A) CG = A + B, CP = A ⊕ B
(B) CG = A ⊕ B, CP = A + B (C) A ⋅ AB ⋅ B ⋅ AB (D) A ⋅ ABB⋅ AB
(C) CG = AB, CP = A ⊕ B
20. For a DeMUX to act as a decoder, what is the required
(D) CG = AB, CP = A + B
condition?
14. If we have a comparator and if E represents (A) Input should be left unconnected and select lines
the condition for equality i.e., (An ⊕ Bn), if An behave as a input to decoder
and Bn are to be compared then the expression (B) Input should be always 0 and select line behave as
A3 B3 + E3 A2 B2 + E3 E2 A1 B1 + E3 E2 E1 A. B. r e p r e s e n t s inputs to decoder
which of the condition for a 4-bit number? (C) Both are same
(A) A > B (B) B>A (D)  Input should become enable and select lines
(C) A = B (D) None of these behave as inputs to decoder
15. When full adder is used to function as a 1-bit incremen- 21. For a full subtractor, which of the combination will give
tor, which of the circuit configurations must be used? the difference?
(A) a 0 (B)
a 0
( A ⊕ B)( A ⊕ B)bi ⋅ bi ( A ⊕ B)bi
(A)

F A F A B ⋅ AB ⋅ bi ( A ⊕ B)
0
(B)
0

A + B + bi + A ⊕ B
(C)
c s c s (D) None of these
 Chapter 3  •  Combinational Circuits  |  1.53

Previous Years’ Questions

1. A 4-bit carry look ahead adder, which adds two 4-bit 16 value of the number. Which one of the following
numbers, is designed using AND, OR, NOT, NAND, functions is ­correct?[2006]
NOR gates only. Assuming that all the inputs are (A) g0 (h3h2h1h0) = Σ(1, 2, 3, 6, 10, 13, 14, 15)
available in both complemented and uncomplemented (B) g1 (h3h2h1h0) = Σ(4, 9, 10, 11, 12, 13, 14, 15)
forms and the delay of each gate is one time unit, what (C) g2 (h3h2h1h0) = Σ(2, 4, 5, 6, 7, 12, 13, 15)
is the overall propagation delay of the adder? Assume (D) g3 (h3h2h1h0) = Σ(0, 1, 6, 7, 10, 11, 12, 13)
that the carry network has been implemented using
6. How many 3-to-8 line decoders with an enable input
two-level AND–OR logic. [2004]
are needed to construct a 6-to-64 line decoder without
(A) 4 time units (B) 6 time units
using any other logic gates? [2007]
(C) 10 time units (D) 12 time units
(A) 7 (B) 8
(C) 9 (D) 10
2. x
0 MUX 7. Suppose only one multiplexer and one inverter are
1 allowed to be used to implement any Boolean function
y of n variables. What is the minimum size of the multi-
z 0 MUX plexer needed? [2007]
f
1 (A) 2n line to 1 line (B) 2n+1 line to 1 line
x
(C) 2n–1 line to 1 line (D) 2n–2 line to 1 line
y
8. In a look-ahead carry generator, the carry generate
Consider the circuit above. Which one of the follow- function Gi and the carry propagate function Pi for
ing options correctly represents f (x, y, z)? [2006] inputs Ai and Bi are given by:
(A) xz + xy + yz (B) xz + xy + yz Pi = Ai ⊕ Bi and Gi = AiB­i
(C) xz + xy + yz (D) xz + xy + yz The expressions for the sum bit Si and the carry bit
Ci+1 of the look-ahead carry adder are given by:
3. Given two 3-bit numbers a2a1a0 and b2b1b0 and c, the
carry in, the function that represents the carry generate Si = Pi ⊕ Ci and Ci+1 = Gi + PiCi, where C0 is the input
function when these two numbers are added is [2006] carry.
(A) a2b2 + a2a1b1 + a2a1a0b0 + a2a0b1b0 + a1b2b1 + a1a0b2b0   Consider a two-level logic implementation of the
+ a0b2b1b0 look-ahead carry generator. Assume that all Pi and
(B) a2b2 + a2b1b0 + a2a1b1b0 + a1a0b2b1 + a1a0b2 + a1a0b2b0 Gi are available for the carry generator circuit and
+ a2a0b1b0 that the AND and OR gates can have any number
of inputs. The number of AND gates and OR gates
(C) a2 + b2 + (a2 ⊕ b2) (a1 + b1 + (a1 ⊕ b1)(a0 + b0))
needed to implement the look-ahead carry generator
(D) a2 b2 + a2 a1b1 + a2 a1a0 b0 + a2 a0 b1b0 for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs
are respectively: [2007]
+ a1 b2 b1 + a1a0 b2 b0 + a0 b2 b1b0 (A) 6, 3 (B) 10, 4
(C) 6, 4 (D) 10, 5
4. We consider the addition of two 2’s complement num-
9. The Boolean expression for the output f of the multi-
bers bn-1bn-2 … b0 and an-1an-2 … a0. A binary adder
plexer shown below is
for adding unsigned binary numbers is used to add
the two numbers. The sum is denoted by cn-1cn-2 … c0
R 0
and the carry-out by cout. Which one of the following R 1
options correctly identifies the overflow condition? R 2 f
 [2006] R 3
S1 S0
(A) cout ( an −1 ⊕ bn −1 )
an −1 bn −1 cn −1 + an −1 bn −1 cn −1
(B)
cout ⊕ cn-1
(C) P Q
an-1 ⊕ bn-1 ⊕ cn-1
(D) P⊕Q⊕R
(A)
5. Consider numbers represented in 4-bit gray code. Let P⊕Q⊕R
(B)
h3h2h1h0 be the gray code representation of a number P+Q+R
(C)
n and let g3g2g1g0 be the gray code of (n + 1) modulo P+Q+R
(D)
1.54 | Unit 1  •  Digital Logic

10. The amount of ROM needed to implement a 4-bit if (x is 1) y = a;

multiplier is [2012] else y = b;
(A) 64 bits }
(B) 128 bits
Which one of the following digital logic blocks is the
(C) 1K bits
most suitable for implementing this function?
(D) 2K bits
(A) Full adder (B) Priority encoder
11. In the following truth table, V = 1 if and only if the input (C) Multiplexer (D) Flip–flop
is valid.
14. Let ⊕ denote the Exclusive OR (X-OR) operation.

Let ‘1’ and ‘0’ denote the binary constants. Consider

Inputs Outputs
the following Boolean expression for F over two vari-
D0 D1 D2 D3 X0 X1 V ables P and Q:
0 0 0 0 x x 0 F(P, Q) = ((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q)
1 0 0 0 0 0 1 ⊕ (Q ⊕ 0)) [2014]
x 1 0 0 0 1 1
The equivalent expression for F is

x x 1 0 1 0 1 P + Q
(A) (B) P + Q
x x x 1 1 1 1 P ⊕ Q
(C) (D) P ⊕ Q

15. A half adder is implemented with XOR and AND

What function does the truth table represent? [2013] gates. A full adder is implemented with two half adders
(A) Priority encoder and one OR gate. The propagation delay of an XOR
(B) Decoder gate is twice that of an AND/OR gate. The propaga-
(C) Multiplexer tion delay of an AND/OR gate is 1.2 microseconds.
A 4-bit ripple-carry binary adder is implemented by
(D) Demultiplexer using four full adders. The total propagation time of
12. Consider the 4-to-1 multiplexer with two select lines this 4-bit binary adder in microseconds is _____
S1 and S0 given below. [2015]

16. Consider the two cascaded 2-to-1 multiplexers as

0 0
shown in the figure.

1 1 4 to 1
F
Multiplexer
R 2
R 3
S1 S0
minimal sum of products form of the output x is
P Q The minimal sum of products form of the output X is
[2016]
The minimal sum-of-products form of the Boolean
expression for the output F of the multiplexer is (A) P Q + PQR (B)  P Q + QR
 [2014] (C) PQ + P Q R (D)  P Q + PQR
(A) PQ + QR + PQR 17. When two 8-bit numbers A7… A0 and B7… B0 in 2’s
(B)
P Q + PQR + PQR + PQR complement representation (with A0 and B0 as the
least significant bits) are added using a ripple-carry
PQR + PQR + QR + PQR
(C)
adder, the sum bits obtained are S7…S0 and the carry
(D)
PQR PQR + PQR + QR + PQR bits are C7…C0. An overflow is said to have occurred
if[2017]
13. Consider the following combinational function block

(A) the carry bit C7 is 1
involving four Boolean variables x, y, a, b, where x, a,
(B) all the carry bits (C7,…,C0) are 1
b are inputs and y is the output. [2014]
f(x, y, a, b) ( A7 ⋅ B7 ⋅ S7 + A7 ⋅ B7 ⋅ S7 ) is 1
(C)
{ ( A0 ⋅ B0 ⋅ S0 + A0 ⋅ B0 ⋅ S0 ) is 1
(D)
 Chapter 3  •  Combinational Circuits  |  1.55

Answer Keys
Exercises
Practice Problems 1
1. D 2. B 3. B 4. D 5. D 6. A 7. C 8. B 9. D 10. A
11. A 12. B 13. B 14. C 15. C 16. D 17. D 18. B 19. C 20. A
21. D

Practice Problems 2
1. C 2. B 3. A 4. D 5. C 6. C 7. C 8. B 9. B 10. C
11. B 12. C 13. C 14. A 15. C 16. C 17. B 18. C 19. C 20. D
21. A

Previous Years’ Questions

1. B 2. A 3. A 4. B 5. C 6. C 7. C 8. B 9. B 10. D
11. A 12. A 13. C 14. D 15. 19.2 16. D 17. C