J26a e IEEE TC 1981 11

A ^{Design of} Programmable Logic _{Arrays with}

Universal _Tests

HIDEO FUJIWARA, MEMBER, IEEE, ANDKOZO KINOSHITA, MEMBER, IEEE

Abstract-In thispaperthe problem of fault detectionineasily testableprogrammable logicarrays(PLA's) is discussed.Theeasily testablePLA'swill bedesigned by adding^extralogic. These augmented PLA'shave thefollowing features: 1) foraPLA with ninputsand m columns(product terms), thereexists a "universal"testset such that the test patternsandresponses do notdependonthefunction of the PLA, but depend onlyon thesizeof the PLA(the valuesn andmi);2) the numberoftests isoforder n + m. For theaugmented PLA's, universaltest sets to detectfaultsinPLA'sarepresented.The types offaults considered here are single and multiple stuck faults and crosspoint faults in PLA's. Fault locationandrepair of PLA'sarealso considered.

IndexTerms-Easily testable design,faultdetection,faultlocation, logic circuits, programmable logic arrays (PLA's), universal test sets.

I. INTRODUCTION

W5jrITH the increasingcircuit densityin a single large- scale integrated (LSI) circuit chip, the difficultyof testingthecircuits is becoming apparent.Inorderto overcome thisproblem, methods have beensuggestedin whichtestpoints andadditional logicareused for the purpose of easing thetest generation problem [1]-[6]. Designingeasilytestablecircuits, one shouldpay attentiontothefollowing features: 1)thecost ofgeneratingtestpatterns islow,thatis,thecomputationtime fortestgeneration isshort;and2)thecostoftestingthe circuits islow, thatis, thelengthoftestsequence is short.

This paper is concerned with theproblemoffault detection and location in theeasilytestableprogrammable logicarrays (PLA's)whichhave the abovementioned features. The PLA, whichis conceptuallyatwo-level AND-OR,isattractive in LSI duetoitsmemory-like arraystructure. Amethod ispresented toaugment PLA'sbyaddingextralogicsothat theaugmented PLA's havethefollowing easily testable features: 1) for a PLA withninputs and m columns (product terms), there exists a

"universal"test setsuch thatthe test patterns and responses donotdependonthe function of the PLA, but depend only on the size of thePLA(the values n and m); 2) the number of tests isof order n + m. Since the augmented PLA's have the uni- versaltestset, the test generationof PLA's is no more neces- sary, and thecostoftestgeneration is considerably reduced toalmostzero.Theaugmented PLA's introduced in this paper aresimilartothePLAwhich wasindependently obtained by

Manuscriptreceived December 10, 1980; revised May 26,1981. H. Fujiwara iswith the Department of Electronic Engineering,^Osaka University,Osaka, Japan.

K.Kinoshitais with theDepartmentofInformationand Behavioral Sci- ences,HiroshimaUniversity, Hiroshima,Japan.

Hong and Ostapko [3]. However, since the augmented PLA's considered inthis paper need less additional hardware than [3] and also sincenotestsequence for multiple faults appears in [3], we will present universal test sequence for single and multiple faults in the PLA's. First, single-stuck faults and single crosspoint faults are considered, and the universal test setsto detectthese faultsinPLA's are presented.Then the type of faults are extended to multiple faults. Fault location and repair of PLA's are also considered where the faults are as- sumedtobemultiple crosspoint faults.

II. PROGRAMMABLE LOGIC ARRAYS

Aprogrammable logic array (PLA) consists of three main parts. These are the decoders, the AND, and the OR arrays. The decoders are usually implemented by single-bit decoders or double-bit decoders, as shown in Figs. 1and 2. Both the AND array and the OR array are used to implement multioutput combinational logic with sum-of-products forms. Fig. 3 shows an example ofa 4-input, 2-output PLA withsingle-bit de- coders, which realizes two functionsinthefollowing:

fl = X1 V X4 V X2X3 V X1X2X3

f2⁼ X2 V X4 V XIX3 V X1X2X3.

Fig.4shows another realization using a PLA with double-bit decoders.

