Unit II: Combinational Logic Design

Syllabus:

➢ Introduction to Combinational Logic: Logical Function Representations - Non-

standard & standard (SOP/POS), minterms & maxterms form, Standard canonical
form
➢ Introduction to Algebraic simplification & Karnaugh map, Simplifications of logic
functions using K map (up to 4 variables) & realization using logic gates. Example
- half adder, full adder & 4-bit parallel binary adder, code converters, 1/2-bit
magnitude comparators.
➢ MSI combinational logic circuits: Multiplexers (MUX), DE multiplexers (DEMUX),
Decoders, encoders & Priority encoder. Multiplexer & DE multiplexer Tree. Logic
function implementation using MUX & DECODER
2.1 INTRODUCTION:

The digital system consists of two types of circuits, namely

(i) Combinational circuits

(ii) Sequential circuits

Combinational circuit consists of logic gates whose output at any time is determined
from the present combination of inputs. The logic gate is the most basic building block of
combinational logic. The logical function performed by a combinational circuit is fully
defined by a set of Boolean expressions.

Boolean Function Boolean algebra is an algebra that deals with binary variables and logic
operations. A Boolean function described by an algebraic expression consists of binary
variables, the constants 0 and 1, and the logic operation symbols.

For a given value of the binary variables, the function can be equal to either 1 or 0.

F(vars) = expression

Set of binary Variables Operators (+, •, ‘)

Constants (0, 1)
Groupings (parenthesis)
Variables
Consider an example for the Boolean function

F1 = x + y’z

The function F1 is equal to 1 if x is equal to 1 or if both y’ and z are equal to 1. F1 is equal

to 0 otherwise. The complement operation dictates that when y’ = 1, y = 0. Therefore, F 1
= 1 if x = 1 or if y = 0 and z = 1.

A Boolean function expresses the logical relationship between binary variables and is
evaluated by determining the binary value of the expression for all possible values of the
variables.

A Boolean function can be represented in a truth table. The number of rows in the truth
table is 2n, where n is the number of variables in the function. The binary combinations
for the truth table are obtained from the binary numbers by counting from 0 through 2n -
1.

Truth Tables

• Enumerates all possible combinations of variable values and the

corresponding function value
• Truth tables for some arbitrary functions F1(x,y,z), F2(x,y,z), and F3(x,y,z)
are shown to the below
 • Truth table: a unique representation of a Boolean function
• If two functions have identical truth tables, the functions are equivalent
(and vice-versa).
• Truth tables can be used to prove equality theorems.
• However, the size of a truth table grows exponentially with the number of
variables involved, hence unwieldy. This motivates the use of Boolean
Algebra

Boolean expressions-NOT unique Unlike truth tables, expressions representing a

Boolean function are NOT unique.

• Example: – F(x,y,z) = x’•y’•z’ + x’•y•z’ + x•y•z’ – G(x,y,z) = x’•y’•z’ + y•z’

• The corresponding truth tables for F() and G() are shown below. They are identical.

• Thus, F() = G( )
2.2 Canonical and Standard Forms

We need to consider formal techniques for the simplification of Boolean functions.

Identical functions will have exactly the same canonical form.

• Minterms and Maxterms

• Sum-of-Minterms and Product-of- Maxterms

• Product and Sum terms

• Sum-of-Products (SOP) and Product-of-Sums (POS)

Definitions

Literal: A variable or its complement

Product term: literals connected by •

Sum term: literals connected by +

Minterm: a product term in which all the variables appear exactly once, either
complemented or uncomplemented

Maxterm: a sum term in which all the variables appear exactly once, either
complemented or uncomplemented.

Canonical form: Boolean functions expressed as a sum of Minterms or product of

Maxterms are said to be in canonical form.

Minterm

• Represents exactly one combination in the truth table.

• Denoted by mj, where j is the decimal equivalent of the minterm’s
corresponding binary combination (bj).
• A variable in mj is complemented if its value in bj is 0, otherwise is
uncomplemented.

Example: Assume 3 variables (A, B, C), and j=3. Then, bj = 011 and its corresponding
minterm is denoted by mj =A’BC

Maxterm
 • Represents exactly one combination in the truth table.
• Denoted by Mj, where j is the decimal equivalent of the maxterm’s
corresponding binary combination (bj).
• A variable in Mj is complemented if its value in bj is 1, otherwise is
uncomplemented.

Example: Assume 3 variables (A, B, C), and j=3. Then, bj = 011 and its corresponding
maxterm is denoted by Mj =A+B’+C’

Truth Table notation for Minterms and Maxterms

• Minterms and Maxterms are easy to denote using a truth table.

Example: Assume 3 variables x,y,z (order is fixed).

Canonical Forms:
Every function F() has two canonical forms:
– Canonical Sum-Of-Products (sum of minterms)
– Canonical Product-Of-Sums (product of maxterms)
Canonical Sum-Of-Products: The minterms included are those mj such that F( ) = 1 in
row j of the truth table for F( ).
Canonical Product-Of-Sums: The maxterms included are those Mj such that F( ) = 0 in
row j of the truth table for F( ).
Example Consider a Truth table for f1(a,b,c) given below.
The canonical sum-of-products form for f1 is
f1(a,b,c) = m1 + m2 + m4 + m6 = a’b’c + a’bc’ + ab’c’ + abc’
The canonical product-of-sums form for f1 is
f1(a,b,c) = M0 • M3 • M5 • M7 = (a+b+c)•(a+b’+c’)• (a’+b+c’)•(a’+b’+c’).

