Digital Electronic Circuits/19ET3DCDEC

Module 2

Analysis and Design of Combinational Logic

Combinational circuits are generally built using the basic digital functional blocks of AND,
OR and NOT and their combinations.

Combinational Logic Design

 In combinational circuit, the outputs depend strictly on the present inputs.

 Combinational logic design begins with a verbal description of the problem which is
then written in the form of a truth table.
 Depending on the number of variables involved, the function as represented in the
truth table is minimised either by using K-maps or by employing algorithmic
procedures like Quine Mc Cluskey technique to obtain the output function in SOP or
POS form.
 These simplified switching expressions are then implemented as required to arrive at
the final schematic.

1. Design a combinational circuit to find the 9’s complement of a BCD numbers.

Solution: Construct the truth table with the description given in the problem. The 9’s
complement of 1 is 8, 2 is 7 and so on. Let ABCD be the BCD number and let WXYZ
be its 9’s complement.

Truth table for BCD to its 9’s complement conversion

1
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

The output minterm expressions are:

W=∑(0,1)+ ∑d(10,11,12,13,14,15)
X=∑(2,3,4,5)+ ∑d(10,11,12,13,14,15)
Y=∑(2,3,6,7)+ ∑d(10,11,12,13,14,15)
Z=∑(0,2,4,6,8)+ ∑d(10,11,12,13,14,15)

K-Maps for the outputs:

Implementation:

2
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

2. Design a combinational circuit to convert BCD to excess-3

Solution: Let ABCD, be the BCD input and WXYZ be the excess-3 output. The truth
table is as shown:

Truth table for BCD to excess-3 converter

The output minterm expressions are:

W=∑(5,6,7,8,9)+ ∑d(10,11,12,13,14,15)
X=∑(1,2,3,4,9)+ ∑d(10,11,12,13,14,15)
Y=∑(0,3,4,7,8)+ ∑d(10,11,12,13,14,15)
Z=∑(0,2,4,6,8)+ ∑d(10,11,12,13,14,15)

3
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

K-Maps for the outputs:

Implementation:

4
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Decoders

A decoder is a device which when activated selects one of its possible 2n outputs based on its
‘n’ bit digit. There are several types of decoders, the most common being the n to 2n type of
decoders as shown.

General Representation of a decoder

2_4 Line Decoders

Truth table and block schematic of a 2 to 4 line decoder

 There are 2 input lines and 22 output lines.

 Y0 = ̅ ̅ , Y1 = ̅ B, Y2 = A ̅, Y3 = AB

Simplifying that all the possible minterms of a two variable expression are available at the
output of a 2 line to 4 line decoder.

IC 74139 (Dual 2_4 Decoder)

The IC 74139 is a high speed dual 2_4 decoder . This has two decoders each accepting
two binary weighted inputs (a, b) and providing for mutually exclusive active low outputs
(Y0 - Y3). Each decoder has an active low enable (E), when E =1, every output is forced
high. The enable can be used as the data input for a 1_4 demux application.

5
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Dual 2_4 line decoder

The wedges at the output indicate a bubbled output or active low outputs. This means that
generally the outputs are high and go low when activated by an appropriate input code. The
wedge at the input indicates that the section of the device is activated by a low on that input.
These operations are captured in the functional table of 74139 as shown.

ðð

Function table of 74139

When G’ line is high and the outputs are high irrespective of inputs and that section of the
device is said to be disabled.The logic diagram for one of the 2-4decoderrs in the IC is shown
in fig

6
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Logic diagram of one section of 74139

3 to 8 line Decoders

 3 to 8 line decoders are available in IC form as 74138.

 The function symbol is as shown
 The device functions as a decoder only when G1=1 & ̅̅̅̅A=̅̅̅̅B =0 and under other
conditions all the outputs will be high.

Function symbol of 74138

Function table of 74138

7
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

1. Implement the following function using 74138

f (a, b, c) = ∑ (2 ,6, 7)

2. Implement the multiple function f1(a, b, c, d) = ∑(0,4,8,10,14,15) and

f2(a, b, c, d) = ∑(3,7,9,13) using two 74138 (3-8) decoders.
Solution: The implementation is as shown

8
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Encoders

Encoders convert one binary code to another. Generally in an encoder, the number of input
lines are much more than the number of output lines. Typically, if there are 2n input lines,
there could be n output lines as shown. Some examples of encoders are 4_2, 8_3, decimal to
BCD encoders & so on.

A general encoder