Inthefollowing Sections III and IV, we present a method toaugmentPLA's withsingle-bit decodersordouble-bit de- coders byaddingextralogicsothat theaugmented PLA'sare easily testable PLA'swith short "universal" testsequences. The types offaults considered in SectionsIIIandIVaresingle faultsinthePLAwhicharethe stuckfaults and the crosspoint faults. Acrosspoint fault in a PLA is a fault such that the presence (absence) ofacontact between a row and column of thePLAbecomes the absence(presence) of thecontact.

III. AUGMENTED PLA's WITHSINGLE-BIT DECODERS Inorder todesignan easily testablePLA with single-bit decoders, we augmentagiven PLA by adding extra logic, that is,ashiftregister, two cascades of EOR'S (EXCLUSIVE-OR'S), andonecolumnandone rowtoANDandORarrays, respec- tively,asshown in Fig.5.Theconnections of the added column intheANDarray isarrangedsothat eachrowof theANDarray hasanodd number of connections. Similarly, the connections of the addedrowintheORarray isarrangedsothateachcol- umn has an odd number ofconnections. In the augmented 0018-9340/81/1100-0823$00.75 © 1981 IEEE

xl

x2e

n <

AND array

I I I I

_{1 1 1 1}

_fl ^Single

OR array f2

fg

Fig. ^{1. PLA with}single-bitdecoders.

x x

x3

xi x4_ e-bit decoder

M_{-c - - N}

II ^{I; ;I} _f2

Fig. 4. Example of PLA with double-bit decoders.

1

_ID2

xi ^Vxi+

wi xi+l

Xi v _xi+l

Xi ^v xi+l Double-bit decoder

x1

x2

x3

f1

f2

fi,

Fig. 2. PLA withdouble-bitdecoders.

r- ⁰ denotes AND

X denotes OR

e- - _{--- -} -- .

r - ___ _^_~ i2 _fl

f,

_4d

^{_ __-__}

^j

^{- 2}

Fig.3. ExampleofPLAwithsingle-bit decoders.

PLAeach column(product term)_biis ANDed by each variable

Si

of the shift

_register

asfollows:

bi =pi, Si ^{fori= 1,2,*,m}

where pi is^aproduct term generated by the ith column of the ANDarraywithout the shift register and m is the number of columns.Fig.5shows a PLA augmented from the PLA shown inFig. 3.

Theaugmented PLA has the following properties. 1) The shift register can be used to select an arbitrary col- umnof theANDarrayby setting 1 totheselected column and 0 toall other columns. [See Fig. 6(a).]

2) Theaugmenteddecoders with control inputs_y1and Y2 canbeusedtosensitize^anarbitraryrowof theANDarray by setting0or 1 totheselectedrowand1 toallotherrows. [See Fig. 6(b).]

column

$~~~~~~~~~~~~~~~

2 Exra row Y1 2

Yl Y2

: EOR x

Fig.5. Augmented PLA with single-bitdecoders.

3) The cascadeof EOR'sbelowtheORarraycanbeused

as a_{paritycheckertodetectsingle}errorsinthesensitizedrow

of theAND array. [See Fig. 6(c).]

4) ThecascadeofEOR'S^onthe left of the^ORarray canbe usedas a_paritycheckertodetectsingleerrorsinthesensitized column of theORarray. [See Fig. 6(d).]

Utilizingthe abovepropertiesof theaugmentedPLAwecan

present ^auniversal test set todetect single faults in the fol- lowing:

1) stuckfaultsontheinputoroutputlinesofgateswithin thedecoders, theANDarray,and theORarray,

2) crosspointfaults in theANDandORarrays.

TableIshows thetest set_An,mtodetectthe abovetypesof faults, whereⁿ is thenumber ofinputs, ^m is thenumber of columnsintheANDarray, and

X2--

