468 FUNDAMENTALS OF DIGITAL CIRCUITS

Once programmed. the data pattern can never be changed. This type of
of
refemed to as ROM. ROMs are highly suited for very high volune usage due
due to read-Only
l ththeir en
Programmable read-only memory (PROM) low nemarycoa n
This type of memory
comes from the manufacturer without any data stored init
.c. empry.Tte
data patten is programmed electrically by the user using a special circuit kn
nown
pogrammer. t can be programmed only once during its life time. Once programm Pk
cannot be altered. This type of memory 1S known as PROM. These are
highly grammed, the de
suited for hi
volume usage due to their low cost of production.
Erasable programmable read-only memory (EPROM)
In this type of memory. data can be written any number of times, i.e. they are reproga
Before it is reprogrammed. the contents already stored are erased by exposing the chip to ul mable
radiation for about 30 minutes. This type of memory is referred to as EPROM.
possible only in MOS technology. Programming is done using a PROM programmer
OM: EPROM
Electrically erasable and programmable read-only memory (EEPROM or EPROM)
This is another type of in is done electrically ratber te
reprogrammable memory which erasing
exposing the chip to the ultraviolet radiation. It is referred to as EEPROM or electrically alterable
ROM (EAROM).

8.6 COMBINATIONAL PROGRAMMABLE LOGIC DEVICES

A combinational PLD is an integrated circuit with programmable gates divided intoan AND am
and an
provide an AND-OR sum of products implementation. There threema
OR array to
types of combinational PLDs and they differ in the placement of the programmable coneciann
are

the AND-OR array. The various PLDs used are PALs (programmable array logics,FL
programmable7 logic arrays) and PROMs (programmable readonlymemories)
shows the configuration of the 3 PLDs. The programmable read-only men
Figure
(PROM) has a fixed AND aray constructed as a decoder and a programmable OR auy
AND gates are programmed to provide the product terms for the Boolean function5, *
has progranae
AN
logically summed in each OR gate. The programmable array logic (PAL)

Fixed AND array Programmable utputs

Inputs (decoder) OR array

(a) Programmable read-only memory (PROM)

Fixed Butpu
inpuls
Programmable
AND array OR array

(6) Programnable array logic (PAL)

Outpuls
Programmable
inputs Programmable
AND array OR array

(c) Programmable logic array (PLA)

configuration of three PLDS.
Figure 8.7 Basic
 PROGRAMMABLE LOGIC DEVICES 469

The most flexible PLID is the programmable logic array (PLA) where
hred OR Arvs can be programmed. Jhe product terms in the AND array may be
OR

and
a
A N D
and
.
1o provide the required sum of products implementation.
gate.
y
OR
a n y

PROGRAMMAE
urdDy
oGRAMMABLEARRAY LOGIC (PAL)
logic (a registered trade mark of Monolithic Memories) is a particular farnily
anablea g i c devices (PLDS) that is widely used and available from a number of
grauma
mTamma PAL circuits consist of a set of AND gates whose inputs can be programmed
urers. n
a n a t at u r
connected to an OR gate, i.e. the inputs to the OR gate are hard-wired. ie.

ahe outih a fixed OR array and a programmable AND array; Because ónly the AND
With

is progra.
ammable. the PAL easier to program but is not as flexible as the PLA. Some
1S

also allow output inversion to be programmed. Thus, like AND-OR and AND-OR-
ufatthey implement a sum of products logic function. Figure 8.8a shows a small example
E ucture. hefuse symbols representfusible links that can be burned open using
PROM that every input variable and its complement can
ent similar to a programmerNote
AND We then say that the AND gates
ither connected or disconnected the every 1s gate.
Irom

mCTammed. Figure 8.86 shows programmed to implement F ABC

how circuit =

are left connected to

RC Note this important point. All input varlabies and their complements
d AND gate, whose output is. therefore, AABBCC=0. The 0 has no affect on the output
the
he OR gate,ANDOn the other
would
hand, if all inputs to the unused AND gate were burned open,
HIGH (logic 1), and the output of the OR gate in that
case
urput of the gate 'float
vaild remain permanently 1. The actual PAL circuits have several groups of AND gates, each
pnup providing inputs to separate OR gates.

