Logic Design with MSI Circuits 1.

1 Half Adder

Performs the addition of two bits.

There are several specialized MSI components
that have extensive use in digital systems.
These are classified as standard components. S = x ′y + xy ′
These include adders, subtractors, comparators, C = xy
decoders, encoders and multiplexers.

1. Binary Adder – Subtractor Implementation:

The most basic arithmetic operation is the addition

of two binary digits. This simple addition consists
of four possible elementary operations:
S = x ′y + xy ′
0+0 =0 C = xy
0 +1= 1
1+ 0 = 1
1 + 1 = 10

The first three operations produce a sum (S) of

one digit, but when both augend and addend bits S =x⊕y
are equal to 1 a carry (C) is also generated (this
C = xy
propagates to the next most significant stage of
the addition).
1 2

1.2 Full Adder Alternative Implementation:

Performs the arithmetic sum of three bits.

The full adder can be also realized with two half
adders and one OR-gate:

Karnaugh maps:
The output S from the second half adder is the X-
OR of z and the output of the first half adder,
giving:

S = z ⊕ (x ⊕ y )
C = z′( xy ′ + x ′y ) + z( xy ′ + x ′y ′)′
= z′( xy ′ + x ′y ) + z( xy + x ′y ′)
= xy ′z′ + x ′yz′ + xyz + x ′y ′z

The carry output is:

C = z( xy ′ + x ′y ) + xy = xy ′z + x ′yz + xy

3 4
1.3 Binary Adder 1.4 Carry Propagation

Produces the arithmetic sum of two binary The longest propagation time in a binary ripple
numbers. It can be realized with full adders (FAs) adder is the time it takes the carry to propagate
connected in cascade. A 4-bit binary ripple adder through all full adders.
is realized as shown below:
The number of gate levels for the carry propagation
can be found from the circuit of the full adder:

An n-bit adder requires n full adders with each

output carry connected to the input carry of the The subscript i denotes a given stage in the adder.
next higher-order full adder. The signals Pi and Gi settle to their steady state
Example: Consider the two binary numbers, A = values after they propagate through their gates. Pi
1011 and B = 0011. Their sum S = 1110 is formed and Gi are common to all full adders and depend
with the 4-bit adders as follows: only on the input augend and addend bits.
The signal from the input carry Ci to the output
carry Ci+1, propagates through two gates. If there
are four full adders, the output carry C4 would
have 2 X 4 = 8 gate levels from C0 to C4.
Clearly, carry propagation time the limiting factor
on the speed with which two numbers are added.
5 6

The most widely used technique for reducing the We can now write the Boolean functions for the
carry propagation time in a parallel adder employs carry outputs of each stage and substitute for each
the principle of carry lookahead. Ci its value from the previous equations:
Consider again the circuit of the full adder: C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1(G0C0 ) = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0

These expressions are implemented in the

following carry lookahead generator:

If two new binary variables are defined:

Pi = Ai ⊕ Bi
Gi = Ai Bi
the output sum and carry can be expressed as:

Si = Pi ⊕ Ci
Ci +1 = Gi + Pi Ci

Gi is called a carry generate and it produces a

carry of 1, regardless of the input carry Ci.
Pi is called a carry propagate because it is the term
associated with the propagation of the carry from
Ci to Ci+1.
7 8
The construction of a 4-bit adder with a carry 1.5 Binary Subtractor
lookahead scheme is shown below:
The subtraction of unsigned binary numbers can
be simplified by means of complements. For
example, 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 realized
with inverters and a 1 can be added to the sum
through the input carry.
A 4-bit adder-subtractor circuit is shown below:

All output carries are generated after a delay

through two levels of gates. Thus outputs S1
through S3 have equal propagation times.
The two level circuit for the output carry C4 is not
M = 0; addition M = 1; subtraction
shown. This can be derived by the equation-
substitution method. The V bit detects an overflow when the two binary
numbers to be added are signed.
9 10

1.6 Overflow 2. Decimal Adder

Sometimes, when an adder/subtractor is using
signed arithmetic, there is arithmetic overflow from Computers or calculators that perform arithmetic
the most significant magnitude bit into the sign bit. operations directly in the decimal number system
An overflow may occur if the two numbers added represent decimal numbers in binary-coded form.
are both positive or negative. The 8421 weighted coding scheme is the most
An example of 4 possible situations that may arise commonly occurring in digital systems and is often
is given below for a 4-bit (n = 4) word. For each referred to as simply BCD (binary-coded decimal).
case the carries Cn-1 and Cn are recorded: When using BCD, a single-decade decimal adder
can be realized by first performing conventional
binary addition on two binary-coded operands and
then applying a corrective procedure. This is
illustrated below:

In the case where the sum should +11 or -11, the

corresponding binary sum is wrong. It is obvious
that an overflow flag should be raised when Cn-1 =
1 and Cn = 0, or, when Cn-1 = 0 and Cn = 1. Hence,
the equation for overflow is:
V = Cn−1 ⊕ Cn
11 12
Since each operand digit does not exceed 9, the The logic circuit that detects the necessary
output sum cannot be greater than 9 + 9 +1 = 19, correction can be derived from the table entries.
the 1 in the sum being an input carry.
Clearly, a correction is needed when the binary
The various outputs from the 4-bit binary adder sum has an output carry K = 1.
and the required outputs from the single-decade
For the other six combinations from 1010 through
decimal adder are summarized in the table below:
1111 (that also need a correction), a Boolean
expression is required to detect them:

f = P3 P2 + P3 P1

The condition for a correction and an output carry

can be expressed by the Boolean function:

Add 6 = K + P3 P2 + P3 P1

No correction to the binary sum is needed when The first term corresponds to the decimal sums 10
KP3P2P1P0 ≤ 01001. to 15 where the carry bit K is 1. The remaining two
However, 0110 (decimal 6) must be added to terms correspond to the decimal sums 16 to 19
P3P2P1P0 when KP3P2P1P0 > 01001. where K = 0.
13 14

The logic diagram of a single-decade BCD adder is

shown below: 3. 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 LSB. Each such
multiplication forms a partial product. Successive
partial products are shifted one position to the left.
The final product is obtained from the sum of the
partial products. A 2-bit by 2-bit binary multiplier is
shown below. It is realized using AND-gates and
two half adder (HA) circuits:

Whenever Cout = 0, the outputs from the upper 4-bit

binary adder are sent to the lower 4-bit adder and
decimal 0 is added.
However, whenever Cout = 1, decimal 6 is added to
the outputs of the upper 4-bit binary adder so that
the correct sum digit is obtained.
A decimal adder for two n-digit BCD numbers can
be constructed by cascading the above system in
much the same way as was done for the ripple
binary adder.
15 16
A combinational circuit binary multiplier with more
bits can be constructed in a similar fashion. For J 4. Magnitude Comparator
multiplier bits and K multiplicand bits (J X K) AND-
A circuit that compares two numbers, A and B,
gates and (J – 1) K-bit adders to produce a product
and determines their relative magnitudes.
of J + K bits. The logic diagram of a 4-bit by 3-bit
binary multiplier is shown below:
4.1 1-bit Comparator
For this case, it is simply the X-NOR function:

f = AB + A ′B ′

So the output is 1 if A = B = 0 or if A = B = 1. In
addition to the equality relation, the outcome must
indicate whether A > B, or A < B:

and from the table it is easy to show that:

A < B = A ′B
A > B = AB ′
A = B = A ′B ′ + AB

with the following NAND-gate realization:

17 18

To determine whether A > B or A < B, examine the

relative magnitudes of pairs of significant digits
starting from the most significant position:

ƒ If the two digits are equal, compare the next

lower significant pair of digits. The comparison
continues until a pair of unequal digits is found.
4.2 4-bit Comparator ƒ If the corresponding digit of A is 1 and that of B
is 0, conclude that A > B.
In this case an algorithm is required. Let the words ƒ If the corresponding digit of A is 0 and that of B
be: is 1, conclude that A < B.
A = A3 A2 A1 A0
B = B3 B2 B1B0 The sequential comparison can be expressed
logically by the two Boolean functions:
The equality relation of each pair of bits can be
expressed logically with the X-NOR function as:
( A > B ) = A3B3′ + x3 A2B2′ + x3 x 2 A1B1′ + x3 x 2 x1A0B0′
x i = Ai Bi + Ai′Bi′ for i = 0, 1, 2, 3 ( A < B ) = A3′ B3 + x3 A2′ B2 + x3 x 2 A1′B1 + x3 x 2 x1A0′ B0

where xi = 1 only if the pair of bits in position i are

The symbols (A > B) and (A < B) are binary
equal (i.e., if both are 1 or both are 0).
outputs that are equal to 1 when A > B or A < B,
For the equality condition to exist, all xi variables respectively.
must be equal to 1. This dictates an AND operation Finally, the logic diagram of the 4-bit magnitude
of all variables: comparator is as follows:
( A = B ) = x 3 x 2 x1x 0

