On single diagnostic tests for logic circuits in the Zhegalkin basis

Background. The article considers a problem of synthesis of irredundant logic circuits in the basis $\{\&, \oplus, 1, 0\}$ which implement Boolean functions on n variables and allow short single diagnostic tests regarding constant faults of type 0 on outputs of gates. It relates to the problem of synthesis of easily testable circuits which was put in 1950s and has been well researched by now. Materials and methods. For construction of easily testable circuits the earlier known method of synthesis was used and modified for the given problem. The lower bounds of test lengths were proved “by contradiction” via obtaining restrictions on the structure of circuits admitting short tests. Results. For each Boolean function, the minimal possible length value of a single diagnostic test in the basis $\{\&, \oplus, 1, 0\}$ regarding the faults mentioned has been found. In particular, it is proved that this value does not exceed two. Conclusions. The problem considered is completely solved. In particular, earlier upper bounds of the minimal lengths of single diagnostic tests in this problem statement have been significally improved.