X34{

- _-i

r- ^{- .. - -} -1

1- I

JT

_

x4

-I _{UCI C VA}

I

01

0 0 1

F ~~~~~~~~~~1t

Selected 0/1

0/1

column 1

1

AND array 1

0 0 _Pi 0 0

Sensitized D rw

AND array

Fig. 6. Features of the augmented PLA. TABLE I

UNIVERSALTEST SET_An,m

X1 ... _{* - -} nY1 Y2 ^S1 2^{m 12} 1^{0 ....0 ...0.. o o o}

For j=1,2,...,m

|I^{2j |°.... ... 0 1 0 0 ...O1 0....O 1 1}

I_I2j ^{. .} ...101 0...0 1 0....0 1 1

For i=1,2,...,n

I3i0 1 ^.10.1 ... 1 0 1 1... 1 ... 1 _em

| Ii|°... .°10...^{0 1 ...}.O1.1 ^......1|e-l

I 0 ...0 10 ...010 1. .1

3i In

(Em _=I ^{ifm is odd}

ifm iseven

and"^-" represents DON'T CARE.

For this^testsetAn,m^wehave thefollowingtheorem. Theorem 1: LetMn,mbe^anaugmentedPLAwith single-bit decoders which hasⁿinputs^andmcolumnsintheANDarray.

ForanyMn,mthetestsetAn,mcandetect allsingle stuckand crosspoint faults in the_decoders,andANDarrayand theOR array.

Proof: When^we apply test inputs

Io

and ^, the jth column isset to^Iandother columns^areallset to0._Therefore,

bothI° andI candetectanycrosspointfault^onthejthcol-

umn of the OR array by observing the output Z2, and a

stuck-at-O fault on the_jthcolumn, stuck-at-I faultsonthe other columns, and stuck-at-O faultsontherowsoftheAND arrayby observingtheoutput

ZI.

Anystuck faultontherow oftheORarraycanbedetected bysome

Io

and I2; (1 ^<j ^< m).Byapplying test_{I°i (I3i),}the (2i - I)th (2ith) row of the ANDarrayisset to0and otherrows are_allset to1._Therefore, test_I3i(13)candetect all crosspoint faults and a_stuck-at-1 faultonthe2i- 1th (2ith)rowin theAND arraybyobserving theoutputZ1.

Tests I°%,I;

_(j

= 1,2,"*, m)and

_Io,

I3i (i=

_1,

2,**, n) can alsodetect all stuck faults in the decoders. The stuck-at-O faults ontheinputlines ofORgates canbe detected by

1o

and

IP

j

= 1, 2, ,m).The stuck-at-I faultsontheinput lines ofOR gates can be detected by I3i and

_Ili

(i = 1, 2,, n). The stuck-at-O faultsontheinput lines xi (i = 1,2, *, n),Yl,and Y2^{canbedetected}

_by

^{I° and}I2

_(j

⁼ 1,2,-,

_m).

^{The stuck-} at-I faultsontheinput lines xi (i= 1,2, * ,n),y1,andY2^can be detected by

Io

and_I3i(i = 1, 2, **, n). Q.E.D. Next,wewill show that thetest setAn,mcanalso detect any multiple stuck fault in the EXCLUSIVE-OR cascadesunderthe fault assumption that permits only stuck-type faults onthe externalinput andoutputlines ofEORgates, thatis,nofault withinEORgatesis considered.

We have the following lemma. Similar results appearin [12].

Lemma1: For anEXCLUSIVE-OR cascade realizationof ak-input linear function, all multiplestuckfaultson the ex- ternallines ofEOR gates can bedetected bythefollowingk +

1 tests:

to =(°,0,^* )

t= (1, 0,.., 0) t2=(0,1 ol ^...IO)

*1\

tk =(O,O, ,l^O,1.

Proof:-

Any

linear function of k orfewer variables^can be_expressed in the form

IA(XI,x2,**,_Xk) ⁼aO _CD3aix, (1Da2X2 CD3^..**( akXk whereai ⁼Oor I _fori ⁼ 1,2, *k andA ⁼

(ao,al,,a2,

ak).-

Itcan _easilybeshown that^evenifone or more_stuck-at-0 orstuck-at-I faults areintroduced into the EXCLUSIVE-OR

cascade,the_resultingcircuitstill realizes^a linear function.

_Sol

any faulty function of the EXCLUSIVE-OR cascade can be expressedⁱⁿthe above form. WhenA ⁼_{(O, 1, *,1),}thelinear functionIA represents the fault-free linear functionlk.

LetIB ⁼bo^EDbXxi(1^{ED-- a}

bkXk'

^bealinear function real- ized_byacircuit undertestwherebi ⁼ OorI _fori ⁼ _1,2,-*_*, k.Applyingthevectorsto,t1, ", tk tothe equation

lA_(X1,X2,' .,_Xk) ⁼ lB(X1,X2, , _Xk)

weobtain

ao= bo

aO^@_a, ⁼ boCD _bi

ao^@ ak = boCD bk

which implies

ai =bi fori =0, 1, 2,*,k.

Therefore,we canuniquely determine the valuesai's,and thus distinguishwhetherIB equalstothe fault-free linearfunction

ornot. Q.E.D.

In Lemma ¹ k+ 1_{teststo, t1,} tkcan easily be extended

tok linearly independent vectorsplus zerovector.Then we

havethefollowing lemma.

Lemma 2: If kinputvectorsare_linearlyindependent,then these k vectors pluszero vector aresufficient todetect any

multiple stuck fault^onthe external lines ofEOR gatesin a

k-inputEXCLUSIVE-ORcascade.

Let_Mn,mbe^anaugmentedPLA,andletC1 and C2be the cascadesof EOR'shavingtheoutputZ1andZ2, respectively, inthe augmentedPLAshown in Fig. 5.Let MOR⁼

_[a11j]

be

a _{matrix ofI} rows_andm columns where

aij⁼

O

ifthere existsa_linkatthe(i,j)thposition of theORarray,and

otherwise.

ByLemmas ¹and 2^wehave thefollowingtheorem for the multiplefaults in^twocascades ofEOR'S, C1 andC2.

Theorem2: Thetests_I1,

_{Io (j}

⁼ 1, 2,* ,m)in An,m are

sufficienttodetect allmultiplestuck faults inC1. If thecolumn rank ofmatrixMORis equaltothe number ofinputs of the

EXCLUSIVE-OR cascade C2, then all the multiple stuck faults inC2canbedetected bytests_II,and

Io

_(j ⁼ 1,2,**, m) inAn,m.

Note that if the column rank of matrixMORisnotequalto the number ofinputsofthe cascadeC2 althoughithardly^oc-

curs,then it isnotguaranteedthat allmultiplestuck faults in the cascadeC2^canbe detectedbythetestsmentioned above. To^overcomethisproblem,itmightbenecessarytoaddextra ORarraysothat the rank of MOR isequaltothe number of inputsof theEXCLUSIVE-OR cascade C2.Note also that^we permit only stuck-typefaults^ontheexternalinputandoutput lines ofEOR_{gates. However,by adding}extraarray_{it is}pos-

sibletogeneratealltest patternsfor thecascade C1 andC2. Thistechniquewasreportedby HongandOstapko [3].

Usingthetest set_An,m,wecanconstructatestsequencefor theaugmentedPLA's^asfollows:

an,m ⁼III21 I22^.*.*I21mI22"1*^. _I2m

U1U2 Um-I _I31I32 I3nI31 I12 31n where thetestpattern _Ui (i⁼ 1, 2,^-* ^,m ^- 1) isdefinedas

XI1 **XnYiY2SIS2^..*SiSi+_I...SmZiZ2

Thetestsequencean,mcanalso detect the shiftfunction of

the shift register,aswellasallsingle stuck and crosspoint faults inthe PLA. The length of the test sequence is 2n + 3m.

Now wehavepresentedthe test setand thetestsequencefor theaugmented PLA's.Both the test setAn,mand the test se- quencean,mhave thefollowing advantagesofeasytestability. Thetest set An,m does not depend on the connection pattern of thePLA,butdependsonlyonthe valuesnand m,thatis, the test patterns and responsesareuniquely determined only bythe sizeofthePLA.Therefore, thetest set An,m is "uni- versal." We can also see that the testsequence _an,rm is uni- versal. Hence, the test generationof the augmented PLA's is notmore necessary. Moreover, the universal test sequence is averyshorttestsequence whoselength is2n +3m.Inthis way we can seethat theaugmented PLA's are very easily testable PLA's having a universal test sequence.

IV. AUGMENTED PLA'sWITH DOUBLE-BIT DECODERS The PLA's with double-bit decoderscan besimilarly aug- mented by adding extra logic, that is, a shift register, two cascades of EOR's, andonecolumn andone row tothe AND andORarrays,respectively, asshownin Fig.7. Fig.7shows a PLAaugmented from thePLAshown in Fig.4.The aug- mented double-bit decoders have four control inputs_Y1,Y2, Y3, and_y4,as shown inFig.7.

For theaugmentedPLAwithdouble-bitdecoders,we can similarlyconstruct auniversaltestsetBn,m,asshown in Table II, and thefollowing theorem holds.

Theorem 3: Let_Nn,mbe anaugmentedPLAwithdouble- bitdecoders which has ninputs and m columns in theAND array.ForanyNn,m, thetest set_Bn,mcandetect allsinglestuck and crosspoint faults in thedecoders,theANDarray, and the ORarray.

Theorem4: Bn,r candetect all multiplestuckfaults in the cascade C1. If the column rank of MOR isequaltothenumber ofrowsintheORarray, then allmultiplestuckfaults in the cascade C2canalsobedetected by

_Bn,rn.

Usingthetest setBn,m,^wecan constructthe universaltest sequence1n,mfor theaugmented PLA'sasfollows:

On, =III21 I22^...I'2m I21 I22*2r 121222*2m 21 '22 '2m U1U2 Um-1 I31 I32^..._I32

3132 I32I3 I32 I3r3 I32 I32

where thetestpattern _{Ui (i} ⁼ 1, 2, , m - ₁₎ isdefined as

X1^..

*XnY1Y2.Y3Y4

^S1..

*Si

^{Si+I ..}

*Sm

^ZIZ2

Ui^{=-*---1 1 1 1 1... I0...0} -

Thelengthof the^testsequenceis 2n+ 5m.

Notethatwealsostatemore_generalresults for PLA with k-bit decoders. The universal ^test sequence might ^{be con-} structedasfollows:

121 * 2mI21 * * 2 _...I2I2m

Ul U2... Um- ^{J 1 ...}In/kI31 _I3nk...I31 wr 3nok

where, n2'nd I3'nre. the.teszt patterns fork-bhit deconders extended from 2-bit decoders. The totaltest_length is_(2k+

1)m⁺ (n/k)2k.

I1 111' l l ^{X1 V} X2V1

_ L.--~ ~ ~ ~ X X2 _ =xl vx2 v y3

. Augmented double-bit decoder

2~~~~~~~~1

Extra row

Fig. 7. _AugmentedPLA withdouble-bit decoders.

TABLE II UNIVERSAL TEST SET Bn,m

1^x2 ' X2i-1x2i ... xn-Ixn ylY2Y3Y4 S1 ^S Sm Z1 Z2

--.01 ... O.. o 0

For j=1,2,...,m

I2j ^....O 000... 0 0 1 0 00 0.... 1....O 1 1

I301.1 ... 1 0 00...O 1 1

I2j 1O....1.. 1000100....1... 1 1

For i=1,2,..*'

IO0 . .₃₁ 1 1 ^.... 0 0...1 1 0 1 1 1 1 ^......1^......1 Em_m

I31i .^{1 0 .... 0 1...} O11^{0 1 0 1 1 1 ....}..1^......1 ^Em

I2 0 0 ^.. O1 111...1 c0

31 m

I31 m ..1 1... 0 1110 1..

3i

V. MULTIPLE FAULT DETECTION

So far^wehave discussed thesinglefault detectionproblem fortheaugmentedPLA's.Inthissectionweextend the_single fault modeltothetypes ofmultiplefaults in the_following,and presentthe universaltest setfor them. Note thatno morethan

one_{of the}following multiple^faultsoccurssimultaneously. 1) Multiplestuck faults^ontheprimaryoutputsxi(i ⁼ 1, 2,^{* *-,}n).

2) Multiplestuck faultsonthe controlinputsyi (i ⁼ 1, 2, 3,4).

3) Multiple stuckfaults^on therowsintheANDarray.

4) Multiplestuck faultsonthe columnsin theANDandOR arrays.

5) Multiplestuck faultsontherowsintheORarray.

6) Multiplestuckfaultsontheinputandoutputlines of the EORcascade C1.

7) Multiple stuck faultsontheinputandoutput linesofthe EOR cascade C2 provided that the column rank ofMOR is equaltothe number ofrowsinOR array.

8) Odd number of crosspoint faultsonthe columns of the ORarray.

