Detection of false paths in logical circuits by joint analysis of the AND/OR trees and SSBDD-graphs. (English. Russian original) Zbl 1302.94075
Autom. Remote Control 74, No. 7, 1164-1177 (2013); translation from Avtom. Telemekh. 2013, No. 7, 126-142 (2013).
Summary: Consideration was given to the problem of time verification of the combinational circuits, namely, to the problem of determining the false paths. The delays arising in the false paths do not manifest themselves in the circuit operational mode. At determination of the maximal circuit delay as a whole it is recommendable to detect and disregard such paths. It was proposed to reduce the problem of detecting a false path to the search of a test pattern for the stuck-at 0.1 faults of the character of the equivalent normal form corresponding to this path. Search of the test patterns comes to analyzing the conjunctions of the equivalent normal form represented compactly by the AND-OR trees and the structurally synthesized binary decision diagrams. The joint analysis of the AND-OR trees and such diagrams was oriented to reducing the computer burden at seeking the test patterns.
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 94C15 | Applications of graph theory to circuits and networks |
References:
| [1] | Bushnell, M.L. and Agrawal, V., Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits, New York: Kluwer, 2000. |
| [2] | Majumder, S., Bhattachary, B.B., Agrawal, V.D., and Bushnell, M.L., A New Classification of Path Delay Fault Testability in Terms of Stuck-at Faults, Comput. Sci. Technol., 2004, vol. 19, no. 6, pp. 955–964. · doi:10.1007/BF02973460 |
| [3] | Matrosova, A., Lipsky, V., Melnikov, A., and Singh, V., Path Delay Faults and ENF, in Proc. EWDTS’10, St. Petersburg, 2010, pp. 164–167. |
| [4] | Armstrong, D.B., On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets, IEEE Trans. Electron. Comput., 1966, vol. 15, no. 1, pp. 66–73. · Zbl 0161.14202 · doi:10.1109/PGEC.1966.264376 |
| [5] | Matrosova, A.Yu., Algoritmicheskie metody sinteza testov (Algorithmic Methods of Test Design), Tomsk: Tomsk. Univ., 1990. |
| [6] | Matrosova, A., Andreeva, V., Melnikov, A., and Nikolaeva, E., Multiple Stuck-at Fault and Path Delay Fault Testable Circuit, in Proc. EWDTS’08, Lviv, 2008, pp. 356–364. |
| [7] | Ubar, R., Multi-Valued Simulation of Digital Circuits with Structurally Synthesized Binary Decision Diagrams, Multiple Valued Logic, 1998, vol. 4, pp. 141–157. · Zbl 1025.94513 |
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.