Programmable
AND gates
Programmabie
AND gates
ABC

F-ABC+A
Output

Unused
a (6)
gure 8.8
Basic structure of a PAL circuit, and implementation of F ABC+ ABC.
=

ure 8.9a shows a

enical gate i conventional
Onventional means for abbreviating PAL connection diagrams.
mean it
Note
The
Atinkes throdenoerawn
ectionthrouph
with
single input line,
a
reality. has three inputs.
whereas in
Inputsand horizontal lines feed the AND gates. An x sugn denotes
the
ntact fusible Tink and a dot sign represents a permanent cojinection.)The
a
470 FUNDAMENTALS OF DIGITAL CIRCUITS

absence of any symbol represents an open or no connection by virtue of a burned.

is connected to the gate through

a fusible link. inpsCD link .

example shown, input A nthe

connected. and input B is disconnected.
Therefore, the output of the
gate is AC Pmane
of how the PAL Structure is represented usino
ANenlky
Figure 8.95 shows an example
connections. It is a 3-input 3-wide AND-OR structure. In this example, cach f
tion hg un
three minterms or product terms. Notice that there are nine AND gates, which imniCan
chosen products of not more than three variables ABC. Inputs to the OR gates at only nie
fixed as shown by xs marked on the vertical lines. The inputs to the AND gates are m a s
corresponding line by the xs. Removing the x implies blowing gthe corresponding f Onte
turn implies that the correspondinginput variable is notapplied to the particulanAND g n
example, the circuit is unprogrammed because affthe fusible links are intact.,Note that gate.I this
the 3-
OR gates in Figure 8.9c are also drawn with a single input line. -1niput

D.tD a) Fixed OR aray

Programmable
AND array

F
(c)
Figure 8.9 Simplifed method for showing connections in circuils
 PROGRAMMABLE LOGIC DEVICES 471

EXAMPLE8.4 Using the connection adbreviations, redraw the circuit in Figure 8.9c to
Us
Pl an be programmed to implement F, = ABC+AC+ABC and F, = BC.

S o l u n o n

Circuit
to implement the given functions is shown in Figure 8.10a. Note that
ne edr
e
AND gate has all ts links ntact. Al links intact can be represented by a x in the
u n u s e dA N N L

snown
n in
in Figure 8.108 Such a diagram is sometimes called the fuse map.
Figure 8.106.
as
AND gate

Fixed OR array

ABC
F ABC+ ABC+ AT

ABC

ABC
F= ABC+BC
\BC

(a) (D) Programmable

AND aray

ABC + ABC+ AC and

to implement F,
=

8.4; PAL programmed

E
F2 ABC+BC.
manufactured
Anexample of an actual
actual PALIC is the PAL 18L8A from
Texas Instruments. It
is

low popowerS an PAL

and eight output
functions. Each
and has ten logic inputs
Rgate is technology therefore it generate functions can
to AND red outputs and
seven gate
s PAL IS that Six of the eight
p up to this particular
hsmaa
uts are 1e back crins.
Dack into
An added feature of
be connected as inputs to any AND gate.
kes the o AND aTay, where they can
of combinational logic.
y useful in generating all sorts

PAL Programming
The fuse rmap able
htee co of table consists of
The fir
aPALC D specified in a tabular form. The PAL
terms
numerically.
programning
The second column specifies
Oumn lists the product
 472 FUNDAME NTALS OF DIGITAL CIRCUITS

