Introduction to Electronics

Part 4: Digital Electronics

L4: 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
 2’s Complement Representation
• An n-bit signed number (–m) in 2’s complement form: 2n – m for m ≠ 0
▪ The most significant bit (MSB) indicates the sign (0: positive, 1: negative)
▪ Complement every bit of the magnitude (m) and then add 1
bn-1 bn-2 b1 b0

Decimal 2’s Decimal 2’s

• Range of numbers: – 2n-1 to + (2n-1 – 1)
complement complement
+0 0000 -8 1000
• Total 2n numbers can be represented
+1 0001 -7 1001 • Unique representations of each number
+2 0010 -6 1010 • We are utilizing all bit of information
+3 0011 -5 1011 • Subtraction can be done using addition
+4 0100 -4 1100 • Note the way the numbers are tabulated
+5 0101 -3 1101
+6 0110 -2 1110
+7 0111 -1 1111 –2n-1 0 +2n-1
Dr. Rik Dey ESC201, 2023-24 Sem-II 4
 More Properties of 2’s Complement Representation
bn-1 bn-2 b1 b0

• An n-bit signed integer in 2’s complement form (MSB have a weight – 2n-1):
B = bn-1… b1 b0 = – bn-1 × 2n-1 + … + b1 × 21 + b0 × 20
• Sign extension: The sign bit can be copied as many times as required in the beginning:
0011 = +3 (4-bit representation), 0000 0011 = +3 (8-bit representation)
1101 = – 3 (4-bit representation), 1111 1101 = – 3 (8-bit representation)
• Shift right by k positions with the sign bit padding gives the quotient after division by 2k
0100 = +4, Shift right by 1 : 0010 = +2; 0011 = +3, Shift right by 1 : 0001 = +1 (quotient)
1100 = – 4, Shift right by 1 : 1110 = – 2 ; 1101 = – 3, Shift right by 1 : 1110 = – 2 (quotient?)
• Shift left by k positions with zero padding multiplies the number by 2k
0011 = +3, Shift left by 1 : 0110 = +6, Shift left by 2 : 1100 = – 4 ?? (check overflow)
1101 = – 3, Shift left by 1 : 1010 = – 6, Shift left by 2 : 0100 = + 4 ?? (check overflow)
➢ Extend the number representation and arithmetic considering the fractional part also
Dr. Rik Dey ESC201, 2023-24 Sem-II 5
 Binary Arithmetic using 2’s Complement
• Compute A – B; A, B are positive
➢ Note that A is a positive number (let’s call it A2)
➢ Compute the 2’s complement of B (let’s call it B2)
➢ Compute R2 = A2 + B2, the result will be in 2’s compliment
➢ About the carry obtained after addition:
➢ If it is ‘1’, ignore the carry, the result is R and is a positive number.
➢ Else (i.e., carry is 0), the result is R and it is negative in 2’s complement form.
+6: A2: 0 1 1 0 +3: A2: 0 0 1 1
– 2: B2 : 1 1 1 0 – 5: B2 : 1 0 1 1
R2: 1 0 1 0 0 R2: 1 1 1 0
+4 –2 in 2’s complement

➢ What we are doing: A + (2n – B) = 2n + (A – B), two cases: A > B and A < B
➢ A > B: we will get a carry of 1 and have to ignore the carry, result will be positive
➢ A < B: we will get a carry of 0, result will be negative and in 2’s complement form
➢ When the sign of two numbers are different, adding them can never result in overflow
➢ When the sign of the two numbers are the same, overflow may occur
➢ In case of overflow, the sign of the sum is different from the sign of either of the numbers
Dr. Rik Dey ESC201, 2023-24 Sem-II 6
 1-bit Adder: Half Adder vs Full adder
S
a b S C a
0 0 0 0 S
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
111 0 0 1 1 0
a b Cin
110 Cout Full Adder Cin 0 1 0 1 0
--------- 0 1 1 0 1
1101 1 0 0 1 0
a b 1 0 1 0 1
Cout
1 1 0 0 1
1 1 1 1 1

S = [Link] + [Link] + [Link] + [Link] ;

Dr. Rik Dey Cout = [Link] + [Link] + [Link] + [Link] ESC201, 2023-24 Sem-II 7
 4-bit Adder and Subtractor in 2’s Complement

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 8

 1’s Complement Representation
