Генерирование тестов для цифровых схем методом булевой производной
Генерирование тестов для цифровых схем методом булевой производной
Булевой производной функции 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 определяется следующим образом.
- 1. Составляем функцию f(x), в которой в качестве переменной присутствует z.
- 2. Определяем частную булеву производную df(x) / dz, приводим полученное выражение к дизъюнктивной форме (ДФ).
- 3. Выбираем один из термов (например, t), полученной в п. 2 ДФ.
- 4. Неисправность z = 0 проверяется на воздействии, при котором значения переменных x1,..., xn обеспечивают условие zЧ t = 1.
- 5. Неисправность z = 1 проверяется на воздействии, при котором значения переменных x1,..., xn обеспечивают условие `zЧ t = 1.
Приведем несколько примеров вычисления тестов методом булевой производной.
Пример. Дана схема (рис. 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.
Если от проверяемой точки имеются несколько путей к контролируемому выходу, то производная для данной точки определяется как произведение нескольких производных, число которых зависит от числа путей.
