Поволжский регион УДК 519.718 Д. С. Романов МЕТОД СИНТЕЗА НЕИЗБЫТОЧНЫХ СХЕМ В БАЗИСЕ ЖЕГАЛКИНА, ДОПУСКАЮЩИХ ЕДИНИЧНЫЕ ДИАГНОСТИЧЕСКИЕ ТЕСТЫ ДЛИНЫ ОДИН1 Аннотация. <...> Тестирование схем из функциональных элементов – важная теоретическая задача, имеющая практические приложения к тестированию и верификации СБИС. <...> Целью данной работы является демонстрация возможности построения для произвольной булевой функции схемы из функциональных элементов, реализующей эту функцию и допускающей короткий единичный диагностический тест при инверсных неисправностях на выходах элементов. <...> При получении основных результатов использовались методы синтеза схем, основанных на разложении булевой функции в полином Жегалкина. <...> Устанавливается, что для произвольной булевой функции f, зависящей от n переменных, существует неизбыточная реализующая функцию f схема из функциональных элементов в базисе {x&y, x⊕y, 1}, допускающая единичный диагностический тест длины 1 при инверсных неисправностях на выходах элементов. <...> Ключевые слова: схема из функциональных элементов, диагностический тест, инверсная неисправность на выходе элемента, функция Шеннона, легкотестируемая схема. <...> Математика Схемы из функциональных элементов (СФЭ) – одна из классических моделей управляющих систем без памяти. <...> Анализ функционирования СФЭ при возникновении в них неисправностей традиционно осуществляется с помощью тестового подхода, предложенного в работах С. В. Яблонского и И. А. Чегис [1, 2] в середине 1950-х гг. <...> В рамках этого подхода предполагается, что на схему S с входами 1x , 2x …, или систему булевых функций 12f xx … x,, ,(), действует источник неисправ, nx , реализующую булеву функцию n ностей U , способный преобразовать схему S к одной из СФЭ (с такими же входами и выходами, что и у S ) некоторого заранее известного списка H конечной длины, содержащего и исходную схему. <...> Исследование схемы заключается в подаче на входы схемы входных наборов и в изучении выходных <...>