Digital Circuits

Design
Dr. Omar A. M. Aly
Dr. Diaaeldin Abdelrahman
diaaeldin@aun.edu.eg
 Lecture-Set 4:
Combinational
Logic
Dr. Omar A. M. Aly
Dr. Diaaeldin Abdelrahman
diaaeldin@aun.edu.eg

M. M. Mano, “Digital Design With an Introduction to the Verilog HDL,” 5th Edition, Pearson
Education, 2013.
Outline
Introduction
Combinational Circuits
Analysis Procedure
Design Procedure
Binary Adder-Subtractor
Decoders
Encoders
Multiplexers

Electronic Devices and Circuits Slide 3

Introduction
Logic circuits for digital systems may be combinational or sequential
 A combinational circuit consists of logic gates whose outputs at any time
are determined from only the present combination of inputs

A combinational circuit performs an operation that can be specified

logically by a set of Boolean functions

The diagram of a combinational circuit has logic gates with no feedback

paths or memory elements

Digital Circuits Design Slide 4

COMBINATIONAL CIRCUITS
The n input binary variables come from an external source
The m output variables are produced by the internal combinational logic
circuit and go to an external destination

Each input and output variable exists physically as an analog signal whose
values are interpreted to be a binary signal that represents logic 1 or logic 0

Digital Circuits Design Slide 5

COMBINATIONAL CIRCUITS
Analysis
o Given a circuit, find out its function
o Function may be expressed as:
♦ Boolean function
♦ Truth table
Design
o Given a desired function, determine its circuit
o Function may be expressed as:
♦ Boolean function
♦ Truth table
Digital Circuits Design Slide 6
Analysis Procedure: Boolean Functions Approach
To obtain the output Boolean functions from a logic diagram:
1) Label all gate outputs that are a function of input variables with arbitrary
symbols but with meaningful names. Determine the Boolean functions for
each gate output
2) Label the gates that are a function of input variables and previously
labeled gates with other arbitrary symbols. Find the Boolean functions for
these gates
3) Repeat the process outlined in step 2 until the outputs of the circuit are
obtained
4) By repeated substitution of previously defined functions, obtain the
output Boolean functions in terms of input variables

Digital Circuits Design Slide 7

Analysis Procedure: Boolean Functions Approach
A F1=AB'C'+A'BC'+A'B'C+ABC
B
F1
C T2=ABC
A T1=A+B+C
B T3=AB'C'+A'BC'+A'B'C
C
A
B F’2=(A’+B’)(A’+C’)(B’+C’)

A
F2
C
F2=AB+AC+BC F2=AB+AC+BC
B
C

Digital Circuits Design Slide 8

Analysis Procedure: Truth Table Approach
To obtain the truth table directly from the logic diagram without going
through the derivations of the Boolean functions:
1) Determine the number of input variables in the circuit. For n inputs, form
the 2n possible input combinations and list the binary numbers from 0 to
(2n - 1) in a table
2) Label the outputs of selected gates with arbitrary symbols.
3) Obtain the truth table for the outputs of those gates which are a function
of the input variables only
4) Proceed to obtain the truth table for the outputs of those gates which are
a function of previously defined values until the columns for all outputs
are determined

Digital Circuits Design Slide 9

Analysis Procedure: Truth Table Approach

A B C F1 F2
A =0
0
B =0
C =0
0
F1 0 0 0 0 0
A =0
B =0 0 0
C =0
1
A =0 0
B =0

A =0 0 0 F2
C =0

B =0 0
C =0

Digital Circuits Design Slide 10

Analysis Procedure: Truth Table Approach

A B C F1 F2
A =0 0 1
0 0 0 0 0
B =0
F1
C =1 0 0 1 1 0
A =0 1
B =0 1
C =1
1
A =0 0
B =0

A =0 0 0
F2
C =1

B =0 0
C =1

Digital Circuits Design Slide 11

Analysis Procedure: Truth Table Approach

