WWW 1m

 

 

 

 

 

 

310785
.rvquIvl RETURNING MATERIALS:
P1ace in book drop to
LJBRARJES remove this checkout from
.—:—- your record. F_I_____NES will
be charged if book is
fide,i \ returned after the date
? <w{’1““" stamped below.
U‘.r.\1~‘“""h W
L h. ‘1
' 3C9 ‘1‘ ,, . I

‘4 mafyy", ”a

‘cfcosvsrfl
354

 

 

 

 

THE DESIGN OF TESTABLE PROGRAMMABLE LOGIC ARRAYS

BY

Tsin-Yuan Chang

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Electric Engineering
and Systems Science

APRIL 1987

THE DESIGN OF TESTABLE PROGRAMMABLE LOGIC ARRAYS

BY

Tsin-Yuan Chang
Department of Electric Engineering

and Systems Science
Michigan State University

Abs act

The key to easily testable programmable logic array (PLA) is the
ability to activate any arbitrary one product line during the test.
Based on this activation mechanism, two testable PLA designs for both
function-independent and function-dependent tests are presented in
this study. In the former, the design of the product line activator
is proposed to reduce the complexity of the test pattern generation.

In the latter, methods to generate the test sets for both Growth
faults and Disappearance faults from the product term specification
of the PLA, “are presented. The proposed algorithm can be applied not
only to generate the test patterns, but also to detect the redundant

crosspoints in a PLA.

ACKNOWLEDGEMENTS

The author wishes to express his sincere appreciation to his
major adviser, Dr. Chin-Long Wey, for the guidance and encouragement
in the course of this research.

He also wishes to thank the committee members Dr. P. D. Fisher

and Dr. M. A. Shanblatt, for giving valuable suggestions and comments

in this work.

TABLE OF CONTENTS

LIST OF TABLES ..................................................

LIST OF FIGURES .................................................

I.

II.

III.

IV.

VI.

LIST OF

Introduction ............................................
Fault Models ............................................
Test Methods ............................................

1 Test Generation ....................................
2 Testable Designs ...................................
A. Special Coding ..................................
B. Parity Checking .................................
C. Divide-and-conquer and Signature Analysis .......

3.
3.

The Design of Easily Testable PLAs ......................

Design and VLSI Implementation of the PAC ..........
Chip Area Overhead .................................
Implementation .....................................
A. Area Overhead ...................................
B. Test Sequences ..................................
4.4 Discussion .........................................

#4-‘4‘
wNH

. Test Pattern Generation .................................

l Detecting Redundant Crosspoints Using K-maps .......
2 Test Pattern Generation ............................
A. Test set for D-faults ...........................
B. Test set for G-faults ...........................
5.3 Simulation Results .................................

5.
5.

Conclusions ..............................................

REFERENCES ..............................................

ii

iii

iv

15
17
21

29

3O
35
37
37
37
42

47

74

Table

ELM—Sables

P_ag§
Cubical notation. ......................................... 1
Test set for C-faults. .................................... 65
Comparison of the number of test patterns. ................ 73
The number of test pattens required in some PLAs. ......... 73
Test set for Figure 18. ................................... 77

iii

Liters
l. A general structure of PLA and its Cubical notation. ....
2. Crosspoint faults. ......................................
3. Bridging faults. ........................................
4. A concurrent testable PLA design. .......................
5. A testable PLA with universal test set. .................
6. A testable PLA with cumulative parity comparison. .......
7. Testing a PLA by BILBOs. ................................
8. A testable PLA design [BoM84]. ..........................
9. A testable PLA design [HaR85]. ..........................
10. A testable PLA design with decoder structure. ...........
11. A testable PLA design with product line activator (PA).
12. The 3-bit input decoder. ................................
13. A schematic diagram of PA design. .......................
14. The floor plan of the proposed PA design. ...............
15. The floor plan of a testable PLA design with SR. ........
16. Chip area overhead. .....................................
l7. Cumulative parity comparison scheme. ....................
18. A schematic diagram of PLA and its K-maps. ..............

List of Figures

iv

10

l6

18

19

22

25

25

3O

3O

32

34

36

36

38

39

45

CHAPTER I

Introduction

Programmable logic arrays (PLAs) have become increasingly popular
for implementing control logic in Very Large Scale Integration (VLSI)
systems. Although FLA implementation of such function requires larger
chip areas than the random logic implementation, the simplicity of the
design and regularity of the structure of PLAs reduce the complexity
of the overall chip design. Because of these advantages, a trend
toward manufacturing larger PLAs is expected. The testing of such
PLAs thus becomes a rather difficult problem.

Figure 1(a) shows the general structure of a FLA, and Figure 1(b)
is the cubical notation of Figure 1(a). Table 1 summarizes the

cubical notation:

Table l. Cubical notation.

 

AND plane 0R plane

 

1: connect to connect to output
complement input

 

0: connect to no connect to output
uncomplement input

 

 

 

x: no connection not used

 

 

 

IQ

ol MISSING 03 MISSING

 

 

 

 

 

 

 

 

 

 

 

 

Q I
F% _4£_}* I
P. .—
a, -T __
I3 __
lo I, I2
(a)
. [31.1213 000.02
POIIO" I00.
HIOOI IIO
$00!): OOI
F5!) 0 at I <3 O l
(b)

Figure l. (a) A general structure of PLA, and
(b) its Cubical notation.

A typical FLA is formed by an AND plane, accepting the true and

complement bits of the input lines (I - I and an OR plane,

0 3)!
providing the output lines (00 - 02). The output of the AND plane is

fed to the OR plane through product lines (P0 - P Pull-down

3)'
transistors or crosspoints are formed at the intersections of the
input lines and output lines with the product lines to implement the
desired logic function. In NMOS technology, both AND and OR planes
are built by NOR functions.

In recent years, research has extensively dealt with the test
generation and fault detection of PLAs. The optimum design to
minimize the test pattern generation cost is achieved by eliminating
the expensive stage of test generation. Enhancement in testability is
accomplished through the use of additional logic to control individual
product lines in test mode. Typically, such a control is achieved by

using either a shift register (or shift register with multiplexer), or

Busing extra bit lines to form a decoder (or decoder-like structure).

Redundancy has been used extensively by semiconductor
manufacturers to enable the repair of partially defective memory chips
[Sch78][M0086], multiprocessor systems [KoP86], and processing arrays
[Sa886]. It has been proved that the yield of integrated circuits
using redundancy has been enhanced significantly

[Moo86][KoP86][Sa886][SMD80][CCH79]. Recently, a novel design of

fault-tolerant PLA has been proposed [WVL86], in which the redunancy
is used to repair the defective PLAs. It has been shown that the
yield of such design is significantly improved [WCV86]. However, this
significant yield improvement could be offset if the hardware overhead
is increased due to the redundancy required for the testing of PLAs.
Therefore, the issue of hardware overhead reduction is of significant

importance to the design of fault-tolerant PLAs.

In Chapter II, the physical failures in a PLA are discussed.
Three types of.faults are considered: crosspoint faults, bridging
faults, and stuck-at faults. Considerable research efforts which are
being devoted to the testing of PLAs can be divided into two classes:
test generation and testable design. The existing techniques in both
approaches are reviewed in Chapter III. Note that the techniques
considered are by no means exhaustive. However, the additional

information can be found from [Zhu86].

In order to reduce the hardware overhead for the design of fault-
tolerant PLAs, the designs for both the function-independent and
function-dependent tests are investigated here. The use of extra
logical circuitry to design a product line activator for an
alternative decoder structure PLA is presented in Chapter IV. The
product line activator is employed to activate only one product line

at a time so that the observability in the output lines is increased.

Since this acivation mechanism is independent of the function the PLA
realize the test is referred to as function-independent. The proposed
design offers the following salient features: (1) homogenous and
regular structure; (2) less chip overhead than the shift register
approach; (3) no performance degradation during the normal operation
due to the added hardware; (4) no additional I/O pins required; and

(5) no extra test sequence needed.

As far as the hardware overhead reduction is concerned, the use
of no extra logic to the test of PLAs is studied in Chapter V for the
further reduction. Based on the activation mechanism developed in
Chapter IV, methods to generate the test sets from the product terms
specification of the PLA under test, are presented. Since the test
sets are determined by the logic functions realized by the PLA, this
test approach is referred to as function-dependent. The proposed
algorithm can be applied not only to generate the test patterns, but
also to detect the redundant crosspoints in a PLA. The algorithm has

been implemented on a VAX 11/780 in FORTRAN.

The conclusions and futher research directions are given in

Chapter VI.

CHAPTER II

Fault Models

The fault models considered in the design of NMOS PLAs are:

crosspoint faults, bridging faults, and stuck-at faults [SGM84].

A crosspoint fault is caused by the unintentional presence (or
absence) of a transistor. Crosspoint faults can be subdivided into
two classes: missing crosspoint faults and extra crosspoint faults.
The former is due to a missing contact at the crosspoint in the AND
plane or the OR plane; the latter is due to the unwanted presence of a
contact at the crosspoint.

According to the location of the crosspoint faults, it is
possible to distinguish four types of faults: growth faults, shrinkage
faults, disappearance faults, and appearance faults. A growth fault
is caused by a missing crosspoint in the AND plane resulting in the
disappearance of an input variable from a product term. A shrinkage
fault is caused by an extra crosspoint in the AND plane resulting in
an additional input variable in a Boolean product term. A
disappearance(appearance) fault is due to a missing (extra) crosspoint

fault in the OR plane.

The four types of crosspoint faults in the PLA of Figure l are
shown in Figure 2 with their effects on the corresponding product
terms. For example, if the contact at Q1 is missing, it is equivalent
to the product term PO growing in size (Figure 2a). On the other
hand, if there is a spurious contact at Q2, this has the effect of
shrinking the product term P2 (Figure 2b) [AbF86]. When there is a

is

missing device in the OR plane, for example Q3, the product turm PO

disappeared from the output 01 (Figure 2c). However, when an extra

device appears at Q4, the extra product term P will appear the output

0
02 (Figure 2d).

In practice, the "extra device" fault model in modern VLSI
circuits has much less significant than the other fault models
normally considered for PLAs. It has been shown that extra devices

represent less than 0.5% of faults mapped from physical failures

[KhBBS].

A bridging fault is a short between two adjacent or crossing
lines. This fault forces the same logic value to appear in both the
lines. A bridging fault can occur either in the AND or the OR plane.

If a bridging fault is present between two adjacent metal lines,
it will cause either a logical AND, or a logical OR, of the bridged
product terms in the plane of occurrence. If a bridging fault makes a
bridge between the drain diffusion line and the grounded diffusion