• An n-bit signed number (–m) in 1’s complement form: 2n – 1 – m
▪ The most significant bit (MSB) indicates the sign (0: positive, 1: negative)
▪ Complement every bit of the magnitude part of the number (1 to 0 and 0 to 1)
bn-1 bn-2 b1 b0

Decimal 1’s Decimal 1’s • Range of numbers: – (2n-1 – 1) to + (2n-1 – 1)

complement complement
• Total 2n – 1 numbers can be represented
+0 0000 -7 1000
• Problem: Two different representations for zero
+1 0001 -6 1001
+2 0010 -5 1010 +0: 0 00...000 and – 0: 1 11…111
+3 0011 -4 1011 • Not fully utilizing information content of MSB
+4 0100 -3 1100 • However, subtraction can be done using addition
+5 0101 -2 1101 • Note the way the numbers are tabulated
+6 0110 -1 1110 –2n-1 0 +2n-1
+7 0111 -0 1111
Dr. Rik Dey ESC201, 2023-24 Sem-II 9
 Binary Arithmetic using 1’s Complement
• Compute A – B; A, B are positive
➢ Note that A is a positive number (let’s call it A1)
➢ Compute the 1’s complement of B (let’s call it B1)
➢ Compute R’ = A1 + B1
➢ About the carry obtained after addition:
▪ If it is ‘1’, add the carry back to R’ (end-around carry), i.e., R1 = R’ + 1, and R1 is a positive number.
▪ Else, if it’s 0, ignore (or add) the carry, the result is R’ and it is negative number in 1’s complement form.
+6: A1: 0 1 1 0 +3: A1: 0 0 1 1
– 2: B1 : 1 1 0 1 – 5: B1 : 1 0 1 0
R’: 1 0 0 1 1 R’: 0 1 1 0 1
C: 1 C: 0
R1: 0 1 0 0 R1: 1 1 0 1
+4 – 2 in 1’s complement
➢ What we are doing: A + (2n – 1 – B) = 2n + (A – B) – 1, two cases: A > B and A < B
➢ Note why we are getting a carry of 1 and also adding it in case of A > B
➢ Note why we are getting a carry of 0 in case of A < B and why the result is in 1’s complement form
❑ Implement the circuit to perform addition/subtraction in 1’s complement
Dr. Rik Dey ESC201, 2023-24 Sem-II 10
 Binary Addition and Subtraction
• Similar to decimal addition and subtraction:
Input Bits a+b
• Corresponding bits are added
a b Carry Sum • The carry bit is added to digits at the left
0 0 0 0
N1: 0010 N1: 0110 Be careful if we are
0 1 0 1
N2: 0011 N2: 0010 using signed numbers.
1 0 0 1 C: 0100 C: 1100 It is a overflow then!!
1 1 1 0 S: 0101 S: 1000

Input Bits a–b • Corresponding bits are subtracted

a b Borrow Difference • Borrow bits are used in a similar manner to carry bit
0 0 0 0 N1: 0100 N1: 0010 See what we are getting is
0 1 1 1 N2: 0010 N2: 0011 nothing but the 2’s
B: 0100 B: 1110 complement form of – 1!!
1 0 0 1 D: 0010 D: 1111
1 1 0 0

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

 1-bit Subtractor: Half and Full Subtractor
Input Bits a–b Input Bits Output Bits • Bin means the bit to the right has
a b B D a b Bin Bout D borrowed from this bit
0 0 0 0 0
• Bout means this bit has borrowed
0 0 0 0
from the bit to the left
0 1 1 1 0 0 1 1 1
• If a < sum of b and Bin, then Bout = 1
1 0 0 1 0 1 0 1 1
1 1 0 0 0 1 1 1 0
1 0 0 0 1
• One can build a half-subtractor circuit 1 0 1 0 0
in a similar manner to the half-adder 1 1 0 0 0
1 1 1 1 1
B = a’.b
D = a’.b + a.b’ = XOR(a,b) • One can write down Boolean
expression for Bout & D
Here, we are doing subtraction • Can we use the half-subtractor
without using 1’s or 2’s complement to build a full-subtractor?
Dr. Rik Dey ESC201, 2023-24 Sem-II 12
 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 13
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
14
 2-bit Multiplier
Multiplicand
B1 B0

A1 A0 Multiplier
A0B1 A0B0
A1B1 A1B0 Partial products

C3 C2 C1 C0
A0

A1 B0
B1 B0 B1

