О единичных диагностических тестах для схем из функциональных элементов в базисе Жегалкина

Актуальность и цели. Рассматривается задача синтеза неизбыточных схем из функциональных элементов в базисе $\{\&, \oplus, 1, 0\}$, реализующих булевы функции от n переменных и допускающих короткие единичные диагностические тесты относительно константных неисправностей типа 0 на выходах элементов. Эта задача относится к проблеме синтеза легкотестируемых схем, поставленной С. В. Яблонским и И. А. Чегис в 50-х гг. прошлого века, и к настоящему времени достаточно хорошо изучена. Материалы и методы. При построении легкотестируемых схем используется ранее известный метод синтеза, модифицированный под данную задачу. Нижние оценки длин тестов доказываются «от противного», путем получения ограничений на структуру схем, допускающих короткие тесты. Результаты. Для каждой булевой функции найдено минимально возможное значение длины единичного диагностического теста в базисе $\{\&, \oplus, 1, 0\}$ при указанных неисправностях. В частности, доказано, что оно не превосходит двух. Выводы. Рассмотренная задача решена полностью. В частности, существенно улучшены имевшиеся ранее верхние оценки минимальных длин единичных диагностических тестов в этой постановке задачи.