Volume 22, No 5, 2015, P. 52-70
UDC 519.718.7
Popkov K. A.
Estimations on lengths of tests of functional elements under a large number of permissible faults
Abstract:
The problems of check of operability and state diagnosis of N logic gates which realize a given Boolean function f (x1, … , xn) in their perfect states are studied by means of composition of one-output logic circuits of them and observation of values produced by these circuits on any value sets of input variables. Random constant faults on outputs of gates are permitted; at the same time, it is assumed that not more than k gates are faulted, where k is a given natural number that does not rank over N. It is needed to minimize a number of circuits required for check of operability and determination of states of all gates. A lower bound on a number of these circuits is obtained when k is close to N. As a corollary from this bound it is derived that, under some condition for N and belonging of k to some segment, the number of circuits mentioned cannot be less than ck, where c > 1 is a constant which does not depend on choice of k from this segment.
Bibliogr. 15.
Keywords: logic gate, fault, logic circuit, check test, diagnostic test.
DOI: 10.17377/daio.2015.22.476
Kirill A. Popkov 1
1. Lomonosov Moscow State University
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: kirill-formulist@mail.ru
Received 13 February 2015
Revised 22 July 2015
References
[1] E. F. Beckenbach and R. Bellman, An Introduction to Inequalities, Random House, New York, 1961. Translated under the title Vvedenie v neravenstva, Mir, Moscow, 1965.
[2] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem (Asymptotic Bounds on Complexity of Control Systems), Izd. MGU, Moscow, 1984.
[3] K. A. Popkov, Bounds on lengths of check and diagnostic tests for logic gates, Diskretn. Anal. Issled. Oper., 21, No. 6, 73–89, 2014.
[4] K. A. Popkov, Fault detection and diagnostic tests for AND, OR, and NOT gates, Vestn. Mosk. Univ., Ser. 1, No. 6, 40–44, 2014. Translated in Mosc. Univ. Math. Bull., 69, No. 6, 267–271, 2014.
[5] K. A. Popkov, Fault detection and diagnostic tests for logic gates, Diskretn. Mat., 26, No. 2, 83–99, 2014. Translated in Discrete Math. Appl., 24, No. 4, 213–225, 2014.
[6] K. A. Popkov, On single tests for logic gates, Diskretn. Mat., 27, No. 2, 73–93, 2015.
[7] N. P. Red’kin, On complete checking tests for circuits of functional elements, Vestn. Mosk. Univ., Ser. 1, No. 1, 72–74, 1986.
[8] N. P. Red’kin, On complete checking tests for circuits of functional elements, in S. V. Yablonskii, ed., Matematicheskie voprosy kibernetiki (Mathematical Problems of Cybernetics), Vol. 2, pp. 198–222, Nauka, Moscow, 1989.
[9] N. P. Red’kin, Nadezhnost’ i diagnostika skhem (Reliability and Diagnosis of Circuits), Izd. MGU, Moscow, 1992.
[10] D. S. Romanov, On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates, Diskretn. Mat., 25, No. 2, 104–120, 2013. Translated in Discrete Math. Appl., 23, No. 3–4, 343–362, 2013.
[11] D. S. Romanov, Method of synthesis of easily testable circuits admitting single fault detection tests of constant length, Diskretn. Matem., 26, No. 2, 100–130, 2014. Translated in Discrete Math. Appl., 24, No. 4, 227–251, 2014.
[12] I. A. Chegis and S. V. Yablonskii, Logical methods for control of electric circuits, Tr. MIAN SSSR, 51, 270–360, 1958.
[13] S. V. Yablonskii, Reliability and monitoring of control systems, in Materialy Vsesoyuznogo seminara po diskretnoi matematike i ee prilozheniyam (Proc. All-Union Seminar on Discrete Mathematics and Its Applications), pp. 7–12, Izd. MGU, Moscow, 1986.
[14] S. V. Yablonskii, Certain questions of reliability and monitoring of control systems, in S. V. Yablonskii, ed., Matematicheskie voprosy kibernetiki (Mathematical Problems of Cybernetics), Vol. 1, pp. 5–25, Nauka, Moscow, 1988.
[15] S. M. Reddy, Easily testable realization for logic functions, IEEE Trans. Comput., 21, No. 1, 124–141, 1972.
