Characterization of Diagnosabilities on the Bounded PMC Model

Abstract

In this paper, we propose a new digragh model for system level fault diagnosis, which is called the |$(f_1,f_{2})$|-bounded Preparata–Metze–Chien (PMC) model (shortly, |$(f_1,f_{2})$|-BPMC). The |$(f_1,f_{2})$|-BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results |$0$| does not exceed |$f_{2}$||$(f_2\leq f_{1})$| provided that the upper bound on the number of faulty processors is |$f_{1}$|⁠. This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput.,EC-16, 848–854) and Barsi–Grandoni–Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585–593). Then we present some characterizations for one-step diagnosibility under the |$(f_1,f_{2})$|-bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of |$f_1/(n-1)$|-diagnosability and three configurations of |$f_1/(n-1)$|-diagnosable system under the |$(f_1,f_{2})$|-BPMC model.