Конкурентный и дифференциальный метод моделирования неисправностей

13.1 Конкуррентный метод моделирования неисправностей

Этот метод является наиболее общим методом моделирования цифровых схем с неисправностями [13.1]. Он, как и предыдущий, является одношаговым, то есть для данного входного набора выявляются сразу все проверяемые неисправности. Он позволяет обрабатывать различные типы моделей схем, неисправностей, задержек и сигналов. Метод основан на том, что в процессе моделирования значения сигналов на большинстве линий неисправных схем совпадают со значениями исправной схемы. Конкурентный метод явно моделирует исправную схему (все ее логические элементы) и для каждой неисправности обрабатывает только те элементы, значения сигналов на которых отличаются от соответствующих значений в исправной схеме. Такие расхождения для каждого элемента собираются в специальный список. В отличие от дедуктивного метода список неисправностей здесь ассоциируется не с линией схемы, а с логическим элементом. При этом список включает не только те неисправности, которые вызывают неправильное значение сигнала на выходе элемента, но и такие, при которых значения сигналов отличны от исправного устройства и на входах элемента. Такой список называют суперсписком неисправностей, так как он обычно существенно шире соответствующего списка дедуктивного метода моделирования.

В конкурентном методе все неисправности обрабатываются наравне с исправными устройствами, то есть для неисправности включенной в суперсписок, выполняется моделирование данного элемента явно. Каждый элемент суперсписка включает в себя номер неисправности и значения сигналов на входах и выходах этого элемента при данной неисправности.

Например, на рис. 13.1 представлен в графическом виде суперсписок неисправностей для вентиля $$c=\overline{a\cdot b}$$ [13.2]. Здесь вверху представлен логический элемент со значениями сигналов в исправной схеме. Во втором сверху элементе показано, что при неисправности номер 3 имеют место значения сигналов $$a=0, b=0, c=1$$. Соответственно третий элемент списка показывает, что для неисправности номер 5 $$a=0, b=0, c=1$$. Заметим, что одинаковые значения сигналов при неисправностях номер 3 и 5 допускаются. Аналогично для последнего элемента списка имеем $$a=1, b=1, c=0$$. Отметим, что только последняя неисправность номер 111 попала бы в список дедуктивного моделирования, связанного с линией c. Как видно из примера, элементы в суперсписке сортируются по номерам неисправностей для более эффективной обработки и хранения в связанных списках либо в последовательных массивах.

Так как суперсписок шире списка, используемого в дедуктивном методе, то затраты памяти в этом методе выше при конкурентном методе. В дедуктивном методе явно (непосредственно) моделируются только те элементы, которые исправны. В конкурентном методе явно моделируются те элементы, значения входов или выходов которых отличны от значений исправных схем. В параллельном методе элементы в исправных и неисправных схемах моделируются явно даже в тех случаях, если значения сигналов у них совпадают.

В качестве примера рассмотрим моделирование фрагмента схемы, представленного на рис. 13.2. На нем представлены в графическом виде суперсписки вентилей схемы для входного набора $$a=0, b=0, d=0, f=0$$. Здесь с вентилем $$с$$ ассоциируется список с константными неисправностями $$a_{1}$$, $$b_{1}$$, и $$с_{0}$$, при которых значения на входах или выходе элемента отличны от исправной схемы. Заметим, что только при неисправности $$с_{0}$$ значение выхода элемента $$с$$ отлично от исправного. Поэтому эта неисправность распространяется далее по схеме (она включается в суперсписки вентилей $$e$$ и $$g$$).

Далее рассмотрим изменение суперсписков, которое происходит вследствие изменения входного набора $$a:0\to 1,e:0\to 1$$. В результате имеем следующие суперсписки, показанные на рис. 13.3.

Видно, что в исправной схеме значение выхода вентиля $$с$$ не изменяется. При неисправности $$b_{1}$$ вентиль $$с$$ моделируется явно и его выход изменяется с 1 на 0. Заметим, что это событие распространяется далее и попадает в суперсписок, связанный с вентилем $$g$$. Очевидно, что неисправность $$a_{0}$$ надо добавить в суперсписок $$с$$ (поскольку при ней значения сигналов отличаются от значений исправной схемы). При неисправности $$a_{1}$$ значение сигналов на всех линиях вентиля $$с$$ совпадает с исправным устройством. Поэтому $$a_{1}$$ исключается из суперсписка $$с$$. Аналогично обрабатываются суперсписки для вентилей $$e$$ и $$g$$.

