Lecture-1 Standard representation for logic functions

Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q -M
method of function realization.

Introduction
Combinational circuits consist of Logic gates. These circuits operate with binary values. The
output of combinational circuit depends on the combination of present inputs. The following
figure shows the block diagram of combinational circuit.

This combinational circuit has ‘n’ input variables and ‘m’ outputs. Each combination of input
variables will affect the output.

Design procedure of Combinational circuits

 Find the required number of input variables and outputs from given specifications.

 Formulate the Truth table. If there are ‘n’ input variables, then there will be 2n possible
combinations. For each combination of input, find the output values.
 Find the Boolean expressions for each output. If necessary, simplify those expressions.

 Implement the above Boolean expressions corresponding to each output by using Logic
gates.

The Boolean function can be simplfy easily in SOP (sum of products) form and POS (product of
sums) form. To represent these standardized equations logically.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-1 Standard representation for logic functions
Digital Electronics

We will get four Boolean product terms by combining two variables x and y with logical AND
operation. These Boolean product terms are called as min terms or standard product terms.
The min terms are x’y’, x’y, xy’ and xy.
Similarly, we will get four Boolean sum terms by combining two variables x and y with logical
OR operation. These Boolean sum terms are called as Max terms or standard sum terms. The
Max terms are x + y, x + y’, x’ + y and x’ + y’.

The following table shows the representation of min terms and MAX terms for 2 variables.

x y Min terms Max terms

0 0 m 0=x’y’ M0=x + y

0 1 m 1=x’y M1=x + y’

1 0 m 2=xy’ M2=x’ + y

1 1 m 3=xy M3=x’ + y’

If the binary variable is ‘0’, then it is represented as complement of variable in min term and as
the variable itself in Max term. Similarly, if the binary variable is ‘1’, then it is represented as
complement of variable in Max term and as the variable itself in min term.

From the above table, we can easily notice that min terms and Max terms are complement of
each other. If there are ‘n’ Boolean variables, then there will be 2 n min terms and 2n Max terms.

Canonical SoP and PoS forms

A truth table consists of a set of inputs and output. If there are ‘n’ input variables, then there
will be 2n possible combinations with zeros and ones. So the value of each output variable
depends on the combination of input variables. So, each output variable will have ‘1’ for some
combination of input variables and ‘0’ for some other combination of input variables.
Therefore, we can express each output variable in following two ways.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-1 Standard representation for logic functions
Digital Electronics

 Canonical SoP form

 Canonical PoS form

Canonical SoP form

Canonical SoP form means Canonical Sum of Products form. In this form, each product term
contains all literals. So, these product terms are nothing but the min terms. Hence, canonical
SoP form is also called as sum of min terms form.
First, identify the min terms for which, the output variable is one and then do the logical OR of
those min terms in order to get the Boolean expression function corresponding to that output
variable. This Boolean function will be in the form of sum of min terms.
Follow the same procedure for other output variables also, if there is more than one output
variable.

Example

Consider the following truth table.

Inputs Output

p q r f

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-1 Standard representation for logic functions
Digital Electronics

1 0 1 1

1 1 0 1

1 1 1 1

Here, the output f is ‘1’ for four combinations of inputs. The corresponding min terms are p’qr,
pq’r, pqr’, pqr. By doing logical OR of these four min terms, we will get the Boolean function
of output f.
Therefore, the Boolean function of output is, f = p’qr + pq’r + pqr’ + pqr. This is the canonical
SoP form of output, f. We can also represent this function in following two notations.

f=m3+m5+m6+m7f=m3+m5+m6+m7
f=∑m(3,5,6,7) f=∑m(3,5,6,7)
In one equation, we represented the function as sum of respective min terms. In other equation,
we used the symbol for summation of those min terms.

Canonical PoS form

Canonical PoS form means Canonical Product of Sums form. In this form, each sum term
contains all literals. So, these sum terms are nothing but the Max terms. Hence, canonical PoS
form is also called as product of Max terms form.
First, identify the Max terms for which, the output variable is zero and then do the logical AND
of those Max terms in order to get the Boolean expression function corresponding to that output
variable. This Boolean function will be in the form of product of Max terms.
Follow the same procedure for other output variables also, if there is more than one output
variable.
Example

Consider the same truth table of previous example. Here, the output f is ‘0’ for four
combinations of inputs. The corresponding Max terms are p + q + r, p + q + r’, p + q’ + r, p’ + q
+ r. By doing logical AND of these four Max terms, we will get the Boolean function of
output f.

Therefore, the Boolean function of output is, f = p+q+r.p+q+r′.p+q′+r.p′+q+r

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-1 Standard representation for logic functions
Digital Electronics

This is the canonical PoS form of output, f. We can also represent this function in following
two notations.

f=M0.M1.M2.M4f=M0.M1.M2.M4

f=∏M(0,1,2,4)f=∏M(0,1,2,4)
In one equation, we represented the function as product of respective Max terms. In other
equation, we used the symbol for multiplication of those Max terms.

The Boolean function, f = p+q+r.p+q+r′.p+q′+r.p′+q+r is the dual of the Boolean function, f =

p’qr + pq’r + pqr’ + pqr.
Therefore, both canonical SoP and canonical PoS forms are Dual to each other. Functionally,
these two forms are same. Based on the requirement, we can use one of these two forms.

Standard SoP and PoS forms

We discussed two canonical forms of representing the Boolean outputs. Similarly, there are two
standard forms of representing the Boolean outputs. These are the simplified version of
canonical forms.

 Standard SoP form

 Standard PoS form
The main advantage of standard forms is that the number of inputs applied to logic gates can be
minimized. Sometimes, there will be reduction in the total number of logic gates required.

Standard SoP form

Standard SoP form means Standard Sum of Products form. In this form, each product term
need not contain all literals. So, the product terms may or may not be the min terms. Therefore,
the Standard SoP form is the simplified form of canonical SoP form.
We will get Standard SoP form of output variable in two steps.

 Get the canonical SoP form of output variable

 Simplify the above Boolean function, which is in canonical SoP form.
Follow the same procedure for other output variables also, if there is more than one output
variable. Sometimes, it may not possible to simplify the canonical SoP form. In that case, both
canonical and standard SoP forms are same.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-1 Standard representation for logic functions
Digital Electronics

Example

Standard PoS form

Standard PoS form means Standard Product of Sums form. In this form, each sum term need
not contain all literals. So, the sum terms may or may not be the Max terms. Therefore, the
Standard PoS form is the simplified form of canonical PoS form.
We will get Standard PoS form of output variable in two steps.

 Get the canonical PoS form of output variable

 Simplify the above Boolean function, which is in canonical PoS form.
Follow the same procedure for other output variables also, if there is more than one output
variable. Sometimes, it may not possible to simplify the canonical PoS form. In that case, both
canonical and standard PoS forms are same.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-1 Standard representation for logic functions
Digital Electronics

Example
Convert the following Boolean function into Standard PoS form.

f = p+q+r.p+q+r′.p+q′+r.p′+q+r
The given Boolean function is in canonical PoS form. Now, we have to simplify this Boolean
function in order to get standard PoS form.

Step 1 − Use the Boolean postulate, x.x = x. That means, the Logical AND operation with any
Boolean variable ‘n’ times will be equal to the same variable. So, we can write the first term
p+q+r two more times.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-1 Standard representation for logic functions
Digital Electronics

…………………………………………….THE END…………………………………………

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-2 K-map representation Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

K-map representation
Karnaugh Map or K-map is introduced by a telecom engineer, Maurice Karnaugh at Bell labs in
1953, as a refined technique of ‘Edward Veitch’s Veitch diagram’ and it is a method to simplify
or reduce the complexities of a Boolean expression.
Karnaugh map method or K-map method is the pictorial representation of the Boolean
equations and Boolean manipulations are used to reduce the complexity in solving them. These
can be considered as a special or extended version of the ‘Truth table’.
By using Karnaugh map technique, we can reduce the Boolean expression containing any
number of variables, such as 2-variable Boolean expression, 3-variable Boolean expression, 4-
variable Boolean expression and even 7-variable Boolean expressions, which are complex to
solve by using regular Boolean theorems and laws.

K-Maps for 2 to 5 Variables

K-Map method is most suitable for minimizing Boolean functions of 2 variables to 5 variables.
Now, let us discuss about the K-Maps for 2 to 5 variables one by one.

2 Variable K-Map

The number of cells in 2 variable K-map is four, since the number of variables is two. The
following figure shows 2 variable K-Map.

3 Variable K-Map

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-2 K-map representation Digital Electronics

The number of cells in 3 variable K-map is eight, since the number of variables is three. The
following figure shows 3 variable K-Map.

4 Variable K-Map

The number of cells in 4 variable K-map is sixteen, since the number of variables is four. The
following figure shows 4 variable K-Map.

5 Variable K-Map

The number of cells in 5 variable K-map is thirty-two, since the number of variables is 5. The
following figure shows 5 variable K-Map.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-2 K-map representation Digital Electronics

Minimization of Boolean Functions using K-Maps

Minimization with Karnaugh Maps and advantages of K-map

 K-maps are used to convert the truth table of a Boolean equation into minimized SOP
form.
 Easy and simple basic rules for the simplification.
 The K-map method is faster and more efficient than other simplification techniques of
Boolean algebra.
 All rows in the K-map are represented by using a square shaped cells, in which each
square in that will represent a minterm.
 It is easy to convert a truth table to k-map and k-map to Sum of Products form equation.

Grouping of K-map variables

 There are some rules to follow while we are grouping the variables in K-maps. They are
 The square that contains ‘1’ should be taken in simplifying, at least once.
 The square that contains ‘1’ can be considered as many times as the grouping is possible