gaekcd w
the equnred paths bhetwcen inputs and AND gates. The third column specif.
OR gates Fr cach product term the inputs are marked with 1, 0, or - (das e
l u t tem ajpears in its tnue torm. the corresponding input variable is t varia Varia
appcars in complemcnted torn, the corresponding input variable is marked i d with
al d with
isahsent in the praduct temm, it is as
marked a- (dash). are I he a0. vne,
The paths etween the
muts n the programming
inputs and the AND gates specified
table. AI in the input column specifies a
under the
connectionne
.

ANID 0 ection ro
anabic to the
gate. A in the nput column
speciiesa conncction from the comathe
anablc to the input of the AND gate. A dash specifies a blown fuse in both the innPetnent
cmplement. It is assumed that a open terminal in the input of an AND gate behaves b e n
s like
The outputs of the OR gates are specified under the column a l
heading outpue
PAL Is specificd by the number of inputs, the number of product terms, and the numheThe s
For n k terms. and m the internal ot outpu
inputs. product outputs logic of the PAL co
invener gates. k AND gates, and m OR gates.
When designing a digital system with a PAL, there is no need to show the intemalIcconnect
of the
unit. All that
is needed is aPAL programming a table which the PAL
from canbepro
to supply the required logic. When implementing combinational circuit with a PA caref.
investigation must be undertaken in order to reduce of distinct
the number Sin product terms.
PAL has a finite of AND gates, this can be dorne by simplifying each
a munimum number of terms.
number Booleanfunci
EXAMPLE 8.5 Implement the following Boolean functions using PAL with four
inpus
and 3-wide AND-OR structure. Also write the PAL programming table.
F A . B. C, D) = E m(2, 12. 13)
F A . B, C, D) = Z m(7, 8, 9, 10, 11, 12, 13, 14, 15)
F(A. B. C. D) = Z m(0, 2, 3, 4, 5, 6, 7, 8, 10, 11. 15)

Solution
F(A, B. C, D) = E m(1, 2, 8, 12, 13).

The K-maps for the above expressions, their minimization and the minimal expresios
obtained from them are shown in Figure 8.11. Note that the function for
terms. The logical sum of two of these terms is equal to F,. By using F, it 1s poSS
F,has four pro
reduce the number of terms for F, from four to three. The implementation of the m inim

iogic expressions using PAL is shown in Figure 8.12b.

0 01 11 0 CD 00 01 11 10
AB
4B 2

15

10

A + BCD
F, ABC+ABCD F2
Figure 8.11 Example 8.5: K-maps (Conta.)
 PROGRAMMABLE LOGIC DEVICES 473

00 10
4 800 01 11 10
LT

0
12
12
1
Fa= CD+ AB
L
BD F ABC +ACD+ ABCD
Fi + ACD + ABCD
=

Figure 8.11 Example 8.5: K-maps.

The programming table that specifies the PAL of Figure 8.12b is listed in Figure 8.12a.
sae he given problem has four outputs the table is divided into four sections with three product
i n each to conform with the PAL ot Figure 8.95. The first two sections need only two
t terms to implement the Boolean function. The last section for output F, needs four
from F, we can reduce the function into a function with three
mduct terms. Using the output
ns.
The fuse map for the PAL as specified in the programming table is shown in Figure 8.12b.
ir cach I or 0 in the table, we mark the corresponding intersection in the diagram with the
for intact fuse. For each dash, wewith blown fuses in both the true
mark the diagram
symbol an
ad complement inputs. If the AND gate is not used, we leave all its input fuses intact. Since the
receives both the of each input variable, we have
and the complement
aTesponding input true
Ã=0 and the output of the AND gate is always 0. Usually a x inside the AND gate is used to
ndicate that all its input fuses are intact.

AND Inputs
Product tem Outputs
A B C D F,
F, ABC+ABCD
1

2 1

F2 =A+ BCD

F AB+ CD +BD
8

ABCD
F =
F+ ACD

0 0 0 1
programming
table
(a) PAL

Figure 8.12 Example 8.5 (Conid)

474 FUNDAMENTALS OF DIGITAL CIRCUITS
AC

Fixed OR array

Programmable AND array

F.
(b) Realizalion of the example functions using PAL
Figure 8.12 Example 8.5.
EXAMPLE 8.6 Realize the following functions using a PAL with four
AND-OR structure. Also write the PAL programming table. inputs an
F,A. B. C, D) =E m6, 8,9, 12-15)
F A, B, C, D) Z m(4-7, 10-11)
=
FA, B. C, D) 2 m(1,4-7, 10-15) =

