Информационный диагностический тест, близкий к минимальному (метод Синдееева)

Этот метод реализует безусловный алгоритм диагностики. Основой этого алгоритма является ТФН, у которой столбцы соответствуют всем возможным состояниям, а строки – всем возможным проверкам (проверка π _i означает контроль выхода z_i). Предполагаем, что все n состояний системы, состоящей из n блоков, равновероятны и сумма вероятностей состояний их отказа равна 1, т.е. проверки, как случайные события, образуют полную группу событий:

P₁=P₂=…=P_n= . (8)

Тогда с точки зрения теории информации неопределённость (энтропия) Н, создаваемая такой схемой для пользователя, в общем случае определяется с помощью формулы Шеннона:

,

где P_i – вероятность i – го события (вероятность отказа i – го блока

системы).

Для рассматриваемого случая из (8) получим формулу Хартли:

, (9)

Для определения состояния схемы необходимо провести эксперимент, состоящий в последовательном выборе не более m наиболее информативных проверок (m< n).

Каждая k – ая проверка π _k несет некоторое количество информации I относительно начального состояния (начальной энтропии Н₀) рассматриваемой схемы (системы).

I=H₀-H(π _k)=∆ H, (10)

где H(π _k) – средняя условная энтропия состояния схемы после проведения проверки π _k, k= .

Т.к. при проведении проверки π _k имеется только два возможных исхода (положительный π _k и отрицательный ), т.е. π _k=1 или =0 с вероятностями соответственно Р(π _k) и P(), то средняя условная энтропия Н(π _k) равна

H(π _k)= Р(π _k)H(π _k)+P()H(), (11)

где Н() и Н(π _k) – энтропия состояний схемы после выполнения проверки π _k соответственно для отрицательного и положительного её исходов.

Р(π _k)= , (12)

Р()= , k=1…n, (13)

где - число единиц в рассматриваемой k ^ой строке ТФН.

Тогда подставляя формулы (12) и (13) в формулу (11), а затем (11) в (10) получим с учетом (9):

. (14)

Информация по формуле (14) вычисляется для каждой строки ТФН. Первой для теста выбирается проверка π _k, которая приносит максимум информации. Если таких проверок несколько, то выбирается любая из них, что возможно, когда информация вычисляется для равновероятных событий (отказов блоков системы) по формуле Хартли.

Если вероятности состояний P(S_j) блоков устройства не одинаковы, то энтропия (неопределенность) в оценке состояния объекта диагностики (ОД) вычисляется по формуле Шеннона (1). В этом случае вероятность отказа P(S_j) j – го блока системы можно оценить по формуле

P_j= P(S_j)= ,

где - интенсивность отказов j – го блока, час^-1;

- интенсивность отказов системы, равное сумме интенсивностей отказов составляющих её блоков.

Строка ТФН, соответствующая лучшей по условию (3) проверке, перемещается на место первой строки ТФН и делит последнюю на две, в общем случае, неравные части, в одну из которых входят столбцы состояний S_j, которым соответствуют “0” в выбранной (лучшей на первом шаге) строке, а в другую – столбцы состояний, которым соответствуют “1” в выбранной строке. Выбранная на первом шаге лучшая по информативности строка больше не участвует в отборах на втором и последующих шагах формирования тестовых проверок.

Успешной (положительной) считается проверка, при которой выход контролируемого блока системы соответствует техническим условиям (ТУ) предприятия-изготовителя. Результаты успешной проверки обозначаются как диагностическая 1. В противном случае проверка считается неуспешной (отрицательной) и обозначается как диагностический 0 в ТФН и других документах.

Выбор второй наиболее информативной проверки проводится одновременно по двум полученным подТФН.

Второй выбирается проверка π _i, которая обладает наибольшей условной информацией I(π _k/π _i) относительно состояния, характеризуемого энтропией H(π _k) после первой выбранной проверки.

I(π _k/π _i)=H(π _k) - H(π _k/π _i) → max (15)

Средняя условная энтропия схемы после 2 ^ой проверки.

Н(π _i/π _k)= Р(π _i/π _k)H(π _i/π _k)+P( /π _k)H( /π _k)+

+Р(π _k/ )Н (π _i/ )+P( / )H( / ), (16)

где Р(π _i/π _k)= - вероятность второй успешной проверки после

успешной первой. (17)

P( /π _k)= - вероятность второй неуспешной проверки

после успешной первой. (18)

