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

Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 20.07.2015
Размер файла 964,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Содержание

Введение

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

.

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

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

х

Состояния S и выходные сигналы Y

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

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

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

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

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

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

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

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

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

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

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

х

Состояния S и выходные сигналы Y

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Кл.

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

x

Состояния Г и выходные сигналы Y

-

-

-

-

-

-

-

-

-

-

-

-

-

-

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

x

Y0

Y1

Y2

Y2

Y1

Y2

Y3

Y3

d1

d0

d1

d0

d1

d0

d1

d0

d1

d0

d1

d0

d1

d0

d1

d0

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

y0

y1

y2

y*2

y3

y4

y5

y*5

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

a2

a1

a0

0

1

1

1

0

1

0

1

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

0

0

0

1

1

1

-

-

-

-

0

1

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

0

0

1

0

1

0

1

0

1

0

1

-

-

-

-

-

-

-

-

0

0

0

1

0

0

0

1

-

-

-

-

-

-

-

-

0

1

0

-

-

-

-

0

1

0

0

0

1

1

0

0

1

1

0

-

-

-

-

1

0

0

1

1

0

0

1

-

-

-

-

0

1

1

0

1

1

1

-

-

-

-

0

1

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

1

0

0

0

0

1

1

0

1

0

1

-

-

-

-

-

-

-

-

0

0

1

1

-

-

-

-

1

1

0

1

0

1

0

1

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

x

Y0

Y1

Y2

Y2*

d1

d0

d1

d0

d1

d0

d1

d0

0

0

0

1

1

0

1

0

y0

y1

y2

y*2

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

0

1

1

1

0

1

0

1

0

1

1

0

0

1

0

0

a2

a1

a0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

0

0

0

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

1

1

1

1

1

1

1

0

-

-

-

-

-

-

-

-

0

0

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

0

1

0

-

-

-

-

-

-

-

 

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

0

1

1

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

1

1

1

1

1

1

1

0

-

-

-

-

-

-

-

-

1

0

0

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Продолжение таблицы 5

x

Y1

Y2

Y3

Y3*

d1

d0

d1

d0

d1

d0

d1

d0

0

1

1

0

1

1

1

1

y3

y4

y5

y*5

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

q3

q2

q1

q0

0

0

1

1

0

0

0

1

1

0

0

1

1

1

0

1

a2

a1

a0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

R3

S3

R2

S2

R1

S1

R0

S0

0

0

0

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

0

0

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

0

1

0

-

-

-

-

-

-

-

-

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

0

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

1

0

0

1

1

1

1

1

1

1

1

-

-

-

-

-

-

-

-

1

1

1

0

1

1

1

1

0

1

1

1

1

1

1

1

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

Структурный синтез начинается с кодирования входного и выходного алфавита и состояний автомата.

Количество разрядов для входных выходных сигналов и состояний определяется в соответствии с формулой (1)

, (2.1)

где М-мощность множества соответствующего алфавита;

х-означает минимальное целое.

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

Для автомата Мура:

, (2.2)

, (2.3)

. (2.4)

Кодирование входных сигналов автомата Мура представлена как в таблице 4.

Таблица 4 - Кодирование входных сигналов автомата Мура

Входной сигнал

Коды

X0

0

0

0

X1

0

0

1

X2

0

1

0

X3

0

1

1

X4

1

0

0

Кодирование выходных сигналов автомата Мура представлена в таблице 5.

Таблица 5 - Кодирование выходных сигналов автомата Мура

Выходной сигнал

Коды

y0

0

0

y1

0

1

y2

1

0

y3

1

1

Одно из возможных вариантов кодирования состояний автомата Мура представлен в таблице 6.

Таблица 6 - Кодирования состояний автомата Мура

Состояния Q

Коды

0

1

1

1

0

1

0

1

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

1

1

0

0

1

1

1

0

1

Вторичный граф переходов-выходов автомата Мили представлен на рисунке 2.

Рисунок 3 - Структурный граф автомата Мура

На основании таблицы возбуждения формируем восемь функций возбуждения:

; (2.5)

