LECTURE 4

Nagia ali
 2

C O M B I N AT I O N A L C I R C U I T S
• Logic circuits for digital systems
– Combinational

– Sequential

• A combinational circuit
– outputs at any time are determined from the present combination of
inputs.

– Performs operation specified by a set of Boolean functions.

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 3

OUTLINE OF CHAPTER 1

Combinational
Circuits

Binary Comparator Decoders Encoders

Binary Adder Multiplexers
Multiplier

28 January, 2025 LOGIC DESIGN

1.1 COMBINATIONAL
CIRCUITS
 5

C O M B I N AT I O N A L C I R C U I T S
• Combinational circuit consist of
– Input variables

– Logic gates
• Accept signals from the inputs

• Generate signals to the output

– Output variables

15/1/2022 INTRODUCTION TO LOGIC DESIGN

 6

D E S I G N P R O C E D U RE
• For a given a problem statement:
– Determine the number of inputs and outputs

– Derive the truth table

– Simplify the Boolean expression for each output

– Produce the required circuit

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 7

D E S I G N P R O C E D U RE
Code conversion example

• Code converter is a circuit that makes the two systems compatible

even though each uses a different binary code.

• To convert from binary code A to binary code B;

Input: Output: generate

supply the bit the
combination of Combinational corresponding
elements specified Circuit bit combination
by code A of code B.

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

1.4 BINARY ADDER -

Nagia ali
 9

B I N A RY A D D E R - 1
• The most basic arithmetic operation is the addition of two binary digits.
• Simple addition consists of 4 possible elementary operations:
– 0+0=0
– 0+1=1
– 1+0=1
– 1 + 1 = 10
• First 3 operations produce a sum of one digit.
• In the 4th operation, the binary sum consists of two digits.

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 10

B I N A RY A D D E R - 1
Half Adder x y C S
0 0 0 0
• Adds 2 bits
0 1 0 1
– 2 inputs
1 0 0 1
– 2 outputs
1 1 1 0
• Produces SUM and CARRY.
S = x’y + xy’
C = xy
x SUM (S)
HA
y CARRY (C)

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 11

B I N A RY A D D E R - 1
Half Adder
x
S = x’y + xy’ y’
x
C = xy S S
y
x’
y
C

x
C
y (b) S = x⊕y, C = xy

(a) S = xy’+x’y, C = xy

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 12

B I N A RY A D D E R - 1
Full Adder x y z C S
0 0 0 0 0
• Adds 3 bits
0 0 1 0 1
– 3 inputs
0 1 0 0 1
– 2 outputs
0 1 1 1 0
• Produces SUM and CARRY. 1 0 0 0 1
x 1 0 1 1 0
SUM (S)
y FA
z CARRY (C) 1 1 0 1 0
1 1 1 1 1
S = x’y’z + x’yz + xy’z’ + xyz
C = x’yz + xy’z + xyz’ + xyz

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 13

B I N A RY A D D E R - 1
S = x ’ y’ z + x ’ yz + x y’ z ’ + x yz C = x ’ yz + x y’ z + x yz ’ + x yz

S = x ⊕y ⊕ z

yz y yz y
x 00 01 11 10 x 00 01 11 10
m0 m1 m3 m2 m0 m1 m3 m2
0 0
1 1 1
m4 m5 M7 m6 m4 m5 M7 m6
x 1 x 1
1 1 1 1 1

z z
C = xy + xz + yz

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 14

B I N A RY A D D E R - 1
Full adder implementation: x’
y’
z

• S = x’y’z + x’yz + xy’z’ + xyz x’

y
z’

S x
• S = x ⊕y ⊕ z x
y S
y’
z’ S
z
• C = x’yz + xy’z + xyz’ + xyz x x
y
y z x
•
x
C = xy + xz + yz z y y

x
z
x
y C
z

x
C y
z
z
C

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 15

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 16

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 17

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

1.5 MAGNITUDE
COMPARATOR
 19

M A G N I T U DE C O M PA R ATO R
• Compare two numbers (A and B)

• 3 outputs <, =, >

– A > B, A = B, A<B

• Consider compare 4-bit number to 4-bit number

A3A2A1A0 B3B2B1B0
– A = A3 A2 A1 A0

– B = B3 B2 B1 B0 Magnitude
Comparator

A>B A=B A<

28 January, 2025
B
INTRODUCTION TO LOGIC DESIGN
 20

