Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions

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\&y,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.