J17 e IEEE TC 1978 3

IEEE TRANSACTIONS ON COMPUTERS, VOL. C-27, NO. 3, MARCH 1978

computer systemarchitecture andtheprogramming language requirementsimpose a wide range of auxiliary operations, not closely relatedtothealgorithm but necessary for its implemen- tation.Evenifit isimpossibleto eliminateTa (or equivalently toobtain Q=1),agoodknowledge of the machine structure leads to anincreaseofQ byaclever choice of the auxiliary instructions. This qualityfactor may turn very useful in the evaluation of the efficiencyofprograms implementing image processing algorithms where thecomputing time generally grows quadratically with basen (CTan2).

ACKNOWLEDGMENT

WewishtothankM.Valenziforhishelp in running the pro- grams onthe HP2116Bsystem.

REFERENCES

[1] D. E. Knuth,The Art of Computer Programming, vol. 1. New York: Addi- son-Wesley, 1973.

[2] L.Hellerman, "A measure of computational work," IEEE Trans. Comput., vol.C-21,pp.439-446, May 1972.

[3] S.Warshall, "On computational cost," Annual Review in Automatic Pro- gramming, vol 5. New York: Pergamon Press, pp. 309-330, 1969. [4] A. Rosenfeld,"Connectivity in digital picture," J. Assoc. Comput. Mach., vol.

17, pp.146-160,1973.

[5] ,DigitalPictureProcessing. New York: Academic Press, 1976. [6] "Arcsandcurvesindigitalpictures," J. Assoc.Comput. Mach.,vol. 20,

pp.81-87, 1973.

[7] A. Rosenfeldand J. L. Pfaltz, "Sequential operationindigitalpicture pro- cessing," J. Assoc.Comput. Mach.,vol. 13, pp.471-494,1966.

[8] S.Levialdi,"Onshrinking binarypatterns," Commun. Assoc.Comput. Mach., vol. 15, pp. 7-10, Jan.1972.

[9] L.Cordela, M. J. B. Duff, and S. Levialdi,"Comparingsequential and parallel processing ofpicture," in 3rd Int. Joint_Conf.PatternRecognition, Coronado, CA,pp.703-707, Nov.1976.

1101 V.Franchina, A.Pirri, and S.Levialdi,"VIP: Animage acquisition device for digital processing,"ⁱⁿProc._Conf.AssistedScanning, Padova,pp.300-321, Apr. 1976.

[11] "Aguide to HPcomputers,"Hewlett-PackardCompany, CA,1972.

ConnectionAssignmentsforProbabilistically Diagnosable Systems

HIDEO FUJIWARAANDKOZOKINOSHITA Abstract-This correspondence is concerned with probabilistic faultdiagnosisfor_digitalsystems. Agraph-theoreticmodel of a diagnosablesystem introducedby PreparataetaL_[3]isconsidered inwhich a system is made up of a number of units with the proba- bility^offailure. The necessary and sufficientconditionsareob- tained for the existence oftesting links (a connection) to form probabilistically t-diagnosablesystems with and withoutrepair. Methods for connection assignmentsaregiven for probabilistic faultdiagnosis procedureswith and withoutrepair.Maheshwari andHakimi[10]gavethenecessary and sufficient condition for a systemtobeprobabilistically t-diagnosableWithoutrepair.Inthis correspondence,weshowthe necessary andsufficientcondition for a systemtobeprobabilisticallyt-diagnosable with repair.

Manuscript received July 8, 1976; revised November 17, 1976.

The authors are with the Department ofElectronicEngineering, Osaka Uni- versity,Osaka, Japan.

Index Terms-Automatic diagnosis, connection assignments, digital systems, graphs, probabilistic fault diagnosis, self-diag- nosablesystems,testinglinks.

I. INTRODUCTION

Studies inself-diagnosablesystems haveappearedin the lit- erature [1]-[10]. Preparataetal. [3] first introduceda graph- theoretic model ofdigitalsystemsfor thepurposeof diagnosis ofmultiple faults,andpresented methodsofoptimalconnection assignmentsforinstantaneous andsequentialdiagnosis proce- dure. Maheshwari and Hakimi [10] introducedadiagnosability measure tbasedontheprobability ofoccurrenceof faults and presentednecessaryand sufficient conditions forasystem tobe probabilistically t-diagnosableinthegraph-theoretic model.

