Digital Logic Design

Chapter-4
Combinational Circuits

★ Output is function of input only

i.e. no feedback

Combination
n • • m
• al •
inputs • • outputs
Circuits

When input changes, output may change (after a

delay)
Combinational Circuits

★ Analysis
● Given a circuit, find out its function ?

● Function may be expressed as: ?

♦ Boolean function
♦ Truth table

★ Design
● Given a desired function, determine its circuit
● Function may be expressed as:
♦ Boolean function ?
♦ Truth table
Analysis Procedure

★ Boolean Expression Approach

T2=ABC
T1=A+B+C
T3=AB'C'+A'BC'+A'B'C

F’2=(A’+B’)(A’+C’)(B’+C’)

F2=AB+AC+BC

F1=AB'C'+A'BC'+A'B'C+ABC
F2=AB+AC+BC
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=0 0 0 0 0 0
0 0
=0
=0
=0 0
=0 0
=0
0 1
=0
=0
0
=0 0
=0
0
=0
=0
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=0 0 0 0 0 0
0 1
=0 0 0 1 1 0
=1
=0 1
=0 1
=1
0 1
=0
=0
0
=0 0
=1
0
=0
=1
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=0 0 0 0 0 0
0 1
=1 0 0 1 1 0
=0
0 1 0 1 0
=0 1
=1 1
=0
0 1
=0
=1
0
=0 0
=0
0
=1
=0
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=0 0 0 0 0 0
0 0
=1 0 0 1 1 0
=1
1
0 1 0 1 0
=0
=1 0 0 1 1 0 1
=1
0 0
=0
=1
0
=0 1
=1
1
=1
=1
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=1 0 0 0 0 0
0 1
=0 0 0 1 1 0
=0
1
0 1 0 1 0
=1
=0 1 0 1 1 0 1
=0 1 0
0 1 1 0 0
=1
=0
0
=1 0
=0
0
=0
=0
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=1 0 0 0 0 0
0 0
=0 0 0 1 1 0
=1
1
0 1 0 1 0
=1
=0 0 0 1 1 0 1
=1
0 0 1 0 0 1 0
=1
=0 1 0 1 0 1
1
=1 1
=1
0
=0
=1
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=1 0 0 0 0 0
0 0
=1 0 0 1 1 0
=0
1
0 1 0 1 0
=1
=1 0 0 1 1 0 1
=0
1 0 1 0 0 1 0
=1
=1 1 0 1 0 1
=1
0 1 1 0 0 1
1
=0
0
=1
=0
Analysis Procedure

★ Truth Table Approach A B C F1 F2

=1 0 0 0 0 0
1 1
=1 0 0 1 1 0
=1
1
0 1 0 1 0
=1
=1 0 0 1 1 0 1
=1
1 0 1 0 0 1 0
=1
=1 1 0 1 0 1
=1
1 1 1 0 0 1
1
=1 1 1 1 1 1
1
=1
=1
B B

0 1 0 1 0 0 1 0
A 1 0 1 0 A 0 1 1 1
C C
F1=AB'C'+A'BC'+A'B'C+ABC F2=AB+AC+BC
Design Procedure

★ 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
Example:
Design a circuit to convert a “BCD” code to
“Excess 3” code
4-bits ? 4-bits
0-9 Value+3
values
Design Procedure

★ BCD-to-Excess 3 Converter
C C
A B C D w x y z
0 0 0 0 0 0 1 1 1 1 1
0 0 0 1 0 1 0 0 1 1 1 1
0 0 1 0 0 1 0 1 x x x x B x x x x B
0 0 1 1 0 1 1 0 A 1 1 x x A 1 x x
0 1 0 0 0 1 1 1 D D
0 1 0 1 1 0 0 0 w = A+BC+BD x = B’C+B’D+BC’D’
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0 C C
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0 1 1 1 1
x x x x 1 1 1 1
1 0 1 0 B B
x x x x x x x x
1 0 1 1 x x x x A A
1 x x 1 x x
1 1 0 0 x x x x
1 1 0 1 x x x x D D
1 1 1 0 x x x x y = C’D’+CD z = D’
1 1 1 1 x x x x
Design Procedure