with it.
 Group shouldn’t include any zeros (0).
 A group should be the as large as possible.
 Groups can be horizontal or vertical. Grouping of variables in diagonal manner is not
allowed.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-2 K-map representation Digital Electronics

 If the square containing ‘1’ has no possibility to be placed in a group, then it should be
added to the final expression.
 Groups can overlap.
 The number of squares in a group must be equal to powers of 2, such as 1, 2, 4, 8 etc.
 Groups can wrap around. As the K-map is considered as spherical or folded, the squares
at the corners (which are at the end of the column or row) should be considered as they
adjacent squares.
 The grouping of K-map variables can be done in many ways, so the obtained simplified
equation need not to be unique always.
 The Boolean equation must be in must be in canonical form, in order to draw a K-map.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-2 K-map representation Digital Electronics

Example

Let us simplify the following Boolean function, f W,X,Y,Z= WX’Y’ + WY + W’YZ’ using K-
map.
The given Boolean function is in sum of products form. It is having 4 variables W, X, Y & Z.
So, we require 4 variable K-map. The 4 variable K-map with ones corresponding to the given
product terms is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-2 K-map representation Digital Electronics

Here, 1s are placed in the following cells of K-map.

 The cells, which are common to the intersection of Row 4 and columns 1 & 2 are
corresponding to the product term, WX’Y’.
 The cells, which are common to the intersection of Rows 3 & 4 and columns 3 & 4 are
corresponding to the product term, WY.
 The cells, which are common to the intersection of Rows 1 & 2 and column 4 are
corresponding to the product term, W’YZ’.

There are no possibilities of grouping either 16 adjacent ones or 8 adjacent ones. There are three
possibilities of grouping 4 adjacent ones. After these three groupings, there is no single one left
as ungrouped. So, we no need to check for grouping of 2 adjacent ones. The 4 variable K-
map with these three groupings is shown in the following figure.

Here, we got three prime implicants WX’, WY & YZ’. All these prime implicants
are essential because of following reasons.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-2 K-map representation Digital Electronics

 Two ones (m8 & m9) of fourth row grouping are not covered by any other groupings.
Only fourth row grouping covers those two ones.
 Single one (m15) of square shape grouping is not covered by any other groupings. Only
the square shape grouping covers that one.
 Two ones (m2 & m6) of fourth column grouping are not covered by any other groupings.
Only fourth column grouping covers those two ones.
Therefore, the simplified Boolean function is
f = WX’ + WY + YZ’

Example

Let us simplify the following Boolean

function, f(X,Y,Z)=∏M(0,1,2,4)f(X,Y,Z)=∏M(0,1,2,4) using K-map.
The given Boolean function is in product of Max terms form. It is having 3 variables X, Y & Z.
So, we require 3 variable K-map. The given Max terms are M0, M1, M2 & M4. The 3 variable
K-map with zeroes corresponding to the given Max terms is shown in the following figure.

There are no possibilities of grouping either 8 adjacent zeroes or 4 adjacent zeroes. There are
three possibilities of grouping 2 adjacent zeroes. After these three groupings, there is no single
zero left as ungrouped. The 3 variable K-map with these three groupings is shown in the
following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-2 K-map representation Digital Electronics

Here, we got three prime implicants X + Y, Y + Z & Z + X. All these prime implicants
are essential because one zero in each grouping is not covered by any other groupings except
with their individual groupings.
Therefore, the simplified Boolean function is
f = X+YX+Y.Y+ZY+Z.Z+XZ+X
In this way, we can easily simplify the Boolean functions up to 5 variables using K-map
method. For more than 5 variables, it is difficult to simplify the functions using K-Maps.
Because, the number of cells in K-map gets doubled by including a new variable.
Due to this checking and grouping of adjacent ones minterms or adjacent zeros Maxterms will
be complicated. We will discuss Tabular method in next chapter to overcome the difficulties
of K-map method.

…………………………………………….THE END…………………………………………

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-3 K-map representation Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

K-map representation

K-Maps 5 Variables

5 & 6 Variable Karnaugh Maps

K-Map is used for minimization or simplification of a Boolean expression. 2-4 variable K-maps
are easy to handle. However, the real challenge is 5 and 6 variable K-maps. Visualization of 5 &
6 variable K-map is a bit difficult. When the number of variables increases, the number of the
square (cells) increases. And drawing the K-map becomes a bit complicated because of drawing
the adjacent cells.

5 Variables K-Map

5 variables have 32 min terms,which mean 5 variable karnaugh map has 32 squares (cells).

A 5-variable K-map is made using two 4-variable K-maps. Consider 5 variables A,B,C,D,E. their
5 variable K-map is given below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-3 K-map representation Digital Electronics

These both 4-variable Karnaugh map together represents a 5-variable K-map for variable
A,B,C,D,E. Notice variable A over the top of each 4-variable K-map. For A=0, the left K-map is
selected and right map for A = 1.

Each corresponding squares (cells) of these 2 4-variable K-maps are adjacent. Visualize these
both K-maps on top of each other. m0 is adjacent to m16, so is m1 to m17 so on until the last
square.

The rule (method) of grouping is same for each of the 4-variable k-maps. However, you also
need to check the corresponding cells in both K-maps as well. A few example of grouping is
given below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-3 K-map representation Digital Electronics

This is the 5-variable k-map for the function given above. There are four groups made in this K-
map. Each group has a different color to differentiate between them.

The red color group is a group of 4 min terms made between both 4-variable k-maps because
they are adjacent cells and it overlaps the green group.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-3 K-map representation Digital Electronics

The yellow group is also a group of 4 min terms made between adjacent cells of the 4-variable k-
maps.

The green group is a group of 4 min terms made in the left 4-variable k-map. The blue group is
of 2 min-terms made in the right 4-variable k-map because there are no common adjacent cells in
the other k-map.

Green color group of 4 min term will produce the term A̅C̅E̅ . The individual 4-variable K-map
will produce C̅E̅ as they are not changing in the group but variable A should also be taken into
account because this individual 4-variable k-map is being represented by A̅.

The red color group will produce C̅D̅E̅ . This group is made between both K-maps which means
variable A changes and in individual K -map, B changes so these both variables will be
eliminated from the term. Only C̅D̅E̅ remains unchanged in this group.

The yellow group will produce B̅CE because these literals are not changing in this group .

Blue group of 2 min terms will produce the term ABDE as they remain unchanged in this group.

The simplified expression will be the sum of these 4 terms, which is given below:

F = A̅C̅E̅ + C̅D̅E̅ + B̅CE + ABDE

In previous chapter, we discussed K-map method, which is a convenient method for minimizing
Boolean functions up to 5 variables. But, it is difficult to simplify the Boolean functions having
more than 5 variables by using this method.

Solving SOP function –

For clear understanding, let us solve the example of SOP function minimization of 5 Variable
K-Map using the following expression :

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-3 K-map representation Digital Electronics

 Subcube 1: The one marked in red comprises of cells ( 0, 4, 8, 12, 16, 20, 24, 28)
 Subcube 2: The one marked in blue comprises of cells (7, 23)
 Subcube 3: The one marked in pink comprises of cells ( 0, 2, 8, 10, 16, 18, 24, 26)
 Subcube 4: The one marked in yellow comprises of cells (24, 25, 26, 27)
Now, while writing the minimal expression of each of the subcubes we will search for the literal
that is common to all the cells present in that subcube.

Finally the minimal expression of the given boolean Function can be expressed as follows :

Solving POS function –

Now, let us solve the example of POS function minimization of 5 Variable K-Map using the
following expression :

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-3 K-map representation Digital Electronics

In the above K-Map we have 4 subcubes:

 Subcube 1: The one marked in red comprises of cells ( 0, 4, 8, 12, 16, 20, 24,
28)
 Subcube 2: The one marked in blue comprises of cells (7, 23)
 Subcube 3: The one marked in pink comprises of cells ( 0, 2, 8, 10, 16, 18,
24, 26)
 Subcube 4: The one marked in yellow comprises of cells (24, 25, 26, 27)

Now, while writing the minimal expression of each of the subcubes we will search for the literal
that is common to all the cells present in that subcube.

Finally the minimal expression of the given boolean Function can be expressed as follows :

K-map with “Don’t care” conditions

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-3 K-map representation Digital Electronics

The "Don't care" condition says that we can use the blank cells of a K-map to make a group of
the variables. To make a group of cells, we can use the "don't care" cells as either 0 or 1, and if
required, we can also ignore that cell. We mainly use the "don't care" cell to make a large group
of cells.

The cross (×) symbol is used to represent the "don't care" cell in K-map. This cross symbol
represents an invalid combination. The "don't care" in excess-3 code are 0000, 0001, 0010, 1101,
1110, and 1111 because they are invalid combinations. Apart from this, the 4-bit BCD to Excess-
3 code, the "don't care" are 1010, 1011, 1100, 1101, 1110, and 1111.
We can change the standard SOP function into a POS expression by making the "don't care"
terms the same as they are. The missing minterms of the POS form are written as maxterms of
the POS form. In the same way, we can change the standard POS function into an SOP
expression by making the "don't care" terms the same as they are. The missing maxterms of the
SOP form are written as minterm of the SOP form.

Example 1: Minimize f = m(1,5,6,12,13,14) + d(4) in SOP minimal form

Solution:

The k-map of the given function in the SOP form is as follows:

So, the minimized SOP form of the function is:

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-3 K-map representation Digital Electronics

f = BC' + BD' + A'C'D

