Исследование и логическое проектирование конечного частично определённого автомата

/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФИЛИАЛ В Г.ИШИМБАЕ

Кафедра Математики

КУРСОВАЯ РАБОТА

«Исследование и логическое проектирование конечного частично определённого автомата»

Выполнил:

студент гр.

Проверил: к.ф.-м.н., доцент

Мугафаров М.Ф.

Ишимбай, 2009

Содержание

Введение

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

1. Построение таблицы поведения автомата и соответствующего графа

2. Кодирование данных

3. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции ш

4. Определение булевой функции для реализации функции ц

5. Составление логической схемы автомата

Заключение

Введение

Цель работы - выполнить исследование и логическое проектирование конечного частично определённого автомата по индивидуальным данным.

Конечный автомат при двоичном кодировании его алфавитов есть структурный автомат. В практике проектирования автоматов встречаются случаи, когда функции переходов и/или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный. При описании таких автоматов неопределенные позиции таблиц помечаются символом '*'. Модель современной вычислительной машины представляет структурный автомат, использующий композицию операционного и управляющего автоматов.

В данной работе реализован конечный частично определённый автомат. В качестве элементов двоичной задержки (или элементов памяти) будем использовать триггеры.

Логическое проектирование автомата - это составление логических функций выходов и функций переходов.

Основными этапами логического проектирования конечного автомата являются:

1) кодирование алфавитов;

2) выбор комбинационных автоматов;

3) выбор элементов двоичной задержки;

4) формирование функций выхода и переходов;

5) построение логической схемы структурного автомата.

Конечным этапом логического проектирования конечного автомата будет трассировка.

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

Исходные данные имеют вид:

Текущее состояние при xвх=x1. Таблица №1

Текущее состояние при xвх=x2. Таблица №2.

Текущее состояние при xвх=x3. Таблица №3

Текущее состояние при xвх=x4. Таблица №4

Требуется провести исследование и логическое проектирование конечного автомата. Задача будет решаться в несколько этапов.

1. Получим таблицу поведения №5 и соединения №6 автомата и нарисуем графы по этим таблицам;

2. По таблице №7 и №8 произведём кодирование данных и получим таблицу №9;

3. По найденной таблице №10 получим систему булевых функций для возбуждения T-триггеров, реализующих функции ш;

4. По найденной таблице №11 получим булеву функцию для реализации функции ц;

5. Составим логическую схему автомата по полученным булевым функциям, используя комбинационные автоматы и T-триггеры.

1. Исходные данные представлены в виде четырех таблиц.(Таблицы №1,2,3,4).Для работы нужно свести четыре таблицы в одну. Для этого каждую таблицу нужно транспонировать. После транспонирования мы получим таблицу поведения №5.

По таблице №5 получим таблицу №6. Алгоритм построения таблицы:

Строка №1: чтобы перейти из q1 в q1 нужно подать сигнал x1/0, чтобы перейти из q1 в q3 нужно подать сигнал x2/0, чтобы перейти из q1 в q4 нужно подать сигнал x4/0, чтобы перейти из q1 в q5 нужно подать сигнал x3/*. Аналогично заполняем остальные строки таблицы №6.

1. Построение таблицы поведения и соответствующего графа

логическое проектирование автомат граф

Таблица №5

*/* - не рассматриваем.

Таблица соединений: Таблица №6

