Introduction to Electronics

Part 4: Digital Electronics

L3: Combinational Circuit Design

Dr. Rik Dey

ASSISTANT PROFESSOR,
ELECTRICAL ENGINEERING, IIT KANPUR

2023-24 SEM-II ESC201A INTRODUCTION TO ELECTRONICS CIRCUITS

1
 Digital Design Flow
x y z f
System Description 0 0 0 0
0 0 1 1
0 1 0 0
Truth Table 0 1 1 1
1 0 0 0
x 1 0 1 1
y 1 1 0 0
system f
1 1 1 1
z

Boolean Expression f = x .y . z + x . y . z + x . y . z + x . y . z

Minimized ⇒ f=𝑧
Boolean Expression

Gate Netlist
Dr. Rik Dey ESC201, 2023-24 Sem-II 2
 Modular Approach
System
Sub-system-1
Sub-system 3:

System Sub-system-3 Sub-Sub-systems

Sub-system-2

There are certain sub-systems or blocks that are used quite often such as :
1. Adder/Subtractors
2. Comparator
3. Multiplexers
4. Demultiplexers/Decoders
5. Encoders
Dr. Rik Dey ESC201, 2023-24 Sem-II 3
 Binary Addition

1
0 11 00 11
1
0 00 11 11 1
0 11 11 1 10 0 1 1

101 1101
110 + 1110
1011 11011

Dr. Rik Dey ESC201, 2023-24 Sem-II 4

 1 bit Addition: Half Adder
S a b S C
0 0 0 0 Truth Table
0 1 1 0
C Half Adder
1 0 1 0
1 1 0 1
a b

S = a.b + a.b ; C = a.b Boolean Expression

a
S Gate Level
b

C
Implementation

Dr. Rik Dey ESC201, 2023-24 Sem-II 5

 𝑥𝟏 𝑥2 𝑦1 𝑦2 𝑧1 𝑧2 𝑧3
Try 2-bit Adder 0 0 0 0 0 0 0
• Let us make a 2 bit adder circuit which can add two 2-bit numbers 0 0 0 1 0 1 0
0 0 1 0 1 0 0
𝑥1 𝑥0
0 0 1 1 1 1 0
+ 𝑦1 𝑦0
0 1 0 0 0 1 0
𝑧2 𝑧1 𝑧0 0 1 0 1 1 0 0
0 1 1 0 1 1 0
• There are 4 inputs and 3 outputs 0 1 1 1 0 0 1
1 0 0 0 1 0 0
• Let us write down all possible combinations!
1 0 0 1 1 1 0
• 24 = 16 rows in the truth table
1 0 1 0 0 0 1
➢ Write down Boolean expressions and design implementation? 1 0 1 1 0 1 1
➢ What about 3 bits? Do we need to do it all over again? 1 1 0 0 1 1 0
➢ Let’s try the modular approach (better) 1 1 0 1 0 0 1
1 1 1 0 0 1 1
Dr. Rik Dey ESC201, 6
1 1 1 1 12023-24
0 Sem-II
1
 Adder: First bit
S
0 11 00 11
C Half Adder 0 00 11 11
0 11 11 1 10 0
a b

Truth Table
a b S C S = a.b + a.b ; C = a.b Boolean expression
0 0 0 0
0 1 1 0 a
S
1 0 1 0 b
Implementation
1 1 0 1
C

Dr. Rik Dey ESC201, 2023-24 Sem-II 7

 Adder: Second bit
S
0 11 00 11
C Half Adder 0 00 11 11
0 11 11 1 10 0
a b

1
But there can be carry 𝑥1 1
+ 𝑦1 1
from previous bits.
𝑧2 𝑧1 0

Dr. Rik Dey ESC201, 2023-24 Sem-II 8

 Need Single Bit Full Adder

Dr. Rik Dey ESC201, 2023-24 Sem-II 9

 1-bit Adder: Half Adder vs Full adder
S
a b S C a
S
0 0 0 0 b
C Half Adder 0 1 1 0
1 0 1 0 C
1 1 0 1
a b
S = a.b + a.b ; C = a.b

a b Cin S Cout

1 S 0 0 0 0 0
0 0 1 1 0
111
0 1 0 1 0
S = [Link] + [Link] + [Link] + [Link] ;
110 Cout Full Adder Cin
---------
0 1 1 0 1
Cout = [Link] + [Link] + [Link] + [Link]
1 0 0 1 0
1101
1 0 1 0 1
a b
1 1 0 0 1
1 1 1 1 1

