RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2022 Number 5, Pages 51–54 (Mi vmumm4497)

Short notes

Short complete diagnostic tests for logic circuits in one infinite basis

K. A. Popkov

Keldysh Institute of Applied Mathematics of Russian Academy of Sciences, Moscow

Abstract: We prove that each Boolean function can be modeled by a logic circuit with one additional input in a basis consisting of conjunctions of an arbitrary number of variables, two-input disjunction and negation, allowing a complete diagnostic test with the length no more than $n+1$ relative to constant faults of type $1$ at outputs of logic gates.

Key words: logic network, stuck-at fault, complete diagnostic test, Boolean function.

UDC: 519.718.7

Received: 04.02.2022


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2022, 77:5, 250–253

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025