P(π _i/ )= - вероятность успешной второй после неуспешной первой проверки. (19)

P( / )= - вероятность неуспешной второй проверки после неуспешной первой. (20)

l₁ и l₂ – число единиц в i-ой строке подТФН №2.1 и подТФН №2.2 соответственно, первая из которых соответствует l-единицам, а вторая – (n-l) – нулям в k ^ой – строке исходной ТФН. Из формулы (9) следует

H(π _i/π _k)= , H( /π _k)= , H(π _k/ )= ,

H( / )= .

Тогда средняя условная энтропия после 2 ^го шага

(π _i/π _k)= . (21)

Информация после 2 ^го шага для i-той строки будет равна разности выражения в квадратных скобках в уравнении (14) и выражения (21).

Вторая лучшая проверка π _i из группы наиболее информативных проверок, записывается второй в исходной ТФН и не участвует в отборе на третьем и последних шагах и т.д.

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

Если отбор проверок для теста заканчивается на m-ом шаге (m< n), то m строк, переставленные вверх по указанным выше правилам в исходной ТФН, автоматически формируют таблицу кодов неисправностей. Причем m – разрядный двоичный код каждой одиночной неисправности читается сверху вниз в каждом столбце ТФН с переставленными вверх наиболее информативными строками (проверками), образующими тестовый набор проверок.

На практике выполняются проверки состояний выходов блоков, вошедших в тестовый набор, в той последовательности, в какой они указаны в тесте. Результат каждой проверки фиксируется в виде диагностической 1 или 0. Комбинация результатов проверок, образующая двоичный код, сравнивается с таблицей кодов неисправностей, которая, как указано выше, автоматически получается из исходной ТФН и состоит из m наиболее информативных строк.

Пример реализации комбинационного метода поиска диагностики неисправностей, реализующего безусловный алгоритм диагностики по методу Синдеева.

Найти информационный тест и таблицу кодов неисправностей для схемы рис.1, в которой имеет место одиночный отказ.

1. Диагностические оценки входных и выходных сигналов:

Z₅=0 – const, x1=1 – const, x2=1 – const.

Рис.15

2. Найдем информацию, которую может принести каждая проверка на

первом шаге. В этом случае

I(π _k)=H₀ - log₂n,

где H₀ – исходная энтропия.

H₀=log₂5=lg5/lg2=3.332 lg5=2.329бит.

ТФН, соответствующая ФДМ на рис.15 представлена табл. 2.

Таблица 2

ТФН для информационного теста

ТФН 2.1 ТФН 2.2

Определим среднюю условную энтропию Н(π ₂) схемы, которую получим в результате проведения проверки π ₂. Согласно (4) и (7)

H(π _k)= .

Для второй проверки

Н(π ₂)= бит

Тогда информация I(π ₂), полученная в результате проведения проверки π ₂, составит:

I(π ₂)=H₀-H(π ₂)

I(π ₂)=2.329-1.354=0.975 бит.

I(π ₁)= бит,

I(π ₃)= бит,

I(π ₄)= бит.

Столбец с вычисленными количествами информации поместим 6-ым в таблицу 1 функций неисправностей (ТФН), соответствующую функционально-диагностической модели (ФДМ) устройства на рис.1. На пересечении j-го столбца и i-й строки π _i в таблице 1 ставится “1”, если при возникновении одиночной неисправности в j-ом блоке устройства сигнал на выходе i-го блока остается соответствующим техническим условиям (ТУ) его эксплуатации и ставится “0” в противном случае.

Первой в тест выбираем проверку π ₂ (контроль выхода блока 2), т.к. она приносит максимум информации и “удачно” делит исходную ТФН на две неравные части ТФН 2.1 и ТФН 2.2, первой из которых соответствуют нули в выбранной строке π ₂, а второй - “1”.

3. На втором шаге определим среднюю условную энтропию после второй проверки, которая включает оставшиеся проверки π ₁, π ₃, π ₄. Например,

H(π ₁/π ₂)= бит.

Тогда I(π ₁/π ₂)= =1.354-0.8=0.554 бит.

Аналогично H(π ₃/π ₂) =0.4+0.4=0.8 бит.

I(π ₃/π ₂)=1.354-0.8=0.554 бит.

Затем H(π ₄/π ₂)= =0.4 бит,

Следовательно I(π ₄/π ₂)=1.354-0.4=0.954 бит.