; (2.6)

; (2.7)

; (2.8)

; (2.9)

; (2.10)

; (2.11)

. (2.12)

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

Таблица 7 - Таблица истинности выходных функций автомата Мура

Состояние автомата

Состояния триггеров

Выходные сигналы

Y

0

0

0

1

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

1

1

1

0

1

В результате получим выражения:

; (2.13)

. (2.14)

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

Функциональная схема автомата Мура на RS - триггерах и элементах И-НЕ представлена в соответствии с рисунком 4.

Для проверки соответствия синтезированной схемы заданным условиям функционирования автомата выполним функциональное моделирование полученной схемы при помощи программы моделирования Electronics Workbench [5].

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

Рисунок 4 - Генератор слов

Рисунок 5 - Временные диаграммы функционирования

Рисунок 5 - Модель автомата Мура

Заключение

В ходе работы было проведено исследование дискретного автомата Мура, состоящее из :

1. Абстрактный синтез. В котором по вход-выходной последовательности и таблице соответствия были рассчитаны: первичная и вторичная таблица переходов-выходов; первичный и вторичный граф переходов-выходов; таблицы

2. Дискретный синтез. В нем была выполнена кодирование входных и выходных сигналов, а так же состояний автомата Мура. На основании вторичного графа переходов-выходов был построен граф с кодированными сигналами и состояниями, а на основании таблицы возбуждения были получены восемь функций возбуждения и две выходные функции, на основании таблицы истинности выходных сигналов.

3. Моделирование дискретного автомата. На этом этапе была построена функциональная модель автомата Мура в программе Electronic WorkBench , построенной по выходным функциям и функциям возбуждения. Запрограммировав генератор слов были получены временные диаграммы, которые соответствуют вход-выходной последовательности.

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

1. Соловьев В.В.Булатова И.Р.Стандартные программируемые логические устройства Зарубежная радиоэлектроника.2000 № 4.С.66-76.

2. Соловьев В.В.Булатова И.Р. Архитектуры сложных программируемых логических интегральных схем Зарубежная радиоэлектроника.2000 № 5.С.62-78.

3. Энциклопедия кибернетики Под ред. В.М.Глушакова. -Киев :Главная редакция украинской советской энциклопедии,1974.

4. Соловьев А.Я. Основы информатики :Учебник для вузов. -М.: Изд-во МГТУ им.Н.Э.Баумана,2001.

5. Трахтенберг Б.А .,Барадин Я.М .Конечные автоматы :Поведение и синтез.М.:Наука,1970

Размещено на Allbest.ru


Подобные документы

  • Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.

    контрольная работа [141,5 K], добавлен 14.10.2012

  • Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.

    курсовая работа [764,0 K], добавлен 27.08.2012

  • Понятие и назначение дискретного (цифрового) автомата, сферы и правила его использования. Граф-дерево автомата Мура и мили, их отличительные черты. Таблица переходов с распределением неопределённостей. Представление функции возбуждения и ее минимизация.

    курсовая работа [423,7 K], добавлен 11.10.2008

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

    курсовая работа [60,9 K], добавлен 15.02.2011

  • Разработка управляющего автомата процессора с жесткой логикой в САПР Quartus II. Построение схемы функциональной микропрограммы команды "Исключающее ИЛИ" в размеченном виде. Унитарное кодирование состояний автомата. Запись функций переходов и выходов.

    курсовая работа [671,3 K], добавлен 04.11.2014

  • Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.

    презентация [357,0 K], добавлен 16.10.2013

  • Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.

    курсовая работа [525,4 K], добавлен 04.11.2012

  • Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.

    курсовая работа [997,7 K], добавлен 28.03.2011

  • Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.

    курсовая работа [2,0 M], добавлен 27.10.2010

  • Алгоритм умножения двоичных чисел. Выбор и описание структурной схемы операционного автомата. Реализация содержательной граф-схемы алгоритма. Построение отмеченной граф-схемы и структурной таблицы переходов и выходов. Правила кодирования на D-триггерах.

    курсовая работа [273,2 K], добавлен 01.04.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.