Thediagnostic model employedinthiscorrespondenceis the model introduced by Maheshwari and Hakimi[10],and it isas- sumed that the reader is familiar with the model, assumptions, definitions, and notations given there. Theconceptof probabi- listicdiagnosability (without repair)wasdefined in[10].Prob- abilisticdiagnosability with repair^canbe defined similarly.

Definition 1

[10]:

A systemS,representedbyadigraph G = (V,E), is saidtobeprobabilistically t-diagnosable without repair (p-t-diagnosable without repair) if foranyweighted digraph G5, representing S andsome setoftestoutcomes,there existsatmost oneconsistent faultsetFc V such thatP(F)> t.

Definition2: AsystemS,represented bya_{digraph G,is said} tobeprobabilistically t-diagnosable with repair (p-t-diagnosable withrepair)ifforanyweighted digraphG5, representingS and some setoftestoutcomes, there existnoconsistent faultsets

Fj,F2,

^--*,F1 such that

n _Fi=

i=l

andP(Fi)

^{> t}fori= 1,2,* ,l.

In ap-t-diagnosablesystemwithrepair,the intersection of all consistent faultsets,whoseapriori probability ofoccurrenceis greaterthant,isnot empty sothatatleast the unitsbelonging tothe intersectionareallfaulty. Hence,there existsasequence ofapplicationsoftestsandrepairsof identified faults that allows all faultsoriginallypresenttobe identified.

II. FUNDAMENTAL THEOREMSFOR_CONNECTION

ASSIGMNENTS

GivenasystemS withunits

_ub,u2,

* ,Unand the probability

p(Ui)

of

_ui

being faultyforalluiE V=

_1ui,U2,

.*..*,Unl, ^thenwe consider theproblemsoffindingaconnection of S such that S isp-t-diagnosablewith and withoutrepair.

Wecan statethefollowingfundamental lemmas.

Lemma1: IfasystemS,representedbydigraphG⁼ (V,E), isp-t-diagnosable withrepair,then thereexists no 2-partition

IU1,U21

^{of V suchthat}

W(U1)

^<

K(t)

and

_W(U2)

<

_K(t).

Proof: Supposeforsome2-partition

_IUl,U2}

of V, W(U1)

<K(t) and W(U2)<K(t). Wecaneasilyfindaweighteddigraph GC of S that has U1 and U2asconsistentfaultsets. Thus,by Definition2,S wouldnotbep-t-diagnosablewith repair.

Q.E.D. Lemma2:Let Vbea setofunits ofasystemS.Ifthereexists no2-partition

_MU1,U21

ofVsuchthatW(U1)<K(t) andW(U2)

<_K(t),thenthere existsadigraph G⁼(V,E)such thata system representedbyGisp-t-diagnosablewithout repair.

Proof:Considera completedigraph G ⁼ (VE) such that

(ui,uj)

^{E E forall}

ui,uj

^{E V. We shallprovethatasystemS} representedbyG isp-t-diagnosablewithout repair.

The proof is by contradiction. Assume the existence ofa

0018-9340/78/0300-0280$00.75 ©1978 IEEE

280

CORRESPONDENCE

weighteddigraph

_G,

forwhich therearetwoconsistent faultsets F1and F2 with W(F1), W(F2)<K(t). Let X= V- _(F1 UF2), Y=

F1 n

^{F2,Z =}

F1

-Y, and Z2=F2- Y.Without loss of gen- erality,wehave Zi

_sg*

If X = X,then

