UNIT I

COMBINATIONAL LOGIC
Combinational Circuits – Karnaugh Map - Analysis and Design Procedures – Binary Adder –
Subtractor – Decimal Adder - Magnitude Comparator – Decoder – Encoder – Multiplexers -
UNIT II COMBINATIONAL
Demultiplexers CIRCUITS:
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.

Sequential logic circuit comprises both logic gates and the state of storage
elements such as flip-flops. As a consequence, the output of a sequential circuit depends
not only on present value of inputs but also on the past state of inputs.
In the previous chapter, we have discussed binary numbers, codes, Boolean
algebra and simplification of Boolean function and logic gates. In this chapter,
formulation and analysis of various systematic designs of combinational circuits will be
discussed.

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.

Block diagram of a combinational logic circuit

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.

ARITHMETIC CIRCUITS – BASIC BUILDING BLOCKS:

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.

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.
 Block schematic of half-adder
The truth table of a half-adder, showing all possible input combinations and
the corresponding outputs are shown below.

Inputs Outputs
A B Carry (C) Sum (S)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Truth table of half-adder

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,

Logic Implementation of Half-adder

Full-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,

Block schematic of full-adder

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,

Truth Table:

Inputs Outputs
A B Cin Sum (S) Carry (Cout)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

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,

Implementation of full-adder in Sum of Products

The logic diagram of the full adder can also be implemented with two half-
adders 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

Sum = Cin † (A † B) [x†y = x‘y+ xy‘]

= Cin † (A‘B+AB‘)
= C‘in (A‘B+AB‘) + Cin (A‘B+AB‘)‘ [(x‘y+xy‘)‘= (xy+x‘y‘)]
= C‘in (A‘B+AB‘) + Cin (AB+A‘B‘)
= A‘BC‘in + AB‘C‘in + ABCin + A‘B‘Cin .
and the carry output is,
Carry, Cout = AB+ Cin (A’B+AB’)
= AB+ A‘BCin+ AB‘Cin
= AB (Cin+1) + A‘BCin+ AB‘Cin [Cin+1= 1]
= ABCin+ AB+ A‘BCin+ AB‘Cin
= AB+ ACin (B+B‘) + A‘BCin
= AB+ ACin+ A‘BCin
= AB (Cin+1) + ACin+ A‘BCin [Cin+1= 1]
= ABCin+ AB+ ACin+ A‘BCin
= AB+ ACin+ BCin (A +A‘)
= AB+ ACin+ BCin.

Implementation of full adder with two half-adders and an OR gate

Half -Subtractor:
A half-subtractor is a combinational circuit that can be used to subtract one binary
digit from another to produce a DIFFERENCE output and a BORROW output. The
BORROW output here specifies whether a ‗1‘ has been borrowed to perform the
subtraction.

Block schematic of half-subtractor

The truth table of half-subtractor, showing all possible input combinations

and the corresponding outputs are shown below.
Input Output
A B Difference (D) Borrow (Bout)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
K-map simplification for half subtractor:

The Boolean expressions for the DIFFERENCE and BORROW outputs are given
by the equations,
Difference, D = A’B+ AB’= A † B
Borrow, Bout = A’ . B

The first one representing the DIFFERENCE (D)output is that of an exclusive-OR

gate, the expression for the BORROW output (Bout) is that of an AND gate with input A
complemented before it is fed to the gate.
The logic diagram of the half adder is,

Logic Implementation of Half-Subtractor

Comparing a half-subtractor with a half-adder, we find that the expressions for

the SUM and DIFFERENCE outputs are just the same. The expression for BORROW in
the case of the half-subtractor is also similar to what we have for CARRY in the case of
the half-adder. If the input A, ie., the minuend is complemented, an AND gate can be
used to implement the BORROW output.
Full Subtractor:
A full subtractor performs subtraction operation on two bits, a minuend and a
subtrahend, and also takes into consideration whether a ‗1‘ has already been borrowed
by the previous adjacent lower minuend bit or not.
As a result, there are three bits to be handled at the input of a full subtractor,
namely the two bits to be subtracted and a borrow bit designated as B in. There are two
outputs, namely the DIFFERENCE output D and the BORROW output Bo. The
BORROW output bit tells whether the minuend bit needs to borrow a ‗1‘ from the next
possible higher minuend bit.
Block schematic of full-adder

The truth table for full-subtractor is,

Inputs Outputs
A B Bin Difference(D) Borrow(Bout)
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1

K-map simplification for full-subtractor:

The Boolean expressions for the DIFFERENCE and BORROW outputs are given
by the equations,
Difference, D = A’B’Bin+ A’BB’in + AB’B’in + ABBin
Borrow, Bout = A’B+ A’Cin + BBin .
The logic diagram for the above functions is shown as,
 Implementation of full-adder in Sum of Products

