RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2025 Volume 117, Issue 5, Pages 736–749 (Mi mzm14492)

Short single-fault tests for circuits in the Zhegalkin basis with arbitrary constant faults of gates

K. A. Popkov

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

Abstract: The problem of implementing Boolean functions by irredundant Boolean circuits in the Zhegalkin basis which admit short single-fault tests in the presence of arbitrary stuck-at faults at gate outputs is considered. It is proved that the Shannon function of the length of a single-fault fault detection (single-fault diagnostic) test does not exceed $3$ (respectively, $5$).

Keywords: Boolean circuit, Zhegalkin basis, stuck-at fault, single-fault fault detection test, single-fault diagnostic test, Boolean function.

UDC: 519.718.7

MSC: 94C12

Received: 02.09.2024
Revised: 22.11.2024

DOI: 10.4213/mzm14492


 English version:
Mathematical Notes, 2025, 117:5, 826–836


© Steklov Math. Inst. of RAS, 2025