ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» №2, 2009

Сложность проверяющих тестов для бесповторных булевых функций

Автор(ы)
Л. В. Рябец

Аннотация

В работе рассматривается вопрос сложности проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций, существенно зависящих от своих переменных. Известно, что большинство неисправностей в схемах функциональных элементов, реализующих бесповторные булевы функции, приводит к новой схеме, реализующей также бесповторную функцию. Построение проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций осуществляется на основе квадратов существенности. В работе получено точное значение функции Шеннона для тестов относительно бесповторной альтернативы в базисе {¬, ∨, &, ⊕}. Также представлен алгоритм получения проверяющего теста для любой бесповторной булевой функции, имеющий сложность 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.