informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-321Research ArticleАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯCOMPUTER AIDED DESIGNПСЕВДОИСЧЕРПЫВАЮЩЕЕ ТЕСТИРОВАНИЕ ЗАПОМИНАЮЩИХ УСТРОЙСТВ НА БАЗЕ МНОГОКРАТНЫХ МАРШЕВЫХ ТЕСТОВPSEUDO-EXHAUSTIVE MEMORY DEVICES TESTING BASED ON MULTIPLE MARCH TESTS 1ЯрмоликВ. Н.YarmolikV. N.

доктор технических наук, профессор

D. Sc. (Engineering), Professor

yarmolik10ru@yahoo.comМрозекИ.MrozekI.

доктор, адъюнкт

Ph. D., Lecture

i.mrozek@pb.edu.plЛеванцевичВ. А.LevantsevichB. A.

магистр технических наук, ассистент

Master of Engineering, Assistant

lvn@bsuir.byБелорусский государственный университет информатики и радиоэлектроники, МинскBelarusian State University of Computer Science and Electronic Engineering, MinskБелостокский технический университет, БелостокPolitechnika Białostocka, Białystok201826032018151110121Copyright © Ярмолик В.Н., Мрозек И., Леванцевич В.А., 20182018Ярмолик В.Н., Мрозек И., Леванцевич В.А.Yarmolik V.N., Mrozek I., Levantsevich B.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/321

Анализируются методы тестирования современных запоминающих устройств. Показывается обоснованность применения псевдоисчерпывающих тестов для обнаружения сложных неисправностей памяти. Формулируется необходимое условие генерирования псевдоисчерпывающего теста для заданного количества ячеек запоминающего устройства. Показывается, что задача генерирования псевдоисчерпывающего теста на базе многократных тестов запоминающих устройств с изменяемым начальным состоянием сводится к комбинаторной задаче собирателя купонов. Приводятся оценки средней, минимальной и максимальной кратности многократного теста для обеспечения исчерпывающего множества комбинаций для заданного числа ячеек запоминающего устройства. Экспериментально показывается справедливость аналитических оценок и подтверждается возможность псевдоисчерпывающего тестирования запоминающих устройств.

 

Methods for modern memory devices are analyzed. The validity of using pseudo-exhaustive tests to detect complex memory faults is shown. A necessary condition for generating a pseudo-exhaustive test for a given number of memory cells is formulated. It is shown that the problem of generating a pseudo-exhaustive test based on multiple memory tests with a variable background is reduced to the combinatorial task of the coupon collector. Estimates of the mean, minimum, and maximum multiplicity of a multiple test are given to provide an exhaustive set of combinations for a given number of cells of a memory device. The validity of analytical estimates is shown experimentally and the possibility of pseudo-exhaustive memory testing is confirmed.