9) Odd number of crosspoint faultsontherowsof theAND array.

Fortheclass of the above mentioned multiple faults,we can showthat thetestsetsAn,m and Bn,marealsouniversaltestsets for the augmented PLA's with single-bit decoders and dou- ble-bit decoders, respectively.

Now,the cascade of EOR'S in thePLA isusedas aparity checkertodetect odd number oferrors on therows andcol- umnsof theANDandORarrays,respectively. Inthe same way this approachcanbe extended toother-multiple fault model by applyingerrordetecting codes suchas linear codes _[101, where the augmented PLA's will be designed to have more thantwocascades of EOR'S.

VI. FAULT LOCATION AND REPAIR

Inthis sectionweconsider the fault detection and repair of theaugmented PLA's. FortheaugmentedPLA'sthere exists auniversal test sequenceoffault location.Thetypes of faults considered herearethe multiple crosspoint faults in theAND and/orOR arrays.

Fault location test can be performed by identifying the configuration of the AND and OR arrays, that is, whether there existsalinkbetween eachrowiandcolumnjof the arrays. By applying the test pattern shown in Fig. 8, we can identify whether there exists a link or contact between row i and col- umn_jandtheANDarray. Ifthe value of output Z1 is 0 (1), thenthereexists a link(correspondingly,nolink)atthe_(ij)th position of theANDarray.

