COE 202: Digital Logic Design

Courtesy of Dr. Radwan E Abdel-Aal

Unit 13
Logic and Computer Design Fundamentals
• Programmable Logic
Chapter
(Section 6-8)
3 – Combinational
Logic Design
• Memory Devices: RAM and ROM
Part 1 – Implementation Technology and Logic
(Supplementary notes: lesson 6_2)
Design
Charles Kime & Thomas Kaminski
© 2004 Pearson Education, Inc.
Terms of Use
(Hyperlinks are active in View Show mode)
Programmable Implementation Technologies:
Overview
 Why programmable logic?
 Programmable logic techniques and
technologies
 Programmable Logic Devices:
• Read-Only Memory (ROM)
• Programmable Array Logic (PAL)
• Programmable Logic Array (PLA)
• VLSI Programmable Logic Devices
(Field Programmable Gate Arrays- FPGA)

Chapter 3 - Part 1 2
 Why Programmable Logic?
 Facts:
• It is most economical to produce an IC in large volumes
• But:
 Many situations require only small volumes of ICs
 Many situations require changes to be done in the
field, e.g. Firmware of a product under development
 A programmable logic device can be:
• Produced in large volumes
• Programmed to implement many different low-volume
designs

Chapter 3 - Part 1 3
 Programmable Logic - Additional Advantages

 Many programmable logic devices are

field-programmable, i. e., can be programmed in the field
by the user - outside of the manufacturer’s environment
 Nowadays, most programmable logic devices are erasable
and reprogrammable (i.e. can programmed many times)
• Allows “updating” a device or firmware, correction of errors
• Allows reuse the device for a different design - re-usability!

Concept of
Logic Programming

Locations of connections
determine the logic function implemented
Chapter 3 - Part 1 4
 Hardware Programming Technologies
 In the Factory - Cannot be erased/reprogrammed by user
• Mask programming (changing the VLSI mask) during
manufacturing
 Programmable only once
• Fuse
• Anti-fuse
 Reprogrammable (Erased & Programmed many times)
• Volatile - Programming lost if chip power lost
 Single-bit storage element
• Non-Volatile - Programming survives power loss
 UV Erasable
 Electrically Erasable
• Flash (as in Flash Memory)
Chapter 3 - Part 1 5
Programmable Logic Configurations:
All use AND-OR structure- differ in which is programmable
 Programmable Read Only Memory (PROM) -
fixed array of AND gates and a programmable
array of OR gates
 Programmable Array Logic (PAL) -
programmable array of AND gates feeding a
fixed array of OR gates.
 Programmable Logic Array (PLA) -
programmable array of AND gates feeding a
programmable array of OR gates.
How many
Possibilities?
Fixed or Programmable
Connections
Fixed or Programmable
Connections 6
ROM, PAL and PLA Configurations

Fixed Fixed Programmable

Inputs Programmable Outputs
AND array
Connections (decoder) Connections OR array

PROM (a) Programmable read-only memory (PROM)

Programmable Programmable Fixed Fixed

Inputs Outputs
Connections AND array Connections OR array

PAL (b) Programmable array logic (PAL) device

Programmable Programmable Programmable Programmable

Inputs Outputs
Connections AND array Connections OR array

PLA (c) Programmable logic array (PLA) device

Chapter 3 - Part 1 7
 Wiring Conventions
for Programmable Logic

• We deal with a large number of gates and gate inputs

• Need a more concise way of expressing gate circuits
graphically
Inputs (literals)
A A B B

Inputs 1 wire X X

X marks a connection, i.e. an input to the OR

Output = ?

Chapter 3 - Part 1 8
 Read Only Memory (ROM)
 Data stored in a ROM is non-volatile
 i.e. Once written, this data is permanently stored
until erased or changed through re-programming
(if applicable)
 The ROM has n input lines for the address and m
output data lines
 So, Total memory capacity of a ROM is 2n x m bits
 ROMs do not have input lines as a write operation
does not exist in them
 Programmable ROMs receive data to be