• Observe that: mj =Mj’

Shorthand: ∑ and ∏
• f1(a,b,c) = ∑ m(1,2,4,6), where ∑ indicates that this is a sum-of-products
form, and m(1,2,4,6) indicates that the minterms to be included are m1, m2,
m4, andm6.
• f1(a,b,c) = ∏ M(0,3,5,7), where ∏ indicates that this is a product-of-sums
form, and M(0,3,5,7) indicates that the maxterms to be included are M0,
M3, M5, andM7.
• Since mj = Mj’ for any j, ∑ m(1,2,4,6) = ∏ M(0,3,5,7) = f1(a,b,c)
Conversion between Canonical Forms
• Replace ∑ with ∏ (or vice versa) and replace those j’s that appeared in the
original form with those that do not.
• Example:
f1(a,b,c)= a’b’c + a’bc’ + ab’c’ + abc’
= m1 + m2 + m4 + m6
= ∑(1,2,4,6)
 = ∏(0,3,5,7)
= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)
Standard Forms
➢ Another way to express Boolean functions is in standard form.
➢ In this configuration, the terms that form the function may contain one, two, or any
number of literals.
➢ There are two types of standard forms: the sum of products and products of sums.
➢ The sum of products is a Boolean expression containing AND terms, called product
terms, with one or more literals each.
➢ The sum denotes the ORing of these terms.
➢ An example of a function expressed as a sum of products is F1 = y’ + xy + x’yz’
➢ The expression has three product terms, with one, two, and three literals.
➢ Their sum is, in effect, an OR operation. A product of sums is a Boolean expression
containing OR terms, called sum terms. Each term may have any number of literals.
➢ The product denotes the ANDing of these terms.
➢ An example of a function expressed as a product of sums is F2 = x(y’ + z)(x’ + y +
z’)
➢ This expression has three sum terms, with one, two, and three literals. The product
is an AND operation.

Conversion of SOP from standard to canonical form

Example-1. Express the Boolean function F = A + B’C as a sum of minterms.
Solution:
• The function has three variables: A, B, and C. The first term A is missing two
variables; therefore, A = A(B + B’) = AB + AB’ This function is still missing one
variable, so A = AB(C + C’) + AB’ (C + C’) = ABC + ABC’ + AB’C + AB’C’
• The second term B’C is missing one variable; hence, B’C = B’C(A + A’) = AB’C + A’B’C
Combining all terms, we have F = A + B’C = ABC + ABC’ + AB’C + AB’C’+ A’B’C
• But AB’C appears twice, and according to theorem (x + x = x), it is possible to
remove one of those occurrences.
• Rearranging the minterms in ascending order, we finally obtain F = A’B’C + AB’C +
AB’C + ABC’ + ABC = m1 + m4 + m5 + m6 + m7
 • When a Boolean function is in its sum-of-minterms form, it is sometimes
convenient to express the function in the following brief notation: F(A, B, C) = ∑m
(1, 4, 5, 6, 7)
Example-2. Express the Boolean function F = xy + x’z as a product of maxterms.
Solution:
• First, convert the function into OR terms by using the distributive law:
F = xy + x’z = (xy + x’)(xy + z)
= (x + x’)(y + x’)(x + z)(y + z)
= (x’+ y)(x + z)(y + z)
• The function has three variables: x, y, and z. Each OR term is missing one variable;
therefore,
x’+ y = x’ + y + zz’ = (x’ + y + z)(x’ + y + z’)
x + z = x + z + yy’ = (x + y + z)(x + y’ + z)
y + z = y + z + xx’ = (x + y + z)(x’ + y + z)
• Combining all the terms and removing those which appear more than once, we
finally obtain
• F = (x + y + z)(x + y’ + z)(x’ + y + z)(x’ + y + z)
• F= M0M2M4M5
• A convenient way to express this function is as follows:
• F(x, y, z) = πM(0, 2, 4, 5)
• The product symbol, π, denotes the ANDing of maxterms; the numbers are the
indices of the maxterms of the function.
2.3 KARNAUGH MAP

Karnaugh map method gives us a systematic approach for simplifying a Boolean expression.
Karnaugh map method was first proposed by Veitch and modified by Karnaugh, hence it is known
as Karnaugh Map or K-map. K-map contains boxes called cells. Each of the cell represents one of
the 2n possible products that can be formed from n variables. A two-variable k-map contains 22
=4 cells, a three variable contains 23 =8 cells and four variable contain 24 =16 cells. The figure 2.1
shows the outline of 1, 2, 3 and 4 variable maps.
 Fig. 2.1
The product term(minterm) assigned to the cells of K-map by labelling each row and column is
shown in 1, 2, 3 and 4 variable map and the product term(minterm) corresponding to each cell is
shown in the below figure (a),(b),(c) and (d) of fig. 2.2.

Fig. 2.2
The labelling of the rows and columns of a 1, 2, 3 and 4 variable K-map using Gray code and the
product terms(minterm) corresponding to each cell is shown in the figure 2.3 (a) (b) (c) and (d).