★ BCD-to-Excess 3 Converter
A B C D w x y z
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
1 0 1 0 x x x x
1 0 1 1 x x x x
1 1 0 0 x x x x
1 1 0 1 x x x x w = A + B(C+D) y = (C+D)’ +
1 1 1 0 x x x x x = B’(C+D) + B(C+D)’ CD
z = D’
1 1 1 1 x x x x
Seven-Segment Decoder
a
w x y z abcdefg
w a
0 0 0 0 1111110 b
0 0 0 1 0110000 x c f b
? d g
0 0 1 0 1101101 y e
0 0 1 1 1111001 z f
g
0 1 0 0 0110011 e c
0 1 0 1 1011011 BCD code
0 1 1 0 1011111
0 1 1 1 1110000 y d
1 0 0 0 1111111
1 0 0 1 1111011 1 1 1
1 0 1 0 xxxxxxx 1 1 1
x x x x x
1 0 1 1 xxxxxxx w 1 1 x x
1 1 0 0 xxxxxxx
1 1 0 1 xxxxxxx z
1 1 1 0 xxxxxxx a = w + y + xz + b=...
x’z’ c=...
1 1 1 1 xxxxxxx
d=...
Binary Adder

★ Half Adder x S
y H
● Adds 1-bit plus 1-bit C
A
● Produces Sum and Carry x
+ y
───
x y C S C S
0 0 0 0
0 1 0 1
x S
1 0 0 1
1 1 1 0
y C
Binary Adder

★ Full Adder x S
y F
● Adds 1-bit plus 1-bit plus 1-bit z C
A
● Produces Sum and Carry x
+ y
y + z
x y z C S
───
0 0 0 0 0 0 1 0 1 C S
0 0 1 0 1 x 1 0 1 0
0 1 0 0 1 z
S = xy'z'+x'yz'+x'y'z+xyz =x⊕
0 1 1 1 0 y⊕z y
1 0 0 0 1
1 0 1 1 0 0 0 1 0
1 1 0 1 0 x 0 1 1 1
1 1 1 1 1 C = xy + xzz +
yz
Binary Adder

★ Full Adder S = xy'z'+x'yz'+x'y'z+xyz = x ⊕

y
C⊕=zxy + xz +
yz

x
S S
x
y y
C
z
z C
Binary Adder

★ Full Adder
x HA HA S
y
z C

x
S

y
C

z
Binary Adder
x3x2x1x0 y 3 y 2 y1 y 0
c 3 c 2 c1 .
+ x3 x 2 x 1 x 0
Carry + y3 y 2 y 1 y 0
Cy Binary Adder C0 Propagat ────────
e Cy S3 S 2 S 1 S 0
Addition
S 3S 2S 1S 0

x3 x2 x1
x0y3 y2 y1
y0 0

FA FA FA FA

C4 C3 C2 C1
S3 S2 S1
S0
Binary Adder

★ Carry Propagate Adder

x7 x6 x5 x4 x3 x2 x1 x0
y7 y6 y5 y4 y3 y2 y1 y0

A3 A2 A1 A0 B3 B2 B1 B0 A3 A2 A1 A0 B3 B2 B1 B0

Cy CPA C0 Cy CPA C0 0

S3 S2 S1 S0 S3 S2 S1 S0

S7 S6 S5 S4 S3 S2 S1 S0
★ Carry propagation
● When the correct outputs are available
● The critical path counts (the worst case)
● (A1, B1, C1) → C2 → C3 → C4 → (C5, S4)
● When 4-bits full-adder → 8 gate levels (n-bits: 2n
gate levels)

Figure 4.10 Full Adder with P and G Shown

Parallel Adders

★ Reduce the carry propagation delay

● Employ faster gates
● Look-ahead carry (more complex mechanism, yet
faster)
● Carry propagate: Pi = Ai⊕B i
● Carry generate: Gi = AiB i
● Sum: Si = Pi⊕C i
● Carry: C i+1 = Gi+PiC i
● C 0 = Input carry
● C 1 = G0+P0C 0
● C 2 = G1+P1C 1 = G1+P1(G0+P0C 0) = G1+P1G0+P1P0C 0
● C 3 = G2+P2C 2 = G2+P2G1+P2P1G0+ P 2P1P0C 0
 Carry Look-ahead Adder (1/2)

★ Logic diagram

Fig. 4.11 Logic Diagram of Carry Look-ahead

Generator
Carry Look-ahead Adder (2/2)

★ 4-bit carry-look
ahead adder
● Propagation
delay of C3, C2
and C1 are equal.

Fig. 4.12 4-Bit Adder with Carry Look-

ahead
BCD Adder