Example 2: Minimize F(A,B,C,D) = m(0,1,2,3,4,5) + d(10,11,12,13,14,15) in SOP minimal

form

Solution:

The POS form of the given function is:

F(A,B,C,D) = M(6,7,8,9) + d(10,11,12,13,14,15)

The POS K-map for the given expression is:

So, the minimized POS form of the function is:

F = A'(B' + C')

Example-3:
Minimize the following function in SOP minimal form using K-Maps: F(A, B, C, D) = m(1,
2, 6, 7, 8, 13, 14, 15) + d(3, 5, 12)

Explanation:

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-3 K-map representation Digital Electronics

The SOP K-map for the given expression is:

Therefore,

f = AC'D' + A'D + A'C + AB

Significance of "Don't Care" Conditions:

Don't Care conditions has the following significance with respect to the digital circuit design:

Simplification:

These conditions denote the set of inputs that never occurs for given digital circuits. Therefore,
to simplify the boolean output expressions, the 'don't care' are used.

Reduced Power Consumption:

The switching of the state is reduced when we group the terms long with "don't care". This
reduces the required memory space resulting in lower power consumption.

Lesser number of gates:

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-3 K-map representation Digital Electronics

For reducing the number of gates that are used to implement the given expression, simplification
places an important role. So, the 'don't care' makes the logic design more economical.

Prevention of Hazards:

In the digital system, the 'don't care' place an important role in hazards prevention.

States in Code Converters:

These also play an important role in code conversion. For example- In the design of a 4-bit BCD-
to-XS-3 code converter, the input combinations 1010, 1011, 1100, 1101, 1110, and 1111 are
don't cares.

…………………………………………….THE END…………………………………………

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 10

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

Multiplexer is a combinational circuit that has maximum of 2n data inputs, ‘n’ selection lines
and single output line. One of these data inputs will be connected to the output based on the
values of selection lines.
Since there are ‘n’ selection lines, there will be 2n possible combinations of zeros and ones. So,
each combination will select only one data input. Multiplexer is also called as Mux

4x1 Multiplexer
4x1 Multiplexer has four data inputs I3, I2, I1 & I0, two selection lines s1 & s0 and one output Y.
The block diagram of 4x1 Multiplexer is shown in the following figure.

One of these 4 inputs will be connected to the output based on the combination of inputs present
at these two selection lines. Truth table of 4x1 Multiplexer is shown below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

Selection Lines Output

S1 S0 Y

0 0 I0

0 1 I1

1 0 I2

1 1 I3

From Truth table, we can directly write the Boolean function for output, Y as
Y=S1′S0′I0+S1′S0I1+S1S0′I2+S1S0I3Y=S1′S0′I0+S1′S0I1+S1S0′I2+S1S0I3
We can implement this Boolean function using Inverters, AND gates & OR gate. The circuit
diagram of 4x1 multiplexer is shown in the following figure.

We can easily understand the operation of the above circuit. Similarly, you can implement 8x1
Multiplexer and 16x1 multiplexer by following the same procedure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

Implementation of Higher-order Multiplexers.

Now, let us implement the following two higher-order Multiplexers using lower-order
Multiplexers.

 8x1 Multiplexer
 16x1 Multiplexer

8x1 Multiplexer

In this section, let us implement 8x1 Multiplexer using 4x1 Multiplexers and 2x1 Multiplexer.
We know that 4x1 Multiplexer has 4 data inputs, 2 selection lines and one output. Whereas, 8x1
Multiplexer has 8 data inputs, 3 selection lines and one output.
So, we require two 4x1 Multiplexers in first stage in order to get the 8 data inputs. Since, each
4x1 Multiplexer produces one output, we require a 2x1 Multiplexer in second stage by
considering the outputs of first stage as inputs and to produce the final output.
Let the 8x1 Multiplexer has eight data inputs I7 to I0, three selection lines s2, s1 & s0 and one
output Y. The Truth table of 8x1 Multiplexer is shown below.

Selection Inputs Output

S2 S1 S0 Y

0 0 0 I0

0 0 1 I1

0 1 0 I2

0 1 1 I3

1 0 0 I4

1 0 1 I5

1 1 0 I6

1 1 1 I7

We can implement 8x1 Multiplexer using lower order Multiplexers easily by considering the
above Truth table. The block diagram of 8x1 Multiplexer is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

The same selection lines, s1 & s0 are applied to both 4x1 Multiplexers. The data inputs of upper
4x1 Multiplexer are I7 to I4 and the data inputs of lower 4x1 Multiplexer are I3 to I0. Therefore,
each 4x1 Multiplexer produces an output based on the values of selection lines, s1 & s0.
The outputs of first stage 4x1 Multiplexers are applied as inputs of 2x1 Multiplexer that is
present in second stage. The other selection line, s2 is applied to 2x1 Multiplexer.
 If s2 is zero, then the output of 2x1 Multiplexer will be one of the 4 inputs I3 to I0 based
on the values of selection lines s1 & s0.
 If s2 is one, then the output of 2x1 Multiplexer will be one of the 4 inputs I7 to I4 based
on the values of selection lines s1 & s0.
Therefore, the overall combination of two 4x1 Multiplexers and one 2x1 Multiplexer performs
as one 8x1 Multiplexer.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

16x1 Multiplexer

In this section, let us implement 16x1 Multiplexer using 8x1 Multiplexers and 2x1 Multiplexer.
We know that 8x1 Multiplexer has 8 data inputs, 3 selection lines and one output. Whereas,
16x1 Multiplexer has 16 data inputs, 4 selection lines and one output.
So, we require two 8x1 Multiplexers in first stage in order to get the 16 data inputs. Since, each
8x1 Multiplexer produces one output, we require a 2x1 Multiplexer in second stage by
considering the outputs of first stage as inputs and to produce the final output.
Let the 16x1 Multiplexer has sixteen data inputs I15 to I0, four selection lines s3 to s0 and one
output Y. The Truth table of 16x1 Multiplexer is shown below.

Selection Inputs Output

S3 S2 S1 S0 Y

0 0 0 0 I0

0 0 0 1 I1

0 0 1 0 I2

0 0 1 1 I3

0 1 0 0 I4

0 1 0 1 I5

0 1 1 0 I6

0 1 1 1 I7

1 0 0 0 I8

1 0 0 1 I9

1 0 1 0 I10

1 0 1 1 I11

1 1 0 0 I12

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

1 1 0 1 I13

1 1 1 0 I14

1 1 1 1 I15

We can implement 16x1 Multiplexer using lower order Multiplexers easily by considering the
above Truth table. The block diagram of 16x1 Multiplexer is shown in the following figure.

De-Multiplexer is a combinational circuit that performs the reverse operation of Multiplexer. It

has single input, ‘n’ selection lines and maximum of 2n outputs. The input will be connected to
one of these outputs based on the values of selection lines.
Since there are ‘n’ selection lines, there will be 2n possible combinations of zeros and ones. So,
each combination can select only one output. De-Multiplexer is also called as De-Mux.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

1x4 De-Multiplexer
1x4 De-Multiplexer has one input I, two selection lines, s1 & s0 and four outputs Y3, Y2,
Y1 &Y0. The block diagram of 1x4 De-Multiplexer is shown in the following figure.

The single input ‘I’ will be connected to one of the four outputs, Y3 to Y0 based on the values of
selection lines s1 & s0. The Truth table of 1x4 De-Multiplexer is shown below.

Selection Inputs Outputs

S1 S0 Y3 Y2 Y1 Y0

0 0 0 0 0 I

0 1 0 0 I 0

1 0 0 I 0 0

1 1 I 0 0 0

From the above Truth table, we can directly write the Boolean functions for each output as

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

Y3=s1s0IY3=s1s0I
Y2=s1s0′IY2=s1s0′I
Y1=s1′s0IY1=s1′s0I
Y0=s1′s0′IY0=s1′s0′I
We can implement these Boolean functions using Inverters & 3-input AND gates. The circuit
diagram of 1x4 De-Multiplexer is shown in the following figure.

We can easily understand the operation of the above circuit. Similarly, you can implement 1x8
De-Multiplexer and 1x16 De-Multiplexer by following the same procedure.

Implementation of Higher-order De-Multiplexers

Now, let us implement the following two higher-order De-Multiplexers using lower-order De-
Multiplexers.

 1x8 De-Multiplexer

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

 1x16 De-Multiplexer

1x8 De-Multiplexer

In this section, let us implement 1x8 De-Multiplexer using 1x4 De-Multiplexers and 1x2 De-
Multiplexer. We know that 1x4 De-Multiplexer has single input, two selection lines and four
outputs. Whereas, 1x8 De-Multiplexer has single input, three selection lines and eight outputs.
So, we require two 1x4 De-Multiplexers in second stage in order to get the final eight outputs.
Since, the number of inputs in second stage is two, we require 1x2 DeMultiplexer in first stage
so that the outputs of first stage will be the inputs of second stage. Input of this 1x2 De-
Multiplexer will be the overall input of 1x8 De-Multiplexer.
Let the 1x8 De-Multiplexer has one input I, three selection lines s2, s1 & s0 and outputs Y7 to
Y0. The Truth table of 1x8 De-Multiplexer is shown below.

Selection Inputs Outputs

s2 s1 s0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0

0 0 0 0 0 0 0 0 0 0 I

0 0 1 0 0 0 0 0 0 I 0

0 1 0 0 0 0 0 0 I 0 0

0 1 1 0 0 0 0 I 0 0 0

1 0 0 0 0 0 I 0 0 0 0

1 0 1 0 0 I 0 0 0 0 0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

