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

Keldysh Institute preprints, 2016 050, 16 pp. (Mi ipmp2126)

This article is cited in 7 papers

On single diagnostic tests for logic circuits in the Zhegalkin basis

K. A. Popkov


Abstract: We consider a problem of synthesis of irredundant logic circuits in the basis $\{\&,\oplus,1,0\}$ which implement Boolean functions on $n$ variables and allow short single diagnostic tests regarding constant faults of type $0$ at outputs of gates. For each Boolean function, the minimal possible length value of such a test is found. In particular, it is proved that this value does not exceed two.

Keywords: logic circuit, fault, single diagnostic test.

DOI: 10.20948/prepr-2016-50



© Steklov Math. Inst. of RAS, 2025