Поступила в редакцию 27.06.2011 УДК 519.718 МЕТОД СИНТЕЗА ЛЕГКОТЕСТИРУЕМЫХ СХЕМ В ОДНОМ БАЗИСЕ, ДОПУСКАЮЩИХ ЕДИНИЧНЫЕ ПРОВЕРЯЮЩИЕ ТЕСТЫ КОНСТАНТНОЙ ДЛИНЫ Д. С. <...> Романов1 функции и допускающих единичные проверяющие тесты длины не более 4 при инверсных и произвольных константных неисправностях на выходах элементов. <...> В работе предлагается метод синтеза неизбыточных схем из функциональных элементов в базисе {x&y,x ⊕ y, 1, ¯ ная неисправность на выходе элемента, инверсная неисправность на выходе элемента, функция Шеннона, легкотестируемая схема. admitting a fault detection test set whose power does not exceed 4 under arbitrary single inverse or constant (stuck-at) faults at outputs of gates. <...> Пусть f(˜ xn) — произвольная булева функция, формально зависящая от переменных x1,x2,. ,xn, а S — схема из функциональных элементов в некотором базисе B, реализующая функцию f (все определения, не введенные в данной статье, можно найти в монографии [1]). <...> №2 25 источник одиночных неисправностей U, вызывающий инверсные или константные неисправности на выходах функциональных элементов, т.е. на выходе любого не более чем одного функционального элемента схемы вместо реализуемой на его выходе функции от его входов может реализовываться либо отрицание этой функции (случай инверсной неисправности), либо произвольная булева константа (случай константной неисправности). <...> При этом мы для простоты будем считать, что источник неисправностей U не может вызывать неисправность типа “константа σ” у функциональных элементов типа “константа σ”, а также константную неисправность выходного элемента схемы S, тождественно равную реализуемой схемой S функции (если таковой функцией является константа). <...> Обозначим через W(S) множество всех попарно неравных функций, каждая из которых может быть реализована схемой S после поломки элементов, вызванной действием на схему источника неисправностей U.Схема S называется неизбыточной (см., например, [1]) тогда и только тогда, когда для любой функции g(˜ α). <...> (Понятие единичного <...>