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

Diskr. Mat., 2020 Volume 32, Issue 3, Pages 49–67 (Mi dm1607)

This article is cited in 2 papers

Bounds on Shannon functions of lengths of contact closure tests for contact circuits

K. A. Popkov

Keldysh Institute of Applied Mathematics

Abstract: We consider the problem of synthesis of irredundant two-pole contact circuits which implement $n$-place Boolean functions and allow short single fault detection or diagnostic tests of closures of at most $k$ contacts. We prove that the Shannon function of the length of a fault detection test is equal to $n$ for any $n$ and $k$, and that the Shannon function of the length of a diagnostic test is majorized by $n+k(n-2)$ for $n\geqslant 2$.

Keywords: contact circuit, contact closure, Boolean function, fault detection test, diagnostic test, Shannon function.

UDC: 519.718.7

Received: 27.12.2019

DOI: 10.4213/dm1607


 English version:
Discrete Mathematics and Applications, 2021, 31:3, 165–178

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025