DEPARTMENT OF COMPUTER ENGINEERING

LECTURE NOTES

Semester : 3rd
Subject Name : Digital Electronics Fundamentals Subject Code
:DI03000011
Chapter Name - Basic Combinational Circuits
Weightage of Chapter in Examination – 23%
Faculty Coordinator : [Link] [Link]

Introduction
Logic circuits can be classified into the following two types.
1. Combinational logic circuits and
2. Sequential Logic Circuit

In a combinational logic circuit, the output at any time depends on the logic level of the input at that
moment. It does not depend on the past state. There is no time delay between the input and the output
except for the propagation delay. Examples of combinational logic circuits include logic gates, binary
adders, subtractors, encoders, comparators, multiplexers, etc.
A sequential circuit contains memory elements in addition to logic gates. In this, the output of the circuit
depends not only on the condition of the input but also on the past condition of the output. Various types
of flip-flops, counters, shift registers, etc. are examples of sequential circuits.
In this unit we will study about combinational logic circuits like binary adder, subtractor, code converter.
We will study about other combinational logic circuits in the next unit

Block Diagram of combinational circuits:

A combinational circuit consists of logic gates, where outputs are at any instant (time) and are determined
only by the present combination of inputs without regard to previous inputs or previous state of outputs. A
combinational circuit performs a specific information-processing operation assigned logically by a set of
Boolean functions.

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
DOC. NO.: OIET/ACAD/LECT/LN/15
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. Figure shows a block diagram of a combinational logic circuit. There are n number of input variables
coming from an electric source and m number of output signals. Adder, subtractor, multiplexer,
demultiplexer, encoder and decoder circuit are combinational circuits.

Classification of combinational circuits:

There are three main categories of combinational circuits: arithmetic or logical functions, data transmission
and code converter as given below in category diagram.

Design Procedure of Combinational Logic:

The steps of combinational logic design are as follows:
1. First a tooth table is created.
2. A K-map is created from the tooth table.
3. A Boolean function is written by giving a simple form of the K-map.
4. A logic circuit is drawn in the required correct form from the Boolean function.

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.
DOC. NO.: OIET/ACAD/LECT/LN/15
 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,

Circuit Diagram

Half Adder using K-Map

For sum,

S = A’B+ AB’= A⊕B

For Carry,

C=A.B
DOC. NO.: OIET/ACAD/LECT/LN/15
Half Adder circuit using AOI gate:

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
1 0 0 1 0
0 1 0 1 0
1 1 0 0 1
0 0 1 1 0
1 0 1 0 1
0 1 1 0 1

1 1 1 1 1

DOC. NO.: OIET/ACAD/LECT/LN/15

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 = AB’Cin’+ A’BC’in + A’B’Cin + ABCin

= C’in (AB’+ A’B) + Cin (A’B’ + AB)
= C’in (A⊕B) + Cin ̅̅̅̅̅̅̅̅̅̅̅̅
(𝐴 ⊕ 𝐵 )

Let A⊕B = X
Now S = C’in X + Cin ̅̅̅̅̅
(𝑋 )

S = 𝑋 ⊕ Cin
Put value of X
S = A ⊕ B ⊕ Cin

Carry, Cout = ABC’in+ AB’Cin + A’BCin + ABCin

= ABC’in+ AB’Cin + A’BCin + ABCin + ABCin + ABCin [A=A+A+A]
Re-arrange the equation
= ABC’in + ABCin + AB’Cin + ABCin + A’BCin + ABCin
= AB (C’in+ Cin) + A Cin (B’ + B) + BCin(A’+ A)
= AB+ ACin + BCin . [C’in+ Cin = 1, B’ + B=1, A’+ A=1]
The logic diagram for the above equations shown as,

Expression of Full Adder from K-Map:

For sum,

DOC. NO.: OIET/ACAD/LECT/LN/15

S = AB’Cin’+ A’BC’in + A’B’Cin + ABCin

= C’in (AB’+ A’B) + Cin (A’B’ + AB)

= C’in (A⊕B) + Cin ̅̅̅̅̅̅̅̅̅̅̅̅

(𝐴 ⊕ 𝐵 )

Let A⊕B = X

Now S = C’in X + Cin ̅̅̅̅̅

(𝑋 )

S = 𝑋 ⊕ Cin

Put value of X

S = A ⊕ B ⊕ Cin

For Carry out,

Cout = AB+ ACin + BCin .

Full Adder circuit using AOI gate

DOC. NO.: OIET/ACAD/LECT/LN/15

Full adder using two Half adder with truth table and logic circuit:
The full adder circuit can be constructed using two half adders as shown in fig. And the detail circuit is
shown in fig.
Block Diagram

Circuit Diagram

The full adder can be implemented using two half adders and an OR gate.
From fig write the expression for sum output as
S = A⊕ B⊕ Cin
this expression is same as that obtained for the full adder.
Now write the expression for carry output Co as,

DOC. NO.: OIET/ACAD/LECT/LN/15

This Expression is same as the full adder.