Forthe OR_array,thetest pattern shown in Fig. 9 can detect thepresenceorabsence ofalinkbetween row i and column_j ofthe ORarray. If the value of output_fi is 1(0), then there exists a link(no link) at the_(ij)thposition of theOR array. Notethat the lastrowoftheORarraydoesnothave a direct output, however it is observable from the additional output Z2.Usingthese testpatterns,we cancompletely determinethe configurationoftheANDand ORarrays.Therefore, all the multiple crosspoint faultscan befoundby observing there- sponses. The number oftestsfor theANDarray is 2nm, and thenumber oftestsfor the ORarray ism. Hence, the total length of the fault location testsequence for theaugmented PLA's is 2nm + m.

Nowafter the fault locationtestthefaultyPLA canbere- paired as follows. For a field programmable logic array (FPLA),it is knownthatanarbitrary product termcanbeboth logicallyandphysically deleted anda newproduct term can begenerated byusingspare columns of thePLA, and thusthe faultyPLA canberepaired usingsparerows_and/orcolumns [11]. If the PLA is a mask programmable logic array (MPLA),it isdifficulttorepairthePLAfor itself. Inthiscase we canrepairthefaultyPLAbyusingthewell-known memory

x1

x2

x3 x4

o... o1o ... o

EL _z

