Данные методы сводятся к решению известных задач на графах.
В частности поиска множества связных вершин, где вес ребра принимает определенное значение.
Как правило данные задачи являются NP — полными. Соответственно не используются в системах реального времени.
NP - полной называется задача, которая не может быть решена за номинальное время.
O(n^2), O- определяет верхнюю границу сложности в качестве аргумента в данном случае указывается величина пропорционально которой изменяется время решения.
O(n) — эта задача имеет линейную сложность.
К сложным задачам относят задачи в которых аргумент нельзя представить в виде полинома.
Если ВС является системой реального времени, то накладываются жесткие ограничения на время проведения процедур связанных с обслуживанием данных систем.
Алгоритмы дешифрации в системах участвуют свойства системы в частности — Диагностическая модель (ДМ).
Синдром исправной системы содержит только 0е элементы, поэтому дешифрацию целесообразно проводить только при наличие в синдроме элемента не = 0!
1.ДМ (0,1,0,0):
Данная ДМ не симметрична. Из множества ЭМ выбираются такие, которые имеют входящую связь с весом = 1.
1. Такие машины относятся к неисправным.
2. Алгоритм:
3. Все ЭМ в составе ВС помечаются как исправные
4. Выбирается элемент из синдрома S_ij
5. Если выбранный элемент = 0, то выполняется переход к шагу 5
6. ЭМ U_j помечается как неисправна
7. Если выбраны не все элементы синдрома, то переходим на шаг 2
8. Конец алгоритма
Порядок выбора элементов синдрома ничем не ограничивается. Соответственно можно выяснить состояние ЭМ по мере поступления элементов синдрома.
То есть не надо дожидаться окончания всех диагностических проверок!
Алгоритм выполняется за 1 цикл, поэтому трудоемкость алгоритма дешифрации пропорциональна количеству элементов синдрома.
m <= n*(n-1) < n^2 - этот алгоритм обладает низкой трудоемкостью (O(n^2)).
Так же для выполнения этого алгоритма требуется малый объем памяти.
2.ДМ (0,1,0,1):
Данную ДМ называют идеальной, так как состояние контролируемой машины однозначно определяется правильно, независимо от состояния контролирующей.
Для определения технического состояния можно использовать тот же алгоритм что и для ДМ(0,1,0,0), при этом неисправность ЭМ в общем случае будет обнаружена даже ранее. Оценка трудоемкости такая же.
3.ДМ (0,1,0,x):
Можно использовать тот же самый алгоритм, то есть при появлении «1» данная модель будет как ДМ (0,1,0,1), а при появлении «0» как ДМ (0,1,0,0).
4.ДМ (0,1,1,0):
Это симметричная модель. Для данной модели характерно получение единичного результата тех проверок в которых либо проверяемая либо проверяющая машина неисправна.
Необходимым и достаточным условием t — диагностируемости является связность ДГ.
Поэтому перед работой алгоритма исключаются все дуги ДГ без которых граф остается связным.
Для этой задачи можно использовать алгоритм Прима либо Краска.
Сначала строится граф: G_0 = ( U, T_0 ) - является подграфом G = ( U, T ), где T — множество связей.
Подграф образуется путем удаления дуг ( U_i, U_j ) взвешанных единичным весом S_ij = 1.
При этом подграф состоит из таких компонентов связности, где состояние вершин входящих в 1у компоненту одинаково. Каждая компонента связности окружена компонентами противоположного состояния, то есть если одна компонента содержит только исправные ЭМ, то соседние с ней компоненты содержат неисправные.
Компоненты соседствующих друг с другом делятся на четные и не четные.
Если количество вершин в четных слоях обозначено как n1 <= t, то все ЭМ четных слоев - неисправны, а не четных — исправны.
Если n1 > t, то ЭМ четных слоев исправны, а нечетных — неисправны.
5.ДМ (0,1,1,1):
Алгоритм:
1й этап:
1. Присвоить F пустое значение ( F -функция состояния ). Если элемент входит туда с инверсией, то машина соответствующая элементу - неисправна, если без — исправна.
2. Если нет синдрома S_ij =0, то выполнить переход к шагу 5
3. Добавить к F конъюнкцию не инвертированных значений b_i, b_j
4. F = F b_i b_j ( машины i и j исправны )
Выполнить переход на шаг 2
2й этап:
1. Выбрать очередной элемент S_ij = 1
2. Если b_i присутствует в F без инверсии, то к F добавляем конъюнкцию b_j с инверсией F = F b_j и выполняем переход к шагу 8
3. Если b_j присутствует в F без инверсии, то к F добавляем конъюнкцию b_i с инверсией F = F b_i и выполняем переход к шагу 8
4. Если не все элементы синдрома выбраны, то выполнить переход к шагу 5
5. i = 1
6. Если b_i не входит в F, то дополнить F b_i: F = F b_i
7. i = i+1
8. Если i <= n, то выполнить переход к 10
9. Конец алгоритма
Для каждого элемента синдрома производится не более 1го изменения логического выражения F. При этом размер выражения не превышает 1го терма.
Количество термов определяется количеством конъюнкций объеденных через дизъюнкцию.
Каждый элемент синдрома рассматривается 1 раз. На последнем этапе работы выполняется дополнительные выражения переменными без инверсий в виде n итераций цикла.
b_i