A =0
A B C F1 F2
0 1
B =1
C =0
F1 0 0 0 0 0
A =0
B =1
1 1 0 0 1 1 0
C =0
A =0 0
1 0 1 0 1 0
B =1

A =0 0 0
F2
C =0

B =1 0
C =0

Digital Circuits Design Slide 12

Analysis Procedure: Truth Table Approach

A =0 0
B =1 0
C =1
F1 A B C F1 F2
A =0
B =1
1 0 0 0 0 0 0
C =1
A =0 0
0 0 0 1 1 0
B =1
0 1 0 1 0
A =0 0 1
F2
C =1 0 1 1 0 1
B =1 1
C =1

Digital Circuits Design Slide 13

Analysis Procedure: Truth Table Approach

A =1 0 1
A B C F1 F2
B =0
F1
C =0 0 0 0 0 0
A =1 1 1
B =0
C =0
0 0 1 1 0
1
A =1
B =0
0 0 1 0 1 0
A =1 0 0
F2
0 1 1 0 1
C =0

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

Digital Circuits Design Slide 14

Analysis Procedure: Truth Table Approach

A B C F1 F2
A =1
B =0
0 0
F1
0 0 0 0 0
C =1
A =1 1 0
0 0 1 1 0
B =0
C =1
0
0 1 0 1 0
A =1 0
B =0 0 1 1 0 1
A =1
C =1
1 1
F2 1 0 0 1 0
B =0
C =1
0 1 0 1 0 1

Digital Circuits Design Slide 15

Analysis Procedure: Truth Table Approach

A B C F1 F2
A =1 0 0
B =1
C =0
F1 0 0 0 0 0
A =1
B =1
1 0
0 0 1 1 0
C =0
0 0 1 0 1 0
A =1 1
B =1 0 1 1 0 1
A =1 0 1
C =0
F2 1 0 0 1 0
B =1
C =0
0 1 0 1 0 1
1 1 0 0 1

Digital Circuits Design Slide 16

Analysis Procedure: Truth Table Approach

A =1
A B C F1 F2
1 1
B =1
C =1
F1 0 0 0 0 0
A =1
B =1
1 0 0 0 1 1 0
C =1
A =1 1
0 0 1 0 1 0
B =1
0 1 1 0 1
A =1 1 1
F2
C =1 1 0 0 1 0
B =1 1
C =1 1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Digital Circuits Design Slide 17

Analysis Procedure: Truth Table Approach
B

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

1 0 1 0 1 0 0 1 0
1 1 0 0 1 A 0 1 1 1
C
1 1 1 1 1
F2=AB+AC+BC
Digital Circuits Design Slide 18
Design Procedure
Given a problem statement:
1) Determine the number of inputs and outputs
2) Derive the truth table
3) Simplify the Boolean expression for each output
4) Produce the required circuit

Digital Circuits Design Slide 19

Design Procedure
Example: Design a circuit to convert a “BCD” code to “Excess 3” code

 4-bits  4-bits
?
 0-9 values  Value+3

Digital Circuits Design Slide 20

Design Procedure
A B C D w x y z Solution: BCD-to-Excess 3 Converter
0 0 0 0 0 0 1 1 C C
0 0 0 1 0 1 0 0 1 1 1
0 0 1 0 0 1 0 1 1 1 1 1
0 0 1 1 0 1 1 0 x x x x
B x x x x
B
0 1 0 0 0 1 1 1 A 1 1 x x
A 1 x x
0 1 0 1 1 0 0 0 D D
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0 w = A+BC+BD x = B’C+B’D+BC’D’
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
C C
1 0 1 0 x x x x 1 1 1 1
1 0 1 1 x x x x 1 1 1 1
x x x x
B x x x x
B
1 1 0 0 x x x x A A
1 x x 1 x x
1 1 0 1 x x x x
1 1 1 0 x x x x D D
1 1 1 1 x x x x y = C’D’+CD z = D’
Digital Circuits Design Slide 21
Design Procedure
A B C D w x y z Solution: BCD-to-Excess 3 Converter
0 0 0 0 0 0 1 1 A
0 0 0 1 0 1 0 0 w
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 x
0 1 1 0 1 0 0 1 B