1 1 0 0 I 0 0 0 0 0 0

1 1 1 I 0 0 0 0 0 0 0

We can implement 1x8 De-Multiplexer using lower order Multiplexers easily by considering
the above Truth table. The block diagram of 1x8 De-Multiplexer is shown in the following
figure.

The common selection lines, s1 & s0 are applied to both 1x4 De-Multiplexers. The outputs of
upper 1x4 De-Multiplexer are Y7 to Y4 and the outputs of lower 1x4 De-Multiplexer are Y3 to
Y0.
The other selection line, s2 is applied to 1x2 De-Multiplexer. If s2 is zero, then one of the four
outputs of lower 1x4 De-Multiplexer will be equal to input, I based on the values of selection
lines s1 & s0. Similarly, if s2 is one, then one of the four outputs of upper 1x4 DeMultiplexer
will be equal to input, I based on the values of selection lines s1 & s0.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 10

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

1x16 De-Multiplexer

In this section, let us implement 1x16 De-Multiplexer using 1x8 De-Multiplexers and 1x2 De-
Multiplexer. We know that 1x8 De-Multiplexer has single input, three selection lines and eight
outputs. Whereas, 1x16 De-Multiplexer has single input, four selection lines and sixteen
outputs.
So, we require two 1x8 De-Multiplexers in second stage in order to get the final sixteen
outputs. Since, the number of inputs in second stage is two, we require 1x2 DeMultiplexer in
first stage so that the outputs of first stage will be the inputs of second stage. Input of this 1x2
De-Multiplexer will be the overall input of 1x16 De-Multiplexer.
Let the 1x16 De-Multiplexer has one input I, four selection lines s3, s2, s1 & s0 and outputs
Y15 to Y0. The block diagram of 1x16 De-Multiplexer using lower order Multiplexers is shown
in the following figure.

The common selection lines s2, s1 & s0 are applied to both 1x8 De-Multiplexers. The outputs of
upper 1x8 De-Multiplexer are Y15 to Y8 and the outputs of lower 1x8 DeMultiplexer are Y7 to
Y0.
The other selection line, s3 is applied to 1x2 De-Multiplexer. If s3 is zero, then one of the eight
outputs of lower 1x8 De-Multiplexer will be equal to input, I based on the values of selection
lines s2, s1 & s0. Similarly, if s3 is one, then one of the 8 outputs of upper 1x8 De-Multiplexer
will be equal to input, I based on the values of selection lines s2, s1 & s0.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 11

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

The same selection lines, s2, s1 & s0 are applied to both 8x1 Multiplexers. The data inputs of
upper 8x1 Multiplexer are I15 to I8 and the data inputs of lower 8x1 Multiplexer are I7 to I0.
Therefore, each 8x1 Multiplexer produces an output based on the values of selection lines, s2,
s 1 & s0 .

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 12

Lecture-4 Multiplexer- De- Multiplexer Digital Electronics

The outputs of first stage 8x1 Multiplexers are applied as inputs of 2x1 Multiplexer that is
present in second stage. The other selection line, s3 is applied to 2x1 Multiplexer.
 If s3 is zero, then the output of 2x1 Multiplexer will be one of the 8 inputs Is7 to I0 based
on the values of selection lines s2, s1 & s0.
 If s3 is one, then the output of 2x1 Multiplexer will be one of the 8 inputs I15 to I8 based
on the values of selection lines s2, s1 & s0.
Therefore, the overall combination of two 8x1 Multiplexers and one 2x1 Multiplexer performs
as one 16x1 Multiplexer.
………………………………………….xxxxxx………………………………………………….

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 13

Lecture-5 Decoders Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

Decoder is a combinational circuit that has ‘n’ input lines and maximum of 2n output lines. One
of these outputs will be active High based on the combination of inputs present, when the
decoder is enabled. That means decoder detects a particular code. The outputs of the decoder
are nothing but the min terms of ‘n’ input variables lineslines, when it is enabled.

2 to 4 Decoder
Let 2 to 4 Decoder has two inputs A1 & A0 and four outputs Y3, Y2, Y1 & Y0. The block
diagram of 2 to 4 decoder is shown in the following figure.

One of these four outputs will be ‘1’ for each combination of inputs when enable, E is ‘1’.
The Truth table of 2 to 4 decoder is shown below.

Enable Inputs Outputs

E A1 A0 Y3 Y2 Y1 Y0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-5 Decoders Digital Electronics

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

From Truth table, we can write the Boolean functions for each output as
Y3=E.A1.A0
Y2=E.A1.A0′
Y1=E.A1′.A0
Y0=E.A1′.A0′
Each output is having one product term. So, there are four product terms in total. We can
implement these four product terms by using four AND gates having three inputs each & two
inverters. The circuit diagram of 2 to 4 decoder is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-5 Decoders Digital Electronics

Therefore, the outputs of 2 to 4 decoder are nothing but the min terms of two input variables
A1 & A0, when enable, E is equal to one. If enable, E is zero, then all the outputs of decoder will
be equal to zero.
Similarly, 3 to 8 decoder produces eight min terms of three input variables A2, A1 & A0 and 4 to
16 decoder produces sixteen min terms of four input variables A3, A2, A1 & A0.

Implementation of Higher-order Decoders

Now, let us implement the following two higher-order decoders using lower-order decoders.

 3 to 8 decoder
 4 to 16 decoder

3 to 8 Decoder

In this section, let us implement 3 to 8 decoder using 2 to 4 decoders. We know that 2 to 4

Decoder has two inputs, A1 & A0 and four outputs, Y3 to Y0. Whereas, 3 to 8 Decoder has three
inputs A2, A1 & A0 and eight outputs, Y7 to Y0.
We can find the number of lower order decoders required for implementing higher order
decoder using the following formula.
Required number of lower order decoders=m2 /m1
Where,
m1 is the number of outputs of lower order decoder.
m2 is the number of outputs of higher order decoder.
Here, m1 = 4 and m2 = 8. Substitute, these two values in the above formula.
Required number of 2to4decoders=8/ 4=2
Therefore, we require two 2 to 4 decoders for implementing one 3 to 8 decoder. The block
diagram of 3 to 8 decoder using 2 to 4 decoders is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-5 Decoders Digital Electronics

The parallel inputs A1 & A0 are applied to each 2 to 4 decoder. The complement of input A2 is
connected to Enable, E of lower 2 to 4 decoder in order to get the outputs, Y 3 to Y0. These are
the lower four min terms. The input, A2 is directly connected to Enable, E of upper 2 to 4
decoder in order to get the outputs, Y7 to Y4. These are the higher four min terms.

4 to 16 Decoder

In this section, let us implement 4 to 16 decoder using 3 to 8 decoders. We know that 3 to 8

Decoder has three inputs A2, A1 & A0 and eight outputs, Y7 to Y0. Whereas, 4 to 16 Decoder
has four inputs A3, A2, A1 & A0 and sixteen outputs, Y15 to Y0
We know the following formula for finding the number of lower order decoders required.
Required number of lower order decoders=m2/m1
Substitute, m1 = 8 and m2 = 16 in the above formula.
Required number of 3to8decoders=16/8=2
Therefore, we require two 3 to 8 decoders for implementing one 4 to 16 decoder. The block
diagram of 4 to 16 decoder using 3 to 8 decoders is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-5 Decoders Digital Electronics

An Encoder is a combinational circuit that performs the reverse operation of Decoder. It has
maximum of 2n input lines and ‘n’ output lines. It will produce a binary code equivalent to the
input, which is active High. Therefore, the encoder encodes 2n input lines with ‘n’ bits. It is
optional to represent the enable signal in encoders.

4 to 2 Encoder
Let 4 to 2 Encoder has four inputs Y3, Y2, Y1 & Y0 and two outputs A1 & A0. The block
diagram of 4 to 2 Encoder is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-5 Decoders Digital Electronics

At any time, only one of these 4 inputs can be ‘1’ in order to get the respective binary code at
the output. The Truth table of 4 to 2 encoder is shown below.

Inputs Outputs

Y3 Y2 Y1 Y0 A1 A0

0 0 0 1 0 0

0 0 1 0 0 1

0 1 0 0 1 0

1 0 0 0 1 1

From Truth table, we can write the Boolean functions for each output as
A1=Y3+Y2
A0=Y3+Y1
We can implement the above two Boolean functions by using two input OR gates. The circuit
diagram of 4 to 2 encoder is shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-5 Decoders Digital Electronics

The above circuit diagram contains two OR gates. These OR gates encode the four inputs with
two bits

Drawbacks of Encoder

Following are the drawbacks of normal encoder.

 There is an ambiguity, when all outputs of encoder are equal to zero. Because, it could be
the code corresponding to the inputs, when only least significant input is one or when all
inputs are zero.
 If more than one input is active High, then the encoder produces an output, which may
not be the correct code. For example, if both Y3 and Y6 are ‘1’, then the encoder
produces 111 at the output. This is neither equivalent code corresponding to Y3, when it
is ‘1’ nor the equivalent code corresponding to Y6, when it is ‘1’.
So, to overcome these difficulties, we should assign priorities to each input of encoder. Then,
the output of encoder will be the binary code corresponding to the active High input s, which
has higher priority. This encoder is called as priority encoder.

Priority Encoder
A 4 to 2 priority encoder has four inputs Y3, Y2, Y1 & Y0 and two outputs A1 & A0. Here, the
input, Y3 has the highest priority, whereas the input, Y0 has the lowest priority. In this case,
even if more than one input is ‘1’ at the same time, the output will be the binarybinary code
corresponding to the input, which is having higher priority.
We considered one more output, V in order to know, whether the code available at outputs is
valid or not.
 If at least one input of the encoder is ‘1’, then the code available at outputs is a valid one.
