Генерирование тестов для цифровых схем методом булевой производной

Генерирование тестов для цифровых схем методом булевой производной

Булевой производной функции 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.

Если от проверяемой точки имеются несколько путей к контролируемому выходу, то производная для данной точки определяется как произведение нескольких производных, число которых зависит от числа путей.