CSF 123: Physics for Computer Systems
Combinational Logic Circuits
Dr Justus Maithya
Open University of Kenya
October 13, 2024
Module Overview
In this module, you will learn adders, operation of decoders and
encoders. You will also learn about the basic architecture of
multiplexer and demultiplexers.
Learning Outcomes
By the end of this module, you should be able to:
Explain operation of adders.
Describe decoders and encoders
Discuss the principles multiplexers and demultiplexers
Study the logic diagram and truth tables of multiplexers and
demultiplexers
Types of Adders
An electronic adder or adder is a logic circuit that performs the
function of binary addition. The adder circuit consists of properly
connected logic gates. There are usually two forms of the adder in
common applications, half adder and full adder.
Half adder (HA)
Is a logic circuit that can add two binary bits. Fig. 7 shows the
block symbol for the half adder. The adder circuit would need two
inputs and two outputs.
Figure: Block symbol for the half adder
Truth Table of a Half Adder
The two inputs are for the two digits to be added, either 0 or 1 .
One output terminal is for the sum of the two inputs and the other
output is for the carry, if necessary. Fig. 7.1 shows the addition
table of the adder and can be thought of as a truth table.
Further on Half adder (HA)
Video Visit the URL below to view a video:
[Link]
Watch the video below to enhance your understanding on half
adders
Half adder (HA)
The numbers being added are on the input side of the table. The
truth table has two output columns, one column for the sum and
one column for the Pcarry. The sum column is labeled with
summation symbol . The carry column is labeled with C0 . The
C0 stands for carry output or carry out. Thus
P the half adder circuit
has two inputs (A, B) and two outputs ( , C0 ).
The output columns (sum and carry) can be produced by using
two gates:
Half adder (HA)
The sum column is the output of XOR gate. The XOR gate has
HIGH output when either input is HIGH but not when both inputs
are the same.
The carry column is the output of the AND gate. Both inputs
must be HIGH for there to be a HIGH in the output.
Half adder can be produced using a two-input AND gate and a
two-input XOR gate as shown in Fig. 7.3
Full Adder (FA)
It adds two binary bits plus a carry input (Cin ) to produce the sum
(Σ) and carry (C0 ) outputs.
Block diagram of a full adder
It is formed by using two half adder circuits and an OR gate as
shown below
Full Adder Truth Table
Note the carry-in input which requires the extra half adder. The
output of the OR gate forms the carry-out (C0 ) output. The full
adder has three inputs: Cin , A and B. Figure 7.6 shows the truth
table for a full adder. It shows all the possible combinations of
A, B and Cin .
Truth Table
Further on Full adder (HA)
Video Visit the URL below to view a video:
[Link]
Watch the video below to enhance your understanding on full
adders
Decoders and Encoders
A digital circuit can process numbers in binary form. However,
most of the information you handle is in decimal form. Therefore,
a digital machine must perform the following functions:
Convert the information from decimal to digital (binary) form
Process the digital information
Convert the digital output back to decimal form
Encoder is a circuit that converts decimal form to digital (binary)
form
Decoder is a circuit that converts digital form to decimal form
Figure 7.7: Encoders and Decoders
Digital Calculator
Figure below shows encoding and decoding in a digital calculator.
Here the input is the decimal number 5 punched in at the
keyboard.
Encoding and decoding in a digital calculator
Decoders and Encoders
The encoder changes the decimal number 5 to the digital form as
the binary digit 0101. The central processing unit (CPU) contains
digital logic circuits for necessary calculations. Here all operations
are carried out in binary form. The output of CPU is fed to the
decoder which changes the binary signal back to the decimal form.
The output display is in the decimal form, showing the original
number 5.
Architecture of Multiplexer and Demultiplexers
Multiplexer
Multiplexer means many to one. A multiplexer (MUX) is a
combinational circuit which is often used when the information
from many sources must be transmitted over long distances and it
is less expensive to multiplex data onto a single wire for
transmission. Multiplexer can be considered as multi-position or
rotary switch as shown below. There are n - inputs and one
output. The switch position is controlled by the selector lines. The
select inputs decide which input is connected to the output
Multiplexer
A multiplexer can be considered as semiconductor equivalent of
multi-position switch. Multiplexer are also called as DATA Selector
or router because it accepts several data inputs and allows only
one of them to get through to the output at a time. The basic
multiplexer has n input lines and single output line. It also has m -
select or control lines. The relation between number of select lines
and number of data inputs is
2m = n
The basic operation is controlled by a selector lines that routes one
of many input signals to the output. Fig. 7.10 shows the logic
symbol of general symbol of multiplexer.
Figure 7.10: Logic Symbol for multiplexer
Multiplexers can be either digital circuits made from high speed
logic gates used to switch digital or binary data or they can be
analogue types using transistors, MOSFET’s or relays to switch
one of the voltage or current inputs through to a single output.
The most basic type of multiplexer device is that of a one-way
rotary switch as shown in Fig. 7.11
Figure 7.11: Basic Multiplexing Switch
Types of Multiplexer: 2 × 1 multiplexer
In this multiplexer, D0 and D1 are the data inputs, S0 is the select
line and Y is the output of the multiplexer. In a function table,
Select line S0 is shown as the input and Y is the output. When
S0 = 0 then the data D0 appears at output Y and when S0 = 1,
the output Y receives the data D1 .
2 × 1 multiplexer
Figure 7.12: Logic symbol, function table and Truth table of 2 to 1
Multiplexer
The 2 to 1 multiplexer can be implemented using two AND gates
and one OR gate. The Not gate provides complemented and
un-complemented form of S0 i.e. select line.
4 to 1 Multiplexer
Logic symbol for 4 to1 multiplexer
4 to 1 multiplexer Function table
Select inputs Output
S1 S0 Y
0 0 D0
0 1 D1
1 0 D2
1 1 D3
The logic symbol (as shown in fig. 713) indicates that there are 4
data inputs namely D0 , D1 , D2 , D3 and single output Y . For 4 data
inputs there are two select lines namely S0 and S1 . The 2 select
inputs provide 4 input combinations for selecting the proper data
input at the output Y .
4 to 1 multiplexer
For 4 to 1 multiplexer, two bit binary code on select inputs (S1 S0 )
allows the data from selected input (either from D0 , D1 , D2 , D3 ) to
pass to the output.
The output Y receives D0 only when S1 = 0 and S0 = 0. Output
Y receives D1 only when S1 S0 = 01. Output Y receives D2 only
when S1 S0 = 10. Output Y receives D3 only when S1 S0 = 11.
8 × 1 multiplexer and 16 × 1 multiplexer
8 × 1 multiplexer has 8 inputs namely D0 , D1 , . . . D7 , 3 select line
S2 , S1 , S0 and Y as the single output. The 16 to 1 multiplexer has
16 inputs D0 , D1 , . . . D15 , 4 select input S3 , S2 , S1 and S0 and Y as
the output below.
Logic symbols of 8 to 1 and 16 to 1 multiplexers
Demultiplexer
It has a single input and n output lines. It reverses the multiplexing
operation. Demultiplexer can be visualized as reverse multi-position
switch. The select lines allow input data from single line to be
switched to any one of the many output lines as shown below
Multi-position switch as Demultiplexer
Logic symbol of basic demultiplexer
Demultiplexer has ’m’ select lines for selecting the desired output
for the input data as shown below. The mathematical relation
between select lines and ’ n ’ output is 2m = n
There are four basic types of demultiplexers: 1 to 2 demultiplexer,
1 to 4 demultiplexer, 1 to 8 demultiplexer and 1 to 16
demultiplexer which are classified by number of select lines.
1 to 2 demultiplexer
Select input Outputs
S0 Y0 Y1
0 D 0
1 0 D
Figure 7.17: Logic symbol and function table of a 1 to 2
demultiplexer
In 1 to 2 demultiplexer, with S0 = 0 the Y0 output of
demultiplexer receive the input data. Similarly when S0 becomes ’
1 ’, the Y1 output of demultiplexer receives the input data. Thus
the Select or control line selects the desired output to which the
input data is transferred or distributed. To distribute the input
data D to Y0 , the select input S0 should be 0 and Y1 will receive
data input D when S0 = 1. The implementation of 1 to 2
demultiplexer requires two 2 input AND gate and a NOT gate
1 × 4 demultiplexer
In 1 to 4 demultiplexer, the in-
put data can be distributed to 1
of the 4 outputs. Selection of the
output is decided by the binary
word applied to the select lines.
With S1 S0 = 00, the Y0 output
of demultiplexer receive the input
data. For S1 S0 = 01, the output
Y1 receives the input data. With
S1 S0 = 10, the input data is dis-
tributed to Y2 and when S1 S0 =
11, the output Y3 receives the in-
put data.
Logic symbol and function ta-
ble of a 1 × 4 demultiplexer
1 × 8 demultiplexer and A 1 × 16 demultiplexer
Introduction to Multiplexers
Video Visit the URL below to view a video:
[Link]
Watch the video below to enhance your understanding on
multiplexers