line, it is a stuck-at—O fault. Alternately, if a bridging fault

 

 

 

 

 

 

a: PP
.3 3
P} 00 Ol IIIo 9% 00 OI IIIO
00 00 _——I
P
j; Z
h—l
OI 0'

 

 

L131

 

 

I ! I

Q ‘ .0

(a) Growth fault.

 

OFI

 

 

 

 

 

 

 

 

 

 

 

 

 

(b) Shrinkage fault.

 

a, ‘3
F53} 00 0| IIIo pfifx 000' ”'0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 0° as Pd
0, 0|-

I I ‘2EE::2§3 A I I i‘i’ii‘i”

Io El '°

 

 

 

(c) Disappearance fault. (d) Appearance fault.

A Figure 2. crosspoint faults.

occurs between two transistor drain diffusion lines, it will turn into
a metal line bridging fault.

Consider a bridging fault occured at B of the AND plane (Figure

l
3), if high dominates, it will result in logical OR of the two bridged
product lines, so that the output functions are changed as shown in
Figure 3a. Nevertheless, if low dominates, a logical AND of the two
bridged product lines is resulted, and then the bridged product lines
in the AND plane are altered as in Figure 3b. Consider a short
between two output lines and assume that high dominates, so that both

outputs will be at logical l in the faulty PLA if at least one output

is at logical l in the fault free PLA, as shown in Figure 3c [50686].

A stuck-at fault is the simplest type of fault that can occur in a
PLA. A stuck-at fault is the result of a metal (or diffusion) line
opened, or shorted to ground or VDD. A single break in the line can
result in the line stuck-at-zero [FKH80], [FuK8l]. This corresponds
to a metal line which is opened in either the AND plane or the OR
plane. If the opening occurs at the diffusion line of a transistor,
the same scenario of the missing crosspoint applies. When a metal
line is shorted to ground in the AND (OR) plane, then this is
equivalent to a stuck-at-zero (one) fault. Finally, if a metal line
is shorted to VDD, then a stuck-at-one fault is present.

All single stuck-at faults in a PLA, except output stuck-at-one,

are equivalent to crosspoint defects [80686].

10

#‘IIIE'II

fl-r- —'-3—f-e—

v:

33W

(a) Bridging fault at B

 

(D
(

 

<9

 

 

 

 

1, High dominates.

 

 

 

 

 

 

 

 

 

f

._ fi- ass
3?

Bridging fault at B Low dominates.

52.

 

 

1’

it

 

 

 

 

 

 

 

 

 

 

 

 

(c) Bridging fault at B High dominates.

2'

Figure 3. Bridging faults.

11

The various fault models which may occur in a PLA can make test
generation a complex process. However, analysis of the relationship
between different types of faults reduces the complexity of the
problem. A complete test set for single crosspoint fault also covers
most single stuck-at faults in input decoders and output lines, as
well as many shorts and a large portion of multiple faults
[Smi79][Osh79]. Any stuck-at fault or bridging fault (of AND type) is
equivalent to multiple crosspoint fault [Min 84]. It has been verified
that 98% of all multiple crosspoint faults of size 8 and less are
inherently covered by every complete single crosspoint fault test set
in a PLA [Agr80]. These results indicate that single crosspoint faults
should be of primary concern in testing. In case other classes of
faults are considered significant, special effort must be made to

ensure for their high fault coverage.

CHAPTER III

Test Methods

A PLA corresponds to a two-level sum-of-product combinational
circuit. To test the PLA one may simply convert the PLA into a two-
level gate and then find tests for stuck-at faults using the existing
test generation algorithm, such as D-algorithm. However, as far as
the fault behavior is concerned, the faults such as an extra
crosspoint fault in the AND plane can not be modeled as a stuck-at
fault in the gate circuit. Therefore, high fault coverage is not
guaranteed. On the other hand, traditional test generation algorithms
are not always effective for PLAs because PLAs have high fan-in, fan-
out, redundancy and special fault models. Although exhaustive testing
and random testing approaches are effective on some combinational
circuits, they are impractical as the size of the PLA increases.

Considerable research efforts have been devoted to the testing of
PLAs could be divided into two classes: test generation and testable

designs.

l2

13

3.1. Test Generation

Most of the earlier approaches fall in this class. Regularity of
the structure is exploited to derive optimal or near optimal test sets
to detect different types of faults in PLAs. However, the basic idea
behind most PLA test generation algorithms is path sensitization, to
select or deselect a product line and then sensitize the chosen
product line through one of the output lines. Knowing a PLA's
personality, tests of this nature can be easily found.

In [SGM83],[SGM84], the well-known Shannon's expansion theorem

F(x.y) - xF(1.y) + §F(0.y)
is employed to find the test patterns of all possible faults.
Consider the example of Figure 1. Suppose a test is generated for a

missing device fault at transistor Q1, it checks

10111213 000102 10111213 000102
1 O O x l O O with P2 1 O O l l l 0
P3 0 O l x O O 1

P4 0 O x l 0 0 l

and rules out P3 and P4 because the input bit I0 is different. The

problem reduces to:

I0 00 01 I0 00 01

does P2 1 l 1 cover x l O

14

By applying Shannon's theorem with x - 0 and checking F(O,y), the
following question is posed:

I0 00 01 o 0o 01
does P2 1 l 1 cover 0 l 0

Clearly, the test pattern (1000) can be selected to detect the

I

fault considered here. Test patterns for other crosspoint faults can
be obtained in the similar way.

The test generation methods provide a software solution for the
PLA testing problem. They do not require any hardware modification to
the PLA. However, as PLAs increase in size, a larger number of test
patterns have. to be generated and stored. Sophisticated automatic
test equipment (ATE) is needed to execute the test process. Hence the
testing becomes a time-consuming and expensive task. To alleviate
this problem, more hardware oriented approaches have been developed
in which the extra built-in self-test (BIST) circuitry is addded to
the original PLA such that the modified PLA can be more easily

tested.

3.2. Testable designs

Most of testable design techniques proposed to date fall into one
of the following categories: special coding, parity checking, divide-
and-conquer, and signature analysis. Some techniques are combinations

of these design philosophies.

15

A. Special coding;

A technique proposed by [KhM8l] makes use of the following fact

about a PLA.

- The input bit lines in the AND plane naturally form a two-rail
code.

- For a non-concurrent PLA, during normal operation the signals
on the m product lines forms a l-out-of-m code.

- The fault-free output patterns are determined by the PLA's
personality matrix. They can be coded into some error detection

code by adding extra output lines to the OR plane.

The proposed testable PLA with concurrent error detection
capability, as shown in Figure 4, employes three checkers: C1 is a
totally-self-checking (TSC) l-out-of-m checker on all product lines,
and can detect any non-concurrent fault, such as product line stuck-
at-l(0), or any missing and/or extra crosspoint faults in the AND
plane. CZ is a TSC two-rail code checker which detects all single
stuck-at faults in the input lines. C3 is an output code checker whose

complexity depends on how the outputs are coded.

I ‘5

GNU
"‘de

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   
  

ener
inhuman

Figure 4. A concurrent testable PIA design [1011181],

17

B. Parity Checking

Since PLAs have a regular array structure, they can be designed
to test by a small set of deterministic tests which are function-

independent. This is based on following important observations:

- One can add extra lines (product lines or output lines) to make
the connections of each line ”odd (even). Then any single
crosspoint fault will change the parity and can be dectected
by the parity checker.

- In order to easily test a PLA, it must individually control each
input line and product line, and sensitize each product line

through the OR plane.

In [FuKBl], two parity checkers are employed, one in product
lines and the other in output lines. In order to make the odd parity,
the following additional circuits are added (Figure 5): a product term
selector, a modified input decoder, and some extra product lines and
output lines. The parity checker is composed of XOR gates. The
purpose of using the product term selector and the modified input
decoder is to activate one row and one column in the PLA, so that
every crosspoint can be uniquely selected and tested. Usually the
product term selector is a special designed shift register whose size

is the width of product line.

18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 Product Tenn Selector S
”:23“ ' 5! ° ° ° 5!! 5M0!
dccodfl W: Jr. . .
I
"wt: “TL 3:" .
'5‘ i : /lim
gI - AND I
s
\‘a "—1' '—
r

 

 

J—

 

 

 

 

 

 

 

 

  

 

 

 

 

3
i U
output“, ; 03
E
“""ILIL.r '-
L . . . 1 _
z|"——'l Parity Chain '1 I z
esm
W'flfl
lies

Figure 5. A testable PIA with universal test set [FuKBl],

l 9

 

 

 

 

5' ...is.“

 

 

 

 

 

IF'
I

""' use “I has“)
no AND
an In"

    

 

 

 

annual] —ll .O.

 

 

 

 

 

 

 

 

I 0: _
r. Jim-“dud i
W-
N saw-dun I V
m kneaded. .
I- as?" S
R . .
LF . . . ‘r f
T "I
_
man-ulnar». /

 

 

   

OI only seen

r-----------‘----------

 

 

 

 

 

 

: has

I - .
3‘33. .. - Arid: .
g :5

L--.

.---=--1;-----------------.

Figure 6. A testable PIA with cumlative parity comparison [N184].

20

A more efficient design has been proposed [Fuj84], in which the
parity check method (Figure 6) is replaced by a cumulative parity
comparison method, the value of the accumulated parity signals in a
flip-flop is compared with the expected value at specific times to
detect the faults. Two control signals Cl and C2 are added which act
just the same as the modified input decoder. One or two extra product
lines are used to make every input bit line contain the odd number of
used and unused crosspoints in the AND plane. The same is done for
the OR plane by adding extra output lines. Only one parity chain is
used at outputs.

An interesting property of this scheme is that the sequence of
cumulated parity bits at 2n+2m+l selected check points is simply a
sequence of alternative 0's and 1's. Hence it is very easy to
generate the expected value on-line. It has been proven that the
fault coverage of this scheme is very high; all single and (l-
2-(m+2n)) of all multiple crosspoint, stuck-at and bridging faults are
covered, where m and n are the number of product lines and output

lines, respectively.

21

C. Divide-and-conguer and signature analysis

In the divide-and-conquer strategy a suitable testable design
methodology is selected for each testable part such that every part
can be embedded in a testable structure.

In the signature approach, a set of input patterns is applied and
the results are compressed to generate a "signature". When the test
is invoked, this signature is compared with a known correct value to
determine if the PLA is faulty.

A design of BIST PLA architecture, as shown in Figure 7, has been
proposed by Daehn and Mucha [DaMBl], in which the combination of
divide-and-conquer and signature analysis strategies is employed.
This design implements the non-linear feedback shift registers as both
test pattern generators and output response compressers. Such
registers are basically a modified form of what is known as a built-in
logic block observer, or BILBO. Basically the PLA is partitioned into
four blocks: input decoder, AND plane, OR plane, and output buffer.
Then, three BILBOs are inserted between these blocks. Testing of each
block is done as follows: let the input BILBO of that block operate as
a test generator and the output BILBO of that block operate as a
signature analyzer. The result is shifted out for inspection. These

blocks are tested one by one.

 

 

I'ooo o I

 

 

$000 I: o

 

(b)

 

I'OOI 0°

 

 

I'OIO GO

 

 

 

 

 

 

 

 

 

 

 

rI'O 00°

 

 

 

 

 

II, .f'OOII

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.0000 In

(c)

Figure 7. Test a PLA by BILBOs.

23

After partitioning, the AND plane and the OR plane are just
arrays of NOR gates. All inputs are controllable and all outputs are
observable, thus testing becomes a very simple task. It is known that

a k-input NOR gate can be fully tested by a simple sequence such as

OOOI—‘O
COP-‘00
OHOOO
HOOOO

A NOR gate array can be tested by the same pattern. The test
generator can be achieved by a non-linear feedback shift register as
shown in Figure 7(b), which produces above patterns. It has been
shown that all single stuck-at faults, crosspoint faults and bridging
faults in AND plane and OR plane are detectable using this sequence

[DaM8l].

Input decoder is tested by a similar sequence generated by the

non-linear feedback shift register shown in Figure 7(c).

For the testable PLA designs, it has been recognized that the key
concept in enhancing FLA testability has been the provision of means
to control individual product lines [BoM84]. Most of the current
testability designs accomplish this goal by incorporating shift

registers in the PLA design [FuK8l]. The data stored in the shift

24

register is used to control the product lines. Unfortunately, the
area of the shift register added generally cannot match with the
compact PLA layout and thus is significant overhead [HJA84].

In [BoM84], some extra input lines, as shown in Figure 8, are
added to the original AND plane so that the augmented AND plane acts
as a decoder that uniquely selects each product line. In this
approach, a set of main test patterns and the corresponding auxiliary
test patterns are employed to detect the faults. A main test pattern
is generated in a way that one and only one product line is selected
at a time. The auxiliary test patterns are generated by flipping the
bits in the main test pattern, one at a time, for each main pattern.
The purpose of an auxiliary pattern is to disable the chosen product
line while maintaining the deselection of other product lines. An
algorithm has been proposed to assure the Hamming distance between
every pair of main test patterns to be two [BoM84]. In order to
satisfy the Hamming distance requirement, a heuristic is implemented
to increase the number of input lines, or crosspoints in the chosen
input lines. It has been proved in [BoM84] that all multiple stuck-at
faults, as well as all multiple extra and multiple missing device
faults, are detected.

Later in [KhB85], a method was proposed to reduce the extra
hardware overhead. The algorithm is based on the fact that as long as

the effect of deselecting a product line with an auxiliary test

 

 

 

  
 

 

 

BUFFER

 

 

 

 

 

Figure 8. A testable PIA design [BoM84].

 

 

‘dl
_

AND OR

I—

 

 

 

 

 

 

 

 

 

 

 

 

II
C i g I BUFFER
}} . II I
* OUTPUT
INTPUT

