Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Препринт ИПМ № 197, Москва, 2018 г.
Авторы: Попков К.А.
Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов
Аннотация:
Установлено, что почти любую булеву функцию от n переменных можно реализовать схемой из функциональных элементов в базисе {x&y,x∨y,x⊕y,1}, допускающей полный проверяющий тест длины не более 4 относительно произвольных константных неисправностей на выходах элементов. Доказаны также следующие утверждения: любую булеву функцию от n переменных можно реализовать схемой из функциональных элементов в базисе {x&y,x∨y,x⊕y,1} (в базисе {x&y,x∨y,x∨y¯,x⊕y}), содержащей не более одной фиктивной входной переменной и допускающей полный проверяющий тест длины не более 5 (соответственно, не более 4) относительно неисправностей такого же типа.
Ключевые слова:
схема из функциональных элементов, произвольная константная неисправность, полный проверяющий тест
Язык публикации: русский, страниц: 24
Направление исследований:
Математическое моделирование в актуальных проблемах науки и техники
Полный текст: Сведения об авторах:
  • Попков Кирилл Андреевич,  ,  ИПМ им. М.В. Келдыша РАН