_{F2,Z11

is a2-partition ofV suchthatW(F2) < K(t) and W(Z1) ^<K(t). Byhypothesis,there exists no 2-parti- tion

_fU1,U21

ofV suchthatW(U1) <K(t)and W(U2) <K(t). Thisis acontradiction. Therefore,wehaveX s _0.

BecauseGiscomplete,there exists an arc

_(ui,uj)

E E suchthat ui ^{E X}and

_uj

E Z1.Since

_ui,uj

E F2and F2 isaconsistentfault set, wehave

_s(ui,uj)

= 0.But sinceF1 is alsoaconsistent fault setandui ^E F1, uj ^E F1,wehave

_s(ui,uj)

=1._{This is}a contra- diction.Hence,ourinitialassumptionwaswrong. Q.E.D. Givena systemS with unlts u1,u2,^...

,un

and the weight

W(ui)

foreach

_ui

E V =

Iu1,u2, .,Un.

, thenwe have thefollowing theorems.

Theorem 1:Given a system S with a set of units V and the weight

W(ui)

^forallui E V, then there existsadigraphG= (V,E) such that Srepresented by G isp-t-diagnosablewithout repair ifand onlyifthere existsno.2-partition

_IU1,U21

ofVsuch that W(U1)<K(t)andW(U2) <K(t).

Proof-Necessity:It isobviousthatevery systemthatisp- t-diagnosablewithoutrepair is alsop-t-diagnosablewithrepair. Hence, the necessityofthe theoremfollows from Lemma1.

Sufficiency:FollowsfromLemma2. Q.E.D. Itcanbe easilyverified that Theorem1isvalidforp-t-diag- nosability with repair also.

Example:Considerasystemconsisting of three units such that

p(Ul)

⁼ Y5,

p(U2)

⁼

¼, p(U3)

⁼ i,^{and t =}

Y20.

^Thenwehave W(u1) = log4, W(u2) =log3,W(U3) ⁼log2,andK(t) ⁼log8. Let U1 =

_luil

_{and U2}= _{1u2,u31, then}wehaveW(U1) =log4 > K(t) andW(U2) =log6 >K(t). Thus, from Theorems1and2, it canbeseenthatthere existsnodigraphGsuch that thesystem represented byG isp-t-diagnosablewithrepairorwithoutre- pair.

IlL CONNECTIONASSIGNMENTSFORDIAGNOSABILITY Ithas been showninthelastsectionthatfora systemSwhich isp-t-diagnosable,thesetof units Vmustsatisfy the condition ofTheorem 1,i.e., there existsno2-partition

_MUP,U21

^{of V}such thatW(U1) ^<K(t)and W(U2) <_K(t). Inthis sectionwe con- sider thedesignofp-t-diagnosable systemsprovided that the above condition holds.

GivenasystemS witha setof units Vandweight

W(ui)

for all ui E

_V,

asubset U of Vsatisfyingthefollowing condition^is calleda basesetof S.

Condition:There existsno2-partition

_IU1,

U2} of U such that W(U1)^<K(t)andW(U2)^<K(t).

Definition 3: A system S with digraph G ⁼ (V,E) issaidto belong^toadesign

Do

^ifforsome basesetUofS,1) (U) ^isa

complete digraph,

and

2) r-l(ui) c

U and

W(F-l(ui))

^>

K(t)

for all_ui e V- U.

Definition 4: A system S with digraph G ⁼ (V,E) issaid to belongto adesign^D1ifforsomebasesetU of S,

1)

_(ui,ui+1)

eEfor1 <_i< n -1, 2)

(un,ul)

E E,

and3)

(ui,us)

^{E E for 1 <i <s- 1,}

where U⁼

_(ul,u2,

^.-- _,u,}and V⁼

_Wu1,u2,

^Un.

Toillustrate thedesigns

_Do

andD1,weconsiderasystem

_S,

which consists offive units U1,U2, ^...,U5. Suppose p(u1) ⁼ ,

p(U2) =

'/6p(u3)

=

/5,p(U4)

= g,p(u5) =

1/s,andt

⁼

_%As,

then wehave

W(ul)

⁼log6, W(u2) =log5, W(U3) ⁼log4,W(u4) = log3, W(U5)⁼ log2,andK(t)=-log

_%A5

+ log

_%

+ log

_%

+ log

%

⁺log4+log%⁼log10.Let U⁼

Wub,u2,u3A.

^{Since W(U)=log}