HA HA

C3 C2 C1 C0

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

 Binary Multiplication of n-bit Numbers
• Circuit for multiplying 4 bit numbers

Complications:

➢How to add four bits and carry?

➢Circuit for left or right shifting?

❑ Combinational circuit design becomes too complicated!

Dr. Rik Dey ESC201, 2023-24 Sem-II 16
 Binary Division
• Circuit for division

Complications:

➢How to compare two numbers? (Ans: Using Comparator Block)

➢Circuit for left and right shifting?

❑ Combinational circuit design becomes too complicated!

Dr. Rik Dey ESC201, 2023-24 Sem-II 17
 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 18
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 19

 Shannon’s Expansion Theorem
▪ Any Boolean function of n variables can be expanded based on a single variable
▪ F(x1, x2, x3, …, xN) = x1'. F(0, x2, x3, …, xN) + x1. F(1, x2, x3, …, xN) expanded on variable x1
▪ F(0, x2, x3, …, xN) is the co-factor w.r.t. x1', F(1, x2, x3, …, xN) is the co-factor w.r.t. x1
▪ Proof: Note that each xi is a Boolean variable, take values either 0 or 1, show LHS = RHS

▪Apply it many times to get the sum of product in which each product is a minterm
▪ Prove: Use mathematical induction
▪ F(x1, x2, x3, …, xN) = x1'.[x2'.F(0, 0, x3, …, xN) + x2.F(0, 1, x3, …, xN)]
+ x1.[x2'.F(1, 0, x3, …, xN) + x2.F(1, 1, x3, …, xN)] = …
= x1'x2'x3'…xN'. F(0, 0, 0, …, 0) + … + x1x2x3…xN. F(1, 1, 1, …, 1)

▪ Note the similarity of this expansion with the expression for output of MUX

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

 Implementation of a Function using Mux
A 2 variable function can be implemented with a 4:1 mux with 2 select lines: one-to-one correspondence

x1 x2 y
0 00 0 0 0
1 01 0 1 1
F
1 10 1 0 1
0 11 1 1 0

x1 x2
expansion variables: x1, x2

Can we do better given that complement

of one of the inputs is also available?

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

 Implementation of a Function using Mux
A 2 variable function can be implemented with a 2:1 mux with 1 select line

x2 0
y = x1 x2 + x1 x2 x2 1
y

x1
expansion variable: x1
x1 x2 y
0 0 0
y = x2 when x1 = 0
0 1 1

1 0 1
y = x2 when x1 = 1
1 1 0

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

 Implementation of a Function using Mux
A 3 variable function can be implemented with a 4:1 mux with 2 select lines

x y z F

0 0 0 0
F = z when xy = 00
0 0 1 1
z 00
0 1 0 1
z F = 𝐳ത when xy =01
01 0 1 1 0
F
0 10 1 0 0 0
F = 0 when xy = 10
1 11 1 0 1 0
1 1 0 1
x y F = 1 when xy = 11
1 1 1 1
expansion variables: x, y
complement of z is available

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

 Implementation of a Function using Mux
A 3 variable function can be implemented with a 4:1 mux with 2 select lines: not an unique implementation

x y z F
0 0 0 0
F = 0 when yz = 00
1 0 0 0
0 00 0 0 1 1
F = x when yz =01
x 01 1 0 1 0
F
1 10 0 1 0 1
F = 1 when yz = 10
11 1 1 0 1
x

y 0 1 1 0
z F = x when yz = 11
expansion variables: y, z 1 1 1 1
complement of x is available

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

 Decoder
• Decodes an encoded information
• maps a smaller number of inputs to a larger set of outputs

Y0 =B. A;
y0
B A Y0 Y1 Y2 Y3
Y1 =B. A;
A y1
2-to-4 line 0 0 1 0 0 0 Y2 =B. A;
B decoder y2 Y3 =B. A
0 1 0 1 0 0
y3
1 0 0 0 1 0
1 1 0 0 0 1

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

 Decoder with ‘Enable’ input
2/4 E B A Y0 Y1 Y2 Y3
E y0
0 x x 0 0 0 0
y1
1 0 0 1 0 0 0
y2
1 0 1 0 1 0 0
A y3 1 1 0 0 0 1 0
B
1 1 1 0 0 0 1

Y0 =E.B.A ; Y1 =E.B.A; Y2 =E.B.A ; Y3 =E.B.A

E
Y0
E.B.A
A

Y1
E.B.A

Y2 E.B.A
B

Y3 E.B.A
Dr. Rik Dey ESC201, 2023-24 Sem-II 26
 Decoder in Vending Machine

M-1
M-1

M-2 M-2
2-to-4
decoder

M-3 M-3

M-4 M-4

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

 Term Generator for SOP Expression of a Function
E
E.B.A
Y0
x y min
term term A
E.B.A
0 0 x.y m0 Y1

0 1 x.y m1 E.B.A
1 0 x.y m2 Y2
B
1 1 x.y m3 E.B.A
Y3

B A f1 2/4
1 E y0
0 0 0 y1
0 1 1 y2 f
1 0 1 A y3
1 1 0 B

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

 Implementation of a Function using Decoder
• Decoder allows a quick implementation

• No minimization, but lots of gates…

C B A f
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

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

 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 30
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 31
 Bigger Decoder
• 3 by 8 decoder using a 2 by 4 decoder (similar to building bigger MUX from smaller ones)

Ee C
c B
b Aa y0 y 1 y2 y 3 y4 y 5 y6 y 7 2/4 0
E y0
0 x x x 0 0 0 0 0 0 0 0
1
1 2/4 y1
1 0 0 0 1 0 0 0 0 0 0 0
Ee E 1 y2 0
1
1 0 0 1 0 1 0 0 0 0 0 0 A y3 0
0 B
1 0 1 0 0 0 1 0 0 0 0 0 0
1 0 1 1 0 0 0 1 0 0 0 0 0 A 2/4 0
Cc E y4
1 1 0 0 0 0 0 0 1 0 0 0 00 B 0
y5
1 1 0 1 0 0 0 0 0 1 0 0 y6 0
1 1 1 0 0 0 0 0 0 0 1 0 A y7 0
1 1 1 1 0 0 0 0 0 0 0 1 E B A Y0 Y1 Y2 Y3 B
0 x x 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1
Dr. Rik Dey ESC201, 2023-24 Sem-II 32
 De-Multiplexer (De-MUX)

u-1 u-11
S1 S0 y0 y1 y2 y3

u-2 u-22 Data 0 0 0 D 0 0 0

Data 1
Mux Demux S1 0 1 0 D 0 0
2
u-33
u-3 S0 3 1 0 0 0 D 0
1 1 0 0 0 D
u-4 u-44

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

 De-Mux vs Decoder
2/4
Data 0 E y0 Only difference is in
1 y1
S1 2 y2
3 A y3
name and application
S0 Dmux B

S1 S0 Y0 Y1 Y2 Y3
E B A Y0 Y1 Y2 Y3
0 0 D 0 0 0 0 x x 0 0 0 0
0 1 0 D 0 0 1 0 0 1 0 0 0

1 0 0 0 D 0 1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 0 0 0 D
1 1 1 0 0 0 1
Data E
Y0 Y0
S0 A

Y1 Y1

Y2 Y2
S1 B

Dr. Rik Dey Y3 Y3 ESC201, 2023-24 Sem-II 34

 Encoder
• Inverse of decoders
d3 d2 d1 d 0 B A
4/2
0 0 0 1 0 0
0 A We do not care what the
0 0 1 0 0 1
1 output (A&B) will be for
0 1 0 0 1 0
2 B other input combinations
3 1 0 0 0 1 1

d1 d0 d1 d0
d3d2 00 01 11 10 d3d2 00 01 11 10
00 x 0 x 1 00 x 0 x 0 Don’t care terms (x) can be included in
01 0 x x x 01 1 x x x encirclements if it helps in obtaining
11 x x x x 11 x x x x larger grouping and/or smaller number
10 1 x x x 10 1 x x x of groups in the expression.
A B
Dr. Rik Dey A = d2 d0 B = d1 d 0 ESC201, 2023-24 Sem-II 35
 Minimization with Don’t Care Terms
• Don’t care terms can be chosen as 1 as necessary
• Sometimes choosing them as 1 yields simpler expressions in SOP minimization

yz
wx 00 01 11 10
00 1 x 0 1 f=𝑤·𝑧+𝑥·𝑦+𝑤·𝑥
01 1 0 1 1
Don’t care terms (x) should be included in
11 0 x 1 1 encirclements if it helps in obtaining larger
grouping or smaller number of groups.
10 1 x 1 x

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