On single detection test sets under replacements of gates with inverters

G.G. Temerbekova^∗ , D.S. Romanov^∗∗

Lomonosov Moscow State University, Moscow, 119991 Russia

E-mail: ^∗gulgaisha93@mail.ru, ^∗∗romanov@cs.msu.ru

Received July 20, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.359-366

For citation: Temerbekova G.G., Romanov D.S. On single detection test sets under replacements of gates with inverters. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 359–366. doi: 10.26907/2541-7746.2020.3.359-366. (In Russian)

Abstract

Detection testing of Boolean functions implemented by Boolean circuits, which are affected by single replacements of gates with inverters, was discussed. The relevance of the study is determined by the fact that replacements of gates with inverters is a type of malfunction that occurs in the development and production of VLSI. The study was carried out in order to prove the possibility of constructing easily testable circuits under replacing elements with inverters. To achieve this goal, special methods for the synthesis of easily testable circuits were developed. Based on the results of the study, the following conclusions were drawn: for an arbitrary Boolean function implemented over a Zhegalkin basis B₁ = {x & y, x ⊕ y, 1} , there is an irredundant circuit that allows a single detection test set consisting of one vector; for an arbitrary Boolean function implemented over a standard basis B₀ = {x & y, x ∨ y, x¯} , there is an irredundant circuit that allows a single detection test set consisting of two vectors.

Keywords: Boolean circuit, detection test set, Shannon function, replacements of gates

Acknowledgments. The study was supported by the Moscow Center for Fundamental and Applied Mathematics (project “Complexity characteristics of Boolean functions and graphs”), Russian Foundation for Basic Research (project no. 18-01-00800-a), and state-financed research work no. 5.4.19 at the Faculty of Computational Mathematics and Cybernetics of Lomonosov Moscow State University.

References

1. Lozhkin S.A. Lektsii po osnovam kibernetiki [Lectures on Basic Cybernetics]. Moscow, Izd. Otd. Fak. VMiK MGU, 2004. 253 p. (In Russian)
2. Borodina Yu.V. Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs. Moscow Univ. Comput. Math. Cybern., 2008, vol. 32, no. 1, pp. 42–46. doi: 10.3103/s11968-008-1006-5.

The content is available under the license Creative Commons Attribution 4.0 License.