Application of Full Adder:

• Arithmetic circuits: Full adders are utilized in math circuits to add twofold numbers. At the point
when different full adders are associated in a chain, they can add multi-bit paired numbers.
• Data handling: Full adders are utilized in information handling applications like advanced signal
handling, information encryption, and mistake rectification.
• Counters: Full adders are utilized in counters to addition or decrement the count by one.
• Multiplexers and demultiplexers: Full adders are utilized in multiplexers and demultiplexers to
choose and course information.
• Memory tending to: Full adders are utilized in memory addressing circuits to produce the location of
a particular memory area.
• ALUs: Full adders are a fundamental part of Number juggling Rationale Units (ALUs) utilized in chip
and computerized signal processors.
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

DOC. NO.: OIET/ACAD/LECT/LN/15

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.
Expression for half subtractor using K-map:
For Difference,

D = A’B+ AB’= A⊕B

For borrow,

DOC. NO.: OIET/ACAD/LECT/LN/15

 Bout = A’ . B

Half subtractor using AOI gates:

Difference, D = A’B+ AB’
Borrow, Bout = A’ . B

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 nextpossible higher minuend bit.

Block schematic of full-adder

The truth table for full-subtractor is,

Input Output
A B Borrow in Bi Difference D Borrow Bo
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

DOC. NO.: OIET/ACAD/LECT/LN/15

From truth table expression of difference and borrow-in using K-Map

For Difference

D = A'B'Bi + A'BBi' + AB'Bi' + ABBi

= A'BBi' + AB'Bi' + A'B'Bi + ABBi

= Bi'(A'B + AB') + Bi (A'B' +AB)

̅̅̅̅̅̅̅̅̅̅
= Bi'(A ⊕ B) + Bi (𝐴 ⊕ 𝐵)

Let consider A ⊕ B = X

= Bi'(X) + Bi (𝑋̅)

= X ⊕ Bi

X=A⊕B

So, D = A ⊕ B ⊕ Bi

For Borrow

Bo = 𝐴̅B + BBi + 𝐴̅Bi

DOC. NO.: OIET/ACAD/LECT/LN/15

Logic Diagram:

Full Subtractor circuit using A-O-I gates:

D = A'B'Bi + A'BBi' + AB'Bi' + ABBi

Bo = A’B + BBi + A’Bi

DOC. NO.: OIET/ACAD/LECT/LN/15

Multiplexers
Multiplexing means one out of many. A multiplexer is a digital circuit. It has many input lines and only one
output line. It selects information in binary form from various inputs and gives it at the output. It is also
called a data selector, because it selects one out of many inputs. The information is selected through the
address line or select input. There are many types of multiplexers according to the number of input lines.
For example, four inputs, 8 inputs, 16 inputs, etc. The block diagram of an n-input multiplexer is shown in
Figure.

It has n inputs Do to Dn-1 and one output Y. Data is selected by m control or select signals So to Sm-1. The
relationship between input line n and control line m is n = 2 m. That is, for n = 4, m = 2. Thus, 2 control lines
are required for a 4-input multiplexer. Similarly, 3 control lines are required for an 8-input multiplexer and
4 control lines are required for a 16-input multiplexer.

4 to 1 Multiplexer
The block diagram of 4 to 1 multiplexer is shown in Figure. There are four input lines D o to D3. There are
two control lines So and S, and one output Y. The tooth table is shown in Table.

Block Diagram

DOC. NO.: OIET/ACAD/LECT/LN/15

 Truth Table

Select Input Output

S1 S0 Y

0 0 D0

0 1 D1

1 0 D2

1 1 D3

 Note that n = 4 hence number of select lines i.e. m = 2

so that 2m = n

 The truth table tells us that if S₁ So = 00, the data bit Do is selected and routed to
output

Y = Do when S 1 S0 = 00

 Similarly if S1 S0 = 01, then D₁ is selected and routed to the output

Y = D1 when S 1 S0 = 01

 Y = D2 for S1 S0 = 10 and Y = D3 for S1 S0 = 11

 The output will be high when the selected input (Do, D₁ etc.) is 1. Hence the logical
expression for output in the SOP form is as follows:

Y = S'1 S'0 Do + S'1 S0 D1 + S1 S'0 D₂ + S1 S0 D3

DOC. NO.: OIET/ACAD/LECT/LN/15

Circuit Diagram:

Applications of Multiplexers:
Multiplexers are widely used in various types of digital systems such as data selection and routing, parallel
to serial conversion, logic functions, and waveform generation, etc. Some of the uses are mentioned below.

1. Data Selection and Routing:

A multiplexer is useful for selecting data and sending it to the desired output line using a select line.

2. Controlled sequencer:
In this, the select line is activated in sequence and the data is selected in sequence one after the other.

3. Parallel to Serial Converter:

When data is in parallel and has to be transmitted over a distance, it becomes expensive (or inconvenient)
to transmit data in parallel, because the number of transmission lines required is so large. To overcome this
problem, a single line is used. With the help of a multiplexer, the parallel data is converted into serial data
and then transmitted. At the receiving end, the serial data is converted into parallel.