The logic diagram of the full-subtractor can also be implemented with two half-
subtractors and one OR gate. The difference,D output from the second half subtractor
is the exclusive-OR of Bin and the output of the first half-subtractor, giving
Difference,D= Bin † (A † B) [x † y = x‘y+ xy‘]
= Bin † (A‘B+AB‘)
= B‘in (A‘B+AB‘) + Bin (A‘B+AB‘)‘ [(x‘y+xy‘)‘= (xy+x‘y‘)]
= B‘in (A‘B+AB‘) + Bin (AB+A‘B‘)
= A‘BB‘in + AB‘B‘in + ABBin + A‘B‘Bin
. and the borrow output is,

Borrow, Bout = A’B+ Bin (A’B+AB’)’ [(x‘y+xy‘)‘= (xy+x‘y‘)]

= A‘B+ Bin (AB+A‘B‘)
= A‘B+ ABBin+ A‘B‘Bin
= A‘B (Bin+1) + ABBin+ A‘B‘Bin [Cin+1= 1]
= A‘BBin+ A‘B+ ABBin+ A‘B‘Bin
= A‘B+ BBin (A+A‘) + A‘B‘Bin [A+A‘= 1]
= A‘B+ BBin+ A‘B‘Bin
= A‘B (Bin+1) + BBin+ A‘B‘Bin [Cin+1= 1]
= A‘BBin+ A‘B+ BBin+ A‘B‘Bin
= A‘B+ BBin+ A‘Bin (B +B‘)
= A‘B+ BBin+ A‘Bin.

Therefore,
we can implement full-subtractor using two half-subtractors and OR gate as,

Implementation of full-subtractor with two half-subtractors and an OR gate

Binary Adder (Parallel Adder):
The 4-bit binary adder using full adder circuits is capable of adding two 4-
bit numbers resulting in a 4-bit sum and a carry output as shown in figure below.

4-bit binary parallel Adder

Since all the bits of augend and addend are fed into the adder circuits
simultaneously and the additions in each position are taking place at the same time, this
circuit is known as parallel adder.

Let the 4-bit words to be added be represented by,

A3A2A1A0= 1111 and B3B2B1B0= 0011.

The bits are added with full adders, starting from the least significant position, to
form the sum it and carry bit. The input carry C0 in the least significant position must be
0. The carry output of the lower order stage is connected to the carry input of the next
higher order stage. Hence this type of adder is called ripple-carry adder.
In the least significant stage, A0, B0 and C0 (which is 0) are added resulting in
sum S0 and carry C1. This carry C1 becomes the carry input to the second stage.
Similarly in the second stage, A1, B1 and C1 are added resulting in sum S1 and carry C2,
in the third stage, A2, B2 and C2 are added resulting in sum S2 and carry C3, in the third
stage, A3, B3 and C3 are added resulting in sum S3 and C4, which is the output carry.
Thus the circuit results in a sum (S3S2S1S0) and a carry output (Cout).
Though the parallel binary adder is said to generate its output immediately after
the inputs are applied, its speed of operation is limited by the carry propagation delay
through all stages. However, there are several methods to reduce this delay.
One of the methods of speeding up this process is look-ahead carry addition
which eliminates the ripple-carry delay.

Carry Propagation–Look-Ahead Carry Generator:

In Parallel adder, all the bits of the augend and the addend are available for
computation at the same time. The carry output of each full-adder stage is connected to
the carry input of the next high-order stage. Since each bit of the sum output depends
on the value of the input carry, time delay occurs in the addition process. This time
delay is called as carry propagation delay.
For example, addition of two numbers (0011+ 0101) gives the result as 1000.
Addition of the LSB position produces a carry into the second position. This carry when
added to the bits of the second position, produces a carry into the third position. This
carry when added to bits of the third position, produces a carry into the last position.
The sum bit generated in the last position (MSB) depends on the carry that was
generated by the addition in the previous position. i.e., the adder will not produce
correct result until LSB carry has propagated through the intermediate full-adders. This
represents a time delay that depends on the propagation delay produced in an each
full-adder. For example, if each full adder is considered to have a propagation delay of
30nsec, then S3 will not react its correct value until 90 nsec after LSB is generated.
Therefore total time required to perform addition is 90+ 30 = 120nsec.

4-bit Parallel Adder

The method of speeding up this process by eliminating inter stage carry delay is
called look ahead-carry addition. This method utilizes logic gates to look at the lower
order bits of the augend and addend to see if a higher-order carry is to be generated. It
uses two functions: carry generate and carry propagate.
 Full-Adder circuit

Consider the circuit of the full-adder shown above. Here we define