120^> 2K(t),there existsno2-partition

_IU1,U2j

of U such that

W(U1)

<K(t)and W(U2) ^<K(t). Therefore Uis abaseset of Si.

In Fig. 1 twodesignsareillustratedfor systemS1.

Do

isshown inFig.1(a) andD1 isshowninFig.1(b).InFig.1(a), (U) is a complete digraph, r-1(u4) =

_r-'(u5)

=

_fu1,u21

⁼ U, and W(1-1(u4)) =

W(r-l(u5))

= log30 ^>K(t). Therefore,system Sirepresented byadigraph showninFig.1(a) belongstodesign Do. ^Itcaneasily be shown thatsystemSi representedbyadi- graph showninFig.l(b) belongstodesignD1.

Weshallprovethat a system isp-t-diagnosable without repair ifitemploysdesignDoand thata systemisp-t-diagnosablewith repairifitemploys design D1.

Theorem2: If a systemS employs design

Do,

then S isp-t- diagnosable without repair.

Proof: The proofisby contradiction. Assume the existence ofaweighted digraphGC for which thereare twoconsistent fault sets F1andF2 withW(F1), W(F2) <K(t).LetX= _U- _(F1 U

F2), Y=F1 n F2, z

⁼

F1

^-

Y,

^and

Z2

⁼

F2-Y,

where U is a basesetof Sindesign

Do.

Without loss ofgenerality,assumeZ

#

_0.

Thefollowingcases arepossible.

Casel:Z

_nl

U# _Oand F2 U5

_qk.

IfX = X,then Z1 n U,F2

_{n Ul}

isa2-partition of U such that

w(z _nl u)

^<

W(Z1)

^<

W(F1)

^<K(t) and

W(F2

n u)

^< W(F2) ^<K(t).

Thiscontradictsthe hypothesis that U isabasesetof S.There- fore,wehaveX -q_0.Because (U) iscomplete,there existsan arc

_(ui,uj)

E Esuch thatui E Xanduj E Zi. Since

_ui,uj

E F2 and F2 isaconsistentfaultset, wehaves

_(ui,uj)

=_0.Butsince

_F,

is alsoaconsistentfaultsetand ui^& F1,

_uj

EF1,wehave

_s(ui,uj)

= 1.Thisis acontradiction.

Case 2:Z1_{n U}= _b, i.e., Z1 ⁼ V- U._{Let uj}e Z1.If

_r-1(uj)

CF2, thenwehave

_W(r-'(uj))

^<

_W(F2)

<K(t), but thiscon- tradictsthehypothesisthat Sbelongstodesign

_Do.

Therefore, there exists_ui& F2 n

_r-'(uj).

Since

_r-'(uj)

CU,wehave

_ui

e

Ziandthusui&F1

P

F2.Since

_ui,uj

E F2andF2 isaconsistent faultset, wehave

_s(ui,uj)

⁼0.But since F1 is alsoaconsistent faultsetandui E _{F1, uj} E F1, wehave

s(ui,u1)

^{= 1.}This isa contradiction.

Case3:F2 n U ⁼

4,

i.e., F2 a V ^- U. Let

_uj

E Z1. Since

r-P(uj)

^{a U, wehave}

r-F(uj)

^{n F2= 0. If}

F-1(uj)

^{cZ1, then} we have

_W(-l(uj))

^<

W(Z1)

^<

W(F1)

<

K(t),

but this contra- dicts the hypothesis. Thereforer-l(u)n

#,

⁴

0.

Hence, there exists

ui E _r-F(uj) n F1 n F2.

Since

_ui,uj

^&

F2

and

F2

is a consistent faultset, wehaves

_(ui,uj)

=0.But since F1 is alsoa consistent faultsetandui e _{F1, uj} & F1, wehave

_s(ui,uj)

^{= 1.} This isacontradiction. Hence,ourinitial assumptionwaswrong. Q.E.D. Theorem3:Ifa systemS employs designD1,then S isp-t- diagnosablewith repair.

Proof: The proof is by contradiction. Assume the existence of aweighted digraph

GC

forwhich thereareconsistent faultsets

Fj,F2,

^{--*,F1suchthat}

n~Fi ⁼

i=1

and

W(F1)

<K(t) forall

Fi

E

_IF1,F2,

^{- -}

,F1J.

Let U⁼

_IU1,U2,

...

_,usj

_beabaseset of S indesignD1and let V⁼

$u1,u2, *n*. ^,unj.

Thefollowingcases arepossible.

Case1:us E

_Fi

for all_Fi E

_jF1,F2,

^{- -}

*,F1j.

In theweighted digraph

GC,

there existsa vertexUksuch that

s(ui-1,ui)

^{=0 for} all i ⁼s + 1,s +2, * *.,k ^- 1,

_s(Uks1,Uk)

= 1,anduk E Fk for someFk E

_1F1,F2,

* ,F1l. Then,wehave

Us+l,Us+2,

^"'

,Uk-1

^&

Fi

^{for all}

Fi

^E

^fF1,F2,

^..*

,F1I}.