По полученной таблице соединений №6 построим графы. Графы строятся по следующему алгоритму: строим граф с истоком в вершине q1, q1 ставим в центр окружности, состоящей из остальных состояний q, смотрим в таблице какие q имеют сигнал, q1 имеет сигнал x1/0 , q3- x2/0, q 4- x4/0 и q5-x3/*. Каждую из этих состояний соединяют с вершиной q1.

Аналогично строятся и остальные.

/

Рисунок 1. Граф с вершиной истока q1

/

Рисунок 2. Граф с вершиной истока q2

Рисунок 3. Граф с вершиной истока q3

/

Рисунок 4. Граф с вершиной истока q4

/

Рисунок 5. Граф с вершиной истока q5

/

Рисунок 6. Граф с вершиной истока q6

/

Рисунок 7. Граф с вершиной истока q7

/

Рисунок 8. Граф с вершиной истока q8

/

Рисунок 9. Граф с вершиной истока q9

/

Рисунок 10. Граф с вершиной истока q10

Рисунок 11. Граф с вершиной истока q11

/

Рисунок 12. Граф с вершиной истока q12

2. Кодирование данных

Для последующей работы вновь вернемся к исходным данным таблицы №6. В таблице №6 произведём кодирование, т.е. заменим состояния и сигналы на уникальные двоичные коды. Поскольку состояний 12, то необходимая длина кода равна 4. Входящих сигналов 4, по этому длина кода равна 2. Кодирование,т.е. сопоставление кодов возможно произвольно. В данной работе будет использоваться следующий метод(см. таблицу №9).

Таблица №7

Таблица №8

Таблица №9

3. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции ш

Триггер представляет собой элементарный автомат Мура, обладающий двумя устойчивыми состояниями 0 и 1. Триггеры делятся на: T, D , RS, JK - триггеры. В данной работе будем использовать T-триггер.

Таблица переходов

T-триггер.

Таблица №10 строится по таблице №9 при помощи таблицы переходов для Т-триггеров. Берём крайний левый столбец состояний и начиная с первого элемента таблицы по порядку производится переход состояний по таблице Т-триггеров.

Таблица №10

По таблице №10 строим СДНФ для функции ш. Алгоритм построения UT1 следующий: берём первую цифру двоичного кода по всем столбцам. Считаем количество 0 и 1.Чего меньше по тому и составляем СДНФ. В данной работе меньше 1. Значит составляем по 1. Мы получим следующее:

UT1=vvvvvvvv= vvvvvvv=vvvvvv

Аналогично составляем для остальных функций.

UT2 = vvv

UT3= vvv

UT4 = vv

4. Определение булевой функции для реализации функции ц

Таблица №11

По таблице №11 строим СДНФ для функции ц. СДНФ будем составлять по 1.

y=vvvvv

vvvvvvvv=vvvvvvvvvvvvv

Все СДНФ упрощены до конца, дальнейшее сокращение невозможно, так как элементы уравнений имеют различие в 2 и более элементов.

5. Составление логической схемы автомата.

Для построения схемы начнём с шин данных, которые расположены слева. Также справа будут находится инверсные шины для состояний. По сколько логические функции получены в виде СДНФ, то первой ступенью будут являться конъюнкторы, второй дизъюнкторы, а заключительной стадией будут триггеры. Выходы триггеров соединены по принципу обратной связи. Конъюнкторы и дизъюнкторы будем использовать множественные, с целью оптимизации схемы.

Для построения логической схемы автомата для функции ш(схема №1), возьмём СДНФ для функции ш, которая состоит из четырёх уравнений. Алгоритм построения уравнения UT1 : возьмём первый конъюнктор K1 с сигналами . Конъюнктор K1 подсоединяется к шинам данных по заданным сигналам. Для отрицательных значений x используются инверсные входы, для отрицательных q используются инверсные шины. По такому же принципу подсоединяются все остальные конъюнкторы. После того как все конъюнкторы подсоединены, их мы подсоединяем к дизъюнктору. К дизъюнктору D1 мы подсоединяем конъюнктуры от K1 по K7. Дизюнктор D1 мы подсоединяем к триггеру T1. Выходы триггера T1 подсоединяются к шинам данных по принципу обратной связи. Аналогично составляются остальные уравнения.

Для построения логической схемы автомата для функции ц (схема №2), возьмём СДНФ для ц. Конъюнкторы подсоединяем к шинам данных, потом все конъюнкторы подсоединяем к одному дизъюнктору. Выходом дизъюнктора является функция Y.

Заключение

1.Получили таблицу поведения №5 и соединения №6 автомата и нарисовали графы по этим таблицам;

2. По таблице №7 и №8 произвели кодирование данных и получили таблицу №9;

3. По найденной таблице №10 получили систему булевых функций для возбуждения T-триггеров, реализующих функции ш;

4. По найденной таблице №11 получили булеву функцию для реализации функции ц;

5. Составили логическую схему автомата по полученным булевым функциям, используя комбинационные автоматы и T-триггеры.

Все поставленные задачи в курсовой работе были выполнены.

Суммарная сложность схемы:

Конъюнкторов: 18

Дизъюнкторов: 4