two functions: carry generate (Gi) and carry propagate (Pi) as,
Carry generate, Gi = Ai †Bi
Carry propagate, Pi = Ai † Bi
the output sum and carry can be expressed as,
Si = Pi † Ci
Ci+1 = Gi † PiCi
Gi (carry generate), it produces a carry 1 when both Ai and Bi are 1, regardless of
the input carry Ci.
Pi (carry propagate) because it is the term associated with the propagation of the
carry from Ci to Ci+1.
The Boolean functions for the carry outputs of each stage and substitute for each
Ci its value from the previous equation:
C0= input carry
C1= G0 + P0C0
C2= G1 + P1C1 = G1 + P1 (G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3= G2 + P2C2 = G2 + P2 (G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0
 Since the Boolean function for each output carry is expressed in sum of products,
each function can be implemented with one level of AND gates followed by an OR gate.
The three Boolean functions for C1, C2 and C3 are implemented in the carry look-ahead
generator as shown below. Note that C3 does not have to wait for C2 and C1 to
propagate; in fact C3 is propagated at the same time as C1 and C2.
Logic diagram of Carry Look-ahead Generator

Using a Look-ahead Generator we can easily construct a 4-bit parallel adder with
a Look-ahead carry scheme. Each sum output requires two exclusive-OR gates. The
output of the first exclusive-OR gate generates the Pi variable, and the AND gate
generates the Gi variable. The carries are propagated through the carry look-ahead
generator and applied as inputs to the second exclusive-OR gate. All output carries are
generated after a delay through two levels of gates. Thus, outputs S1 through S3 have
equal propagation delay times.
 4-Bit Adder with Carry Look-ahead

Binary Subtractor (Parallel Subtractor):

The subtraction of unsigned binary numbers can be done most conveniently by
means of complements. The subtraction A-B can be done by taking the 2‘s complement
of B and adding it to A. The 2‘s complement can be obtained by taking the 1‘s
complement and adding 1 to the least significant pair of bits. The 1‘s complement can be
implemented with inverters and a 1 can be added to the sum through the input carry.
 The circuit for subtracting A-B consists of an adder with inverters placed
between each data input B and the corresponding input of the full adder. The input
carry C0 must be equal to 1 when performing subtraction. The operation thus
performed becomes A, plus the 1‘s complement of B, plus1. This is equal to A plus the
2‘s complement of B.

4-bit Parallel Subtractor

Parallel Adder/ Subtractor:

The addition and subtraction operation can be combined into one circuit with
one common binary adder. This is done by including an exclusive-OR gate with each
full adder. A 4-bit adder Subtractor circuit is shown below.

4-Bit Adder Subtractor

The mode input M controls the operation. When M= 0, the circuit is an adder and
when M=1, the circuit becomes a Subtractor. Each exclusive-OR gate receives input M
and one of the inputs of B. When M=0, we have B 0= B. The full adders receive the
value of B, the input carry is 0, and the circuit performs A plus B. When M=1, we have B
1= B‘ and C0=1. The B inputs are all complemented and a 1 is added through the input
carry. The circuit performs the operation A plus the 2‘s complement of B. The exclusive-
OR with output V is for detecting an overflow.

Decimal Adder (BCD Adder):

The digital system handles the decimal number in the form of binary coded
decimal numbers (BCD). A BCD adder is a circuit that adds two BCD bits and produces
a sum digit also in BCD.
Consider the arithmetic addition of two decimal digits in BCD, together with an
input carry from a previous stage. Since each input digit does not exceed 9, the output
sum cannot be greater than 9+ 9+1 = 19; the 1 is the sum being an input carry. The
adder will form the sum in binary and produce a result that ranges from 0 through 19.
These binary numbers are labeled by symbols K, Z8, Z4, Z2, Z1, K is the carry. The
columns under the binary sum list the binary values that appear in the outputs of the 4-
bit binary adder. The output sum of the two decimal digits must be represented in BCD.

Binary Sum BCD Sum

Decimal
K Z8 Z 4 Z2 Z1 C S8 S4 S2 S1
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 2
0 0 0 1 1 0 0 0 1 1 3
0 0 1 0 0 0 0 1 0 0 4
0 0 1 0 1 0 0 1 0 1 5
0 0 1 1 0 0 0 1 1 0 6
0 0 1 1 1 0 0 1 1 1 7
0 1 0 0 0 0 1 0 0 0 8
0 1 0 0 1 0 1 0 0 1 9
 0 1 0 1 0 1 0 0 0 0 10
0 1 0 1 1 1 0 0 0 1 11
0 1 1 0 0 1 0 0 1 0 12
0 1 1 0 1 1 0 0 1 1 13
0 1 1 1 0 1 0 1 0 0 14
0 1 1 1 1 1 0 1 0 1 15
1 0 0 0 0 1 0 1 1 0 16
1 0 0 0 1 1 0 1 1 1 17
1 0 0 1 0 1 1 0 0 0 18
1 0 0 1 1 1 1 0 0 1 19

In examining the contents of the table, it is apparent that when the binary sum is
equal to or less than 1001, the corresponding BCD number is identical, and therefore no
conversion is needed. When the binary sum is greater than 9 (1001), we obtain a non-
valid BCD representation. The addition of binary 6 (0110) to the binary sum converts it
to the correct BCD representation and also produces an output carry as required.
The logic circuit to detect sum greater than 9 can be determined by simplifying
the boolean expression of the given truth table.
To implement BCD adder we require:
x 4-bit binary adder for initial addition
x Logic circuit to detect sum greater than 9 and
x One more 4-bit adder to add 01102 in the sum if the sum is greater than 9 or
carry is 1.

The two decimal digits, together with the input carry, are first added in the top4-
bit binary adder to provide the binary sum. When the output carry is equal to zero,
nothing is added to the binary sum. When it is equal to one, binary 0110 is added to
the binary sum through the bottom 4-bit adder. The output carry generated from the
bottom adder can be ignored, since it supplies information already available at the
output carry terminal. The output carry from one stage must be connected to the
input carry of the next higher-order stage.

Block diagram of BCD adder

Binary Multiplier:
Multiplication of binary numbers is performed in the same way as in decimal
numbers. The multiplicand is multiplied by each bit of the multiplier starting from the
least significant bit. Each such multiplication forms a partial product. Such partial
products are shifted one position to the left. The final product is obtained from the sum
of partial products.
Consider the multiplication of two 2-bit numbers. The multiplicand bits are B1
and B0, the multiplier bits are A1 and A0, and the product is C3, C2, C1 and C0. The first
partial product is formed by multiplying A0 by B1B0. The multiplication of two bits such
as A0 and B0 produces a 1 if both bits are 1; otherwise, it produces a 0. This is identical
to an AND operation. Therefore the partial product can be implemented with AND
gates as shown in the diagram below.

The second partial product is formed by multiplying A1 by B1B0 and shifted one
position to the left. The two partial products are added with two half adder (HA)
circuits.

2-bit by 2-bit Binary multiplier

Usually there are more bits in the partial products and it is necessary to use full
adders to produce the sum of the partial products. The least significant bit of the
product does not have to go through an adder since it is formed by the output of the
first AND gate.
A combinational circuit binary multiplier with more bits can be constructed in a
similar fashion. A bit of the multiplier is ANDed with each bit of the multiplicand in as
many levels as there are bits in the multiplier. The binary output in each level of AND
gates are added with the partial product of the previous level to form a new partial
product. The last level produces the product. For J multiplier bits and K multiplicand
bits we need (J x K) AND gates and (J-1) k-bit adders to produce a product of J+K bits.
Consider a multiplier circuit that multiplies a binary number of four bits by a
number of three bits. Let the multiplicand be represented by B3, B2, B1, B0 and the
multiplier by A2, A1, and A0. Since K= 4 and J= 3, we need 12 AND gates and two 4-bit
adders to produce a product of seven bits. The logic diagram of the multiplier is shown
below.
 4-bit by 3-bit Binary multiplier

PARITY GENERATOR/ CHECKER:

A Parity is a very useful tool in information processing in digital computers to
indicate any presence of error in bit information. External noise and loss of signal
strength causes loss of data bit information while transporting data from one device to
other device, located inside the computer or externally. To indicate any occurrence of
error, an extra bit is included with the message according to the total number of 1s in a
set of data, which is called parity.
If the extra bit is considered 0 if the total number of 1s is even and 1 for odd
quantities of 1s in a set of data, then it is called even parity. On the other hand, if the
extra bit is 1 for even quantities of 1s and 0 for an odd number of 1s, then it is called odd
parity.
 The message including the parity is transmitted and then checked at the
receiving end for errors. An error is detected if the checked parity does not correspond
with the one transmitted. The circuit that generates the parity bit in the transmitter is
called a parity generator and the circuit that checks the parity in the receiver is called a
parity checker.

Parity Generator:
A parity generator is a combination logic system to generate the parity bit at the
transmitting side. A table illustrates even parity as well as odd parity for a message
consisting of three bits.

3-bit Message Odd Party Even Parity

A B C bit bit
0 0 0 1 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 0 1
Parity generator truth table for even and odd parity

If the message bit combination is designated as A, B, C and Pe, Po are the even
and odd parity respectively, then it is obvious from table that the boolean expressions
of even parity and odd parity are
Pe = A†
B†C) and
Po = (A†B†C)′.

K-map Simplification:

P= A’B’C+ A’BC’+ A’B’C’+ ABC

= A’ (B’C+ BC’) + A (B’C’+ BC)
= A’ (B†C) + A (B†C)’
= A†
B†C)
Logic Diagram:

3-bit even parity generator

Parity Checker:
The message bits with the parity bit are transmitted to their destination, where
they are applied to a parity checker circuit. The circuit that checks the parity at the
receiver side is called the parity checker. The parity checker circuit produces a check bit
and is very similar to the parity generator circuit. If the check bit is 1, then it is assumed
that the received data is incorrect. The check bit will be 0 if the received data is correct.
The table shows the truth table for the even parity checker.

4-Bit Received Parity Error

A B C D Check (PEC)
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
K-map Simplification:

PEC= A’B’ (C’D+ CD’) + A’B (C’D’+ CD) + AB (C’D+ CD’) + AB’ (C’D’+ CD)
= A’B’ (C†D) + A’B (C†D)’ + AB (C†D) + AB’ (C†D)’
= (A’B’+ AB) (C†D) + (A’B+ AB’) (C†D)’
= (A†B)’ (C†D) + (A†B) (C†D)’
= (A†B) † (C†D)

Logic Diagram:

4-bit even parity checker

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 and B are the two numbers being compared.

Block diagram of magnitude comparator

 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.

2-bit Magnitude Comparator:

The truth table of 2-bit comparator is given in table below—
Truth table:

Inputs Outputs
A3 A2 A1 A0 A>B A=B A<B
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0

K-map Simplification:
Logic Diagram:
 2- bit Magnitude Comparator