The Truth table of 8 to 3 line encoder is as shown

Truth table of 8 to 3 line encoder

The Boolean expression for the outputs can be written as:

y2=x4+x5+x6+x7

y1=x2+x3+x6+x7

y0=x1+x3+x5+x7

9
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Block diagram

Implementation

8 to 3 Line Priority Encoder

 In 8 to 3 line encoder, when more than one inputs are at logic 1 there may be an error
in the output code. Ex: If x3=x4=111 then y2y1y0=111, where as this output should
have resulted for only x7.
 Also when the output is 000 all the inputs are at logic 0 as well as when xo=1. 8 to 3
encoder doesn’t distinguish between these two conditions of inputs.
 These problems can be overcome by the priority encoder with a validity indicator.

10
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Truth table of 8 to 3 line priority encoder

 Here, the higher order bits have higher priority.

 Ex: If x3 is at logic1, then irrespective of logic values of x0,x1 and x2 the output code
will be 011.
 The valid output being 1 indicates that input code is valid. The outputs at row 0 and
row 1 are now distinguished by the logic level of the ‘valid’ output.

Decimal to BCD Encoder

A decimal to BCD encoder produces the 8421 output code depending on which of its nine
input lines are active. The 74147 is a decimal to BCD encoder with both inputs and outputs
active low.

Logic Symbol

11
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Truth table

When the input goes low, the outputs C, B and A go low. Such devices are generally
used to interface a numeric keypad to a microcontroller or a computer.

1. Design a priority encoder for a system with three inputs, with the middle bit with
highest priority encoding to 10, the MSB with the next priority encoding to11, while
the LSB with the least priority encoding to 01.
Solution: The truth table is as shown

Truth table

K-Maps for Y and Z:

12
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Implementation:

13
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Binary Half Adder

A binary half adder adds two binary bits and generates a sum bit and a carry bit.The block
diagram and the truth table are as shown, where a and b are the inputs and s is the sum output
and c is the carry output.

s = ab

c = ab
Implementation:

Binary Full Adder

 A half adder adds two binary bits and generates the sum bit and the carry bit.
 In order to cascade several one-bit adder to configure multiple bit adders there must
be a provision to add the carry from the previous stage.
 Such an adder is called a full adder. The block diagram and truth table is as shown:

14
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Truth table

K-Maps for the two outputs in order to obtain a minimal boolean expression for sum and
carry outputs.

s = a  b  ci
ci+1 =ab+bci+aci

Implementation:

Implementation using two half adders:

15
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Binary Half Subtractor

A binary half Subtractor subtracts one binary bit from another and generates the difference
and the borrow outputs. The block diagram and the truth table of a half Subtractor is as
shown where bit b is to be subtracted from bit a, d is the difference and b is the borrow.

d = a b

b= a’b

Implementation:

Full Subtractor

16
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Parallel Adder and Subtractor

An exclusive OR-gate can be used to perform parallel addition as well as subtraction using
the configuration shown.

Parallel adder and subtractor

 The carry input c0 to the bit-0 stage acts as a control input

 When c0 is set to 0, addition is performed because b0,b1,b2 and b3 appear
uncomplemented at the inputs of the full adder.
 When co is set to 1, subtraction is performed because b0,b1,b2 and b3 appear
complemented the inputs of the full adder.
 The outputs of the arrangement represent the sum if co=0 and difference if co=1

17
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Look Ahead Carry Adder

 In ripple adders and subtractors, the sum and carryout of any stage depends on the
carry output of the previous stage.
 The carryout of the previous stage depends on the carryout of the stage prior and so
on.
 If we could ensure that the sum and carry output of any stage is not dependent on the
results of any previous stages, then the ripple effect is eliminated and speed of
addition remarkably increases.

Consider the carry equation,

Ci+1=aibi+bici+aici
Ci+1=aibi+ci(aibi) ------------- 1

The term aibi relates to the carry formed at the ith stage and is referred to as the carry
generate function gi.

ie., gi. = aibi -----------------------------------------------2

The term ai.bi relates to the carry generated at the previous stage and thus aibi is
reffered to as carry propagate function

pi=aibi -----------------------------------------------3

Both pi and gi. are the functions of only the parallel inputs ai and bi. Comparing
equations 1,2 and 3 we can write

Ci+1=gi+piCi ----------------------------------------------------4

Now, let us look at the carry generated at every stage of the 4-bit parallel
adder.Setting i= 0 in eq 4 we get

