Digital Logic Design

Chapter 4: Combinational Function and Circuits

2nd Semester BS Electronics

Instructor: Muhammad Asif

Chapter 2 - Part 1 1
Overview
 Functions and functional blocks
 Rudimentary logic functions
 Decoding
 Encoding
 Selecting
 Implementing Combinational Functions Using:
• Decoders and OR gates
• Multiplexers (and inverter)
• ROMs
• PLAs
• PALs
• Lookup Tables

Chapter 4 2
Functions and Functional Blocks
 The functions considered are those found to be
very useful in design
 Corresponding to each of the functions is a
combinational circuit implementation called a
functional block.
 In the past, many functional blocks were
implemented as SSI, MSI, and LSI circuits.
 Today, they are often simply parts within a
VLSI circuits.

Chapter 4 3
Rudimentary Logic Functions
 Functions of a single variable X
TABLE 4-1
 Can be used on the
Functions of One Variable
inputs to functional
blocks to implement X F=0 F=XF= X F=1

other than the block’s 0 0 0 1 1

intended function 1 0 1 0 1

V CC or V DD

1 F5 1 F5 1 X F5 X
(c)

0 F5 0 F5 0
X F5 X

(a) (b) (d)

Chapter 4 4
Multiple-bit Rudimentary Functions

 Multi-bit Examples:
A F3 A
3 2
1 F2 1 2 4 4 2:1 F(2:1)
F F
0 F1 0 1
0 (c)
A F0 A
(a) (b) 3
4 3,1:0 F(3), F(1:0)
 A wide line is used to represent F
a bus which is a vector signal (d)
 In (b) of the example, F = (F3, F2, F1, F0) is a bus.
 The bus can be split into individual bits as shown in (b)
 Sets of bits can be split from the bus as shown in (c)
for bits 2 and 1 of F.
 The sets of bits need not be continuous as shown in (d) for bits 3, 1, and
0 of F.

Chapter 4 5
Enabling Function
 Enabling permits an input signal to pass
through to an output
 Disabling blocks an input signal from passing
through to an output, replacing it with a fixed
value
 The value on the output when it is disable can
be Hi-Z (as for three-state buffers and
transmission gates), 0 , or 1 ENX F
 When disabled, 0 output (a)
 When disabled, 1 output
X
 See Enabling App in text F
EN

(b) Chapter 4 6
Decoding
 Decoding - the conversion of an n-bit input
code to an m-bit output code with
n m  2n such that each valid code word
produces a unique output code
 Circuits that perform decoding are called
decoders
 Here, functional blocks for decoding are
• called n-to-m line decoders, where m  2n, and
• generate 2n (or fewer) minterms for the n input
variables
Chapter 4 7
Decoder Examples
 1-to-2-Line Decoder A D0 D1
D0 5 A
0 1 0
1 0 1 A D1 5 A
 2-to-4-Line Decoder (a) (b)
A0
A1 A0 D0 D1 D2 D3
A1
0 0 1 0 0 0 D0 5 A 1 A 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1 D1 5 A 1 A 0

(a)
D2 5 A 1 A 0
 Note that the 2-4-line
made up of 2 1-to-2- D3 5 A 1 A 0
line decoders and 4 AND gates.
(b)
Chapter 4 8
Decoder Expansion
 General procedure given in book for any decoder with n
inputs and 2n outputs.
 This procedure builds a decoder backward from the
outputs.
 The output AND gates are driven by two decoders with
their numbers of inputs either equal or differing by 1.
 These decoders are then designed using the same
procedure until 2-to-1-line decoders are reached.
 The procedure can be modified to apply to decoders
with the number of outputs ≠ 2n

Chapter 4 9
 Decoder Expansion - Example 1
 3-to-8-line decoder
• Number of output ANDs = 8
• Number of inputs to decoders driving output ANDs = 3
• Closest possible split to equal
 2-to-4-line decoder
 1-to-2-line decoder
• 2-to-4-line decoder
 Number of output ANDs = 4
 Number of inputs to decoders driving output ANDs = 2
 Closest possible split to equal
• Two 1-to-2-line decoders

 See next slide for result

Chapter 4 10
Decoder Expansion - Example 1
 Result 4 2-input ANDs 8 2-input ANDs