19 20
 5. Decoders
Often, digital information represented in dome
binary form must be converted into some
alternative digital form. This is achieved by a
multiple-input, multiple output network referred to
as a decoder. The most commonly used decoder
is the n-to-2n-line decoder:

A = A3 A2 A1 A0
B = B3 B2 B1B0

x i = Ai Bi + Ai′Bi′ for i = 0, 1, 2, 3
The structure of a such decoder is straightforward.
Consider the truth table of a 3-to-8-line decoder:

The four x outputs are generated with X-NOR

circuits and applied to an AND gate to give the
output binary variable (A = B).
The other two outputs use the x variables to
generate the Boolean functions shown before.
21 22

This corresponds to the logic diagram shown 5.1 Decoders with an Enable Input
below:
Some decoders include one or more enable inputs
to control the circuit operation. The logic diagram
and truth table of a 2-to-4-line decoder are shown
below:

A particular application for this decoder is binary- A decoder with enable input can function as a
to-octal conversion. The input variables represent demultiplexer. The above decoder can function as
a binary number, and the outputs represent the a 4-to-1-line demultiplexer when E is taken as a
eight digits in the octal number system. data input line and A and B are taken as the
selection inputs.
23 24
Decoders with enable inputs can be connected The n-to-2n-line decoder is only one of several
together to form a larger decoder circuit. A 4-to-16- types of decoders. Function-specific decoders exist
line decoder realized using two 3-to-8-line having fewer than 2n outputs. Examples include
decoders is shown below: the BCD-to-decimal decoder (7442A) and the
BCD-to-7-segment decoder.

When w = 0, the top decoder is enabled and the

other is disabled. The bottom decoder outputs are
all 0’s, and the top eight outputs generate
minterms 0000 to 0111.
When w = 1, the enabled conditions are reversed;
the bottom decoder generates minterms 1000 to
1111, while the outputs of the top decoder are all
0’s.

25 26

5.2 Combinational Logic Implementation When more than ½ the total number of minterms
must be OR-ed, it is usually more economical to
An n-to-2n-line decoder is a minterm generator. use NOR-gates rather than OR-gates to do the
Recall that any Boolean function is describable by summing. Consider the pair of expressions:
a sum-of-minterms. Thus, by using OR-gates in f1 ( x 2 , x1, x 0 ) = ∑ (0, 1, 3, 4, 5, 6)
conjunction with an n-to-2n-line decoder
realizations of Boolean functions are possible. f 2 ( x 2 , x1, x 0 ) = ∑ (1, 2, 3, 4, 6)
However, these realizations do not correspond to
minimal sum-of-products. These may be realized with a 3-to-8-line decoder
and two OR-gates having a total of 11 terminals
Consider the pair of expressions:
between them. However, a more efficient
f1 ( x 2 , x1, x 0 ) = ∑ (1, 2, 4, 5) realization is to re-write the expressions as:

f 2 ( x 2 , x1, x 0 ) = ∑ (1, 5, 7) f1′′( x 2 , x1, x0 ) = f1′( x 2 , x1, x0 ) = ∑ (2, 7)

f2′′( x 2 , x1, x0 ) = f2′ ( x 2 , x1, x0 ) = ∑ (0, 5, 7)

Using a single 3-to-8-line decoder and two OR-
gates, the following realization is obtained:
This corresponds to the realization shown below:

27
A total of five gate-input terminals are needed. 28
6. Encoders 6.1 Priority Encoder

The encoder defined before has the limitation that

Perform the inverse operation of decoders. An
only one input can be active at any given time. If
encoder has 2n (or fewer) input lines and n output
two inputs are active simultaneously, the output
lines. The output lines generate the binary code
produces an undefined combination. This is
corresponding to the input value. An example of
resolved by establishing an input priority function.
an encoder is the octal-to-binary encoder whose
truth table is as follows: The truth table of a four-input priority encoder is:

In addition to the two outputs, x and y, the circuit

has a third output V; this is a valid bit indicator and
The equations for the three outputs are: is set to 1 when one or more inputs are equal to 1.
X’s in the output represent don’t-care conditions.
z = D1 + D3 + D5 + D7
y = D 2 + D3 + D 6 + D7 X’s in the input columns are for representing the
truth table in condensed form. Instead of listing all
x = D 4 + D5 + D 6 + D7
16 minterms of four variables, the truth table uses
an X to represent either 1 or 0.
The encoder can be realized with three OR-gates.
According to the table, D3 has the highest priority
followed by D2 and D1.
29 30