IfUk E

_Fj

forsome

_Fj,

thenwehave

Uk1

F1

nP

FkandUk E F1 ^Q

Fk.

SinceUk6_,Uk E FJandFJ isaconsistent faultset, wehaveS(Uk-1,Uk)= 0.But since Fk is alsoaconsistentfaultset and

_Uk-1

E^Fk,

_Uk

E

Fk,

wehave

S(Uk-1,Uk)

⁼

1.

^{Thisis a con-}

281

IEEE TRANSACTIONS ON COMPUTERS, VOL. C-27, NO. 3, MARCH 1978

(a)

Fig.1. Designs(a)Doand (b) D1.

tradiction. Therefore,

_uk

&

_Fj

forall F1. However, this contradicts that

fl Fi =4).

i=1

Case2:us E

_Fj

for some

_Fj

E fF1,F2,*

_,Ft1.

IfF1 n u =u , then

_FJ

- Uand thusW(F1)2 W(U). Since

_W(Fj)

<K(t),we have W(U) <K(t). But t-his contradicts that U isabaseset. ThereforeF1 n U # 4.

Since

r Fi= 4),

i=l

wehaveus EFk^forsomeFkE

_IF1,F2,

^-*,F

_I.

Now,weshall show thatF1n UaFk. Assume that there existsa vertex

u,a Fj

n Fk Uu.Since Fkis aconsistentfaultsetand

ua,us

EFk,wehave

s(ua,us) =0. But since

_Fj

isalsoa consistent fault setand

uta

E

Fj,

us E

_Fj,

we have

s(ua,us)

⁼ 1. This is a contradiction. Therefore,wehave

_Fj

n u _Fk.

Let U1=

_Fj

_{n U and U2}=F1 nu.Clearly, U1

#4),

U2#4),

Ul

^{U U2=UandUl}

nU2

=4.Since Ula

_Fj

and U2cFk,we have W(U1) ^<

W(F1)

<K(t) and W(U2) ^< W(Fk) <K(t). Hence, thereexists a2-partition

_IU1,U2j

ofUsuch thatW(U1)

<K(t)andW(U2)<K(t).Thiscontradictsthat U isabaseset. Q.E.D. Theorems2and3showthatif one canfindabasesetUofa system,thenone caneasilyconstructp-t-diagnosablesystems withand without repair usingdesignsD1 and

Do,

respectively. Hence,^weshall show^amethod forfindingabasesetofagiven system.

GivenasystemS witha setofunits V⁼

IUL,u2,

* *

_{*,un I}

and weight

W(ui)

^forallui E V, then without loss ofgeneralityas- sume

_W(uj)

2 W(U2) 2^...>

_W(Un).

IfthesystemS satisfies thenecessaryand sufficient conditionofTheorem 1,wecanfind abasesetU ofSasfollows.

1) If.W(V) ^>2K(t),then let U⁼

_Iu1,u2,

*

_*,u,j

such that

s-1L W(uj) < 2K(t) and il1

ZS _W(uj) ^>2K(t).

i=l1

2) IfW(V) <2K(t), then let U⁼ V.

Example: Considerthesystem

_S,