Fig. 2.3
The sum term(maxterm) assigned to the cells of K-map by labelling each row and column is shown
in 1, 2, 3 and 4 variable map and the sum term(maxterm) corresponding to each cell is shown in
the below figure 2.4 (a),(b),(c) and (d).
 Figure 2.4
The labelling of the rows and columns of a 1, 2, 3 and 4 variable K-map using Gray code and the
sum terms(maxterm) corresponding to each cell is shown in the figure 2.5 (a) (b) (c) and (d)

Figure 2.5
Plotting a Karnaugh Map
Representation of truth table on K-map

Figure 2.6
The representation of a two and three variable truth table on a Karnaugh map is shown in fig. 2.6
& 2.7 respectively

Figure 2.7
The representation of a four variable truth table on a Karnaugh map is shown below in fig. 2.8
 Fig. 2.8
Representation standard SOP on K-map
Example 1: Plot Boolean expression Y=ABC’ +ABC+A’ B ’ C on the Karnaugh map

Example 2: Plot Boolean expression Y=A’ BC’ D ’ + AB’CD’ +A’ BCD’ +AB’ CD+ABC’ D on the
karnaugh map.
Grouping Cells for Simplification
1. Grouping Two adjacent Pairs & Grouping Four adjacent ones (Quad)
2. Grouping Eight adjacent ones (Octet)
Simplification of Sum of Products Expression (SOP)
Example 1: Minimize the Boolean expression Y=A’ BC’D ’ + A’ BC’D +ABC’D ’ + ABC’D +AB’ C ’D +
A’ B ’ CD’ on Karnaugh map

Y=A’ B ’ CD’ +AC’D+BC’

Example 2: Simplify the logic function specified by the truth table using Karnaugh map method.
Y is the output variable and A,B,C are the input variable
 Y=B’ C ’ +BC
2.4 DON’T CARE CONDITIONS
• An output condition that can be regarded as either high or low
• The logical sum of the minterms associated with a Boolean function specifies the
conditions under which the function is equal to 1. The function is equal to 0 for the
rest of the minterms. This pair of conditions assumes that all the combinations of
the values for the variables of the function are valid. In practice, in some
applications the function is not specified for certain combinations of the variables.
As an example, the four-bit binary code for the decimal digits has six combinations
that are not used and consequently are considered to be unspecified. Functions
that have unspecified outputs for some input combinations are called
incompletely specified functions. In most applications, we simply don’t care what
value is assumed by the function for the unspecified minterms. For this reason, it
is customary to call the unspecified minterm of a function don’t care conditions.
 These don’t care conditions can be used on a map to provide further simplification
of the Boolean expression.
• A don’t care minterm is a combination of variables whose logical value is not
specified. Such a minterm cannot be marked with a 1 in the map, because it would
require that the function always be a 1 for such a combination. Likewise putting a
0 on the square requires the function to be 0. To distinguish don’t care condition
from 1’s or the 0’s an X is used. Thus an X inside a square in the map indicates that
we don’t care whether the value of 0 or 1 is assigned to F for the particular
minterm.
• In choosing the adjacent squares to simplify the function in a map the don’t care
minterms may be assumed to be either 0 0r 1. When simplifying the function, we
can choose to include each don’t care minterm with either the 1’s or the 0’s
depending on which combination gives the simplest expression.
Example Problem: Simplify the Boolean function F(w,x,y,z) = ∑(1,3,7,11,15) which has
the don’t care conditions d(w,x,y,z) = ∑(0,2,5).
Solution The minterms of F are the variable combinations that make the function equal
to 1. The minterms of “d” are don’t care minterms that may be assigned either 0 or 1. The
map simplification is shown in fig. the minterms of F are marked by 1’s. Those of d are
marked by X’s and remaining squares are filled with 0’s. To get simplified expression in
sum-of- product form we must include all five 1’s in the map but we may

In the part of the diagram, don’t care minterm 0 and 2 is included the units 1’s and the
simplified function is now
F = yz+w’x’
In the second don’t care minterm 5 is included with the 1’s , and the simplified function is
now
F = yz + w’z
2.5 NAND AND NOR IMPLIMENTATION

Digital circuits are frequently constructed with NAND and NOR gates rather than with
AND and OR gates. NAND and NOR gates are easier to fabricate. So, rules and procedures
have been developed for the conversion from Boolean functions given in terms of AND,
OR and NOT into equivalent NAND and NOR logic diagrams.
Two level NAND- NAND implementation
To facilitate the conversion to NAND logic, it is convenient to define an alternative graphic
symbol for the gate. The alternate representation of NAND gate is shown in fig. according
to De Morgan’s theorem
Steps to be followed
1. Simplify the given logic expression and convert it in the SOP form
2. Draw the logic circuit using AND, OR and NOT gate
3. Replace every AND gate by a NAND gate, Every OR gate by a bubbled OR gate and
NOT gate by a NAND inverter.
4. Replace bubbled-OR gate by NAND gate.
Example: Implement the following Boolean equation using only NAND gates
Y=AB+CDE+F
Solution:
Step 1: realization using basic gates
Step 2: replace AND →NAND, OR →bubbled – OR, NOT →NAND inverter
Step 3: draw the logic circuit using only NAND gates

