Сокращение диагностической информации при помощи масок

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

Назовем точкой проверки пару номер тестового воздействия:номер выхода. Тогда маской \[ h \] назовем любую совокупность точек проверки.

Пусть имеется некоторое разбиение множества \[ S \] и пусть \[ S_j \] - элементы этого разбиения. Поставим в соответствие каждому подмножеству \[ S_j \] некоторую маску \[ h_j \] . Множество всех \[ h_j \] обозначим через \[ H \] . Построим по списку полных реакций (СПР) и множеству масок \[ H \] таблицу следующим образом. Каждая строка таблицы соответствует техническому состоянию. Содержимое строки таблицы, соответствующей состоянию \[ s_i\in S_j \] , будут составлять значения точек проверки из \[ h_j \] , взятые из строки СПР, соответствующей \[ s_i \] , в порядке их следования в СПР. Построенную таким образом таблицу будем называть (по аналогии с [1]) словарем полной реакции, построенный по маскам из \[ H \] , и обозначать \[ СПР_H \] . Маску \[ h_j \] будем называть индивидуальной маской для каждого состояния из \[ S_j \] , а множество \[ H \] - множеством индивидуальных масок.

Например, построим СПР для СПР из табл. 27.5, если \[ S_1=\{s_0\} \] , \[ S_2=\{s_1\} \] , \[ S_3=\{s_2\} \] , \[ S_4=\{s_3,s_4\} \] , \[ S_5=\{s_5\} \] , \[ S_6=\{s_6\} \] , \[ S_7=\{s_7\} \] , \[ S_8=\{s_8\} \] , а элементы множества \[ H \] : \[ h_1=\{1:1,1:2,2:1\} \] , \[ h_2=\{1:2,2:1\} \] , \[ h_3=\{1:1,3:1\} \] , \[ h_4=\{1:2,3:1,3:2\} \] , \[ h_5=\{3:1,3:2,4:1\} \] , \[ h_6=\{4:1\} \] , \[ h_7=\{3:1,3:2\} \] , \[ h_8=\{1:1,3:1\} \] . Элементы СПР, выбираемые с помощью масок из \[ H \] , выделены прямоугольниками в СПР в табл. 29.1, а сам словарь неисправностей \[ СПР_H \] приведен в табл. 29.2.

Заметим, что представление диагностической информации в виде \[ СПР_H \] предполагает наличие полной таблицы СПР, а также множества масок \[ H \] и указания соответствия между \[ s_i \] и \[ h_j \] .

Содержательно выделение информации с помощью маски можно пояснить следующим образом. Полную СПР будем интерпретировать как прямоугольную таблицу с пронумерованными строками и столбцами. В каждой клетке СПР, находящейся на пересечении \[ i \] -ой строки и \[ j \] -го столбца, находится двоичная последовательность длины \[ k \] , где \[ k \] - число выходов диагностируемого ЦУ.Эта последовательность есть реакция ЦУ в состоянии \[ s_i \] на \[ j \] -ый тестовый набор. Тогда маска \[ h_i \] соответствует "окошечкам" в сплошном битовом шаблоне \[ i \] -ой строки, которые следует "прорезать" , чтобы увидеть выделяемые этой маской биты реакции ЦУ на диагностический тест.

В процессе диагностирования предполагается получение выходной реакции объекта диагностирования на диагностический тест, после чего на эту реакцию накладываются поочередно маски \[ h_j \] , а результат наложения сравнивается со значениями в \[ СПР_H \] для всех \[ s_i\in S_j \] . Те из \[ s_i \] , для которых произошло совпадение, заносятся в СПН.

Пусть в рассматриваемом примере объект находится в техническом состоянии \[ s_6 \] . В этом случае выходная реакция объекта - \[ 01 00 01 00 \] . Ни одна из масок, кроме \[ h_6 \] , не приведет к занесению в СПН ни одного состояния. После наложения маски \[ h_6 \] будет получена последовательность 0 и в СПН будет внесено состояние \[ s_6 \] . Результат диагностирования объекта есть СПН, равный \[ \{s_6\} \] .

Очевидно, что если СПР обладает свойством различения всех неисправностей, то найдется множество индивидуальных масок таких, что \[ СПР_H \] будет обладать свойством различения всех неисправностей.

Если множество \[ H \] содержит только одну маску для всех технических состояний из \[ S \] , то такую маску называют единой (общей) маской.

Рассмотрим, например, диагностический тест для схемы \[ С17 \] и множество \[ H \] , содержащее одну маску \[ h=\{1:2,2:1,3:1,3:2,,4:1\} \] . В этом случае \[ СПР_H \] будет выглядеть так, как показано в табл. 29.3.

Использование единой маски имеет некоторые преимущества в процессе диагностирования объекта. Действительно, если используется единая маска , то при получении выходной реакции устройства можно сразу отфильтровывать с использованием маски \[ h \] последовательность выходных значений и не сохранять при этом всю выходную реакцию. Более того, после получения очередного "отфильтрованного" с помощью маски выходного значения можно сразу формировать и вносить изменения в СПН. Сначала в СПН вносятся все технические состояния объекта, но при получении очередного бита информации происходит удаление из СПН состояний, не соответствующих значению данного бита.

