bsuirДоклады БГУИРDoklady BGUIR1729-76482708-0382БГУИР10.35596/1729-7648-2022-20-6-52-60bsuir-3443Research ArticleЭЛЕКТРОНИКА, РАДИОФИЗИКА, РАДИОТЕХНИКА, ИНФОРМАТИКАELECTRONICS, RADIOPHYSICS, RADIOENGINEERING, INFORMATICSМера отличия для управляемых вероятностных тестовDistance Measure for Controlled Random TestsЯрмоликВ. Н.YarmolikV. N.

Ярмолик В.Н., д.т.н., профессор

220013, г. Минск, ул. П. Бровки, 6, тел. +375 29 769-96-77

Dr. of Sci. (Eng.), Professor 

220013, Minsk, P. Brovka St., 6, tel. +375 29 769-96-77

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

Шевченко Н.А., студент

г. Дармштадт

Shauchenka M.A., Student

ПетровскаяВ. В.PetrovskayaV. V.

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

220013, г. Минск, ул. П. Бровки, 6, тел. +375 29 769-96-77

Petrovskaya V.V., M. Sci.

Белорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsДармштадский технический университетDarmstadt Technical University2022031020222065260Copyright © Ярмолик В.Н., Шевченко Н.А., Петровская В.В., 20222022Ярмолик В.Н., Шевченко Н.А., Петровская В.В.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://doklady.bsuir.by/jour/article/view/3443

Исследуется задача построения характеристик различия тестовых последовательностей. Обосновывается ее актуальность для генерирования управляемых вероятностных тестов и сложность нахождения мер отличия для символьных тестов. Показывается ограниченность применения расстояния Хэмминга и Дамерау – Левенштейна для получения меры отличия тестовых наборов. Для произвольного случая определяется новая мера различия двух символьных тестовых наборов на основе интервала, используемого в теории строя цепи последовательных событий. Расстояние D(Ti, Tk) между тестовыми наборами Ti и Tk, использующее характеристику интервала, основано на определении независимых пар одинаковых (тождественных) символов, принадлежащих двум наборам, и вычислении интервалов между ними. Показывается комбинаторный характер вычисления предложенной меры отличия для символьных тестовых наборов произвольного алфавита и размерности. Приводится пример вычисления данной меры и показываются возможные ее модификации и ограничения. Рассматривается применение меры различия для случая многократного тестирования запоминающих устройств на основе адресных последовательностей pA с четным p повторением адресов. Для случая p = 2 приводятся математические соотношения вычисления интервалов и расстояния D(Ti, Tk) для последовательностей адресов 2A, используемых для управляемого вероятностного тестирования запоминающих устройств. Приводятся экспериментальные результаты, подтверждающие эффективность предложенной меры отличия.

The problem of constructing characteristics of the difference between test sequences is investigated. Its relevance for generating controlled random tests and the complexity of finding difference measures for symbolic tests are substantiated. The limitations of using the Hamming and Damerau–Levenshtein distances to obtain a measure of the difference between test patterns are shown. For an arbitrary case, a new measure of the difference between two symbolic test sets is determined based on the interval used in the theory of the chain of successive events. The distance D(Ti, Tk) between test patterns Ti and Tk, using the interval characteristic, is based on determining independent pairs of identical (equal) symbols belonging to two patterns and calculating the intervals between them. The combinatorial nature of the calculation, the proposed difference measure for symbolic test patterns of an arbitrary alphabet and dimension, is shown. An example of calculating this measure is given and its possible modifications and limitations are shown. The application of the measure of difference is considered for the case of multi-run testing of memory devices based on address sequences pA with even p repetition of addresses. For the case p = 2, mathematical relations are given for calculating intervals and distances D(Ti, Tk) for address sequences 2A used for controlled random testing of memory devices. Experimental results are presented confirming the effectiveness of the proposed difference measure.

расстояниерасстояние Хэммингарасстояние Левенштейнатесттестовый наборdistanceHamming distanceLevenshtein distancetesttest patternReferencesHuang R., Sun W., Xu Y., Chen H., Towey D., Xia X. A Survey on Adaptive Random Testing. IEEE Transactions on Software Engineering. 2021;47(10):2052-2083. DOI: 10.1109/tse.2019.2942921.Huang R., Sun W., Xu Y., Chen H., Towey D., Xia X. A Survey on Adaptive Random Testing. IEEE Transactions on Software Engineering. 2021;47(10):2052-2083. DOI: 10.1109/tse.2019.2942921.Yarmolik V.N, Mrozek I., Yarmolik S.V. Controlled Method of Random Test Synthesis. Automatic Control and Computer Sciences. 2015;49(6):395-403.Yarmolik V.N, Mrozek I., Yarmolik S.V. Controlled Method of Random Test Synthesis. Automatic Control and Computer Sciences. 2015;49(6):395-403.Леванцевич В.А., Ярмолик В.Н. Многократное управляемое вероятностное тестирование. Доклады БГУИР. 2019;121(3):65-69.Levantsevich V.A., Yarmolik V.N. [Multiple controlled random testing]. Doklady BGUIR = Doklady BGUIR. 2019;121(3):65-69. (in Russ.)Sadovsky M.G. Comparison of symbol sequences: no editing, no alignment. Open Systems & Information Dynamics. 2002;09(01):19-36. DOI: 10.1023/A:1014278811727.Sadovsky M.G. Comparison of symbol sequences: no editing, no alignment. Open Systems & Information Dynamics. 2002;09(01):19-36. DOI: 10.1023/A:1014278811727.Bard G.V. Spelling-error tolerant, order-independent pass-phrases via the Damerau – Levenshtein string-edit distance metric. Proc. of the Fifth Australasian Symposium on ACSW Frontiers. 2007:117-124.Bard G.V. Spelling-error tolerant, order-independent pass-phrases via the Damerau – Levenshtein string-edit distance metric. Proc. of the Fifth Australasian Symposium on ACSW Frontiers. 2007:117-124.Gumenyuk A.S., Skiba A.A., Pozdnichenko N.N., Shpynov S.N. About Similarity Measures of Components Arrangement of Naturally Ordered Data Arrays. SPIIRAS Proceedings. 2019;18(2):471-503. DOI: 10.15622/sp.18.2.471-503. / Gumenjuk A.S, Skiba A.A., Pozdnichenko N.N., Shpunov S.N. [On the measures of similarity of the arrangement of components in arrays of naturally ordered data]. Proc. SPIIRAS. 2019;18(2):471-503. DOI: 10.15622/sp.18.2.471-503. (In Russ.)Gumenyuk A.S., Skiba A.A., Pozdnichenko N.N., Shpynov S.N. About Similarity Measures of Components Arrangement of Naturally Ordered Data Arrays. SPIIRAS Proceedings. 2019;18(2):471-503. DOI: 10.15622/sp.18.2.471-503. / Gumenjuk A.S, Skiba A.A., Pozdnichenko N.N., Shpunov S.N. [On the measures of similarity of the arrangement of components in arrays of naturally ordered data]. Proc. SPIIRAS. 2019;18(2):471-503. DOI: 10.15622/sp.18.2.471-503. (In Russ.)Mrozek I., Yarmolik V.N. Transparent Memory Tests Based on the Double Address Sequences. Entropy. 2021;23:894. DOI: 10.3390/e23070894.Mrozek I., Yarmolik V.N. Transparent Memory Tests Based on the Double Address Sequences. Entropy. 2021;23:894. DOI: 10.3390/e23070894.

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