withW(u1)⁼log6, W(u2)

=log5, W(U3)=log 4,W(U4)⁼log3,W(U5)⁼log2, andK(t)= log 10.

W(V) = E5

_W(uj)

⁼log720>2K(t) ⁼log100. i=1

W(uD)

^{+ W(u2)=log30< 2K(t) and}

W(ul)

⁺ W(U2)⁺W(U3)

=_log120 >2K(t).Hence,wehave U⁼

1u1,u2,u3j,

^{which isabase}

setof

_Sl.

IV. NECESSARYANDSUFFICIENTCONDITIONFOR DIAGNOSABILITY

Sofar wehavediscussed connection assignmentproblemfor probabilisticallydiagnosablesystems. Inthissectionwepresent thenecessaryand sufficient condition forasystemrepresented byadigraph^tobeprobabilistically diagnosable.Maheshwari and Hakimi [10] gave the necessaryand sufficient condition for a system tobep-t-diagnosablewithoutrepair.Wecan statethe necessaryandsufficient conditionforasystem tobep-t-diag- nosable with repairinthefollowing.

Theorem4: AsystemS withdigraph G⁼ (V,E)isp-t-diag- nosable with repairifand onlyiffor allU ⁼ Vwithr-F(U)⁼0, whenever there exist subsetsofU,F1,F2,^--,F- suchthatU =

_1Fi

= u,

nQ=1Fi

⁼4 and

_W(Fi)

<K(t)forallFi ^&

IF1,F2,

^..

.,Fill

thenr-1(Fa n

_Fn

)

_Fn

n_F)

P

0 for^some

_Fa,F,

e F1,F2,

* **,FI3-

Proof-Necessity: Suppose the condition of the theorem does nothold. Then, forsome Ua Vwith r-(U) =

4,

there exist subsets of U,F1,F2,* * ,F1 such thatU ^.1F1 = _{U, n 1Fi} = 4),

W(Fi)

^<K(t)^forall

Fi,

and

r-'(Fa

n

F3)

nFan,

_Fo

⁼ 0 for all

_Fa,F3

E tF1,F2,*^--,FI.

Constructaweighted digraph

_G,

asfollows. For eacharc

_(ui,uj)

E E,

- , ifui^&

_Fk,uj

E

Fk

forsome_Fk s ui,,UJ ^-

10,

otherwise.

Forany_FiE

$F1,F2,

^-* ,FA3,weshallshow thatFi^{is aconsis-} tentfaultsetforthe aboveweighted digraph

_G,.

1) Forany arc

_(ui,uj)

EEsuch thatui ^&

_{Fi, uj}

E

_Fi,

wehave s

_(ui,uj)

⁼1bythedefinition of

_G,.

2) Forany arc

_(ui,uj)

E Esuchthat

_ui,uj

^&

Fi,

we canshow that

_s(ui,uj)

⁼0 asfollows.Supposethat

_s(ui,uj)

⁼1,then from the definition of

G8,

ui EFk,

_uj

EFk forsome_Fk. This_implies ui ^E r-l(Fk n

Fi) nl

Fk n

Fi.

But,thiscontradicts thehy- pothesis.Therefore^s

_(ui,uj)

^=0.

Hence, F1,F2,^-

--,Fl

are all consistent fault sets for

_G,

Moreover,

nl=1Fi

⁼

4, W(Fi)

^<K(t)^{for all}

Fi.

Therefore,the systemis^notp-t-diagnosablewithrepair.

Sufficiency:

The

proof

is

by

contradiction. Assume the ex- istence ofaweighted digraph

_G,

forwhich thereareconsistent faultsetsF1,F2,^--,F- suchthat n

=,F1

^{=4 and}

W(Fi)

^<K(t) forall

_Fi.

Let U⁼ U

_LLFi.

IfF-'(U) ^#

4,

then there existsanarc

_(ui,uj)

& Ewithui E Uand

_uj

E U. Moreover,since