MULTILEVEL NAND CIRCUITS

The standard form of expressing Boolean function results in a two-level implementation.
If has digital system three or more levels then the most common procedure in the design
of multilevel circuits is to express the Boolean function in terms of AND, OR and
compliments operations.
The general procedure for converting multilevel AND – OR logic diagram into an all-NAND
logic diagram is as follows
1. Convert all AND gates to NAND gates with AND – invert graphic symbols
2. Convert all OR gates to NAND gates with invert –OR graphic symbol.
3. Check all the bubbles in the diagram. For every bubble that is not compensated by
other small circle along the same line insert an inverter or compliment the input
literal.
Example: Implement the following Boolean expression using NAND gates only
F=A(CD+B)+BC
Solution:
Step 1: Draw logic diagram using AND,OR and NOT gate as shown in the fig.
NOR IMPLEMENTATION
The NOR operation is the dual of the AND operation. Therefore all procedures and rules
for NOR logic are the dual for the corresponding procedures and rules developed for
NAND logic. The NOR gate is another universal gate that can be used to implement any
Boolean function. The alternative representation of NOR gate according to demorgan’s
theorem is shown below.
Steps to be followed
1. Simply the given logic expression and convert it into product of sum (POS) form.
2. Draw the AND – OR-NOT realization.
3. Replace every OR gate by NOR, every AND gate by a bubbled AND gate and ever
inverter by a NOR inverter.
4. 4. Draw the final circuit using only the NOR gates.
Example: Implement the following function by using NOR gates Y=(A’+B+C)(A+B)D
Solution:
Step 1: Implement the given Boolean function by using AND, OR and NOT gate as shown
below.

Step 2: Replace OR → NOR AND → invert AND NOT → NOR invert Step 3: Replace invert
AND gate by NOR gate shown in fig.

Step 3: Replace invert AND gate by NOR gate shown in fig.

MULTILEVEL NOR IMPLEMENTATION

The procedure for converting a multilevel AND-OR diagram to an all NOR diagram is
similar to multilevel NAND implements. The following steps are followed for multilevel-
NOR implementation
• Step 1. Implement the logic function using AND, OR and NOT gate.
• Step 2. Convert all AND gates to NOR gates with invert-AND graphic symbol.
• Step 3. Convert all OR gates with OR invert graphic symbols.
 • Step 4. Check all the bubbles in the diagram. For every bubble that is not
compensated by another small circle along the same line, insert an inverter or
compliment the input literal.
Example: Implement the following Boolean function using NOR gatesY=(AB’+A’B)(C+D’)
Solution:
Step 1: Implement the Boolean function using AND,OR and NOT gate as shown in fig.

Step 2: Replace AND → invert-AND symbol, OR → NOR gate

Step 3: Check each line has even number of bubbles. If any line does not have even number
of bubbles the insert bubble (i.e. input A, B’,A’, B has odd number of bubbles. Therefore,
apply the inverted inputs to make even numbers of bubbles).

2.6 COMBINATIONAL CIRCUIT

A combinational circuit consists of input variables, logic gates, and output variables. The
logic gates accept signals from inputs and output signals are generated according to the
logic circuits employed in it. Binary information from the given data transforms to desired
output data in this process. Both input and output are obviously the binary signals, i.e.,
both the input and output signals are of two possible states, logic 1 and logic 0. [Fig. 2.9]

Fig. 2.9
For n number of input variables to a combinational circuit, 2n possible combinations of
binary input states are possible. For each possible combination, there is one and only one
possible output combination. A combinational logic circuit can be described by m Boolean
functions and each output can be expressed in terms of n input variables.
DESIGN PROCEDURE:
Any combinational circuit can be designed by the following steps of design procedure.
1. The problem is stated.
2. Identify the input and output variables.
3. The input and output variables are assigned letter symbols.
4. Construction of a truth table to meet input -output requirements.
5. Writing Boolean expressions for various output variables in terms of input
variables.
6. The simplified Boolean expression is obtained by any method of minimization—
algebraic method, Karnaugh map method, or tabulation method.
7. A logic diagram is realized from the simplified boolean expression using logic
gates.
The following guidelines should be followed while choosing the preferred form for
hardware implementation:
1. The implementation should have the minimum number of gates, with the gates
used having the minimum number of inputs.
2. There should be a minimum number of interconnections.
3. Limitation on the driving capability of the gates should not be ignored.
2.7 ARITHMETIC CIRCUITS:

In this section, we will discuss those combinational logic building blocks that can be used
to perform addition and subtraction operations on binary numbers. Addition and
subtraction are the two most commonly used arithmetic operations, as the other two,
namely multiplication and division, are respectively the processes of repeated addition
and repeated subtraction.
The basic building blocks that form the basis of all hardware used to perform the
arithmetic operations on binary numbers are half-adder, full adder, half-subtractor, full-
subtractor.
A. HALF-ADDER:
A half-adder is a combinational circuit that can be used to add two binary bits. It has two
inputs that represent the two bits to be added and two outputs, with one producing the
SUM output and the other producing the CARRY.

The truth table of a half-adder, showing all possible input combinations and the
corresponding outputs are shown below.

K-map simplification for carry and sum:

