J32 e IEEE D&T 1984 11

D&T

ira _nsia:n o_n

This article is translated in revised form from

Monographs

_of

^the

_Des4itn

^A

_wtoiatnior

Working Grouip oftheInform,ation Processing

Societv ofJapan, Vol. 19,^{No.3, Nov.} 1983. and isreprinted withpermission. © 1983 IPS.1

Design for Testability

for Complete Test

Coverage

Very large scale circuits present great obstacles to complete

testing. A pattern generation algorithm offers a direct approach

to the problem.

Akira Motohara and Hideo Fujiwara, Osaka University

T he

problem

of

reliability

is

gain- make

it

difficult

toachievea

_high

rate

T

ing increasing importance with of test coverage.

the rapid advance of semiconductor

Designing

for

testability

has been technology toward very large scale in- offered as a

solution of

this

problem

tegration of logic circuits. The very (see Williams and Parker

i).

Methods large scale of the circuits, however, to reduce the

complexity

of

testing

for makes test pattern generationextreme-

sequential circuits

to the

level for

com-

ly difficult,

and when test patterns can-

binational circuits

have

been proposed

not be obtained within the allowed and

achieved.24 However, for

com- computation time, aborted

faults

binational

circuits of large scale,

it is still

_extremely

difficultto achieve 100 percent test coverage.

summary Among ^the

^most

promising ^DFT

Some design-for-testability techniques, such as level-sensitive scan methods are those aimed at complete design, scan path, and scan/set, reduce test pattern generation of sequen- test coverage through the addition ofa tial circuits to that ofcombinational circuits by enhancing the controllabili- few hardware elements to thecircuit. ty and/or observability of all the memory elements. However, even for

com-

This redundant hardware is called test binational circuits, 100 percent test coverage of large-scale circuits is

points. 5'6

The test point strategies we generally very difficult to achieve. This article presents DFT methods are considering here fall into four cate- aimedatachievingtotalcoverage. Two methods arecompared: One,based

_gories-

on testability analysis, involves the addition of test points to improve

_g1

_I

_ert

_{AND OR t} testability beforetest pattemgeneration.The other method employs a test

(1) _{Inse N,O gates.}

pattem generation algorithm(the FAN algorithm). Results show that 100 (2) Change NOT gates to NOR, percent coveragewithintheallowed limits is difficult with the former ap- NAND, gates.

proach. The latter, however,enables us to generate a test pattern for any

(3)

^Add

primary input points

^for detectable fault within the allowed time limits, and 100 percent test control.

coverage is possible. (4) Add primary output points

for

observation.

These _strategies are illustrated in

Figuire

^1.

When two or more of the control test

_{points (Figure}

_{1, a-c)}aretobe

_used

at thesametime, thev'^{are merged} into oneprimarv input to reduce the num- ber of additional input points (Figure 2).Moreover, if_scan-path

technliqlS,

as_showniin_Figure3,^areused,one test

point wvill^then correspond ^toone flip- flop,and the increase in thenuimberof external _points can be avoided.

We have investigated ^two methods of_alteringcircuitstofacilitatetestabil- itythroughthe addition oftest _points.

Thefirst method is basedontestabilitv analvsis and involves the addition of test points to improve testability be- fore a test _pattern is generated. Ob- tained results show that 100 percent test coverage within the allowed time limits is difficult to achieve with this method. The second method

_emiploys

a test pattern generation

algorithm,

enablinig

^{us to} generate ^{a test} pattern for any detectable fault wvithin the allowed time limits, and

_making

100 percenttest coveragepossible.Wepro-

grammed ^{the two}methods, and after

evaluating

^some circuits with several thousand

gates.,

vewereabletoobtain very favorable results wvith the second method. In thisarticle wveexamnineand compare these methods.

Circuits considered here are com-

binational circuits_consisting ofAND, OR, NOT, NAND, and NOR ele- ments, and faults are assumed to be Figure ^1.Typesof test

points.sigetukaful.

DFT

_through

testability analysis

To increase the effectiveness oftest pattern generation, testability ^mea-