C1=g0+p0C0 ---------------------------------------------------5

Setting i=1 in eqn 4 we get,

C2=g1+p1

Substitute C1 from eq 5

C2=g1+p1(g0+p0)

C2=g1+p1g0+p1p0C0 --------------------------------------------6

18
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

According to equations 5 & 6, C1 and C2 are functions of only the parallel inputs and C0 .

Similarly,

C3=g2+p2c2

Substitute from eq 6

C3=g2+p2(g1+p1g0+p1p0C0)

C3=g2+p2g1+p2p1g0+p2p1p0C0 --------------------------------7

Similarly,

C4=g3+p3c3

C4=g3+p3(g2+p2g1+p2p1g0+p2p1p0C0)

C4=g3+p3g2+p3p2g1+p3p2p1g0+p3p2p1p0C0 ------------------8 and so on.

Equations 7 and 8 indicate that C3 and C4 are functions of only the parallel inputs and C0

The Boolean expression for C1 , C2 , C3 etc can themselves be implemented using gates and
the carry required at each stage of the parallel adder can be made available simultaneously,
thereby icreasing the speed of addition.

Four bit parallel fast look ahead adder

Adder block Implementation

19
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

The four bit look ahead carry generator can be implemented as shown:

20
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

1. Design a full adder using decoder

Solution:

Decoder implementation of full adder

Multiplexers

 Multiplexer 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 single output line.
 The selection of a particular input line is controlled by a set of selection lines.
 Normally there are 2n input lines and ‘n’ select lines whose bit combinations
determine which input is selected.
 Therefore, multiplexer is many into one and it provides the digital equivalent of an
analog selector switch.

21
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Symbol of 8 to 1 Mux

4-1 Multiplexers

Symbol and Truth table of 4_1 Mux

 As seen in row 0, when E=1, irrespective of other inputs f=0.

 When E=0, the data at the addressed or select input appears at the output.
 In row 3, the select inputs are 01 which selects dataline d1. The data on d1 appears at
the output.
 If d1=0, f=0 (row 3) and if f=1 (row 0). This functional description can be represented
in a functional table shown

Function table of 4_1 Mux

( ̅̅̅̅ ̅̅̅ ̅̅̅ ̅̅̅̅ )̅

22
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

1. Design 16:1 mux using 8:1 mux

Solution:
 Connect the select lines (s2, s1,s0) of two multiplexers in parallel
 Connect most significant select line s3 such that when s3=0 Mux 1 is enabled
& when s3 =1 Mux 2 is enabled.
 Logically OR the outputs of the two multiplexers to obtain the final output

16 to 1 Mux configured using 4 to 1 Mux

Logic Design with Multiplexers

 A multiplexer consists if a set of AND gates whose outputs are connected to single
OR gate.
 Because of this construction any Boolean function in a SOP form can be easily
realized using multiplexer.
 Each AND gate in a multiplexer represents a minterm.
 To the multiplexers, by connecting the function variables directly to the select inputs ,
a multiplexer can be made to select the AND gate that corresponds to the minterm in
the function.

23
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

 If a minterm exists in a function, we have to connect the AND gate data input to logic
1; otherwise we have to connect it to logic 0.

1. Implement the given function using multiplexer.

f (x, y, z) = ∑ (0, 2, 6, 7)
Solution:
a. Select the multiplexer. Here, Boolean expression has 3 variables thus we
require 23 = 8, 8:1 mux
b. Connect inputs corresponding to the the present minterms to logic1
c. Connect remaining inputs to logic 0
d. Connect input variables to select lines of mux.

2. Implement the given function using 4 :1 multiplexer.

f (a, b, c) = ∑ (1, 3, 5, 6)
Solution:
a. Connect the least significant variables as a select inputs of multiplexer.
Here connect C to S0 and b to S1.
b. Derive inputs for multiplexer using implementation table.

(a) Implementation Table (b) Multiplexer Implementation

24
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

The implementation is nothing but the list of the inputs of the multiplexer and under them the
list of minterms in two rows. The first row lists all those minterms where A is complemented,
and the second row lists all the minterms with A uncomplemented.The minterms given in the
function are circled and then each column is inspected separately as follows:

 If the two minterms in a column are circled, 0 is applied to the corresponding

multiplexer input
 If the two minterms in a column are circled, 1 is applied to the corresponding
multiplexer input
 If the minterm in the second row is circled and minterm in the first row is not circled,