The Boolean expressions for the SUM and CARRY outputs are given by the equations,
Sum, S = A’B+ AB’= AB
Carry, C = A . B
The first one representing the SUM output is that of an EX-OR gate, the second one
representing the CARRY output is that of an AND gate.
The logic diagram of the half adder is,

B. FULL-ADDER:
Logic Implementation of Half-adder A full adder is a combinational circuit that forms the
arithmetic sum of three input bits. It consists of 3 inputs and 2 outputs. Two of the input
variables, represent the significant bits to be added. The third input represents the carry
from previous lower significant position. The block diagram of full adder is given by,
The full adder circuit overcomes the limitation of the half-adder, which can be used to add
two bits only. As there are three input variables, eight different input combinations are
possible. The truth table is shown below,

To derive the simplified Boolean expression from the truth table, the Karnaugh map
method is adopted as,

The Boolean expressions for the SUM and CARRY outputs are given by the equations,
Sum, S = A’B’Cin+ A’BC’in + AB’C’in + ABCin
Carry, Cout = AB+ ACin + BCin .
The logic diagram for the above functions is shown as,
The logic diagram of the full adder can also be implemented with two halfadders and one
OR gate. The S output from the second half adder is the exclusive-OR of Cin and the output
of the first half-adder, giving

and the carry output is,

2.8 FOUR-BIT PARALLEL ADDERS:

A group of four bits is called a nibble. A basic 4-bit parallel adder is implemented with
four full-adder stages as shown in Figure (2.10).

Fig. 2.10
• A binary parallel adder is a digital circuit that adds two binary numbers in parallel
form and produces the arithmetic sum of those numbers in parallel form.
• It consists of full adders connected in a chain , with the output carry from each full-
adder connected to the input carry of the next full-adder in the chain.
• The interconnection of four full-adder (FA) circuits to provide a 4-bit parallel
adder. The augends bits of A and addend bits of B are designated by subscript
numbers from right to left, with subscript 1 denoting the lower –order bit. The
carries are connected in a chain through the full-adders. The input carry to the
adder is Cin and the output carry is C4. The S output generates the required sum
bits.
• When the 4-bit full-adder circuit is enclosed within an IC package, it has four
terminals for the augends bits, four terminals for the addend bits, four terminals
for the sum bits, and two terminals for the input and output carries. [Fig. 2.11]
• AN n-bit parallel adder requires n-full adders. It can be constructed from 4-bit, 2-
bit and 1-bit full adder ICs by cascading several packages. The output carry from
one package must be connected to the input carry of the one with the next higher
–order bits. The 4-bit full adder is a typical example of an MSI function
Fig. 2.11
2.9 MAGNITUDE COMPARATOR:

A magnitude comparator is a combinational circuit that compares two given numbers (A

and B) and determines whether one is equal to, less than or greater than the other. The
output is in the form of three binary variables representing the conditions A = B, A>B
and A<B, If A & B are the two numbers being compared. [Fig. 2.12]

Fig. 2.12
For comparison of two n-bit numbers, the classical method to achieve the Boolean
expressions requires a truth table of 22n entries and becomes too lengthy and
cumbersome.
1-Bit Magnitude Comparator
A comparator used to compare two bits is called a single-bit comparator. It consists of two
inputs each for two single-bit numbers and three outputs to generate less than, equal to,
and greater than between two binary numbers.
The truth table for a 1-bit comparator is given below.

From the above truth table logical expressions for each output can be expressed as
follows.
A>B: AB’
A<B: A’B
A=B: A’B’+AB
From the above expressions, we can derive the following formula.

By using these Boolean expressions, we can implement a logic circuit for this comparator
as given below.

Fig. 2.13
2-bit Magnitude Comparator:
The truth table of 2-bit comparator is given in table below—
K-map Simplification:
Logic Diagram:
2.10 MULTIPLEXER: (DATA SELECTOR)

A multiplexer or MUX, is a combinational circuit with more than one input line, one output
line and more than one selection line. A multiplexer selects binary information present
from one of many input lines, depending upon the logic status of the selection inputs, and
routes it to the output line. Normally, there are 2n input lines and n selection lines whose
bit combinations determine which input is selected. The multiplexer is often labelled as
MUX in block diagrams.
A multiplexer is also called a data selector, since it selects one of many inputs and steers
the binary information to the output line.

Fig. 2.13
2-to-1- line Multiplexer:
The circuit has two data input lines, one output line and one selection line, S.
When S= 0, the upper AND gate is enabled and I0 has a path to the output.
When S=1, the lower AND gate is enabled and I1 has a path to the output.

The multiplexer acts like an electronic switch that selects one of the two sources.
Truth table:

4-to-1-line Multiplexer:
A 4-to-1-line multiplexer has four (2n) input lines, two (n) select lines and one output
line. It is the multiplexer consisting of four input channels and information of one of the
channels can be selected and transmitted to an output line according to the select inputs
combinations. Selection of one of the four input channel is possible by two selection
inputs.
Each of the four inputs I0 through I3, is applied to one input of AND gate. Selection lines
S1 and S0 are decoded to select a particular AND gate. The outputs of the AND gate are
applied to a single OR gate that provides the 1-line output.

Truth table:
To demonstrate the circuit operation, consider the case when S1S0= 10. The AND gate
associated with input I2 has two of its inputs equal to 1 and the third input connected to
I2. The other three AND gates have at least one input equal to 0, which makes their outputs
equal to 0. The OR output is now equal to the value of I2, providing a path from the selected
input to the output.