★ 4-bits plus 4-bits + x3 x 2 x 1 x 0

+ y3 y 2 y 1 y 0
★ Operands and Result: 0 to 9 ────────
Cy S3 S 2 S 1 S 0
X +Y x3 x2 x1 x0 y 3 y2 y1 y0 Sum Cy S 3 S2 S1 S0
0+0 0 0 0 0 0 0 0 0 =0 0 0 0 0 0
0+1 0 0 0 0 0 0 0 1 =1 0 0 0 0 1
0+2 0 0 0 0 0 0 1 0 =2 0 0 0 1 0

0+9 0 0 0 0 1 0 0 1 =9 0 1 0 0 1
1+0 0 0 0 1 0 0 0 0 =1 0 0 0 0 1
1+1 0 0 0 1 0 0 0 1 =2 0 0 0 1 0

1+8 0 0 0 1 1 0 0 0 =9 0 1 0 0 1
1+9 0 0 0 1 1 0 0 1 =A 0 1 0 1 0 Invalid
2+0 0 0 1 0 0 0 0 0 =2 0 0 0 1 0 Code
9 + 9 1 0 0 1 1 0 0 1 = 12 1 0 0 1 0 Wrong BCD
0001 Value
BCD Adder

Required BCD
X +Y x3 x2 x1 x0 y 3 y2 y1 y0 Sum Cy S 3 S2 S1 S0 Value
Output

9+0 1 0 0 1 0 0 0 0 =9 0 1 0 0 1 0 0 0 0 1 0 0 1 =9
9+1 1 0 0 1 0 0 0 1 = 10 0 1 0 1 0 0 0 0 1 0 0 0 0 = 16
9+2 1 0 0 1 0 0 1 0 = 11 0 1 0 1 1 0 0 0 1 0 0 0 1 = 17
9+3 1 0 0 1 0 0 1 1 = 12 0 1 1 0 0 0 0 0 1 0 0 1 0 = 18
9+4 1 0 0 1 0 1 0 0 = 13 0 1 1 0 1 0 0 0 1 0 0 1 1 = 19
9+5 1 0 0 1 0 1 0 1 = 14 0 1 1 1 0 0 0 0 1 0 1 0 0 = 20
9+6 1 0 0 1 0 1 1 0 = 15 0 1 1 1 1 0 0 0 1 0 1 0 1 = 21
9+7 1 0 0 1 0 1 1 1 = 16 1 0 0 0 0 0 0 0 1 0 1 1 0 = 22
9+8 1 0 0 1 1 0 0 0 = 17 1 0 0 0 1 0 0 0 1 0 1 1 1 = 23
9+9 1 0 0 1 1 0 0 1 = 18 1 0 0 1 0 0 0 0 1 1 0 0 0 = 24

+6
BCD Adder

★ Correct Binary Adder’s Output (+6)

● If the result is between ‘A’ and ‘F’
● If Cy = 1

S 3 S2 S1 S0 Err
S1
0 0 0 0 0

1 0 0 0 0
1 1 1 1 S2
1 0 0 1 0
S3 1 1
1 0 1 0 1
1 0 1 1 1 S0
1 1 0 0 1
Err = S3 S2 + S3
1 1 0 1 1
S1
1 1 1 0 1
1 1 1 1 1
BCD Adder

Err
Binary Subtractor

★ Use 2’s complement with binary adder

● x – y = x + (-y) = x + y’ + 1
Binary Adder/Subtractor

★ M: Control Signal (Mode)

● M=0 F=x+y
● M=1 F=x–y
Overflow

★ Unsigned Binary xNumbers

x x1
3 2
x 0 y3 y2 y1
y0 0

FA FA FA FA

Carr C 4 C 3 C2 C1
y S
★ 2’s Complement Numbers
S 3 2 S1 S0

x3 x2 x1
x 0 y3 y2 y1
y0 0

FA FA FA FA

Overflo C4 C3 C2 C1
S3 S2 S1 S0
w
Magnitude Comparator

★ Compare 4-bit number to 4-bit number

● 3 Outputs: < , = , >
● Expandable to more number of bits

A3A2A1A0
B3 B2 B1 B0
Magnitude
Comparator

A<B A=B A>B

Magnitude Comparator
Magnitude Comparator

x7 x6 x5 x4 x3 x2 x1 x0
y7 y6 y5 y4 y3 y2 y1 y0

