Том 22, номер 5, 2015 г., Стр. 52-70
УДК 519.718.7
Попков К. А.
Оценки длин тестов для функциональных элементов при большом числе допустимых неисправностей
Аннотация:
Рассматриваются задачи проверки исправности и диагностики состояний N функциональных элементов, реализующих в исправном состоянии заданную булеву функцию f (x1, … , xn), путём составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах функциональных элементов; при этом предполагается, что не более k элементов неисправны, где k — заданное натуральное число, не превосходящее N. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех элементов. Получена нижняя оценка на число указанных схем в случае, когда k близко к N. В качестве следствия из этой оценки установлено, что при выполнении некоторого условия на N и принадлежности k некоторому отрезку число таких схем не может быть меньше ck, где c > 1 — константа, не зависящая от выбора числа k из этого отрезка.
Библиогр. 15.
Ключевые слова: функциональный элемент, неисправность, схема, проверяющий тест, диагностический тест.
DOI: 10.17377/daio.2015.22.476
Попков Кирилл Андреевич 1
1. Московский гос. университет им. М. В. Ломоносова
Ленинские горы, 1, 119991 Москва, Россия
e-mail: kirill-formulist@mail.ru
Статья поступила 13 февраля 2015 г.
Исправленный вариант — 22 июля 2015 г.
Литература
[1] Беккенбах Э., Беллман Р. Введение в неравенства. М.: Мир, 1965. 168 c.
[2] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 139 c.
[3] Попков К. А. Оценки длин проверяющих и диагностических тестов для функциональных элементов // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 6. С. 73–89.
[4] Попков К. А. Проверяющие и диагностические тесты для конъюнкторов, дизъюнкторов и инверторов // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2014. № 6. С. 40–44.
[5] Попков К. А. Проверяющие и диагностические тесты для функциональных элементов // Дискрет. математика. 2014. Т. 26, вып. 2. С. 83–99.
[6] Попков К. А. О единичных тестах для функциональных элементов // Дискрет. математика. 2015. Т. 27, вып. 2. С. 73–93.
[7] Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 1986. № 1. С. 72–74.
[8] Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Мат. вопросы кибернетики. 1989. Вып. 2. С. 198–222.
[9] Редькин Н. П. Надёжность и диагностика схем. М.: Изд-во МГУ, 1992. 191 c.
[10] Романов Д. С. О синтезе схем, допускающих полные проверяющие тесты константной длины относительно произвольных константных неисправностей на выходах элементов // Дискрет. математика. 2013. Т. 25, вып. 2. С. 104–120.
[11] Романов Д. С. Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины // Дискрет. математика. 2014. Т. 26, вып. 2. С. 100–130.
[12] Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем // Тр. МИАН. 1958. Т. 51. С. 270–360.
[13] Яблонский С. В. Надежность и контроль управляющих систем // Материалы Всесоюз. семинара по дискрет. математике и еЁе прил. М.: Изд-во МГУ. 1986. С. 7–12.
[14] Яблонский С. В. Некоторые вопросы надежности и контроля управляющих систем // Мат. вопросы кибернетики. 1988. Вып. 1. С. 5–25.
[15] Reddy S. M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. Vol. 21, No. 1. P. 124–141.
