On effective methods for diagnosis of retaining faults in circuits
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.
diagnosis retaining faults combinatorial circuits decision trees