Dr. Rik Dey ESC201, 2023-24 Sem-II 10

 1-bit Full Adder Circuit using Two 1-bit sHalf Adders
S = [Link] + [Link] + [Link] + [Link] S = Cin  (a  b)

Cout = [Link] + [Link] + [Link] + [Link] Cout = Cin (a.b + a.b) + a.b = Cin .(a  b) + a.b

a a b Cin  (a  b)
b S

Cin .(a  b)

Cout
a.b
Cin
Dr. Rik Dey ESC201, 2023-24 Sem-II 11
 2-bit Adder
𝑧2

𝑥1
𝑦1
𝑥1 𝑥0 𝑧1
+ 𝑦1 𝑦0
𝑧2 𝑧1 𝑧0
𝑥0

𝑦0
𝑧0
0

Dr. Rik Dey ESC201, 2023-24 Sem-II 12

 Multi-bit Adder Example: 4-bit Adder
• How to add two 4-bit numbers?

• Truth table would have 28=256 entries

• Instead, use already designed logic circuits as subsystems

1101
+ 1110
11011

Dr. Rik Dey ESC201, 2023-24 Sem-II 13

 4-bit Adder
S(0:3)
A 3 A 2 A 1 A 0 B 3 B 2 B 1 B 0 S 3 S 2 S 1S 0 Cout
C3 C2 C1
0000 0000 0000 0
1
A 3 A 2 A 1A 0
0000 0001 0001 0
Cout 4-bit adder
0001 0000 0001 0 B 3 B 2 B 1B 0
C 4 S 3 S 2 S 1S 0

A(0:3) B(0:3)

S3 S2 S1

C4 C3 C2 C1 0
FA FA FA FA

A3 B3 A2 B2 A1 B1 A0 B0

Dr. Rik Dey ESC201, 2023-24 Sem-II 14

 4-bit Subtractor
A – B = A + 2’s complement of B
A − B = A + B +1
A – B = A + 1’s complement of B + 1

FA FA FA FA 1

B3 B2 B1 B0
A3 A2 A1 A0

B3 B2 B1 B0

B0  1 = B0 .1 + B0 .1 = B0
Dr. Rik Dey ESC201, 2023-24 Sem-II 15
 4-bit Adder and Subtractor

FA FA FA FA

A3 A2 A1 A0

M=1

B3 B2 B1 B0

B0  0 = B0 .0 + B0 .0 = B0 M = 0 for Adder
B0  1 = B0 .1 + B0 .1 = B0 M=1 for Subtractor

Dr. Rik Dey ESC201, 2023-24 Sem-II 16

 Comparator
A = A3 A2 A1 A0
B = B3 B2 B1 B0

Dr. Rik Dey ESC201, 2023-24 Sem-II 17

 Bit-wise Comparison
A = A3 A2 A1 A0
B = B3 B2 B1 B0

xi = Ai .Bi + Ai .Bi for i = 0,1,2,3 a

b

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

a
(i.e., if both are 1 or both are 0). b

𝑥𝑖 = 𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖 = (𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖 ) a a
b a>b
b
Proof: (𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖 ) = (𝐴𝑖 + 𝐵𝑖 ). (𝐴𝑖 + 𝐵𝑖 ) a a=b
a
a<b
b
= 𝐴𝑖 . 𝐴𝑖 + 𝐴𝑖 . 𝐵𝑖 + 𝐵𝑖 . 𝐴𝑖 + 𝐵𝑖 . 𝐵𝑖 = 𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖
Dr. Rik Dey ESC201, 2023-24 Sem-II 18
 Bit-wise Comparison

a
a>b 𝑦𝑖 = 𝐴𝑖 . 𝐵𝑖
𝑎 > 𝑏 only if 𝑎 = 1 and 𝑏 = 0 b

a
𝑎 < 𝑏 only if 𝑎 = 0 and 𝑏 = 1 a<b 𝑧𝑖 = 𝐴𝑖 . 𝐵𝑖
b

𝑎 = 𝑏 only if 𝑎 > 𝑏 and 𝑎 < 𝑏 both are false 𝑥𝑖 = (𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖 ) = 𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖

