lOMoARcPSD|45714441

CS3351 DPCO Unit 1 - Notes

computer science and engineering (Anna University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)
 lOMoARcPSD|45714441

UNIT-I
COMBINATIONAL LOGIC
Combinational circuits-KMap-Analysis and Design Procedures-Binary Adder-Binary
Adder-Decimal Adder- Magnitude comparator-Decoder-Encoder-Multiplexers-
Demultiplexers

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.

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Problems:
1. Design a combinational circuit with three inputs and one output. The output is 1
when the binary value of the inputs is less than 3. The output is 0 otherwise.
Solution:
Truth Table:

x y z F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
K-map Simplification:

Logic Diagram:
The combinational circuit can be drawn as,

2. Design a combinational circuit with three inputs, x, y and z, and the three
outputs, A, B, and C. when the binary input is 0, 1, 2, or 3, the binary output is

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

one greater than the input. When the binary input is 4, 5, 6, or 7, the binary
output is one less than the input.
Solution:
Truth Table:
Derive the truth table that defines the required relationship between inputs and
outputs.

x y z A B C
0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 1 1
0 1 1 1 0 0
1 0 0 0 1 1
1 0 1 1 0 0
1 1 0 1 0 1
1 1 1 1 1 0

Obtain the simplified Boolean functions for each output as a function of the input
variables.
K-map for output A:

The simplified expression from the map is: A= xz+ xy+ yz

Logic Diagram:

K-map for output B:

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

The simplified expression from the map is: B= x’y’z+ x’yz’+ xy’z’+ xyz
Logic Diagram:

K-map for output C:

The simplified expression from the map is: C=z’

Logic Diagram:

3. A majority circuit is a combinational circuit whose output is equal to 1 if the

input variables have more 1’s than 0’s. The output is 0 otherwise. Design a 3-
input majority circuit.
Solution:
Truth Table:

x y z F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
5

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

K-map Simplification:

The simplified expression from the map is: xz+ yz+ xy

Logic Diagram:

4. Design a combinational circuit that generates the 9's complement of a BCD digit.
Solution:
Truth Table:

Inputs Outputs
A B C D w x y z
0 0 0 0 1 0 0 1
0 0 0 1 1 0 0 0
0 0 1 0 0 1 1 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 0 1 1
0 1 1 1 0 0 1 0
1 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0
6

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

K-map Simplification:

Logic Diagram:

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

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.
Truth Table:

Inputs Outputs
A B Sum (S) Carry (C)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
K-map simplification:

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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 three inputs and two 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

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

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

K-map simplification:

The Boolean expressions for the SUM and CARRY outputs are given by the eqns.,

Carry, Cout= AB+ ACin + BCin .

Logic Diagram:

10

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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
= B (A+A’Cin) + AB’Cin
= B (A+Cin) + AB’Cin
= AB + BCin + AB’Cin
= AB + Cin (B + AB’)
= AB + Cin (A + B)
= AB+ ACin+ BCin.

11

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

Inputs Outputs
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:

The Boolean expressions for the DIFFERENCE and BORROW outputs are
given by the equations,
12

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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- subtractor

The truth table for full-subtractor is,
Inputs Outputs
13

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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:

The Boolean expressions for the DIFFERENCE and BORROW outputs are
given by the equations,

Borrow, Bout = A’B+ A’Bin + BBin .

The logic diagram for the above functions is shown as,

14

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Implementation of full- subtractor

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
= B (A’+ABin) + A’B’Bin
= B (A’+Bin) + A’B’Bin
= A’B + BBin + A’B’Bin
= A’B + Bin( B + A’B’)
= A’B + Bin (B+ A’)
= A’B+ BBin+ A’Bin.
Therefore,
We can implement full-subtractor using two half-subtractors and OR gate as,

15

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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,

A3 A2 A1 A0= 1 1 1 1 and B3 B2 B1 B0= 1 0 1 1.

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

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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 (S3 S2 S1 S0) 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 Look Ahead Adder:

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 (1111+ 1011) gives the result as 1010.
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
17

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

produced in an each full-adder. For example, if each full adder is considered to have
a propagation delay of 8nsec, then S3 will not react its correct value until 24 nsec
after LSB is generated. Therefore total time required to perform addition is 24+ 8 =
32nsec.

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 propagate, Pi = Ai  Bi
Carry generate, Gi = Ai . Bi
the output sum and carry can be expressed as,
Si = Pi  Ci
Ci+1 = Gi + Pi.Ci

18

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Gi (carry generate), it produces a carry 1 when both Ai and Bi are 1, regardless of the
input carry Ci. Pi (carry propagate), 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.

Logic diagram of Carry Look-ahead Generator

19

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.
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 S 1 through S3
have equal propagation delay times.

4-Bit Adder with Carry Look-ahead

Binary Subtractor (Parallel Subtractor)

20

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.
Let the 4-bit words to be subtracted be represented by,
A3 A2 A1 A0= 1 1 1 1 and B3 B2 B1 B0= 1 0 1 1.

4-bit Parallel Subtractor

Parallel Adder/ Subtractor

21

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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 C, S3, S2, S1, S0, C is the carry.
The columns under the binary sum list the binary values that appear in the outputs

22

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

of the 4-bit binary adder. The output sum of the two decimal digits must be
represented in BCD.
To implement BCD adder:
• For initial addition , a 4-bit binary adder is required,
• Combinational circuit to detect whether the sum is greater than 9 and
• One more 4-bit adder to add 6 (0110)2 with the sum of the first 4-bit adder, if
the sum is greater than 9 or carry is 1.
The logic circuit to detect sum greater than 9 can be determined by
simplifying the Boolean expression of the given truth table.

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)2 is
added to the binary sum through the bottom 4-bit adder.

23

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

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

24

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

25

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

26

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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:

27

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

1. They are used as a data selector to select out of many data inputs.
2. They can be used to implement combinational logic circuit.
3. They are used in time multiplexing systems.
4. They are used in frequency multiplexing systems.
5. They are used in A/D and D/A converter.
6. They are used in data acquisition systems.

Implementation of Boolean Function using MUX:

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.

28

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Multiplexer Implementation:

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

Multiplexer Implementation:

29

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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( A, B, C, D)= ∑m (0, 1, 3, 4, 8, 9, 15)

30

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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:

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:

31

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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)

32

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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
33

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

= 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:
= 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:
34

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

35

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

(Using 4:1 MUX)

10. Implement the Boolean function using 8: 1 multiplexer

36

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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:
37

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Multiplexer Implementation:

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

38

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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 line 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

39

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

40

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

41

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

Logic diagram of 1-to-8 demultiplexer

1. Design 1:8 demultiplexer using two 1:4 DEMUX.

42

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

Applications:
1. It can be used as a decoder
2. It can be used as a data distributer
3. It is used in time division multiplexing at the receiving end as a data separator.
4. It can be used to implement Boolean expressions.

43

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

44

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

45

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

46

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

47

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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:

48

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

49

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.
4. Address decoding
5. Implementation of combinational circuits.
6. Code converters.

50

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

51

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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

52

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

The higher the subscript number, higher the priority of the input. Input D 3,
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:
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

53

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

K-map Simplification:

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

4-Input Priority Encoder

54

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.8.1 2-bit Magnitude Comparator

The truth table of 2-bit comparator is given in table below
Truth table:
Inputs Outputs
A1 A0 B1 B0 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

55

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

K-map Simplification:

56

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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 A 3 = 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,

57

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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,

58

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)

 lOMoARcPSD|45714441

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.

59

Downloaded by Kamini Ganesan G (kaminiganesan13@gmail.com)