Lecture Notes Digital Design and Computer Organization

Module 2
COMBINATIONAL LOGIC CIRCUITS

MULTIPLEXERS:
A multiplexer (or data selector, abbreviated as MUX) has a group of data inputs and a group of control inputs. The
control inputs are used to select one of the data inputs and connect it to the output terminal. The following Figure
shows a 2-to-1 multiplexer.

When the control input A is 0, the switch is in the upper position and the MUX output is Z = I0; when A is 1, the
switch is in the lower position and the MUX output is Z = I1. In other words, a MUX acts like a switch that
selects one of the data inputs (I0 or I1) and transmits it to the output. The logic equation for the 2-to-1 MUX is
therefore: 𝑍 = 𝐴′ 𝐼0 + 𝐴𝐼1

The following Figure shows diagrams for a 4-to-1 multiplexer, 8-to-1 multiplexer, and 2n-to-1 multiplexer

The 4-to-1 MUX acts like a four-position switch that transmits one of the four inputs to the output. Two control
inputs (A and B) are needed to select one of the four inputs. If the control inputs are AB = 00, the output is I0;
similarly, the control inputs 01, 10, and 11 give outputs of I1, I2, and I3, respectively.

The 4- to-1 multiplexer is described by the equation: 𝑍 = 𝐴′ 𝐵′𝐼0 + 𝐴′ 𝐵𝐼1 + 𝐴𝐵′𝐼2 + 𝐴𝐵𝐼3

Chaitra.B ,Asst .Prof, Dept of ISE,AcIT 1

 Lecture Notes Digital Design and Computer Organization

Similarly, the 8-to-1 MUX selects one of eight data inputs using three control inputs.

It is described by the equation: 𝑍 = 𝐴′ 𝐵′𝐶′𝐼0 + 𝐴′ 𝐵′ 𝐶𝐼1 + 𝐴′𝐵𝐶′𝐼2 + 𝐴′𝐵𝐶𝐼3 + 𝐴𝐵′𝐶′𝐼4 + 𝐴𝐵′ 𝐶𝐼5 +

𝐴𝐵𝐶′𝐼6 + 𝐴𝐵𝐶𝐼7.

Multiplexers can also have an additional input called an enable input.

If the OR gate in the above Figure is replaced by a NOR gate, then the 8-to-1 MUX inverts the selected input.
To distinguish between these two types of multiplexers, we will say that the multiplexers without the inversion
have active high outputs, and the multiplexers with the inversion have active low outputs.

In general, a multiplexer with n control inputs can be used to select any one of 2n data inputs. The general
equation for the output of a MUX with n control inputs and 2n data inputs is

Where mk is a minterm of the n control variables and Ik is the corresponding data input.

Multiplexers are frequently used in digital system design to select the data which is to be processed or stored.

The following Figure shows how a quadruple 2-to-1 MUX is used to select one of two 4-bit data words. If the
control A = 0, the values of x0, x1, x2, and x3 will appear at the z0, z1, z2, and z3 outputs; if A = 1, the values
of y0, y1, y2, and y3 will appear at the outputs.

Chaitra.B ,Asst .Prof, Dept of ISE,AcIT 2

Lecture Notes Digital Design and Computer Organization

Multiplexer Logic:
A digital design usually begins with a truth table. The problem is to come up with a logic circuit that has the
same truth table. We have two standard methods for implementing a truth table – the SOP and the POS solution.
The third method is the multiplexer solution.

Problem: Implement Y (A, B, C, D) = ∑m (0, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 15) using 16-to-1 multiplexer
(IC 74150) & 8-to-1 multiplexer.

Solution: Notice that, output is an active low signal in IC 74150

8-to-1 MUX
A B C D Y
Data Inputs
0 0 0 0 1
̅
𝐷
0 0 0 1 0
0 0 1 0 1
1
0 0 1 1 1
0 1 0 0 1
1
0 1 0 1 1
0 1 1 0 0
0
0 1 1 1 0
1 0 0 0 1
1
1 0 0 1 1
1 0 1 0 1
1
1 0 1 1 1
1 1 0 0 1
1
1 1 0 1 1
1 1 1 0 0
D
1 1 1 1 1

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 3

Lecture Notes Digital Design and Computer Organization

We follow a procedure that is similar to the one that we adopted in Entered Variable Map method to
implement Y using 8-to-1 MUX.

8-to-1 MUX
A B C
Data Inputs
0 0 0 ̅
𝐷
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 D

Problem:

Design a 32-to-1 multiplexer using two 16-to-1 multiplexer and one 2-to-1 multiplexer. Solution: The circuit
diagram is shown in the following Fig. A 32-to-1 multiplexer required 5 (log2 32) select lines (say, ABCDE).
The lower four select lines (BCDE) chose 16-to-1 multiplexer outputs. The 2- to-1 multiplexer chooses one of
the outputs of two 16-to-1 multiplexers, depending on the 5th select line

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 4

Lecture Notes Digital Design and Computer Organization

Problem: Realize 𝑌 = 𝐴̅𝐵 + 𝐵𝐶̅ + 𝐴𝐵𝐶 using an 8-to-1 multiplexer. Also, realize the same with a 4-to-1multiplexer.
Solution: Given, 𝑌 = 𝐴̅𝐵 + 𝐵̅ 𝐶̅ + 𝐴𝐵𝐶
𝑌 = 𝐴̅𝐵(𝐶̅ + 𝐶) + 𝐵̅ 𝐶̅ (𝐴̅ + 𝐴) + 𝐴𝐵𝐶
𝑌 = 𝐴̅𝐵𝐶̅ + 𝐴̅ 𝐵𝐶 + 𝐴̅𝐵̅ 𝐶̅ + 𝐴𝐵̅ 𝐶̅ + 𝐴𝐵𝐶
Y = ∑m (0, 2, 3, 4, 7).
Hence, to generate the given logic function, using 8-to-1 multiplexer,we find D0 = D2 = D3 = D4 = D7 = 1 and
D1 = D5 = D6 = 0.

Alternative method
8-to-1 MUX 4-to-1 MUX
A B C
𝑌 = 𝐴̅𝐵𝐶̅ + 𝐴̅ 𝐵𝐶 + 𝐴̅𝐵̅ 𝐶̅ + 𝐴𝐵̅ 𝐶̅ + 𝐴𝐵𝐶
Data Inputs Data Inputs

0 0 0 1 = D0
𝐶̅ = D0
0 0 1 0 = D1 𝑌 = 𝐴̅𝐵̅ (𝐶̅ ) + 𝐴̅ 𝐵(𝐶̅ ) + 𝐴̅ 𝐵(𝐶) + 𝐴𝐵̅ (𝐶̅ ) + 𝐴𝐵(𝐶)
0 1 0 1 = D2
1 = D1 Hence, for a 4-to-1 multiplexer,
0 1 1 1 = D3
1 0 0 1 = D4 we find D0 = C’, D1 = 1, D2 = C’, and D3 = C generates the
𝐶̅ = D2
1 0 1 0 = D5 given function.
1 1 0 0 = D6
C = D3
1 1 1 1 = D7

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 5

Lecture Notes Digital Design and Computer Organization

THREE STATE BUFFERS:

A gate output can only be connected to a limited number of other device inputs without degrading the
performance of a digital system. A simple buffer may be used to increase the driving capability of a gate output.
The following Figure shows a buffer connected between a gate output and several gate inputs. Because no bubble
is present at the buffer output, this is a non-inverting buffer, and the logic values of the buffer input and output
are the same, that is, F = C.

Normally, a logic circuit will not operate correctly if the outputs of two or more gates or other logic devices are
directly connected to each other. Use of three-state logic permits the outputs of two or more gates or other logic
devices to be connected together. The following Figure shows a three-state buffer and its logical equivalent.

When the enable input B is 1, the output C equals A; when B is 0, the output C acts like an open circuit. In other
words, when B is 0, the output C is effectively disconnected from the buffer output so that no current can flow.
This is often referred to as a Hi-Z (high-impedance) state of the output because the circuit offers a very high
resistance or impedance to the flow of current. Three-state buffers are also called tri-state buffers.

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 6

Lecture Notes Digital Design and Computer Organization

The following Figure shows the truth tables for four types of three-state buffers.

In Figures (a) and (b), the enable input B is not inverted, so the buffer output is enabled when B = 1 and disabled
when B = 0. That is, the buffer operates normally when B = 1, and the buffer output is effectively an open circuit
when B = 0. We use the symbol Z to represent this high-impedance state.

In Figure (b), the buffer output is inverted so that C = A’ when the buffer is enabled.

The buffers in Figures (c) and (d) operate the same as in (a) and (b) except that the enable input is inverted, so the
buffer is enabled when B = 0.

In the following Figure, the outputs of two three-state buffers are tied together. When B = 0, the top buffer is
enabled, so that D = A; when B = 1, the lower buffer is enabled, so that D = C. Therefore, 𝐷 = 𝐵′ 𝐴 + 𝐵𝐶. This is
logically equivalent to using a 2-to-1 multiplexer to select the A input when B = 0 and the C input when B = 1.