0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0 C y
1 0 1 0 x x x x
1 0 1 1 x x x x
D z
1 1 0 0 x x x x
1 1 0 1 x x x x w = A + B(C+D) y = (C+D)’ + CD
1 1 1 0 x x x x
1 1 1 1 x x x x z = D’
x = B’(C+D) + B(C+D)’
Digital Circuits Design Slide 22
Design Procedure
Example: Design a seven-segment decoder
a
w a
b
x c f b
d g
y ? e
z f
g e c
BCD code
d

Digital Circuits Design Slide 23

Design Procedure
w x y z a b c d e f g
Solution: a seven-segment decoder 0 0 0 0 1 1 1 1 1 1 0
y 0 0 0 1 0 1 1 0 0 0 0
0 0 1 0 1 1 0 1 1 0 1
a
0 0 1 1 1 1 1 1 0 0 1
1 1 1 0 1 0 0 0 1 1 0 0 1 1 f b
1 1 1 0 1 0 1 1 0 1 1 0 1 1 g
x 0 1 1 0 1 0 1 1 1 1 1
x x x x
w 0 1 1 1 1 1 1 0 0 0 0
e c
1 1 x x 1 0 0 0 1 1 1 1 1 1 1
z 1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 x x x x x x x
d
a = w + y + xz + x’z’ 1 0 1 1 x x x x x x x
1 1 0 0 x x x x x x x
1 1 0 1 x x x x x x x
b=... c=... d=... 1 1 1 0 x x x x x x x
1 1 1 1 x x x x x x x

Digital Circuits Design Slide 24

Binary Adder
 Half Adder x
x
oAdds 1-bit plus 1-bit HA
S + y
y C ───
oProduces Sum and Carry C S

x y C S
0 0 0 0 x S
0 1 0 1
1 0 0 1 C
y
1 1 1 0

Digital Circuits Design Slide 25

Binary Adder
Full Adder
oAdds 1-bit plus 1-bit plus 1-bit
oProduces Sum and Carry

x
x S + y
y FA
z C + z
───
C S

Digital Circuits Design Slide 26

Binary Adder
Full Adder y
0 1 0 1
x y z x 1 0 1 0
C S
z
0 0 0 0 0 S = xy'z'+x'yz'+x'y'z+xyz = x  y  z
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
y
1 0 0 0 1 0 0 1 0
1 0 1 1 0 x 0 1 1 1
1 1 0 1 0 z
1 1 1 1 1 C = xy + xz + yz

Digital Circuits Design Slide 27

Binary Adder
Full Adder
x S
y HA HA
S = xy'z'+x'yz'+x'y'z+xyz
= (x  y)  z z C

x
C = xy + xz + S
yz
y
C

Digital Circuits Design Slide 28

DECODERS
Extract “Information” from a code

A decoder is a combinational circuit that converts binary information from

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

If the n-bit coded information has unused combinations, the decoder may
have fewer than 2n outputs

n -to- m -line decoders is one the known one where

Digital Circuits Design Slide 29

Decoders: 2-bit Binary Decoder
 Extract information from the code

Digital Circuits Design Slide 30

Decoders: 2-bit Binary Decoder
Also known as 2-to-4 line Decoder

Digital Circuits Design Slide 31

Decoders: 3-to-8 Line Decoder
Eight outputs each representing one of the minterms of the three input
variables
Truth table

Digital Circuits Design Slide 32

Decoders: 3-to-8 Line Decoder

Digital Circuits Design Slide 33

Decoder with enable input
 Enable Control

Digital Circuits Design Slide 34

Decoder with enable input with output low
Some decoders are constructed with NAND gates

Enable with Active low

Digital Circuits Design Slide 35

Decoder with enable input with output low
Some decoders are constructed with NAND gates

Digital Circuits Design Slide 36

Decoder Expansion
How to extent a 2-to-4 line decoder to 3-to-8 line decoder ?
I2 I1 I0

