МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Синтез комбинацонных схем и конечных автоматов, сети Петри

    Во - первых, автомат может быть задан непосредственно уравнениями вида

    (2.2.3) или (2.2.4).

    Во - вторых, уравнения (2.2.3) и (2.2.4) могут быть представлены в

    табличной форме. Табличный аналог первого уравнения в (2.2.3) называется

    таблицей переходов, второго – таблицей выходов.

    В - третьих, таблицы переходов и выходов можно объединить в одну.

    Содержимое каждой клетки представляет собой дробь: над косой чертой

    вписывается соответствующее значение из таблицы переходов, под косой чертой

    – значение из таблицы выходов. Полученная таким образом таблица называется

    общей таблицей переходов и выходов конечного автомата.

    Граф автомата – это сигнальный граф, вершины которого обозначают

    состояния автомата, на дугах отражены условия перехода из состояния в

    состояние и значения выходных сигналов в виде дроби: над косой чертой –

    x(j), под ней – y(j).

    Конечный автомат можно также описать с помощью матрицы переходов. Это

    аналог графа в табличной форме. Она представляет собой квадратную матрицу

    размерности число состояний [pic] число состояний, в которой отражены

    условия перехода из состояния в состояние аналогично изображённым на графе.

    Общее определение конечного автомата:

    M = (X, Y, S, ?, ?),

    (2.2.5)

    где X – входной алфавит, Y – выходной алфавит, S – множество

    состояний, ? – функция переходов, ? – функция выходов.

    Пусть имеется два автомата: M и M’.

    Если для любого [pic] существует по крайней мере одно [pic],

    эквивалентное ему, то говорят, что M’ покрывает M: M’ ? M.

    Если одновременно M’ ? M и M ? M’, то M ~ M’ . Получаем

    эквивалентные автоматы. В этом случае невозможно различить M и M’ по их

    реакции на входные сигналы.

    Существуют два основных положения определения понятия эквивалентности

    состояний:

    а) состояния si и sj явно различны, если соответствующие им строки

    в таблице выходов разные;

    б) состояния si и sj явно эквивалентны, если соответствующие им

    строки в общей таблице переходов автомата одинаковы или становятся таковыми

    при замене si на sj или наоборот.

    Минимизация (упрощение) автоматов основано на понятии эквивалентных

    автоматов. Под минимизацией автомата будем понимать сокращение числа его

    состояний.

    2.3 Расчёты и полученные результаты.

    Построение таблиц переходов, выходов и общей таблицы переходов и

    выходов на основе заданных уравнений автомата Мили очевидно:

    | |0 |1 |2 |3 |

    |x(j) | | | | |

    |s(j) | | | | |

    |0 |1 |0 |1 |0 |

    |1 |0 |1 |0 |1 |

    |2 |1 |0 |1 |0 |

    |3 |0 |1 |0 |1 |

    |4 |1 |0 |1 |0 |

    |5 |0 |1 |0 |1 |

    |6 |1 |0 |1 |0 |

    |7 |0 |1 |0 |1 |

    Таблица 2.3.1 – Таблица выходов автомата

    | |0 |1 |2 |3 |

    |x(j) | | | | |

    |s(j) | | | | |

    |0 |0 |1 |2 |3 |

    |1 |2 |3 |4 |5 |

    |2 |4 |5 |6 |7 |

    |3 |6 |7 |0 |1 |

    |4 |0 |1 |2 |3 |

    |5 |2 |3 |4 |5 |

    |6 |4 |5 |6 |7 |

    |7 |6 |7 |0 |1 |

    Таблица 2.3.2 – Таблица переходов автомата

    | |0 |1 |2 |3 |

    |x(j) | | | | |

    |s(j) | | | | |

    |0 |0/1 |1/0 |2/1 |3/0 |

    |1 |2/0 |3/1 |4/0 |5/1 |

    |2 |4/1 |5/0 |6/1 |7/0 |

    |3 |6/0 |7/1 |0/0 |1/1 |

    |4 |0/1 |1/0 |2/1 |3/0 |

    |5 |2/0 |3/1 |4/0 |5/1 |

    |6 |4/1 |5/0 |6/1 |7/0 |

    |7 |6/0 |7/1 |0/0 |1/1 |

    Таблица 2.3.3 – Общая таблица переходов и выходов автомата

    Перейдём непосредственно к минимизации полученного автомата по числу

    состояний. Для этого воспользуемся алгоритмом, известным в литературе как

    метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно

    минимальную форму автомата. Однако в общем случае он является довольно

    трудоёмким и применяется, как правило, для автоматов с небольшим

    количеством состояний. Он основан на свойстве транзитивности

    эквивалентности

    (si ~ sj) ? (sj ~ sk) [pic] (si ~

    sk) (2.3.1)

    Пара эквивалентных состояний переходит при всех возможных значениях

    входа в пары также эквивалентных состояний.

    Алгоритм состоит из следующих шагов.

    Сначала разбиваем все состояния автомата на множества по признаку

    совпадения выходных сигналов. В нашем случае получаем 2 множества: S1

    = {0, 2, 4, 6} и S2 = {1, 3, 5, 7}.

    Чтобы назвать каждый из полученных классов новым состоянием, нужно

    убедиться в том, что в каждый класс входят только эквивалентные между собой

    состояния. Для этого составляем таблицу пар эквивалентных состояний. При

    этом не забываем о том, что эквивалентными могут быть состояния,

    принадлежащие только одному классу. В таблицу заносим все те пары, в

    которые переходят при соответствующих входах исходные, вероятно

    эквивалентные, пары:

    |пары |0 |1 |2 |3 |

    |0;2 |0;4 |1;5 |2;6 |3;7 |

    |0;4 |0;0 |1;1 |2;2 |3;3 |

    |0;6 |0;4 |1;5 |2;6 |3;7 |

    |2;4 |4;0 |5;1 |6;2 |3;7 |

    |2;6 |4;4 |5;5 |6;6 |7;7 |

    |4;6 |0;4 |1;5 |2;6 |3;7 |

    |1;3 |2;6 |3;7 |4;0 |5;1 |

    |1;5 |2;2 |3;3 |4;4 |5;5 |

    |1;7 |2;6 |3;7 |4;0 |5;1 |

    |3;5 |6;2 |7;3 |0;4 |1;5 |

    |3;7 |6;6 |7;7 |0;0 |1;1 |

    |5;7 |2;6 |3;7 |4;0 |5;1 |

    Таблица 2.3.4 – Таблица пар эквивалентных состояний

    Ищем в полученной таблице неэквивалентные пары – пары из разных

    множеств. В таблице таких нет, значит, окончательно получаем автомат с

    двумя новыми состояниями – обозначим их 0 и 1.

    Следующим шагом оформляем общую таблицу переходов для минимизированной

    формы автомата:

    | |0 |1 |2 |3 |

    |x(j) | | | | |

    |s(j) | | | | |

    |0 |0/1 |1/0 |0/1 |1/0 |

    |1 |0/0 |1/1 |0/0 |1/1 |

    Таблица 2.3.5 – Новая общая таблица переходов.

    На основании полученной общей таблицы переходов и выходов можно

    нарисовать граф минимизированного автомата с двумя состояниями:

    0/1U 2/1 1/0 U 3/0

    1/1U 3/1

    0 1

    0/0 U 2/0

    Рисунок 2.3.1 – Граф минимизированного автомата

    Для практической реализации полученного автомата надо двоично

    закодировать все сигналы. Для кодировки y и s достаточно одного

    двоичного разряда, x требует двух – x1 и x2:

    |x |x1 |x2 |

    |0 |0 |0 |

    |1 |0 |1 |

    |2 |1 |0 |

    |3 |1 |1 |

    Таблица 2.3.6 – Двоичная кодировка x

    Составляем таблицу истинности для комбинационной части схемы на основе

    таблицы (2.3.5). Получаем две функции трёх аргументов:

    |x1(j) |0|0|0|0|1|1|1|1|

    |x2(j) |0|0|1|1|0|0|1|1|

    |s(j) |0|1|0|1|0|1|0|1|

    |y(j) |1|0|0|1|1|0|0|1|

    |s(j+1)|0|0|1|1|0|0|1|1|

    Таблица 2.3.7 – Таблица истинности комбинационной части

    Каждую из функций y(j) и s(j+1) минимизируем с помощью карт Карно:

    y(j)

    s(j+1)

    x1(j)x2(j)

    x1(j)x2(j)

    00 01 11 10

    00 01 11 10

    0 1 1

    0 1 1

    s(j)

    s(j)

    1 1 1

    1 1 1

    Рисунок 2.3.2 – Карты Карно для комбинационной части

    На основании выбранных покрытий записываем минимизированные выражения

    для функций переходов и выходов:

    [pic] (2.3.2)

    [pic]

    (2.3.3)

    Реализуем полученные функции в виде комбинационной схемы, добавляя к

    ней элементы памяти – D - триггер и задержку. Комбинационную часть

    реализуем в базисе И – ИЛИ – НЕ.

    Рисунок 2.3.2 – Схема минимизированного автомата в базисе И – ИЛИ – НЕ

    2.3.4 Выводы по разделу

    В этом разделе был показан пример минимизации (упрощения) конечного

    автомата с сокращением числа состояний, а также пример реализации автомата

    на логических элементах и элементах памяти. Мы убедились в том, что

    конечный автомат является расширением понятия комбинационной схемы на

    случай, когда для получения выходного сигнала в данный момент времени

    требуется “помнить” некоторое количество предыдущих значений входного

    сигнала, а не только его текущее значение. При практической реализации

    автомата стала очевидной польза проведённых операций по упрощению исходного

    автомата и приведению его комбинационной части к конкретному базису.

    3 Сети Петри

    3.1 Постановка задачи

    Для заданной сети Петри, описывающей распределение ресурсов для случая

    двух процессов, сделать следующее:

    а) выписать матричное уравнение смены маркировок;

    б) построить дерево и граф покрываемости маркировок;

    в) описать поведенческие свойства сети на основе графа покрываемости и

    матричных уравнений;

    г) выписать множество достижимых из ?0 маркировок;

    д) разработать программу моделирования сети Петри.

    3.2 Теоретические сведения

    Сети Петри – наиболее удачный из существующих математический аппарат

    для моделирования, анализа, синтеза и проектирования самых разных

    дискретных систем с параллельно протекающими процессами.

    Определение. Сетью Петри называется четвёрка элементов

    C = (P, T, I ,O),

    (3.2.1)

    где

    P = { p1, p2,…,pn }, n > 0

    (3.2.2)

    множество позиций (конечное),

    T = { t1, t2,…,tm }, m > 0

    (3.2.3)

    множество переходов (конечное),

    I: T > P

    (3.2.4)

    функция входов (отображение множества переходов во входные позиции),

    O: T > P

    (3.2.5)

    функция выходов (отображение множества переходов в выходные позиции).

    Если pi [pic] I (tj) , то pi – входная позиция j - го перехода,

    если pi [pic]I (tj) , то pi – выходная позиция j - го перехода.

    Для наглядного представления сетей Петри используются графы.

    Граф сети Петри есть двудольный ориентированный мультиграф

    G = (V,[pic]),

    (3.2.6)

    где V = P U T , причём P ? T = Ш.

    Исходя из графического представления сети Петри, её можно определить и

    так:

    C = (P, T, A),

    (3.2.7)

    где А – матрица инцидентности графа сети.

    Определим понятие маркированной сети Петри – оно является ключевым для

    любой сети.

    Маркировка ? сети Петри C = (P, T, I, O) есть функция:

    N = ?(P), N [pic] N,

    (3.2.8)

    отображающая множество позиций на множество натуральных чисел. Маркировку

    можно также определить как вектор:

    ? = {?1, ?2,…, ?n} ,

    (3.2.9)

    где n = |P |, а ?i [pic] N. Между этими определениями есть связь:

    ?i = ? (pi)

    (3.2.10)

    На графе маркировка отображается ссответствующим числом точек в каждой

    позиции. Точки называются маркерами или фишками. Если фишек много (больше

    трёх), то их количество отображается числом.

    Таким образом, маркированная сеть Петри представляет собой пятёрку

    элементов:

    M = (P, T, I, O, ?).

    (3.2.11)

    Пример простейшей сети Петри:

    p1

    ???

    t1

    p3

    p2 ?

    Рисунок 3.2.1 – Пример сети Петри

    Правила работы с сетями Петри.

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

    быть запущен в том случае, когда он разрешён. Переход является разрешённым,

    если каждая из его входных позиций содержит число фишек не меньшее, чем

    число дуг из неё в данный переход.

    Процедура запуска состоит в удалении из каждой входной позиции

    перехода числа фишек, равного числу дуг из неё, и в выставлении в каждой

    выходной позиции числа фишек, равного числу дуг, входящему в неё.

    Проиллюстрируем сказанное на примере уже нарисованной сети Петри.

    Запустим в ней переход t1 – он является разрешённым:

    p1

    ?

    t1

    p3

    ?

    p2 ?

    Рисунок 3.2.2 – Пример запуска перехода сети Петри

    Пространство состояний и поведенческие свойства сетей Петри.

    Пусть имеется маркированная сеть Петри:

    M = (P, T, I, O, ?)

    (3.2.12)

    У неё n позиций. В каждой позиции не более N фишек. Тогда

    пространство сотояний есть множество всех возможных маркировок сети.

    Определим ? – функцию следующего состояния.

    Если переход tj разрешён при текущей маркировке ? , то следующая

    маркировка ?’ определится так:

    ?’ = ? (?, tj)

    (3.2.13)

    Если переход tj не разрешён, то ? не определена.

    Пусть {tj0, tj1,…, tjs} – последовательность запущенных переходов.

    Тогда ей будет соответствовать последовательность {?0, ?1,…,?s+1}, то есть

    ?k+1 = ?(?k, tjk)

    (3.2.14)

    На основании последнего равенства можно определить понятие

    непосредственно достижимой маркировки. Для сети C = (P, T, I ,O)

    маркировка ?’ называется непосредственно достижимой из ? , если

    существует такой переход tj [pic] T, при котором

    ?' = ?(? , tj)

    (3.2.15)

    Можно распространить это понятие на множество достижимых из данной

    маркировок. Определим множество достижимых из ? маркировок R(C, ?)

    следующим образом:

    во - первых, ? [pic] R(C, ?);

    во - вторых, если ?’ [pic] R(C, ?), ?’ = ?(? , tj) и ?’’ = ?(?’,

    tk), то и ?’’ [pic] R(C, ?).

    На основе введённых понятий можно сформулировать ряд свойств сети

    Петри, характеризующих её в процессе смены маркировок – назовём их

    поведенческими свойствами сети Петри. Определим наиболее важные из них.

    1. Достижимость данной маркировки. Пусть имеется некоторая маркировка

    ?, отличная от начальной. Тогда возникает вопрос достижимости:

    можно ли путём запуска определённой поледовательности переходов

    перейти из начальной в заданную маркировку.

    2. Ограниченность. Сеть Петри называется k- ограниченной, если при

    любой маркировке количество фишек в любой из позиций не превышает

    k. В частности, сеть называется безопасной, если k равно 1. Кроме

    того, сеть называется однородной, если в ней отсутствуют петли и

    одинарной (простой), если в ней нет кратных дуг.

    3. Активность. Сеть Петри называется активной, если независимо от

    дотигнутой из ?0 маркировки существует последовательность

    запусков, приводящая к запуску этого перехода.

    Реально вводят понятия нескольких уровней активности для

    конкретных переходов. Переход tj [pic] T называется:

    а) пассивным (L0- активным), если он никогда не может быть

    запущен;

    б) L1- активным, если он может быть запущен последовательностью

    переходов из ?0 хотя бы один раз;

    в) L2- активным, если для любого числа K существует

    последовательность запусков переходов из ?0 , при которой данный

    переход может сработать K и более раз;

    г) L3- активным, если он является L2- активным при K >

    ?.

    4. Обратимость. Сеть Петри обратима, если для любой маркировки ?

    [pic] R(C, ?0) маркировка ?0 достижима из ?.

    5. Покрываемость. Маркировка ? покрываема, если существует другая

    маркировка ?’ [pic] R(C, ?0) такая, что в каждой позиции ?’

    фишек не меньше, чем в позициях маркировки ?.

    6. Устойчивость. Сеть Петри называется устойчивой, если для любых двух

    разрешённых переходов срабатывание одного из них не приводит к

    запрещению срабатывания другого.

    Существуют два основных метода анализа сетей Петри: матричные и

    основанные на построении дерева покрываемости.

    Первая группа методов основана на матричном представлении маркировок и

    последовательностей запуска переходов. Для этого определим две матрицы

    Страницы: 1, 2, 3


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.