|
This article is cited in 3 scientific papers (total in 3 papers)
Diagnostic tests under shifts with fixed filling tuple
G. V. Antyufeev JSC NIIMA PROGRESS
Abstract:
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$.
Keywords:
shifts, tests, the Shannon function.
Received: 11.10.2019
Citation:
G. V. Antyufeev, “Diagnostic tests under shifts with fixed filling tuple”, Diskr. Mat., 32:4 (2020), 3–9; Discrete Math. Appl., 31:5 (2021), 309–314
Linking options:
https://www.mathnet.ru/eng/dm1620https://doi.org/10.4213/dm1620 https://www.mathnet.ru/eng/dm/v32/i4/p3
|
|