I2 I1 I0 Y7 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 Y3 Y7

Decoder
I0

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

Decoder
I0

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

Digital Circuits Design Slide 37

Decoder Expansion
4 * 16 decoder constructed with two 3 * 8 decoders

Digital Circuits Design Slide 38

Uses for Decoders
 Binary number might serve to select some operation Number might
encode a CPU Instruction.
Decoder lines might select add, or subtract, or multiply, etc.

Number might encode a Memory Address To read or write a particular

location in memory.

Decoders may be used to implement Boolean Functions.

Digital Circuits Design Slide 39

Decoders
Example: Implement a full-adder circuit with a decoder.
Solution: From the truth table of the full-adder, we obtain the functions for
this combinational circuit in sum of minterms:

Digital Circuits Design Slide 40

ENCODERS
Put “Information” into code
An encoder is a digital circuit that performs the inverse operation of a
decoder.
An encoder has 2n (or fewer) input lines and n output lines

Example: 4 to 2 Encoder

Digital Circuits Design Slide 41

ENCODERS
From Truth table, we can write the Boolean functions for each output as
A1 =Y3 +Y2 A0 =Y3+Y1

Inputs Outputs
Y3 Y2 Y1 Y0 A1 A0
0 0 0 1 0 0
0 0 1 0 0 1
0
0 1 0 0 1

1 0 0 0 1 1

Digital Circuits Design Slide 42

Octal-to-Binary Encoder (8-to-3)
I7 I6 I5 I4 I3 I2 I1 I0 Y2 Y1 Y0
I7
0 0 0 0 0 0 0 1 0 0 0 I6
0 0 0 0 0 0 1 0 0 0 1 I5

Encoder
Y2

Binary
0 0 0 0 0 1 0 0 0 1 0 I4
0 0 0 0 1 0 0 0 0 1 1 Y1
I3 Y0
0 0 0 1 0 0 0 0 1 0 0 I2
0 0 1 0 0 0 0 0 1 0 1 I1
0 1 0 0 0 0 0 0 1 1 0 I0 I7
1 0 0 0 0 0 0 0 1 1 1 I6 Y2
I5
Y2  I 7  I 6  I 5  I 4 I4
I3 Y1
Y1  I 7  I 6  I 3  I 2 I2
I1
Y0  I 7  I 5  I 3  I1 I0 Y0

Digital Circuits Design Slide 43

Application: Encoder / Decoder Pairs
Binary Binary
Encoder Decoder

I7 Y7
I6 Y6
I5 Y5
Y2 I2 Y4
I4 Y1 I1 Y3
I3 Y0 I0 Y2
I2
I1 Y1
I0 Y0

Digital Circuits Design Slide 44

Multiplexers (MUX)

Digital Circuits Design Slide 45

Multiplexers (MUX)

Digital Circuits Design Slide 46

Multiplexers (MUX): 2-to-1 Line Multiplexer

Digital Circuits Design Slide 47

Multiplexers (MUX)

Digital Circuits Design Slide 48

Multiplexers (MUX)
Quad 2-to-1 MUX

Y3
B3

Y2
B2
Y1
B1
Y0
B0

Digital Circuits Design Slide 49

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 50

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 51

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 52

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 53

Example Alternate Implementation of Binary Adder

Digital Circuits Design Slide 54

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 55

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 56

MUX-based Combinational Logic Implementation

Digital Circuits Design Slide 57

Three-State gate

Digital Circuits Design Slide 58

Three-State gate
Mux using Three-state gate

Digital Circuits Design Slide 59

DeMultiplexers (DeMUX)

Digital Circuits Design Slide 60

DeMultiplexers (DeMUX) Vs Decoders
Decoder produces a “1” on one of the 2n outputs and “0” elsewhere
DeMUX transmits data to one of the 2n outputs and “0” elsewhere

Digital Circuits Design Slide 61

Application Mux/De-Mux Pair
 Serializer/De-Serializer

Digital Circuits Design Slide 62

 Thanks and Feedback

Electronic Devices and Circuits Slide 63