In this case, the output, V will be equal to 1.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-5 Decoders Digital Electronics

 If all the inputs of encoder are ‘0’, then the code available at outputs is not a valid one. In
this case, the output, V will be equal to 0.
The Truth table of 4 to 2 priority encoder is shown below.

Inputs Outputs

Y3 Y2 Y1 Y0 A1 A0 V

0 0 0 0 0 0 0

0 0 0 1 0 0 1

0 0 1 x 0 1 1

0 1 x x 1 0 1

1 x x x 1 1 1

Use 4 variable K-maps for getting simplified expressions for each output.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-5 Decoders Digital Electronics

The simplified Boolean functions are

A1=Y3+Y2
A0=Y3+Y2′Y1
Similarly, we will get the Boolean function of output, V as
V=Y3+Y2+Y1+Y0
We can implement the above Boolean functions using logic gates. The circuit diagram of 4 to
2 priority encoder is shown in the following figure.

The above circuit diagram contains two 2-input OR gates, one 4-input OR gate, one 2input
AND gate & an inverter. Here AND gate & inverter combination are used for producing a valid
code at the outputs, even when multiple inputs are equal to ‘1’ at the same time. Hence, this
circuit encodes the four inputs with two bits based on the priority assigned to each input.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-7 Adders, Subtractors Digital Electronics
Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

Binary Adder
The most basic arithmetic operation is addition. The circuit, which performs the addition of two
binary numbers, is known as Binary adder. First, let us implement an adder, which performs
the addition of two bits.

Half Adder
Half adder is a combinational circuit, which performs the addition of two binary numbers A and
B are of single bit. It produces two outputs sum, S & carry, C.
The Truth table of half adder is shown below.

Inputs Outputs

A B C S

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

When we do the addition of two bits, the resultant sum can have the values ranging from 0 to 2
in decimal. We can represent the decimal digits 0 and 1 with single bit in binary. But, we can’t
represent decimal digit 2 with single bit in binary. So, we require two bits for representing it in
binary.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-7 Adders, Subtractors Digital Electronics
Let, sum, S is the least significant bit and carry, C is the most significant bit of the resultant
sum. For first three combinations of inputs, carry, C is zero and the value of S will be either
zero or one based on the number of ones present at the inputs. But, for last combination of
inputs, carry, C is one and sum, S is zero, since the resultant sum is two.
From Truth table, we can directly write the Boolean functions for each output as

We can implement the above functions with 2-input Ex-OR gate & 2-input AND gate.
The circuit diagram of half adder is shown in the following figure.

In the above circuit, a two input Ex-OR gate & two input AND gate produces sum, S & carry, C
respectively. Therefore, Half-adder performs the addition of two bits.

Full Adder

Full adder is a combinational circuit, which performs the addition of three bits A, B and Cin.
Where, A & B are the two parallel significant bits and Cin is the carry bit, which is generated
from previous stage. This Full adder also produces two outputs sum, S & carry, Cout, which are
similar to Half adder.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-7 Adders, Subtractors Digital Electronics
The Truth table of Full adder is shown below.

Inputs Outputs

A B Cin Cout S

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

When we do the addition of three bits, the resultant sum can have the values ranging from 0 to 3
in decimal. We can represent the decimal digits 0 and 1 with single bit in binary. But, we can’t
represent the decimal digits 2 and 3 with single bit in binary. So, we require two bits for
representing those two decimal digits in binary.
Let, sum, S is the Least significant bit and carry, Cout is the Most significant bit of resultant sum.
It is easy to fill the values of outputs for all combinations of inputs in the truth table. Just count
the number of ones present at the inputs and write the equivalent binary number at outputs. If
Cin is equal to zero, then Full adder truth table is same as that of Half adder truth table.
We will get the following Boolean functions for each output after simplification.

The sum, S is equal to one, when odd number of ones present at the inputs. We know that Ex-
OR gate produces an output, which is an odd function. So, we can use either two 2input Ex-OR
gates or one 3-input Ex-OR gate in order to produce sum, S. We can implement carry,
Cout using two 2-input AND gates & one OR gate. The circuit diagram of Full adder is shown
in the following figure.
Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3
Lecture-7 Adders, Subtractors Digital Electronics

This adder is called as Full adder because for implementing one Full adder, we require two
Half adders and one OR gate. If Cin is zero, then Full adder becomes Half adder. We can verify
it easily from the above circuit diagram or from the Boolean functions of outputs of Full adder.

4-bit Binary Adder

The 4-bit binary adder performs the addition of two 4-bit numbers. Let the 4-bit binary
numbers, A=A3A2A1A0 and B=B3B2B1B0. We can implement 4-bit binary adder in one of
the two following ways.
 Use one Half adder for doing the addition of two Least significant bits and three Full
adders for doing the addition of three higher significant bits.
 Use four Full adders for uniformity. Since, initial carry Cin is zero, the Full adder which
is used for adding the least significant bits becomes Half adder.
For the time being, we considered second approach. The block diagram of 4-bit binary adder is
shown in the following figure.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-7 Adders, Subtractors Digital Electronics

Here, the 4 Full adders are cascaded. Each Full adder is getting the respective bits of two
parallel inputs A & B. The carry output of one Full adder will be the carry input of subsequent
higher order Full adder. This 4-bit binary adder produces the resultant sum having at most 5
bits. So, carry out of last stage Full adder will be the MSB.
In this way, we can implement any higher order binary adder just by cascading the required
number of Full adders. This binary adder is also called as ripple carry binary adder because
the carry propagates ripples from one stage to the next stage.

Half Subtractor-

 Half Subtractor is a combinational logic circuit.

 It is used for the purpose of subtracting two single bit numbers.
 It contains 2 inputs and 2 outputs (difference and borrow).

Half Subtractor Designing-

Half subtractor is designed in the following steps-

Step-01:

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-7 Adders, Subtractors Digital Electronics
Identify the input and output variables-

 Input variables = A, B (either 0 or 1)

 Output variables = D, b where D = Difference and b = borrow

Step-02:

Draw the truth table-

Step-03:

Draw K-maps using the above truth table and determine the simplified Boolean expressions-

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-7 Adders, Subtractors Digital Electronics
Step-04:

Draw the logic diagram.

The implementation of half subtractor using 1 XOR gate, 1 NOT gate and 1 AND gate is as
shown below-

Full Subtractor-

 Full Subtractor is a combinational logic circuit.

 It is used for the purpose of subtracting two single bit numbers.
 It also takes into consideration borrow of the lower significant stage.
 Thus, full subtractor has the ability to perform the subtraction of three bits.
 Full subtractor contains 3 inputs and 2 outputs (Difference and Borrow) as shown-

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-7 Adders, Subtractors Digital Electronics

Designing a Full Subtractor-

Full subtractor is designed in the following steps-

Step-01:

Identify the input and output variables-

 Input variables = A, B, Bin (either 0 or 1)

 Output variables = D, Bout where D = Difference and Bout = Borrow

Step-02:

Draw the truth table-

Inputs
Outputs

A B Bin Bout (Borrow) D (Difference)

0 0 0 0 0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-7 Adders, Subtractors Digital Electronics

0 0 1 1 1

0 1 0 1 1

0 1 1 1 0

1 0 0 0 1

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Truth Table

Step-03:

Draw K-maps using the above truth table and determine the simplified Boolean expressions-

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-7 Adders, Subtractors Digital Electronics

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 10

Lecture-7 Adders, Subtractors Digital Electronics
Step-04:

Draw the logic diagram.

Carry Look Ahead Adder-

 Carry Look Ahead Adder is an improved version of the ripple carry adder.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 11

Lecture-7 Adders, Subtractors Digital Electronics
 It generates the carry-in of each full adder simultaneously without causing any delay.
 The time complexity of carry look ahead adder = Θ (logn).

Logic Diagram-

The logic diagram for carry look ahead adder is as shown below-

Carry Look Ahead Adder Working-

The working of carry look ahead adder is based on the principle-

The carry-in of any stage full adder is independent of the carry bits generated during intermediate stages.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 12

Lecture-7 Adders, Subtractors Digital Electronics
The carry-in of any stage full adder depends only on the following two parameters-

 Bits being added in the previous stages

 Carry-in provided in the beginning

Now,

 The above two parameters are always known from the beginning.
 So, the carry-in of any stage full adder can be evaluated at any instant of time.
 Thus, any full adder need not wait until its carry-in is generated by its previous stage full
adder.
4-Bit Carry Look Ahead Adder-

Consider two 4-bit binary numbers A3A2A1A0 and B3B2B1B0 are to be added.

Mathematically, the two numbers will be added as-

From here, we have-

C1 = C0 (A0 ⊕ B0) + A0B0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 13

Lecture-7 Adders, Subtractors Digital Electronics
C2 = C1 (A1 ⊕ B1) + A1B1

C3 = C2 (A2 ⊕ B2) + A2B2

C4 = C3 (A3 ⊕ B3) + A3B3

For simplicity, Let-

 Gi = AiBi where G is called carry generator

 Pi = Ai ⊕ Bi where P is called carry propagator

Then, re-writing the above equations, we have-

C1 = C0P0 + G0 ………….. (1)

C2 = C1P1 + G1 ………….. (2)

C3 = C2P2 + G2 ………….. (3)

C4 = C3P3 + G3 ………….. (4)

