Estimates of test lengths in the Zhegalkin basis for constant type-1 faults at gate outputs

Abstract For Boolean functions f of special form, we obtain an upper estimate for the length D ( f ) of a fault detection test if f is implemented by circuits of gates in the Zhegalkin basis with constant type-1 faults at gate outputs. As a corollary, <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>D</m:mi> <m:mo stretchy="false">(</m:mo> <m:mi>f</m:mi> <m:mo stretchy="false">)</m:mo> <m:mo>≤</m:mo> <m:mfrac> <m:msup> <m:mi>n</m:mi> <m:mrow> <m:mi>k</m:mi> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msup> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:mi>k</m:mi> <m:mo>−</m:mo> <m:mn>2</m:mn> <m:mo stretchy="false">)</m:mo> <m:mo>!</m:mo> </m:mrow> </m:mfrac> <m:mo>+</m:mo> <m:mn>1</m:mn> </m:math> $D(f) \leq \frac{n^{k-1}}{(k-2)!}+1$ for functions f of n ≥ k variables whose Zhegalkin polynomial is of degree at most k .