sures, which express the ^{ease or} dif- ficulty of testing, ^are used in two al- gorithms: ^{Podem7 and} Fan,8 short forpath-oriented decision-making^and fanout-oriented test generation algo- rithm, respectively.

Herewedraw attentiontothe mea- surement of testability, ^{and we de-} scribe methods of_designmodification that facilitate testing through ^{the im-} provement oftestability. ^{The overall}

Figure^{2. Addition}of test

points,

^{flow ofthese DFTmethods}is shown in

Figure 4. Although theentire process could be automated, ^we have imple- mentedthesystem ininteractive form to improve efficiency by enabling the designer to input the choice ofsignal

lines needing improvement and the SWTC

_FLOP

SWITCH FLIP-

decision as to whether the desired degree of testability has been achieved. Testability analysis. Various ^mea-

sureshavebeen proposedasmeasures COMBINATIONAL^CIRCUIT

of testability.9-1 Here we use Gold- stein's measures,9 which express the

costs of controlling and observing. Figure3. Scan path method. Thus, to maximize testability, these

costs must be minimized. Goldstein proposed six measures in all, threeof which_applytocombinationalcirciiits:

* [CC' _(L)] The smallest number _TsaiiyAayi

of signal lines which ^{must have} their logical values set in orderto

Coc fSga ie

setthe logical valueof signal line^L Choiceof Signal Lines for to 1; called signal line L's "I"

controllabilitycost.

* [CCO (L)] Defined in the same lec ionofTest Point

way as [CC' (L)]; called signal InsertionLocation

line L's "O"controllabilitycost.

* [CO (L )IThe smallest numberof nserion^ofTest Points

signal lines whichmust havetheir logical valuessetin orderto prop-

agatethe valueofsignal line L to _Hasdesired

_testabty

primaryoutput;called the observ- beenachieved?

abilitycost of signal lineL. Each of these valuescan be found for any given circuit through simple cal-E_D culations.

Selectionof_signallines_needingim-

Figure

4. Work sequence in testability analysis

_DFr

method. provement. At this point the designer

can see from the system the greatest controllability and observability cost values. Then hedecideswhether to im- prove thecontrollability^ortheobserv- ability and sets the threshold values. Values exceeding threshold valuesare then improved, starting from those nearestthe

primary input signal

^line.

Test point insertion locationsearch. Insertingtestpointsasshownin Figure I, a-c, markedlyimproves^thecontrol- lability ^{for the}signal ^{lines ontheout-}

put side of the insertion point, leaving the input side

unchanged.

Accord- ingly, test points are inserted several

gates to the input side of signal lines Figure 5. Test point insertion location search.

with high controllability costs. Simi- duce here the method that was effec- neously high controllability cost. ^In larly, to improve observability, test tivein actual tests. the former case, it is best to insert a^test pointsareinsertedseveralgatestothe Lookingatsignal line with highcon- point a bit further toward the input output sideofthesignallines withhigh trollability cost, we find two situa- side.Inthe latter case, insertionof the observability costs. The exact place- tions. Inthe first, oneofseveralinput test point is best on thesignal lineit- mentof test points is an extremely dif- lines dominates the others. In the sec- self. Space does not permit us to go ficultproblem, however, andweintro- ond, several input lines have simulta- into the standards used in deciding whetherwe arefaced with the firstor second situation, butwehave found it

generally

^{difficult to determine the} mostsuitable standard.

When asignal line has high control- lability cost, we find that either the observability^cost drops

rapidly,

^orit does not. With a

rapid drop,

^{we as-}

sume a_problemin

controllability,

^and

we then search for aproper

point

^of test-point insertion to lowerthe con- trollability cost (see Figure 5). ^Ifthe

observability

^costdoesnot

drop rapid-

ly,the next step is to analyze output. If no sudden drop in observability cost canbe^seenallthe _waythroughtothe primaryoutput,^thenatest

point

is in- sertedonthe original signalline a few gates towardthe outputside,asinFig-

ure Id. Insertion ^so that the observ-

Figure 6. Test point insertion. ability costisonehalf of that for the

original signal linewasthemosteffec- tive.

Test point insertion methods. Fig-

ure6 shows one _example ofan inser-

START

^s_tion

location. The numbers appearing above each line express the control- lability^{costs. Inthis}example, ^thereis __ _Ptomultiple inp gate

_Gno

^{need to inserttest pointson input}

input^{side of}signal^{line L lines Xl}trollability cost on line^{through X4toX5.lower}Insertion of^thecon- twotestpoints,^oneoneach of the lines Xl and X2 with poor controllability,

Can the method in or three test points on lines

Xl,

X2,

igure^lcbeapplied and X3, would be sufficient. This

Insert

test

_point

would spare ^us the problem of the

asin_Figurelc standardstobe

_applied

when

_inserting

Is thereanysingle ^{_ _thetest point ontheinput line.}

input gate onP? ^{_ _} For the test point, a gate could be

added as shown in Figure la. How- ever, the addition of a gate would cause delay in a circuit designed for Inserttestpoint Insert test point high-speed operation, requiring a

asin Figurela ^asinFigurelb

_redesign

_ofthe

_circuit

_withthe new test point. It is preferable, if possible, to use oneof the methods shown inFig-

r END ^{ure 1, b andc. Whenaddinga gate to}

signal

^lineL,wefollowthe flow chart in Figure ⁷ to determine whether

Figure 7. Selection of test point types. method lb orIccan be used.

Experimental results. After pro- all detectable faults. This method pays

fault;

^{when a fault} is

_aborted,

it is gramming the _design method de-

special

attention toaborted faults ^oc- called a

t-difficult-to-test-for fault.

scribed above, we applied it to some

_curring

after the test pattern genera- ^{When no}

_particular

^number ofback- circuits of several thousand gates and tion

_algorithm

is

_applied,

and it in- tracks is

_specified,

^t_maybe omitted. surveyed how the test coverage volves the

subsequent placement

of From the

perspective

^oftestpattern changed with the insertion of test test

_points

tomakesuch faults easierto

generation,

aborted faults ^can be

points. The computer used for our test. divided into three_types:

calculationswasthe

_large

computerat Types of aborted faults. With a test Fault type 1. An aborted fault Osaka University, an NEC _System pattern generation algorithm that caused by difficulty in producing a 1000 (computation speed: 15 _{MIPS). sendsa}signal whose value varies with faulty

_signal.

We used Fortran for programming, the existence or absence of a fault Fault type 2. A fault for which and for the test pattern generation (called a "faulty signal") along a faulty signal production is easy, but algorithm, we used the FAN _algo- signal line on which a fault is inserted propagationof the

faulty signal

tothe rithm.8 Aborted faultswerethe faults (called a "faulty line"), we try prop- _next

_gate

_is

_difficult

^y

that remained undetected after more agating a faulty signal from the faulty

_Faun

_{t type 3.A}

_fault

for which ob- than_The100characteristics of thebacktrackoperations.circuits line to a primary output. When westart a backtrack cycle of a specific

_servation primary output

_{of the}

is faulty signal

difficult,

even

^at

beforedesigning fortestability ^arede- _{number(say100}

_times)

_of

backtracks,

though both the production and prop- scribed in Table 1. Test coveragewas t, the test pattern generation is agation of the faulty signal for more definedasfollows: aborted, indicating an aborted fault. than one gate were accomplished Testcomprehensiveness ^We_difficult^canassume_{to testfor.}^that_Below,^anaborted_{afault that}^faultis without

difficulty.

Number of detectedfaults ___ is^not

aborted-i.e.,

that doesnot_ap- We^candetermine into whichof these Numberof detected faults + abortedfaults pear after alimited number of back-

_categories

the fault falls

_{by running}

a

tracks,

t-is called a _t-easily tested testpatterngeneration algorithm. Our findings are shownin thegraph in

Figure8. Althoughtherearecases, as

shownby circuit 3,where the insertion Table

_1.

oftest points causes a clear drop in Characteristics of circuits before designing for testability. abortedfaults,therearealso cases,^as

with circuit 2, where the addition of Circuit Defined Aborted Test

testpointsmakes thetestingmoredif- ^{Number Gates Faults Faults}

Coverage _(%)

ficult. #1 1165 2747 45 98.31

Takingthese resultsas_evidence,it is ^#2 2348 5888 24 99.57

clearthat themeasuresoftestabilitydo #3 2592 6348 30 99.57

notalways reflect theease or

_difficulty

oftesting accurately.

Also, although

the insertion oftestpoints

clearly

^im- proved testability, itwouldbeimpos- sibletosay that in allcasesthecircuit

had been designed fortestability. \

DFT through test pattemr

generation algorithms

Asshown above, it is difficulttoob- tain complete test coverage with methodsbasedon

testability analysis.

In fact, for the number oftest

_points

added, thetestcoverage didnoteffec- tivelyimprove. Here,therefore,we ex- pand upon a method that ensures generation of test patterns for all detectable faults within the allowed computation time-in other

words,

^a method ofaddingtestpoints thatwill

result in 100 percent test coverage for Figure^8.Experimental^{results of}testability analysis^method.

Insertion oftest_points. Theoverall

START

~~~~~~~flow

is shown in _Figure 9. The test

points ^are of two _types, showvn in

Generatepatterntest ^{~Figure 1, c and d. The following dis-}

l 11|1 - for all faults _ ^{cussion covers the methods of test}

point insertion based on the type of aborted fault:

- allSlUck-Place_Cpericncesa

abortedtau

on (1)orte2 faultlist

_||LookigFault

^t

^"ype

^{I. Test point insertion}

followstheflow chart inFigure 10,in- suringthat a

_faulty

_signa can e _pro-

selectt abortedsfault listanput duced without backtracking.

_tgenerat

^clest

toprmatrnpt

_{_When} we are _tryingto _assigna cer- tain value to a certain signal line, ^the

valueand the _signal line are _together ncalled ^an "objective." Several _objec-

fault selected

tives held simultaneously ^{are called a}

"1setof

objectives."

When

signal

linel

experiences ^a stuck-at fault at either0

nsert Insert ^{or I in atype I fault,} the initial objec-

s ing,

_inttive

_Tessis(0, L) ^or (I, L).

st tLooking ^{at the} "type ^of

objective"

frame in Figure 10, ^{wecan see}that for type_(i),wecan meettheobjective byin- Select all faultstron serting ^a test

point

^of

the

^{type seen in}

aborted fault list and

Figure

Ic. For type (ii), the objective type 3 fault list and

_~~cannot

_{bemet. Fortype(iii), the}

_signal

generatetest_{pattern. line isa}

_primary

_{input,andnotestpoint} is needed. With type(ii),^weneedtosee

Figure_9.Overallflow oftestpoint insertion, whattype ofvalue^{on the}input ^would enable the _objective to be achieved. That value would be called the START

~~~~~~~~~~equivalent

objective" (Figure ^I1).

After several test _points have been inserted in accordance with the flow Etblishinitialobjectivese ^chartinFigure 10, theobjective^setwill become empty andtheinsertion ofthe test _points will be _complete. For test-

ing, these input lines will become one

Extract one objective

_~~~test

point according ^tothe circuitcon-

struction in _Figure 2.

Fauilt tYpe

^{2. Testpoint}insertion for a _type 2 fault is also carried out ac-

.YV.

~~~~~~~~~cording

^{toFigure 10. However,thein-}

of _objective

~~~~~~~itial

objective^setis determined inadif- ferent manner from that for a _{type I} fault.When,^asin

_Figure

12,^wehavea Addinputline stuck-at 0 fault on_signallineL,the in-

testingfor itial_objective set is

~(I,L

^),

^(0,M),

^(0,N)

Ptequivalent

^Fut 'Ts on neto o

obtectiveinobjectiveset

Faity~pe3.

^{Ts oitisrto o}

a _type 3 fault is carried out _only after test_pointinsertion has been_completed for fault types 1 and 2. Thetest

_point

Figure^{10. Test}pointinsertion for_{typeI and type}2 faults. usedisshownin_Figure Id,andthefol-

lowing procedures are followed to minimize the numberoftest pointsto be inserted:

First, for each

faulIt,

makea search forpossible locations that ensure that test point insertion facilitates detec- tion. Once located, ^a faulty signal should be produced and propagation

attempted, inthesame manner as for Figure 11.Equivalent objectives.

classifying

^{aborted faults.}

Next,choose the smallestnimber of test point insertion locations that will enable all faults to be detected.

If we are to eliminate all aborted faultsby the above method, any fault occurring in the newlv added test points must be easily testable. Fol- lowingthe flow chart in Figure9, we can avoid a difficult-to-detect fault in the test points in the manner shown briefly belowv:

First, for the test point insertion shown in

_Figuire

Ic, used with faulit types I and 2, consider the exarnple shownin Figure 13. Astuck-at0fault at test pointXisequivalentto astuck-

at0 faultat Yand is thus easy^{to test}

_Figure

_12. Initial objective for

type

²fault. for. A stuck-at 1 fauilt at X becomes

redundant ifthestuck-at0faultat Yis redundant, andbecomes testableifthe stuck-at 0faultat Yis testable, because it can be tested by the same test pattern with X ⁼ 0. Thus, the stuck-at I fault at X can be seen as the equivalent of the stuck-at0faultat Y. Accordingly, the number of difficult-to-test-for

faults does not increase. ^{Figure 13. Exampleoftestpointsfor faulttypesI and 2.} Second,to usethe methodshown in

Figure Id for type 3 faults, consider the example shownin Figure 14. This type of test _point insertion is carried outaftertypes I and 2 havebeen elim- inatedfrom the circuit. Accordingly, it iseasy to set signalline Yat either 0 or 1, making it easy to test signal line X.

Figure 14. Example of test points forfaulttype 3. Fxperimental results.The resultswe

obtainedfrom programming theDFT Table 2.

method incorporating a test pattern Results of design for testability withtest pattern generation algorithm. generation algorithm are shown in

Table 2. The computer, thelanguage, Circuit Computation Test

and theapplied circuits we used were ^{Number Added} Input AddedOutput Time(sec.) Coverage (o)

all the same as those we used for the #1 3 8 13.7 100.0

testability analysis method. As shown #2 1 6 11.3 100.0

inTable2,withthetestpatterngenera- #3 4 4 14.5 100.0

tion algorithm, circuits of from 1000 References ^{6. W.}Coy^{and A.}Vogel,"Inserting^Test

to3000_gates^were100percenttestable Points forSimpleTest Generation,"

with the addition of only about 10 test Proc. Fourth Intl _Conf. Fault-

1. T. W. Williams and K. P. Parker, ^Tolerant

Systems

^and Diagnostics, points. Theratiobetween the number "Design for Testability-a Survey," 1981, pp.

_180-186.

of the first aborted faults and the Proc. IEEE,Vol.71, No._1,Jan. 1983, 7. P. Goel, "An Implicit Enumeration number oftest _points was3.4to4.1. pp.98-112. Algorithm to GenerateTests for

_Com-

Compared with the resultsof thetest- _. binational Logic Circuits," IEEE ability analysis _method, insertion of 2. M- J. Wilhams and J. B. Angell, Trans. Computers, Vol.C-30,No.3, testpointswashighly effective.

_Integrated Circuits via Test

Point and ^{Mar. 1981,}pp. 215-222.

Computation time. To lessen the Additional Logic," IEEE Trans. 8. H. _Fujiwaraand T. _Shimono, "On number oftestpoints,whenevera test _Computers, Vol. _C-22, No. _1, Jan. the Acceleration of Test Generation point ofthetype shown inFigure lc ^{1973,pp. 46 60.} Algorithms," Proc. 13th_Fault Tolerant Computing, JuneInt'lConf. was inserted, test pattern generation 3. E. B. Eichelberger and T.

_W.

1983, pp. 98-105; also IEEE Trans. wasconducted for all aborted faults. Williams, "A Logic Design Structure Computers, Vol. C-32, No. 12, Dec. Because of this, each circuit took 10-15 forLSI Testing," Proc. 14th Design 1983,pp. 1137-1144.

seconds. Theprocesstookprecedence ^Automation Conf., ^June 1977, pp. 9. L. H. Goldstein, "Controllability/ over redesigning and comprised 7-30 462-468. Observability AnalysisofDigitalCir- percent of the time required for test 4 S F ^N cuits," IEEE Trans. Circuits and

patte genratin.Hweve, cosid- ^{4. S.Funasu, . Waatsui, ad T.}

^Systemzs,

^{Vol. CAS-26, No. 9, Sept.}

pattern generation. However, consid- *

_Arima,

_{"TestGeneration}

_{Systems in}

1979, pp.

_685-693.

ering that there isusuallynoguarantee Japan," Proc. 12th Design Automa- _10.

_{P. G.} Kovijanic, "Testability

Analy- that test coverage will always be 100 tionSymp., June1975, pp. 114122. sis," Digest of

_Papers,

1979 Test percent eveniftestpatterngeneration _{5. J. P. Hayes and A. D. Friedman,}

_Conf.,

pp.

_310-316.

time is extended _by this amount, ^we _"Test

_{Point Placement}

to Simplify 11. H. Fujiwaraand H. Ozaki,

"A

^New

believe the time is a small price for FaultDetection," IEEE Trans.

_Com-

Measure for Test Generation by a completetestcoverage. puters, Vol. C-23, No. 7, July 1974, Heuristic Method," IECE mono- Astotheexpenseinvolved in adding pp. 727-735. graph, EC80-38,Oct. 1980,pp. 1-8. hardware,weusedaverylow number

of test points and only those which could be realized at aminimumcost; thuswebelieve thatcostisnot agreat

problem.

A mong themethodswehave dis- cussedand mentionedhere,the methodutilizinga testpatterngenera- tion algorithm obtained the best resultsby far. We attribute thisto our useofadirect solutiontotheproblem

ofdifficult-to-test-for faults. [ AkiraMotohara is a graduate student in the HideoFujiwara has beenwith the Depart- Department of Electronic Engineering, ment of Electronic Engineering of Osaka Faculty ofEngineering, at Osaka Universi- University since 1974. In 1981 he was a ty. Hisresearch interests include test pat- visting assistant professor at theUniversity terngeneration, design for testability, logic ofWaterloo, and,in1984, avisitingassoci- simulation, and faultsimulation. ate professor at McGill University, Can- Hereceived the BE degree in electronic ada. His research interestsincludeswitch- engineering from Osaka University in1983. ing theory, design for testability, test He is amember ofthe Institute of Electron- patterngeneration, faultsimulation, built- ics and Communication Engineers of inself-test, and fault-tolerant systems.

ACknowledgments

^Japan. Fujiwara received the BE, ME, and PhD

We wish to thank Hiroshi Ozaki, pro- degrees in electronic engineering from

fessor emeritus at Osaka University, for his OsakaUniversityin 1969, 1971, and 1974

support andencouragement of thiswork. respectively. Hewasmember of the Tech-

We also thank the members of the sixth nical ProgramCommittee ofthe 1982 In-

chair of the Department of Electronic ternational Symposiumon Fault-Tolerant

Engineering, Osaka Univeristy, for their Computing. He received an Institute of

valuable discussions. Special thanks to Electronics and CommunicationEngineers

Kenjiro Sasaoka (presently with MITI) for Theauthors' address is Department of Young Engineer Award in 1977. He isa the testabilityprogramming aswellas the Electronic Engineering, Faculty of Engi- senior memberoftheIEEE, a member of results of the test pattern generationexperi- neering, Osaka University, 2-1 Yamada- the IECEof Japan, and a member of the ment. Oka, SuitaCity,Osaka 565, Japan. InformationProcessingSocietyofJapan.