Figure 9. A testable PIA design [HaRBS].

26

pattern is propagated to at least one output line, the distance of two
is not necessary. In addition, it was claimed that "extra device"
fault model is not significant in modern VLSI circuits. Therefore,
the requirement of choosing a main test pattern is relaxed by the
following fact. It is not necessary to find a vector that uniquely
selects a product line if the collective output response of the other
selected product terms do not cover the observability of the chosen
product line. A modified algorithm of [BoM84] was then proposed to
take these advantages and reduce the number of input lines added.

One major disadvantage in adding new input lines is that the
number of input lines needed for providing testability is not a
constant and depends on the functions implemented by the PLA. In
addition, the extra input lines have to be disabled during normal

operation.

One unique feature of PLAs is that the input lines feed their
true and complement bits into the AND planes This fact places an
important restriction on the applicable test patterns as mentioned
before.

In fact, a Hamming distance of one between each pair of main test
patterns is sufficient to assure the existence of main test patterns.
This can be demonstrated by the PLA shown in Figure l. "1101" is a good

main test pattern for P even though the Hamming distances between P

0

and all other product lines but p4 are only one. However, if the

O

27

Hamming distance between two main test patterns is less than two, there
is always the possibility of accidentally selecting another product line
when a bit of the main test pattern is flipped to generate an auxiliary
test pattern. In the above example test pattern for selecting PO, if
the leftmost bit is switched, the auxiliary test pattern, "1001", will
accidentally select P1. This is due to the fact that the distance
between P0 and P1 is less than two. [KhB85] pointed out the special
conditions when this dilemma can be tolerated.

In essence, it is not necessary to add any extra input line for an

irredundant PLA, even if two product lines have zero Hamming distance

and the same outputs. This motivates the study of Chapter V.

Recently, a new testable PLA design has been proposed by Ha and
Reddy, as shown in Figure 9, in which the normal PLAs are augmented with
the addition of pass transistors in the input decoder [HaRBS]. The
transistors are used to temporarily disconnect the true bits of the
inputs, so that their previous values can be retained for a short period
by the line parasitic capacitances, and new values can then be applied
to the complement bits. As a result, arbitrary test patterns can be
applied to all true and complement bits. In other words, each true or
complement bit of an input line can be controlled independently. This
significantly enhances the testability of PLAs.

One shortcoming of this method is that two phases are required to

apply a test pattern which the values of the true bits are assigned in

28

the first phase and the values of the complement bits are assigned in
the second phase. A more severe disadvantage is that a test pattern
can only be maintained for a brief time due to the small parasitic
capacitances available on the lines.

To improve the deficiency of the above approaches, an alternative

design of easily testable PLA is presented in the next chapter.

CHAPTER IV

The Design of Easily Testable PLAs

The key to easily testable PLA design is the ability to activate
one and only one product line. This activation mechanism enhances the
observability in the OR plane, and it is usually achieved by adding
shift registers to select the product lines. The data stored in the
shift registers are used to operate the activation mechanism.
However, a shift register cell is wider than a product term. This
makes the shift register wider than the PLA, with cells extending
beyond either end. This mismatch wastes area and distorts the
floor plan of the PLA [BHM84].

Recently, a decoder structure has been proposed by Sato and Tohma
[SaT82] to achieve the same activation mechanism. In this approach,
Figure 10, two control lines C1 and C2 are used either to deactivate
all AND word lines or to acivate only one AND word line of the input
decoder, and another control line CO is applied to disable the PA
(Product line Activator) during the normal operation. It has been
shown that the proposed design structure is more homogenous than that
of shift register. However, the need for extra input pins and

performance degradation due to the modified input decoder, limits its

applicability.

'j 0

C2

PA mput normallnput output

        

 

BuFFer

AND UR

Plane Plane

Figure 10. A testable PIA design with decoder structure.

 

fl
PA AND UR
' : Plane —I Plane
L TV

> b
H [Decoder 1 | BuFFer- ' I
II fl I F T
PA Input normal. Input output

 

 

 

 

 

 

 

Figure 11. A testable PIA design with product line activator (PA).

31

The objective of this chapter is to propose an alternative
decoder-like structure that performs the same activation mechanism,
and requires less chip area and almost no performance degradation.

Instead of adding the extra shift registers into the AND plane, a
product line activator (PA) is employed to operate the same activation
mechanism (Figure 11). The PA consists of two parts: product line

activator circuit (PAC) and code sequence generator (CSC).

4.1. Design and VLSI Implementation of the Product Line Activator

Consider a conventional 3-bit input line decoder with PLA
implementation as illustrated in Figure 12. A product line can be
activated according to the decoded input bits. For example, if a
sequence of the numbers from 0 to 7 (represented in binary form) is
applied one at a time, then only one product line is activated in the
order from the top to the bottom. This activation mechanism in the
decoder is much easier than that of the shift register. However, the
only disadvantage behind this decoder structure is the need of the
extra input pins. Therefore, in order to reduce the extra pins, the
code sequence must be generated and applied internally.

The code sequence generation can be accomplished by using a
linear feedback shift register (LFSR). In fact, a LFSR implemented

with EX-NOR gate consumes less chip area than that with EX-OR gate

 

°2 CII c'o

Figure 12. The 3-bit input decoder.

33

A four-bit modified LFSR is shown in Figure l3(a). With the
seed, (b3b2blbO)-(OOOO), a total of 15 (24-1) code sequences is
generated in Figure 13(b). On the other hand, when a seed (1111) is
applied, the modified LFSR will generate the same pattern (1111). The
design of PAC with PLA implementation is illustrated in Figure l3(c).

Since the length of the cyclic code sequence generated by the
modified LFSR may not coincide with the number of product lines in a
PLA, a control signal is needed to restart the operation of the
modified LFSR, so that the code sequence can be applied periodically.
As shown in Figure l3(c), the extra product line, BMPLI, is employed
as the control line. In this implementation, BMPLI is programmed as
same as the logic function of the bottom-most product line.

In fact, the PA is used only when the test process is performed,
and it must be disabled during the normal operation. The D-line is
use to control this operation, where D-O(l) for normal operation mode
(for test mode). During the test mode, D - 1, the code sequence is
generated by the modified LFSR with a seed of (D D D D) or (0000).
This sequence is continously generated until the corresponding
sequence of the bottom-most product line is recognized. Once the code
bits stored in the shift registers match with this corresponding
sequence, the BMPLI are set to 1. When the test mode is completed,
the D-line is then set to 0 for the normal operation. As a result,

the seed (D D D D) becomes to (1111) and will be loaded to the

shift registers to disable the PA.

'3 A

00101000110151.1000

 

 

 

I
A 4 bits LSFR scheme.

(a)

Code sequence.

(b)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

BMPLI

 

 

 

 

 

 

 

 

—! - ‘-

CSG

 

 

 

 

 

 

 

 

 

 

 

 

 

u.___________-__-J

(c)' The design of no and csog

Figure 13. A schematic diagram of PA design.

35

4.2. Chip Area Overhead

A floor plan of the PA design is illustrated in Figure 14. all
dimensions are in the units of lambda ,A, [MeC80]. The number of bits
required for the PA design depends on the number of product lines in.
the PLA. For a PLA with m product lines, a k-bit PA is needed, where
k - [Log2 (m+l)]. The chip area required to design the PAC is
essentially the same as the area required for the k input lines in a
standard PLA. According to Mead and Conway's design rules and
[NeM83], a product or output line requires 8A in width, while an input
line consumes 16A in width. Therefore, the chip area for PAC is
approximately 128mkA2, or (8mA)(l6kA). In addition, each bit of C86
may approximately consume 16) x 155). In other words, the chip area

