Главная Информатика
Генерирование тестов для цифровых схем методом булевой производной
|
Генерирование тестов для цифровых схем методом булевой производнойГенерирование тестов для цифровых схем методом булевой производной Булевой производной функции f(x) = f(x1, x2,..., xn) по xi называется функция df(x) / dxi = f(x1, x2,..., xi,..., xn) Е f(x1, x2,...,,..., xn), где Е - сумма по модулю 2. Булева производная может быть также вычислена и по следующей формуле: df(x) / dxi = f(x1, x2,..., 0,..., xn) Е f(x1, x2,..., 1,..., xn). Булева производная определяет значения логических переменных x1,..., xn (кроме xi), при которых изменение состояния xi приводит к изменению значения функции f(x). Тест для неисправности xi = 0 (хi = 1) определяют значения логических переменных, при которых xi Ч df(x) / dxi = 1 (`xi Ч df(x) / dxi =1). Сказанное можно распространить и на внутренние переменные. Тест для неисправностей z =0 (z =1) внутренней линии схемы определяют значения логических переменных, при которых zЧ df(x) / dz =1 ( Ч df(x) / dz = 1). Таким образом, входное воздействие для проверки неисправности в точке z определяется следующим образом.
Приведем несколько примеров вычисления тестов методом булевой производной. Пример. Дана схема (рис. 4.6), реализующая функцию f(x)= x1 х2 Ъ x3. Найти тесты неисправностей x1 = 0 и x1 = 1. Найдем булеву производную df(x) / dx1: ![]() ![]() Рис. 4.6 ![]() Тест для x1 = 0 определим из условия x1Ч df(x) / dx1 = 1, то есть . Следовательно, x1 = 1, x2 = 1, x3 = 0. Тест для x1 = 1 определим из условия , то есть ![]() ![]() Следовательно, x1 = 0, x2 = 1, x3 = 0. Пример. Для схемы рис. 4.7 найти тестовые наборы для проверки неисправностей x2 = 0 и x2 = 1. Схема реализует функцию ![]() ![]() Пользуясь формулой для вычисления булевой производной df(x) / dx2, находим ее значение: df(x) / dx2 =(x1Ч 1 Ъ x1Ч 0) Е (x1Ч 0 Ъ x1 Ч 1)= 0. Это означает, что f(x) не зависит от x2, то есть неисправности x2 = 0 и x2 = 1 являются непроверяемыми. Пример. Дана схема рис. 4.8. Найти тестовый набор для проверки неисправности y6 = 0. Выразим f(x) через внутренние переменные схемы: ![]() ![]() Найдем булеву производную df(x) / dy6: ![]() Тест для y6 =0 найдем из условия y6Ч df(x) / dy6 = 1, то есть функция неисправность булевой производная ![]() Следовательно, тестом для проверки рассматриваемой неисправности является набор x1 = 1, x2 = 1, x3 = 0 и x4 = 0. Если от проверяемой точки имеются несколько путей к контролируемому выходу, то производная для данной точки определяется как произведение нескольких производных, число которых зависит от числа путей. |