1

I 1 0 1 1

0

o... o1o...o

-1-

Fig. 8. Fault location test for AND array.

J o ... o1o ...0

I

Fi Fig.9.

1

I

-1 i ^I

Fault locationtestforORarray.

0

patch technique. This is^{amethodtorecoverthefunctionof} the faulty MPLA by switching it^{toaspareFPLAwhensome}

errors occur.

VII. CONCLUSION

Inthis^{paper we}have introduced^adesign of easily testable PLA's by addingextralogic and presented universaltestse- quencesforthem. These augmented PLA's have the^veryshort universal test sequences such that the ^testpatterns and ^re-

sponses areuniquely determined only by the size of the PLA's independently of the function of them. The length of the uni- versaltestsequencestodetect single and multiple faults is of ordern+^m,andthelength of the universaltestsequencesto

locate multiple faults is of order^nm,whereⁿis the number of inputs andmis the number of columns of the^ANDarray.

Theaugmented PLA in this ^paper,however, has ^aweak point such that there exist ^some stuck faults inside of^EX-

CLUSIVE-OR gates which cannot be detected by the uni- versaltests.This problem^canberesolved by addingextraOR arraysuchasHong and Ostapko [3]togeneratethetestpat- ternsfor such faults.

Although^wehavenotconsidered PLA's with flip-flops in this^{paper,we can}augment themtohave theuniversaltest sets. Thiscanbedone by applying^ascan-inandscan-outtechnique such^asLSSD [51, [6].

ACKNOWLEDGMENT