Что касается объема сокращенного с помощью масок словаря неисправностей, то в случае единой маски его величина равна \[ |S|M \] , где \[ M \] - количество точек проверок, составляющих маску. В случае сокращения ДИ с помощью множества индивидуальных масок объем словаря составит

где \[ b' \] - количество бит, необходимых для отделения данных по одному техническому состоянию от остальной информации, \[ M' \] - суммарное количество точек проверки по всем маскам в множестве \[ H \] , \[ M'' \] - суммарное количество точек проверки по всем маскам, с учетом их кратности.

Заметим, что с помощью масок можно проводить сокращение ДИ, представленной также и в виде ТН. В этом случае элементом маски \[ h \] выступает не точка проверки, а номер тестового вектора, информация об обнаружении неисправности которого заносится в сокращенную таблицу. Таблицу, построенную в результате сокращения ТН с помощью набора масок \[ H \] , будем называть таблицей неисправностей, построенной по маскам из \[ H \] ,и обозначать через \[ TH_H \] .

В связи со сказанным выше, подход к сокращению ДИ при помощи масок приводит к необходимости исследования задач поиска различных масок. Остановимся на этом немного подробнее.

Так, в работе [1] формулируются три задачи, касающиеся сокращения ДИ с помощью масок:

1. Для каждого технического состояния найти такую индивидуальную маску \[ h_i \] , чтобы объем СПР ( \[ H=\{h_0\ldots h_{|S|}\} \] , \[ S_i=\{s_i\} \] ) был минимальным и разрешающая способность диагностирования с помощью \[ СПР_H \] не ухудшалась по сравнению с разрешающей способностью диагностирования с помощью СПР.
2. Для множества технических состояний \[ S \] найти такую единую (общую) маску \[ h \] , чтобы объем \[ СПР_H \] ( \[ H=\{h\} \] ) был минимальным и разрешающая способность диагностирования с помощью \[ СПР_H \] не ухудшалась по сравнению с разрешающей способностью диагностирования с помощью СПР.
3. Для множества состояний \[ S \] определить такое его разбиение \[ S_1,\ldots,S_l \] и такой набор масок \[ H=\{h_1,\ldots,h_l\} \] , чтобы объем \[ СПР_H \] был минимальным и разрешающая способность диагностирования с помощью СПР не ухудшалась по сравнению с разрешающей способностью диагностирования с помощью СПР.

Сформулированные задачи принято называть задачами минимизации ДИ при помощи масок [2,3]. В работах [3,4,5,6] рассматриваются методы точного аналитического решения первой, а в работе [6] еще и второй из сформулированных задач.

В ряде случаев для решения задач минимизации применимы методы, предложенные для оптимизации безусловных алгоритмов диагностирования [7].

В работе [3] сформулирована еще одна задача - задача оптимизации: для множества \[ S \] определить разбиение \[ S_1,\ldots,S_l \] и набор масок \[ H=\{h_1,\ldots,h_l\} \] , чтобы объем \[ СПР_H \] не превышал заданной величины \[ Z \] и изменение разрешающей способности диагностирования с помощью \[ СПР_H \] по отношению к разрешающей способности диагностирования с использованием СПР было минимальным. Здесь же рассматриваются варианты точного аналитического решения этой задачи.

В работах [3,8] отмечается, что предложенные варианты точных решений задач поиска масок связаны с частичным перебором, и требуют большого объема вычислений. При значительном увеличении количества неисправных модификаций, характерного для современных устройств, а также при увеличении длины диагностического теста такие варианты решений становятся неприемлемыми из-за больших временных затрат. Выходом из сложившейся ситуации является замена точного решения приближенным. В тех же работах, а также в работе [2], предлагаются методы приближенного решения задачи минимизации и оптимизации объема \[ СПР_H \] , когда \[ H \] - множество индивидуальных масок.

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

Имеющийся опыт исследования многих оптимизационных прикладных задач показывает, что для их решения эффективным математическим аппаратом являются генетические алгоритмы (ГА). В лекции 25 была показана полезность ГА и их приемлемость с точки зрения временных затрат применительно к решению задач синтеза тестов. Далее мы убедимся, что и для различных модификаций задач поиска масок ГА также дают прекрасные результаты.

В дальнейшем изложении предполагается, что читатель знаком с содержанием лекции 25, где были определены основные понятия и термины,используемые в генетических алгоритмах, а также описан простой генетический алгоритм (ПГА).

Кратко напомним необходимые нам сведения о ПГА, содержащем следующие этапы:

• Формирование начальной популяции;
• Подбор особей в родительские пары;
• Получение дочерних особей с помощью оператора репродукции (скрещивания);
• Выполнение оператора мутации;
• Отбор особей для формирования следующего поколения;
• Проверка условий окончания процесса эволюции.

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

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