J18 e IEEE TC 1978 4

(1)

(a) ^(b) Fig.4. Resultsofsmoothing Fig.I(a), (b)using the maximal neighborhood of each

pointas anaveraging neighborhood.

(a)

5, IA.

Ir

(b)

Fig. 5. Edges detectedon Fig. 1(a), (b) SPANneighborhoods (a) ^(b),and usin

As theexamnples show,there arereal-world classesofpictures that can be treated as piecewise constant for purposes of SPAN construction. On the other hand, for a picture that contains a significantgraylevelramp,theSPANmethod breaks down,since it will attempt to approximate therampbyastaircase.

It should be possible, in principle, to generalize the SPAN approach toa wider class ofpictures, e.g., pictures thatare ap- proximately piecewise linear, rather than piecewise constant, in graylevel. Here, for each neighborhood N,(x, y),wewouldtest the hypothesis that itsgray levelpopulation isagood fit to aramp, say in the leastsquares sense.The largest rfor which this fit is sufficiently good would define the neighborhood N(x, y), and^we couldthen find the maximal N(x, y)'sasabove.On regiongrow- ing in piecewise linear pictures,see[7].

In conclusion, the SPAN approach isausefulgeneralization of Blum's MAT concept to noisy, unsegmented pictures. Like the MAT, it provides natural, concise approximations to such pic- turesthatcanbe used forpurposesof encoding, recognition, and description, while avoiding the commitment of segmentation. Since it is a parallel method, it could be implemented quite efficientlyon aparallel array^processor.

(C) (d)

using ^pairs^ofadjacent, nonoverlapping

gtheRobertscrossoperator

_(cd

_(d)

[5] -,"Techniques for optimal compaction ofpictures andmaps," Comput. Graphics and Image Processing, vol. 3,pp.215-224,1974.

[6] S.L.Horowitzand T.Pavfidis,"Picturesegmentationbyadirectedsplit-and-

mergeprocedure," inProc. 2nd Int. JointConfonPatternRecognition, Aug 1974,pp.424-433.

[7] T.Pavlidis, "Optimal piecewise polynomialL2approximationof functionsof

oneandtwovariables,"IEEE Trans.Comput.,vol.C-24,pp.98-102,1975. [8] LS.Davis,A.Rosenfeld, and^J. S.Weszka,"Regionextractionby averaging

andthresholding."IEEE Trans.Syst., Man, Cybern.,vol.SMC-5,pp.383-388, 1975.

[9] A. F.Blumenthal, L S. Davis, and A. Rosenfeld, "Detecting natural 'plateaus' in one-dimensional patterns," IEEE Trans. Comput., vol. C-26,pp.178-179, 1977. [10] L. S. Davis, A. Rosenfeld, and N. Ahuja, "Piecewise approximation of pictures using maximal neighborhoods," Comput. Sci. Cen., Univ. Maryland, College Park, Rep. TR-455, May 1976.

[11] N. Ahuja, L. S. Davis, D. L. Milgram, and A. Rosenfeld, "Piecewise approximation of pictures: Further experiments," Comput. Sci. Cen., Univ. Maryland, College Park, Rep. TR-462, July 1976.

[12] P. G. Roething. "Image enhancement by noise suppression," J. Opt. Soc. Amer., vol. 60,pp.867-869, 1970.

[13] S. W. Zucker, "Region growing: Childhood and adolescence," Comput. Graphics andImage Processing, vol. 5,pp.382-399, 1976.

[14] M. H. Hueckel, "Anoperatorwhich locates edges in digital pictures," J. Ass. Comput.Mach., vol. 18,pp.113-125, 1971.

[15]^-, "A local visual operator which recognizes edges and lines," J. Ass. Comput. Mach., vol. 20,pp.634-647, 1973.

[16] L. S. Davis and A. Rosenfeld, "Detection ofstepedges in noisy one-dimensional data," IEEE Trans. Comput., vol. C-24,^pp. 1006-1010,1975.

ACKNOWLEDGMENT

The help of S. Rowe in preparing this paper ^is gratefully

acknowledged.

REFERENCES

[I] ^H. Blum,^"Atransformation ^forextracting^newdescriptors^ofshape,"^{in W.} Wathen-Dunn, Ed., Models for the Perception of Speechand Visual Form.

Cambridge, MA: M.I.T. Press, 1976,pp.362-380.

[2] G. Levi andU.Montanari,"Agray-weighted skeleton," Inform. Contr.,vol.17,

pp.62-91, 1970.

[3] D. Rutovitz, "Datastructuresfor operationsondigital images,"in G.C.Cheng

etal.,Eds., PictorialPattern Recognition. Washington, DC: Thompson, 1968,

pp.105-133.

[4]T.Pavldis, "Segmentationofpicturesandmapsthrough functional approximation," Comput. Graphics andImageProcessing,vol. 1,pp.360-372, 1972.

Some Existence Theorems for Probabilistically

Diagnosable Systems

HIDEO FUJIWARA AND KOZO KINOSHITA

Abstract-This correspondence is concerned with probabilistic fault diagnosis for digitalsystems. The model considered in this correspondence is thediagnostic model introduced by Maheshwari

ManuscriptreceivedSeptember 30, 1976;revised July 12, 1977.

The authorsarewith the Department ofElectronicEngineering,Osaka Univer- sity, Osaka, Japan.

0018-9340/78/0400-0379$00.75 ( 1978 IEEE

CORRESPONDENCE

(2)

and Hakimi where each unithas aprobability offailure.For this model under both fault assumptions byMaheshwari-Hakimiand by Barsi-Grandoni-Maestrini, someexistence theoremsare obtained forprobabilistically diagnosablesystems.1)Necessary and sufficient conditions for theexistenceoftestinglinkstoformprobabilistically t-diagnosable systems with and without repair.2) Necessary and sufficient conditions for the existence ofprobabilitiesof failure of all units to formprobabilistically t-diagnosablesystemswith and with- outrepair which havenohardcore.