маршевые тестыпсевдоисчерпывющие тестызадача собирателя купоновmarch testspseudo-exhaustive testscoupon collector problemReferencesBarzilai, Z. Exhaustive Generation of Bit Pattern with Application to VLSI Self-Testing / Z. Barzilai, D. Coppersmith, A. Rozenberg // IEEE Transactions on Computers. – 1983. – Vol. C–31, no. 2. – P. 190–194.Barzilai, Z. Exhaustive Generation of Bit Pattern with Application to VLSI Self-Testing / Z. Barzilai, D. Coppersmith, A. Rozenberg // IEEE Transactions on Computers. – 1983. – Vol. C–31, no. 2. – P. 190–194.Das, D. Exhaustive and Near-Exhaustive Memory Testing Techniques and their BIST Implementations / D. Das, M. G. Karpovsky // Journal of Electronic Testing. − 1997. – Vol. 10. − P. 215−229.Das, D. Exhaustive and Near-Exhaustive Memory Testing Techniques and their BIST Implementations / D. Das, M. G. Karpovsky // Journal of Electronic Testing. − 1997. – Vol. 10. − P. 215−229.Ярмолик, В. Н. Псевдоисчерпывающее тестирование ОЗУ / В. Н. Ярмолик, И. Мрозек, В. А. Леванцевич // Информатика. – 2017. – № 2(54). – С. 58–69.Ярмолик, В. Н. Псевдоисчерпывающее тестирование ОЗУ / В. Н. Ярмолик, И. Мрозек, В. А. Леванцевич // Информатика. – 2017. – № 2(54). – С. 58–69.Ярмолик, С. В. Итеративные почти псевдоисчерпывающие вероятностные тесты / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2010. – № 2(26). − С. 66−75.Ярмолик, С. В. Итеративные почти псевдоисчерпывающие вероятностные тесты / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2010. – № 2(26). − С. 66−75.Mrozek, I. Method for Generation Multiple Controlled Random Tests / I. Mrozek, V. Yarmolik // Proc. of the Computer Information Systems and Industrial Management (CISIM 2016), 14–16 September 2016. – Vilnius, Lithuania, 2016. – P. 429–440.Mrozek, I. Method for Generation Multiple Controlled Random Tests / I. Mrozek, V. Yarmolik // Proc. of the Computer Information Systems and Industrial Management (CISIM 2016), 14–16 September 2016. – Vilnius, Lithuania, 2016. – P. 429–440.Mrozek, I. Iterative Antirandom Testing / I. Mrozek, V. Yarmolik // Journal of Electronic Testing: Theory and Applications (JETTA). – 2012. – Vol. 9, no. 3. – P. 251–266.Mrozek, I. Iterative Antirandom Testing / I. Mrozek, V. Yarmolik // Journal of Electronic Testing: Theory and Applications (JETTA). – 2012. – Vol. 9, no. 3. – P. 251–266.Yarmolik, S. V. The Syntheses of Probability Tests with a Small Number of Kits / S. V. Yarmolik, V. N. Yarmolik // Automatic Control and Computer Science. – 2011. − Vol. 45, no. 3. − P. 133−141.Yarmolik, S. V. The Syntheses of Probability Tests with a Small Number of Kits / S. V. Yarmolik, V. N. Yarmolik // Automatic Control and Computer Science. – 2011. − Vol. 45, no. 3. − P. 133−141.Yarmolik, V. N. Address Sequences for Multiple Run March Tests / V. N. Yarmolik, S. V. Yarmolik // Automatic Control and Computer Sciences. – 2006. – No. 5. – С. 59–68.Yarmolik, V. N. Address Sequences for Multiple Run March Tests / V. N. Yarmolik, S. V. Yarmolik // Automatic Control and Computer Sciences. – 2006. – No. 5. – С. 59–68.Mrozek, I. Antirandom Test Vectors for Bist in Hardware/Software Systems / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2012. – No. 119. – P. 1–23.Mrozek, I. Antirandom Test Vectors for Bist in Hardware/Software Systems / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2012. – No. 119. – P. 1–23.Ярмолик, C. В. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / С. В. Ярмолик, В. Н. Ярмолик // Автоматика и телемеханика. – 2007. – № 4. – С. 126–137.Ярмолик, C. В. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / С. В. Ярмолик, В. Н. Ярмолик // Автоматика и телемеханика. – 2007. – № 4. – С. 126–137.Goor, A. J. Testing Semiconductor Memories, Theory and Practice / A. J. Goor. – Chichester, UK : John Wiley & Sons, 1991. – 536 p.Goor, A. J. Testing Semiconductor Memories, Theory and Practice / A. J. Goor. – Chichester, UK : John Wiley & Sons, 1991. – 536 p.Niggemeyer, D. Integration of Non-classical Faults in Standard March Tests / D. Niggemeyer, M. Redeker, J. Otterstedt // Records of the IEEE Intern. Workshop on Memory Technology, Design and Testing, 24–25 August 1998. – Washington, DC, USA, 1998. – P. 91–98.Niggemeyer, D. Integration of Non-classical Faults in Standard March Tests / D. Niggemeyer, M. Redeker, J. Otterstedt // Records of the IEEE Intern. Workshop on Memory Technology, Design and Testing, 24–25 August 1998. – Washington, DC, USA, 1998. – P. 91–98.Mrozek, I. Optimal Backgrounds Selection for Multi Run Memory Testing / I. Mrozek, V. N. Yarmolik // Proc. of the 11th IEEE Workshop on Design and Diagnostic Circuits and Systems (DDECS 2008). – Bratislava, Slovakia, 2008. – P. 1–7.Mrozek, I. Optimal Backgrounds Selection for Multi Run Memory Testing / I. Mrozek, V. N. Yarmolik // Proc. of the 11th IEEE Workshop on Design and Diagnostic Circuits and Systems (DDECS 2008). – Bratislava, Slovakia, 2008. – P. 1–7.Karpovsky, M. G. Transparent Random Access Memory Testing for Pattern Sensitive Faults / M. G. Karpovsky, V. N. Yarmolik // J. Electron. Testing: Theory and Applications (JETTA). – 1994. – Vol. 5, no. 1. – P. 91–113.Karpovsky, M. G. Transparent Random Access Memory Testing for Pattern Sensitive Faults / M. G. Karpovsky, V. N. Yarmolik // J. Electron. Testing: Theory and Applications (JETTA). – 1994. – Vol. 5, no. 1. – P. 91–113.Karpovsky, M. G. Transparent Memory Testing for Pattern Sensitive Faults / M. G. Karpovsky, V. N. Yarmolik // Proc. Intern. Test Conf. IEEE Publisher. – Washington, DC, USA, 1994. – P. 860–869.Karpovsky, M. G. Transparent Memory Testing for Pattern Sensitive Faults / M. G. Karpovsky, V. N. Yarmolik // Proc. Intern. Test Conf. IEEE Publisher. – Washington, DC, USA, 1994. – P. 860–869.Flajolet, P. Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search / P. Flajolet, D. Gardy, L. Thimonier // Discrete Appl. Math. – 1992. – No. 39. – P. 207–229.Flajolet, P. Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search / P. Flajolet, D. Gardy, L. Thimonier // Discrete Appl. Math. – 1992. – No. 39. – P. 207–229.

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