14. Графовый метод дешифрации синдрома

Данные методы сводятся к решению известных задач на графах.

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

Как правило данные задачи являются NP — полными. Соответственно не используются в системах реального времени.

NP - полной называется задача, которая не может быть решена за номинальное время.

O(n^2), O- определяет верхнюю границу сложности в качестве аргумента в данном случае указывается величина пропорционально которой изменяется время решения.

O(n) — эта задача имеет линейную сложность.

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

15. Алгоритмы ускоренной дешифрации синдрома

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

Алгоритмы дешифрации в системах участвуют свойства системы в частности — Диагностическая модель (ДМ).

Синдром исправной системы содержит только 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, то ЭМ четных слоев исправны, а нечетных — неисправны.