Scaling controlled random tests based on Hadamard matrices

Objectives. The problem of constructing controlled random tests is solved by two-dimensional scaling of initial templates using Hadamard matrices. The limitations of classical approaches to generating test patterns based on enumeration of candidates for test patterns are shown. With an increase in the threshold values of the difference measures of binary test patterns, the computational complexity of constructing such tests increases. The main goal of this article is to develop methods for constructing tests based on initial templates and their expansion to the required bit size based on the application of formal rules.
Methods. For two-dimensional scaling of initial templates with specified Hamming distance thresholds, Hadamard matrices and the Sylvester recursive procedure for their construction are applied. The experimental research employed the method of statistical trials.
Results. It is demonstrated that methods for constructing controlled random tests based on templates can be viewed as a procedure for scaling controlled random tests to the required bit size. Both templates characterized by the minimum bit size of patterns and any controlled random tests are used to construct the desired tests. The procedure itself is characterized as one-dimensional scaling, which increases the bit size of patterns while maintaining their quantity. To simultaneously increase the bit size and quantity of test sets, a method based on two-dimensional scaling of templates using Hadamard matrices is proposed. This allows for the construction of controlled random tests without the labor-intensive process of enumerating candidate test patterns and computing their difference measure values. It is shown that the unique orthogonality property of Hadamard matrices, as their order increases, enables achieving ratios of the average Hamming distance between test patterns to their bit size close to 1/2. It is noted that the characteristics of the initial templates do not significantly affect the characteristics of the resulting tests constructed using Hadamard matrices obtained through the Sylvester recursive procedure. The feasibility and efficiency of the proposed approach to constructing controlled random tests are evaluated for the case of testing memory devices. It is demonstrated that controlled random tests constructed using Hadamard matrices have significantly higher coverage capability compared to random tests.
Conclusion. An approach for generating test patterns in the formation of controlled random tests using Hadamard matrices is considered. The proposed approach is based on two-dimensional scaling of initial templates using these matrices. It is shown that the use of various templates and their two-dimensional scaling allows for the construction of controlled random tests with the required bit size of test patterns and a larger number of them

1. Anand S., Burke E. K., Chen T. Y., Clark J., Cohen M. B., …, Zhu H. An orchestrated survey on automate software test case generation. Journal of Systems and Software, 2014, vol. C-39, no. 4, pp. 582–586.

2. Yarmolik V. . Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).

3. Karmore S. P., Mahajan A. R. Testing of embedded system, an issues and challenges. International Journal of Enhanced Research in Science, Technology & Engineering, 2015, vol. 4, no. 8, pp. 181–186.

4. Krupp A., Muller W. A Systematic approach to the test of combined HW/SW systems. Proceeding of the IEEE Conference on the Testing and Automation of Embedded Systems (DATE 2010), Dresden, Germany, 8–12 March 2010. Dresden, 2010, pp. 323–326.

5. Malaiya Y. K., Yang S. The coverage problem for random testing. Proceeding of the International Test Conference, Philadelphia, PA, USA, 16 18 October 1984. Philadelphia, 1984, pp. 237–242.

6. Arcuri A., Iqbal M. Z., Briand L. Random testing: Theoretical results and practical implications. IEEE Transactions on Software Engineering, 2011, vol. 38, no. 2, рр. 258–277.

7. Garousi V., elderer M., Karapıçak C. M., Yılmaz U. Testing embedded software: A survey of the literature. Information and Software Technology, 2018, vol. 104, pp. 14–45.

8. Saini D. K. Software testing for embedded systems. International Journal of Computer Applications, 2012, vol. 43, no. 17, pp. 1–6.

9. Karmore S. P., Mahajan A. P. Universal methodology for embedded system testing. Proceeding of the 8th International Conference on Computer Science & Education (ICCSE 2013), Colombo, Sri Lanka, 26 28 April 2013. Colombo, 2013, pp. 567–572.

10. Huang R., Sun W., Xu Y., Chen H., Towey D., Xia X. A survey on adaptive random testing. IEEE Transactions on Software Engineering, 2021, vol. 47, no. 10, pp. 2052–2083.

11. Chen T. Y., Kuo F. C., Merkel R. G., Tse T. H. Adaptive random testing: The art of test case diversity. Journal of Systems and Software, 2010, vol. 83, pp. 60–66.