D0
A0

D1

A1
D2

2-to-4-Line D3
decoder
D4

A2 D5

1-to-2-Line decoders D6

D7

3-to-8 Line decoder

Chapter 4 11
Decoder Expansion - Example 2
 7-to-128-line decoder
• Number of output ANDs = 128
• Number of inputs to decoders driving output ANDs = 7
• Closest possible split to equal
 4-to-16-line decoder
 3-to-8-line decoder
• 4-to-16-line decoder
 Number of output ANDs = 16
 Number of inputs to decoders driving output ANDs = 2
 Closest possible split to equal
• 2 2-to-4-line decoders
• Complete using known 3-8 and 2-to-4 line decoders

Chapter 4 12
 Decoder with Enable
 In general, attach m-enabling circuits to the outputs
 See truth table below for function
• Note use of X’s to denote both 0 and 1
• Combination containing two X’s represent four binary combinations
 Alternatively, can be viewed as distributing value of signal
EN
EN to 1 of 4 outputs
A 1

 In this case, called a

A
demultiplexer
0
D 0

EN A 1 A 0 D0 D1 D2 D3 D1

0 X X 0 0 0 0
1 0 0 1 0 0 0 D2
1 0 1 0 1 0 0
1 1 0 0 0 1 0
D3
1 1 1 0 0 0

(b)
Chapter 4 13
 Encoding
 Encoding - the opposite of decoding - the conversion
of an m-bit input code to a n-bit output code with n
m  2n such that each valid code word produces a
unique output code
 Circuits that perform encoding are called encoders
 An encoder has 2n (or fewer) input lines and n output
lines which generate the binary code corresponding to
the input values
 Typically, an encoder converts a code containing
exactly one bit that is 1 to a binary code corres-
ponding to the position in which the 1 appears.
Chapter 4 14
Encoder Example
 A decimal-to-BCD encoder
• Inputs: 10 bits corresponding to decimal
digits 0 through 9, (D0, …, D9)
• Outputs: 4 bits with BCD codes
• Function: If input bit Di is a 1, then the
output (A3, A2, A1, A0) is the BCD code for i,
 The truth table could be formed, but
alternatively, the equations for each of the
four outputs can be obtained directly.

Chapter 4 15
 Encoder Example (continued)
 Input Di is a term in equation Aj if bit Aj is 1
in the binary value for i.
 Equations:
A3 = D8 + D9
A2 = D4 + D5 + D6 + D7
A1 = D2 + D3 + D6 + D7
A0 = D1 + D3 + D5 + D7 + D9
 F1 = D6 + D7 can be extracted from A2 and A1
Is there any cost saving?
Chapter 4 16
Priority Encoder
 If more than one input value is 1, then the
encoder just designed does not work.
 One encoder that can accept all possible
combinations of input values and produce
a meaningful result is a priority encoder.
 Among the 1s that appear, it selects the
most significant input position (or the least
significant input position) containing a 1
and responds with the corresponding
binary code for that position.
Chapter 4 17
Priority Encoder Example
 Priority encoder with 5 inputs (D 4, D3, D2, D1, D0) - highest priority to most
significant 1 present - Code outputs A2, A1, A0 and V where V indicates at
least one 1 present.
No. of Min- Inputs Outputs
terms/Row D4 D3 D2 D1 D0 A2 A1 A0 V

1 0 0 0 0 0 X X X 0
1 0 0 0 0 1 0 0 0 1
2 0 0 0 1 X 0 0 1 1
4 0 0 1 X X 0 1 0 1
8 0 1 X X X 0 1 1 1
 Xs in16
input part1of table
X represent
X X 0 orX1; thus
1 table
0 entries
0 correspond
1 to
product terms instead of minterms. The column on the left shows that all
32 minterms are present in the product terms in the table

Chapter 4 18
Priority Encoder Example (continued)

 Could use a K-map to get equations, but

can be read directly from table and
manually optimized if careful:
A2 = D4
A1 = D4 D3 + D4 D3D2 = D4F1, F1 = (D3 + D2)
A0 = D4 D3 + D4 D3 D2D1 = D4(D3 + D2D1)
V = D4 + F1 + D1 + D0

Chapter 4 19
Selecting
 Selecting of data or information is a critical