Now,

 Clearly, C1, C2 and C3 are intermediate carry bits.

 So, let’s remove C1, C2 and C3 from RHS of every equation.
 Substituting (1) in (2), we get C2 in terms of C0.
 Then, substituting (2) in (3), we get C3 in terms of C0 and so on.

Finally, we have the following equations-

 C1 = C0P0 + G0
 C2 = C0P0P1 + G0P1 + G1
 C3 = C0P0P1P2 + G0P1P2 + G1P2 + G2
 C4 =C0P0P1P2P3 + G0P1P2P3 + G1P2P3 + G2P3 + G3

These equations are important to remember.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 14

Lecture-7 Adders, Subtractors Digital Electronics

These equations show that the carry-in of any stage full adder depends only on-

 Bits being added in the previous stages

 Carry bit which was provided in the beginning

Trick To Memorize Above Equations-

As an example, let us consider the equation for generating carry bit C2.

There are three possible reasons for generation of C2 as depicted in the following picture-

In the similar manner, we can write other equations as well very easily.

Implementation Of Carry Generator Circuits-

The above carry generator circuits are usually implemented as-

 Two level combinational circuits.

 Using AND and OR gates where gates are assumed to have any number of inputs.

Implementation Of C1–

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 15

Lecture-7 Adders, Subtractors Digital Electronics

 The carry generator circuit for C1 is implemented as shown below.

 It requires 1 AND gate and 1 OR gate.

Implementation Of C2–

 The carry generator circuit for C2 is implemented as shown below.

 It requires 2 AND gates and 1 OR gate.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 16

Lecture-7 Adders, Subtractors Digital Electronics

Implementation Of C3 & C4–

Similarly, we implement C3 and C4.

 Implementation of C3 uses 3 AND gates and 1 OR gate.

 Implementation of C4 uses 4 AND gates and 1 OR gate.

Total number of gates required to implement carry generators (provided carry propagators P i and
carry generators Gi) are-

 Total number of AND gates required for addition of 4-bit numbers = 1 + 2 + 3 + 4 = 10.
 Total number of OR gates required for addition of 4-bit numbers = 1 + 1 + 1 + 1 = 4.

General Formula-

The following formula is used to calculate number of gates required for evaluating all carry bits-

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 17

Lecture-7 Adders, Subtractors Digital Electronics

For a n-bit carry look ahead adder to evaluate all the carry bits, it requires-

 Number of AND gates = n(n+1) / 2

 Number of OR gates = n

Advantages of Carry Look Ahead Adder-

The advantages of carry look ahead adder are-

 It generates the carry-in for each full adder simultaneously.

 It reduces the propagation delay.

Disadvantages of Carry Look Ahead Adder-

Disadvantages of Carry Look Ahead Adder-

The disadvantages of carry look ahead adder are-

 It involves complex hardware.

 It is costlier since it involves complex hardware.
 It gets more complicated as the number of bits increases.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 18

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic functions
using K-map, minimization of logical functions. Don‟t care conditions, Multiplexer, De-
Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial adder,
ALU, elementary ALU design, popular MSI chips, digital comparator, parity checker/generator,
code converters, priority encoders, decoders/drivers for display devices, Q-M method of function
realization.

ALU
Arithmetic Logic Unit (ALU), which is capable of performing logical operations (e.g. AND, OR,
Ex-OR, Invert etc.) in addition to the arithmetic operations (e.g. Addition, Subtraction etc.). The
control unit supplies the data required by the ALU from memory, or from input devices, and directs
the ALU to perform a specific operation based on the instruction fetched from the memory. ALU is
the “calculator” portion of the computer.

An arithmetic logic unit(ALU) is a major component of the central processing unit of the a computer
system. It does all processes related to arithmetic and logic operations that need to be done on
instruction words. In some microprocessor architectures, the ALU is divided into the arithmetic unit
(AU) and the logic unit (LU).

An ALU can be designed by engineers to calculate many different operations. When the operations
become more and more complex, then the ALU will also become more and more expensive and also
takes up more space in the CPU and dissipates more heat. That is why engineers make the ALU

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

powerful enough to ensure that the CPU is also powerful and fast, but not so complex as to become
prohibitive in terms of cost and other disadvantages.

ALU is also known as an Integer Unit (IU). The arithmetic logic unit is that part of the CPU that
handles all the calculations the CPU may need. Most of these operations are logical in nature.
Depending on how the ALU is designed, it can make the CPU more powerful, but it also consumes
more energy and creates more heat. Therefore, there must be a balance between how powerful and
complex the ALU is and how expensive the whole unit becomes. This is why faster CPUs are more
expensive, consume more power and dissipate more heat.

Different operation as carried out by ALU can be categorized as follows –

 logical operations − These include operations like AND, OR, NOT, XOR, NOR, NAND,
etc.

 Bit-Shifting Operations − This pertains to shifting the positions of the bits by a certain
number of places either towards the right or left, which is considered a multiplication or
division operations.

 Arithmetic operations − This refers to bit addition and subtraction. Although multiplication
and division are sometimes used, these operations are more expensive to make.
Multiplication and subtraction can also be done by repetitive additions and subtractions
respectively.

Digital Comparator

The Digital Comparator is another very useful combinational logic circuit used to compare the value
of two binary digits

Digital or Binary Comparators are made up from standard AND, NOR and NOT gates that compare
the digital signals present at their input terminals and produce an output depending upon the
condition of those inputs.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

For example, along with being able to add and subtract binary numbers we need to be able to
compare them and determine whether the value of input A is greater than, smaller than or equal to
the value at input B etc. The digital comparator accomplishes this using several logic gates that
operate on the principles of Boolean Algebra. There are two main types of Digital
Comparator available and these are.

 1. Identity Comparator – an Identity Comparator is a digital comparator with only one output
terminal for when A = B, either A = B = 1 (HIGH) or A = B = 0 (LOW)
 2. Magnitude Comparator – a Magnitude Comparator is a digital comparator which has three
output terminals, one each for equality, A = B greater than, A > B and less than A < B
The purpose of a Digital Comparator is to compare a set of variables or unknown numbers, for
example A (A1, A2, A3, An, etc) against that of a constant or unknown value such as B (B1, B2, B3,
Bn, etc) and produce an output condition or flag depending upon the result of the comparison. For
example, a magnitude comparator of two 1-bits, (A and B) inputs would produce the following three
output conditions when compared to each other.

Which means: A is greater than B, A is equal to B, or A is less than B

This is useful if we want to compare two variables and want to produce an output when any of the
above three conditions are achieved. For example, produce an output from a counter when a certain
count number is reached. Consider the simple 1-bit comparator below.

1-bit Digital Comparator Circuit

Then the operation of a 1-bit digital comparator is given in the following Truth Table.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

Digital Comparator Truth Table

Inputs Outputs

B A A>B A=B A<B

0 0 0 1 0

0 1 1 0 0

1 0 0 0 1

1 1 0 1 0

You may notice two distinct features about the comparator from the above truth table. Firstly, the
circuit does not distinguish between either two “0” or two “1”„s as an output A = B is produced
when they are both equal, either A = B = “0” or A = B = “1”. Secondly, the output condition for A =
B resembles that of a commonly available logic gate, the Exclusive-NOR or Ex-NOR function
(equivalence) on each of the n-bits giving: Q = A ⊕ B

Parity Generator

Definition: The parity generator is a combination circuit at the transmitter, it takes an original
message as input and generates the parity bit for that message and the transmitter in this generator
transmits messages along with its parity bit.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

Types of Parity Generator

The classification of this generator is shown in the below figure

Even Parity Generator

The even parity generator maintains the binary data in even number of 1‟s, for example, the data
taken is in odd number of 1‟s, this even parity generator is going to maintain the data as even
number of 1‟s by adding the extra 1 to the odd number of 1‟s. This is also a combinational circuit
whose output is dependent upon the given input data, which means the input data is binary data or
binary code given for parity generator.

Let us consider three input binary data, that three bits are considered as A, B, and C. We can write
23 combinations using the three input binary data that is from 000 to 111 (0 to 7), total eight
combinations will get from the given three input binary data which we have considered. The truth
table of even parity generator for three input binary data is shown below.

0 0 0 – In this input binary code the even parity is taken as „0‟ because the input is already in
even parity, so no need to add even parity once again for this input.
0 0 1 – – In this input binary code there is only a single number of „1‟ and that single number of „1‟
is an odd number of „1‟. If an odd number of „1‟ is there, then even parity generator must
generate another „1‟ to make it as even parity, so even parity is taken as 1 to make the 0 0 1
code into even parity.
0 1 0 – This bit is in odd parity so even parity is taken as 1 to make the 0 1 0 code into even
parity.
0 1 1 – This bit is already in even parity so even parity is taken as 0 to make the 0 1 1 code into
even parity.
1 0 0 – This bit is in odd parity so even parity is taken as 1 to make the 1 0 0 code into even
parity.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

1 0 1 – This bit is already in even parity so even parity is taken as 0 to make the 1 0 1 code into
even parity.
1 1 0 – This bit is also in even parity so even parity is taken as 0 to make the 1 1 0 code into even
parity.
1 1 1 – This bit is in odd parity so even parity is taken as 1 to make the 1 1 1 code into even parity.
Even Parity Generator Truth Table

ABC Even Parity

0 00 0
0 01 1
0 10 1
0 11 0
1 00 1
1 01 0
1 10 0
1 11 1
The karnaugh map (k-map) simplification for three-bit input even parity is

k-map-for-even-parity-generator
From the above even parity truth table, the parity bit simplified expression is written as

The even parity expression implemented by using two Ex-OR gates and the logic diagram of this
even parity using the Ex-OR logic gate is shown below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

