informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2025-22-2-63-80inform-1322Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМасштабирование управляемых вероятностных тестов с применением матриц АдамараScaling controlled random tests based on Hadamard matricesЯрмоликВ. Н.YarmolikV. N.

Ярмолик Вячеслав Николаевич, доктор технических наук, профессор

ул. П. Бровки, 6, Минск, 220013

Vyacheslav N. Yarmolik, D. Sc. (Eng.), Prof.

st. P. Brovki, 6, Minsk, 220013

yarmolik10ru@yahoo.comШевченкоН. А.ShauchenkaM. A.

Шевченко Николай Алексеевич, студент

Каролиненплац, 5, Дармштадт, 64289

Mikalai A. Shauchenka, Student

Karolinenplatz, 5, Darmstadt, 64289

nik.sh.de@gmail.comПетровскаяВ. В.PetrovskayaV. V.

Петровская Вита Владленовна, магистр технических наук

ул. П. Бровки, 6, Минск, 220013

Vita V. Petrovskaya, M. Sc. (Eng.)

st. P. Brovki, 6, Minsk, 220013

vita.petrovskaya@gmail.comБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsДармштадтский технический университетTechnical University of Darmstadt2025100720252226380Copyright © Ярмолик В.Н., Шевченко Н.А., Петровская В.В., 20252025Ярмолик В.Н., Шевченко Н.А., Петровская В.В.Yarmolik V.N., Shauchenka M.A., Petrovskaya V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1322

Цели. Решается задача двухмерного масштабирования управляемых вероятностных тестов небольшого размера, задающих исходные шаблоны, с помощью матриц Адамара. Показывается ограниченность применения классических подходов генерирования тестов, основанных на перечислении кандидатов в тестовые наборы. С повышением пороговых значений мер различия двоичных тестовых наборов увеличивается вычислительная сложность построения таких тестов. Главной целью настоящей статьи является развитие методов построения тестов на базе исходных шаблонов путем их расширения до требуемой разрядности на основании применения формальных правил.Методы. Для двухмерного масштабирования исходных шаблонов с заданными пороговыми значениями расстояния Хэмминга применяются матрицы Адамара и рекурсивная процедура Сильвестра для их построения. При проведении экспериментальных исследований использовался метод статистических испытаний.Результаты. Показано, что методы построения управляемых вероятностных тестов, основанные на использовании шаблонов, можно рассматривать как процедуру масштабирования управляемых вероятностных тестов до требуемой их разрядности. Для построения искомых тестов используются как шаблоны, характеризующиеся минимальной разрядностью наборов, так и любые управляемые вероятностные тесты. Сама процедура характеризуется как одномерное масштабирование, которое увеличивает разрядность тестовых наборов, но сохраняет их количество. С целью одновременного увеличения разрядности наборов и их количества предлагается метод, основанный на двухмерном масштабировании шаблонов с применением матриц Адамара. Это позволяет строить управляемые вероятностные тесты без трудоемкой процедуры перечисления кандидатов в тестовые наборы и вычисления для них значений меры (мер) различия. Показано, что уникальное свойство ортогональности матриц Адамара с ростом их порядка позволяет достигать отношений среднего значения расстояния Хэмминга между тестовыми наборами к их разрядности, близких к 1/2. Отмечено, что характеристики исходных шаблонов несущественно влияют на характеристики результирующих тестов, построенных с применением матриц Адамара, которые получены на основании рекурсивной процедуры Сильвестра. Работоспособность и эффективность предложенного подхода к построению управляемых вероятностных тестов оценены для случая тестирования запоминающих устройств. Показано, что управляемые вероятностные тесты, построенные с применением матриц Адамара, имеют заметно большую покрывающую способность по сравнению с вероятностными тестами.Заключение. Рассмотрен метод генерирования тестовых наборов при формировании управляемых вероятностных тестов с использованием матриц Адамара. Основой предложенного метода является двухмерное масштабирование исходных шаблонов с применением указанных матриц. Показано, что использование различных шаблонов и их двухмерное масштабирование позволяют строить управляемые вероятностные тесты с требуемой разрядностью тестовых наборов и большим их количеством

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