Из этого примера видно, что основными процедурами в конкурентном методе является внесение влияний неисправностей, сужение и расширение суперсписков, обработка последователей элемента [13.3]. Перед началом моделирования проводится инициализация, в процессе которой все неисправности схемы вносятся в соответствующие суперсписки. Это делается локально - для каждого элемента в его суперсписок включаются неисправности, при которых входы и выходы элемента имеют значения сигналов, отличные от значений исправной схемы. Далее в процессе моделирования влияние этих неисправностей распространяется по схеме. Как мы видели на примере, элемент в суперсписке может стать идентичным элементу в исправном устройстве, когда значения их сигналов на всех входах и выходах совпадают. Тогда этот элемент должен быть исключен из суперсписка, который при этом сужается. При этом совпадение сигналов у исправных и неисправных элементов может произойти по двум причинам:

В первом случае для всех неисправных элементов, которые были промоделированы, должно быть выполнено сравнение с исправными элементами и в случае совпадения соответствующий элемент исключается из списка. Эта ситуация представлена на рис. 13.4 а).

Во втором случае для всех элементов суперсписка неисправностей должно быть выполнено сравнение с неисправным элементом. Эта ситуация представлена на рис. 13.4 б). Очевидно, рассматриваемые процедуры требуют затрат на поиск элементов и просмотр списка, включение и исключение элементов из него. Аналогично, при какой-либо неисправности в процессе моделирования значения сигналов элемента могут стать отличными от значений сигналов исправного устройства. Тогда в суперсписок должен быть включен соответствующий элемент, что ведет к расширению списка. Неисправности, при которых значения выходов отличаются от выходов исправных элементов, включаются в суперсписки элементов-последователей. Если изменились значения элемента в исправной схеме, то кандидатами на включение в список являются неисправности этого элемента. Эта ситуация представлена на рис. 13.5.

Так как в конкурентном методе моделирование элемента при каждой неисправности выполняется явно и независимо от других неисправностей, то в нем можно использовать самые эффективные модели элементов, такие как табличные и функциональные.

Далее сравним параллельный, дедуктивный и конкурентный методы моделирования по следующим критериям:

Параллельный и дедуктивный методы моделирования достаточно эффективны в двоичном алфавите. Обобщение параллельного метода на троичный алфавит выполняется достаточно просто - при этом как мы видели быстродействие уменьшается, а затраты памяти увеличиваются в два раза. Обобщение дедуктивного метода на троичный алфавит выполняется уже сложнее и требует значительного увеличения ресурсов. Обобщение параллельного и дедуктивного метода на многозначные алфавиты также возможно, но требует значительного увеличения вычислительных ресурсов. Структура данных и реализация алгоритмов в параллельном и дедуктивном методах существенно зависит от значности используемого алфавита моделирования.

Оба метода частично допускают использование функциональных моделей логических элементов. Это возможно только в том случае, когда функционирование элементов может быть описано с помощью булевых функций.

Напротив конкурентный метод моделирования относительно легко допускает использование многозначных алфавитов и переход на функциональный уровень: структура данных и реализация алгоритма слабо зависят от значности алфавита. Более того, этот метод допускает использование различных, в том числе более адекватных, моделей задержек, поскольку в нем каждый неисправный элемент обрабатывается индивидуально.

Мы уже отмечали, что дедуктивный метод эффективнее параллельного для больших схем. Экспериментальные исследования показали, что конкурентный метод по быстродействию превосходит дедуктивный. Это обуславливается следующими факторами. В конкурентном методе реализуется событийность не только по значениям сигналов и спискам, но и по неисправностям. В конкурентном методе активными являются только отдельные неисправные элементы, а в дедуктивном часто заново вычисляются списки неисправностей.

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

Известны работы, в которых предпринималась попытка объединить преимущества всех трех методов.

13.2 Test-Detect

