Статический анализ оптимального алгоритма обнаружения
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
комбинации РЖ, РЖРЖ, РЖРЖРЖ, IV):
- начальное состояние, которому также ставим в соответствие комбинации выполнения логики обнаружения конца пачки;
- поступила одна единица, т.е. комбинация ;
- поступила комбинация ;
- поступила комбинация : - это состояние, когда выполненная логика обнаружения начала пачки, итак, этому состояни отвечают также комбинации и ;
- поступила комбинация ;
- поступила комбинация ;
- поступила комбинация ;
- поступил один нуль после выполнения логики обнаружения начала пачки, т.е. комбинация ;
- поступила комбинация .
На основе выделенных состояний строятся основные ветви графа. Поскольку появление единицы и нуля - события случаю и характеризуются вероятности их соответственно и (формула 1.13), то переходы автомата с одного состояния в другое будут происходить также случайно. Строить граф удобно последовательно для каждой коньюнкции отдельно, начиная, например, с первой, учитывая все заданные соответствия состояния и комбинации сменных , что поступают. После построения ветви графа для первой коньюнкции строится ветвь для второй коньюнкции с учетом общих состояний первой и второй коньюнкции. Потом для третьей коньюнкции аналогично, учитывая общие части уже построенных ветвей.
На рис.1.8 изображенная основная часть графа, построенная согласно указанной последовательности. Состояния 1, 2, 3 отображают коньюнкции , станы 1, 4, 5, 6 отображают коньюнкции , состояния 1, 2, 6, 3 - , а состояния 7, 8, 0 - .
На переходах графа обозначения ( ) указывают вероятность данного перехода, а 1(0) - за какими сигналами осуществляется данный переход.
В таком виде граф незаконченный, так как не из всех состояний есть переходы за каждым видом входного сигнала. Например, из состояния 4 есть переход только по сигналу "1", а по сигналу "0" переход не определен, хотя "0" может поступить и в то время, когда автомат находится в состояни 4. Т.е. состояние 4 не определен, в отличие от состояния 1, где есть реакция и на единицу, и на нуль. Итак, граф нужно доопределить.
Доопределение графа состоит из добавления переходов состояния, который имеет неполный их состав. К неопределенным относятся 0, 3, 4, 5, 6, 7, 8-и состояния. Адрес доопределенного перехода устанавливается, исходя из заданных логик обнаружения. Например, если в состояние 4 прийдет нуль, то, с учетом первой единицы, сформируется в данный момент комбинация 100, и уже не может быть логика обнаружения 3/4, независимо от вида сигнала на следующей 4-и позиции (1001 и 1000 означает невыполнение логики), поэтому нужно при поступлении комбинации 100 начинать заново обнаруживать начало пачки, т.е. переходить в состояние "0". Другая ситуация складывается, если в состояние 5 поступил "0", это означает, что будет получена комбинация 1010, т.е. логика 3/4 не выполненна. Если перейти с 5-го состояния в 0-и, то вся эта информация будет утрачена. В то же время, если сохранить в составе этой комбинации последние 10, то за два следующих шага, если поступят две единицы, логика обнаружения будет выполнена (1011).
Сохранить указанную информацию можно, если перейти с 5-го в 4-и состояние, который и нужно сделать при доопределении (101011). Таким образом, доопределить состояние необходимо с учетом заданных критериев обнаружения, избегая потери информации. На рис.2.9 изображен полный граф, где пунктирные линии показывают доопределенные переходы.
Полученный граф со случайными переходами отображает в абсолютном виде процесс работы логического обнаружителя, физическая реализация которого может быть разной. Как правило, на переходах обозначаются только вероятности переходов и .
Используя граф, можно изобразить автомат в виде матрицы переходных вероятностей (стохастические матрицы переходов). Матрица переходных вероятностей для автомата, который рассматривается, имеет вид (табл. 2.1):
Таблица
Для построения матрицы необходимо из графа определить для каждого состояния адреса переходов и в соответствующие клеточки матрицы записать вероятности переходов по этим адресам. Например, из состояния 0 можно перейти с вероятностью в это же состояние и с вероятностью в состояние 1; из состояния 1 перейти в состояние 2 с вероятностью и в состояние 4 с вероятностью , и т.п.. Строки матрицы можно рассматривать как входы, а столбцы - как выходы состояния автомата. Матрица переходных вероятностей используется для математического анализа логических обнаружителей.
2.5 Статистический анализ логических обнаружителей
Если изобразить обнаружитель в виде абстрактной схемы и получить матрицу переходных вероятностей, то для его анализа можно применить результаты теории простых цепей Маркова.
Если цепь Маркова эргодичний, т.е. вероятности переходов (и состояний) не зависят от шага (момента времени), что рассматриваем, то для него справедливое равенство
, (2.9)
где - вектор (матрица) ограниченных вероятностей состояний автомата;
- матрица переходных вероятностей;
и - одинаковые на каком шагу.
Для неэргодичних цепей Маркова имеет место равенство
, (2.10)
где - вектор (матрица) вероятностей автомата на -му шагу;
- вектор (матрица) вероятностей станiв автомата на -му шагу;
- матрица переходных вероятностей на -му шагу.
Формула 2.10 есть рекурентное, т.е. ее применяют последовательно от 1-й к -й позиции для решения задачи анализа на данной -й позиции. При этом используется граф с поглощающ