Theauthorswouldlike to thankProf. H.Ozaki of Osaka University forhisencouragement andsupport. The authors wouldalso like to thank Dr. T. Sasao^ofOsakaUniversity and Y.Fukui of SharpCorporationfor their useful discussions.

REFERENCES

[1] R.G.BennettsandR.V. Scott, "Recentdevelopmentsinthetheoryand practice oftestablelogicdesign," Computer, pp. 47-63, June 1976. [2] S. M.Reddy,"Easilytestable realizationsfor logicfunctions,"IEEE

Trans.Comput., vol.C-21,pp. 1183-1188, Nov. 1974.

[3] S. J.HongandD. L.Ostapko,"FITPLA:Aprogrammablelogic array for function independenttesting," in Dig. 10thInt. Symp. Fault-Tol- erantComput., Kyoto,Japan, June 1980, pp. 131-136.

[4] H.Fujiwara, K.Kinoshita,and H.Ozaki,"Universal test setsforpro- grammable logic arrays," in Dig. 10th Int. Symp. Fault-Tolerant Comput.,Kyoto, Japan, June 1980, pp. 137-142.

[5] M. J.Williamsand J. B. Angell,"Enhancingtestabilityoflarge-scale integratedcircuits via test points andadditionallogic," IEEE Trans. Comput.,vol. C-22, pp. 46-60, Jan. 1973.

[6] E.B.EichelbergerandT.W.Williams,"Alogicdesign structurefor LSItestability," in Proc.14th Des. Automat. Conf.,June 1977, pp. 462-468.

[7] H.Fleisher andL.I.Maissel, "An introduction to array logic," IBM J. Res. Develop., vol. 19, pp. 98-109, Mar. 1975.

[8] D.L.Ostapkoand S.J.Hong,"Faultanalysisandtest generationfor programmable logic arrays(PLA's)," inDig.8thInt.Symp. Fault- Tolerant Comput., Toulouse, France, June 1978, pp. 83-89. [9] V. K. Agarwal, "Multiple fault detection inprogrammablelogic arrays,"

inDig. 9thInt. Symp.Fault-Tolerant Comput.,Madison,WI, June 1979, pp. 227-234.

[10] W. W. Peterson and E. J.Weldon,Jr., Error-CorrectingCodes. Cam- bridge,MA: MITPress,1972.

[11] Signetics FieldProgrammable Logic Arrays, Signetics, CA, Oct. 1977.

[12] K. K. SalujaandS. M.Reddy, "Faultdetectingtest setsfor Reed- Muller canonic networks," IEEE Trans. Comput., vol. C-24, pp. 995-998,Oct.1975.

Hideo Fujiwara (S'70-M'74) was born in_Nara,

Japan,^onFebruary9, 1946.Hereceivedthe B.E., M.E.,and Ph.D. degreesin electronic engineering from Osaka University, Osaka, Japan, in 1969,

1971,and 1974,respectively.

Since 1974 he has been with the^Departmentof Electronic Engineering, Osaka University. His^re- search interests^areswitching theory and logic de- sign, and he specializes in the development oftest- ing, testable logic design, and^systemdiagnosis.

Dr. Fujiwara is ^a member of the Institute of Electronics and Communication Engineers ofJapanandtheInformation Processing Society ofJapan.

KozoKinoshita (S'58-M'64) ^{wasborn in} Osaka,

Japan, on June 21, 1936. ^He received ^the B.E.,

M.E.,and Ph.D.degreesincommunication engi- neering fromOsaka University, Osaka,Japan in 1959, 1961, and 1964, respectively.

From1964to1966 hewas anAssistant Profes-

sorandfrom 1967to 1977 he^{was an}Associate Professor of ElectronicEngineeringatOsakaUni- versity. Since1978 he has beenaProfessorin the Department ofInformation and Behavioral Sci-

ences,Hiroshima University.Hisfieldsof interest

arelogic design, fault diagnosis, and fault-tolerant design of digital^sys- tems.

Dr.Kinoshita is^amemberofthe Institute of Electrical Engineers ofJapan, theInstitute of Electronics andCommunicationEngineers ofJapan,and the Information Processing Society ofJapan.

I

1

±0 1 1

1

1

i

J

j