В [лекции 7). Здесь предполагается, что все вентили имеют нулевую задержку. Сначала выполняется моделирование исправной схемы в двоичном алфапвите, что позволяет определить значения сигналов для всех линий схемы. Далее по очереди (последовательно) анализируется проверяемость каждой неисправности на текущем входом наборе. Анализ выполняется на основе алфавита $$B_{4}=\{0,1,D,D'\}$$, который позволяет одновременно моделировать исправную и неисправную схему. Напомним, чт о элементы алфавита $$B_{4}$$ имеют следующую интерпретацию: $$0(1)=00(11)$$ - значения сигналов равны; $$D'(D)=01(10)$$ - значения сигналов различны в исправной и неисправной схеме.

При моделировании сначала производится активизация неисправности, где неисправной линии присваивается значение $$D$$ (для константы 0) или $$D'$$ (для константы 1). Далее выполняется распространение значений $$D,D'$$ через логические элементы и узлы разветвления на текущем входном наборе. Если значение $$D$$ или $$D'$$ достигает хотя бы одного внешнего выхода, то считается, что неисправность проверяется данным входным набором. После этого значения сигналов для всех линий схемы восстанавливаются (к значениям исправной схемы) и производится анализ следующей неисправности. Когда выполнен анализ всех неисправностей, процедура повторяется для следующего входного набора и т.д.

На рис. 13.6 приведен пример моделирования неисправности данным методом. На рис. 13.6) представлены результаты для неисправности константа 1 на нижней ветви разветвления. Здесь при активизации неисправной линии присвоено значение $$D'$$ и далее выполнено $$D$$-распространение через логические вентили путем моделирования в алфавите $$B_{4}$$ .

При этом, необходимы многозначные модели основних вентилей. Здесь можно использовать многозначные модели (табличне или компонентные), приведенные в лекциях 7 или 15. Поскольку в результате D-распространения внешний выход схемы получил значение D (сигналы в исправной и неисправной схеме имеют различные значения), то данная неисправность проверяется текущим входным набором.

С другой стороны на рис. 13.6 б) представлены результаты моделирования для неисправности константа 1 для верхней ветви узла разветвления. Здесь процедура D-распространения не дает значения $$D$$ (или $$D'$$) на внешнем выходе схемы, что говорит о том, что эта неисправность не проверяется текущим входным набором.

13.3 Дифференциальный метод моделирования неисправностей

На основе метода "Test-Detect" в [13.6] разработан дифференциальный метод моделирования неисправностей, в котором по сравнению с указанным сделаны следующие изменения: 1) отказ от D-исчисления (моделирования в алфавите $$B_{4}$$); 2) отказ от процедуры явного восстановления значений сигналов перед анализом следующей неисправности. Название "дифференциальный " метод получил вследствие того, что в нем явным образом анализируется различие (сигналов) между двумя схемами (исправной и неисправной). Отметим, что первоначально метод разработан для комбинационных и синхронных последовательностных схем с нулевыми задержками элементов. Сначала рассмотрим дифференциальный метод для комбинационных схем, для которых основной алгоритм можно описать следующим образом:

Отметим, что основное отличие от предшествующего метода "Test-Detect" содержится в п.6 приведенного алгоритма. Отсутствие вычислений в $$B_{4}$$_{ } позволяет сделать программную реализацию проще. Кроме этого, одновременное восстановление сигнала для предыдущей неисправности и активизация (внесение) неисправности в два раза снижает число проходов событийного моделирования. Таким образом, в алгоритме обрабатываются следующие события: 1) входные вследствие изменения входного вектора; 2) активизация следующей неисправности; 3) восстановление значений для предыдущей неисправности; 4) изменение значений сигналов на входах элемента в процессе моделирования.

По существу, оба последних метода являются "дифференциальными" поскольку основаны на анализе различий сигналов в исправной и неисправной схеме. Эти методы могут быть распространены и на синхронные последовательностные схемы. Это корректно если максимальная задержка комбинационной схемы в модели Хафмена меньше период синхронизации управляющих триггеров. В этом случае комбинационная логика может моделироваться с нулевыми задержками, триггера предполагаются идеальными элементами памяти, которые синхронизируются изменением входных векторов. При этом моделируются только неисправности комбинационной логики схемы.

Обобщение этого метода на последовательностные схемы требует, чтобы каждый триггер имел текущий список неисправностей и каждому входу триггера соответствовал следующий список неисправностей. При этом текущий список содержит те неисправности, которые влияют на выход триггера в текущее время. Аналогично, следующий список содержит те не исправности, влияние которых достигло выходов комбинационной схемы, питающих триггера. Таким же образом, как распространяется влияние неисправностей в комбинационной логике, выполняется распространение влияния неисправностей для текущего списка. При изменении входного вектора неисправность может дать несколько событий. Все они распространяются вместе с влиянием неисправности текущего списка. Если влияние неисправности достигает входа триггера, то эта неисправность вносится следующий список. При изменении значений входного вектора значения сигналов передаются со входов на выходы триггеров. Аналогично соответствующий следующий список неисправностей становится текущим списком неисправностей. Как обычно, проверяемыми считаются те неисправности, влияние которых достигло внешних выходов схемы.

