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

Актуальность и цели. Тестирование дискретных моделей схем переключательного типа - это важная теоретическая задача, имеющая практические приложения к тестированию и верификации сверхбольших интегральных схем. В качестве класса управляющих систем в основном рассматривается класс так называемых обобщенных итеративных контактных схем, содержащий внутри себя классические контактные схемы, но допускающий использование суперпозиций. Целью данной работы является демонстрация возможности построения (для произвольной, отличной от константы булевой функции), допускающей короткий единичный проверяющий тест схемы, реализующей или моделирующей эту функцию (в последнем случае схема реализует функцию после подстановки вместо некоторых входных переменных констант). Материалы и методы. При получении основных результатов использовались методы синтеза схем, основанных на разложении булевой функции в полином Жегалкина. Результаты. Устанавливается, что для произвольной, отличной от константы булевой функции $f$, зависящей от $n$ переменных, существуют тестопригодные реализующие функцию $f$ обобщенные итеративные контактные схемы, допускающие: а) единичный проверяющий тест замыкания (размыкания) длины $O(1)$; б) единичный проверяющий тест длины $O(n)$, а также имеются тестопригодные моделирующие функцию f обобщенная итеративная контактная схема и контактная схема, допускающие единичные проверяющие тесты длин $O(1)$.