function in digital systems and computers
 Circuits that perform selecting have:
• A set of information inputs from which the selection
is made
• A single output
• A set of control lines for making the selection
 Logic circuits that perform selecting are called
multiplexers
 Selecting can also be done by three-state logic or
transmission gates
Chapter 4 20
Multiplexers
 A multiplexer selects information from an
input line and directs the information to an
output line
 A typical multiplexer has n control inputs
(Sn 1, … S0) called selection inputs, 2n
information inputs (I2n 1, … I0), and one
output Y
 A multiplexer can be designed to have m
information inputs with m 2n as well as n
selection inputs
Chapter 4 21
2-to-1-Line Multiplexer
 Since 2 = 21, n = 1
 The single selection variable S has two values:
• S = 0 selects input I0
• S = 1 selects input I1
 The equation:
Y = SI0 + SI1
Enabling
 The circuit: Decoder Circuits

I0
Y
S
I1

Chapter 4 22
2-to-1-Line Multiplexer (continued)
 Note the regions of the multiplexer circuit shown:
• 1-to-2-line Decoder
• 2 Enabling circuits
• 2-input OR gate
 To obtain a basis for multiplexer expansion, we combine
the Enabling circuits and OR gate into a 2  2 AND-OR
circuit:
• 1-to-2-line decoder
• 2  2 AND-OR
 In general, for an 2n-to-1-line multiplexer:
• n-to-2n-line decoder
• 2n  2 AND-OR

Chapter 4 23
Example: 4-to-1-line Multiplexer
 2-to-22-line decoder
 22  2 AND-OR
Decoder
S1

4 3 2 AND-OR
S0
Decoder
S1

S0

Y
I1
Y

I2

I3

Chapter 4 24
Multiplexer Width Expansion
 Select “vectors of bits” instead of “bits”
 Use multiple copies of 2n  2 AND-OR in
parallel I 0,0
4 3 2 AND-OR

Y0

 Example:
.
.
.

4-to-1-line I 3,0 4 3 2 AND-OR

D0 I 0,1
A0
. Y1
quad multi- 2-to-4-Line decoder .
.
.
.
.
D3
plexer A1 I 3,1
I 0,2
4 3 2 AND-OR

Y2
.
.
.
I 3,2 4 3 2 AND-OR
I 0,3
Y3

I 3,3

Chapter 4 25
Other Selection Implementations
 Three-state logic in place of AND-OR
S0
I0

I1
S1

I2

I3

 Gate input cost = 14 compared to 22 (or

18) for gate implementation
Chapter 4 26
Other Selection Implementations
 Transmission Gate Multiplexer
S0
 Gate input S1

cost = 8
compared I0 TG
(S 0 5 0)

to 14 for TG
(S 1 5 0)

3-state logic
I1
TG
(S 0 5 1)

and 18 or 22 Y

for gate logic

I2
TG
(S 0 5 0)

TG
(S 1 5 1)

TG
I3 (S 0 5 1)

Chapter 4 27
Combinational Function Implementation
 Alternative implementation techniques:
• Decoders and OR gates
• Multiplexers (and inverter)
• ROMs
• PLAs
• PALs
• Lookup Tables
 Can be referred to as structured implementation
methods since a specific underlying structure is
assumed in each case

Chapter 4 28
Decoder and OR Gates
 Implement m functions of n variables with:
• Sum-of-minterms expressions
• One n-to-2n-line decoder
• m OR gates, one for each output
 Approach 1:
• Find the truth table for the functions
• Make a connection to the corresponding OR from the
corresponding decoder output wherever a 1 appears in
the truth table
 Approach 2
• Find the minterms for each output function
• OR the minterms together

Chapter 4 29
 Decoder and OR Gates Example
 Implement the following set of odd parity functions of
(A7, A6, A5, A3)
P1 = A7 +A5 +A3 A7 0 P1
P2 = A7 +A6 +A3 1
A6 2
+ +
P 4 = A7 A 6 A 5 A5 3
4
 Finding sum of A4 5 P2
6
minterms expressions 7
8
P1 = m(1,2,5,6,8,11,12,15) 9
P2 = m(1,3,4,6,8,10,13,15) 10
11
P4
P4 = m(2,3,4,5,8,9,14,15) 12
13
 Find circuit 14