Вычисленные количественные оценки информации на втором шаге I(π _i/π _k) поместим в 7-ом столбце табл. 2.

Анализируя содержимое этого столбца, на втором шаге выбираем 4 ^ую проверку π ₄ т.к. она несет наибольшее количество информации относительно энтропии, оставшейся после 1 ^ой, выбранной нами проверки π ₂.

4. Перед выбором третьей информативной проверки перенесем на вторую строку исходной ТФН содержимое строки π ₄, соответствующей выбранной проверке. Указанная ситуация отображена в табл. 3, где место первой строки занимает информация строки (проверки) π ₂, выбранной на первом шаге. Тогда остаются две альтернативные проверки π ₁ и π ₃. Содержимое строк π ₁ и π ₃ распределяется в таблице 2 по четырем подТФН, причем ТФН 3.1 и ТФН 3.2 строятся на базе ТФН 2.1, а ТФН 3.3 и ТФН 3.4 - на базе ТФН 2.2.

Таблица 3.

ТФН для выбора 3-ей проверки теста

ТФН 3.1 ТФН 3.2 ТФН 3.3 ТФН 3.4

ТФН 2.1 ТФН 2.2

ТФН 3.2, 3.3 и 3.4 вырождаются в столбцы, что облегчает выбор проверок и указывает на быстрое завершение формирования теста.

Информация, доставляемая третьей проверкой I(π _n/π _m/π _k) определяется по формуле:

I(π _n/π _m/π _k)=H(π _m/π _k)-H(π _n/π _m/π _k).

Например, если третьей будет проверка π ₁, то

H(π ₁/π ₄/π ₂)=

т.е. I(π ₃/π ₄/π ₂)= 0.4-0 = 0.4 бит.

Если третьей будет π ₃, то

H(π ₃/π ₄/π ₂)=

бит.

Следовательно, I(π ₃/π ₄/π ₂)=0.4-0.4=0 бит, т.е. проверки надо прекратить!

Располагая проверки π ₂, π ₄, π ₁ последовательно друг за другом, получим таблицу кодов неисправностей с трёхразрядными двоичными кодами одиночных неисправностей, которые могут иметь место в устройстве на рис.15. Такое расположение проверок сформировано в табл. 2. Код неисправности 1-го блока (состояние устройства S₁) составляет 010, код состояния S₂ – 011, код состояния S₃ – 001, код состояния S₄ – 101 и код состояния S₅ –111.

Выполняя на практике последовательно проверки π ₂, π ₄, π ₁ (проверяя выходы Z₂, Z₄, Z₁) и фиксируя результаты проверок в виде диагностических “0” или “1”, получают трёхразрядную двоичную комбинацию и идентифицируют неисправность в устройстве, сравнивая полученную комбинацию с таблицей кодов неисправностей.

1.10. Метод критерия различимости – комбинационный метод, реализующий безусловный алгоритм диагностики

1) Постановка задачи

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

2) Таблица неисправностей – используется для представления результатов генерирования тестов, является двух мерным массивом, имеющем по одной строке на каждую неисправность и по одному столбцу на каждый тест. Для элемента таблицы :

=1, если -я неисправность обнаруживается -м тестом и

=0 – в противном случае.

Строка называется отображениями неисправности и является вектор–строками, - отображение -й неисправности. Два отображения неисправности и различимы , если для некоторого , где - номер теста. Таким образом задача трансформируется в задачу нахождения минимального набора столбцов таблицы так, чтобы каждая строка, соответствующей подтаблицы имела бы по крайней мере одну «1». Чтобы различать все неисправности необходим минимальный набор столбцов, соответствующий вышеизложенным требованиям и имеющий все различимые строки.

3) Метод критерия различимости.

Основная идея – в приписывании весов отдельным тестам. Веса отражают относительную способность тестов различать неисправности.

На основе весов отбираются тесты для получения эффективного набора тестов.

Вес теста определяется как и число пар неисправностей, которые он различает:

,

где и - число соответственно «0» и «1» в -м столбце таблицы

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

Пусть кандидат на () элемент набора и пусть и - число «0» и «1» в -м столбце блока . Тогда после -го шага вес для будет равен:

Тест, для которого -max, выбирается как элемент набора тестов. Отбор тестов продолжается до тех пор, пока разделение неисправностей перестанет приносить дальнейшее улучшение, т.е. до тех пор, пока веса всех неиспользованных «тестов» не станет равное «0» (не станет «0» или «1» )