Diagnostic tests under shifts with fixed filling tuple

G. V. Antyufeev

Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 3-9

Résumé

We consider a fault source under which the fault functions are obtained from the original function $f({\tilde{x}}^n)\in P_2^n$ by a left shift of values of the Boolean variables by at most $n$. For the vacant positions of the variables, the values are selected from a given filling tuple $\tilde \gamma = (\gamma_1,\gamma_2,\dots,\gamma_n) \in E^n_2$, which also moves to the left by the number of positions corresponding to a specific fault function. The problem of diagnostic of faults of this kind is considered. We show that the Shannon function $L_{\tilde{\gamma}}^{\rm shifts, diagn}(n)$, which is equal to the smallest necessary test length for diagnostic of any $n$-place Boolean function with respect to a described fault source, satisfies the inequality $\left\lceil \frac{n}{2} \right\rceil \leq L_{\tilde{\gamma}}^{\rm shifts, diagn}(n) \leq n$.

Détail

Keywords: shifts, tests, the Shannon function.