F(A. B. C, D) =Z m(4-7,9-15)
Solution
The first step the
in
realization is to obtain the minimal form of all
the gc
sum of products
products
K-maps for the given functions, their Sum
nimal.SOP
Tunctons. The
expressions obtained from them are shown in minimization, and tne
Each section in the Figure 8.13. Therea e

PAL comprises three AND gates feeding the

four such sections. Notice that
F, has four product terms but the
givenAL device
PA.

provision for
three products give becomes

only as
inputs toOR gates. So some
necessary. Observe that out of four terms two of the terms
man
of F, are equa
 PROGRAMMABLE LOGIC DEVICES 475
cm of F, and the remeining two terms. The PAL
C n
as
the s

eR.14a. The actual realization 1s shown in Figure 8.14t

programming table is
at n ' g u r

CD
A B0 0
01
AB 00
01 11 10
00

15 14

10
10
F, AB + AC + BCD Fa AB+ ABC+ ACD+ BC
=Fa+ BC+ACD
01 11 10 00 01 11 10
AB 00 AB

00
3 AND
o | g a each

2 13 15
1 H OP gai

AD + AC
F= AB+ ABC F=B +

Figure 8.13 Example 8.6: K-maps.

AND Inputs Outputs

Product term A B C D F

AC+ BCDD
F, =AB+

1 F2 AB+ ABC ACD+BC

= F+BC+ACD
5
1

F A B +ABC

10 B AD
AC
F
table
PAL p r o g r a m m i n g
(a)
Example 8.6 (Contd.)
Figure 8.14
 476 FUNDAMENTALs OF DIGITAL CIRCUITS

Fixed OR array

Programmable AND array

F F2
(6) Realization of the example functions using PAL
Figure 8.14 Example 8.6.

8.8
PROGRAMMABLE LOGIC ARRAY(PLA)
The PLA represents another
type of
c h i t e c t u r e

The PLA combines the

programmable logic but with a slightly difterent m
characteristics of the PROM and the PAL
OR array and a programmable AND array, i.e. in a PLA both AND providing
by bon aae fu
at
the inpufs. (Athird set of fuses in the output inverters allows the
gates and O inverto
Tequired Usually X-OR gates äre used for controlled inversion. output This
Tune es it the
versatile of the three PLDs.JHowever, it has some disadvantages. teatu sets of fus
it is more difficult to
manufacture, program and test it than a
Because DAL Figure
demonstrates the structure of PRO link intact.
Like ROM, PLA can be
a
three-input, four-output PLA with every TU With Th
mask programmable or field progran manui anufacturer
programmable PLA, the user must submit a PLA
programming table to u
 PROGRAMMABLE LOGIC DEVICES 477

vender to
vender
to produce a user made PLA that has the required internal paths between
prod

the

sedby second type of PLA available is called a field programmable logic amray or
ies uls.

d ouean be programmed by the user by means of certain recommended procedures.

hergrammed with commercially available programmer units.
s can

Programmable
AND gates

Programmable
OR gates
Ouly Out
Out, Oug
PLA
Structure of (an
unprogrammed) CirCt
'gure 8.15
to
be programmed
XAMPLE 8.7 Snow how the PLA
circuit in Figure
8. 15 would

t h e sum and carry outputs of a full adder.

solTheutitruth
on t Drawing
the K-maps
for the sum

of a full-adder is shown in Figure

8.16a . s u m and carry-ou
ndCarble
Dut minimal
expressions
for the
G n oB)D

lerms are terms and n

minin
imizing
them, the
a )r
The sum is A
is tn

S= ABCn+ABC+ ABC, +AB In

in
478 FUNDAMENTALS OF DIGITAL CIRCUITS

and the c a n y O u t 18

