RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2022 Volume 34, Issue 2, Pages 67–82 (Mi dm1702)

This article is cited in 3 papers

Short complete diagnostic tests for circuits with two additional inputs in some basis

K. A. Popkov

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

Abstract: We prove that any Boolean function in $n$ variables can be modeled by a testable Boolean circuit with two additional inputs in the basis “conjunction, oblique conjunction, disjunction, negation” so that the circuit admits a complete diagnostic test of the length at most $2n+3$ with respect to stuck-at faults of the type $1$ at gate outputs.

Keywords: Boolean circuit, stuck-at fault, complete diagnostic test, Boolean function.

UDC: 519.718.7

Received: 28.02.2022

DOI: 10.4213/dm1702


 English version:
Discrete Mathematics and Applications, 2023, 33:4, 219–230


© Steklov Math. Inst. of RAS, 2025