A3 A2 A1 A0 B3 B2 B1 B0 A3 A2 A1 A0 B3 B2 B1 B0
0 I(A>B) I(A>B)
1 Magnitude Magnitude
I(A=B) I(A=B)
0 I(A<B)Comparator I(A<B)Comparator
A<B A=B A>B A<B A=B A>B

A<B A=B A>B

Decoders

★ Extract “Information” from the codeOnly

★ Binary Decoder one
lamp
● Example: 2-bit Binary Number will
turn on

0 1
x1 0
Binary
x0 0 Decoder 0
0
 Decoders
★ 2-to-4 Line Decoder
★ Decoder produces midterm

y3

Decoder
I1

Binary
y2
y1
I0 y0

I 1 I 0 Y 3 Y2 Y1 Y0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0
Decoders

★ 3-to-8 Line Decoder

Y7
Y6

Decoder
I2 Binary
I1 Y5
I0 Y4

Y3
Y2

Y1
Y0
Decoders

★ “Enable” Control

Decoder
I1

Binary
Y3
I0 Y2
E
Y1
Y0
E I1 I 0 Y 3 Y2 Y1 Y0
0 x x 0 0 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 0 0 0
Decoders

★ Expansion I2 I 1 I 0

I 2 I 1 I 0 Y 7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0

Decoder
I0

Binary
0 1 0 0 0 0 0 0 1 0 0 Y3 Y7
I1 Y2 Y6
0 1 1 0 0 0 0 1 0 0 0 E
1 0 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0 Y1 Y5
Y0 Y4
1 1 0 0 1 0 0 0 0 0 0

Decoder
I0

Binary
1 1 1 1 0 0 0 0 0 0 0 Y3
I1 Y2
E
Y3
Y1
Y2
Y0
Decoders

★ Active-High / Active-Low
I 1 I 0 Y 3 Y2 Y1 Y0 I 1 I 0 Y 3 Y2 Y1 Y0
0 0 0 0 0 1 0 0 1 1 1 0
0 1 0 0 1 0 0 1 1 1 0 1
1 0 0 1 0 0 1 0 1 0 1 1
1 1 1 0 0 0 1 1 0 1 1 1
Decoder

Decoder
I1 I1
Binary

Binary
Y3 Y3
Y2 Y2
I0 I0
Y1 Y1
Y0 Y0
Implementation Using Decoders

★ Each output is a minterm

Binary
Decoder
★ All minterms are produced
★ Sum the required minterms Y
7
Y6
x I2
Example: Full Adder y I1 Y5
z I0 Y4
S(x, y, z) = ∑(1, 2, 4, 7)
C(x, y, z) = ∑(3, 5, 6, 7) Y3
Y2

Y1
Y0
S C
Implementation Using Decoders
Binary Binary
Decoder Decoder

Y7 Y7
Y6 Y6
x I2 x I2
y I1 Y5 y I1 Y5
z I0 Y4 z I0 Y4
Y3
Y3 Y2
Y2
Y1
Y1 Y0
Y0
S C
S C
Encoders

★ Put “Information” into code Only

★ Binary Encoder one
switch
● Example: 4-to-2 Binary Encoder should
be
activate
x1 d at a
x 3 x2 x1 y0
y1time
y1 0 0 0 0 0
x2 Binary
0 0 1 0 1
Encoder
y0 0 1 0 1 0
x3 1 0 0 1 1
Encoders

★ Octal-to-Binary Encoder (8-to-3)

I7
I7 I6 I5 I4 I3 I2 I1 I0 Y 2 Y1 Y0 I6

Encoder
0 0 0 0 0 0 0 1 0 0 0 I5

Binary
Y2
0 0 0 0 0 0 1 0 0 0 1 I4 Y1
0 0 0 0 0 1 0 0 0 1 0 I3 Y0
0 0 0 0 1 0 0 0 0 1 1 I2
0 0 0 1 0 0 0 0 1 0 0 I1
0 0 1 0 0 0 0 0 1 0 1 I0
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1
Encoder / Decoder Pairs

Binary Binary
Encod Decod
er er
I7
I6 Y7
I5 Y Y6
2 I2
I4 Y
1 I1 Y5
I3 Y
0 I0 Y4
I2
I1
I0 Y3
Y2

Y1
Y0
Multiplexers

S1 S 0 Y I0
0 0 I0 I1
MUX Y
0 1 I1 I2
1 0 I2 I3
S1 S 0
1 1 I3
Multiplexers