15
 Is this a good idea?
Chapter 4 30
Multiplexer Approach 1
 Implement m functions of n variables with:
• Sum-of-minterms expressions
• An m-wide 2n-to-1-line multiplexer
 Design:
• Find the truth table for the functions.
• In the order they appear in the truth table:
 Apply the function input variables to the multiplexer inputs S n
 1, … , S0

 Label the outputs of the multiplexer with the output variables

• Value-fix the information inputs to the multiplexer
using the values from the truth table (for don’t cares,
apply either 0 or 1)

Chapter 4 31
Example: Gray to Binary Code
 Design a circuit to Gray Binary
ABC xyz
convert a 3-bit Gray 000 000
code to a binary code 100 001
110 010
 The formulation gives 010 011
the truth table on the 011 100
right 111 101
101 110
 It is obvious from this 001 111
table that X = C and the
Y and Z are more complex

Chapter 4 32
 Gray to Binary (continued)
 Rearrange the table so Gray Binary
that the input combinations ABC xyz
000 000
are in counting order 001 111
010 011
 Functions y and z can 011 100
100 001
be implemented using 101 110
a dual 8-to-1-line 110 010
multiplexer by: 111 101
• connecting A, B, and C to the multiplexer select inputs
• placing y and z on the two multiplexer outputs
• connecting their respective truth table values to the inputs
Chapter 4 33
Gray to Binary (continued)
0 D00 0 D10
1 D01 1 D11
1 D02 1 D12
0 D03 0 D13
0 D04 1 D14
Out Y Out Z
1 D05 0 D15
1 D06 0 D16
0 D07 1 D17
A S2 A S2 8-to-1
8-to-1
B S1 B S1
C S0 MUX C S0 MUX

 Note that the multiplexer with fixed inputs is identical to a

ROM with 3-bit addresses and 2-bit data!

Chapter 4 34
Multiplexer Approach 2
 Implement any m functions of n + 1 variables by using:
• An m-wide 2n-to-1-line multiplexer
• A single inverter
 Design:
• Find the truth table for the functions.
• Based on the values of the first n variables, separate the truth
table rows into pairs
• For each pair and output, define a rudimentary function of the
final variable (0, 1, X, X )
• Using the first n variables as the index, value-fix the
information inputs to the multiplexer with the corresponding
rudimentary functions
• Use the inverter to generate the rudimentary function X

Chapter 4 35
Example: Gray to Binary Code
 Design a circuit to Gray Binary
ABC xyz
convert a 3-bit Gray 000 000
code to a binary code 100 001
110 010
 The formulation gives 010 011
the truth table on the 011 100
right 111 101
101 110
 It is obvious from this 001 111
table that X = C and the
Y and Z are more complex

Chapter 4 36
 Gray to Binary (continued)
 Rearrange the table so that the input combinations are in
counting order, pair rows, and find rudimentary functions
Gray Binary Rudimentary Rudimentary
ABC xyz Functions of Functions of
C for y C for z
000 000
F=C F=C
001 111
010 011
F=C F=C
011 100
100 001
F=C F=C
101 110
110 010
F=C F=C
111 101

Chapter 4 37
 Gray to Binary (continued)
 Assign the variables and functions to the multiplexer inputs:
C D00 C D10
C D01 C D11
C C
C D02 Out Y C D12 Out Z
C D03 C D13

A S1 8-to-1 A S1 8-to-1
B S0 MUX B S0 MUX
 Note that this approach (Approach 2) reduces the cost by almost
half compared to Approach 1.
 This result is no longer ROM-like
 Extending, a function of more than n variables is decomposed
into several sub-functions defined on a subset of the variables.
The multiplexer then selects among these sub-functions.

Chapter 4 38
Read Only Memory
 Functions are implemented by storing the truth
table
 Other representations such as equations more
convenient
 Generation of programming information from
equations usually done by software
 Text Example 4-10 Issue
• Two outputs are generated outside of the ROM
• In the implementation of the system, these two functions
are “hardwired” and even if the ROM is
reprogrammable or removable, cannot be corrected or
updated

Chapter 4 39
Programmable Array Logic
 There is no sharing of AND gates as in the
