Geodesic
Diagnostic tests under shifts with fixed filling tuple
Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 3-9
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DM_2020_32_4_a0,
     author = {G. V. Antyufeev},
     title = {Diagnostic tests under shifts with fixed filling tuple},
     journal = {Diskretnaya Matematika},
     pages = {3--9},
     year = {2020},
     volume = {32},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_4_a0/}
}
TY  - JOUR
AU  - G. V. Antyufeev
TI  - Diagnostic tests under shifts with fixed filling tuple
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 3
EP  - 9
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_4_a0/
LA  - ru
ID  - DM_2020_32_4_a0
ER  - 
%0 Journal Article
%A G. V. Antyufeev
%T Diagnostic tests under shifts with fixed filling tuple
%J Diskretnaya Matematika
%D 2020
%P 3-9
%V 32
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2020_32_4_a0/
%G ru
%F DM_2020_32_4_a0
G. V. Antyufeev. Diagnostic tests under shifts with fixed filling tuple. Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 3-9. http://geodesic.mathdoc.fr/item/DM_2020_32_4_a0/

[1] Antyufeev G. V., “O svoistve bulevykh funktsii, garantiruyuschem suschestvovanie logarifmicheskikh diagnosticheskikh testov otnositelno sdvigov peremennykh”, Voprosy radioelektroniki. Ser. "Elektronnaya vychislitelnaya tekhnika (EVT)", 2014, no. 4, 71–77

[2] Antyufeev G. V., “Obnaruzhenie i diagnostika neispravnostei pri sdvigakh peremennykh v bulevykh funktsiyakh”, Voprosy radioelektroniki. Ser. "Elektronnaya vychislitelnaya tekhnika (EVT)", 2015, no. 2, 14–17

[3] Lozhkin S. A., Lektsii po osnovam kibernetiki, Uchebnoe posobie, Izd. otdel fakulteta VMiK MGU im. M.V. Lomonosova, Moskva, 2004, 256 pp.

[4] Romanov D. S., Antyufeev G. V., “O testakh otnositelno primitivnykh sdvigov peremennykh v bulevykh funktsiyakh”, Voprosy radioelektroniki. Ser. "Elektronnaya vychislitelnaya tekhnika (EVT)", 2013, no. 2, 64–68

[5] Shur A. M., Kombinatorika slov, Izd-vo Uralskogo un-ta, Ekaterinburg, 2003, 96 pp.

[6] Fine N. J., Wilf H. S., “Uniqueness theorem for periodic functions”, Proc. Amer. Math. Soc., 16:1 (1965), 109–114 | DOI | MR | Zbl