Презентация_ТЕХ.ДИАГНОСТИКА_2. Конспект лекций по курсу "техническая диагностика" Ю. В. Малышенко введение
 Скачать 0.81 Mb.
|
|
4.4. d-алгоритм Общее решение задачи построения теста на основе идеи активизации пути наиболее удачно воплощено в предложенном Ротом (Roth J.P., 1967) d-алгоритме. В основе его лежат понятия логических кубов различного вида и правила действия над кубами, что делает удобным реализацию алгоритма на ЭВМ. Под логическим кубом понимается вектор размерностью n, каждая координата которого имеет одно из пяти значений: 0,1,х,d,d. Здесь 0 и 1 представляют обычные булевы значения, х - символ неопределенного или безразличного значения; более точно его смысл, так же, как смысл символов d и d , станет ясен из дальнейшего. Над парой логических кубов А =(а1,а2 , .. , аn) и В =(b1, b2, ..., bn) можно производить операцию пересечения, которая выполняется покоординатно по следующим правилам: Если хотя бы для одной координаты результат пересечения не определен, то и пересечение кубов А и В считается пустым. Каждому логическому элементу схемы соответствует три набора кубов элемента, которые используются при построении тестов: вырожденные (сингулярные) кубы, d-кубы элементов и d-кубы неисправностей. Вырожденные (сингулярные кубы) позволяют представить таблицу истинности элемента в сокращенном виде. В этих кубах входам, не влияющим на значение выхода, присваивается значение “ х”. На рис.4.4 для элементов И, ИЛИ-НЕ, М2 показаны их сингулярные кубы. Для элемента М2 нет несущественных входов, поэтому его покрытие полностью повторяет полную таблицу истинности à) & 3 2 1 1 2 3 4 1 1 1 1 0 x x 0 x 0 x 0 x x 0 0 4 3 2 1 1 б) 1 2 3 4 0 0 0 1 1 x x 0 x 1 x 0 x x 1 0 Рис.4.4 4 M2 2 1 в) 1 2 3 0 0 0 0 1 1 1 0 1 1 1 0 3 d-кубы элементов позволяют указать ситуации, когда сигнал на некотором входе или группе входов определяет значение выхода элемента. Для их построения можно использовать пары вырожденных кубов А и В, таких, что значения на выходной координате в А и В различны. Такой паре соответствует d-куб G =(g1 , ... , gn), определенный следующим образом (операция d-пересечения): Cравнивая подобным образом каждую пару вырожденных кубов получим множество d-кубов элемента. В каждом из них выходная координата и по крайней мере одна из входных равны d или d. Например, пересечение первых двух сингнулярных кубов элемента И (рис.4.4,а) даст d-куб 1111 0хх0 = d11d. Полученный куб показывает, что при фиксации в “единицах” второго и третьего входов элемента сигнал на его выходе определяется значением на первом входе. Это делает удобным использование d-кубов для построения активизированного пути в схеме. d-кубы , полученные в результате пересечений сингулярных кубов, достаточны при решении задачи формирования тестового воздействия путем активизации одного пути от неисправного элемента до выхода схемы. Однако, в общем случае, необходимо иметь все возможные d-кубы элементов, которые можно получить, если при пересечениях символы “х” заменять на 0 и 1 . Для элементов на рис. 4.4 это d-кубы: a) (1,1,d,d), (1,d,1,d), (d,1,1,d), (1,d,d,d), d,1,d,d), (d,d,1,d), (d,d,d,d), (1,1,d,d), (1,d,1,d), (d,1,1,d), (1,d,d,d), (d,1,d,d), (d,d,1,d), (d,d,d,d); б) (0,0,d,d), (0,d,0,d), (d,0,0,d), (0,d,d,d), (d,0,d,d), (d,d,0,d), (d,d,d,d), (0,0,d,d), (0,d,0,d), (d,0,0,d), (0,d,d,d), (d,0,d,d), (d,d,0,d), (d,d,d,d); в) (0,d,d), (1,d,d), (d,0,d), (d,1,d), (0,d,d), (1,d,d), (d,0,d), (d,1,d). В d-кубе неисправности координаты, сопоставленные входам элемента, имеют значения, при которых данная неисправность наблюдается (иногда говорят проявляется) по выходу элемента. Координата, сопоставленная выходу, равна d, если при исправном состоянии на выходе элемента 1. Эта координата равна d при исправном состоянии . Для одной неисправности может существовать несколько d - кубов неисправности. Например, “неисправности 0 на линии 1” элемента М2 (рис.4.4,в) соответствует два d-куба неисправности: (1 0 d) и (1 1d). Ниже в табл.4.6 показаны d-кубы неисправностей константного типа элемента И , представленного на рис.4.4,а: Из таблицы видно, что неисправности типа “0” для всех линий имеют один и тот же d- куб неисправности, а для неисправности “1 на линии 4” существует три разных d- куба. d-алгоритм предполагает, что тестовое воздействие (входной набор) определяется отдельно для каждой неисправности. Совокупность полученных наборов образует тест для всего множества допустимых неисправностей. Таблица 4.6
В d-алгоритме можно выделить следующие три основные операции построения тестового набора для проверки заданной неисправности. 1. Выбирается d-куб заданной неисправности. 2. Активизируются возможные пути от элемента с выбранной неисправностью к контролируемому выходу. При этом применяется операция пересечения d-куба неисправности с d-кубами всех элементов путей от неисправности до выхода схемы (прямая фаза d-алгоритма). 3. Выполняется пересечение полученного в п.2 d-куба с сингулярными кубами остальных элементов с целью обеспечения условий активизации, заданных этим d-кубом (обратная фаза d-алгоритма). Пример. Необходимо определить тестовое воздействие для неисправности “= 0” на втором входе (линия 8) элемента D3 схемы рис.4.5. a b k M2 & 1 D2 D4 D3 Рис.4.5. & 1 D1 2 3 4 7 9 8 6 10 11 12 c e f r s 5 Прежде чем начать выполнение d-алгоритма следует подготовить исходную информацию, которая понадобится при его исполнении. Это сингулярные и d-кубы элементов, которые были приведены ранее, а также d-куб заданной неисправности. Последний имеет вид( в верхней строке даны номера линий) : 7 8 9 11 0 1 0 d . Если для заданной неисправности существует несколько d-кубов неисправности, то первоначально можно выбрать любой из них. В рассматриваемой схеме пронумеровано 12 линий. Удобно вести вычисления, представляя кубы в виде 12-ти разрядных векторов. После подготовки исходной информации можно перейти к операциям d-алгоритма. 1. d-куб неисправности " = 0 на втором входе элемента D3" имеет вид( в верхней строке даны номера линий): 1 2 3 4 5 6 7 8 9 10 11 12 СО = х х х х х х 0 1 0 х d х. От выхода D3 имеется только один путь к выходу схемы (через элемент D4). Выполняем пересечение куба СО с d-кубом С1 элемента D4, имеющим символ d* на третьем входе: 1 2 3 4 5 6 7 8 9 10 11 12 СО = х х х х х х 0 1 0 х d x С1 = x x x x x 1 x x x 1 d d ---------------------------------------- C2 = x x x x x 1 0 1 0 1 d d. Появление в результирующем кубе символа d на выходной координате (т.е. на линии 12) свидетельствует об окончании прямой фазы d-алгоритма. 3. Обратная фаза d-алгоритма для рассматриваемого алгоритма будет состоять в последовательном пересечении куба С2 с сингулярными кубами элементов D1 и D2. Из сингулярных кубов элемента D1 необходимо выбрать тот, в котором на его выходе значение 1, так как в кубе С2 координата 8 определена равной 1. 1 2 3 4 5 6 7 8 9 10 11 12 С2 = x x x x x 1 0 1 0 1 d d С3 = x x 1 1 1 x x 1 x x x x --------------------------------------- C4 = x x 1 1 1 1 0 1 0 1 d d. Из сингулярных кубов элемента D2 следует выбрать тот, в котором на выходе значение 1, так как в кубе С4 координата 6 имеет значение 1. Таких кубов несколько. Первоначально можно взять любой. 1 2 3 4 5 6 7 8 9 10 11 12 С4 = x x 1 1 1 1 0 1 0 1 d d С5 = 0 1 x x x 1 x x x x x x ---------------------------------------- С6 = 0 1 1 1 1 1 0 1 0 1 d d, В полученном кубе С6 нет неопределенных (т.е. равных “x” ) координат. Поэтому выполнение d-алгоритма закончено. На последнем шаге по координатам 1-5,7,9,10 определяем входной набор, проверяющий заданную неисправность: a b c e f r s k 0 1 1 1 1 0 0 1 . Возможно, что при выполнении п.2 или п.3 в результате пересечения будет значение "пусто". Тогда следует взять другой куб для пересечения (если такой существует). Если все же после перебора всех кубов (в том числе всех вариантов d-кубов рассматриваемой неисправности) не удалось избавиться от значения "пусто", то это означает, что данная неисправность не может быть проверена, т.е. в схеме имеется избыточность. 4.5. Построение теста по методу булевой производной Булевой производной функции 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: x3 x1 x2 f(x) 1 & Рис. 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 являются непроверяемыми. x1 x2 & 1 & & f(x) Рис.4.7. Пример. Дана схема рис. 4.8. Найти тестовый набор для проверки неисправности y6 = 0. Выразим f(x) через внутренние переменные схемы: x1 x2 x4 x3 f(x) 1 1 1 y5 y6 Рис.4.8. Найдем булевую производную df(x) / dy6: Тест для y6 =0 найдем из условия y6 df(x) / dy6 = 1, то есть Следовательно, тестом для проверки рассматриваемой неисправности является набор x1 = 1, x2 = 1, x3 = 0 и x4 = 0. Если от проверяемой точки имеются несколько путей к контролируемому выходу, то производная для данной точки определяется как произведение нескольких производных, число которых зависит от числа путей. 4.6. Построение теста по методу эквивалентной нормальной формы Этот метод основан на представлении булевой функции в виде эквивалентной нормальной формы (ЭНФ), описывающей конкретную реализацию схемы. ЭНФ отличается от ДФ тем, что ее переменные сопоставлены не входам схемы, а всем возможным путям распространения сигналов. Эквивалетная нормальная форма, как и обычная нормальная, может быть вычислена методом подстановки, с той лишь разницей, что избыточные термы не исключаются, так как они характеризуют конкретную реализацию схемы. Так для схемы рис.4.9. ЭНФ может быть получена путем следуюющих подстановок (применяется процедура обратной подстановки): y c d n 1 b a k m 1 & 1 1 1 5 2 4 1 3 Рис.4.9. Раскрыв скобки, имеем Закодируем последовательности элементов путей схемы следующим образом: 2,1 - 1; 5,2,1 - 2; 5,4,3,1 - 3; 4,3,1 - 4. С учетом введенных обозначений запишем Аргументами ЭНФ являются буквы ЭНФ. Число букв ЭНФ в общем случае больше числа входных переменных схемы, так как одна и та же входная переменная может быть связана с выходом схемы несколькими путями. Наряду с ЭНФ можно использовать при построении тестов также обратную ЭНФ (ОЭНФ). Обратная ЭНФ для схемы рис.4.9 имеет вид: Идея построения теста неисправности по ЭНФ (или ОЭНФ) основана на следующем. При неисправности константного типа функцию, реализуемую схемой, можно получить из исходной, зафиксировав некоторые буквы в значениях 0 и 1. Например, функцию схемы при неисправности "линия m=1" можно получить из исходной ЭНФ, зафиксировав буквы a1 и b2 в значении 1, либо буквы a1 и c2 в значении 1. После подстановки этих значений в функцию исправной схемы получим функцию, реализуемую при заданной неисправности: y = 0. Очевидно, что из этого факта следует возможность построения теста неисправности путем определения входного набора , обнаруживающего "фиксацию букв" ЭНФ заданной неисправностью. Поскольку ЭНФ представляет собой сумму логических произведений, она соответствует гипотетической схеме нескольких И-ИЛИ. Каждой схеме И соответствует один терм ЭНФ. Из такого представления ЭНФ становится очевидным, что для выявления неисправностей, связанных с переменной (буквой) ”xi”, входящей в какой-либо терм ЭНФ, необходимо выполнение следующих условий: 1) равенство нулю всех термов, кроме содержащего переменную xi; 2) равенство единице всех компонент выбранного терма, в который входит переменная xi. Выполнение этих условий обеспечивает тождественное равенство f(x) = xi и, как следствие , неисправности, изменяющие значение данной переменной, изменяют и значение выхода схемы. Тест, проверяющий фиксацию всех букв в значениях 0 и 1 является тестом, проверяющем все неисправности константного типа. Методику построения теста по методу ЭНФ можно представить ввиде следующих операций. 1. Пронумеровав линии схемы и элементы, строим ЭНФ. 2. Выбираем букву ЭНФ и терм с этой буквой. 3. Для проверки буквы на неисправность типа 1(0) присваиваем ей значение 0(1). Всем остальным буквам выбранного терма присваиваем значения так, чтобы они давали значение 1 в выбранном терме . 4. В остальных термах хотя бы одной букве присваиваем такое значение, чтобы терм стал равным нулю. Если оказалось невозможным выполнить это условие для выбранного терма, то возвращаемся к п.3 и берем другой терм с рассматриваемой буквой. 5. Определяем значения переменных ЭНФ, сопоставленных входам схемы. Они устанавливаются в соответствии с назначенными значениями букв и задают входной набор для проверкм выбранной в п.2 буквы. 6. Повторяем п.2-4 до тех пор пока не будут рассмотрены все буквы ЭНФ и их фиксации. Каждой букве сопоставлена группа линий и элементов схемы. Поэтому тестовый набор проверяющий букву фактически проверяет правильность прохождения сигнала через соответствующую группу линий и элементов, а следовательно проверяет некоторое множество неисправностей. Заметим, что возможны ситуации, когда для проверки неисправности необходимо искать набор, проверяющий фиксацию некоторой группы букв. Однако такие ситуации достаточно редки. |