Index Terms-Automatic diagnosis, digital systems, graphs, probabilistic faultdiagnosis, probability offailure, self-diagnosable systems,testinglinks.

I. INTRODUCTION

Thedemand for high availabilityindigitalsystems has created an urgent need for the development ofself-diagnosable systems. Studies in self-diagnosable systems have appeared in the litera- tures _[1]-[11]. Preparata et al. [3] first introduced a graph- theoretic model of digital systems for the purpose of diagnosis of multiple faults, and presented methods of optimal connection assignments for instantaneous and sequential diagnosis procedures. Maheshwari and Hakimi [10]introduced a diagnos- ability measure t based on the probability of occurrence of faults and presented necessary and sufficient conditions for a system to be probabilistically t-diagnosablein the graph-theoretic model.

For the class of failures, most of the previous works considered thefollowing faultassumption.

Fault Assumption A: Assume that unit ui tests unit

_uj.

Then, the test outcomeis"0"if, under thehypothesisthat

ui

isfault-free, uj^is also fault-free.Thetest outcomeis "1" if, under the same hypothesis,

_uj

is faulty. In the case that

ui

isfaulty, the test outcome is unreliable andcanassumeeither of the values 0, 1, regardless of thestatus of

_uj.

Barsi et al. [11]considered the following fault assumption. Fault Assumption B: Assume that unit

ui

tests unit uj. Then, the testoutcomeis "0"if,under thehypothesisthatuiisfault-free,

_uj

is also fault-free.Thetestoutcomeis"1,,if, under the same hypothesis, uJ ^is faulty. Ifui is faulty and ujis fault-free,both test outcomes are possible. If

_ui

and _uj are _faulty, the test outcome is necessary "1."

In this correspondence, we consider the Maheshwari-Hakimi model and four classes ofprobabilistically diagnosablesystems as follows.

1)

Aclassof systems which areprobabilistically t-diagnosable with repair under fault assumptionA.

2)

Aclass of systems which are

probabilistically

t-diagnosable without repair under fault assumptionA.

3)

Aclass of systems which areprobabilistically t-diagnosable with repair under fault assumption B.

4)

^Aclass of systemswhich areprobabilistically t-diagnosable without repair under fault assumption B.

For the above classes of systems, we treat two fundamental problems in this correspondence. SupposeasystemS with units U1, u2, ',

_u,

and the probability

_p(ui)

of

_ui

beingfaultyfor allui, then it seems tobe aninteresting problemtodecidewhether we can design a probabilistically t-diagnosable system by adding some_testing linkstoS. This is Problem 1.

Problem 1: To find necessary andsufficient conditions forthe existence of testing links to form probabilistically t-diagnosable systems.

Supposeasystem with_testing_links,thenit alsoseems tobean

interestingproblemtodecide whetherwe candesignaprobabilist-

ically t-diagnosable

system without hardcore

by giving

suitable

reliability

^toeach unit. This is Problem 2.

Problem 2: To find necessary and sufficient conditions for the existence of

probabilities

of failure of all unitstoform

probabilist-

ically t-diagnosable

systems without hardcore.

II. DIAGNOSTIC MODEL

A system is supposedto be partitioned inton subsystems, or

units,

^not

necessarily

identical but powerful enoughto testother

unitsof the system

by applying

stimuli andobservingthe

_ensuing

