35. Вероятностное тестирование

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

Два способа организации вероятностного тестирования приве­дены на рис. 4.61 и 4.62. Первый способ использует эталонную схе­му (см. рис. 4.61). Наборы случайного теста, вырабатываемые ге­нератором, поступают на входы испытуемой и эталонной схем. Их реакции сравниваются устройством сравнения. В случае их расхож­дения делается вывод о неисправности испытуемой схемы. Второй способ отличается методом сравнения выходных реакций. В этом случае реакция испытуемой схемы приводится к компактному виду с помощью схемы сжатия. Результат сравнивается со сжатым эта­лоном.

В отличие от детерминированного тестирования, когда обна­ружение данной неисправности гарантированно, при случайном тестировании это происходит с некоторой вероятностью. Пусть испытуемая схема имеет п входов и пусть Е есть множество последовательностей из k входных векторов, которые могут быть при­ложены к схеме. Каждый входной вектор может быть одним из 2^п векторов. Тогда Е содержит 2^nk элементов.

Предположим, что все входные векторы вырабатываются гене­ратором случайных наборов с одинаковой вероятностью и что появление векторов в последовательности независимо друг от дру­га. Пусть E_i – множество последовательностей из Е, которые об­наруживают неисправность i. Мощность множества E_i равна σ_i.

Вероятность того, что один входной вектор не обнаруживает неис­правность i равна 1 – σ_i / 2^п. Вероятность того, что случайная входная последовательность длины k обнаруживает неисправность i:

Формула позволяет получить ответ на следующий воп­рос. Дана схема и требуемая вероятность обнаружения данной не­исправности. Какова должна быть длина случайного теста?

Рис. 4.61. Схема вероятностного тестирования

Рис. 4.62. Схема вероятностного компактного тестирования

36. Диагностирование дискретных устройств с памятью. Построение диагностических и проверяющих тестов

Многотактные схемы (рисунок 1) или схемы с памятью являются более сложными для диагностирования объектами, чем комбина­ционные схемы. Многотактная схема (МС) содержит блок памяти (БП) и логический преобразователь (ЛП). Элементы памяти (ЭП), входящие в БП, сохраняют информацию о предыдущих входных воздействиях. ЛП является комбинационной схемой, которая вычис­ляет значения выходов и состояния ЭП в каждом такте работы МС.

Рисунок 1 – Структура МС

При диагностировании многотактной схемы необходимо обес­печить проверку исправного состояния каждого ЭП и каждого ло­гического элемента, входящего в ЛП. Логический преобразова­тель проверяется как комбинационная схема, но при этом необхо­димо учитывать, что пере­менные y₁, …, y_k , поступа­ющие на вход ЛП, не явля­ются независимыми (как пе­ременные x₁, …, x_n). В дан­ный момент времени они определяются состояниями ЭП. Поэтому возникает следующая задача. Если из­вестен входной набор, на котором обнаруживается неисправность некоторого ЛП, то, для того чтобы обеспечить ввод этого набора, необходимо предварительно установить ЭП в состояния, соответствующие этому набору. Другими словами, проверка элемента требует предваритель­ной подачи некоторой установочной последовательности входных на­боров. Так как каждый ЭП имеет свою установочную последователь­ность, то объединение их в общий тест является достаточно сложной задачей. Кроме того, имеет место проблема установки схемы в исход­ное состояние, из которого начинается процедура диагноза. В неко­торых МС возможно увеличение числа ЭП в результате возникнове­ния константных неисправностей, а также появление критических со­стязаний, отсутствующих в исправной схеме.

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

Рисунок 2 – Многотактная схема

Работу многотактной схемы отображают при помощи таблицы переходов ТП. Для ее построения составляют функции, описыва­ющие схемы включения внутренних элементов памяти (реле У₁ и У₂) и выходную схему (включение лампы Z). Для данной схемы:

По полученной системе функций составляют кодированную ТП (таблица 1), которая содержит 2^п граф (п - число входов схемы) и 2^k строк (k - число внутренних элементов памяти). Каждая графа соответствует одному из входных состояний схемы. В данном случае имеется два входных состояния: х = О (кнопка х не нажата) и х = 1 (кнопка х нажата). Строки соответствуют внутренним состояниям схемы, которые определяются состояниями ЭП. Рассматриваемая схема имеет 4 внутренних состояния: 00,01, 11, 10. Каждому состоя­нию сопоставлено десятичное число 1, 2, 3, 4. На пересечении графы и строки в клетке ТП указано внутреннее состояние, в кото­рое переходит схема, если она находилась в состоянии, соответ­ствующем данной строке, и на вход схемы поступил входной на­бор, соответствующий данному столбцу.

Таблица 1

S	y1, y2	X
		0	1