4. Logic Function and Waveform Generator:

A multiplexer can be used to generate logic functions directly from a tooth table. For this, the variable is
connected to the select line and the data input is connected to logic 1 or logic 0 according to the mean
term.

DOC. NO.: OIET/ACAD/LECT/LN/15

Demultiplexers

Demultiplex means one to many (as opposed to multiplex). . A demultiplexer is a logic circuit that receives
data on a single line and outputs data on one line from multiple lines. The block diagram of a demultiplexer
is shown in Figure.

It has one input line and m select lines with the help of which the output line is selected.

A demultiplexer is also called a serial to parallel converter, because the data given on the input line is
received on one of the n lines.

1 to 4 Demultiplexer
It has one data input line on which the data to be transmitted is given. There are two select lines S o and S₁.
There are four output lines Yo to Y3. The tooth table is shown in Table.

Block Diagram

Data D is transferred to the desired output line according to the status of the select line. For example,
when the select line S₁ So is at logic 10, data D is transferred to the output line Y2. The K-map from the
logic expression from the tooth table is as follows.

DOC. NO.: OIET/ACAD/LECT/LN/15

 Truth Table

Data Select Output

input Input
D S1 S0 Y3 Y2 Y1 Y0
D 0 0 0 0 0 D
D 0 1 0 0 D 0
D 1 0 0 D 0 0
D 1 1 D 0 0 0

 From Truth tanle

Yo = DS'1S'0

Y1 = DS'1S0

Y2 = DS1S'0

Y3 = DS1S0

Circuit Diagram

DOC. NO.: OIET/ACAD/LECT/LN/15

Decoder:

A decoder is a logic circuit that converts n bit binary input data into 2 n output lines
in such a way that each output line is activated for only one of the possible
combinations of inputs. There are many types of decoders. Here we will get
information about some decoders.

2 to 4 Decoder

This type of decoder has two inputs A and B and four outputs Do to D3. Its block
diagram is as follows.

Truth Table

Input Output
A B D3 D2 D1 D0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0

 From Truth tanle

D0 = A’B’

D1 = A’B

D2 = AB’

D3 = AB

DOC. NO.: OIET/ACAD/LECT/LN/15

Circuit Diagram

3-to-8 Decoder:
• A 3-to-8 line decoder has three inputs (A, B, C) and eight outputs (D 0- D7). Based on the 3
inputs one of the eight outputs is selected.

• The block diagram of 3 to 8 decoder is show in fig.

• A, B and C are the three inputs whereas D 0 to D7 are the eight output.

DOC. NO.: OIET/ACAD/LECT/LN/15

Truth Table

Inputs Outputs
A B C D0 D1 D2 D3 D4 D5 D6 D7
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
From truth table

D0=A’B’C’
D1=A’B’C
D2=A’BC’
D3=A’BC
D4=AB’C’
D5=AB’C
D6=ABC’
D7=ABC
Logic Diagram:

DOC. NO.: OIET/ACAD/LECT/LN/15

Applications of Decoder:
1. Decoder is used in a counter system to convert binary counts to decimal digits.
2. Useful in analog to digital converters.
3. In computers and microprocessors, the address code of a memory location is used to activate it.
4. It is useful in output devices of a computer system such as printers, modems, scanners, disk drives, etc.

Encoder:
The function of an encoder is opposite to that of a decoder. A decoder converts a binary number into a
digital system, while an encoder converts a decimal signal into an equivalent binary signal. An encoder is a
combinational logic circuit that converts an active input signal into a coded output signal. An encoder has n
input lines and m output lines. Usually, m is less than n. For example, an octal to binary encoder has 8 input
lines and three output lines. Similarly, a decimal to BCD encoder has ten input lines and four output lines.
The block diagram is shown in Figure.

4 to 2 Encoder
The 4 to 2 encoder has four inputs as per 4 input lines A, B, C, D and two outputs as per D 0, and D1,
respectively. Its block diagram is as per Figure.

Truth Table

Input Output
A B C D D0 D1
0 0 0 1 0 0
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 0 1 1

DOC. NO.: OIET/ACAD/LECT/LN/15

From Truth table

D0 = A + B and D1 = A + C

Logic Diagram:

8 to 3 Encoder:

• The 8 to 3 encoder has 8 input and 3 output.

• Shows the block diagram of 8 to 3 encoder and truth table show in fig.

DOC. NO.: OIET/ACAD/LECT/LN/15

 Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 X Y Z
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

From truth table

X = D4 + D5 + D6 + D7
Y = D2 + D3 + D6 + D7
Z = D1 + D3 + D5 + D7
Logic Diagram

Applications of Encoder:
Any digital system works in binary form, while the data given from outside is not in binary form, so it is
necessary to convert that digital form into binary. Encoders are useful in this way in input devices like
computers, microprocessors etc.

Signature
Head of Department
DOC. NO.: OIET/ACAD/LECT/LN/15