CotAB+ACi+BC
To implement these expressions, we nced a
the inputs to the OR gates of the PLA can be
4-input OR gate and a 3 input (
programmed, we can imni Eate
c\pressions as shown in Figure 8.16c.

nputs Outputs
implernent ihe give
C S C
01 11 10 BC
A00
1 10
1

S ABCn+ABCin+ABC +ABC,
(a) i u t h table
Cout An+ BC,
(6) R-maps AB

-ANDgo

ABCin
ABCn
ABC

ABC

AB

AC

BC

(c)
S Out
L
Implementation of full-adder Unused

Figure 8.16 Example 8.7.

 PROGRAMMABLE LOGIC 0EVICES 479

Show how the PLA circuit in Figure 8. 15 can be programmed to implement

but binary-to-gl conversion.

(B,. B,. B,Ho-gray (G,. G,.G,) is shown in

Figure & 17a
Sanon
table of 3-bit binary expressions for the
esion table observe that
we the outputs are
nve
G, E m(4, 5, 6. 7)

G, =
m(2, 3, 4, 5)
E m(1, 2. 5, 6)
G, =

and G, in terms of binary inputs B.

for the Gray code outputs G3. G2.
iac the K-maps
them as s h o w n in Figure
8.176, the minimal expressions for G,. G
and minimizing
art
5 ANDgair
G,= B3
G B,B +B,B, 3 ga
G, =B,B, +B,B, 8.17e.
conversion is shown in Figure
the PLA circuit to implement the
of
programming the gate in the
The
in each AND gate is listed along the output of
product term generated are connected
and
The from the inputs whose cross points
is determined terms. The
The product term selected product
agram.
OR gate gives the logic sum of the of the
ried with ax. The output of an
on the connection for one

left in its true form depending

or 8.18.
uput may be complemented feature is shown
n Figure
polanty
A PLD with a programmable
OKgate inputs.
BB
B

G-8,8,88
G,B
Binary Gray
B B 2
0 B,

G,B,B, B,B,
(b) K-map
(Cona.)
(a) Conversion table code
converter

binary-to-Gray
Figure 8.17 PLA as a
3-bit
Example
anple 8.8. Use ot
8.8:
'14o
480 FUNDAMENTALS OF DIGITAL CIACUITS

f1 4 o

B,8
B,B2

B,8

(c) Implementation
igure 8.17 Example 8.8: Use of PLA G
as a 3-bit
binary-to-Gray code converle.
P

Polarity fuse
-**

intact
O P,+ P2+ Pa
D
Polarity fuse blown
Q =

P, +Pz+P
=
P, P2 Pa
Polarity
tuse

Figure 8.18 PLD with a

programmable polarity reau
 PROGRAMMABLE LOGIC DE VYE 481

A Prográmming Table

PLA be specified in tabular form. The PLA programming table consists f

a
can
PLA
a lists the
product lerm numerically. The second column specifies
map of irst column
Ihe third column specifies the paths between
auns hetween inputs and
AND gaes.
variable, we may have a T (for true) or C (for complement
red
patns or each output of the table; they
hK-OR gate)The product terms listed on the left are not parn
ND and
AND
the
X-OR,
term the inputs are marked with 1, 0, or -(dash).
only. For each product
input variable
programming
i f o r r e f e r e n c e
is

x appears ns true Torm, the corresponding

include the product term marked with a 0.
complemented, the corresponding input variable is
co
varno If tit appears
aPpears

it iS marked as a- ash).
marked with
aLJt

absent in thne product

term, under the column heading
are specified
ariable is
naths between
the inputs and the AND gates
column specifies a connection
from the input
A I in the input
rogramming table. a connection from the complement
of
column specifies
gput'si A O in the input
blown fuse in both the input
the AND gate. gate. A
-

(dash) specifies a
of the AND AND gate
in the input of an
wariable to the input It IS assumed that an open terminal

rable and its complement.

under the column heading outputs.
OR gates are specified
behaves Iike a l .

between the
A N D and
terms that are included in the function.
The paths with Is for those product of the AND
a r e marked a path from the output
variables requires
The output I in the output
c o l u m n
It is assumed
term that has
a a blown fuse.
Each product with a - (dash) specify dictates
Those marked
the OR gate. a T (true) output
of like O. Finally,
gate to the input
a
OR gate behaves and a C (complemen)
terminal in the input of a n connected to 0,
that an open X-OR gate be
other of the corresponding
input
tnat
the terms. and
the
a connection to 1. the number of product
Specifies number of inputs, PLA
PLA is specified by
the
outputs the
internal logic of the
Size of
ne a
terms, and m
number For n inputs, k product and m A-OR gates.
uputs. AND gates, m OR gates,
butfer inverter gates, k
functions
ne implementation of the Boolean
F AB+A +

BC 8.19b
F = AC +

table that specifies

the PLA of Figure
programming
PL 8.195. The connectios

Histed gure the intemal

in Figure 8.19a. PLA, there

is no need
to show
table from
which

When digital system with a

PlLA
programming
needed is a
a

unit
unit as
as was
g
done in Fi1gu 8.19b. All that is be
ve PLA Can required logic. investigation
must

supply the
careful
to PLA, finite
has a
grammed circuit with
a
terms.
Since a
PLA

dertakenplementing a combinational product to a

minimum

of distinct
function
number Boolean are
berin the each vanables

of cduce simplitying all the input

gates this c
Caan
done by
n be done
simpiityine
important
since to see

ber of t simplified
not be
ms, The n D e r of literals in
should
a term is function that
terms

able
uhie any way. Both the ue a n d the complement ofeach provides
product
ich one tru terms
which
and
one

are can be
be exprec fewer product
Omm exP
non to other
other functions.
to
with a
 482 FUNDAMENTALS OF DIGITAL CIRCUITS

Product term Inputs Outputs

(C)
4ANDg
A BC F F
AB ongal
AC_
3 ABC
4
BC
(a) PLA Programming table

AB

AC

ABC

3C

B BC C

(b) Fuse map

Flgure 8.19 Programmable logic array.
CEXAMPLE 8.9 Implement the following two Boolean functions with aPLA:
FA, B, C) = Z m(0, 1, 2,4)
FCA, B, C) = Z m(0, 5, 6,7)
Solution
The
K-maps for the functions F, and F,, their
complement forms of those minimization,
both the true and ions ter
and the minimal
For in sum of expre 0
finding the
minimal in true form, consider the products shown in
are
rnin
in Is
complement form consider the Os
on the map.
on the map and for finding mininu
u
Considering the Is of F,
Considering the Os of F VFT)= +B+
Therefore, F =