_n(=1F1

=

_4,

we have

_uj

E

_Fj

nFk forsome

_Fj,Fk.

Since

_ui,uj

E

Fk

and Fkisa consistentfaultset, wehave

_s(ui,u1)

⁼0. But since

_Fj

isalsoa consistent faultsetandui E F1, uj E

_Fj,

wehave

_s(ui,u1)

= 1. This isacontradiction. Therefore,wehave

P-1(U)

^=4.

Thus, by hypothesis,

F-1(Fa

n

FP)

n

Fa

n

FP

$ 4) forsome

Fa,Fgj,

i.e.,there existsan arc

_(ui,uj)

EEwithui E

_F.

_n

FP,

and

Uj

^{EFa n}

^FP.

^{Sinceui EFa,} u;j Fa, andFaisaconsistent fault set, wehave

_s(ui,uj)

⁼ 1.Butsince F, is alsoaconsistent fault

282

CORRESPONDENCE

set andui,uj ^E F,wehave

_s(ui,uj.)

⁼ 0.This is^acontradiction. Hence, our initialassumption^waswrong. Q.E.D.

V. CONCLUSIONS

In this correspondencewehavepresented the^necessaryand sufficient conditions for the existence of^aconnectiontoform probabilisticallyt-diagnosablesystemswithand withoutrepair, and also presented thedesignsD1 and Do forp-t-diagnosable systems withandwithout repair, respectively. However,these designs arenotoptimal,andhencetheinvestigation of optimal connection assignmentsforprobabilisticallydiagnosablesystems

withand withoutrepair isanopenresearchproblem. ACKNOWLEDGMENT

The authors wishto acknowledge the support and^encour- agement ofProf. H.OzakiofOsaka University, Osaka, Japan.

REFERENCES

[1] R. E. Forbes,D. H.Rutherford,C.B.Stieglitz,and L. H. Tung, "A self-diag- nosable computer,"in1965Fall Joint Comput. Conf.,AFIPSConf.^Proc.,vol.

27, Washington,DC:Spartan,1965,pp.1073-1086.

[2] E. Manning,"Oncomputerselfdiagnosis-Part^I: Experimental study ofa

processor-PartII: Generalizations and design principle," IEEE Trans.

Electron.Comput.,vol. EC-15,pp.873-881,882-890,Dec.1966.

[3] F. P. Preparata,G. Metze, and R. T.Chien, "On the connectionassignment problem of diagnosablesystems,"IEEE Trans. Electron._Comput.,vol. EC-16, pp.848-854,Dec.1967.

[4] C. V. Ramamoorthyand W. Mayeda, "Computer diagnosis using the blocking gate approach," IEEE Trans. Comput., vol. C-20, pp. 1294-1299, Nov. 1971.

[5] N. Seshagiri,"Completely self-diagnosable digitalsystems,"Int.J.Syst.,vol. 1,pp.235-246,Jan. 1971.

[6]S. L. HakimiandA. T. Amin, "Characterization of connection assignment of diagnosable systems,"IEEE Trans. Comput.(Corresp.), vol. C-23,^pp.86-88, Jan.1974.

[7] A. D. Friedman,"Anewmeasureofdigitalsystemdiagnosis," in Proc. Fault TolerantComputing Conf.,^pp.167-170,June1975.

[8] J. D. Russelland C. R. Kime," System fault diagnosis: Closure and diagnosa- bilitywith repair,"IEEE Trans. Comput., vol.C-24,^pp.1078-1089, Nov. 1975.

[9] J. D. RussellandC. R. Kime, "System fault diagnosis:Masking,exposure,and diagnosabilitywithoutrepair,"IEEE Trans. Comput.,vol.C-24,pp._1155-

1161,Dec.1975.

[10]S. N. Maheshwariand S.L.Hakimi, "On modelsfordiagnosablesystemsand probabilisticfaultdiagnosis,"IEEE Trans._Comput.,vol. C-25,^pp.228-236,

Mar.1976.

Semi-FastFourier TransformsoverGF(2m). DILIP V. SARWATE

Abstract-Analgorithm whichcomputesthe Fourier transform of a sequenceof lengthn overGF(2m) using approximately2nm

multiplicationsandn2+nmadditions is developed. The number of multiplicationsisthus considerably smaller than then2multi- plications requiredforadirect evaluation, though thenumberof