programmed on the output lines
 Generally, system-level programs that need to be
accessed frequently and at power up access are
stored in the computer’s ROM, e.g. the BIOS
firmware
 1. Read Only Memory (ROM)
Programmable sum of (fixed) minterms
 Example: 8 X 4 PROM (n = 3 input lines, m = 4 output lines)
 The fixed "AND" array is a 8 X 3-input fixed ANDs give all 8 minterms
m0
“decoder” with 3 inputs and 8 D0 X X X
outputs implementing minterms D1

8 Minterms
D2 X X
 The programmable "OR“ D3 X

array uses a single line to A A2 D4 X

D5
X X
represent all inputs to an B LSB A1 D6 X
C A0 D7
OR gate. An “X” in the n I/Ps m7
array corresponds to attaching the
m O/Ps
minterm to the OR
 Read Example: For input (A2,A1,A0) F3 F2 F1 F0
2n x m Programmable
= 010, output is (F3,F2,F1,F0 ) = 1001. Connections
 What are functions F3, F2 , F1 and F0 in terms of (A2, A1, A0)?
Chapter 3 - Part 1 10
 Read Only Memory (ROM): n i/ps to m o/ps
2n locations x m bits each
 Read Only Memories (ROM) have:
• n input (address) lines  2n locations  2n decoded minterms
• m output lines (word width)
 Fixed array of 2n AND gates implementing all the N-literal minterms.
 Programmable OR Array with m outputs lines to form up to
m expressions, each being a sum of selected minterm.
 The program for a PROM is simply the multiple-output truth table
to be implemented
• If a 1 entry, a connection is made to the corresponding minterm for
the corresponding output
• If a 0, no connection is made
 Can be viewed as a memory with the inputs as addresses of data
(output values), hence ROM or PROM names!
Device on previous slide is an 8 x 4 memory (8 locations, each 4 bits)
 Truth table is a listing of the memory contents
Chapter 3 - Part 1 11
 Read Only Memory (ROM)
Advantages/Limitations
 Advantages:
• Can implement any function (all the minterms are available)
• Program is derived directly from the truth table
(uses the canonical form)
 Disadvantages:
• Becomes complex for a large number of inputs n
(# of ANDs = 2n, each n-input wide)
• Does not support multi-level circuits (no outputs brought
back as inputs)

Chapter 3 - Part 1 12
 Types of ROM Devices
 Simply ROM: Programmed only once and by the
manufacturer (in factory), based on the client’s truth table
 PROM: A ROM programmable only once by the user
(in the field). The user blows fuses to remove unwanted
connections. This process is irreversible and hence
device is programmed only once
 EPROM: Erasable, Programmable ROMs. Can have their
data erased using Ultraviolet light and reprogrammed.
The user can then reprogram the ROM many times using
special programmers Off- situ.

Off-situ: Remove from

computer to erase/program An
EPROM
 Types of ROM, Contd.
 EEPROMs: Electrically Erasable Programmable ROMs.
Have memory cells that can be erased and
reprogrammed by exposure to electrical signals.
Erasure/Programming is now much easier and in-situ.
The processor can now “write” into the EEPROM.
 Flash memory devices:
• Memory cells are erased in blocks not one-by-one as in
EEPROMs  Shorter life but faster operation
Read Only Memory (ROM)
Naming Conventions determined by Programming Technology

Programming ROM Name Remarks

Technology
Mask ROM Programmed at
manufacturing only
Fuse/Antifuse PROM Programmed (only
once) by the user
EPROM Erased and
Floating Gate Programmed by user
(UV Erasable) many times- off situ

Electrically EEPROM Erased and

Programmed by user
Erasable many times- in situ

Chapter 3 - Part 1 15
 ROM-based Designs
 Combinational Circuits:
ROMs can be used to implement combinational circuits
from their truth tables
(i.e. SOm form, without the need for minimization to SOP)

 Sequential Circuits:
Use ROMs to design the combinational part of the
sequential circuit
ROM-based Designs:
Combinational Circuits
Example 1: Implement the following two combinational functions using a
ROM
F1 (X,Y) = ∑ m (1,2,3)
F2 (X,Y) = ∑ m (0,2)

Solution:
 Specifying the ROM required:
ROM has n = 2 inputs ( 22 = 4 locations)
and m = 2 outputs ( Each location has 2 bits) … 4 x 2 bit ROM
 Specifying the ROM data content (to be programmed into the ROM):
Directly from the truth table of the two functions

Index
0
1
2
3
ROM-based Designs:
Combinational Circuits
Example 2: X2 look-up table, X is 3-bit binary number

 Specification: Use a ROM to implement a combinational circuit that

accepts a 3-bit binary number at the input and generates its square at
the output.

 Formulation:
8 x 6 bits ROM, Truth Table 
8
 Observations on the truth table:
Locations
1. Output B0 = Input A0
2. Output B1 = Always 0
6 bits
No need to ‘store’ data for B0 and B1
This reduces the size of the ROM required from 8 x 6 bits to 8 x 4 bits
ROM-based Designs:
Combinational Circuits
Example 2, Continued

Truth Table for Reduced ROM

8
Locations

4 bits
Implementations of the X2 Look-up Table:
ROM-based Designs:
Sequential Circuits
Conventional Design Individual FFs

ROM-Register
Based Design
ROM-based Designs:
Sequential Circuits
Example: Design a sequential circuit that has the following
State Transition Table Using a ROM and a Register
Q1+ = Σm (1, 2, 5, 6)
Q2+ = Σm (4, 6)
Y: (Q1, Q2, X) = Σm (3, 7)
8
Locations

ROM inputs ROM Outputs

(Address) (Data)

3 bits 3 bits
ROM-based Designs:
Sequential Circuits
The ROM Required

Organization

Truth Table
ROM-based Designs:
Sequential Circuits
Implementation

:
2. Programmable Array Logic (PAL)
Sum of a fixed number of products
AND gates inputs
Programmable
 4-input, 4-output PAL 0 1 2 3 4 5 6 7 8 9
X
Product 1
with fixed, 3-input OR term
X
Fixed
X
2 F1
terms 3

 What are the equations I1 A

O/P made available
for F1 through F4?
X X X
4
X X as I/P  support
5 F2
F1 = A B + C X X multilevel circuits
6
F2 = A B C + AC + AB
I2 B
F3 = 7
X X

F4 = 8
X X
F3
X
9

What if a function uses I3 C

more than 3 products?

X X
10

Implement as multi-
X X
11 F4

level
X
12
I4

0 1 2 3 4 5 6 7 8 9
Chapter 3 - Part 1 24
 Programmable Array Logic (PAL)

 PAL is the opposite of the ROM, having a set of

programmable ANDs combined with a set of fixed
ORs- Here programmable means selectable I/Ps
 Advantages
• For given internal complexity, a PAL can support larger N
and M than a PROM
• PAL has outputs from OR terms fed as internal inputs to all
AND terms, allowing implementation of multi-level circuits
• Some PALs have outputs that can be complemented,
allowing expressions in terms of a POS: F = F
SOP

 Disadvantages
• Has only a limited number of products (= # of ANDs = # of
inputs to an OR). If function needs more product terms it can
not be implemented directly in 2-level logic
Chapter 3 - Part 1 25
 Programmable Array Logic (PAL), Contd.

 There is no sharing of the AND gates Here: Max of 3 products/section

as in the ROM and PLA. i.e. AND AND gates inputs

gate outputs (product terms) are not

Product A A B B C C D D WW
term
1

available for connecting to all the ORs 2 W

(Sums) 3 X

 Design requires fitting functions within A

the limited number of ANDs per

All fuses intac
4 (always5 0)

output (i.e. per OR gate) 5 F1

 We start by single function B

6

optimization, trying to fit the function 7

into one section (one SOP) 8 F2

 If the number of terms in a function is 9

greater than the number of ANDs per C

OR gate (products/section), then we 10

use more than one section to 11

implement an output (multilevel) 12

XFuse intact

 If several outputs use the same

D
1Fuse blown

A A B B C C D D WW

product, this reduces circuit cost Chapter 3 - Part 1 26

 Programmable Array Logic (PAL)
Example
 Equations: F1 = AB C + A B C + A B C + ABC = W
F2 = AB + BC + AC
 F1 must be AND Inputs PAL Programming Table
factored term
Product
A B C D W Outputs

since four 1 Take Compl. 0 0 1 — — W = A B C Remove both connections

2 Take True. 1
terms (> 3) 3 Full gate not used.— 1— 1— — —
—
—
+ ABC
 Factor out 4 See next slide 1 0 0 — — F1 = X = AB C
5 0 1 0 — —
+ AB C + W
last two 6 — — — — 1

terms as W 78 1
—
1
1
—
1
—
—
—
—
F2 = Y
9 1 — 1 — — = AB + BC +AC
PAL comes with all
Connections made. 10 — — — — —
Connections that are 11 — — — — —
12 — — — — —
not needed must be
removed How many connections are removed for productChapter
1?, for 3product
- Part 1 3? 27
Programmable Array Logic
Example
AND gates inputs
Product A A B B C C D D W W
term
1 X X X

For an unused product, 2 X X X W

Leave all connections intact 3 X

Why? A
All fuses intact
4 X X X (always =5 0)

5 X X X F1

6 X
Opposite of ROM:
B
ANDs: programmable
7 X X ORs: not
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 3 - Part 1 28
 3. Programmable Logic Array (PLA)
Programming at both the product and the sum levels
A  What are the equations for F1 and F2?
n inputs
B  Could the PLA implement the
(3)
functions without the XOR gates?
C
X X 1 X X AB k products
(4)
Programmable X X 2 X BC XFuse intact
Connections,
Fuse blown
X X 3 X AC
Get expressions
for each group for Programming
a PLA with:
X X 4 X AB the Output inversions
n inputs, k products, C C B B A A X 0
m outputs X 1
F1
PLA with 3-inputs, 4 product terms, m outputs
2-outputs, + programmable output (2)
F2
inversions Chapter
Express F2 as a SOP and3POS
- Part 1 29
 Programmable Logic Array (PLA)
 Compared to ROMs and PALs, PLA is the most flexible
economical device: having programmable ANDs,
programmable ORs, and programmable output inversions
 Advantages
• PLA can have large numbers of inputs N and outputs M, permitting
implementation of optimized functions that are impractical for
a ROM (because of the large number of inputs N required)
• A PLA has all of its product terms available for connecting to all
outputs, overcoming the problem of the limited number of inputs
to each PAL OR
• Any product can be shared by all output functions (sums)
• Some PLAs have outputs that can be complemented, to give
F expressions in terms of product of sum (POS) (inverted SOP of F)
 Disadvantage
• Often the # of product terms limits the application of a PLA.
Solution:  Use two-level multiple-output optimization to reduce the
number of product terms required, thus fitting it into the PLA.
Chapter 3 - Part 1 30
 Using Programmable Logic Array (PLA)

 The set of functions to be implemented A

must fit the available number of product B
terms
 Any product is available for use by any C
X X 1 X X
output, so we try to maximize sharing of
products among various outputs X X 2 X X
XFuse intact
 The best approach to fitting is multiple- X X 3 X X
1Fuse blown

output, two-level optimization

 Since output inversion is available, terms X X X 4 X
X 0
can implement either a function or its CCBBAA
X 1
complement if this reduces the number of F1
products needed and/or increases F2
sharing of products
 For small circuits, use K-maps to
optimize individual functions and
maximize product term sharing including
use of output complementing Implement F or F to maximize sharing
 For larger circuits, CAD software is used Of products- easy to invert to get F
to do this optimization
Chapter 3 - Part 1 31
Programmable Logic Array (PLA) Example
F1(A,B,C), F2(A,B,C), PLA: (3 inputs, 4 products, 2 outputs
with programmable inversion)
B B
 K-map BC
00 01 11 10
BC
00 01 11 10
A A
specifications
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 only four products? C F1 map C F2 map

 Complete the F1 = ABC + A B C + A B C F2 = AB + AC + BC
F AB + AC + BC + A B C F2 = AC + AB + B C
programming table 1 =
 Choose implementations PLA programming table
(F or F) that use the largest Outputs
SUM (OR)
Product Inputs (C) (T) Programming
# of shared products! term A B C F1 F2
 How many products AB 1 1 1 – 1 1
needed if we implement AC 2 1 – 1 1 1 Product (AND)
BC 3 – 1 1 1 1 Programming
F1 and F2? ABC 4 0 0 0 1 –
Chapter 3 - Part 1 32
 Programmable Logic Array (PLA)
Example, Contd.
A

B
Good sharing
of products! The 4 products
C

X X 1 X X AB

X X 2 X X AC XFuse intact
1 Fuse blown
X X 3 X X BC
But we actually
X X X 4 X ABC need F1 as an O/P,
not F1- So invert F1
Give algebraic expressions C C B B A A X 0
With the XOR
1
of F1 and F2 X
F1

F2 F1
We inclement F1 F2

Using the PLA then invert it

, as this is more economical Chapter 3 - Part 1 33
 2. Memory Devices:
Introduction
 Storage element  Memory device for data storage

 One flip flop stores a bit

 A set of m flip flops make a register that stores m bits

 m = 8: Byte, m = 16: Word,

m = 32: double words, m = 64: Quad words, etc.

 Over the years, Processors have used larger and larger

registers to process data: m = 4, 8, 16, 32, 64, 128 bits
 Memory Devices
 A memory device consists of a set of
registers (memory locations) that share a
common set of input lines (input bus) and
a common set of output lines (output bus)
 With Read/Write memory devices we can
store (write) into or read from any memory
location
 We select which location to access by
specifying its address on the address bus
 We select a specific memory chip and Chip
Select
specify a READ or a WRITE operation using
control signals (e.g. RD/WR) on the A memory device that we can write
control bus into and read from is a Read/Write
 Time taken for the read data to appear at (RAM) device
the device output after specifying the
location address is access time (ns)
 Capacity of a Memory Device
 Storage Capacity: Number of
storage locations x width of data
in each location
 With Address = n bits
Number of registers (storage
locations) = 2n locations
 If each location is m-bit wide
then memory capacity is
2n x m bits
 Example: n = 10, m = 8
 210 x 8 bits What is n, m for a 64 K locations,
 1K Bytes of storage each being 1 Byte?
= 1 KB = 8 K bits
 Basic Types of Memory Devices
 Two Basic Types:
• Random Access Memory (RAM): Can be Read or written
into
• Read Only Memory (ROM): Can be read only. Writing
requires programming
 RAM Memory

 The contents of a RAM can be accessed in random order

(so is ROM by the way- a misnomer!)
 A better name is Read-Write memory: i.e. Can be read or
written into
  Has both input and output data lines
 Time taken to transfer data to or from any register (storage
location) is the same regardless of address
 This is different from sequential storage e.g. on tape or disc
 Data held in a RAM memory is volatile (not permanent) –
Disappears when power is removed
Will not survive a power down  Use ROM for this purpose
 Two main types of RAM Memory
 Static Memory (SRAM): Each bit is
stored in a latch
 Once data is written, it remains as long
as power is ON
 More costly, requires a larger number
of transistors, lower storage capacity,
faster access times

 Dynamic memory (DRAM): Each bit is

stored as a chage on a capacitor
 The charge leaks, and data needs to Write
be refreshed to prevent data loss (snag) Read

 Simpler circuit, larger storage capacity,

lower cost, slower access time
 Overview

Unit 13
• Programmable Logic

• Memory Devices: RAM and ROM