When these terms are ORed, the total expression for the data output is,

As in decoder, multiplexers may have an enable input to control the operation of the unit.
When the enable input is in the inactive state, the outputs are disabled, and when it is in
the active state, the circuit functions as a normal multiplexer.
Quadruple 2-to-1 Line Multiplexer:

This circuit has four multiplexers, each capable of selecting one of two input lines. Output
Y0 can be selected to come from either A0 or B0. Similarly, output Y1 may have the value of
A1 or B1, and so on. Input selection line, S selects one of the lines in each of the four
multiplexers. The enable input E must be active for normal operation.
Although the circuit contains four 2-to-1-Line multiplexers, it is viewed as a circuit that
selects one of two 4-bit sets of data lines. The unit is enabled when E= 0. Then if S= 0, the
four A inputs have a path to the four outputs. On the other hand, if S=1, the four B inputs
are applied to the outputs. The outputs have all 0‘s when E= 1, regardless of the value of
S.
Application:
The multiplexer is a very useful MSI function and has various ranges of applications in
data communication. Signal routing and data communication are the important
applications of a multiplexer. It is used for connecting two or more sources to guide to a
single destination among computer units and it is useful for constructing a common bus
system. One of the general properties of a multiplexer is that Boolean functions can be
implemented by this device.

Implementation of Boolean Function using MUX:

Any Boolean or logical expression can be easily implemented using a multiplexer. If a
Boolean expression has (n+1) variables, then ‗n‘ of these variables can be connected to
the select lines of the multiplexer. The remaining single variable along with constants 1
and 0 is used as the input of the multiplexer. For example, if C is the single variable, then
the inputs of the multiplexers are C, C ‘, 1 and 0. By this method any logical expression can
be implemented. In general, a Boolean expression of (n+1) variables can be implemented
using a multiplexer with 2n inputs.
1. Implement the following boolean function using 4: 1 multiplexer,
F (A, B, C) = ∑m (1, 3, 5, 6).
Solution:
Variables, n= 3 (A, B, C)
Select lines= n-1 = 2 (S1, S0)
2n-1 to MUX i.e., 22 to 1 = 4 to 1 MUX
Input lines= 2n-1 = 22 = 4 (D0, D1, D2, D3)
Implementation table:
Apply variables A and B to the select lines. The procedures for implementing the function
are:
• List the input of the multiplexer
• List under them all the minterms in two rows as shown below.
The first half of the minterms is associated with A‘ and the second half with A. The given
function is implemented by circling the minterms of the function and applying the
following rules to find the values for the inputs of the multiplexer.
1. If both the minterms in the column are not circled, apply 0 to the corresponding
input.
2. If both the minterms in the column are circled, apply 1 to the corresponding input.
3. If the bottom minterm is circled and the top is not circled, apply C to the input.
4. If the top minterm is circled and the bottom is not circled, apply C‘ to the input.

Multiplexer Implementation:

2. 2. F (x, y, z) = ∑m (1, 2, 6, 7)
Solution:
Implementation table
Multiplexer Implementation:

3. 3. F ( A, B, C) = ∑m (1, 2, 4, 5)
Solution:
Variables, n= 3 (A, B, C)
Select lines= n-1 = 2 (S1, S0)
2 n-1 to MUX i.e., 22 to 1 = 4 to 1 MUX
Input lines= 2n-1 = 22 = 4 (D0, D1, D2, D3)
Implementation table:

Multiplexer Implementation:

4. F ( P, Q, R, S)= ∑m (0, 1, 3, 4, 8, 9, 15)

Solution:
Variables, n= 4 (P, Q, R, S)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

Implementation:

5. Implement the Boolean function using 8: 1 and also using 4:1 multiplexer
F (A, B, C, D) = ∑m (0, 1, 2, 4, 6, 9, 12, 14)
Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:
Implementation (Using 8: 1 MUX):

Using 4: 1 MUX:

6. F (A, B, C, D) = ∑m (1, 3, 4, 11, 12, 13, 14, 15)

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2 n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:
Multiplexer Implementation

7. Implement the Boolean function using 8: 1 multiplexer.

F (A, B, C, D) = AB’D + A’C’D + B’CD’ + AC’D.
Solution:
Convert into standard SOP form,
= AB‘D (C‘+C) + A‘C‘D (B‘+B) + B‘CD‘ (A‘+A) + AC‘D (B‘+B)
= AB‘C‘D + AB‘CD+ A‘B‘C‘D + A‘BC‘D +A‘B‘CD‘ + AB‘CD‘ +AB‘C‘D+ ABC‘D
= AB‘C‘D + AB‘CD+ A‘B‘C‘D + A‘BC‘D +A‘B‘CD‘ + AB‘CD‘+ ABC‘D
= m9+ m11+ m1+ m5+ m2+ m10+ m13
= ∑m (1, 2, 5, 9, 10, 11, 13).
Implementation Table:
Multiplexer Implementation:

8. Implement the Boolean function using 8: 1 and also using 4:1 multiplexer
F (w, x, y, z) = ∑m (1, 2, 3, 6, 7, 8, 11, 12, 14)
Solution:
Variables, n= 4 (w, x, y, z)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:
Multiplexer Implementation (Using 8:1 MUX):

