Метод синтеза неизбыточных схем в базисе Жегалкина, допускающих единичные диагностические тесты длины один

Актуальность и цели. Тестирование схем из функциональных элементов - важная теоретическая задача, имеющая практические приложения к тестированию и верификации СБИС. Целью данной работы является демонстрация возможности построения для произвольной булевой функции схемы из функциональных элементов, реализующей эту функцию и допускающей короткий единичный диагностический тест при инверсных неисправностях на выходах элементов. Материалы и методы. При получении основных результатов использовались методы синтеза схем, основанных на разложении булевой функции в полином Жегалкина. Результаты. Устанавливается, что для произвольной булевой функции $f$, зависящей от n переменных, существует неизбыточная реализующая функцию $f$ схема из функциональных элементов в базисе $\{x \& y, x \oplus y, 1\}$, допускающая единичный диагностический тест длины 1 при инверсных неисправностях на выходах элементов.