1	00	00,0	01,0
2	01	11,1	01,1
3	10	11,1	10,1
4	11	00,0	10,0

Состояния, в которых находится схема, вычисляются по урав­нениям системы. Определяются значения функций У₁ и У₂ при подста­новке переменных х, У₁ и Y₂ соответствующих строке и графе, ко­торым принадлежит элемент таблицы ТП, соответствующий дан­ному состоянию.

От кодированной ТП (см. таблицу 1) осуществля­ется переход к ТП, в кото­рой внутренние состояния обозначаются цифрами (таблица 2), а от нее – к графу переходов (рисунок 3). В последнем вершины соответствуют состояниям схе­мы, а дуги - переходам между состояниями. Значение входа, под воздействием которого осуществляется переход, указывает­ся над дугой. Из таблицы 1 видно, что значение выхода полнос­тью определяется внутренним состоянием схемы. На графе пе­реходов значения выходов указаны под обозначениями внутрен­них состояний.

Таблица 2

S	X
	0	1
1	1,0	2,0
2	3,1	2,1
3	3,1	4,1
4	1,0	4,0

Рисунок 3 – Граф переходов

При помощи таблицы переходов или графа переходов можно моделировать работу многотактной схемы на любой последова­тельности входных наборов. В табл. 5.3 показан результат работы рассматриваемой схемы на входной последовательности 010101, подаваемой за шесть тактов.

Таблица 3

Такт t	Входной набор X	Внутреннее состояние			Выход Z
		S	y1	y2
1	0	1	0	0		0
2	1	2	0	1		1
3	0	3	1	1		1
4	1	4	1	0		0
5	0	1	0	0		0
6	1	2	0	1		1

Первый такт отводится для установки схемы в исходное состоя­ние. В данной схеме, которая осуществляет управление лампой Z от одной кнопки Х, в качестве исходного состояния выбирается случай, когда кнопка X не нажата, реле У₁ и У₂ выключены, а лам­па Z не горит (см. рисунок 2). В таблице указаны внутренние состоя­ния, в которые переходит схема в каждом такте работы, и значе­ния выхода. Так как при диагностировании наблюдаются только вхо­ды и выходы устройства, то работа многотактной схемы описывает­ся входной-выходной последовательностью (ВВП):010101 – 011001.

Каждая неисправность превращает исправную схему в неисправ­ную схему, которая описывается собственной таблицей переходов. Последняя строится так же, как и ТП исходной схемы. ВВП обнаруживает неисправность N_i, если ВВП неисправной схемы, имеющая ту же входную последовательность, от­личается от нее хотя бы в одном такте выходной последовательности.

Для МС может быть построена проверяющая ВВП, на которой обнаруживаются все неисправности схемы из заданного списка. Тривиальная проверяющая ВВП строится следующим образом. Рассматривается граф переходов схемы. Выбирается исходное со­стояние схемы, реализуемое в первом такте ВВП. Составляется ВВП с выполнением следующего условия. Если граф переходов содержит переход S_i→S_f (S_i≠S_f) под воздействием входного набо­ра a_r, то этот переход должен моделироваться хотя бы в одном так­те ВВП. В том случае, когда переход S_i→S_f осуществляется под воздействием нескольких входных наборов, то моделироваться должен каждый случай перехода. Переходы S_i→S_j моделируются в ВВП автоматически. Минимальное число тактов ВВП

Где – множество индексов дуг в графе переходов; – число входных наборов, приписанных дуге с индексом p.

Составляется список неисправностей схемы, относительно ко­торых строится тест. В него включаются неисправности ЭП и элементов ЛП. Последний рассматривается как комбинацион­ная схема, в которой выделяются множества эквивалентных и импликантных неисправностей.

Для каждой неисправности из полученного списка составляет­ся ТП, описывающая работу неисправной схемы, и вычисляется ВВП, соответствующая последовательности. Составляется таблица выходных последовательностей, в которой вы­писываются ВВП исправной схемы и всех ее неисправных модифи­каций. В таблице выходных последовательностей осуществляется сравнение столбца, соответствующего исправной схеме, со всеми столбцами неисправностей. Если столбцы не совпадают, то дан­ная неисправность обнаруживается ВВП; в противном случае не обнаруживается. Составляется множество необнаруживаемых не­исправностей. Так как ВВП моделирует все возможные перехо­ды в многотактной схеме, то число таких неисправностей невели­ко. Последовательно рассматривается каждая необнаруживаемая не­исправность. Удлиняется ВВП для их обнаружения.

Для того, чтобы различать две неисправности друг от друга, необходимо подать такую входную последовательность, для которой выходные последовательности будут различны при этих неисправностях. Если же существуют не­различимые неисправности, которые не являются эквивалентны­ми, то соответствующая ВВП(входная-выходная последовательность) удлиняется.