required for the entire PA design is

APA - ( 8 x m + 155 ) x 16 x [Log2 (m+l)] A2 (l)

36

 

PAC

AND

CIR

 

CSG

ISA

 

 

Figure l4.

}— 155A

Argumented
Input

 

 

lg).

A

175

Decoderjh

Parlty

 

Checker

 

r9er

The floor plan of the proposed PA design.

 

S R
I——I7oI——4

 

AND

UR

 

'16x

 

 

Argumente;[
Input 3

Parlty
Checker

 

Decoder I

'IéA

 

i-95x1

Figure 15. The floor plan of a testable PLA
design with a shift register.

3A

37

4.3. Implementation

In order to demonstrate the effectiveness of the PA design for
BIST PLA design, the implementation of the PA design into TRPLA

[TFA85] is presented.

A ea e head
A floor plan of TRPLA is illustrated in Figure 15. The chip

2

area for the shift register consumes A - 1360m A , or 170A x 8mA.

SR
Figure 16(a) plots the areas required for both PA and SR design versus
the number of product lines. It is obvious that the PA design
requires less chip area than that of shift register (SR) in a
reasonable PLA design. The fraction of area reduction in the PA

design calculated by ( ASR - APA) / ASR is illustated in Figure 16(b).

The curves show that the area reduction can be up to 25%.

W

The test sequences employed in TRPLA design are listed in Figure
17. It has been proved that the test sequences can detect all single
faults and almost all multiple faults [Fuj84]. In fact, the PA design
has the same mechanism as the SR design, these test sequences can also

be applied to the PA design without requiring any extra test

A2

Area required

(ASK - APA ) / ASR

38

 

«our

1

l‘fl‘l

100-0

 

Shift register

The proposed PA

 

 

UI'U‘IUIUVU'U‘UIII“IIIIIDUU'UUIUUII'IIII'UUI'I'Wimim'tU'U'I'"T'UU'II

SD 100! 180' 33. III Jflfll lflfll 40.
The number of product lines

(a) Chip area.

 

ll)
OJI‘

Ilifir

 

 

 

 

 

I:

l

 

 

4. 'UIUIU'IUI'UI'UIUIIUT'U'IIIIIIll'U'U'IIU'I'UIIIIUWIUUUWUUUIU'UV'UIll'WUII'UU

10' IIII IOII see ill! ill? 4“!I
The number of product lines

(b) The fraction of area reduction in the PA design.

Figure 16. Chip area overhead.

ransom 0me ans—1L

 

 

x... x. 3....5, OumuIvecm CumuIeuve
II o...o I I 0 '0
'1
I :9
l3. 0'°°0 I : MI'S ee
0 O O
I "

'O-mmz

IsInoemIsmm

 

 

 

..l
- CD
is
D.

  
  

:I-Inulwes 2

 

 

l6 9.. mg” e (M:I)M2
23.: . 3 «helmet
0 1 00M!
' (helm!
I 3 3
l ' Inzmwnef
«me, ~
all s o
. :
I’ -, (arms
0
om: II II .1;
H OH “‘. ‘02—?" ‘

 

 

 

h

Figure 17. Cumulative parity comparison scheme.

40

sequences. The only problems remain are how to test the PA itself
and whether or not extra test sequences are needed to test it.

Consider the stuck-at faults and/or bridging faults which occur
on the product line(s) of the PAC. These are the same as the product
line faults in the AND plane and can be detected by appling the test
sequence 11. On the other hand, if these types of faults occur on the
input line(s) of the PAC, then they can be observed from the signal of
the shift-out pin in the CSG. In the meanwhile, the crosspoint faults
occur on the PAC may result the following error cases:

(1) The activation of the product lines is not in order, but one

and only one product line is activated at a time;
(2) No product line is activated;
(3) Even number of product lines are activated; and

(4) Odd number of product lines are activated.

According to the activation mechanism in the PA design and the
characteristics of the universal test sequences, as long as one and
only one product line is activated, the order of activation is not
really important. Therefore, the case (1) does not harm the
activation mechanism. In other words, the proposed PA design can
tolerate the crosspoint faults, as the case (1), in the PAC. The

fault tolerant capability is one of the positive features.

41

If the parity bit detector gives the correct signal for the test
sequences, I1, 12, and I3, then the detector is sure that the
activation mechanism be functioned properly. On the other hand, if no
product line or multiple product lines are activated due to the
crosspoint faults, then these faults can be detected as follows.

The single crosspoint fault may cause either no product line in
the PAC to be activated, or two product lines to be activated
simultaneously, for a certain code sequence generated from the CSG.
For example, if a crosspoint is missed at the P4 and A3, it will
change the function from (100) to (-00). When the code sequence (100)

is applied, P is the only activated product line. On the other hand,

4
when the code sequence (000) is applied, the lines P and P4 are

0
activated simultaneously. In either case, the even parity signal is
detected, therefore, the use of the test sequence 12 can detect that
fault.

For the multiple faults, the combination of crosspoint faults may
result in the error cases (2), (3), and (4). The crosspoint faults in
the error cases (2) and (3) can be detected in a manner similiar to
the case of single fault. Due to the odd parity design, the proposed
PA design may fail to detect the faults if the crosspoint faults on
these activated product lines pass both parity checkers. Specifically,
(I3

a) to pass I2 ) test, the crosspoints in the OR plane and in

J .1

these odd number of product lines activated by the j-th pattern must

42

enable an odd number of output lines; and
4
b to ass I -line X' -
) P J J ( 1

line) in these product lines activated by the j-th pattern must be

(I5 ) test, the number of crosspoints of X

i
odd, and the crosspoints in the activated product lines and the OR
plane enable only odd number of product lines.

In fact, it has been shown that the probabilty of having these
failures is very low and negligible [TFA85]. Therefore, it is not

necessary to increase the test sequence in the use of PA design.

4.4 Discussion.

The salient features of the proposed PA design are (l) homogenous
and regular structure; (2) less chip overhead; (3) no performance
degradation during the normal operation due to the added hardware; (4)
no additional I/O pins required; and (5) no extra test sequence
needed. The proposed design can be implemented on any testable PLA
designs using the shift registers so that the chip area overhead can

be reduced.

CHAPTER V

Test Pattern Generation

Consider an AND-OR PLA with n input lines, p output lines, and m
product lines. The functions realized by this PLA are represented as
arrays L:(C,D) [Smi79], or cubes. A k-tuple a-(a1,a2,..,ak), where ai
is one of the items (0,1,x), is defined to be a cube. Here the "don't
care" term x takes value 0 or 1. The array L has two parts: an input
part (C-array, n columns and m rows) and an output part (D-array, p

columns and m rows). Each cube/row C of the C-array represents a

1

product term of one or more functions realized by the PLA.

Esme—l:
A simple schematic diagram of a PLA, as shown in Figure 18,

implementing five 4-variable switching functions:

4.
H
HI
4.
H

44

The cubical representation of this PLA is

I0 I1 12 I3 00 O1 O2 O3 04
CO: 0 x l 1 DO: 1 0 0 l 0
C1: 1 0 x x D1: 1 1 1 O 0
C2: x 0 0 1 DZ: 1 l 1 0 0
C3: x 0 x 0 D3: 0 1 0 1 0
C4: 1 x l 1 D4: 0 O l 0 l

and the corresponding Karnaugh-map (K-map) is also shown in Figure 18.
It should be noted that the notation C1 in the cubes of the K-map

represents the l-cube that is produced by the product term Ci'

Definitions:

1. A crosspoint-irredundant PLA is one in which all the crosspoint
faults are detectable.

2. A G-D-irredundant PLA is one in which all C and D faults are
detectable.

3. Let a and b be any two cubes. If a has 1 in every minterm in
which b has 1, then a is said to cover b. If neither a covers b,
nor b covers a, then, a and b are said to be unordered.

4. A product term C is said to be non-isolated ( with respect to a

1

given output function), if there is at least one other product

term C (iflj). in the functional specification, such that C and

J 1

C cover one or more common minterms. Otherwise, it is said to

J

be isolated product term.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ob

 

 

 

 

CG
CI ._1
ca -_—
CS _ _. _.
C4 .__
cubical
representation
%
.0 0| it t.
‘1
" ‘8
0| c.
It
“ ‘I fia ‘3 fl
°L_
00
.,‘:
0|
it
i.
h

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

._ 0 I r '
+ 0 ° 2I3 ”0‘1 * II 2‘3
_ 1 011 I112‘: * ‘1‘:
F 0 I I f '
.... 2 o 1 1‘21; + £01213
03 I0 2‘: * ‘1‘:
?V °a Iorzrz
I0 I1 Iz I3 00 01 O2 O3 04
Co: 0 x l l ‘ Do: I 0 0 l 0
Cl: 1 0 x x 01: l i l 0 0
c2: x 0 0 l 02: l l ' l 0 0
C3: x 0 x 0 D3: 0 l 0 l O
64: l x l l D“: 0 0 l 0 l
°L °L_
00 0| It i. .0 0| II I.
a 5 ‘I 5
O. O
0| 0|.
II It
6‘ .
G
u m' ‘
.;I am “I “In“:
.3‘
.; ,, es en II to
a Q a
C. N
n g
' s
u R
C

Figure 18. A schematic diagram of PIA and its K-maps.

46

. For a given output function, a minterm covered by a product term
is said to be free if it is not covered by any other product term
of the function under consideration. Otherwise, it is said to be
bound.

. Two minterms covered by a product term are said to be adjacent if
they differ in only one bit.

. The number of bit positions in which two product terms differ is
called the Hamming distance.

. Let Rj’ j - l,2,...,p, be the columns of D-array. A column Rk is
said to be minimal if Rk does not cover any other columns. On the
other hand, a column Rt is said to be maximal if Rt is not
covered by any other columns. Note that neither minimal nor
maximal column is unique.

. Two rows of D-array, D and D are said to bit-disjointed, if

Notations:

i j’
there does not exist a bit q such that diq-djq-l'
Consider two product terms Ci-(c11,c12,..,cin) and
C - c ,c ,..,c . Let
J ‘31 32 In’

