Geodesic
Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions
Matematičeskie zametki, Tome 113 (2023) no. 1, pp. 75-89

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that each of the Boolean functions $x_1\oplus\dots\oplus x_n$, $x_1\oplus\dots\oplus x_n\oplus 1$ can be implemented by a logic circuit in each of the bases $\{x\oplus y,1\}$, $\{x\\overline y,x\vee y,\overline x\}$, $\{x\,x\vee y,\overline x\}$, allowing a complete diagnostic test of length not exceeding $\lceil\log_2(n+1)\rceil$ (for the first two bases) or not exceeding $n$ (for the third basis) relative to one-type stuck-at faults at outputs of gates. We also establish that each of the functions $x_1\oplus\dots\oplus x_n$, $x_1\oplus\dots\oplus x_n\oplus 1$ can be implemented by a logic circuit in the basis $\{x\oplus y,1\}$ allowing a complete diagnostic test of length not exceeding $\lceil\log_2(n+1)\rceil+1$ relative to arbitrary stuck-at faults at outputs of gates.
Keywords: logic circuit, complete diagnostic test, stuck-at fault, linear Boolean function. 
@article{MZM_2023_113_1_a6,
     author = {K. A. Popkov},
     title = {Short {Complete} {Diagnostic} {Tests} for {Circuits} {Implementing} {Linear} {Boolean} {Functions}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {75--89},
     publisher = {mathdoc},
     volume = {113},
     number = {1},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2023_113_1_a6/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions
JO  - Matematičeskie zametki
PY  - 2023
SP  - 75
EP  - 89
VL  - 113
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2023_113_1_a6/
LA  - ru
ID  - MZM_2023_113_1_a6
ER  - 
%0 Journal Article
%A K. A. Popkov
%T Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions
%J Matematičeskie zametki
%D 2023
%P 75-89
%V 113
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2023_113_1_a6/
%G ru
%F MZM_2023_113_1_a6
K. A. Popkov. Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions. Matematičeskie zametki, Tome 113 (2023) no. 1, pp. 75-89. http://geodesic.mathdoc.fr/item/MZM_2023_113_1_a6/