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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ФИЛИАЛ В Г. ИШИМБАЕ Кафедра Математики

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

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

Выполнил:

студент гр.

Проверил: к.ф.-м.н., доцент Мугафаров М.Ф.

Ишимбай, 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