Even-parity-logic-circuit
In this way, the even parity generator generates an even number of 1‟s by taking the input data.

Odd Parity Generator

The odd parity generator maintains the binary data in an odd number of 1‟s, for example, the data
taken is in even number of 1‟s, this odd parity generator is going to maintain the data as an odd
number of 1‟s by adding the extra 1 to the even number of 1‟s. This is the combinational circuit
whose output is always dependent upon the given input data. If there is an even number of 1‟s then
only parity bit is added to make the binary code into an odd number of 1‟s.

Let us consider three input binary data, that three bits are considered as A, B, and C. The truth table
of odd parity generator for three input binary data is shown below.

0 0 0 – In this input binary code the odd parity is taken as „1‟ because the input is in even parity.
0 0 1 – This binary input is already in odd parity, so odd parity is taken as 0.
0 1 0 – This binary input is also in odd parity, so odd parity is taken as 0.
0 1 1 – This bit is in even parity so odd parity is taken as 1 to make the 0 1 1 code into odd
parity.
1 0 0 – This bit is already in odd parity, so odd parity is taken as 0 to make the 1 0 0 code into odd
parity.
1 0 1 – This input bit is in even parity, so odd parity is taken as 1 to make the 1 0 1 code into odd
parity.
1 1 0 – This bit is in even parity, so odd parity is taken as 1.
Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7
Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

1 1 1 – This input bit is in odd parity, so odd parity is taken as o.

Odd Parity Generator Truth Table

ABC Odd Parity

0 00 1
0 01 0
0 10 0
0 11 1
1 00 0
1 01 1

1 10 1
1 11 0
The Kavanaugh map (k-map) simplification for three-bit input odd parity is

k- map-for-odd-parity-generator

From the above odd parity truth table, the parity bit simplified expression is written as

The logic diagram of this odd parity generator is shown below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

logic-circuit
In this way, the odd parity generator generates an odd number of 1‟s by taking the input data.

Parity Check

Definition: The combinational circuit at the receiver is the parity checker. This checker takes the
received message including the parity bit as input. It gives output „1‟ if there is some error found and
gives output „0‟ if no error is found in the message including the parity bit.
Types of Parity Checker

The classification of the parity checker is shown in the below figure

Types-Of-Parity-Checker

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

Even Parity Checker

In even parity checker if the error bit (E) is equal to „1‟, then we have an error. If error bit E=0 then
indicates there is no error.

Error Bit (E) =1, error occurs

Error Bit (E) =0, no error

The parity checker circuit is shown in the below figure

logic-circuit
Odd Parity Checker

In odd parity checker if an error bit (E) is equal to „1‟, then it indicates there is no error. If an error
bit E=0 then indicates there is an error.

Error Bit (E) =1, no error

Error Bit (E) =0, error occurs

The parity checker won‟t be able to detect if there are errors in more than „1‟ bit and the correct of
data is also not possible, these are the main disadvantages of the parity checker.

Parity Generator/Checker using IC’s

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 10

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

The IC 74180 does the function of parity generation as well as checking. The 9 bit (8 data bits, 1
parity bit) Parity Generator/Checker is shown in the below figure.

IC-74180

The IC 74180 contains eight data bits (X0 to X7), Vcc, even input, odd input, Seven output, S odd
output, and ground pin.
If the given even and odd input both are high (H), then the even and odd outputs both are low (L),
similarly, if the given inputs both are Low (L), then the even and odd outputs both becomes high
(H).

Advantages of Parity

 Simplicity

 Easy to use
Applications of Parity

The applications of parity are

 In digital systems and many hardware applications, this parity is used

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 11

Lecture-6 ALU, Comparator and Parity Generator/Checker
Digital Electronics

 The parity bit is also used in Small Computer System Interface (SCSI) and also in Peripheral
Component Interconnect (PCI) to detect the errors

………………………………………….XXXX…………………………………………………..

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 12

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Syllabus

Module 2: Combinational Digital Circuits (7Hours)

Standard representation for logic functions, K-map representation, simplification of logic
functions using K-map, minimization of logical functions. Don‟t care conditions, Multiplexer,
De- Multiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity
checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M
method of function realization.

Encoder

Unlike a multiplexer that selects one individual data input line and then sends that data to a
single output line or switch, Digital Encoder more commonly called a Binary Encoder takes
ALL its data inputs one at a time and then converts them into a single encoded output. So we can
say that a binary encoder, is a multi-input combinational logic circuit that converts the logic level
“1” data at its inputs into an equivalent binary code at its output.

Generally, digital encoders produce outputs of 2-bit, 3-bit or 4-bit codes depending upon the
number of data input lines. An “n-bit” binary encoder has 2n input lines and n-bit output lines
with common types that include 4-to-2, 8-to-3 and 16-to-4 line configurations.

The output lines of a digital encoder generate the binary equivalent of the input line whose value
is equal to “1” and are available to encode either a decimal or hexadecimal input pattern to
typically a binary or “B.C.D” (binary coded decimal) output code.

4-to-2 Bit Binary Encoder

One of the main disadvantages of standard digital encoders is that they can generate the wrong
output code when there is more than one input present at logic level “1”. For example, if we

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 1

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

make inputs D1 and D2 HIGH at logic “1” both at the same time, the resulting output is neither at
“01” or at “10” but will be at “11” which is an output binary number that is different to the actual
input present. Also, an output code of all logic “0”s can be generated when all of its inputs are at
“0” OR when input D0 is equal to one.

One simple way to overcome this problem is to “Prioritise” the level of each input pin. So if
there is more than one input at logic level “1” at the same time, the actual output code would
only correspond to the input with the highest designated priority. Then this type of digital
encoder is known commonly as a Priority Encoder or P-encoder for short.

Priority Encoder

The Priority Encoder solves the problems mentioned above by allocating a priority level to
each input. The priority encoders output corresponds to the currently active input which has the
highest priority. So when an input with a higher priority is present, all other inputs with a lower
priority will be ignored.

The priority encoder comes in many different forms with an example of an 8-input priority
encoder along with its truth table shown below.

8-to-3 Bit Priority Encoder

Priority encoders are available in standard IC form and the TTL 74LS148 is an 8-to-3 bit priority
encoder which has eight active LOW (logic “0”) inputs and provides a 3-bit code of the highest
ranked input at its output.

Priority encoders output the highest order input first for example, if input lines “D2“, “D3” and
“D5” are applied simultaneously the output code would be for input “D5” (“101”) as this has the
highest order out of the 3 inputs. Once input “D5” had been removed the next highest output
code would be for input “D3” (“011”), and so on.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 2

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

The truth table for a 8-to-3 bit priority encoder is given as:

Where X equals “dont care”, that is logic “0” or a logic “1”.

From this truth table, the Boolean expression for the encoder above with data inputs D0 to D7 and
outputs Q0, Q1, Q2 is given as:

Output Q0

Output Q1

Output Q2

Then the final Boolean expression for the priority encoder including the zero inputs is defined as:

Priority Encoder Output Expression

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 3

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

In practice these zero inputs would be ignored allowing the implementation of the final Boolean
expression for the outputs of the 8-to-3 priority encoder. We can constructed a simple encoder
from the expression above using individual OR gates as follows.

Digital Encoder using Logic Gates

Digital Encoder Applications

Keyboard Encoder

Priority encoders can be used to reduce the number of wires needed in a particular circuits or
application that have multiple inputs. For example, assume that a microcomputer needs to read
the 104 keys of a standard QWERTY keyboard where only one key would be pressed either
“HIGH” or “LOW” at any one time.

One way would be to connect all 104 wires from the individual keys on the keyboard directly to
the computers input but this would be impractical for a small home PC. Another alternative and
better way would be to interface the keyboard to the PC using a priority encoder.

The 104 individual buttons or keys could be encoded into a standard ASCII code of only 7-bits
(0 to 127 decimal) to represent each key or character of the keyboard and then input as a much
smaller 7-bit B.C.D code directly to the computer. Keypad encoders such as the 74C923 20-key
encoder are available to do just that.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 4

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Positional Encoders

Another more common application is in magnetic positional control as used on ships navigation
or for robotic arm positioning etc. Here for example, the angular or rotary position of a compass
is converted into a digital code by a 74LS148 8-to-3 line priority encoder and input to the
systems computer to provide navigational data and an example of a simple 8 position to 3-bit
output compass encoder is shown below. Magnets and reed switches could be used at each
compass point to indicate the needles angular position.

Priority Encoder Navigation

Binary Output

Compass Direction

Q0 Q1 Q2

North 0 0 0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 5

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

North-East 0 0 1

East 0 1 0

South-East 0 1 1

South 1 0 0

South-West 1 0 1

West 1 1 0

North-West 1 1 1

Display Decoder

A Digital Decoder IC, is a device which converts one digital format into another and one of
the most commonly used devices for doing this is called the Binary Coded Decimal (BCD)
to 7-Segment Display Decoder.

7-segment LED (Light Emitting Diode) or LCD (Liquid Crystal Display) type displays, provide
a very convenient way of displaying information or digital data in the form of numbers, letters or
even alpha-numerical characters.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 6

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Typically 7-segment displays consist of seven individual coloured LED‟s (called the segments),
within one single display package. In order to produce the required numbers or HEX characters
from 0 to 9 and A to F respectively, on the display the correct combination of LED segments
need to be illuminated and BCD to 7-segment Display Decoders such as the 74LS47 do just
that.

A standard 7-segment LED display generally has eight (8) input connections, one for each LED
segment and one that acts as a common terminal or connection for all the internal display
segments. Some single displays have also have an additional input pin to display a decimal point
in their lower right or left hand corner.

