4.1. Алгоритм podem, условные обозначения, понятия и принципы

Алгоритм PODEM представляет собой процедуру генерации проверяющего теста для заданной неисправности, основанную на принципах транспортировки неисправности вдоль активизирован­ного пути. В этом отношении алгоритм PODEM аналогичен D- алгоритму, и, действительно, в этой процедуре используется D-нотация (см. далее), впервые введенная при разработке D-алго-ритма. От D-алгоритма PODEM отличается способом определе­ния логических значений первичных входов, необходимых для ак­тивизации пути от источника неисправности до первичного выхо­да (ПВых). Эти значения определяются при обратном проходе от места заданной неисправности к входам путем обеспечения в логических узлах схемы условий тестирования этой неисправно­сти до тех пор, пока не будут определены логические значения первичных входов (ПВх). После этого полнота определенных зна­чений первичных входов (ПВх-определения) оценивается с по­мощью процедуры моделирования, которая заключается в про­верке условий тестируемости для всех узлов схемы. Если для не­которого узла эти условия не обеспечиваются, процедура обрат­ного прохода повторяется, начиная с этого узла. Сущность мето­да прояснится в большей степени после иллюстрации его на при­мере. Перед тем как это сделать, необходимо ввести и опреде­лить некоторые понятия и идеи, используемые в алгоритме PODEM.

4.1.1. УСЛОВНОЕ ОБОЗНАЧЕНИЕ УЗЛА СХЕМЫ

Слово «узел» отождествляется с соединением схемы, переда­ющим сигнал от одного элемента к другому. Если узел не обоз­начен специальным символом, то ему присваивается условное обозначение элемента и добавляется номер вывода элемента, от которого направлена линия соединения, но не допускается ис­пользовать номер вывода элемента, к которому направлена ли­ния соединения. В этом случае обозначение узла, соответствую­щего элементу схемы с ветвлениями к нескольким элементам, не будет содержать неопределенности. Обозначения узлов записы­ваю юя, как «номер элемента, номер вывода», т.е. вывод 3, соот­ветствующий выходу элемента G1, обозначается, как узел схемы G1.3.

Рис. 4.1. Условное обозначение узлов

На рис. 4.1 предложенное условное обозначение узлов ил­люстрируется на примере простой схемы с ветвлениями. (Отме­тим: на рис. 4.1 и на последующих схемах номера выводов эле­ментов проставлены произвольно, хотя они могут соответствовать номерам выводов микросхем, например, типа SN7400. Читатель не должен придавать этому большого значения. Принятый спо­соб обозначения позволяет только исключить неопределенность идентификации узлов схемы.)

4.1.2 ЛОГИЧЕСКИЕ СОСТОЯНИЯ УЗЛОВ

В алгоритме PODEM используется D-нотация для описания эффекта проявления неисправности или передачи состояния ло­гического узла. Полное множество состояний, в котором может находиться узел, следующее:

а) фиксированное состояние логического 0;

б) фиксированное состояние логической 1;

в) фиксированное состояние D или D, где D==1 (D=0) со­ответствует исправному состоянию узла, a D=0 (D=1) опреде­ляет неисправное состояние узла, соответствующее либо появле­нию в этом узле неисправности, либо транспортировке неисправ­ности из предшествующего узла;

г) неопределенное состояние X, которое может принимать любое значение: 0, 1, D или D.

Для читателей, не знакомых с D-нотацией, на рис. 4.2 показан простой пример схемы, к входам которой подается тестовый на­бор, позволяющий обнаружить неисправность элемента G 3.3 (в исправном состоянии значение на выходе равно 1; в неисправ­ном равно 0, что соответствует неисправности на выходе G3.3 типа н-к-0) и транспортировать ее через элементы G4 и G5.

Рис.4.2. Пример D-нотации

На рис. 4.2 показаны также фиксированные состояния 0 и 1 узлов схемы, обеспечивающие условия тестирования неисправности вместе с неопределенным значением (X) на одном из первичных входов.

Рис.4.3. D – нотация:

а – условия тестирования неисправностей; б – условия D - распространения

На рис. 4.3 приведены в обобщенном виде условия тестиро­вания и D-распространения для каждого элементарного логиче­ского вентиля, включая элемент Исключающее ИЛИ. Входные комбинации на каждом вентиле (рис. 4.3) позволяют обнаружить н-к-1 на выходе вентиля (значение на выходе D) или неисправ­ность типа н-к-0 (значение выхода D). На рис. 4.3. определены фиксированные значения входов вентилей, которые обеспечи­вают транспортировку значения D со стороны входа вентиля к его выходу.