4-bit Magnitude Comparator:
Let us consider the two binary numbers A and B with four digits each. Write
the coefficient of the numbers in descending order as,
A = A3A2A1A0
B = B3 B2 B1 B0,
Each subscripted letter represents one of the digits in the number. It is observed from
the bit contents of two numbers that A = B when A3 = B3, A2 = B2, A1 = B1 and A0 = B0.
When the numbers are binary they possess the value of either 1 or 0, the equality
relation of each pair can be expressed logically by the equivalence function as
Xi = AiBi + Ai′Bi′ for i = 1, 2, 3, 4.
Or, Xi = (A † B)′. or, Xi ′ = A † B
Or, Xi = (AiBi′ + Ai′Bi)′.
where,
Xi =1 only if the pair of bits in position i are equal (ie., if both are 1 or both are 0).
To satisfy the equality condition of two numbers A and B, it is necessary that all
Xi must be equal to logic 1. This indicates the AND operation of all Xi variables. In other
words, we can write the Boolean expression for two equal 4-bit numbers.
(A = B) = X3X2X1 X0.
The binary variable (A=B) is equal to 1 only if all pairs of digits of the two numbers
are equal.
To determine if A is greater than or less than B, we inspect the relative
magnitudes of pairs of significant bits starting from the most significant bit. If the two
digits of the most significant position are equal, the next significant pair of digits is
compared. The comparison process is continued until a pair of unequal digits is found.
It may be concluded that A>B, if the corresponding digit of A is 1 and B is 0. If the
corresponding digit of A is 0 and B is 1, we conclude that A<B. Therefore, we can derive
the logical expression of such sequential comparison by the following two Boolean
functions,

(A>B) = A3B3′ +X3A2B2′ +X3X2A1B1′ +X3X2X1A0B0′

(A<B) = A3′B3 +X3A2′B2 +X3X2A1′B1 +X3X2X1A0′B0

The symbols (A>B) and (A<B) are binary output variables that are equal to 1 when
A>B or A<B, respectively.
The gate implementation of the three output variables just derived is simpler
than it seems because it involves a certain amount of repetition. The unequal outputs
can use the same gates that are needed to generate the equal output. The logic
diagram of the 4-bit magnitude comparator is shown below,
 4-bit Magnitude Comparator

The four x outputs are generated with exclusive-NOR circuits and applied to
an AND gate to give the binary output variable (A=B). The other two outputs use the
x variables to generate the Boolean functions listed above. This is a multilevel
implementation and has a regular pattern.
CODE CONVERTERS:
A code converter is a logic circuit that changes data presented in one type of
binary code to another code of binary code. The following are some of the most
commonly used code converters:
i. Binary-to-Gray code
ii. Gray-to-Binary code
iii. BCD-to-Excess-3
iv. Excess-3-to-BCD
v. Binary-to-BCD
vi. BCD-to-binary
vii. Gray-to-BCD
viii. BCD-to-Gray
ix. 8 4 -2 -1 to BCD converter

1. Binary to Gray Converters:

The gray code is often used in digital systems because it has the advantage that
only one bit in the numerical representation changes between successive numbers. The
truth table for the binary-to-gray code converter is shown below,

Truth table:
Binary code Gray code
Decimal
B3 B2 B1 B0 G3 G2 G1 G0
0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1
2 0 0 1 0 0 0 1 1
3 0 0 1 1 0 0 1 0
4 0 1 0 0 0 1 1 0
5 0 1 0 1 0 1 1 1
6 0 1 1 0 0 1 0 1
7 0 1 1 1 0 1 0 0
8 1 0 0 0 1 1 0 0
9 1 0 0 1 1 1 0 1
10 1 0 1 0 1 1 1 1
11 1 0 1 1 1 1 1 0
12 1 1 0 0 1 0 1 0
13 1 1 0 1 1 0 1 1
14 1 1 1 0 1 0 0 1
15 1 1 1 1 1 0 0 0
K-map simplification:

Now, the above expressions can be implemented using EX-OR gates as,
Logic Diagram:

2. Gray to Binary Converters:

The truth table for the gray-to-binary code converter is shown below,

Truth table:
Gray code Binary code
G3 G2 G1 G0 B3 B2 B1 B0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 1
1 0 0 0 1 1 1 1
1 0 0 1 1 1 1 0
1 0 1 0 1 1 0 0
1 0 1 1 1 1 0 1
1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 1
1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0
From the truth table, the logic expression for the binary code outputs can be written as,
G3= ∑m (8, 9, 10, 11, 12, 13, 14, 15)
G2= ∑m (4, 5, 6, 7, 8, 9, 10, 11)
G1= ∑m (2, 3, 4, 5, 8, 9, 14, 15)
G0= ∑m (1, 2, 4, 7, 8, 11, 13, 14)
K-map Simplification:

From the above K-map,

