RUS  ENG
Full version
JOURNALS // Preprints of the Keldysh Institute of Applied Mathematics // Archive

Keldysh Institute preprints, 2016 014, 20 pp. (Mi ipmp2090)

On tests of contact closure for contact circuits

K. A. Popkov


Abstract: We consider a problem of synthesis of two-pole contact circuits which realize Boolean functions on $n$ variables and permit of short fault detection and diagnostic tests regarding contact closures. It is obtained than almost all Boolean functions on $n$ variables are realizable by irredundant two-pole contact circuits which permit of single fault detection, complete fault detection, and single diagnostic tests of a constant length. The following facts are also proved: (1) each Boolean function $f(x_1,\dots,x_n)$ can be realized by an irredundant two-pole contact circuit which contains not more than one input variable different from variables $x_1,\dots,x_n$ and permits of single and complete fault detection tests lengths of which do not exceed $2n$; (2) each Boolean function $f(x_1,\dots,x_n)$ can be realized by an irredundant two-pole contact circuit which contains not more than two input variables different from variables $x_1,\dots,x_n$ and permits of a single diagnostic test a length of which does not exceed $4n$.

Keywords: contact circuit, contact closure, single fault detection test, complete fault detection test, single diagnostic test.



© Steklov Math. Inst. of RAS, 2025