Сложность проверяющих тестов для бесповторных булевых функций
| Авторы: | Л. В. Рябец |
| Аннотация: | В работе рассматривается вопрос сложности проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций, существенно зависящих от своих переменных. Известно, что большинство неисправностей в схемах функциональных элементов, реализующих бесповторные булевы функции, приводит к новой схеме, реализующей также бесповторную функцию. Построение проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций осуществляется на основе квадратов существенности. В работе получено точное значение функции Шеннона для тестов относительно бесповторной альтернативы в базисе {¬, ∨, &, ⊕}. Также представлен алгоритм получения проверяющего теста для любой бесповторной булевой функции, имеющий сложность O(n3). |
| Ключевые слова: | бесповторные булевы функции, тестирование схем, проверяющие тесты, тесты относительно бесповторной альтернативы |
| УДК: | 519.7 |
| Литература: |
1. ВороненкоА.A. Опроверяющихтестахдлябесповторныхфункций/ А.A. Вороненко // Математические вопросы кибернетики. — 2002. — Вып 11. — С. 163–176. 2. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1, &, ∨, ¬} /А.А. Вороненко// Дискретнаяматематика. —2005. — Том 17. Выпуск 2. — С. 139–143. 3. Избранные вопросы теории булевых функций: Монография / А. С. Балюк,С. Ф. Винокуров, А. И. Гайдуков и др.; Под ред. С. Ф. Винокурова, Н. А. Перязева. — М.: Физматлит, 2001. — 192 с. 4. Редькин Н. П. Надежностьидиагностикасхем/ Н. П.Редькин. — М.: Изд-во Моск. ун-та, 1992. — 192 с. 5. Рябец Л. В. Тестирование бесповторных булевых функций / А. С. Балюк, Л. В. Рябец // Вестник Томского государственного университета. Приложение.— 2006. — Вып 17. — С. 10–14. |