M A G N I T U DE C O M PA R ATO R
• A = B if:
– A3 = B3 AND A2 = B2 AND A1 = B1 AND A0 = B0
Ai Bi xi (A = B) x3 = A3’ . B3’ + A3 . B3
0 0 1
x2 = A2’ . B2’ + A2 . B2
0 1 0
x1 = A1’ . B1’ + A1 . B1
1 0 0
1 1 1 x0 = A0’ . B0’ + A0 . B0

xi = Ai’ . Bi’+ Ai . Bi
x = x3 . x2 . x1 . x0 = (A = B)
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 21

M A G N I T U DE C O M PA R ATO R
• A > B if
– Ai = 1 and Bi = 0
Ai Bi yi (A > B) y3 = A3 . B3’
0 0 0
y2 = x3 . A2 . B2’
0 1 0
y1 = x3 . x2 . A1 . B1’
1 0 1
1 1 0 y0 = x3 . x2 . x1 . A0 . B0’

yi = Ai . Bi’
y = y3 + y2 + y1 + x0 = (A > B)
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 22

M A G N I T U DE C O M PA R ATO R
• A < B if
– Ai = 0 and Bi = 1
Ai Bi zi (A < B) z3 = A3’ . B3
0 0 0
z2 = x3 . A2’ . B2
0 1 1
z1 = x3 . x2 . A1’ . B1
1 0 0
1 1 0 z0 = x3 . x2 . x1 . A0’ . B0

zi = Ai’ . Bi
z = z3 + z2 + z1 + z0 = (A < B)
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
1.6 DECODERS
 24

DECODERS
• Discrete quantities of information are represented in digital systems
by binary codes.

• A binary code of n bits is capable of representing up to 2n distinct

elements of coded information.

• A decoder is a combinational circuit that converts binary information

from n input lines to a maximum of 2n unique output lines.

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 25

DECODERS
Only one lamp
• Example: 2-bit binary number
will turn on!

1
0
x1 10 0
1
Binary
0
1
x0 10 Decoder
1
0

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 26

DECODERS
• 2-to-4 Line Decoder D3
D3

Decoder
A D2 D2
Binary D1
B D0 D1

A B D0 D1 D2 D3 D0
0 0 1 0 0 0 D3= A’B’
0 1 0 1 0 0 D2= A’B A
1 0 0 0 1 0 D1= AB’ B
1 1 0 0 0 1 D0= AB
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 27

DECODERS
• 3-to-8 Line Decoder (Binary to Octal Conversion)
x y z D0 D1 D2 D3 D4 D5 D6 D7
D7
0 0 0 1 0 0 0 0 0 0 0
D6
0 0 1 0 1 0 0 0 0 0 0
Decoder D5
0 1 0 0 0 1 0 0 0 0 0
x D4
Binary

0 1 1 0 0 0 1 0 0 0 0
y D3
1 0 0 0 0 0 0 1 0 0 0
z D2
1 0 1 0 0 0 0 0 1 0 0
D1
1 1 0 0 0 0 0 0 0 1 0
D0
1 1 1 0 0 0 0 0 0 0 1
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 28

DECODERS
• 3-to-8 Line Decoder (Binary to Octal Conversion)
x y z D0 D1 D2 D3 D4 D5 D6 D7
0 0 0 1 0 0 0 0 0 0 0 D0= x’ y’ z’
0 0 1 0 1 0 0 0 0 0 0 D1= x’ y’ z
0 1 0 0 0 1 0 0 0 0 0 D2= x’ y z’
0 1 1 0 0 0 1 0 0 0 0 D3= x’ y z
1 0 0 0 0 0 0 1 0 0 0 D4= x y’ z’
1 0 1 0 0 0 0 0 1 0 0 D5= x y’ z
1 1 0 0 0 0 0 0 0 1 0 D6= x y z’
1 1 1 0 0 0 0 0 0 0 1 D7= x y z

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 29

DECODERS
• 3-to-8 Line Decoder (Binary to Octal Conversion)
D7 D7= x y z
D6 D6= x y z’
D5 D5= x y’ z
D4 D4= x y’ z’
D3 D3= x’ y z
D2 D2= x’ y z’
D1 D1= x’ y’ z
D0 D0= x’ y’ z’

x
y
z
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 30

DECODERS
D7 Example: Full Adder
D6
Decoder
D5 S(x, y, z) = ∑(1, 2, 4, 7)
D4
Binary