Покажем суть метода на примере схемы рис. 13.7, где моделируются две константные неисправности, отмеченные (1) и (2).

Рассмотрим моделирование этих несправностей на тестовой последовательности, состоящей из трех входных наборов. Результаты моделирования на первом наборе (11) представлены на рис. 13.7. Здесь начальное состояние тригера предполагается неопределенным имеет значение - $$u$$, текущий и следующий списки неисправностей пусты. Моделирование исправной схемы на этом наборе показывает, что ни одна из указанных неисправностей не активизируется. После моделирования на втором наборе (10), результаты которого показаны на рис. 13.8, обе неисправности активизируются. Влияние первой неисправности на рисунке обозначено $$D'(1)$$ и второй соответственно - $$D'(2)$$. Отметим, что только влияние первой неисправности достигает входа триггера и эта неисправность вносится в следующий список неисправностей. рис. 13.9 представляет результаты моделирования на следующем входном наборе (01). Здесь текущий список пополняется неисправностью $$D(1)$$, которая распространяется до внешнего выхода, что показывает ее проверяемость и она исключается из списка обрабатываемых неисправностей. Поскольку больше ни одна неисправность не распространяется до триггера, следующий список неисправностей является пустым.

Отметим, что подобным образом можно обрабатывать несколько (непересекающихся) различий сигналов. Дальнейшее развитие данный метод получил в параллельной реализации - PROOF , выполненной в [13.7], которая очень широко используется в промышленных симуляторах.

Ключевые термины:

Суперсписок неисправностей - связывается с вентилем схемы и включает в себя множество неисправностей, изменяющих значение сигналов на линии на противоположное.

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

Дифференциальный метод - основан на распространении различия сигналов в исправной и неисправной схеме.

Краткие итоги

Рассмотрен самый универсальный конкурентный (совместный) метод моделирования неисправностей на основе обработки суперсписков неисправностей. Изложен дифференциальный метод моделирования неисправностей на базе распространения различия сигналов в исправной и неисправной схеме.

В разделе 13.1 введено понятие суперсписка неисправностей, которое в отличие от дедуктивного метода связывается с элементом (а не линией) схемы и содержит неисправности, при которых значения сигналов отличаются от исправной схемы. Рассмотрены вопросы обработки распространения суперсписков в процессе моделирования и основные процедуры сужения и расширения суперсписков.

Раздел 13.2 содержит описание метода моделирования неисправностей "Test-Detect", который использует D-исчисление в многозначном алфавите для распространения различий сигналов в исправной и неисправной схеме.

Раздел 13.3 посвящен дифференциальному методу моделирования неисправностей, который также основан на распространении различий сигналов и является развитием "Test-Detect", но использует двоичный или троичный алфавит.

Вопросы и упражнения

Чем отличается суперсписок неисправностей конкурентного метода от списка неисправностей дедуктивного метода?

Приведите пример суперсписка неисправностей.

Что такое расширение суперсписка и когда оно возможно?

Что такое сужение суперсписка и когда оно возможно?

Выполните моделирование одиночных константных неисправностей конкурентным методом для приведенной схемы рис. 13.10 на тестовом наборе (11101). (рис 13.10) Схема для упражнения 5.

Сравните параллельный, дедуктивный и конкурентный метод по функциональным возможностям.

Сравните параллельный, дедуктивный и конкурентный метод по вычислительным ресурсам.

В чем суть метода "Test-Detect"?

Выполните моделирование константной неисправности =0 на выходе второго нижнего вентиля первого уровня методом "Test-Detect" для приведенной схемы рис. 13.10. на тестовом наборе (11111).

Чем отличается дифференциальный метод моделирования неисправностей от "Test-Detect".

Какие события обрабатываются в дифференциальном методе?

Для каких схем корректно можно применять дифференциальный метод?

Какие дополнительные списки необходимы при обобщении этого метода на схемы с памятью?