Курсовая работа (т): Моделирование дискретного автомата

Моделирование дискретного автомата

Содержание

Введение

Абстрактный синтез дискретного автомата

Структурный синтез дискретных автоматов

Моделирование дискретного автомата

Заключение

Список использованных источников

Введение

Современные приборы и устройства сервиса представляют собой сложные технические системы, реализованные на базе средств вычислительной техники. Цифровые устройства и микропроцессоры являются важнейшей составной частью различных объектов бытовой техники: радиоэлектронной аппаратуры, стиральных и посудомоечных машин, холодильников и климат-систем, изделий оргтехники и других устройств.

Такой широкий диапазон применения цифровых устройств определяется их высокими техническими параметрами и технико-экономическими показателями. В частности - это низкое энергопотребление, высокое быстродействие, высокая надежность и помехозащищенность, возможность реализации алгоритмов управления и обработки сигналов любой сложности, малые габариты, технологичность и низкая стоимость [1].

Управляющие автоматы реализуются в виде "гибкой" или программируемой логики, на основе микропроцессоров, а также в виде "жесткой логики" - на основе последовательностных цифровых устройств. Математическими моделями, используемыми при анализе и синтезе последовательностных устройств. В последнее время интерес к конечным автоматам возрос, что связано с развитием интегральной программируемой электроники и др. В основе синтеза таких устройств лежат методы абстрактного (логического) и структурного синтеза конечных автоматов. Это обстоятельство делает необходимым приобретения знаний и навыков применения этих методов для анализа и синтеза цифровых устройств управления объектами и устройствами [2].

1 Абстрактный синтез дискретного автомата

Рассмотрим содержание и особенности определенных этапов синтеза на примере.

Пусть требуется синтезировать асинхронный автомат Мура начальное описание, которого представлено вход-выходной последовательностью и таблицей соответствия:

дискретный автомат сигнал триггер

.

Определяем мощность входного и выходного множества Мх=5 Му=4.Строим первичную таблицу переходов-выходов автомата Мура, как показано в соответствии с таблицей 1.

Таблица 1.1 Первичная таблица переходов-выходов автомата Мура

Задача минимизации автомата сводится возможности максимального уменьшения числа внутренних состояний без изменения закона их функционирования.

Решение этой задачи выполним методом Ауфенкампа и Хона основанного на понятии эквивалентных состояний.

Эквивалентным состоянием называется sn и sm такие состояния которым во-первых соответствуют одинаковые входные сигналы y(t) а во вторых переход из состояний sn и sm под воздействием любого символа приводит к одному и тому же эквивалентному состоянию [3].

Алгоритм минимизации:

.        Методом последовательного разбиения выделяем все попарно эквивалентные состояния.

.        Объединяем эквивалентные состояния в одиночные классы у1 у2 и выделяем в каждом классе по одному состоянию для выполнения последующих этапов при разбиении на классы пустые клетки во внимание не принимаются.

.        Строим вторичную таблицу переходов-выходов в которой каждый класс состояний представляем только одним эквивалентным состоянием.

Рисунок 1 - Первичный граф переходов-выходов автомата Мура

Первое разбиение состояний на классы выполняем по выходным сигналам как показано в таблице 2. Анализ показывает что в классе у1 состояние s1 не является эквивалентным основным состоянием этого класса так как при поступлении сигнала х1 автомат переходит из состояния s1 в класс состояний у2 в отличии от других состояний класса переводящих автомат под действием сигнала х1 в состояния класса у1 [4].

Таблица 2 - Разбиение на классы автомата Мура

Таблица 3 - Переходы-выходы автомата Мура

Таблица 4 - Первичная таблица возбуждения

q0

101

---

---

---

---

101

Таблица 5 - Вторичная таблица возбуждения

S1R0S0

---

---

---

---