B3= G3
B2= G3‘G2+ G3G2‘
B2= G3†G2
B1= G3‘G2‘G1+ G3‘G2G1‘+ G3G2G1+ G3G2‘G1‘
= G3‘ (G2‘G1+ G2G1‘) + G3 (G2G1+ G2‘G1‘)
= G3‘ (G2†G1) + G3 (G2†G1)‘ [x†y = x‘y+ xy‘], [(x†y)‘ = xy+ x‘y‘]
B1= G3† G2†G1
B0= G3‘G2‘ G1‘G0+ G3‘G2‗G1G0‘+ G3G2G1‗G0+ G3G2G1 G0‘+ G3‘G2G1‘G0‘+
G3G2‗G1‘G0‘+ G3‘G2G1G0+ G3G2‗G1 G0.
= G3‘G2‘ (G1‘G0+ G1G0‘) + G3G2 (G1‘G0+ G1G0‘) + G1‘G0‘ (G3‘G2+ G3G2‘) +
G1G0 (G3‘G2+ G3G2‘).
= G3‘G2‘ (G0†G1) + G3G2 (G0†G1) + G1‘G0‘ (G2†G3) +G1G0 (G2†G3).
= G0†G1 (G3‘G2‘ + G3G2) + G2†G3 (G1‘G0‘+G1G0)
= (G0†G1) (G2†G3)‘+ (G2†G3) (G0†G1) [x†y = x‘y+ xy‘]
B0= (G0†G1) † (G2†G3).
Now, the above expressions can be implemented using EX-OR gates as,

Logic diagram of 4-bit gray-to-binary converter

3. BCD –to-Excess-3 Converters:
Excess-3 is a modified form of a BCD number. The excess-3 code can be derived
from the natural BCD code by adding 3 to each coded number.
For example, decimal 12 can be represented in BCD as 0001 0010. Now adding 3 to each
digit we get excess-3 code as 0100 0101 (12 in decimal). With this information the truth
table for BCD to Excess-3 code converter can be determined as,

Truth Table:
BCD code Excess-3 code
Decimal
B3 B2 B1 B0 E3 E2 E1 E0
0 0 0 0 0 0 0 1 1
1 0 0 0 1 0 1 0 0
2 0 0 1 0 0 1 0 1
3 0 0 1 1 0 1 1 0
4 0 1 0 0 0 1 1 1
5 0 1 0 1 1 0 0 0
6 0 1 1 0 1 0 0 1
7 0 1 1 1 1 0 1 0
8 1 0 0 0 1 0 1 1
9 1 0 0 1 1 1 0 0

From the truth table, the logic expression for the Excess-3 code outputs can be
written as,
E3= ∑m (5, 6, 7, 8, 9) + ∑d (10, 11, 12, 13, 14, 15)
E2= ∑m (1, 2, 3, 4, 9) + ∑d (10, 11, 12, 13, 14, 15)
E1= ∑m (0, 3, 4, 7, 8) + ∑d (10, 11, 12, 13, 14, 15)
E0= ∑m (0, 2, 4, 6, 8) + ∑d (10, 11, 12, 13, 14, 15)
K-map Simplification:
Logic Diagram:

4. Excess-3 to BCD

Converter: Truth table:

Excess-3 code BCD code

Decimal
E3 E2 E1 E0 B3 B2 B1 B0
3 0 0 1 1 0 0 0 0
4 0 1 0 0 0 0 0 1
5 0 1 0 1 0 0 1 0
6 0 1 1 0 0 0 1 1
7 0 1 1 1 0 1 0 0
8 1 0 0 0 0 1 0 1
9 1 0 0 1 0 1 1 0
10 1 0 1 0 0 1 1 1
11 1 0 1 1 1 0 0 0
12 1 1 0 0 1 0 0 1
From the truth table, the logic expression for the Excess-3 code outputs can be
written as,
B3= ∑m (11, 12) + ∑d (0, 1, 2, 13, 14, 15)
B2= ∑m (7, 8, 9, 10) + ∑d (0, 1, 2, 13, 14, 15)
B1= ∑m (5, 6, 9, 10) + ∑d (0, 1, 2, 13, 14, 15)
B0= ∑m (4, 6, 8, 10, 12) + ∑d (0, 1, 2, 13, 14, 15)

K-map Simplification:

Now, the above expressions the logic diagram can be implemented as,
Logic Diagram:

5. BCD –to-Binary Converters:

The steps involved in the BCD-to-binary conversion process are as follows:
1. The value of each bit in the BCD number is represented by a binary equivalent
or weight.
2. All the binary weights of the bits that are 1‘s in the BCD are added.
3. The result of this addition is the binary equivalent of the BCD number.
Two-digit decimal values ranging from 00 to 99 can be represented in BCD by two 4-
bit code groups. For example, 1910 is represented as,

The left-most four-bit group represents 10 and right-most four-bit group represents 9.
The binary representation for decimal 19 is 1910 = 110012.
 BCD Code Binary
B4 B3 B2 B1 B0 E D C B A
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 0 1 0
0 0 0 1 1 0 0 0 1 1
0 0 1 0 0 0 0 1 0 0
0 0 1 0 1 0 0 1 0 1
0 0 1 1 0 0 0 1 1 0
0 0 1 1 1 0 0 1 1 1
0 1 0 0 0 0 1 0 0 0
0 1 0 0 1 0 1 0 0 1
1 0 0 0 0 0 1 0 1 0
1 0 0 0 1 0 1 0 1 1
1 0 0 1 0 0 1 1 0 0
1 0 0 1 1 0 1 1 0 1
1 0 1 0 0 0 1 1 1 0
1 0 1 0 1 0 1 1 1 1
1 0 1 1 0 1 0 0 0 0
1 0 1 1 1 1 0 0 0 1
1 1 0 0 0 1 0 0 1 0
1 1 0 0 1 1 0 0 1 1