ManuscriptreceivedJune28, 1976;revised April27, 1977.This workwas sup-

ported inpartbythe Joint Services Electronics Program (U.S. Army,U.S.Navy,

and U.S.AirForce) underContractDAAB-07-72-C-0259.

The authoris withtheCoordinated ScienceLaboratoryandthe Department of

ElectricalEngineerig,University of IllinoisatUrbana-Champaign, Urbana, IL 61801.

additions is slightly larger. Unlike the fast Fouriertransform,this method does not depend on the factors of n and can be used when n is not highly composite or is a prime.

Index Terms-Analysis of algorithms, computationalcomplexity,

error-correcting codes, finite fields, Fouriertransforms.

I. INTRODUCTION

The discrete Fourier transform (DFT) of asequence ofnele- ments of a finite field can be computed by means ofthe fast Fourier transform (FFT) algorithm over the finitefield [1].This algorithm is just the well-known complexfield FFTalgorithm (e.g.,

_[2])

with the primitive nth root of unity exp

_(j27r/n)

in the -complexfield being replaced by a primitive nth rootof_unityin the finite field. When n is composite, with factorsnl,n2 * * ,n, the finite field FFT is essentially what iscalled a mixed-radix FFTand requiresn(ni+n2 +^* + n8) multiplications and

_n(n1

+ n2+^* +

_n,)

additions as compared to then2 multiplications andn2 additions required to evaluate the DFTinthe most ob- vious way. If n is not highly composite, (or if n is a_prime), the saving in computation is quite small (ornonexistent). In such cases, the DFT can be computed from the cyclicconvolutionof two appropriately defined sequences of lengthapproximately2n or more [3]-[5]. This convolution itself can be computed

_by

computing the forward transforms of the two

_sequences,

a

pointwise multiplication of the transforms, and an inverse transform. If the length of the sequence is chosen tobe

_highly

composite, the FFT algorithm can be used to computethe three transforms and significant savings in computation can be achieved.

The problem that arises in using the convolutionmethod is that the

_fmite

fieldmay not contain an appropriateprimitiveroot of unity, and computations may have to be done in amuch larger field [6]. In such a case, one can transform theproblemof com- puting a finite field convolution into one ofcomputing aconvo- lution of arrays of integers. If the array convolutioniscomputed by means of a two-dimensional complex fieldFFT

_algorithm,

then the DFT over gf)pm) can be computed [6] using_{0(nm log} nmM(q)) bit operations where M(q) is the numberof bit oper- ations required to multiply two q-bit numbers and q ⁵ 2_log2n +4

_log2

m +4

_log2

p. However, this method is notvery_efficient forsmallvalues ofn.

The algorithm proposed in this correspondence requires 2(n

- _1)(m - 1) multiplications and (n^- _1)(n+ m- _{1)additionsin} GF(2m) to compute a transform of length n, n a _prime, over

GF(2m).

Ifn is not a prime, the number ofmultiplications is somewhat less and the number of additions is_somewhatmore. Since multiplications require more time thanadditions, the al- gorithm is somewhat faster than the direct method,thoughboth require_0(n2)arithmetic operations. However, the

_proposed

_al- gorithm requires_0(n2log n) bit operations only,which is better by a factor of log n over the direct method. For smallvaluesof n, the proposed method is superior to the cyclic

convolution

technique and to the usual FFT algorithm based onthe factors of n. Asymptotically, of course, the cyclic-convolution_technique requires _0(n

_log4

n) bit operations only, and is vastly_superior. For these reasons, the proposed algorithm is dubbed a

_semi-fast

Fourier transform (SFFT) algorithm.

II. THE SFFT ALGORITHM

Let n be an odd integer, m the multiplicativeorderof 2mod n, a a primitive nth root of unity in GF(2m), and: an

element

of degree m in GF(2m). It is convenient, but notnecessary, totake fi to be a primitive element. Let A(x) =_Ao +

_Alx

+A2x2* * +^-

0018-9340/78/0300-0283$00.75 ©1978IEEE

283