ROM and PLA
 Design requires fitting functions within the
limited number of ANDs per OR gate
 Single function optimization is the first step
to fitting
 Otherwise, if the number of terms in a
function is greater than the number of
ANDs per OR gate, then factoring is
necessary
Chapter 4 40
Programmable Array Logic Example
 Equations: F1 = A B C + AB C+ A B C + ABC
F2 = AB + BC + AC
 F1 must be AND Inputs
Product
factored term A B C D W Outputs

since four 1 0 0 1 — — W = A BC
terms 2
3
1
—
1
—
1
—
—
—
—
—
+ ABC

 Factor out 45 1
0
0
1
0
0
—
—
—
—
F1 = X = A B C
+ AB C + W
last two 6 — — — — 1

terms as W 78 1
—
1
1
—
1
—
—
—
—
F2 = Y
9 1 — 1 — — = AB + BC +AC
10 — — — — —
11 — — — — —
12 — — — — —

Chapter 4 41
Programmable Array Logic Example
AND gates inputs
Product A A B B C C D D W W
term
1 X X X

2 X X X W

3 X

A
All fuses intact
4 X X X (always 5 0)

5 X X X F1

6 X

7 X X

8 X X F2

9 X X

10

11

12
X Fuse intact
D
1 Fuse blown

A A B B C C D D W W Chapter 4 42
Programmable Logic Array
 The set of functions to be implemented must fit the
available number of product terms
 The number of literals per term is less important in
fitting
 The best approach to fitting is multiple-output, two-
level optimization (which has not been discussed)
 Since output inversion is available, terms can
implement either a function or its complement
 For small circuits, K-maps can be used to visualize
product term sharing and use of complements
 For larger circuits, software is used to do the
optimization including use of complemented functions

Chapter 4 43
Programmable Logic Array Example
BC B BC B
 K-map 00 01 11 10 00 01 11 10
A A
specification
0 0 1 0 1 0 0 0 1 0
 How can this
be implemented A 1 1 0 0 0 A 1 0 1 1 1

with four terms? C C

 Complete the F1 5 A BC + A B C + A B C F2 5 AB+ AC+ BC
F1 5 AB + AC + BC + A B C F2 5 AC + AB+ B C
programming table
PLA programming table

Outputs
Product Inputs ( ) (T)
term A B C F1 F2

AB 1 1 1 – 1
AC 2 1 – 1 1
BC 3 – 1 1 1
4 –
Chapter 4 44
Programmable Logic Array Example
A

X X 1 X X

X X 2 X X
X Fuse intact
1 Fuse blown
X X 3 X X

X X X 4 X

C C B B A A X 0
X 1

F1

F2

Chapter 4 45
Lookup Tables
 Lookup tables are used for implementing logic in
Field-Programmable Gate Arrays (FPGAs) and
Complex Logic Devices (CPLDs)
 Lookup tables are typically small, often with four
inputs, one output, and 16 entries
 Since lookup tables store truth tables, it is
possible to implement any 4-input function
 Thus, the design problem is how to optimally
decompose a set of given functions into a set of 4-
input two- level functions.
 We will illustrate this by a manual attempt
Chapter 4 46
Lookup Table Example
 Equations to be implemented:
F1(A,B,C,D,E) = A D E + B D E + C D E
F2(A,B,D,E,F) = A E D + B D E + F D E
 Extract 4-input function:
F3(A,B,D,E) = A D E + B D E
F1(C,D,E,F3) = F3 + C D E
F2(D,E,F,F3) = F3 + F D E
 The cost of the solution is 3 lookup tables

Chapter 4 47
Terms of Use
 © 2004 by Pearson Education,Inc. All rights reserved.
 The following terms of use apply in addition to the standard Pearson
Education Legal Notice.
 Permission is given to incorporate these materials into classroom
presentations and handouts only to instructors adopting Logic and
Computer Design Fundamentals as the course text.
 Permission is granted to the instructors adopting the book to post these
materials on a protected website or protected ftp site in original or
modified form. All other website or ftp postings, including those
offering the materials for a fee, are prohibited.
 You may not remove or in any way alter this Terms of Use notice or
any trademark, copyright, or other proprietary notice, including the
copyright watermark on each slide.
 Return to Title Page

Chapter 4 48