Ci/cjk-(cil’ci2"°’cjk""cin)’
i.e., substituting the k-th bit of Ci by the complement of the
k-th bit of C .. Similarly,

J
ci/cik-(cil’ci2’"’ci(k-l)’cik’ci(k+l)’°"cin)

47

5.1 Detecting Redundant Crosspoints from K—Maps

In this section, the objective is to derive a set of rules to
detect the redundant crosspoints in both the AND and the OR planes.
The removal of such redundant crosspoints will make the designed PLA
G-D-irredundant. Therefore, all the G and D faults in the PLA can be
detected. These detection rules are initially derived from the
observations in the K-maps. A systematic derivation will be further
discussed in the next section.

As mentioned in Chapter II, the "extra device" fault model in
modern VLSI circuits has much less significance than other fault
models normally considered for PLAs. Therefore, the test pattern
generation process discussed in this chapter, is concentrated on both
the Disappearance faults (D-fault) and Growth faults (G-faults).

As it is shown in Figure 2(a) and 2(c), a G-fault causes the
additional minterms expand to its adjacent terms, while a D-fault
makes some minterms disappear from the K-map.

Consider the irredundant crosspoints in the OR plane. As its
name implied, the removal of an irredundant crosspoint will affect the
output functions. In other words, some minterms are missing in the K-
map. Conversely, the removal of a redundant crosspoint will not
affect the output function at all and the K-map is unchanged. Based

on this observation, it is easy to conclude that a crosspoint is not

48

redundant if its corresponding minterms are free. However, if the

corresponding minterms are bound, the determination is discussed as

 

 

 

 

 

 

 

 

 

follows.
Example 2:
Consider a PLA and its K-maps
Io I1 I2 00 O1 02
C0: 0 l x Do: 0 l 1
Cl: 0 0 1 D1: 0 0 1
C2: 0 l 0 D2: 1 0 1
C3: 1 0 x D3: 0 1 0
O0 01: 02:
00 01 ll 10 00 01 ll 10 V 00 01 ll 10
0 C2 0 Co Co 0 C1 CO CO
C
2
l 1 C3 C3 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

From the above K-maps, it is easy to check that all minterms are

free, except that the minterm (010) in O is bound by the product

2
terms Co and C2. The redundancy is determined if there exists an
order between the bound product terms. In other words, for an output
function, if a product term associated with one of the bound terms is
covered by any others' corresponding product terms, then the removal

of such term won't affect the output function. Therefore, the

corresponding crosspoints in the covered term are redundant.

49

Specifically, since the product term CO-(le) covers C2=(010), the

exclusive of the product term C0 in 02 may miss the minterm (011). On

the other hand, the exclusive of the term C2 in 02, no minterm is
missing. In this example, since CO covers C2, the minterm (010) in 02
is covered by Co regardless of the existence of C2, hence, the
crosspoint in C2 and 02, or d22, is detected as redundant.

Rule RCDl: (Detecting the redundant crosspoints in the OR plane)
If a minterm in O is bound and a bound product term C1: is covered

J

by other bound product terms, then the corresponding crosspoint, dij

is redundant.

When an irredundant crosspoint occurs in the AND plane, then the
removal of this crosspoint is equivalent to producing a G-fault. In
other words, the additional minterms are created in the K-map when
that crosspoint is removed. On the other hand, the created minterms
due to the removal of the redundant crosspoints will be always bound
by the other product terms. Based on this observation, if the
corresponding adjacent minterms are free in, at least, one output
function (or, K-map), then the corresponding crosspoint is

irredundant. Otherwise, it is redundant.

50

Examplg 3:
Consider the same PLA in Example 2, except remove the redundant

crosspoint d from the OR plane. The corresponding K-maps are

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

22
00: 01: 02:
r I
00 01 ll 10 f 00 01 ll 10 00 01 ll 10
0 C2 0 CO Co 0 C1 C0 C0
1 1 C3 03 1
From K-maps for both 00 and 01, the adjacent minterms of these
minterms covered by Co, C2, and C3, are free. According to the

definition, the corressponding crosspoints are irredundant. On the

other hand, consider the minterm (001) in the K-map for 02, the free

adjancent minterms at (000) and (101) guarantee that the corresponding

crosspoints c10 and c12 are irredundant. However, due to the fact
that the adjacent minterm at (011) is covered by C0, it is concluded
that the corresponding crosspoint c11 is redundant.

Rule RCD2: (Detecting the redundant crosspoints in the AND plane)
A crosspoint in the AND plane is redundant if the adjacent
minterms of the corresponding minterm in all output functions (or, K-

maps) are all covered by any other product terms.

51

With the redundancy detection process, the redundant crosspoints
in both planes are removed to assure the PLA under test is a 6-D-

irredundant PLA.

5.2 Test Pattern Generation

In this section, the ways to select the minimum number of test
patterns for detecting the G and D faults are discussed. As it is
shown by Smith [Smi79], if Ts is the test set for detecting single G
or D faults, then any detectable combination of G and D faults in a G-
D irredundant circuit, is detected by Ts. Therefore, we only consider
the test pattern generation for detecting single G and D faults.

In order to simplify the explanation of the test pattern
generation process for both D-faults and G-faults, the basic concepts

are introduced with K-maps.

W

Based on the following two observations: a D-fault makes some
minterms disappear from the output functions (or, K-map), and the PLA
under test contains no redundant crosspoint. A D-fault at the
corresponding crosspoint is detected by simply examining if there

exists a free minterm with respect to all output functions.

52

Specifically, from the K-maps, the test set for detecting a D-fault

can be generated as follows:

Case DFl:

Case DF2:

Case DF3:

if a product term is isolated, i.e. the minterms covered by
the isolated product terms are free, then the product term

is chosen as the test set;

if a product term is non-isolated, but there exists at
least one common free minterm, then the common free

minterms are chosen as the test set; and

if there is no common free minterm in a non-isolated
product term, then the test set is formed by the minimum

number of minterms which are free in all output functions.

Applying these three generation rules, the test set for D-faults

in the K-maps of Figure 18 are generated in the following example.

Let PGD(D1) be the test set for detecting the D-faults at Di'

W:

The FLA of Example 1 can be easily shown as G-D-irredundant by

the redundancy detection rules. Since the product term Co is isolated

as illustrated in the K-maps, according to the case DFl, the test set

53

is found to be PGD(DO)-CO, that is ((0011),(Olll)}. In other words,
either test pattern in these test sets can be applied to detect the D-

faults at DO. For the non-isolated product terms CZ’ C3, and C4’ by

the case DF2, the common free minterms (0001), (00x0), (1111) can be

chosen as the test sets for D2, D3, and D respectively. Thus

49
PGD(D2) - {(0001)}

PGD(D3) - {(0000),(0010))
PGD(D4) - {(1111)}.

Although the non-isolated product term C1 has no common free

minterm, it can be found from the K-maps that the minterm (1000) is

free in the output functions 00 and 02, but bound in 01, while the

minterm (1011) is free in 00 and 01, but bound in 02. In other words,

while the minterm (1000) can detect the D-faults at the corresponding

crosspoints at O0 and O the blind point at O can be detected by the

2’ l
minterm (1011). Therefore, with the use of these two test patterns

the D-faults at D1 can be detected. Alternately, another pair (1010)

and (1011) can also be used as the test set. Therefore,

PGD(D1) - {{(1011),(1000)},{(1011),(1010)I}.

The key to easily testable PLA design is the ability to select
any arbitrary one product line during the test. If the only product

line, say C1, is activated, then the status of D1 is observable and

the D-faults at Di can be identified. Based on this concept, the test

pattern generation problem is then turned to how to choose a test

54

pattern that can separate the product term Ci from other product
terms .
As illustrated in the case DFl, if the product term C1 is

isolated, then the minterms of C are free in all output functions of

i
occurrence. This implied that the product term Ci has no common
minterms with any others, or C1.- is separated from the others. In
other words, the Hamming distance of any pair (Ci’cj)’ for any other
C 's, is at least one. Therefore, the case DFl is essentially

J

equivalent to the case of Hamming distance of at least one.

Theorem 1:
If dH(Ci’Cj) z 1, for all Cj s, then PCD(Di)-Ci.

LSMLI:
If there exists a test pattern that selects only the product
line, C
21:22::

Since only the product line C1 is selected, the status of the

1, then this pattern can detect the D-faults at Di'

crosspoints at D1 is observable. Thus this test pattern can

detect the D-faults at 01'

55

O eor

Since dH(C ) 2 l, for all C applying a test pattern of C1

J'S'

and deselect the others. Thus, by

i’Cj
will only select the line Ci
Lemma 1, the test patterns of Ci form the set PGD(Di), i.e.

PGD(Di)-Ci.

Example 5:
Consider the same PLA as in the Example 1, it is easy to derive
that
dH(C0’Cj)-1’ for j-l,2,3, and 4,
Thus, the test set PGD(Do)-Co-(0xll), or {(0111),(001l)}. This is the

same as the test set generated in Example 4.

Consider the case of zero-Hamming distance. dH(Ci’Cj)-O implies

that C and C contain at least one test pattern in common. In other

1 J

words, applying the common test patterns may activate the product

lines C and C simultanously. Therefore if the test patterns are

1 J

chosen to separate the product term C from C the common test

1 j’
patterns must be excluded. In fact, the determination of the
exclusive test patterns depends on the crosspoints in the output
functions. The test set generated for detecting the D-fault at D1 in

the case of zero-Hamming distance should be derived from the test

patterns generated for detecting D-fault at each crosspoint at Di' For

56

notational simplicity, dH(Ci’Cj)-o is assumed for all Cj's in the PLA

under test. Let R 's, j-l,2,..,p, be denoted as the columns of the

J

array D, and

Siq- I Cj | dH(Ci’Cj)-O and diq - djq - l I.

Copollpzy 1.1:
If Siq-{Ci}’ then PGD(diq)-Ci.
Proof:
Siq-{Ci} implies that either dH(Ci’Cj) 2 l, or diq is the only 1

in the column Rq. In the former case, by Theorem 1, PGD(d1q)-Ci.
In the latter case, since C1 is the only product term in the
output function Oq’ it is obviously isolated, hence, from case

DFl, PGD<diq)-Ci°

If the set S contains more than one product term, then the D-

iq
fault at diq may be masked by djq's’ unless Ci can be seperated from
the other Cj's in siq' For the purpose of simplicity and clarity, the

case of S-{C I is first considered in Theorem 2, and the general

i’cj

case will be presented in Theorem 3.

m2:

If Siq-{C1,Cj),'then PGD(diq) - E {Ci/cjk | cik-x and c

jk # x}.

57

Lemma

If Ci is covered by Cj’ then Di and Dj are bit-disjointed.

ngof:
Assuming that Di and Dj are not bit-disjointed, there exists a

bit k such that dik-djk-l' Since C1 is covered by Cj’ applying

any test pattern to activate C would also activate C . This

i J

results in a redundant bit at dik and contradicts the assumption

of irredundancy. Therefore, D and D are bit-disjointed.

i J

In essence, the crosspoint at d is detected as redundant if C1

is
is covered by C and d -d -1. This is exactly the same as the

J’ 1Q Jq

redundancy detection rule RCDl.

ma:
If D1 and DJ are not bit-disjointed and dH(Ci’Cj)-o’ then there
exists a bit k such that c1k - x and cjk # x.

Proof:
Assume that there exists no such k, i.e. C1 is covered by Cj'
By Lemma 2, Di and DJ are bit-disjointed, contradict the
assumption.

Lama:
If Siq-{C1,Cj}, then there exists a bit k such that the test

pattern from C1/ can detect the D-fault at d

ch iq'

58

Since 8 - C ,C , i.e. C ,C -0 and d -d -l, or, D and D.
iq ‘ 1 J’ dH‘ 1 J) iq Jq i J

are bit-disjointed, by Lemma 3, there exists a bit k such that

cik-x and cjk # x. Applying a test pattern from Ci/cjk will

activate only the line C1 and deactivate the others. By Lemma 1,

the D-faults at diq can be detected by this pattern.

P e em

From Lemma 4, Ci/Ejk is one of the PGD(diq) at bit k. Therefore,

PGD(d x and c i x}.

iq)' U {01/ jk ' cik ‘ jk

