A method of synthesis of irredundant circuits admitting single fault detection tests of constant length. (English. Russian original) Zbl 1454.94146
Discrete Math. Appl. 29, No. 1, 35-48 (2019); translation from Diskretn. Mat. 29, No. 4, 87-105 (2017).
Summary: A constructive proof is given that in each of the bases \(B' = \{x\& y, x\oplus y, x \sim y\}\), \(B_1 = \{x\& y,x\oplus y, 1\}\) any \(n\)-place Boolean function may be implemented: by an irredundant combinational circuit with \(n\) inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates) a single fault detection test of length at most 16, by an irredundant combinational circuit with \(n\) inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most \(2n-2\log_2n+O(1)\); besides, there exists an \(n\)-place function that cannot be implemented by an irredundant circuit admitting a detecting test whose length is smaller than \(2n-2\log_2n - \Omega(1)\), by an irredundant combinational circuit with \(n\) inputs and three outputs admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most 17.
MSC:
| 94C05 | Analytic circuit theory |
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
| 94C12 | Fault detection; testing in circuits and networks |
Keywords:
circuit of gates; fault detection test; stuck-at fault; Shannon function; easily testable circuitReferences:
| [1] | Red’kin N. P., Reliability and diagnostics of circuits, Izdatel’stvo MGU, Moscow, 1992 (in Russian), 192 pp.; Red’kin, N. P., Reliability and diagnostics of circuits, 192 (1992) · Zbl 1358.94118 |
| [2] | Reddy S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., 21:1 (1972), 124-141.; Reddy, S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., 21, 1, 124-141 (1972) · Zbl 0243.94032 |
| [3] | Hayes J. P., “On modifying logic networks to improve their diagnosability”, IEEE Trans. Comput., C-23:1 (1974), 56-62.; Hayes, J. P., “On modifying logic networks to improve their diagnosability”, IEEE Trans. Comput., C-23, 1, 56-62 (1974) |
| [4] | Saluja K. K., Reddy S. M., “On minimally testable logic networks”, IEEE Trans. Comput., C-23:1 (1974), 552-554.; Saluja, K. K.; Reddy, S. M., “On minimally testable logic networks”, IEEE Trans. Comput., C-23, 1, 552-554 (1974) · Zbl 0279.94032 |
| [5] | Noskov V. N., “Design of easily testable combinational circuits”, Discrete Math. Appl., 3:5 (1993), 535-553.; Noskov, V. N., “Design of easily testable combinational circuits”, Discrete Math. Appl., 3, 5, 535-553 (1993) · Zbl 0807.94023 |
| [6] | Hirayama T., Koda G., Nishitani Y., Shimizu K., “Easily testable realization based on OR-AND-EXOR expansion with singlerail inputs”, IEICE Trans. Inf. and Syst., E-82D:9 (1999), 1278-1286.; Hirayama, T.; Koda, G.; Nishitani, Y.; Shimizu, K., “Easily testable realization based on OR-AND-EXOR expansion with singlerail inputs”, IEICE Trans. Inf. and Syst., E-82D, 9, 1278-1286 (1999) |
| [7] | Kalay U., Hall D. V., Perkowski M. A., “A minimal universal test set for self-test of EXOR-Sum-of-Products circuits”, IEEE Trans. Comput., 49:3 (2000), 267-276.; Kalay, U.; Hall, D. V.; Perkowski, M. A., “A minimal universal test set for self-test of EXOR-Sum-of-Products circuits”, IEEE Trans. Comput., 49, 3, 267-276 (2000) · Zbl 1003.94541 |
| [8] | Inose H., Sakauchi M., “Synthesis of automatic fault diagnosable logical circuits by function conversion method”, First USA-Japan Computer Conf. Proc., 1972, 426-430.; Inose, H.; Sakauchi, M., “Synthesis of automatic fault diagnosable logical circuits by function conversion method”, First USA-Japan Computer Conf. Proc., 426-430 (1972) |
| [9] | DasGupta S., Hartmann C. R. P., Rudolph L. D., “Dual-mode logic for function-independent fault testing”, IEEE Trans. Comput., C-29:11 (1980), 1025-1029.; DasGupta, S.; Hartmann, C. R. P.; Rudolph, L. D., “Dual-mode logic for function-independent fault testing”, IEEE Trans. Comput., C-29, 11, 1025-1029 (1980) · Zbl 0447.94048 |
| [10] | Red’kin N. P., “About complete checking tests for circuits of functional elements”, Moscow University Mathematics Bulletin, \(1986, N^o, 72-74\) (in Russian).; Red’kin, N. P., “About complete checking tests for circuits of functional elements”, Moscow University Mathematics Bulletin, 72-74 (1986) · Zbl 0597.94024 |
| [11] | Red’kin N. P., “About complete checking tests for circuits of functional elements”, Matem. voprosy kibernetiki, 2, Nauka, Moscow, 1989, 198-222.; Red’kin, N. P., Matem. voprosy kibernetiki, 2, 198-222 (1989) · Zbl 0712.94027 |
| [12] | Romanov D. S., “Method of synthesis of easily testable circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 24:4 (2014), 227-251.; Romanov, D. S., “Method of synthesis of easily testable circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 24, 4, 227-251 (2014) · Zbl 1339.94106 |
| [13] | Red’kin N. P., “About checking tests for circuits with single-type constant faults on the inputs of elements”, Izv. vuzov. Matematika, \(1988, N^o 7, 57-64\) (in Russian).; Red’kin, N. P., “About checking tests for circuits with single-type constant faults on the inputs of elements”, Izv. vuzov. Matematika, 7, 57-64 (1988) · Zbl 0657.94020 |
| [14] | Borodina Yu. V., “Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs”, Moscow Univ. Comput. Math. Cyber., 32:1 (2008), 42-46.; Borodina, Yu. V., “Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs”, Moscow Univ. Comput. Math. Cyber., 32, 1, 42-46 (2008) · Zbl 1146.93327 |
| [15] | Borodina Yu. V., “Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements”, Moscow Univ. Math. Bulletin, 63:5 (2008), 202-204.; Borodina, Yu. V., “Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements”, Moscow Univ. Math. Bulletin, 63, 5, 202-204 (2008) · Zbl 1304.94140 |
| [16] | Borodina Yu. V., Borodin P. A., “Synthesis of easily testable circuits over the Zhegalkin basis in the case of constant faults of type 0 at outputs of elements”, Discrete Math. Appl., 20:4 (2010), 441-449.; Borodina, Yu. V.; Borodin, P. A., “Synthesis of easily testable circuits over the Zhegalkin basis in the case of constant faults of type 0 at outputs of elements”, Discrete Math. Appl., 20, 4, 441-449 (2010) · Zbl 1201.94149 |
| [17] | Borodina Yu.V., “Lower estimate of the length of the complete test in the basis {x|y}”, Moscow Univ. Math. Bulletin, 70:4 (2015), 185-186.; Borodina, Yu. V., “Lower estimate of the length of the complete test in the basis {x|y}”, Moscow Univ. Math. Bulletin, 70, 4, 185-186 (2015) · Zbl 1357.94109 |
| [18] | Romanov D. S., “On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates”, Discrete Math. Appl., 23:3-4 (2013), 343-362.; Romanov, D. S., “On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates”, Discrete Math. Appl., 23, 3-4, 343-362 (2013) · Zbl 1329.94108 |
| [19] | Popkov K.A., “On an exact length value of a minimal single diagnostic test for one class of circuits”, Preprinty IPM im. M. V. Keldysha RAN, 2015, 074 (in Russian), 20 pp.; Popkov, K. A., “On an exact length value of a minimal single diagnostic test for one class of circuits”, Preprinty IPM im. M. V. Keldysha RAN, 074, 20 (2015) · Zbl 1399.93061 |
| [20] | Romanov D. S., Romanova E. Yu., “The method of synthesis of non-redundant circuits allowing short single diagnostic tests for constant faults on the outputs of the elements”, Izv. vuzov. Povolzhsk. reg. Fiz-matem. nauki, \(2016, N^o 2, 87-102\) (in Russian).; Romanov, D. S.; Romanova, E. Yu., “The method of synthesis of non-redundant circuits allowing short single diagnostic tests for constant faults on the outputs of the elements”, Izv. vuzov. Povolzhsk. reg. Fiz-matem. nauki, 2, 87-102 (2016) |
| [21] | Popkov K.A., “On single diagnostic tests for circuits of functional elements in the Zhegalkin basis”, Preprinty IPM im. M. V. Keldysha RAN, 2016, 050 (in Russian), 16 pp.; Popkov, K. A., “On single diagnostic tests for circuits of functional elements in the Zhegalkin basis”, Preprinty IPM im. M. V. Keldysha RAN, 050, 16 (2016) · Zbl 1492.94229 |
| [22] | Popkov K.A., “Single fault detection tests for networks of functional elements in the basis “conjunction-negation”, Preprinty IPM im. M. V. Keldysha RAN, 2017, 030 (in Russian), 31 pp.; Popkov, K. A., “Single fault detection tests for networks of functional elements in the basis “conjunction-negation”, Preprinty IPM im. M. V. Keldysha RAN, 030, 31 (2017) · Zbl 1525.94072 |
| [23] | Popkov K.A., “Lower estimates for the lengths of the complete diagnostic tests for circuits and circuit inputs”, Prikladnaya diskretnaya matematika, \(2016, N^o 4(34), 65-73\) (in Russian).; Popkov, K. A., “Lower estimates for the lengths of the complete diagnostic tests for circuits and circuit inputs”, Prikladnaya diskretnaya matematika, 4, 34, 65-73 (2016) · Zbl 1492.94229 |
| [24] | Popkov K.A., “Lower estimates for unit test lengths for functional element circuits”, Diskretnaya matematika, 29:2 (2017), 53-69 (in Russian).; Popkov, K. A., “Lower estimates for unit test lengths for functional element circuits”, Diskretnaya matematika, 29, 2, 53-69 (2017) |
| [25] | Alekhina M. A., “On reliability of circuits from unreliable functional elements under single-type constant faults on outputs of elements”, Diskretnaya matematika, 5:2 (1993), 59-74.; Alekhina, M. A., “On reliability of circuits from unreliable functional elements under single-type constant faults on outputs of elements”, Diskretnaya matematika, 5, 2, 59-74 (1993) · Zbl 0808.94031 |
| [26] | Alekhina M. A., Synthesis of asymptotically optimal schemes for reliability from unreliable elements, IITs PGU, Penza, 2006 (in Russian), 156 pp.; Alekhina, M. A., Synthesis of asymptotically optimal schemes for reliability from unreliable elements, 156 (2006) |
| [27] | Alekhina M. A., Klyanchina D. M., “On the asymptotically optimal in terms of reliability schemes in some special bases”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, \(2010, N^o 4(16), 3-13\) (in Russian).; Alekhina, M. A.; Klyanchina, D. M., “On the asymptotically optimal in terms of reliability schemes in some special bases”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, 4, 16, 3-13 (2010) |
| [28] | Alekhina M. A., “On reliability of circuits over an arbitrary complete finite basis under single-type constant faults at outputs of elements”, Discrete Math. Appl., 22:4 (2012), 383-391.; Alekhina, M. A., “On reliability of circuits over an arbitrary complete finite basis under single-type constant faults at outputs of elements”, Discrete Math. Appl., 22, 4, 383-391 (2012) · Zbl 1262.94028 |
| [29] | Alekhina M. A., Barsukova O. Yu., “The reliability of circuits in the basis anticonjuction with constant faults of gates”, Comput. Sci. Inf. Technol., 2(1) (2014), 51-54.; Alekhina, M. A.; Barsukova, O. Yu., “The reliability of circuits in the basis anticonjuction with constant faults of gates”, Comput. Sci. Inf. Technol., 2, 1, 51-54 (2014) · Zbl 1324.94066 |
| [30] | Alekhina M. A., “Synthesis of reliable circuits for constant faults on the inputs and outputs of elements”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, \(2015, N^o 2, 3-15\) (in Russian).; Alekhina, M. A., “Synthesis of reliable circuits for constant faults on the inputs and outputs of elements”, Izv. vuzov. Povolzhsk. reg. Fiz.-matem. nauki, 2, 3-15 (2015) · Zbl 1059.94049 |
| [31] | Alekhina M. A., Kurysheva V. V., “On the reliability of circuits in the basis of “anti-conjunction” with constant faults on the inputs of elements“, Izv. vuzov. Matematika, \(2016, N^o 7, 3-9\) (in Russian).; <element-citation publication-type=”journal“ publication-format=”print“>Alekhina, M. A.Kurysheva, V. V.”On the reliability of circuits in the basis of “anti-conjunction” with constant faults on the inputs of elements”Izv. vuzov. Matematika2016739in Russian · Zbl 1345.94106 |
| [32] | Romanov D. S., Romanova E. Yu., “Short tests for circuits in the Zhegalkin basis”, Intellektual’nye sistemy. Teoriya i prilozheniya, 20:3 (2016), 73-78 (in Russian).; Romanov, D. S.; Romanova, E. Yu., “Short tests for circuits in the Zhegalkin basis”, Intellektual’nye sistemy. Teoriya i prilozheniya, 20, 3, 73-78 (2016) |
| [33] | Noskov V. N., “On the complexity of tests controlling the operation of logic circuit inputs”, Diskretnyy analiz, 27, IM SO AN SSSR, Novosibirsk, 1975, 23-51 (in Russian).; Noskov, V. N., Diskretnyy analiz, 27, 23-51 (1975) · Zbl 0325.94024 |
| [34] | Pogosyan G. R., On fault detection testing of logic circuits, VTs AN SSSR, Moscow, 1982 (in Russian), 57 pp.; Pogosyan, G. R., On fault detection testing of logic circuits, 57 (1982) · Zbl 1310.42002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
