Материал: ОТД №4 - Метод существенных путей
Федеральное агентство железнодорожного транспорта Федеральное государственное бюджетное
образовательное учреждение высшего профессионального образования «ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»
_____________________________________________________________
Кафедра «Автоматика и телемеханика на железных дорогах»
ПОСТРОЕНИЕ ТЕСТОВ ДЛЯ КОМБИНАЦИОННЫХ СХЕМ МЕТОДОМ СУЩЕСТВЕННЫХ ПУТЕЙ
Методические указания к практическим занятиям по дисциплинам
«Основы теории надежности» и «Основы технической диагностики»
САНКТ-ПЕТЕРБУРГ ПГУПС
2014
Цель практического занятия – изучение метода существенных путей для построения тестов комбинационных логических схем.
1 Основы теории построения тестов методом существенных путей
1.1Структурный способ задания схем и таблицы D-кубов
Взадачах построения тестов для комбинационных схем со сложной архитектурой, включающей в себя большое количество логических элементов и связей между ними, применяются локальные алгоритмы построения тестов. Локальный алгоритм не требует вычисления функции, реализуемой всей схемой, и использует только информацию, характеризующую логические элементы схемы. Другими словами, анализ схемы проводится по частям, что снижает время построения алгоритма диагностирования, а также объемы занимаемой памяти микропроцессоров.
Схему удобно задавать структурным способом: в виде списка, содержащего информацию о каждом логическом элементе рассматриваемой комбинационной схемы (net list) [1]. Такой список содержит столько строк, сколько логических элементов содержится в комбинационной схеме. Каждая строка включает в себя такую информацию: номер логического элемента, тип элемента, связи с другими элементами.
Рассмотрим комбинационную схему, приведенную на рис. 1. Схема имеет три входа a, b и c, и один выход f. В структуре схемы выделяется 6
логических элементов (они обозначены как Gi), а также 17 линий (линии обозначены арабскими цифрами; каждая линия может быть также задана номерами элементов, которые она связывает, например, G2 – G4).
|
|
G1 |
|
|
|
|
|
a |
1 |
4 |
|
|
G3 |
|
|
|
1 |
6 |
|
|
|
||
|
|
|
G5 |
|
|||
|
|
|
|
|
|||
|
|
|
|
& |
|
||
|
|
|
|
|
|
||
|
|
5 |
|
|
11 |
|
|
|
|
|
|
|
|
||
b |
2 |
|
|
10 |
|
1 |
16 |
|
|
|
15 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
12 |
G4 |
|
|
|
|
G2 |
|
1 |
|
|
|
|
|
|
|
|
|
||
|
|
7 |
|
|
14 |
|
|
|
|
|
|
|
|
||
|
|
& |
9 |
13 |
|
|
|
|
|
|
|
|
|
||
c |
3 |
8 |
|
|
|
|
|
Рис. 1. Комбинационная схема
G6 |
|
1 |
f |
|
|
|
17 |
1
Зададим исходную комбинационную схему структурным способом:
G1: ИЛИ; a, G4; c, G2; G3; G2: И; b, G3; c, G1; G4, G5; G3: И; G1; b, G2; G5;
G4: ИЛИ-НЕ; a, G1; G2, G5; G6; G5: ИЛИ-НЕ; G3; G2, G4; G6; G6: ИЛИ; G5; G4; f.
Список определяет структуру схемы, логика же задается описанием элементов, которые содержатся в схеме. Такое описание задается в виде таблиц истинности логических элементов (рис. 2).
a) |
|
|
|
|
|
|
|
|
г) |
|
|
|
|
|
|
|
||
|
|
|
|
|
x1 |
x2 |
|
y |
|
|
|
|
|
x1 |
x2 |
|
y |
|
x1 |
|
& |
y |
0 |
|
0 |
|
0 |
x1 |
|
& |
y |
0 |
0 |
|
1 |
||
|
|
|
||||||||||||||||
|
|
0 |
|
1 |
|
0 |
|
|
0 |
1 |
|
1 |
||||||
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x2 |
|
|
|
|
1 |
|
0 |
|
0 |
x2 |
|
|
|
|
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
1 |
1 |
|
0 |
б) |
|
|
|
|
|
|
|
|
д) |
|
|
|
|
|
|
|
||
|
|
|
|
|
x1 |
x2 |
|
y |
|
|
|
|
|
x1 |
x2 |
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
x1 |
|
1 |
y |
0 |
|
0 |
|
0 |
x1 |
|
1 |
y |
0 |
0 |
|
1 |
||
|
|
|
||||||||||||||||
|
|
0 |
|
1 |
|
1 |
|
|
0 |
1 |
|
0 |
||||||
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x2 |
|
|
|
|
1 |
|
0 |
|
1 |
x2 |
|
|
|
|
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
1 |
1 |
|
0 |
в) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
y |
|
|
|
|
|
|
|
|
|
|
|
1 |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|||
x |
|
|
|
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
Рис. 2. Таблицы истинности логических элементов: а) И; б) ИЛИ; в) НЕ; г) И-НЕ; д) ИЛИ-НЕ
Кроме логики работы каждый логический элемент характеризуется конкретными условиями трансляции (передачи) ошибок входных сигналов на выход. К примеру, ошибка 0→1 на каком-либо из входов логического элемента И транслируется на выход только в том случае, если на втором входе присутствует сигнал 1 (рис. 3).
а) |
0→1 |
|
|
|
|
б) |
0→1 |
|
|
|
|
|
& |
|
0→1 |
|
& |
|
0 |
||||
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
||||
|
1 |
|
|
|
|
0 |
|
|
|
||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Рис. 3. Пример трансляции ошибки логического элемента И: а) транслируемая ошибка; б) нетранслируемая ошибка
2
Ошибку 1→0 обозначим D, ошибку 0→1 – соответственно D . Тогда для элемента И можно составить таблицу, характеризующую возможность трансляции на выход логического элемента любой ошибки на входе (табл. 1). Строка такой таблицы называется D-кубом. Подобное название связано с геометрическим заданием функций алгебры логики в виде n-мерного (в данном случае, двухмерного) куба [2]. Строки с номерами 1 – 6 характеризуют условия отсутствия трансляции ошибок с входов на выход элемента И; строки 7 – 12, наоборот, характеризуют условия трансляции ошибок с входов на выход элемента И.
Таблица 1
Таблица условий трансляции ошибок элемента И
Номер |
x1 |
x2 |
f |
Отсутствие трансляции ошибки
1 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
D |
|
|
|
|
||||
2 |
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
D |
|
|
|||||
3 |
|
0 |
|
|
D |
|
0 |
|
||
4 |
|
|
D |
|
0 |
|
|
0 |
|
|
5 |
|
|
D |
|
|
|
|
|
0 |
|
|
|
|
|
D |
|
|
||||
6 |
|
|
|
|
|
D |
|
0 |
|
|
|
|
D |
|
|
|
|
||||
|
|
|
|
|
||||||
|
Трансляция ошибки |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
D |
|
1 |
|
|
D |
||
8 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
D |
|
D |
|||||
9 |
|
|
D |
|
1 |
|
|
D |
||
10 |
|
1 |
|
|
D |
|
D |
|||
11 |
|
|
D |
|
|
D |
|
D |
||
12 |
|
|
|
|
|
|
|
|
|
|
|
|
D |
|
|
D |
|
D |
|||
Строки табл. 1 под номерами 1 – 6 носят название тупиковых D- кубов, т.к. трансляция ошибки «заходит в тупик».
Поскольку таблицы истинности хранятся в памяти микропроцессора, производящего вычисления для поиска теста, их представляют в сжатом виде. С этой целью введем символ x, имеющий смысл безразличного значения 0 или 1 ( x 0;1 ). Символ x позволяет сжать таблицу истинности элемента И (см. рис. 2, а) до табл. 2.
Таблица 2
Сжатая таблица истинности элемента И
x1 |
x2 |
f |
|
|
|
x |
0 |
0 |
0 |
x |
0 |
1 |
1 |
1 |
3
Табл. 2 содержит 3 куба. К примеру, смысл куба 0x0 таков: если на одном входе элемента И имеется сигнал логического 0, то независимо от значения сигнала на втором входе сигнал на выходе будет равен 0.
Учитывая тот факт, что входы логического элемента И равноправны (замена индексов входов друг на друга не изменит результата), табл. 2 можно сжать еще больше, удалив первую или вторую строку (табл. 3).
Таблица 3
Максимально сжатая таблица истинности элемента И
x1 |
x2 |
f |
|
|
|
x |
0 |
0 |
1 |
1 |
1 |
Точно также можно сжать и таблицу D-кубов (см. табл. 1). Учитывая равноправность входов, можно удалить строки 2, 3, 6, 8 и 10. Используя введенный ранее символ x, можно объединить строки 1 и 4. Таким образом, получена сжатая таблица условий трансляции ошибок логического элемента И.
Таблица 4
Сжатая таблица условий трансляции ошибок элемента И
|
x1 |
|
x2 |
|
f |
|||
|
|
|
|
|
|
|
|
|
|
x |
0 |
|
0 |
|
|||
|
D |
|
|
|
0 |
|
||
|
|
D |
|
|||||
|
|
|
1 |
|
|
|
|
|
|
D |
|
|
D |
||||
|
D |
1 |
|
|
D |
|||
|
D |
|
D |
|
D |
|||
|
|
|
|
|
|
|
|
|
|
D |
|
D |
|
D |
|||
Для удобства использования сжатые таблицы истинности и таблицы условий трансляции ошибок объединяются в одну, называемую расширенной таблицей D-кубов. Любая такая таблица несет информацию трех видов: логику работы логического элемента, информацию о трансляции ошибки, информацию об отсутствии условий трансляции ошибки.
Для элемента И таблица D-кубов – это табл. 5. Для остальных логических элементов – это таблицы 6 – 9.
4