(Using 4:1 MUX):

9. Implement the Boolean function using 8: 1 multiplexer

F (A, B, C, D) = ∏m (0, 3, 5, 8, 9, 10, 12, 14)
Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

Multiplexer Implementation:

10. Implement the Boolean function using 8: 1 multiplexer

F (A, B, C, D) = ∑m (0, 2, 6, 10, 11, 12, 13) + d (3, 8, 14)
Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2 n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation Table:
Multiplexer Implementation:

11. An 8×1 multiplexer has inputs A, B and C connected to the selection inputs S2, S1, and
S0 respectively. The data inputs I0 to I7 are as follows I1=I2=I7= 0; I3=I5= 1; I0=I4= D and
I6= D'. Determine the Boolean function that the multiplexer implements.
Multiplexer Implementation:

Implementation table:
I0 I1 I2 I3 I4 I5 I6 I7
̅
𝑫 0 2 4 6 8 10 12 14
D 1 3 5 7 9 11 13 15
D 0 0 1 D 1 ̅
𝑫 0

F (A, B, C, D) = ∑m (1, 6, 7, 9, 10, 11, 12)

2.11 DEMULTIPLEXER:
Demultiplex means one into many. Demultiplexing is the process of taking information
from one input and transmitting the same over one of several outputs.
A demultiplexer is a combinational logic circuit that receives information on a single
input and transmits the same information over one of several (2n) output lines.

Fig. 2.14
The block diagram of a demultiplexer which is opposite to a multiplexer in its
operation is shown above. The circuit has one input signal, ‗n‘ select signals and 2 n
output signals. The select inputs determine to which output the data input will be
connected. As the serial data is changed to parallel data, i.e., the input caused to appear
on one of the n output lines, the demultiplexer is also called a ―data distributer or a
―serial-to-parallel converter.
1-to-4 Demultiplexer:
A 1-to-4 demultiplexer has a single input, Din, four outputs (Y0 to Y3) and two select
inputs (S1 and S0).

The input variable Din has a path to all four outputs, but the input information is
directed to only one of the output lines.
The truth table of the 1-to-4 demultiplexer is shown below.
From the truth table, it is clear that the data input, Din is connected to the output Y0,
when S1= 0 and S0= 0 and the data input is connected to output Y1 when S1= 0 and S0=
1. Similarly, the data input is connected to output Y2 and Y3 when S1= 1 and S0= 0 and
when S1= 1 and S0= 1, respectively. Also, from the truth table, the expression for
outputs can be written as follows,
Y0= S1’S0’Din
Y1= S1’S0Din
Y2= S1S0’Din
Y3= S1S0Din

Now, using the above expressions, a 1-to-4 demultiplexer can be implemented using
four 3-input AND gates and two NOT gates. Here, the input data line Din, is connected
to all the AND gates. The two select lines S1, S0 enable only one gate at a time and the
data that appears on the input line passes through the selected gate to the associated
output line.
1-to-8 Demultiplexer:
A 1-to-8 demultiplexer has a single input, Din, eight outputs (Y0 to Y7) and three select
inputs (S2, S1 and S0). It distributes one input line to eight output lines based on the
select inputs. The truth table of 1-to-8 demultiplexer is shown below.

From the above truth table, it is clear that the data input is connected with one of the
eight outputs based on the select inputs. Now from this truth table, the expression for
eight outputs can be written as follows:
Y0= S2‘S1‘S0‘Din Y4= S2 S1‘S0‘Din
Y1= S2‘S1‘S0Din Y5= S2 S1‘S0Din
Y2= S2‘S1S0‘Din Y6= S2 S1S0‘Din
Y3= S2‘S1S0Din Y7= S2S1S0Din
Now using the above expressions, the logic diagram of a 1-to-8 demultiplexer can be
drawn as shown below. Here, the single data line, Din is connected to all the eight AND
gates, but only one of the eight AND gates will be enabled by the select input lines. For
example, if S2S1S0= 000, then only AND gate-0 will be enabled and thereby the data
input, Din will appear at Y0. Similarly, the different combinations of the select inputs,
the input Din will appear at the respective output.
1. Design 1:8 demultiplexer using two 1:4 DEMUX.
 2. Implement full subtractor using demultiplexer.

2.12 DECODERS:

A decoder is a combinational circuit that converts binary information from ‗n‘ input lines
to a maximum of ‗2n‘ unique output lines. The general structure of decoder circuit is –

Fig. 2.15
The encoded information is presented as ‗n‘ inputs producing ‗2n‘ possible outputs. The
2n output values are from 0 through 2n-1. A decoder is provided with enable inputs to
activate decoded output based on data inputs. When any one enable input is unasserted,
all outputs of decoder are disabled.
Binary Decoder (2 to 4 decoder):
A binary decoder has ‗n‘ bit binary input and a one activated output out of 2n outputs. A
binary decoder is used when it is necessary to activate exactly one of 2n outputs based on
an n-bit input value.

2-to-4 Line decoder

Here the 2 inputs are decoded into 4 outputs, each output representing one of the
minterms of the two input variables.