Dr. Rik Dey ESC201, 2023-24 Sem-II 19

 Full Comparator via Modular Approach

𝑦𝑖 = 𝐴𝑖 . 𝐵𝑖
A = A3 A2 A1 A0 b
a a
b
a>b
𝑥𝑖 = 𝐴𝑖 . 𝐵𝑖 + 𝐴𝑖 . 𝐵𝑖
B = B3 B2 B1 B0 a
a
a=b
a<b
b
𝑧𝑖 = 𝐴𝑖 . 𝐵𝑖
( A = B ) = x3 x2 x1 x0
𝐴 > 𝐵 = 𝑦3 + 𝑥3 𝑦2 + 𝑥3 𝑥2 𝑦1 + 𝑥3 𝑥2 𝑥1 𝑦0
𝐴 < 𝐵 = 𝑧3 + 𝑥3 𝑧2 + 𝑥3 𝑥2 𝑧1 + 𝑥3 𝑥2 𝑥1 𝑧0
Dr. Rik Dey ESC201, 2023-24 Sem-II 20
a3 a3<b3
1-bit
b3 a3>b3
comparator
a3=b3

a2<b2
𝐴 > 𝐵 = 𝑦3 + 𝑥3 𝑦2 + 𝑥3 𝑥2 𝑦1 + 𝑥3 𝑥2 𝑥1 𝑦0
a2
1-bit
b2 a2>b2
comparator x1 A>B
a2=b2 OR y
x2
a1 a1<b1
1-bit
a1>b1 x1
b1 comparator OR y
a1=b1 x2 A< B

a0 a0<b0
1-bit A=B
a0>b0
b0 comparator 𝐴 = 𝐵 = 𝑥3 𝑥2 𝑥1 𝑥0
a0=b0
21
 Multiplexers (MUX)
I0
I0
2:1
y
mux
I1
I1 Y0

S
S

S I0 I1 y

S y is a shortcut to say
0 0 0 0 𝑦 = 𝑆𝐼ҧ 0 𝐼ഥ1 + 𝑆𝐼ҧ 0 𝐼1 + 𝑆𝐼ഥ0 𝐼1 + 𝑆𝐼0 𝐼1
I0 0 0 1 0 = 𝑆𝐼ҧ 0 𝐼ഥ1 + 𝐼1 + 𝑆𝐼1 𝐼ഥ0 + 𝐼0
0 = 𝑆ҧ 𝐼0 + 𝑆 𝐼1
0 1 0 1
1 I1 0 1 1 1
• The shortcut version of truth table is more useful
𝑦 = 𝑆ҧ 𝐼0 + 𝑆 𝐼1 1
1
0
0
0
1
0
1 • => Minimization is more natural
1 1 0 0
1 1 1 1 22
Dr. Rik Dey ESC201, 2023-24 Sem-II
 Bigger Multiplexer (MUX)
I0 00 𝑦 = 𝑆1 𝑆0 𝐼0 + 𝑆1 𝑆0 𝐼1 +𝑆1 𝑆0 𝐼2 + 𝑆1 𝑆0 𝐼3
I1 01 4:1
y
I2 10 mux S0 S1

I3 11

S1 S0
I0

S1 S0 y
I0 I1
0 0 Y
0 1 I1
I2
1 0 I2
1 1 I3
I3

Dr. Rik Dey ESC201, 2023-24 Sem-II 23

 Bigger MUX from Smaller MUX
I0 S1 S0 y I0 00
S y 2:1
y I0
mux 0 0 I1 01 4:1
I0 I1 y
0 I2 10 mux
0 1 I1
1 I1 S I3 11
1 0 I2
1 1 I3 S1 S0
I0
2:1
y
mux
I1
I0
2:1
S0 y
mux
I1
I02
2:1
y SS1
mux
I13

Dr. Rik Dey

S0 24
ESC201, 2023-24 Sem-II
 Bigger MUX from Smaller MUX with Enable
E S1 S0 y
E S y
I0 0 y I0
0 0
0 x 0
I1 1 0 1 I1
1 0 I0
1 0 I2
S 1 1 I1
1 1 I3

01 01
E E I31
0I1
I0 0 I2 0 y
0I3
I1 1 I3 1
1 1
S0 S0
10
S1
Dr. Rik Dey ESC201, 2023-24 Sem-II 25