русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 812; Нарушение авторских прав


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

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

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

Как правило данные задачи являются 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 итераций цикла.

O(n^2+n) — трудоемкость.



<== предыдущая лекция | следующая лекция ==>
Аналитический метод дешифрации синдрома | Планирование работы ОУВС


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.