4.1.3. ЦЕЛЕВЫЕ УЗЛЫ СХЕМЫ

Детальная реализация алгоритма PODEM основана на иден­тификации и попытке достижения определенных целей, связан­ных с установкой конкретного узла схемы в требуемое состояние. Например, возвращаясь к рис.4.2, можно было бы записать «ус­тановить в узле G 3.3 состояние D» или «установить в узле G1.3 состояние 0». Такие целевые узлы и их исходные состояния бу­дем обозначать OB (G3.3=D) и OB (G1.3=0).

4.1.4. ВЫБОР ПУТИ РАСПРОСТРАНЕНИЯ ЛОГИЧЕСКИХ СОСТОЯНИИ

Алгоритм PODEM включает в себя процедуру поиска усло­вий, обеспечивающих заданное логическое состояние в выходном узле путем транспортировки его значения к входному узлу, ко­торая основана на выборе «самого легкого» или «самого сложного» пути распространения сигналов. (Концептуально эта про­цедура соответствует логике операций в D-алгоритме.) В данном контексте понятия «самый легкий» и «самый сложный» связаны с относительными значениями управляемостей множества вход­ных узлов и могут быть основаны на оценках управляемости, по­лученных в результате применения системы CAMELOT.

Наряду с упомянутой процедурой существует простейшая про­цедура вычисления относительных значений управляемости для множеств узлов схемы, кратко описываемых здесь.

Рис. 4.4. Легко и сложно управляемые входы

Для иллюстрации подхода рассмотрим элемент схемы, пред­ставленный на рис. 4.4. На рисунке изображен трехвходовый вен­тиль И-НЕ, обозначенный G5, который является частью большой схемы. Значения управляемости известны и указаны для каждо­го входного узла (выводы 3—5), однако не установлены логиче­ские значения узлов, т.е. узлы имеют неопределенные состояния X. Транспортировка логических значе­ний с выхода элемента на входы может быть выполнена только при неопределенном состоянии входных узлов. Те­перь рассмотрим случай, когда ОВ (G5.6=1). Это логическое состояние в управляемые входы целевом узле можно обеспечить, уста­навливая на одном из трех входов вентиля логический 0. Сле­довательно, имеет смысл выбрать входной узел, в котором на­иболее легко устанавливается 0. В этом случае выбирается вход 3, так как этот узел имеет максимальное значение управ­ляемости. Этот выбор определяет транспортировку логического состояния целевого узла к новому целевому узлу OB (G5.3==0), и, таким образом, процедура обратной транспортировки (обрат­ного прохода) продолжается до полного описания состояний всех вентилей.

Рассмотрим теперь вариант с другим логическим состоянием целевого узла G5.6, а именно OB (G5.6=0). Это состояние мож­но обеспечить только в случае, если на всех трех входах вентиля И-НЕ установить 1. Исходя из временных затрат, безусловно, предпочтительнее следовать по одному пути транспортировки ло­гических состояний, чем одновременно по нескольким. Это зна­чит, что процедура должна определять один из входов последу­ющего обратного прохода. Наиболее рациональное решение за­ключается в выборе входа с худшей управляемостью, т. е. входа 4, на том основании, что если этот вход не может быть установ­лен в требуемое состояние, то нет необходимости доопределять узлы схемы с более высокими значениями управляемости. Дру­гими словами, если стремиться к сокращению временных затрат, то целесообразнее решить первой наиболее сложную задачу, а не простую.

Если начальный целевой узел OB (G5.6=0), то об­ратный проход заключается в определении логического значения нового целевого узла OB (G5.4=1), и, таким образом, процесс продолжается далее.

В случае если G5.4 действительно устанавливается в состоя­ние 1, то процесс возвращается к начальному целевому узлу 0В (G5.6==0). В этом случае необходимо сделать выбор между вхо­дами 3 и 5; результатом выбора является OB (G5.5=1), так как управлять входом 5 сложнее, чем входом 3.

Рис. 4.5. Самые легкие и самые сложные условия установки логических состояний вентилей

На рис. 4.5 при­ведены «самые легкие» и «самые сложные» условия установки логических значений на выходах для всех типов элементарных вентилей, включая вентиль Исключающее ИЛИ.