As shown in the truth table, if enable input is 1 (EN= 1) only one of the outputs (Y 0 – Y3),
is active for a given input.
The output Y0 is active, ie., Y0= 1 when inputs A= B= 0,
Y1 is active when inputs, A= 0 and B= 1,
Y2 is active, when input A= 1 and B= 0,
Y3 is active, when inputs A= B= 1.
3-to-8 Line Decoder:
A 3-to-8 line decoder has three inputs (A, B, C) and eight outputs (Y0- Y7). Based on the 3
inputs one of the eight outputs is selected.
The three inputs are decoded into eight outputs, each output representing one of the
minterms of the 3-input variables. This decoder is used for binary-to-octal conversion.
The input variables may represent a binary number and the outputs will represent the
eight digits in the octal number system. The output variables are mutually exclusive
because only one output can be equal to 1 at any one time. The output line whose value is
equal to 1 represents the minterm equivalent of the binary number presently available in
the input lines.
Applications of decoders:
1. Decoders are used in counter system.
2. They are used in analog to digital converter.
3. Decoder outputs can be used to drive a display system.

Boolean Function Implementation using Decoders:

➢ Implement a full adder circuit with a decoder and two OR gates.
The sum and carry expression of the full adder is given:
S (x,y,z) = Σ ( 1,2,4,7)
C (x,y,z) = Σ ( 3,5,6,7)
1. Logical Expression for SUM is :
A’B’C-IN + A’BC-IN’ + AB’C-IN’ + ABC-IN = C-IN (A’B’ + AB) + C-IN’ (A’B + AB’) = C-IN XOR
(A XOR B) = (1,2,4,7)
2. Logical Expression for C-OUT is :
A’ B C-IN + A B’ C-IN + A B C-IN’ + A B C-IN = A B + B C-IN + A C-IN = (3,5,6,7)
The truth table of a full adder is shown in Table1

i. The A, B and Cin inputs are applied to 3:8 decoder as an input.

ii. The outputs of decoder m1, m2, m4 and m7 are applied to OR gate as shown in
figure to obtain the sum output.
iii. Similarly, outputs m3, m5, m6 and m7 are applied to another OR gate to obtain the
carry output.
iv. Implementation of full adder is shown in figure1.

2.13 ENCODERS:

An encoder is a digital circuit that performs the inverse operation of a decoder. Hence, the
opposite of the decoding process is called encoding. An encoder is a combinational circuit
that converts binary information from 2n input lines to a maximum of ‗n‘ unique output
lines. The general structure of encoder circuit is –

Fig. 2.16
It has 2n input lines, only one which 1 is active at any time and ‗n‘ output lines. It encodes
one of the active inputs to a coded binary output with ‗n‘ bits. In an encoder, the number
of outputs is less than the number of inputs.
Octal-to-Binary Encoder:
It has eight inputs (one for each of the octal digits) and the three outputs that generate
the corresponding binary number. It is assumed that only one input has a value of 1 at any
given time.

The encoder can be implemented with OR gates whose inputs are determined directly
from the truth table. Output z is equal to 1, when the input octal digit is 1 or 3 or 5 or 7.
Output y is 1 for octal digits 2, 3, 6, or 7 and the output is 1 for digits 4, 5, 6 or 7. These
conditions can be expressed by the following output Boolean functions:
z= D1+ D3+ D5+ D7
y= D2+ D3+ D6+ D7
x= D4+ D5+ D6+ D7
The encoder can be implemented with three OR gates. The encoder defined in the below
table, has the limitation that only one input can be active at any given time. If two inputs
are active simultaneously, the output produces an undefined combination.
For eg., if D3 and D6 are 1 simultaneously, the output of the encoder may be 111. This does
not represent either D6 or D3. To resolve this problem, encoder circuits must establish an
input priority to ensure that only one input is encoded. If we establish a higher priority
for inputs with higher subscript numbers and if D3 and D6 are 1 at the same time, the
output will be 110 because D6 has higher priority than D3.

Another problem in the octal-to-binary encoder is that an output with all 0‘s is generated
when all the inputs are 0; this output is same as when D0 is equal to 1. The discrepancy
can be resolved by providing one more output to indicate that atleast one input is equal
to 1.
2.14 Priority Encoder:

A priority encoder is an encoder circuit that includes the priority function. In priority
encoder, if two or more inputs are equal to 1 at the same time, the input having the highest
priority will take precedence.
In addition to the two outputs x and y, the circuit has a third output, V (valid bit indicator).
It is set to 1 when one or more inputs are equal to 1. If all inputs are 0, there is no valid
input and V is equal to 0.
The higher the subscript number, higher the priority of the input. Input D3, has the highest
priority. So, regardless of the values of the other inputs, when D3 is 1, the output for xy is
11.
D2 has the next priority level. The output is 10, if D2= 1 provided D3= 0. The output for D1
is generated only if higher priority inputs are 0, and so on down the priority levels.
Truth table:

Although the above table has only five rows, when each don‘t care condition is replaced
first by 0 and then by 1, we obtain all 16 possible input combinations. For example, the
third row in the table with X100 represents minterms 0100 and 1100. The don‘t care
condition is replaced by 0 and 1 as shown in the table below.

Modified Truth table:

K-map Simplification:

The priority encoder is implemented according to the above Boolean functions.

Fig. 4-Input Priority Encoder