The maps for simplifying outputs x and y are

shown below: 7. Multiplexers
A multiplexer is a circuit that selects binary
information from one of many input lines and
directs it to a single output. Normally, there are 2n
input lines and n selection lines whose bit
combination determine which input is selected.
The logic and block diagrams of a 2-to-1-line
multiplexer are shown below:

The condition for output V is an OR function of all

the input variables:
V = D0 + D1 + D2 + D3

The priority encoder is implemented as follows:

The circuit has two data input lines, I1 and I2, one
output line Y, and one selection line S.
When S = 1, the lower AND gate is enabled and I1
has path to the output. This multiplexer acts like a
switch that selects one of the two sources.
31 32
A 4-to-1-line multiplexer is shown below: By interconnecting several multiplexers in a
treelike structure, it is possible to produce a larger
multiplexer. For example, a 16-to-1 line multiplexer
may be constructed using five 4-to-1-line
multiplexers as follows:

A multiplexer is also called a data selector, since it

selects one of many inputs and steers the binary
information to the output line.
In general, a 2n-to-1-line multiplexer is constructed
from an n-to-2n decoder by adding to it 2n input
lines, one to each AND gate. The outputs of the
AND gates are applied to a single OR gate.
As in decoders, multiplexers may have an enable
input to control the operation of the unit.
33 34

7.1 MUX/DeMUX Transmission System 7.2 Logic Design with Multiplexers

One of the primary applications of multiplexers is to Consider the Boolean function of three variables:
provide for the transmission of information from
several sources over a single path. This process is f ( x, y , z ) = ∑ (0, 2, 3, 5)
known as multiplexing. E.g., the multiplexing of
conversations on the telephone system. The function can be implemented with an 8-to-1-
When a multiplexer is used in conjunction with a line multiplexer:
demultiplexer, an effective means is provided for
connecting information from several source
locations to several destination locations. This
basic application is illustrated below:

The realization is obtained by placing x, y, and z

By using n of the structures shown above in on the S2, S1, and S0 lines respectively, logic-1 on
parallel, an n-bit word from any of four source data input lines I0, I2, I3, and I5 and logic-0 on the
locations is transferred to the four destination remaining data input lines. Also the multiplexer
locations. must be enabled by setting E = 1.
35 36
If at least one input variable of a Boolean function Karnaugh maps provide a convenient tool for
is assumed to be available in both its normal and obtaining multiplexer realizations. First it is
complemented form, then any n-variable function necessary to establish which variables to assign to
can be realized with a 2n–1-to-1-line multiplexer. the select lines. Next the inputs for the Ii data lines
are read directly from the map.
For example, reconsider the previous function:
To illustrate this, again consider the three-variable
f ( x, y , z ) = ∑ (0, 2, 3, 5) function:
= x ′y ′z ′ + x ′yz ′ + x ′yz + xy ′z f ( x, y , z ) = ∑ (0, 2, 3, 5)
Doing some simple factoring becomes:
Assume that x is placed on the S1 line and y is
f ( x, y , z ) = x ′y ′( z ′) + x ′y ( z ′ + z ) + xy ′( z ) placed on the S0 line, the resulting map is:
= x ′y ′( z ′) + x ′y (1) + xy ′( z ) + xy (0)

which is realized using a 4-to-1-line multiplexer:

submaps:

Grouping the 1-cells, the expressions for the sub-

The last term, xy(0), was included to indicate what
functions may be written. That is, I0 = z′, I1 = 1, I2 =
input must appear on the I3 line to provide for the
z, and I3 = 0. The logic realization is as before.
appropriate output when selected with x = y =1.
37 38

7.3 Three-State Gates and the construction of a 4-to-1-line multiplexer is

shown below:
A multiplexer can be constructed with three-state
gates. A three-state gate is a digital circuit that
exhibits three states. Two of the states are signals
equivalent to logic 1 and 0. The third state is a
high-impedance state which behaves like an open
circuit.
The graphic symbol of a three-state buffer is:

The presence of the high-impedance state allows

the connection of a large number of three-state
gate outputs to a common line without endangering
The use of a decoder ensures that no more than
loading effects.
one buffer control input is active at any given time.
The realization of a 2-to-1-line multiplexer with When the EN input of the decoder is 0, all of its
three-state buffers is shown below: four outputs are 0, and the bus line is in a high-
impedance state.
When EN is active, one of the buffers will be active
depending on the binary value in S1 and S2 of the
decoder.

39 40