K-map Simplification:
From the above K-map,

A= B0

B= B1B4‘+ B1’B4
= B1†B4

C= B4’B2 + B2B1’ + B4B2’B1

D= B4’B3 + B4B3’B2’ + B4B3’B1’

E= B4B3 + B4B2B1

Now, from the above expressions the logic diagram can be implemented as,

Logic Diagram:
6. Binary to BCD Converter:
The truth table for binary to BCD converter can be written as,
Truth Table:
Binary Code BCD Code
Decimal
D C B A B4 B3 B2 B1 B0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 1
2 0 0 1 0 0 0 0 1 0
3 0 0 1 1 0 0 0 1 1
4 0 1 0 0 0 0 1 0 0
5 0 1 0 1 0 0 1 0 1
6 0 1 1 0 0 0 1 1 0
7 0 1 1 1 0 0 1 1 1
8 1 0 0 0 0 1 0 0 0
9 1 0 0 1 0 1 0 0 1
10 1 0 1 0 1 0 0 0 0
11 1 0 1 1 1 0 0 0 1
12 1 1 0 0 1 0 0 1 0
13 1 1 0 1 1 0 0 1 1
14 1 1 1 0 1 0 1 0 0
15 1 1 1 1 1 0 1 0 1

From the truth table, the logic expression for the BCD code outputs can be written as,
B0= ∑m (1, 3, 5, 7, 9, 11, 13, 15)
B1= ∑m (2, 3, 6, 7, 12, 13)
B2= ∑m (4, 5, 6, 7, 14, 15)
B3= ∑m (8, 9)
B4= ∑m (10, 11, 12, 13, 14, 15)

K-map Simplification:
From the above K-map, the logical expression can be obtained
as, B0= A
B1= DCB’+ D’B
B2= D’C+ CB
B3= DC’B’
B4= DC+ DB
Now, from the above expressions the logic diagram can be implemented as,

Logic Diagram:
7. Gray to BCD Converter:
The truth table for gray to BCD converter can be written as,

Truth Table:

Gray Code BCD Code

G3 G2 G1 G0 B4 B3 B2 B1 B0
0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 1
0 0 1 1 0 0 0 1 0
0 0 1 0 0 0 0 1 1
0 1 1 0 0 0 1 0 0
0 1 1 1 0 0 1 0 1
0 1 0 1 0 0 1 1 0
0 1 0 0 0 0 1 1 1
1 1 0 0 0 1 0 0 0
 1 1 0 1 0 1 0 0 1
1 1 1 1 1 0 0 0 0
1 1 1 0 1 0 0 0 1
1 0 1 0 1 0 0 1 0
1 0 1 1 1 0 0 1 1
1 0 0 1 1 0 1 0 0
1 0 0 0 1 0 1 0 1

K-map Simplification:
From the above K-map, the logical expression can be obtained as,
B0= (G0†G1) † (G2†G3)
B1= G’2G1+ G’3G2G’1
B2= G’3G2+ G3G’2G’1
B3= G3G2G’1
B4= G3G’2+ G3G1
Now, from the above expressions the logic diagram can be implemented as,

Logic Diagram:
8. BCD to Gray Converter:
The truth table for gray to BCD converter can be written as,
Truth table:
BCD Code (8421) Gray code
B3 B2 B1 B0 G3 G2 G1 G0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
 0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1

K-map Simplification:

Now, from the above expressions the logic diagram can be implemented as,

Logic Diagram:
9. 8 4 -2 -1 to BCD Converter:
The truth table for 8 4 -2 -1 to BCD converter can be written as,

Truth Table:
Gray Code BCD Code
D C B A B4 B3 B2 B1 B0
0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1
0 1 1 0 0 0 0 1 0
0 1 0 1 0 0 0 1 1
0 1 0 0 0 0 1 0 0
1 0 1 1 0 0 1 0 1
1 0 1 0 0 0 1 1 0
1 0 0 1 0 0 1 1 1
1 0 0 0 0 1 0 0 0
1 1 1 1 0 1 0 0 1
1 1 1 0 1 0 0 0 0
1 1 0 1 1 0 0 0 1
1 1 0 0 1 0 0 1 0
K-map Simplification:

From the above K-map, the logical expression can be obtained as,
B0 = A
B1= A’B’CD+ (A†B) (C’+D’)
B2= D’CB’A’+ C’ (A+B)
B3= D (ABC+ A’B’C’)
B4= CD ( A’+B’)

Logic Diagram:
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 –

General structure of decoder

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 2 n
outputs. A binary decoder is used when it is necessary to activate exactly one of 2 n
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.

Inputs Outputs
Enable A B Y3 Y2 Y1 Y0
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