Eram212_é:

Consider the following PLA,

C1: 1 0 x x D1: 1 l 1 0 0
C2: x 0 O 1 D2: 1 1 l 0 0
C3: x 0 x 0 D3: 0 1 0 1 0
C4: 1 x l 1 D4: 0 0 1 0 1

This PLA is the same as the PLA in Example 1, except the first

product line is removed. It is easy to check that dH(Cl’C )-0, for

J

j-2,3,and 4, and Sll-{Cl’ CZ}. The test set PGD(dll) is generated as
follows:
(1) Since c13-x and c23-O # x, the test patterns are selected

from Cl/c23-(c11 c12 c23 c14)-(101x), or {(1010),(1011)}.

59

(2) Since cla-x and c24-1 # x, the test patterns are selected

from Cl/C )- -(10x0), or {(1000), (1010)}.

24 '(°11° 12 c13 C24
By Theorem 2, the test set is the union of the test patterns generated

in the both cases, or

PGD(d11)-TP1-(101x)U(10x0)-{(1000),(1010),(1011)}.
Theogem 3:
If Siq-{Cj | dH(CN j)- -0 and diq- djq-1}’ and s - |Siq| > 1, then
PGD(diq) - TP1 n TP2 n ...n TPs
where each TP as shown in Theorem 2, is the test set generated

k!
for the pair (Ci’ck)'

Prior to the proof of Theorem 3, we consider Lemma 5.
Lemma

If TP and TP are any two sets of test patterns generated for

l 2
the pairs Mj) and (C1,Ct), respectively, then TPl and TP2
have common test pattern(s).

Proof:
By Theorem 2, TPl- U { C 1/c cjk | C1 -x and cjk # x } and

rez— U I ci/ctr I

Consider Ci/cjk and Ci/ctr subsets of TP1 and TP2,

c -x and c # x .
ir tr }

respectively. If k < r, then

Tp - (cil’c12""cjk"'ctr""cin)

is a subset of both C 1/cjk and Ci/Etr' In other words, TP1 and

60

TP have common test patterns. The same result can be obtained

2
for k > r. On the other hand, for k - r, if c. - E is
jk tr

assumed, then the "don't care" term cik is a logical OR of cjk

and c . Since for all other bits, c is covered by both c.
tr iy jy

and cty' Thus C1 is covered by C3 U Ct’ resulting that the bit

diq is redundant. Therefore, cjk-Ctr’ i.e., Ci/Cjk is the

common subset of both TP1 and TP27

Proof pf Ibeogem 3:

Since each TPJ is a test set for the pair (C1,CJ), this set

consists of the test patterns which can seperate Ci from Cj'

Therefore, the test pattern used to seperate C1 from others will

be the intersection of the test sets TPl’ TP2,.., and TPs' From

Lemma 5, it can be shown that this intersection is not empty.

Fresnel:
Consider the PLA in Example 6. Since Slz-{C1,C2,C3} and s-2,

there exist two don't cares in 01' Therefore, the PGD(dlZ) is

generated as follows:
(1) From Example 6, TPl-(101x)U(le0)-{(1000),(1010),(1011)}.
(2) Similarly, for (C1,C3), TPZ-(lel)-{(1001),(1011)}.

By Theorem 3, PGD(dll) - TP1 n TP2 - {(1011)}.

Similarly, PGD(d12)-(10x0)-{(1000),(1010)}.

61

The test set PGD(diq) consists of the test patterns which are
used to detect the D-fault at diq’ where diq-l. Thus, the test set
PGD(Di) is a collection of the test sets that consist of a test
pattern from each PGD(diq), for all q. However, due to the

relationship among the test sets PGD(diq)'s, the generation process

for the test set PGD(Di) can be simplified as follows.

Lemma 6:

If the column Rq covers Rj’ then PGD(diq) is a subset of
PGD(dij)'
Proof:

Since Rq covers R], in other words, every pair of l-valued

entities in Rj will also be in Rq’ then the test patterns

generated for d are always for d i.e., PGD(diq) is a subset

iq ij’
of PGD(dij).

Ems—Q:

Since D1 contains only three crosspoints at d10’ dll’ and d12,

the test set PGD(DI) is determined by the test sets PGD(d j-0, l,

lj)’

and 2. Among the corresponding columns R0, R1 and R2 ,it is found

that the columns R1 and R2 are maximum, i.e. PGD(le) is a subset of