When we connect two three-state buffer outputs together, as shown in the following Figure, if one of the buffers
is disabled (output = Z), the combined output F is the same as the other buffer output. If both buffers

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 7

Lecture Notes Digital Design and Computer Organization

are disabled, the output is Z. If both buffers are enabled, a conflict can occur. If A = 0 and C = 1, we do not know
what the hardware will do, so the F output is unknown (X). If one of the buffer inputs is unknown, the F output
will also be unknown. The table in the following Figure summarizes the operation of the circuit. S1 and S2
represent the outputs the two buffers would have if they were not connected together. When a bus is driven by
three-state buffers, we call it a three-state bus. The signals on this bus can have values of 0, 1, Z, and perhaps X.

A multiplexer may be used to select one of several sources to drive a device input. For example, if an adder input
must come from four different sources; a 4-to-1 MUX may be used to select one of the four sources. An
alternative is to set up a three-state bus, using three-state buffers to select one of the sources (see the following
Figure). In this circuit, each buffer symbol actually represents four three-state buffers that have a common enable
signal.

Integrated circuits are often designed using bi-directional pins for input and output. Bi-directional means that the
same pin can be used as an input pin and as an output pin, but not both at the same time. To accomplish this, the
circuit output is connected to the pin through a three-state buffer, as shown in the following Figure. When the
buffer is enabled, the pin is driven with the output signal. When the buffer is disabled, an external source can
drive the input pin.

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 8

Lecture Notes Digital Design and Computer Organization

DECODERS AND ENCODERS:

The decoder is another commonly used type of integrated circuit. The following Figure shows the diagram and
truth table for a 3-to-8 line decoder. This decoder generates all of the minterms of the three input variables.
Exactly one of the output lines will be 1 for each combination of the values of the input variables.

The following Figure illustrates a 4-to-10 decoder. This decoder has inverted outputs (indicated by the small
circles). For each combination of the values of the inputs, exactly one of the output lines will be 0. When a
binary-coded-decimal digit is used as an input to this decoder, one of the output lines will go low to indicate
which of the 10 decimal digits is present

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 9

Lecture Notes Digital Design and Computer Organization

In general, an n-to-2n line decoder generates all 2n minterms (or maxterms) of the n input variables. The
outputs are defined by the equations:

yi = mi, i = 0 to 2n – 1 (non-inverted outputs)

or
yi = mi’ = Mi, i = 0 to 2n – 1 (inverted outputs)
where mi is a minterm of the n input variables and Mi is a maxterm.

Example: Realize the following functions using a 4-to-10

decoder. f1 (a, b, c, d) = m1 + m2+ m4 and f2 (a, b, c, d) =

m4 + m7 +m9 Solution:

An n-input decoder generates all of the minterms of n variables. Hence, n-variable functions can be realized by
ORing together selected minterm outputs from a decoder.

Rewriting given f1 and f2; we have: f1 = (m1’ m2’m4’)’ and f2 = (m4’ m7’m9’)’ Now, f1 and f2 can be generated
using NAND gates, as shown in the following Figure

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 10

Lecture Notes Digital Design and Computer Organization

Problem:
Show how using a 3-to8 decoder and multi-input OR gates following Boolean expression can be realized
simultaneously.
F1 (A, B, C) = ∑m (0, 4, 6) F2 (A, B, C) = ∑m (0, 5) F3 (A, B, C) = ∑m (1, 2, 3, 7).
Solution: Since, at the decoder output, we get all the min-terms, we use them as shown in the following Fig, to get
the required Boolean expression.

An encoder (converts an active input signal to a coded output signal) performs the inverse function of a decoder.
The following Figure shows a 8-to-3 priority encoder with inputs y0 through y7. If input yi is 1 and the other
inputs are 0, then the abc outputs represent a binary number equal to i. For example, if y3 = 1, then abc = 011.

If more than one input is 1 at the same time, the output can be defined using a priority scheme. The truth table in
the above Figure uses the following scheme: If more than one input is 1, the highest numbered input determines

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 11

Lecture Notes Digital Design and Computer Organization

the output. For example, if inputs y1, y4, and y5 are 1, the output is abc = 101.The X’s in the table are don’t-
cares; for example, if y5 is 1, we do not care what inputs y0 through y4 are. Output d is 1 if any input is 1,
otherwise, d is 0. This signal is needed to distinguish the case of all 0 inputs from the case where only y0 is 1.

CHAITRA.B ,ASST .PROF, DEPT OF ISE,ACIT 12