управляемые вероятностные тестыдвоичный тестовый набормера различия символьных набороврасстояние Хэммингаматрицы Адамарапроцедура Сильвестраtechnical diagnosticscontrolled random testsbinary test patternmeasure of difference of symbol setsHamming distanceHadamard matricesSylvester procedureReferencesAn orchestrated survey on automated software test case generation / S. Anand, E. Burke, T. Chen [et al.] // Journal of Systems and Software. – 2014. – Vol. C-39, no. 4. – P. 582–586.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.Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бестпринт, 2019. – 387 с.Yarmolik V. . Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).Karmore, S. P. Testing of embedded system, an issues and challenges / S. P. Karmore, A. R. Mahajan // International Journal of Enhanced Research in Science, Technology & Engineering. – 2015. – Vol. 4, no. 8. – P. 181–186.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.Krupp, A. A Systematic approach to the test of combined HW/SW systems / A. Krupp, W. Muller // Proc. of IEEE Conf. on the Testing and Automation of Embedded Systems (DATE 2010), Dresden, Germany, 8–12 Mar. 2010. – Dresden, Germany, 2010. – P. 323–326.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.Malaiya, Y. K. The coverage problem for random testing / Y. K. Malaiya, S. Yang // Proc. of the Intern. Test Conf., Philadelphia, PA, USA, 16–18 Oct. 1984. – Philadelphia, 1984. – P. 237–242.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.Arcuri, A. Random testing: Theoretical results and practical implications / A. Arcuri, M. Z. Iqbal, L. Briand // IEEE Transactions on Software Engineering. – 2011. – Vol. 38, no. 2. – P. 258–277.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.Garousi, V. Testing embedded software: A survey of the literature / V. Garousi, M. elderer, C. M. Karapıçak, U. Yılmaz // Information and Software Technology. – 2018. – Vol. 104. – P. 14–45.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.Saini, D. K. Software testing for embedded systems / D. K. Saini // International Journal of Computer Applications. – 2012. – Vol. 43, no. 17. – P. 1–6.Saini D. K. Software testing for embedded systems. International Journal of Computer Applications, 2012, vol. 43, no. 17, pp. 1–6.Karmore, S. P. Universal methodology for embedded system testing / S. P. Karmore, A. R. Mahajan // Proc. of the 8th Intern. Conf. on Computer Science & Education (ICCSE 2013), Colombo, Sri Lanka, 26–28 Apr. 2013. – Colombo, 2013. – P. 567–572.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.A survey on adaptive random testing / R. Huang, W. Sun, Y. Xu [et al.] // IEEE Transactions on Software Engineering. – 2021. – Vol. 47, no. 10. – P. 2052–2083.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.Chen, T. Y. Adaptive random testing: The art of test case diversity / T. Y. Chen, F. C. Kuo, R. G. Merkel, T. H. Tse // Journal of Systems and Software. – 2010. – Vol. 83. – P. 60–66.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.Yarmolik, S. V. Controlled random tests / S. V. Yarmolik, V. N. Yarmolik // Automation and Remote Control. – 2012. – Vol. 73, no. 10. – P. 1704–1714.Yarmolik S. V., Yarmolik V. N. Controlled random tests. Automation and Remote Control, 2012, vol. 73, no. 10, pp. 1704–1714.Mrozek, I. Antirandom test vectors for BIST in hardware/software systems / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2012. – Vol. 119, no. 2. – P. 163–185.Mrozek I., Yarmolik V. Antirandom test vectors for BIST in hardware/software systems. Fundamenta Informaticae, 2012, vol. 119, no. 2, pp. 163–185.Alamgir, A. Adaptive random testing with total Cartesian distance for black box circuit under test / A. Alamgir // Indonesian Journal of Electrical Engineering and Computer Science. – 2020. – Vol. 20, no. 2. – P. 720–726.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.Wu, S. H. Antirandom testing: A distance-based approach / S. H. Wu, S. Jandhyala, Y. K. Malaiya, A. P. Jayasumana // Hindawi Publishing Corporation VLSI Design. – 2008. – Vol. 2008, Article ID 165709. – 9 p. – DOI: 10.1155/2008/165709.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.Xu, S. Maximum distance testing / S. Xu, J. Chen // Proc. of the 11th IEEE Asian Test Symp. (ATS’02), Guam, USA, 18–20 Nov. 2002. – Guam, 2002. – P. 15–20.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.Xu, S. Orderly random testing for both hardware and software / S. Xu // Proc. of the 2008 14th IEEE Pacific Rim Intern. Symp. on Dependable Computing, Washington, D.C., USA, 15–17 Dec. 2008. – Washington, 2008. – P. 160–167.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.Yarmolik, S. V. The synthesis of probability tests with a small number of kits / S. V. Yarmolik, V. N. Yarmolik // Automatic Control and Computer Sciences. – 2011. – Vol. 45, no. 3. – P. 133–141.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.Mrozek, I. Optimal controlled random tests / I. Mrozek, V. Yarmolik // Proc. of Computer Information Systems and Industrial Management: 16th IFIP TC8 Intern. Conf., CISIM 2017, Bialystok, Poland, 16–18 June 2017. – Bialystok, 2017. – P. 27–38.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.Hamming, R. W. Error detecting and error correcting codes / R. W. Hamming // The Bell System Technical Journal. – 1950. – Vol. 29, no. 2. – P. 147–160.Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147–160.Peterson, W. W. Error-Correction Codes / W. W. Peterson, E. J. Weldon. – Cambridge, Massachusetts, London England : The MIT Press, 1972. – 560 p.Peterson W. W., Weldon E. J. Error-Correction Codes. Cambridge, Massachusetts, London, England, The MIT Press, 1972, 560 p.Ярмолик, В. Н. Модификации способов определения расстояния Хэмминга для их применения в качестве мер различия при генерировании управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, Н. А. Шевченко // Информатика. – 2024. − Т. 21, № 2. – С. 54–72.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.).Ярмолик, С. В. Управляемое случайное тестирование / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2011. − Т. 29, № 1. – С. 79–88.Yarmolik S. V., Yarmolik V. N. Controlled random testing. Informatika [Informatics], 2011, vol. 29, no. 1, pp. 79−88 (In Russ.).Plotkin, M. Binary codes with specified minimum distance / M. Plotkin // IRE Transactions on Information Theory. – 1960. – Vol. 6, no. 4. – P. 445–450.Plotkin M. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 1960, vol. 6, no. 4, pp. 445–450.Управляемые вероятностные тесты с фиксированным минимальным значением расстояния Хэмминга / В. Н. Ярмолик, В. В. Петровская, Д. В. Деменковец, В. А. Леванцевич // Информатика. – 2025. − Т. 22, № 1. – С. 7–26.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.).MacWilliams, F. J. The Theory of Error-Correcting Codes / F. J. MacWilliams, N. J. A. Sloane. – Amsterdam, The Netherland : Elsevier-North-Holland Pub. Co., 1977. – 762 p.MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes. Amsterdam, The Netherland, Elsevier-North-Holland Pub. Co., 1977, 762 p.Hedayat, A. Hadamard matrices and their applications / A. Hedayat, W. D. Wallis // Annals of Statistics. – 1978. – Vol. 6, no. 6. – P. 1184–1238.Hedayat A., Wallis W. D. Hadamard matrices and their applications. Annals of Statistics, 1978, vol. 6, no. 6, pp. 1184–1238.Seberry, J. Hadamard matrices: Constructions using number theory and linear algebra / J. Seberry, M. Yamada. – Hoboken, NJ, USA : John Wiley & Sons, Inc., 2020. – 384 p.Seberry J., Yamada M. Hadamard Matrices: Constructions using Number Theory and Linear Algebra. Hoboken, NJ, USA, John Wiley & Sons, Inc., 2020, 384 p.Mrozek, I. Multiple controlled random testing / I. Mrozek, V. Yarmolik // Fundamenta Informaticae. – 2016. – Vol. 144, no. 1. – P. 23–43.Mrozek I., Yarmolik V. Multiple controlled random testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.Ярмолик, В. Н. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / В. Н. Ярмолик, С. В. Ярмолик // Автоматика и телемеханика. – 2007. – Вып. 4. – С. 126–137.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.Cheng, K.-L. Neighborhood pattern-sensitive fault testing and diagnostics for random-access memories / K.-L. Cheng, M.-F. Tsai, C. T. Wu // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 11. – P. 284–267.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.Parvathi, M. Novel test methods for NPSF faults in SRAM / M. Parvathi, T. Hmiasree, T. Bhavyasree // Proc. of Intern. Conf. on Computational and Characterization Techniques in Engineering & Sciences (CCTES), Lucknow, India, 14–15 Sept. 2018. – Lucknow, 2018. – P. 112–118.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.Ярмолик, В. Н. Построение и применение маршевых тестов для обнаружения кодочувствительных неисправностей запоминающих устройств / В. Н. Ярмолик, В. А. Леванцевич, Д. В. Деменковец, И. Мрозек // Информатика. – 2021. − Т. 18, № 1. – С. 25–42.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.).

The authors declare that there are no conflicts of interest present.