both PGD(dll) and PGD(d Therefore, PGD(Di) is determined by these

12"
two subsets. Specifically, from Example 8,

62

PGD(d11)-{(1011))
and PGD(d12)-(10x0)-{(1000),(lOlO)}.
then the element of the test set PGD(Di) is formed by selecting a
pattern from both PGD(dll) and PGD(dlZ)’ or
PGD(D1)-{{(1011),(1000)},{(1011),(1010)}}
This is exactly the same as the test set generated in the case DF3.
In fact, if the generated test sets, PGD(diq)’s, are the same for
each d in Di’ i.e., PGD(Di)-PGD(diq), then this is equivalent to

iq
the case DF2.

The test set for detecting the D-faults can be summarized in the

following theorem,

Ihepggm 4:
Consider Si-{le dH(Ci,CJ)-0}, and s - |Si|.
( i) If s - 1, then PGD(Di)-Ci, or
(ii) If s > 1, then the test set
PGD(D1)-{ {p1,..,pk} I each pj, j-l,2,.,.k, is selected from

PGD(d ) for all maximum columns R I. (l)

1J J

Erect:
If s-l, then either Si-{Ci} or dH(C1,CJ)21. By Theorem 1,
PGD(D1)-C1. On the other hand, if s>l, then the test set PGD(Di)

is generated from the test sets PGD(diq)'s that correspond to the

maximal columns. The test set PGD(Di) is expressed as Equation

(1).

63

Based on Theorem 4, the test pattern generation for D-fault is

summarized in Algorithm PGD.

Algorithm PGD:

Step 1: (Test pattern generation)
DO i-l to m (m is the number of product lines)
BEGIN
IF s-ISi
BEGIN
Determine the maximum columns
PGD(D1 ) is generated by equation (liq,s
END
END

|-1, THEN PGD(D1 )-C1 ELSE

Step 2: (Test pattern compaction)
Eliminate the duplicated test patterns from PGD(Di) for all
i.
Exam 9:

Consider the PLA in Example 1. Applying the Algorithm PGD, the

test set for D-faults are generated as follows:

PGD(DO) - (0x11) - {(0011),(0111)},

PGD(Dl) - {{(1011),(1010)}, {(1011),(1000)}},
PGD(DZ) - {(0001)}.

PGD(D3) - (00x0) - {(0000),(0010)}, and
PGD(DA) - {(1111)}.

Thus, {(0011),(1011),(1010),(0001),(0000),(llll)} is one of the test sets.

64

B Tes et fo -fau ts
Let PGG(cik) be the test set for a G-fault at the crosspoint

c #x. As shown in the K-maps, a G-fault at c may cause the

ik ik

additional logics to expand toward the corresponding direction, Eik’

or to the adjacent minterms C In fact, these adjacent minterms

i/Cik'
must be free. Otherwise, the corresponding crosspoints are redundant.

Consequently, if an additional term is presented in one of these

adjacent minterms, a G-fault at c1k is detected. Specifically, the

test set for detecting the G-fault at c is generated as follows:

ik

Case GFl: If the term 01/3 3 isolated with respect to any given

ik 1
output function, then Ci/Eik is chosen as the test set for

Cik.

Case GF2: If the term Ci/Eik is non-isolated, then the free minterms

are chosen as the test set for c .

°f Ci/cik ik

Erannle.19:

Consider the same G-D irredundant PLA and its K-maps (Figure 18).

From the K-map for O the minterms Co/coo-(lxll) are all free. In

3’
other words, Co/E00 is isolated with respect to 03. Thus, by the case

GFl, these minterms can be chosen as the test set to detect G-fault at

or PGG(c - (1x11). On the other hand, from the K-

°oo' oo) ' Co/coo

maps for 00, 01, and 02, although the non-isolated minterms

65

Cl/Eoo-(00xx) has some bound minterms, it still contains several free

minterms, such as (0000) and (0010) in O (0011) in O and (0000),

0' l’

(0010), and (0011) in 0 Thus, PGG(c10)- {(0000),(0010),(0011)}.

2.
Similarly, _the remaining PGG(cik)'s are generated as shown in

Table 2.

 

 

 

 

 

 

 

 

 

 

 

Table 2. Test Set for G-faults.
PGG(Cik)
k: 0 l 2 3
i:
0 (1x11) -- (0x01) (0x10)
(00x0)
1 (llxx) -- --
(001x)
-- (x101) (0011) (0000)
-- (xlx0) -- (8031)
(0x11) -- (1x01) (1x10)

 

 

66

Similar to the test set generation process for D-faults, the
concept of Hamming distance is also applied here. The case GFl is

equivalent to the following theorem.

Theorem 5:

If dH(Ci/cik’cj) z 1, for all Cj's, then PGG(Cik)=Ci/Cik'

Proof:

If dH(Ci/cik’cj) 2 1, for all C s, then the minterms Ci/Cik are

J

all free in all output functions. Consequently, PGG(cik)=Ci/Eik.

Note that, if the crosspoint d is the only one in the output

iq
function Oq’ then the K-map with respect to Oq may contain only the

product term C Obviously, the adjacent minterms of C in the K-map

i' i

are all free. In this special case, the test set is chosen as

follows.

Theorem—6:
If diq is the only crosspoint in Oq, then PGG(cik)-Ci/cik’ for
all cik'

Progf:
Since the minterms Ci/Eik’ for all cik’ are all free, they can

be chosen as test patterns, thus, PGG(cik)- Ci/cik'

67

Consider the case of dH(Ci/E )-0, this is equivalent to the

ik’cj
case GF2. For notational simplicity, dH(Ci/Eik,Cj)-O is assumed for

all Cj's in the PLA under test. R 's, j-l,2,..,p, are again denoted

J

as the columns of array D. The PGG(c is denoted as the test set

ik)q

generated with respect to the output function Oq (or column Rq) for a

G-fault at cik' This test set can be generated in a manner similar to

Theorem 3.

Theorem 2:
Let Tik - { Cj | dH(Ci/cik’cj) - 0 }. If t - lTikl > 0, then

PGG(cik)q - TP1 n TP2 c ... n TPt
where TPJ is the test set generated for the pair (Ci/Eik'cj)'
pgoofi: It is the same as Theorem 3 by looking Ci/Eik as C1 and t as s,
respectively.
Erannle.li=

Consider the test set PGG(clo) of the PLA in Figure 18. It can

be easily check that dH(C1/E for j-O, 2, and 3. The cubical

lovcj)-OI

notation is rewritten as follows:

0 1 2 3 a
c /E : o o x x D : 1 1 1 o 0
1com: o x 1 1 D3: 1 o o 1 0
02 x o o 1 D2: 1 1 1 o 0
03 x o x 0 D3: 0 1 o 1 o .

68

In 00, the test sets for the pairs (Cl/CIO’CO) and (Cl/c10,C2)

are TPl- {(000x),(00x0)} and TP2- {(001x),(00x0)}, respectively.

Thus, PGG(clO)o - TP1 n TP2-{(000x),(00x0)}n{(001x),(00x0)}-{(00x0)}.

From the K-map for O the adjacent minterms (0000) and (0010) of C

0’ l

are free. They can be chosen as the test set regardless other

adjacent minterms (0001) and (0011) are bound by C2 and C0,

respectively.
Similarly, from either Theorem 7 or the K-maps, we can generate

PGG(c - {(001x),(00x0)}n {(00xl)} = {(0011)} for O and

10’1 1'

PGG(c - {(001x),(00x0)} for O

1o’2 2'

Because each individual test pattern in PGG(c can detect the

ik)q

D-fault at cik’ the test set PGG(cik) is then a collection of all

elements in PGG(c Therefore,

ik)q'
PGG(c PGG(c U PGG(c

U PGG(c - {(001x),(00x0)}.

10" 10’0 1o)1 10)2

and we conclude that the test set PGG(cik) - U I PGG(cik)q }.

It is inefficient and impractical to derive all poosible test
sets for the corresponding outputs without simplification. In fact,
from the above example,

PGG(clo) - {(001x),(00x0)} - PGG(c10)2.

This is due to the fact that the column R2 covers both columns R0 and

R1.

69

Lemma 8:
If column R covers R , then PGG(c. ) is a subset of PGG(c. )..
q j 1k q 1k j
ngof:
Since the set PGG(cik)r is the generated test set with respect to
the output function Or. The test set is generated by
intersecting the test sets of pairs. If Rq covers Rj’ in other
words, the bits in R.j are also in R , then the more intersection

is performed, the smaller set is obtained. Therefore, PGG(Cik)q
is a subset of PGG(cik)j'

Based on the relationship derived in Lemma 8, the test set can be
simplified as

PGG(cik) - U { PGG(c | Rq's are the minimum columns }. (2)
q

ik)q
Ibeorem.§=
Consider Tik - I Cj | dH(Ci/cik’cj)-o }, and t - lTikI'

(1) if t - 0, then PGG(cik)-C1/E or

ik’
(ii) if t z 1, then PGG(cik) is expressed in (2).

Proof:
If t-0, then dH(Ci/cik’cj) 2 l, by Theorem 5, PGG(cik)-Ci/cik°
If t z 1, by Lemma 8, PGG(cik) can be expressed as the union of

the test sets generated with respect to the minimum columns.

70

Corollary 8.1:
If diq is the only crosspoint in column Rq, then
PGG(cik)-Ci/Cik'
Proof:
If diq is the only crosspoint in column Rq, then Rq is minimum, by

Theorems 6 and 7, PGG(cik)-Pcc(cik)q-Ci/cik°

Based on the above discussions, the test generation for G-faults

is summarized in Algorithm PGG.

W:

Consider the PLA in Example 1, applying the Algorithm PGG, the
test set for D-fauls at each c1k are the same as in Table 2. The test
compaction process will eliminate the duplicated patterns. Therefore,

a test set for both D-faults and G-faults in the PLA of Figure 18 is

{(0000),(0001),(0011),(0110),(1010),(1011),(1101),(1111)}.

71

Algorithm PGG:

Step 1: EIGEN(i)-false, i-1,2,..,m (m is the number of product lines)

Step 2:

Step 3:

Step 4:

DO j-l to p (p is the number of output lines)
BEGIN (Theorem 6)
IF d is the only crosspoint in O , THEN
BEGINq q
EIGEN(i)-true.
DO k-l to n (n is the number of input lines)
BEGIN
ENDIF c1k # x THEN PGG(cik)-Ci/
END
END

Cik.

D0 i-l to m
BEGIN (Theorem 8)
IF (EIGEN(i)-false) THEN

BEGIN
D0 k-l to n
BEGIN
IF (c1k # x) THEN
BEGIN
IF t-IT | - 0_ THEN
PGG(c )-C /c
ELSE ik i ik
BEGIN ,
determine the minimum columns R 's
PGG(c ) is dereived as the equationq(2).
ik
END
END
END
END
END

(Test Pattern Compaction)

Eliminate the duplicated test patterns from PGG(c. ) and
1k

PGD(Di).

72

5.3. Simulation Results

The Proposed test pattern generation algorithm has been
implemented on a VAX 11/780 in FORTRAN. In order to demonstrate the
effectiveness of the proposed algorithm, the ten PLAs in [BoM84] have
been simulated and a comparison of the number of test patterns
required with other techniques [FuK8l][SKF81][Kha83][SaT82][BoH8h] are
given in Table 3. The test length for each example shown in Table 3
is derived according to the heuristic that the test set is comprised
by choosing every first test pattern of the test sets PGD(Di) and
PGG(cik) and eliminating the duplicated test patterns. Therefore, the
test length presented in Table 3 for the proposed algorithm can be
improved if a better heuristic algorithm for test generation and
compaction process is applied.

To collect experimental data, we also used testable versions of
49 PLAS that were used earlier in collecting data on efficacy of a PLA
minimization program called ESPRESSO [BHM84]. After the PLA raw data
are processed by ESPRESSO, the minimized PLAs with the test lengths
are listed in Table 4, and these minimized PLA data are supposed to be
irredundant. In fact, some redundant PLAs, as the entries marked with
'*' in Table 4, are detected by our program. For example, 29
redundant crosspoints have been detected in the PLA 'cps' which has 29

input lines, 162 product lines, and 109 output lines.

73
Table 3. Comparison of the number of test patterns

MW

Master 104 902 515 594 540 51
New alu 102 871 496 572 520 33
bar new 95 598 398 528 462 62
recur 44 153 101 117 90 16
traffic 36 113 74 88 72 9
alu test 119 1105 650 792 684 87
cond 83 549 338 408 312 58
bar 87 530 350 435 337 64
rimp 119 1028 626 780 663 104
Cerber 159 1927 1102 1300 1150 160

Table 4. The number of test patterns required in some PLAs

MEL WWW

 

adr4 8 75 5 9O root 8 57 5 101
a1u1 12 19 8 8 sqn 7 38 3 68
a1u2 10 68 8 73 sqr6 6 50 12 46
a1u3 10 66 8 70 ti 47 213 72 346 *
ala 10 25 12 57 tial 14 S79 8 1179 *
ch 26 179 11 451* vg2 25 110 8 178
bca 26 180 46 1445 win 4 9 7 8
bob 26 156 39 1270 x1dn 27 110 6 194
be: 26 137 45 1143 x6dn 39 81 5 209 *
bed 26 117 38 977 x9dn 27 120 7 194
chkn 29 140 7 505 :4 7 59 4 68
c014. 14 14 1 106 in3 35 74 29 140 *
cps 24 162 109 919* in4 32 212 20 394 *
dc1 4 9 7 13‘ inS 24 62 14 214
dc2 8 39 7 71 in6 33 54 23 183

die: 8 120 5 175* in7 26 54 10 82
dk27 9 10 9 l7 misg 56 69 23 43
dk48 15 21 17 34 mish. 94 82 43 17
e31 4 7 7 9 0194. 8 127 8 164
£513. 8 76 8 74 ope 17 79 69 223
gery 15 107 11 345* reddl 8 75 5 90
inO 15 107 11 347 rck1 32 32 7 529
inl 16 104 17 478 rd53 5 - 31 3 32
in2 19 135 10 342 rd73 7 127 3 128
rise 8 28 31 39
Ni: the number of input lines.
Np: the number of product lines.
No: the number of output lines.

CHAPTER VI

Conclusion

Two testable PLA designs for both function-independent and
function-dependent tests, have been presented.

The key to easily testable PLA design is the ability to select
any arbitrary one product line during the test. This key concept has
been implemented to design a product line activator in Chapter IV. It
has been shown that the proposed design has the following salient
features: (1) homogenous and regular structure; (2) less chip
overhead; (3) no performance degradation during the normal operation
due to the added hardware; (4) no additional I/O pin required; and (S)
no extra test sequence needed.

The above key concept is also used to the test pattern generation
in Chapter V. One of the major contributions in this approach is the
introduction of the concept of Hamming distance to the test pattern
generation. The test pattern generation problem is, therefore, turned
in to the problem of how to choose a test pattern so that a product
term can be seperated from others.

Based on the proposed algorithm, a software program has been
implemented on a VAX 11/780 in Fortran. This program provides not
only the generated test set, but also the information of redundant

crosspoints in the PLA under test.

74

75

Since the "extra device" fault model in modern VLSI circuits has
been less significant than other fault models normally considered for
PLAs [KhBBS], in Chapter V, the emphasis of the test pattern
generation is on the detection of G and D faults. Also, as it has
been shown, if Ts is the test set for detecting single G and D faults,
then any detectable combination of G and D faults in a G-D irredundant
PLA, is detected by TS [Smi79]. -Therefore, the proposed test
generation for the single fault detection can essentially be applied
for the multiple fault detection.

Although the proposed approach concentrated on the G and D
faults, the same principle can be extended to the shrinkage and
appearance faults, if necessary. However, this extension is held only
if the combination of G and D faults and the combination of S and A
faults do not occur simultaneously [Smi79].

As mentioned earlier, the motivation of doing this work is to
reduce the hardware overhead for the test purpose in the design of
fault-tolerant PLAs. Since the extra hardware overhead may offset the
yield improvement, thus, the test generation approach that requires no
hardware overhead may be superior to the testable design approach for
this purpose. The development of an efficient test generation process
with the minimal test length is of significient importance that leads
to a future research direction.

In essence, the proposed pattern generation provides a potential
to derive the near-minimal test length. Unlike the heuristic process

applied to generate the test set in the existing generation

76

algorithms, the proposed algorithm is capable of generating all
possible test patterns for each fault. Therefore, the derivation of
the minimal test length can be accomplished by a method applied to
derive the minimal covering set of fault-detection tests for the
combinational circuits. Table 5 shows that all possible test patterns
for each fault of the PLA in Example 1 are listed. The test set
generated in Example 12 is essentially the minimal covering set of
this table.

One of the most important issues in the design of fault-tolerant
PLAs is fault-location. The faults must be located so that the spares
can be efficiently allocated to repair the partially defective chips
[WeL87]. The fault location problem had been overlooked for years
until the fault-tolerant PLA being recently proposed. Research
efforts have been devoted to the fault location problem.

It is possible to develop a fault location algorithm based on the
proposed test generation approach. Again, since all possible test
pattern(s) are generated, if the fault-location experiments [Koh78]
developed for the combinational circuits are implemented, it is
possible to generate the test set and set schedule to locate the

fault which leads to an another future research direction.

 

Table 5. Test set for Figure 18.

77

 

 

 

COO

 

 

 

N00

 

MOO

 

Or-‘O

 

rnr-n

 

 

 

uNO

 

Hun

 

HMO

 

0&0

 

~¢~n

 

urn

 

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

 

HH

 

HD-‘l-‘H

 

 

[AbF86]

[BHM84]

[BoM84]

[cca79]

[Cha78]

[DaM81]

[EiL80]

[FKHBO]

[mass]

[Fuj84]

[FuK8l]

LIST OF REFERENCES

Abraham, J. A. and W. K. Fuchs, "Fault and Error Models for
VLSI", Proceedings of IEEE, Vol. 74, No. 5, pp. 639-654, May
1986.

Brayton, R.K., Hachtel, G.D., McMullen and A.L. Sangiovanni-
Vincentelli, Logic Hinimization Algorithm for VLSI Synthesis,
Kluwer Academic Publishers, Hingham, MA, 1984.

Bozorgui-Nesbat, S. and E. J. McCluskey, "Lower Overhead
Design for Testability of Programmable Logic Arrays", 1984
International Test Conference, pp. 856-865.

Cenker, R.P., Clemons, D.G., Huber, W.R., Petrizzi, J.B.,
Procyk, F.J., and G.M. Trout, "A Fault-tolerant 64k Dynamic
RAM", IEEE Trans. on Electr. Dev., Vol. ED-26, No. 6, pp. 853-
860, June 1979.

Cha, C. W., " A Testing Strategy for PLAs", Proc. 15th Design
Automation Conference, pp. 326-334, 1978.

Daehn, W. and J. Mucha, "A Haredware Approach to Self-testing
of Large Programmable Logic Arrays", IEEE Trans. on Computers,
Vol.C-30, pp. 829-833, Nov. 1981.

Eichelberger, E. B. and E. Lindbloom, "A Heuristic Test-
pattern Generator for Programmable Logic Array", IBM J. Res.
8 Dev., pp. 15-22, Jan. 1980.

Fujiwara, H., Kinoshita, K. and H. Ozaki, "Universal Test
Sets for Programmable Logical Array", Proc. International
Symposium on Fault-tolerant Computing, pp. 137-142, 1980.

Fung, H.S. and S. Hirschhorn, "An Automatic DFT System for the
Slic Silicon Compiler", IEEE Design and Test, pp. 45-47, Feb.
1986.

H. Fujiwara, "A New PLA Design for Universal Testability",
IEEE Trans. on Computers, Vol. C-33, No. 8, pp. 745-750, Aug.
1984.

Fujiwara, H. and K. Kinoshita, ”A Design of Programmable

Logic Arrays with Universal Test", IEEE Trans. on Computers,
Vol. C-30, No. 11, pp. 823-828, Nov. 1981.

78

[HaR85]

[HJA84]

[Kha83]

[KhBSS]

[KhM81]

[Koh78]

[KoP86]

[MAD82]

[MeC80]

[Min84]

[M0086]

[NeM83]

79

Ha, D.S. and S.M. Reddy, "On the Design of Testable Domino
PLAs", 1985 International Test Conference, pp. 567-573, 1985.

Hua, K.A., Jou, J.Y. and J.A. Abraham, "Built-In Tests for
VLSI Finite-State Machines", Digest, Proc. 14th International
Symposium on Fault-Tolerant Computing, pp. 292-297, 1984.

Khakbaz, J., "A Testable PLA Design with Low Overhead and High
Fault Coverage", Proc. 13th International Symposium on Fault-
Tolerant Computing, pp. 426-429, 1983.

Khakbaz, J. and S. Bozorgui-Nesbat, "Mimimizing Extra Hardware
for Fully Testable PLA Design", International Conference on
Computer Aided Design, pp. 102-104, 1985.

Khakbaze, J. and E. J. McCluskey, "Concurrent Error
Detection and Testing for Large PLAs", CRC Tech. Rep. 81-14,
Stanford Univ., Oct. 1982.

Kohavi, 2., Switching and Finite Automata Theory, McGraw-Hill,
1978.

Koren, I. and D.K. Pradhan, "Yield and Performance Enhancement
through Redundancy in VLSI and WSI Multiprocessor Systems”,
Proceedings of the IEEE, Vol. 74, No. 5, pp. 699-711, May
1986.

Mak, G. P., Abraham, J. M. and E. S. Davidson, "The Design
of PLAs with Concurrent Error Detection”, Proc. 1982
International Test Conference, pp. 303-310.

C. Mead and L. Conway, Introduction to VLSI system, Addison-
Wesley, 1980.

Min, Y., "A PLA Design for Ease of Test Generation", Proc.
14th International Symposium on Fault-Torelant Computing,
pp. 436-442, June 1984.

Moore, W.R., " A Review of Fault-Tolerant Techniques for the
Enhancement Integrated Circuit Yield", Proceedings of the
IEEE, Vol. 74, No. 5, pp. 684-689, May 1986.

J. Newkirk and R. Mathens, The VLSI Designer's Library,
Addison-Wesley, 1983.

[OsH79]

[SaS86]

[SaT82]

[Sch78]'

[scus3]

[semen]

[SKF81]

[SMD80]

[Smi79]

[80686]

[SoP80]

80

Ostapko D. L. and S. J. Hong, "Fault Analysis and Test
Generation for Programmable Logic Array", IEEE Trans. on
Computers, Vol. C-28, pp. 617-626, Sep. 1979.

Semi, M. and R. Stenfanelli, "Reconfigurable Architectures
for VLSI Processing Arrays”, Proceedings of the IEEE, Vol. 74,
No. 5, pp. 699-711, May 1986.

Sato, T. and Y. Tohma, "A New Configuration of PLA with
Functional Independent Test", Tech. Rep., Dept. of Computer
Science, Tokyo Inst. of Technology, Tokyo, Japan, Oct. 1982.

Schuster, S.E., "Multiple 'Word/Bit Line Redundancy for
Semiconductor Memories", IEEE J. Solid-State Circuits, SC-l3,
No. 5, pp. 698-703, 1978.

Somenzi F., Gai S., Mezzalama M. and P. Prinetto, "A New
Integrated System for PLA Testing and Verification”, IEEE 20th
Design Automation Conference, pp. 57-63, 1983.

Somenzi, F., Gai S., Mezzalama M. and P. Prinetto,
”PART:Programmab1e Array Testing Based on a Partitioning
Algorithm", IEEE Trans. on Computer Aided Design, Vol. CAD-3,
No. 2, pp. 142-149, April 1984.

Saluja, K.K., Kinoshita, K. and H. Fujiwara, "A Multiple
Fault Testable Design of Programmable Logic Arrays", Proc.

11th International Symposium on Fault-Torelant Computing, pp.
44-46, 1981.

Stapper, C.H., Mclaren, A.N., and M. Dreckmann, "Yield Model
for Productivity Optimization of VLSI Memory Chips with

redundancy and parially good product", IBM J. Res. Dev.,
Vol.24, pp. 398-409, May 1980.

Smith, J. E., "Detection of Faults in Programmable Logic
Arrays", IEEE Trans. on Computers, pp. 845-853, Nov. 1979.

Somenzi, F. and S. Gai, ”Fault Detection in Programmable
Logic Arrays", Proceedings of the IEEE, pp. 655-667, Vol. 74,
No. 5, May 1986.

Son, K. and D. K. Pardhan, "Design of Programmable Logic
Arrays for Testability", Proc. 1980 International Test
Conference, pp. 163-166.

[Ta584]

[TFA85]

[waves]

[WeL86]

[WVL86]

[Zhu86]

’81

Tamir, Y. and C. H. Sequin, "Design and Application of Self-
Testing Comparators Implemented with MOS PLA's", IEEE Trans.
on Computer, Vol. C-33, No. 6, pp. 493-505, June 1984.

Treuer, R., Fujiwara, H. and V.K. Agrawal, "Implementing a
Built-In Self-Test PLA Design", IEEE Design & Test, pp. 37-48,
April 1985.

Wey, C.L., Chang, T.Y., and M.K. Vai, "On the Design of Fault-
Tolerant Programmable Logic Arrays", Proc. of International
Computer Symposium, Tainan, 1986, pp. 298-304.

Wey, C.L., and F. Lombardi, "On the Repair of Programmable
Logic Arrays (RPLA)", Proc. 1986 IEEE International Symposium
on Circuits and syatems, pp. 649-652, San Jose, CA. May 5-7,
1986.

Hey, C.L., Vai, M. R., and F. Lombardi, "On The Design of A
Reduntant Programmable Logic Arrays (RPLA)", IEEE J. of Solid-
State Circuits. (in press).

Zhu, Xi-an, "A Knowledge-Based System for Testable Design
Methodology Selection", Tech. Rep. CRI-86-23 U.S.C., Ph.D.
dissertation.