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

Diskr. Mat., 2018 Volume 30, Issue 3, Pages 99–116 (Mi dm1509)

This article is cited in 9 papers

Short single tests for circuits with arbitrary stuck-at faults at outputs of gates

K. A. Popkov

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

Abstract: The following results are proved: 1) any nonconstant Boolean function may be implemented by an irredundant circuit of gates in the basis $\{x\&y,$ $\overline x,x\oplus y\oplus z\}$ admitting a single fault detection test of length at most 2 with respect to arbitrary stuck-at faults at outputs of gates, 2) there exists a six-place Boolean function $\psi$ such that any nonconstant Boolean function may be implemented by an irredundant circuit of gates in the basis $\{\psi\}$ admitting a single diagnostic test of length at most 3 with respect to arbitrary stuck-at faults at outputs of gates.

Keywords: circuit of gates, stuck-at fault, single fault detection test, single diagnostic test.

UDC: 519.718.7

Received: 08.03.2018

DOI: 10.4213/dm1509


 English version:
Discrete Mathematics and Applications, 2019, 29:5, 321–333

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025