As shown in the truth table, if enable input is 1 (EN= 1) only one of the outputs
(Y0 – 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.

Inputs Outputs
A B C Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1
 3-to-8 line decoder

BCD to 7-Segment Display Decoder:

A seven-segment display is normally used for displaying any one of the decimal
digits, 0 through 9. A BCD-to-seven segment decoder accepts a decimal digit in BCD
and generates the corresponding seven-segment code.
 Each segment is made up of a material that emits light when current is passed
through it. The segments activated during each digit display are tabulated as—

Digit Display Segments Activated

0 a, b, c, d, e, f

1 b, c

2 a, b, d, e, g

3 a, b, c, d, g

4 b, c, f, g

5 a, c, d, f, g
 6 a, c, d, e, f, g

7 a, b, c

8 a, b, c, d, e, f, g

9 a, b, c, d, f, g

Truth table:

BCD code 7-Segment code

Digit A B C D a b c d e f g
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1
3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1
5 0 1 0 1 1 0 1 1 0 1 1
6 0 1 1 0 1 0 1 1 1 1 1
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1
9 1 0 0 1 1 1 1 1 0 1 1
K-map Simplification:
Logic Diagram:
 BCD to 7-segment display decoder

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.
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 –

General structure of Encoder

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.

Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 A B C
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1
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.

Octal-to-Binary Encoder

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.

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 D 3 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:

Inputs Outputs
D0 D1 D2 D3 x y V
0 0 0 0 x x 0
1 0 0 0 0 0 1
x 1 0 0 0 1 1
x x 1 0 1 0 1
x x x 1 1 1 1
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:

Inputs Outputs
D0 D1 D2 D3 x y V
0 0 0 0 x x 0
1 0 0 0 0 0 1
0 1 0 0
0 1 1
1 1 0 0
0 0 1 0
0 1 1 0
1 0 1
1 0 1 0
1 1 1 0
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
K-map Simplification:

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

4- Input Priority Encoder

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 2 n input lines
and n selection lines whose bit combinations determine which input is selected. The
multiplexer is often labeled 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.

Block diagram of Multiplexer

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.

Logic diagram

The multiplexer acts like an electronic switch that selects one of the two sources.
Truth table:
S Y
0 I0
1 I1
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.

4-to-1-Line Multiplexer

Function table:

S1 S0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3

To demonstrate the circuit operation, consider the case when S 1S0= 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 atleast one input equal to 0, which
makes their outputs equal to 0. The OR output is now equal to the value of I 2, providing
a path from the selected input to the output.
 The data output is equal to I0 only if S1= 0 and S0= 0; Y= I0S1‘S0‘.
The data output is equal to I1 only if S1= 0 and S0= 1; Y= I1S1‘S0.
The data output is equal to I2 only if S1= 1 and S0= 0; Y= I2S1S0‘.
The data output is equal to I3 only if S1= 1 and S0= 1; Y= I3S1S0.
When these terms are ORed, the total expression for the data output is,
Y= I0S1’S0’+ I1S1’S0 +I2S1S0’+ I3S1S0.
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:
 i. List the input of the multiplexer
ii. 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. F (x, y, z) = ∑m (1, 2, 6, 7)
Solution:
Implementation table:

Multiplexer Implementation:

3. F ( A, B, C) = ∑m (1, 2, 4, 5)
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:
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:
Multiplexer 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:
Multiplexer 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)
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:

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

F (A, B, C, D) = A’BD’ + ACD + B’CD + A’C’D.
Solution:
Convert into standard SOP form,
= A‘BD‘ (C‘+C) + ACD (B‘+B) + B‘CD (A‘+A) + A‘C‘D (B‘+B)
= A‘BC‘D‘ + A‘BCD‘+ AB‘CD + ABCD +A‘B‘CD + AB‘CD +A‘B‘C‘D+ A‘BC‘D
 = A‘BC‘D‘ + A‘BCD‘+ AB‘CD + ABCD +A‘B‘CD +A‘B‘C‘D+ A‘BC‘D
= m4+ m6+ m11+ m15+ m3+ m1+ m5
= ∑m (1, 3, 4, 5, 6, 11, 15)

Implementation table:

Multiplexer Implementation:

8. 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:

9. 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):

10. 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:

11. 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)
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:

12. 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:

F (A, B, C, D) = ∑m (3, 5, 6, 8, 11, 12, 13).

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.

Block diagram of demultiplexer

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 2n
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).

Logic Symbol

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.

Enable S1 S0 Din Y0 Y1 Y2 Y3
0 x x x 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 1 0 0 0 0 0
1 0 1 1 0 1 0 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 1

Truth table of 1-to-4 demultiplexer

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

Logic diagram of 1-to-4 demultiplexer

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.

Din S2 S1 S0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
0 x x x 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 0 0 1 0 0
 1 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1 0 0 0 0
1 1 0 1 0 0 1 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
Truth table of 1-to-8 demultiplexer
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.
 Logic diagram of 1-to-8 demultiplexer
1. Design 1:8 demultiplexer using two 1:4 DEMUX.
2. Implement full subtractor using demultiplexer.

Inputs Outputs
A B Bin Difference(D) Borrow(Bout)
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1