О единичных проверяющих тестах относительно замен элементов на инверторы

Г.Г. Темербекова, Д.С. Романов

Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.359-366

Для цитирования: Темербекова Г.Г., Романов Д.С. О единичных проверяющих тестах относительно замен элементов на инверторы // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 359–366. – doi: 10.26907/2541-7746.2020.3.359-366.

For citation: Temerbekova G.G., Romanov D.S. On single detection test sets under replacements of gates with inverters. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 359–366. doi: 10.26907/2541-7746.2020.3.359-366. (In Russian)

Аннотация

В статье рассмотрены вопросы проверяющего тестирования булевых функций, реализуемых схемами из функциональных элементов (СФЭ), на которые действует источник одиночных неисправностей, вызывающий замены функциональных элементов на инверторы. Актуальность исследования определена тем, что замены функциональных элементов на инверторы представляют собой тип неисправности, встречающийся при разработке и производстве СБИС. Исследование проведено с целью доказать возможность построения легкотестируемых схем относительно замен элементов на инверторы. Для достижения поставленной цели разработаны специальные методы синтеза легкотестируемых схем. На основе результатов исследования сделаны следующие выводы. Для произвольной булевой функции, реализуемой с помощью СФЭ над базисом Жегалкина, найдется схема, допускающая единичный проверяющий тест из одного набора. Для произвольной булевой функции, реализуемой с помощью СФЭ над стандартным базисом, найдется схема, допускающая единичный проверяющий тест из двух наборов.

Ключевые слова: схема из функциональных элементов, проверяющий тест, функция Шеннона, замены элементов

Благодарности. Работа выполнена при финансовой поддержке Московского центра фундаментальной и прикладной математики (проект «Оценки сложностных характеристик булевых функций и графов»), РФФИ (проект № 18-01-00800-а) и госбюджетной темы НИР № 5.4.19 факультета ВМК МГУ.

Литература

1. Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отд. фак. ВМиК МГУ, 2004. – 253 с.
2. Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. – 2008. – № 1. – С. 40–44.

Поступила в редакцию 20.07.2020

Темербекова Гульгайша Габдуловна, аспирант факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

E-mail: gulgaisha93@mail.ru

Романов Дмитрий Сергеевич, доктор физико-математических наук, доцент факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

E-mail: romanov@cs.msu.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.