A is applied to the corresponding multiplexer input.

 If the minterm in the second row is circled and minterm in the second row is not
circled, ̅ is applied to the corresponding multiplexer input.

3. Implement the given function f (a, b, c, d) = ∑ (0, 1, 5, 6, 7, 9,10, 15)

Using i. 8 :1 multiplexer with a, b, c as select lines
ii. 4:1 multiplexer with a, b as select lines
Solution

i.

ii.

25
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Comparators

Comparators are designed to compare the magnitude of two binary numbers and indicate
whether one is than (gt), less than (lt) or equal to the other.

One-bit Comparator

One bit comparators are compare two one-bit numbers a and b and produce three output a=b,
a>b and a<b.

The truth table of a one-bit comparator is shown

Truth table of one-bit comparator

a eq b = ̅ ̅

a gt b = ̅

a lt b = ̅

Implementation of one-bit comparator

26
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Two- Bit Comparators

A two bit magnitude comparator would accept two-2 bit numbers and generate three output.
The block diagram is as shown

Block diagram of a two bit magnitude comparator

 x=1 if a1a0 > b1b0


y =1 if a1a0 = b1b0
 z = 1 if a1a0 < b1b0

Truth table of two-bit magnitude comparator

27
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

We have, x= ∑(4,8,9,12,13,14), y=∑(0,5,10,15) and z = ∑(1,2, 3,6,7,11)

Implementation of a two bit magnitude comparator

28
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

Question Bank

1. Perform the following to design a full-subtractor: (i) Construct the truth table and
simplify the output equations. (i) Draw the resulting logic diagram (iii) Realise using
NAND gates.
2. Write two bit Magnitude Comparator, write the Karnaugh Map for each output, the
resulting equation and circuit.
3. Perform the following to design a combinational logic circuit to convert the BCD
digit to an excess-3 BCD digit. i) Construct the truth table. ii) Simplify the output
function and write the min term equation iii) Simplify the output function and write
reduced logic equation and iv) Draw the resulting logic diagram.
4. What is Gray Code? Write the procedure to convert Gray to Binary and vice versa.
Design circuit.
5. Implement 16:1 multiplexer using 4:1 multiplexer.
6. Realize a Full Adder using minimum number of 2 input NAND gates. Write Truth
Table.
7. Write a detailed note on 4-bit Carry look ahead Adder.
8. Design 1:4 DMUX using NAND gates & explain its working.
9. 10.Realize using 74153 IC : F(ABCD) = ∑(0,2,4,5,7,8,10,12,13)
10. Realize the following function using 8:1 MUX,
F (ABCD) = ∑ (1, 2, 9, 10, 14).
11. Realize the following function F (ABCD) = ∑ (0, 1, 3, 5, 7)
(a) Using single 8:1 MUX (b) Using single 4:1 MUX
12. Implement the following function using 8:1 MUX,
F(ABCD) = A’BD’+ AC’D’ + B’CD + A’C’D
13. Design 1:8 DMUX using two 1:4 DMUX.
14. Design a comparator to check if two n-bit numbers are equal. Configure these using
cascaded stages of 1-bit comparators.
15. What is Multiplexer? Give the applications of Mux.

16. Explain 3:8 Line Decoder and Implement a full Subtractor using 3:8 lines Decoder
with the decoder having high outputs and active low enable inputs.
17. Design a 4:16 decoder using two 3:8 decoder and write the truth Table.
18. Realize a 2:4 decoder using gates. Use this as a block and show how to obtain 3:8
Decoders.
19. Design a BCD to 7 Segment decoder for common Anode using 4:16 decoder, give
relevant truth table, Karnaugh Map simplification and logic diagram details.
20. What are the problems associated with the basic encoder? Explain how can these
problems be overcome by priority encoder, considering 8 input lines.
21. a. Write the condensed truth table for a 4to 2 line priority encoder with a valid output
where the highest priority is given to the highest bit position or input with highest
index and obtain the minimal sum expressions for the outputs.
b. Descibe general working principle of decoder.
22. Design a combinational circuit to find the 9’s compliment of a single digit BCD
number.Realize the circuit using suitable logic gates.
23. a. Implement the following function pairs using 74138 decoder:

29
ETCE, DSCE
Digital Electronic Circuits/19ET3DCDEC

f1(a,b,c)= ∑(0,2,4); f2(a,b,c)= ∑(1,2,4,5,7).

b.Realize 16:4 encoder using two 8:3 priority encoders.

30
ETCE, DSCE