On Effective Methods for Diagnosis of Retaining Faults in Circuits

Article type: Research Article

Authors: Moshkova, Albina

Affiliations: Faculty of Computing Mathematics and Cybernetics of Nizhny Novgorod State University 23, Gagarina Av., Nizhny Novgorod, 603950, Russia. allmo@rol.ru

Note: [] Address for correspondence: Faculty of Computing Mathematics and Cybernetics of Nizhny Novgorod State University, 23, Gagarina Av., Nizhny Novgorod, 603950, Russia

Abstract: In the paper so-called retaining faults of combinatorial circuits are considered. It is proved that for iteration-free circuits there exist decision trees which solve the problem of circuit diagnosis relatively retaining faults and which depth is bounded from above by a linear function on the number of gates in circuits. For each closed class of Boolean functions a basis is found which is optimal from the point of view of complexity of diagnosis of formula-like circuits over this basis (during the procedure of diagnosis each formula-like circuit is transformed into an iteration-free circuit). Relationships are studied between two types of Shannon functions. A function of the first type characterizes the complexity of diagnosis of formula-like circuits realizing Boolean functions from a closed class. A function of the second type characterizes the complexity of formulas realizing Boolean functions from a closed class. The obtained relationships allowe to transfer some known results for Shannon functions of the second type on the case of Shannon functions of the first type.

Keywords: combinatorial circuits, retaining faults, diagnosis, decision trees

Journal: Fundamenta Informaticae, vol. 66, no. 3, pp. 299-313, 2005