AB+AC +BC
=
Considering the ls ofF, (AB+ AC +BC)
AT)=ABC+ AB+AC
 PROGRAMMABLE LOGIC DEVICES 483
the
Oso f
Considernng
F= ABC + +
Theretore,
FC) = AB+ AB+
EC.F.(T), F,(C), the combination that gives the minimum number of product
bmo f
F,(T)

F(C) = (AB+ AC+ Bc)

F (T) =
AB + AC + ABC
distinct terms: AB, AC, and BC and ABC. The PLA programming table for
Thisg i v e s f o u r

in Figure 8.21a. The implementation using a PLA is shown in

combination
is shown
thisco

it in the table. This is because F, is

Figure 8.21b.

output though a C is marked over

even
i the true available at the output of the OR gate. The
X-OR
tod with an AND-OR circuit and is
generated
the tunction to produce the true F, output.
gate complements C
01 11 10 A00 01
00

AB+ AC + BC
AC+BC+ ABB F, =

F(T) =

F,(C) = (AB+ AC+BC)

(a) K-map for F

00 01 10
00 01 11 10

ABC+
AB+ AC
Fa
AB+ A C AB +AC
F2(T) =
ABC+
Fa(C)=ABC

K-map
1or F2
(b) K-maps.
8.9:
Example
8.20
Figure
Outpuls
Inpuls
Product tefm
A B C
(C) (
Fi

AB

ABC table
(Conta)

programming
a n dfuse
map
PLA table
(a) Programming

8.9:
Example

Figure 21