In electronics there are two important types of 7-segment LED digital display.

 1. The Common Cathode Display (CCD) – In the common cathode display, all the
cathode connections of the LED‟s are joined together to logic “0” or ground. The
individual segments are illuminated by application of a “HIGH”, logic “1” signal to the
individual Anode terminals.
 2. The Common Anode Display (CAD) – In the common anode display, all the anode
connections of the LED‟s are joined together to logic “1” and the individual segments are
illuminated by connecting the individual Cathode terminals to a “LOW”, logic “0” signal.

Common Cathode and Common Anode Format

Electrical connection of the individual diodes for a common cathode display and a common
anode display and by illuminating each light emitting diode individually, they can be made to
display a variety of numbers or characters.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 7

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

7-Segment Display Format

So in order to display the number “3” for example, segments a, b, c, d and g would need to be
illuminated. If we wanted to display a different number or letter then a different set of segments
would need to be illuminated. Then for a 7-segment display, we can produce a truth table giving
the segments that need to be illuminated in order to produce the required character as shown
below.

Truth Table for a 7-segment display

Individual Segments Individual Segments

Display Display

a b c d e f g a b c d e f g

× × × × × × 0 × × × × × × × 8

× × 1 × × × × × × 9

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 8

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

× × × × × 2 × × × × × × A

× × × × × 3 × × × × × b

× × × × 4 × × × × C

× × × × × 5 × × × × × d

× × × × × × 6 × × × × × E

× × × 7 × × × × F

7-Segment Display Elements for all Numbers.

It can be seen that to display any single digit number from 0 to 9 in binary or letters
from A to F in hexadecimal, we would require seven separate segment connections plus one
additional connection for the LED‟s “common” connection. Also as the segments are basically a
standard light emitting diode, the driving circuit would need to produce up to 20mA of current to
illuminate each individual segment and to display the number “8”, all seven segments would
need to be lit resulting a total current of nearly 140mA, (8 x 20mA).

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 9

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Obviously, the use of so many connections and power consumption is impractical for some
electronic or microprocessor based circuits and so in order to reduce the number of signal lines
required to drive just one single display, display decoders such as the BCD to 7-Segment Display
Decoder and Driver IC‟s are used instead.

BCD to 7-Segment Display Decoders

A binary coded decimal (BCD) to 7-segment display decoder such as the TTL 74LS47 or
74LS48, have 4 BCD inputs and 7 output lines, one for each LED segment. This allows a smaller
4-bit binary number (half a byte) to be used to display all the denary numbers from 0 to 9 and by
adding two displays together, a full range of numbers from 00 to 99 can be displayed with just a
single byte of eight data bits.

BCD to 7-Segment Decoder

The use of packed BCD allows two BCD digits to be stored within a single byte (8-bits) of data,
allowing a single data byte to hold a BCD number in the range of 00 to 99.

An example of the 4-bit BCD input ( 0100 ) representing the number “4” is given below.

Display Decoder Example No1

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 10

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

In practice current limiting resistors of about 150Ω to 220Ω would be connected in series
between the decoder/driver chip and each LED display segment to limit the maximum current
flow. There are different display decoders and drivers available for the different types of
available displays, either LED or LCD. For example, the 74LS48 for common-cathode LED
types, the 74LS47 for common-anode LED types, or the CMOS CD4543 for liquid crystal
display (LCD) types.

Liquid crystal displays (LCD´s) have one major advantage over similar LED types in that they
consume much less power and nowadays, both LCD and LED displays are combined together to
form larger Dot-Matrix Alphanumeric type displays which can show letters and characters as
well as numbers in standard Red or Tri-colour outputs.

Quine-McClukey tabular method

Quine-McClukey tabular method is a tabular method based on the concept of prime implicants.
We know that prime implicant is a product orsumorsum term, which can‟t be further reduced
by combining with any other product orsumorsum terms of the given Boolean function.
This tabular method is useful to get the prime implicants by repeatedly using the following
Boolean identity.
xy + xy‟ = xy+y′y+y′ = x.1 = x

Procedure of Quine-McCluskey Tabular Method

Follow these steps for simplifying Boolean functions using Quine-McClukey tabular method.
Step 1 − Arrange the given min terms in an ascending order and make the groups based on the
number of ones present in their binary representations. So, there will be at most ‘n+1’
groups if there are „n‟ Boolean variables in a Boolean function or „n‟ bits in the binary
equivalent of min terms.
Step 2 − Compare the min terms present in successive groups. If there is a change in only one-
bit position, then take the pair of those two min terms. Place this symbol „_‟ in the differed bit
position and keep the remaining bits as it is.
Step 3 − Repeat step2 with newly formed terms till we get all prime implicants.
Step 4 − Formulate the prime implicant table. It consists of set of rows and columns. Prime
implicants can be placed in row wise and min terms can be placed in column wise. Place „1‟ in
the cells corresponding to the min terms that are covered in each prime implicant.
Step 5 − Find the essential prime implicants by observing each column. If the min term is
covered only by one prime implicant, then it is essential prime implicant. Those essential
prime implicants will be part of the simplified Boolean function.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 11

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Step 6 − Reduce the prime implicant table by removing the row of each essential prime
implicant and the columns corresponding to the min terms that are covered in that essential
prime implicant. Repeat step 5 for Reduced prime implicant table. Stop this process when all
min terms of given Boolean function are over.

Example

Let us simplify the following Boolean

function, f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15)f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15) using
Quine-McClukey tabular method.
The given Boolean function is in sum of min terms form. It is having 4 variables W, X, Y & Z.
The given min terms are 2, 6, 8, 9, 10, 11, 14 and 15. The ascending order of these min terms
based on the number of ones present in their binary equivalent is 2, 8, 6, 9, 10, 11, 14 and 15.
The following table shows these min terms and their equivalent binary representations.

Group Name Min terms W X Y Z

2 0 0 1 0
GA1

8 1 0 0 0

6 0 1 1 0

GA2 9 1 0 0 1

10 1 0 1 0

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 12

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

11 1 0 1 1

GA3
14 1 1 1 0

GA4 15 1 1 1 1

The given min terms are arranged into 4 groups based on the number of ones present in their
binary equivalents. The following table shows the possible merging of min terms from
adjacent groups.

Group Name Min terms W X Y Z

2,6 0 - 1 0

2,10 - 0 1 0
GB1

8,9 1 0 0 -

8,10 1 0 - 0

6,14 - 1 1 0

GB2 9,11 1 0 - 1

10,11 1 0 1 -

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 13

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

10,14 1 - 1 0

11,15 1 - 1 1

GB3
14,15 1 1 1 -

The min terms, which are differed in only one-bit position from adjacent groups are merged.
That differed bit is represented with this symbol, „-„. In this case, there are three groups and
each group contains combinations of two min terms. The following table shows the
possible merging of min term pairs from adjacent groups.

Group Name Min terms W X Y Z

2,6,10,14 - - 1 0

2,10,6,14 - - 1 0

GB1
8,9,10,11 1 0 - -

8,10,9,11 1 0 - -

10,11,14,15 1 - 1 -
GB2

10,14,11,15 1 - 1 -

The successive groups of min term pairs, which are differed in only one-bit position are merged.
That differed bit is represented with this symbol, „-„. In this case, there are two groups and each
group contains combinations of four min terms. Here, these combinations of 4 min terms are

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 14

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

available in two rows. So, we can remove the repeated rows. The reduced table after removing
the redundant rows is shown below.

Group Name Min terms W X Y Z

GC1 2,6,10,14 - - 1 0

8,9,10,11 1 0 - -

GC2 10,11,14,15 1 - 1 -

Further merging of the combinations of min terms from adjacent groups is not possible, since
they are differed in more than one-bit position. There are three rows in the above table. So, each
row will give one prime implicant. Therefore, the prime implicants are YZ‟, WX‟ & WY.
The prime implicant table is shown below.

Min terms / Prime 2 6 8 9 10 11 14 15

Implicants

YZ’ 1 1 1 1

WX’ 1 1 1 1

WY 1 1 1 1

The prime implicants are placed in row wise and min terms are placed in column wise. 1s are
placed in the common cells of prime implicant rows and the corresponding min term columns.
The min terms 2 and 6 are covered only by one prime implicant YZ’. So, it is an essential
prime implicant. This will be part of simplified Boolean function. Now, remove this prime
implicant row and the corresponding min term columns. The reduced prime implicant table is
shown below.

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 15

Lecture-7 Priority Encoders, Display Decoder and Q-M tabular Method
Digital Electronics

Min terms / Prime 8 9 11 15

Implicants

WX’ 1 1 1

WY 1 1

The min terms 8 and 9 are covered only by one prime implicant WX’. So, it is an essential
prime implicant. This will be part of simplified Boolean function. Now, remove this prime
implicant row and the corresponding min term columns. The reduced prime implicant table is
shown below.

Min terms / Prime 15

Implicants

WY 1

The min term 15 is covered only by one prime implicant WY. So, it is an essential prime
implicant. This will be part of simplified Boolean function.
In this example problem, we got three prime implicants and all the three are essential.
Therefore, the simplified Boolean function is
fW,X,Y,Z = YZ’ + WX’ + WY.
………………………………….XXXXXXX…………………………………………………….

Rashmi Priya, [Link] EEE Dept,MCE Motihari Page 16

 MODULE-2
NUMERICAL
1. Convert Y=AB + AC’ +BC into canonical SOP form.

2. Convert Y= (A+B)(A+C)(B+C’) into canonical POS form.

3.
4.