12. Yarmolik S. V., Yarmolik V. N. Controlled random tests. Automation and Remote Control, 2012, vol. 73, no. 10, pp. 1704–1714.

13. Mrozek I., Yarmolik V. Antirandom test vectors for BIST in hardware/software systems. Fundamenta Informaticae, 2012, vol. 119, no. 2, pp. 163–185.

14. Alamgir A. Adaptive random testing with total Cartesian distance for black box circuit under test. Indonesian Journal of Electrical Engineering and Computer Science, 2020, vol. 20, no. 2, pp. 720–726.

15. Wu S. H., Jandhyala S., Malaiya Y. K., Jayasumana A. P. Antirandom testing: A distance-based approach. Hindawi Publishing Corporation VLSI Design, 2008, vol. 2008, article ID 165709, 9 p. DOI: 10.1155/2008/165709.

16. Xu S., Chen J. Maximum distance testing. Proceedings of the 11th Asian Test Symposium ( ’02), Guam, USA, 18 20 November 2002. Guam, 2002, pp. 15–20.

17. Xu S. Orderly random testing for both hardware and software. Proceedings of the 2008 14th IEEE Pacific Rim International Symposium on Dependable Computing, Washington, D.C., USA, 15–17 December 2008. Washington, 2008, pp. 160–167.

18. Yarmolik S. V., Yarmolik V. N. The synthesis of probability tests with a small number of kits. Automatic Control and Computer Sciences, 2011, vol. 45, no. 3, pp. 133–141.

19. Mrozek I., Yarmolik V. Optimal controlled random tests. Proceedings of Computer Information Systems and Industrial Management: 16th IFIP TC8 International Conference, CISIM 2017, Bialystok, Poland, 16–18 June 2017. Bialystok, 2017, pp. 27–38.

20. Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147–160.

21. Peterson W. W., Weldon E. J. Error-Correction Codes. Cambridge, Massachusetts, London, England, The MIT Press, 1972, 560 p.

22. Yarmolik V. N., Petrovskaya V. V., Shevchenko N. A. Dissimilarity measures based on the application of Hamming distance to generate controlled probabilistic tests. Informatika [Informatics], 2024, vol. 21, no. 2, pp. 54−72 (In Russ.).

23. Yarmolik S. V., Yarmolik V. N. Controlled random testing. Informatika [Informatics], 2011, vol. 29, no. 1, pp. 79−88 (In Russ.).

24. Plotkin M. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 1960, vol. 6, no. 4, pp. 445–450.

25. Yarmolik V. N., Petrovskaya V. V., Demenkovets D. V., Levantsevich V. A. Controlled random tests with fixed minimal Hamming distance. Informatika [Informatics], 2025, vol. 22, no. 1, pp. 7−26 (In Russ.).

26. MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes. Amsterdam, The Netherland, Elsevier-North-Holland Pub. Co., 1977, 762 p.

27. Hedayat A., Wallis W. D. Hadamard matrices and their applications. Annals of Statistics, 1978, vol. 6, no. 6, pp. 1184–1238.

28. Seberry J., Yamada M. Hadamard Matrices: Constructions using Number Theory and Linear Algebra. Hoboken, NJ, USA, John Wiley & Sons, Inc., 2020, 384 p.

29. Mrozek I., Yarmolik V. Multiple controlled random testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.

30. Yarmolik V. N., Yarmolik S. V. Multiple non-destructive marching tests with variable address sequences. Automation and Remote Control, 2007, vol. 4, pp. 126–137.

31. Cheng K.-L., Tsai M.-F., Wu C. T. Neighborhood pattern-sensitive fault testing and diagnostics for random-access memories. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 11, pp. 284−267.

32. Parvathi M., Hmiasree, T., Bhavyasree T. Novel test methods for NPSF faults in SRAM. Proceedings of the International Conference on Computational and Characterization Techniques in Engineering & Sciences (CCTES), Lucknow, India, 14 15 September 2018. Lucknow, 2018, pp. 112–118.

33. Yarmolik V. N., Levantsevich V. А., Demenkovets D. V., Mrozek I. Construction and application of march tests for pattern sensitive memory faults detection. Informatika [Informatics], 2021, vol. 18, no. 1, pp. 25−42 (In Russ.).