x x
y y D3 C(x, y, z) = ∑(3, 5, 6, 7)
z z D2
D1
D0

S C

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

1.6 ENCODERS
 32

ENCODERS
• An encoder is a digital circuit that performs the inverse operation of
a decoder.

• An encoder has 2𝑛 (or fewer) input lines and n output lines.

• The output lines generate the binary code corresponding to the input
value.

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 33

ENCODERS
• Example: 4-to-2 Binary Encoder
Only one switch should be
activated at a time
x1
x4 x3 x2 y1 y0
y1
x2 x1
Binary y0 0 0 0 1 0 0
x3 Encoder 0 0 1 0 0 1
x4 0 1 0 0 1 0
1 0 0 0 1 1
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 34

ENCODERS
• Example: Octal-to-Binary Encoder
D7 D6 D5 D4 D3 D2 D1 D0 Y2 Y1 Y0
Y2= D7 +D6 +D5 +D4
0 0 0 0 0 0 0 1 0 0 0
Y1= D7 +D6 +D3 +D2
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0 Y0= D7 +D5 +D3 +D1
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
1.7 MULTIPLEXERS
 36

M U LT I P L E X E R S
• A multiplexer (MUX) is a
combinational circuit that selects
A
binary information from one of

MUX
B
QQ==A
B
many input lines and directs it to C C
D
a single output line. D

• The selection of a particular

S S
input line is controlled by a set of 1
0 1
0
0 1
selection lines.
• There are 2n input lines and n
selected lines.
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 37

M U LT I P L E X E R S
• 4-to-1 Multiplexer
A
S0 S1 Q
A
MUX
0 0 A B
B
QQ==A
B Y
C C
D 0 1 B C
D 1 0 C
D
1 1 D
S S
1
0 1
0
0 1

S1 S0

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 38

M U LT I P L E X E R S
• Example: F(x, y) = ∑ (0, 1, 3)

x y F 1 I0
0 0 1 1 I1

MUX
D F
0 1 1 0 I2

1 0 0 1 I3
S1 S0
1 1 1
xy

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 39

M U LT I P L E X E R S
• Example:F(x, y, z) = ∑(1, 2, 6, 7)
x y z F
0 0 0 0
0 0 1 1
F=z
0 1 0 1
z I0
0 1 1 0
F = z’ z’ I1
MUX Y
0 I2
1 0 0 0
F=0 1 I3
1 0 1 0 S1 S0
1 1 0 1
F=1
1 1 1 1 x y
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 40

M U LT I P L E X E R S
• Example:F(A, B, C, D) = ∑(1,3,4,11,12,13,14,15)
A B C D F
0 0 0 0 0
F=D D I0
0 0 0 1 1
0 0 1 0 0
F=D
D I1
0 0 1 1 1
0 1 0 0 1 D’ I2
0 1 0 1 0 F = D’
0 1 1 0 0 0 I3
F=0 MUX Y F
0
1
1
0
1
0
1
0
0
0
0 I4
F=0
1
1
0
0
0
1
1
0
0
0
D I5
1 0 1 1 1 F=D 1 I6
1 1 0 0 1
1 1 0 1 1 F=1 1 I7
1 1 1 0 1 S2 S1 S0
1 1 1 1 1 F=1
A B C
28 January, 2025 INTRODUCTION TO LOGIC DESIGN
 41

D E M U LT I P L E X E R S
Y3 Y3
Y2
I DeMUX
Y1 Y2
S1 S0 Y0 I
Y1

Y0
S1 S0 Y3 Y2 Y1 Y0
0 0 0 0 0 I
0 1 0 0 I 0
1 0 0 I 0 0 S1
1 1 I 0 0 0 S0

28 January, 2025 INTRODUCTION TO LOGIC DESIGN

 42

D E M U LT I P L E X E R
Y3 D3

Decoder
Y2 A

Binary
I D2
DeMUX Y B
1 D1
Y0 E D0
S1 S0
E A B Y3 Y2 Y1 Y0
S1 S0 Y3 Y2 Y1 Y0 0 X X 0 0 0 0

0 0 0 0 0 I 1 0 0 0 0 0 1

0 1 0 0 I 0 1 0 1 0 0 1 0

1 0 0 I 0 0 1 1 0 0 1 0 0

1 1 I 0 0 0 1 1 1 1 0 0 0

28 January, 2025 INTRODUCTION TO LOGIC DESIGN