responses. Note thatnounittestsitself. LetV={u1, u2, ''',un4be thesetof all units. The relation of

testability

^can^berepresented

by

afunction F

_mapping

Vinto V such that_ujE

_F(uj)

if andonly^ifu tests_uj.It is also assumed that the faultsarestatistically

_indepen-

dent and the probability of failure of unit ui is denoted by

p(ui),

that

is, probability

of failure can berepresented by^a_{function p}

mapping

VintoR,whereRisthesetof_positivereal numbers less thanone.

_Hence,

a_systemSwill berepresented

by

^atriple^S⁼

_(V,

F,

p).

^{When F}^orp isundefined,it is denotedbythedash,that

is,

S=(V, -, p) ^or ^S⁼ (V, F, -). Clearly, this diagnostic model S =_(V, F,p)^canbe also representedbyavertex-weighted

digraph

G=

_{(V, F)}

with

weight

function p, where the arc (ui,

_uj)

is an

ordered

_pair

of vertices in V such that

_uj

E

_F(ui).

Theoutcomesofthetest_{may be}representedasbinary

weights

onthearcsofG. Theweight^{of the}^arc(ui,

_uj),

denotedbys(ui,

uj),

is "0" if_ui_{finds uj}to be_nonfaulty, andis"1"if_uifinds

_uj

to be

faulty.

^Thus ^a system S together with aset _oftest outcomes is represented byanarc-weighted digraph,which wedenote by

_G,.

We now define two types of consistent fault ^sets under fault assumptions A and B. A subset F ofV,which satisfies the following ^two conditions, is called an A-consistent fault set of S with respect^to

G,.

Condition 1:

_s(ui, _uj)

=

1,

for allui andujsuch that uj^E

F(ui),

ui^E F= _V-F,and_ujE F.

Condition 2:s(ui,

Uj)

⁼⁰^{for all}ui, uj^{such that}uj^E

F(uj)

and ui, uje ^F.

A subset F ofV,which satisfies the abovetwo conditions and thefollowing condition, is calledaB-consistentfaultsetof S with respectto

_G,.

Condition 3:s(ui,

Uj)

⁼ ¹^{for all}ui, ujsuch thatuj E F(u1)andui,

uje

^F.

Note that,when all arcs arelabeled with "0," the empty set 0 canbeaconsistent faultset.Thiscasemeans that all the unitsare

nonfaulty.

Since the faults are assumed to be statisticallyindependent, ^a prioriprobability that F c V is thesetof faults in S is given

by

P(F)

⁼_Ui6E^H

⁽¹

^-

p(ui))

_uieF

_f p(ui).

Definition 1: A system S= _{(V, F,}p) is said to be

probabilist-

ically t-diagnosable without repair under fault assumption A (fault assumption B) [shortly, p-t-diagnosable without

repair

under A _(B)] if for any arc-weighted digraph

G,

=(V, F)there existsatmost oneA-consistent (B-consistent) fault set F c V such that P(F)> t. Let

A'

(Bo) be the class of systems that are p-t- diagnosable without repair under A (B).

Itis easytoseethat inap-t-diagnosable system without_repair, any fault^setwhoseaprioriprobability of occurrence greater than tcanbe correctly identified.

Definition 2: A system S = (V, r, p) is said to be probabilistically t-diagnosable with repair under fault assumption A (fault assumption B) [shortly, p-t-diagnosable with repair under A (B)] if

(3)

CORRESPONDENCE

for any arc-weighted digraph G,⁼(V, F) there exist no A- consistent (B-consistent)fault sets F1, F2, , F1 (I 22)suchthat

n!=

^Fi⁼ ⁰^and

P(F1)

^{> t} ^forⁱ⁼

1, 2,,

^{1. Let} ^At1

(Bt1)

^{be the}

class of systems that are p-t-diagnosable with repair under A(B). In a p-t-diagnosable system with repair, theintersection of all consistent fault sets, whose a priori probability of occurrence is greater thant,is not empty so that at least the units belonging to the intersection are all faulty. Hence, there exists a sequence of applications oftests andrepairs of identified faults that allows all faults originallypresent tobeidentified.

The following theorem easily follows from the above definitions.

Theorem 1: For any O< t < 1, 1) Ao' At1, 2) Al '

Bo,

³⁾ At1 c Bt1, and 4) Bo ' B1.

Let

K(t)⁼ -log t +

_E

log (1 ^-

p(ui))

uiEV

and

1-p(ui)

W(uj)

⁼

log

^P()

for all _uiE V. Then we can readily show that for any fault set Fc V, P(F)> tif and only ifW(F)< K(t)where

W(F)= E

_W(uj).

z4eF

Therefore, the problem of finding the faulty units in a p-t- diagnosable system is reduced to that ofdeterminingtheconsist- ent fault set for which the sum of the weights of the vertices belongingtoit is lessthan

K(t).

Hence, whenreferringto asystem S represented by S⁼(V, F, p) of its diagnostic model, the re- presentation S=

_(V,

_F,

_W)

_will_also_be _utilized._Also,_{we assume} that a unit is more likely to be nonfaulty than faulty, that is,

p(ui)

^<^{i for}all ui^E ^V. This implies

_W(uj)

>0 forallui E V. Ahardcore ofa system S =_{(V, F,}

_W)

_isdefined to be a unitui such that

_W(ui)

.

_K(t),

_that _is,

_P(ui)

<t. Graph

<Z>,

called the inducedsubgraph of G on Z, consists of vertex set Z c Vand all arcs in G incident at pairs of vertices in Z. It is convenient to further extendthe domain of Fasfollows. Let

F'(ui)

⁼

_{ujIUi

uE

_F(uj)}.

ForXc

_V,

let

r(x) = U _(ui)

-

X

F-'(X)= _U F-'(ui)

^-^X.

ujeX

Using the precedingdefinitions and notations, wecan rewrite Problems 1 and 2 asfollows.

Problem 1: Givenasystem S⁼(V,-, W);find necessary and sufficient conditions for the existence of a function F to form probabilistically t-diagnosablesystems.

Problem 2: Given asystem S⁼(V,F,

-);

find necessary and sufficient conditions for the existence of a function W to form probabilistically t-diagnosable systemswithouthardcore.

III. EXISTENCE THEOREMS FOR FUNCTION F

In this section, we consider Problem 1 for each class ofp-t- diagnosablesystems.First,weshallshow necessary and sufficient conditions for the existence of a function F to form p-t- diagnosablesystems inA' and A1.

Lemma 1:If S =(V, F, W) is a system in A'1, then there exists no partition

_{U,,

U2} of V such that W(U1)< K(t) and

W(U2) < K(t).

Proof: Suppose for some partition {U1, U2} ofV, W(U1) < K(t) and W(U2)< K(t).Wecaneasily findaweighted digraphG, of S that has U1 and U2 as A-consistent fault sets. Thus, by Definition 2, S would not be p-t-diagnosable with repair under

fault assumption A. Q.E.D.

Lemma 2: Givenasystem S =

_(V,

,W), there exists a function F, such that S =(V, F, W) is in_Ao,ifthere exists no partition {U1, U2} of Vwith W(U1), W(U2)< K(t).

Proof: Consider a maximally connected graph G= _{(V, F),} i.e., F(u,)= V for all ui^E ^V. ^We shall prove that the system

s =

(V,F,W)is inAt.Theproof is bycontradiction.Assume the existence of a weighted digraph G, for which there are two A- consistent fault sets F1 and F2 with

_W(Fj),

W(F2) < K(t). Let X= V- _(F1 u F2), Y= F1 r F2,Z1 =F1- Y, and

Z2=_F2 ^-Y. Without loss of generality,wehave Z1 7 0.

IfX = 0, then {F2, Z1} isapartition ofVsuch that W(F2)< K(t) and W(Z1)<K(t). This contradicts the hypothesis. There- fore, wehave X

_*

0.

Since

_F(uj)

= V for all ui^E V, there exists an arc

_(ui, _uj)

such that_uiE^Xand

_uj

E Z1. Sinceui, uj^E ^F,and F2 isanA-consistent fault set,wehave

_s(ui, _Uj)

=0. Butsince F1isalsoanA-consistent fault set and

_ui

E F1, _ujE F1, we h-ave

_s(ui, _uj)

= 1. This is a contradiction. Hence,our initialassumption waswrong. Q.E.D. Theorem 2: Given a system S =

_(V,

-, W),^{then there}exists a function F, such that S= (V, F, W)is in Ao,if and _onlyif there exists no partition {U1, U2} of V such that

W(U1)

^<

K(t)

and W(U2)< K(t).

Proof: The necessity of the theorem follows from

1)

of Theorem 1 and Lemma 1. The sufficiency follows from Lemma

2. Q.E.D.

Theorem 3: Given a system S=(V,-, W),then there existsa function F,such that S =

(V,

F,

W)

is inAt1,if andonly if there exists no partition

_JU1,

U2} of ^V such that

W(U1)

^<

K(t)

and

W(U2)< K(t).

Proof: Thenecessityof the theorem followsfrom Lemma 1. Thesufficiencyfollows from Lemma2and 1)of Theorem 1. Q.E.D.

As anexample, considerasystemconsisting ofthree units such that p(u1)= , p(u2)= , p(U3)= , and t= . Then we have

W(ul)

⁼^log^4, W(u2)⁼ log 3, W(u3)⁼log 2, and K(t)⁼log ^8. Let U1 =

_{uj}

_{and U2}= _{U2,_{U3}, then}wehave

_W(Uj)

⁼log⁴ ^< K(t)and W(U2)⁼log 6<K(t). Thus,from Theorems 2 and3,^it canbeseenthat there exists^nofunctionFsuch that the systemis in A orAt.

When theprobability of failure of all units is the same, itcan easilybeseenthat the above conditionmeansthat thenumberof faulty units present does not exceed L(n^- 1)/2i where n=

_VI

and Lx]denotes the greatest

integer

^not

exceeding

^x.

Therefore,

Theorems 2and 3containTheorem 1 of Preparataetal.

_[3].

Next, we show the necessary and sufficient condition for the existenceof^afunction ^Ftoforma

p-t-diagnosable

^{system in}

BO.

Theorem4: Given asystem S=

_(V,

_-,

_W),

then thereexistsa

function

F,

such that S⁼

(V, F, W)

isin

_B'O,

if and

only

if there exists no partition {U,

{u1},

{u2}} of V such that

_W(U)

+

W(ul)

^<

K(t)

^and

W(U)

⁺

W(U2)

^<

K(t).

Proof-Necessity: The proof is by contradiction. Suppose 381

(4)

that S=(V, F, W)is inBb,and that for some partition {U,{u1}, {U2}} of V, W(U) +

_W(ul)

< K(t)and W(U)+ _W(U2)<K(t). Let G5 be an arc-weighteddigraph such that

s(u1, _Uj)

= 1 for all arcs (u1,

_Uj).

LetF1⁼ U u {u1}and F2 = _{U u} _{u2},_then_F1_{and F2 are} B-consistent fault sets with respect to

_G,.

Thus, S is not p-t- diagnosable without repair under assumptionB.This contradicts thehypothesis.

Sufficiency: Consider a maximally connected digraph G = (V, F). We shall prove that the system S = (V, F,W)is in

_Bo.

The proof is by contradiction. Assume the existence of a weighted digraph

_G,

for which there are two B-consistent fault setsF1and F2 with W(F1), W(F2)< K(t). Let X⁼ V^- (F1 u F2), Y = F1 n

_F2,

_Z1 =F1- Y, and Z2= _F2 - _{Y. Without} _{loss of} generality,wehave Z1 # 0.

IfX

_*

0,then there exists an arc

_(ui, _uj)

such that

ui

E X and uj E

ZI.

^Since

ui,

ujE F2 and F2 is a B-consistent fault set, we have

s(ui, _uj)

⁼0. But since F1 is also a B-consistent fault set and ueE F1, we have

_s(ui, _Uj)

= 1. This is a contradiction. Hence, we have X= 0.

If Z .2, then there exists an arc

(ui, _uj)

withui,

_uj

E Z1 since G is amaximallyconnected digraph. Since

ui, _uj

E F2 and F2 is a B-consistent faultset, wehave

_s(ui, _Uj)

=0. But sinceF1 is also a B-consistent fault set and _ujc_F1, _{we have}

_s(ui, _uj)

= _{1. This is} a contradiction. Hence, we have

.Z

^< 1. Similarly, we have

IZ21 <1.SinceZ1 #0and _IZ1 <.1,wehave JZJ =1,and

canlet Z1 ={u1}.

If Z2 + 0, then 1Z21 = 1 and we can let Z2⁼{U2}. Then we 'have

W(Y)+ W(u1)=

_W(F1)

<

_K(t),

W(Y)+W(u2)= _W(F2)<

_K(t),

and { Y, {u 1},{u2}}isapartitionofVsinceX⁼

0.

This contradicts thehypothesis of the theorem.

If Z2= _0, _then _{Y =}_F2. _{Let U}₌ _Y-_{{u2} for} _some _u2_{E Y.} Then wehave

W(U)+

W(ul)

^<

_W(Fj)

^<

K(t),

W(U)+ W(u2)⁼ W(F2) c K(t),

and{Y,

{tU1}, {u2}}

isapartitionofVsinceX⁼

_0.

This contradicts the hypothesis of the theorem. Hence,ourinitialassumption^was wrong, whichimpliesS⁼

(V,

F,

W)

is in _Bo. Q.E.D. When the

probability

of failure ofall unitsis the same,^we^can also show that theconditionof Theorem 4meansthat the number of

faulty

units present doesnotexceedn- _2.Thiscoincideswith Theorem 1 of Barsietal.

[11],

which isa_specialcaseof Theorem 4.

Lastly, we show the necessary and sufficient condition for the existence ofafunction Ftoformap-t-diagnosablesystem inBt'. Theorem5: Givenasystem S=

_(V,

_-,

_W),

then there existsa function F, such that S⁼

(V, F, W)

is in

Bt',

if and _only if there exists a subset U of V such that

Ut

=

_lvi

-1 and W(U)>_K(t).

Proof-Necessity:

The proof is by contradiction. Assume thatthere existsnosubset UofVsuch that U ⁼ V

_I1

and

W(U)

^.

_K(t).

Let V⁼

_{{ul, u2,}

,

_un4,

and

_Fi

⁼ V^-

_{ul

for all ui^E ^V. Then 1F11 = lV -1 and thus

_W(F1)

<

_K(t)

foralli⁼ _1, 2, , n. Clearly,

n n

nFi

⁼

0

and

_U Fi=

^V.

i=l i=l

Consider an

arc-weighted digraph G,

^{for which}

s(ui, uj)

⁼ 1 for allarcs

(ui, uj). Then,

^Fi^is^aB-consistent faultsetwith respect^to

G,

^{for all} ⁱ⁼

1, 2,

, ^n.

Hence,

S⁼

(V,

F,

W)

is not _p-t-

diagnosable

^with

repair

^underassumptionB. This contradicts the

hypothesis.

Sufficiency:

^Consider ^a

maximally

connected

_digraph

G = (V,

_F),

that

is, F(ui)

⁼ ^V for all u1i E V. Weshall prove that S

(V,

F,

W)

isin

Bt1.

The

_proof

is

_by

contradiction. Assume the existence of a

weighted digraph _G,

for which there exist B- consistent fault sets

_{Fl, F2,}

_,

_F,

_{such that}

n Fi=

^{0 and}

_W(F1)

^<

_K(t),

^{for all}ⁱ⁼

1, _2,,

1. If

_U5i

Fi

_* V,

then there exists anarc

(ui, uj)

such that ui E (> Fiand UjE

_Fj

r) _Fkforsome

_Fj, _Fk,

_E

_{F1, _F2,

_,_{F}. Since}

ui, ujE

Fk

^and Fkis aB-consistent fault set,^wehave_s(ui,

_uj)

=0. But since

_Fj

is alsoaB-consistent fault setand

_uj

E

_Fj,

wehave

s(ui, uj)

⁼ ^{1. This is}^a contradiction.

Hence,

wehave

U

Fi⁼ ^V.

If

Fj

.2 2 for^some

Fj,

then there existsan arc_(ui,

_uj)

_{with ui,} uj E

Fj

^since

F(ui)

⁼^V.

UL=J1

Fi⁼ ^V

implies

uj^E F,, for some

Fk#

Fj.

Since ui,

_uj

E

_Fj

and

_Fj

is a B-consistent fault set, we

have

_{s(ui, Uj)}

= 0. But sinceFkis alsoaB-consistenitfaultsetand Uj E

Fk,

^we ^have

s(ui, Uj)

⁼ 1. This isa contradiction. Hence,we

have

_IFi

_<1,

_i.e., _IFi1

_.

_lVI

_{-1 for all} i=

_1,2,,

1. From this and

_n(=1

Fi⁼

0,

^we have Fi ¢ V for allFi. Thus

_IF11

= V|i

_{-1, i.e.,} _FiF

= 1 for all

_F1. _(l=t _F1

= 0 implies

U5=! ^Fi=

^V.

^Hence, ^U!= F1=

^V ^and

FiF

⁼ ¹

^imply

^that

1=

_Vi, i.e.,

all the subsets UofVwith

_Ug

₌

_lV _I-1

are

_F1,

F2,

,

F,. Moreover, W(F1)

^< K(t).This contradicts the

_hypoth-

esis that for some Uc V with Ul =

_VI

- _{1, W(U)}_.

_K(t).

Hence,

^our initial_assumption waswrong, which impliesS=

_(V,

F,

W)

^{is in}

_BQ.

Q.E.D.

Theorems 2 and 3 have shown that the existence theorem for_Ao and

_At'

is thesame.Thesameresultcannotbe obtained for B' and

Bt1.

^That

is,

the condition of Theorem 4 isnot_equivalent_to_{that of} Theorem 5.

_However,

when the probability ^offault of all units is the same, the condition of Theorem 4 coincides with that of Theorem 5. That_is, the condition forBoandBt1 can be restated that the number offaulty units present does not exceed n-2 when all the faults areequiprobable. This isaninteresting result.

To illustrate Theorems 4 and 5,considerasystem S=

_(V,

W),

which consists of five units Ul, U2, ,U5. Suppose

p(ul)

=_4,

p(U2)

= 4,

p(U3)

⁼4,

p(U4)

= X, and

p(U5)=

a, ^then ^we have

W(ul)

⁼

log

6,

_W(u2)

⁼

log 5, _W(U3)

⁼

_log 4, _W(U4)

⁼

_log 3,

and

W(Ui5)

⁼log2.

Supposethat t= ± thenwehave K(t)=log 100. min_{W(U)

_I

U c V,

_I

U

_I

= _l

_VI

_-i}

=

_W(U2)

⁺

_W(U3)

⁺

_W(U4)

⁺

_W(U5)

⁼log 120 .

K(t).

This

implies

that fort= , S=(V,-, W)satisfies the condition of Theorems 4 and 5. Thus there exists afunction F such that

s = (V,

F,

W)

isin

B'

and

Bt'.

Suppose that t=_{4 , then} we have K(t) = log 200. Let U= _{U3, _U4, _{u5}, then} _W(U)₊ _W(u1)₌_{log 144}_< _{K(t) and}

W(U)⁺ W(U2)=log 120< K(t). This implies that for t =70, S= (V, , W) does not satisfy the condition of Theorem 4. Thus

(5)

CORRESPONDENCE

there exists no function r such that S= (V, F, W) is in

_BtO.

However, we can see that S = (V, -, W) satisfies the condition of Theorem 5 as follows: Let U⁼{u1, U2, U3, U4}, then we have W(U)⁼^{log 360 .} K(t).Hence,for t = , there exists a function F such that S = (V, F, W)isin B',.

IV. EXISTENCETHEOREMS FORFUNCTION W

In the last section, we have considered Problem 1 for each class ofp-t-diagnosable systems, and have obtained different results for

At,

At,,

Bt,

andB' . However, for Problem 2, we can show that the resultsfor

At,

4t,

Bt,

^and B' are all the same.

First we need the following lemma.

Lemma 3: If S=_(V, _F, _W)is a system in

_B'l

and has no hardcore, then 1) IF '(ui)

_*

0 for all ui^E V, and 2)for any U c V with

_I

U

_I

=2, we haveIF

`(U)

# 0.

Proof: To see that 1) is necessary, suppose otherwise. Then

there exists a vertex

UkC V

such that

F

_'((u,)

= 0. Let

G,

be an arc-weighted digraph such that

s(ui, uj)

⁼⁰for all arcs

(ui, uj)

^and

let F1 =

_{uk}

and F2 =0.Then it can easily be seen that bothF, and F2 are B-consistent fault sets with respect toGC. Moreover, since S has no hardcore, W(F1)and W(F2)<

_K(t).

This implies thatSis not p-t-diagnosable with repair under B. This contradicts the hypothesis of the theorem.

To seethat2)is necessary, suppose otherwise. Then there exists

a subset U of

V

such that

^j

U

=

2 and r- l(U)

⁼

0. Let U

=

_{ul,

u2}, F1 = {u1}and F2={u2}. Consider an arc-weighted digraph

_G,

such that for all

_uj

^E

_F(uj), _s(ui, _uj)

⁼ 1 if

_uj

⁼

ui

orU2, and

s(ui,

Uj)

⁼⁰ otherwise. Then, clearly F, and F2 are B-consistent fault setswith respectto

GC.

Moreover,

W(F1)

^and ^W(F2)^<

^K(t)

^since

S has no hardcore. This implies that S is not in

B',,

which contradicts thehypothesis ofthetheorem. Q.E.D. Suppose that all the faults are equiprobable, that is, p(u,)=p for all uiE V. One can show that

max

_{p(1-P` ₁₀

_<_p _< n ^I

_V.

₂

_3}

= (n - Hence, if

(n-1f"'

t2 ⁿ _ni

then

_P(ui)

=

p(1

^-

p)-

^.^t^for^any^{0 <}^p^<4,^thatis,each unit

_ui

isahardcore for anyprobability of failure.As a matteroffact,this caseis notrealistic. So,fromnow on,weassume that

0<

_(n-l)n-

nn

For any

(n

^-1'

n

itcan easily be seen that there existsasolution ptothefollowing inequalities:

p2(1

^_

pf-2

^<t<

_p(1

^- _p)n- and 0< p^< This impliesthat

log _p log (1

_tp < 2 _log

Ifwelet W⁼log

[(1

^-

p)/p],

then the above inequalities imply W<

_K(t)

<2W.

Therefore, for any

0<t<

(n

^-^I

thereexists afunction Wsuch that W(ui)<K(t)<

_2W(ui)

for all

Uic V.

Lemma 4: Given a system S = (V, F,-)and O<t<

_{(n-_1r-'}

then there exists a function W, such that S= (V, F, W) has no hardcore and is in

At,

^if ¹⁾

F-'(ui)½

^{0 for all}

uie

^{V and} ²⁾

F-'(U) 0

^{for any U}^c

^V

^{with U}

=2.

Proof: Since

< t< (n

_I)n-

nⁿ

there existsafunction Wsuch that W(ui)<

_K(t)

<

2W(ui)

forall ui^E V. This implies that

_W(uj)

+

_W(uj)

> _K(t)for all

ui,

Uj E V.

Let S= (V, r, W)be a systemsatisfying the conditions of the theorem. We shall show that S is in

At.

Assume that Sis not inAt, then there exists an arc-weighted digraphG, for which there are two A-consistent fault sets _F, and F2with W(F1)and W(F2)<

K(t).

^Since

W(tu)

⁺

W(uj)

^. ^K(t) ^{for all} ui,

_uj

^E V, we have

IF,! <land IF21 <.1

IfF1= 0,then F2 ½ 0and welet F2

{u$.

From 1)wehave F-

_'(i)

½ 0, thus there exists a vertex v

E

F- (u). Since u

E

F2 and F2 is anA-consistent fault set, we haves(v, u)= 1. Butsince F1 = 0is also anA-consistent fault set and u, v E F1, we haves(v, u)=0. This is a contradiction. Therefore we have F1 ½

0,

^and similarly F2 ½ 0.

Let F,⁼{u1},'F2⁼{u2} and U⁼

_{uI,

u2}. From 2) we have F

_'(U)

½ 0, thus without loss of generality we have

U3 ^EC U

and

U,

^E

F(u3).

^Since

it,

U3 E F2 and F2 isanA-consistent fault set,we have

_S(U3, u,)

⁼ ^0. ^But since F, is also ^anA-consistent fault set and U3 E

F1,

ui ^E F1,we have

S(U3,

U1)= 1. This isacontradic- tion. Hence,ourinitialassumption was wrong, whichimpliesthat

S is in At. Q.E.D.

Condition 4: 1)

F

_'(ui)

½ 0

for all _{ui E}

V

and 2)

^F-

l(U)

^½ ⁰

for any Uc V with U

_I=

2. Given a system S = (V, F,

-)

and

n0n<

then we have the following theorem for

_At, _A', _BO,

and

_B',

from Theorem 1 and Lemmas 3 and 4.

Theorem6:Thereexists afunction W,such that S ⁼(V,

F, W)

is in At

_{(A',, Bgo,}

and

B',)

and has no hardcore if and only if S satisfies Condition4.

Proof: Incase ofA,-thenecessity follows from 2)and4)of Theorem 1 and Lemma 3. Thesufficiency follows fromLemma 4. In case ofA',the necessity follows from 3)of Theorem 1 and Lemma 3. The sufficiency follows from

1)

of Theorem 1 and Lemma 4.

In case of

Bt,

thenecessity follows from

4)

of Theorem 1 and Lemma 3. The sufficiency follows from

2)

of Theorem 1 and Lemma 4.

In case of

B',,

^the necessity follows from Lemma 3. The sufficiencyfollows from

₁₎

and

₃₎

ofTheorem 1andLemma4.

Q.E.D. 383

(6)

Hence, by Theorem 6 we can see that the necessary and sufficient conditions for the existence ofafunction Wtoform a

p-t-diagnosable systemin Ab, A',

B',

and B' are_{all the} same.

V. CONCLUSIONS

Thiscorrespondence has consideredtwofundamentalproblems for fourclasses ofp-t-diagnosable ^systemsA'^,A',_BtO,andB'1: 1) Given asystemS⁼ (V, ^, W), findnecessaryandsufficient^conditions for the existence ofafunction Fsuch that^{S =} (V,F,W)is p-t-diagnosable. 2) Given asystemS⁼ (V,F,-), find necessary

and sufficient conditions for the existence ofa function Wsuch that ⁼ (V,F, W)isp-t-diagnosable and hasno hardcore.

The model anditsdiagnosability treatedhereare moregeneral than those inprevious investigations [1]-[l1].When theprobability of failure of all units ^is the same, the existence theorem of^a function ^Ffor A' and At' coincideswith thatofPreparataetal. [3] and that for_B'ocoincideswith that of Barsietal. [11]. Hence,some

existence theorems in this paper are the generalizations of previous results [3],

_[11].

The necessary and sufficient conditions for the existence of functions rand Ware,ingeneral,verysimpleandnotsohardto test. Hence, these results are useful to design various p-t- diagnosable systems. Thesynthesis problems of findingthe optimal functions ^F and W have not been considered in this correspondence. Afunction ^F is said tobe optimalif

E (U)I

is minimized. Afunction Wis said tobe optimalif

'eV ^W(uj)

is minimized. In the above sense of optimality, optimal designs of p-t-diagnosable systems are open research problems.

ACKNOWLEDGMENT

The authors wishtothank Prof. H. Ozaki of Osaka University for his support and encouragement and Mr. M. Kim of Osaka University for his useful discussions.

REFERENCES

[I] R. E. Forbs. D. H. Rutherford, C. B. Stieglitz, and L. H. Tung, "A self- diagnosable computer," in 1965 Fall Joint Comput.Conf.,AFIPS Conf. Proc., vol. 27.Washington, DC:Spartan,1965,pp. 1073-1086.

[2] E. Manning, "On computer self diagnosis-Part I: Experimental study of a processor-Part II: Generalizations and design principle," IEEE Trans. Elec- tron. Comput.,vol. EC-15, pp. 873-881, 882-890, Dec. 1966.

[3] ^F. P.Preparata,G.Metze,and R. T. Chien, "On the connection assignment problemof diagnosablesystems,"IEEE Trans.Electron. Comput., vol. EC-16, pp.848-854, Dec. 1967.

[4] C. V.Ramamoorthyand W.Mayeda,"Computerdiagnosis using the blocking gateapproach," IEEE Trans. Comput., vol. C-20, pp. 1294-1299, Nov. 1971. [5] N.Seshagiri, "Completely self-diagnosable digital systems,"^{Int. J.}Syst., vol.1,

pp.235-246,Jan. 1971.

[6] S. L. Hakimi and A. 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, "A new measure of digital system diagnosis," in Proc. Fault- Tolerant ComputingConf.,pp. 167-170, June1975.

[8] J.D.Russell and C. R.Kime, "Systemfaultdiagnosis:Closure anddiagnosabi- litywith repair," IEEE Trans.Comput.,vol. C-24, pp. 1078-1089, Nov. 1975. [9] -,"System faultdiagnosis:Masking,exposure, and diagnosabilitywithout

repair," IEEE Trans.Comput., vol. C-24, pp. 1155-1161, Dec. 1975. [10] S. N.Maheshwari and S. L. Hakimi, "On models for diagnosable systems and

probabilistic fault diagnosis," IEEE Trans. Comput., vol. C-25, pp. 228-236, Mar. 1976.

[11] F.Barsi,F.Grandoni,and P.Maestrini, "A theoryofdiagnosabilityof'digital systems,"IEEE Trans.Comput., vol. C-25, pp. 585-593, June 1976.