★ 2-to-1 MUX

I0
MUX Y
I1
S

★ 4-to-1 MUX

I0
I1
MUX Y
I2
I3
S1 S 0
Multiplexers

★ Quad 2-to-1 MUX

x3 I0
y3 MUX Y
I1
S

x2 I0
y2 MUX Y
I1
S A3
A2
I0 Y3
MUX Y A1
x1 I1
S
Y2
A0 MUX Y
y1 B3 1
Y0
B2
I0 B1
MUX Y
I1 B0
S S E
x0
y0 S
Multiplexers

★ Quad 2-to-1 MUX

A3
A2
Y3
A1 Y2
A0 MUX
B3
Y1
B2
Y0
B1
S E
B0
Extra
Buffers
Implementation Using Multiplexers

★ Example
F(x, y) = ∑(0, 1, 3)

x y F I0
1
0 0 1 1 I1
MUX Y F
0 1 1 0 I2
1 0 0 1 I3
S1 S 0
1 1 1
x y
Implementation Using Multiplexers

★ Example
F(x, y, z) = ∑(1, 2, 6, 7)
0 I0
x y z F 1 I1
0 0 0 0 1 I2
0 0 1 1 0 I3
Y F
0 1 0 1 0 I4 MUX
0 I5
0 1 1 0
1 I6
1 0 0 0 I7
1
1 0 1 0 S2 S 1 S 0
1 1 0 1
1 1 1 1 x y
z
Implementation Using Multiplexers

★ Example
F(x, y, z) = ∑(1, 2, 6, 7)

x y z F
0 0 0 0 z I0
F= z I1 F
0 0 1 1
z 0 I2
MUX Y
0 1 0 1
F= 1 I3
0 1 1 0 S1 S 0
z
1 0 0 0
F= x
1 0 1 0 0 y
1 1 0 1
F=
1 1 1 1 1
Implementation Using Multiplexers

★ 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 I0
0 0 0 1 1
0 0 1 0 0 D D I1
F=
0 0 1 1 1
D
D I2
0 1 0 0 1
F= 0 I3
0 1 0 1 0
D MUX Y F
0 1 1 0 0
F=
0 I4
0 1 1 1 0
0 D I5
1 0 0 0 0
1 0 0 1 0
F= 1 I6
0
1 0 1 0 0 F= 1 I7
1 0 1 1 1
1 1 0 0 1
D S2 S 1 S 0
F=
1 1 0 1 1 1
1 1 1 0 1 F=
1 1 1 1 1
A B
1
C
Multiplexer Expansion

★ 8-to-1 MUX using Dual 4-to-1 MUX

I0 I0
I1 I1
MUX Y
I2 I2
I3 I3
S1 S 0 I0
MUX Y Y
I1
I0 S
I4
I5 I1
MUX Y
I6 I2
I7 I3
S1 S 0

1 0
S2 S 1 0
S0
DeMultiplexers

Y3
Y2
I DeMUX Y
1

S S Y0
1 0

S1 S 0 Y3 Y 2 Y 1 Y 0
0 0 0 0 0 I
0 1 0 0 I 0
1 0 0 I 0 0
1 1 I 0 0 0
Multiplexer / DeMultiplexer Pairs

MU DeMU
X X
I7
I6 Y7
I5 Y6
I4
I3 Y I Y5
I2 Y4
I1
I0 Y3
Y2
S2 S 1 S 0 S2 S 1 S 0
Y1
Y0
Synchron
x2 x1 y2 y 1 y 0
ize
x0
DeMultiplexers / Decoders

Y3

Decoder
I1

Binary
Y2 Y3
I DeMUX Y I0 Y2
1
E
S S Y0
1 0
Y1
Y0
E I1 I 0 Y 3 Y2 Y1 Y0
S1 S 0 Y3 Y 2 Y 1 Y 0 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
Three-State Gates

★ Tri-State Buffer
C A Y
0 x Hi-Z
A Y
1 0 0
1 1 1
C
A Y
★ Tri-State Inverter
C
Three-State Gates

A C D Y
0 0 Hi-Z
Y 0 1 B
C
1 0 A
B 1 1 ?
Not
D Allowed
A
C A if C =
Y 1
=
B if C =
B 0
Three-State Gates

I
3

I
2
Y
I
1

I
0

Decoder
S I1 Binary Y3
S
1 I0 Y2
E0 E
Y1