Genetic Algorithm for Placing Control Points in a Digital Device


The article considers the problem of placing control points in a digital device in order to increase its controlability. The previously known methods for solving this problem were based on a preliminary analysis of the device topology (structure) for the estimation of such parameters as controllability, observability and testability. The corresponding indicators in many well-known systems for analyzing compliance were calculated using software tools. Carrying out such an analysis is a rather laborious process. In the proposed article, the solution of the problem of placing control points, which is one of the ways to increase the controllability, is based on a fundamentally different approach. This approach also involves the evaluation of the above-mentioned indicators of the device, but this estimate is related to the calculation of the amount of information delivered to various nodes of the device during the process of supplying random input sequences to it. This approach is less labor-intensive than the analysis of the topology (structure) of the digital device.


1. Khalchev V. F. Povyshenie kontroleprigodnosti diskretnykh ustroistv : sostoianie i problemy [Increase of controllability of discrete devices: state and problems]. Izmereniia, kon-trol’, avtomatizatsiia, 1980, no. 1, pp. 25–30 (in Russian).
2. Williams T. W., Parker K. P. Design for Testability A Survey. IEEE Trans. Comput., vol. 31, no. 1, pp. 2–15. DOI: 10.1109/TC.1982.1675879.
3. Robach C., Guibert S. Testability measures: a review. Computer Systems, 1988, vol. 3, no. 3, pp. 117–126.
4. Bennets R. G. Design of testable logic circuits. Addison Wesley Publishing Company, 1984. 274 p.
5. Grason J. TMEAS, a testability measurement program. DAC’79 Proceedings of the 16th Design Automation Conference. IEEE Press, Piscataway, NJ, USA, 1979, pp. 156–161.
6. Goldstein L. H. Controlability/observability analysis of digital circuits. IEEE Transactions on Circuits and Systems, 1979, vol. 26, no. 9, pp. 685–693. DOI: 10.1109/ TCS.1979.1084687.
7. He M. T., Contreras G. K., Tehranipoor M., Tran D., Winemberg L. Test-point insertion efficiency analysis for LBIST applications. IEEE 34th VLSI Test Symposium (VTS), Las Vegas, NV, 2016, pp. 1–6. DOI: 10.1109/VTS.2016.7477314.
8. Speranskii D. V. Testability analysis of discrete devices on information approach base: theory, software, statistical results. Proc. 6th Intern. Symposium of Technical Diagnostics 89. Prague, Czech Republic, 1989, vol. 2, pp. 439–442.
9. Barashko A. S., Skobtsov Yu. A., Speranskiy D. V. Modelirovanie i testirovanie diskretnykh ustroistv [Modeling and testing of discrete devices]. Kiev, Naukova dumka, 1992. 286 p. (in Russian).
10. Savir J. Good controllability and observability do not guarantee good testability. IEEE Transactions on Computers, 1983, vol. C-32, no. 12. pp. 1198–1200. DOI: 10.1109/TC.1983.1676183.

11. Yaglom A. M., Yaglom I. M. Probability and Information (Theory and Decision Library). Kluwer, 1983. 421 p.
12. Gmurman V. E. Fundamentals of Probability Theory and Mathematical Statistics. Iliffe Books Ltd., 1968. 249 p.
13. Skobtsov Yu. A., Speranskiy D. V. Evoliutsionnye vychisleniia [Evolutionary calculations]. Moscow, Natsional’nyi otkrytyi universitet „INTUIT“, 2015. 326 p. (in Russian).

Full text: