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

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

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

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

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

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

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

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

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

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

Выполнил:

студент гр.

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

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

Ишимбай, 2009

Содержание

Введение

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

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

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

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

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

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

Заключение

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q1;0

q2;0

q3;0

q4;0

q5;*

q6;*

q7;*

q8;1

*;1

*;1

*;1

*;*

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

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q3;0

q4;0

q5;*

q6;*

q7;*

q8;1

*;1

*;1

*;1

*;*

q1;0

q2;0

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

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q5;*

q6;*

q7;*

q8;1

*;1

*;1

*;1

*;*

q1;0

q2;0

q3;0

q4;0

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

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q4;0

q5;*

q6;*

q7;*

q8;1

*;1

*;1

*;1

*;*

q1;0

q2;0

q3;0

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

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

xi q[ф]	x1	x2	x3	x4
q1	q1;0	q3;0	q5;*	q4;0
q2	q2;0	q4;0	q6;*	q5;*
q3	q3;0	q5;*	q7;*	q6;*
q4	q4;0	q6;*	q8;1	q7;*
q5	q5;*	q7;*	*;1	q8;1
q6	q6;*	q8;1	*;1	*;1
q7	q7;*	*;1	*;1	*;1
q8	q8;1	*;1	*;*	*;1
q9	*;1	*;1	q1;0	*;*
q10	*;1	*;*	q2;0	q1;0
q11	*;1	q1;0	q3;0	q2;0
q12	*;*	q2;0	q4;0	q3;0

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

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

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q1

x1/0

-

x2/0

x4/0

x3/*

-

-

-

-

-

-

-

q2

-

x1/0

-

x2/0

x4/*

x3/*

-

-

-

-

-

-

q3

-

-

x1/0

-

x2/*

x4/*

x3/*

-

-

-

-

-

q4

-

-

-

x1/0

-

x2/*

x4/*

x3/1

-

-

-

-

q5

x1/1

-

-

-

x1/*

-

x2/*

x4/*

-

-

-

-

q6

x3/1

x4/1

-

-

-

x1/*

-

x2/1

-

-

-

-

q7

x2/1

x3/1

x4/1

-

-

-

x1/*

-

-

-

-

-

q8

x2/1

-

x4/1

-

-

-

-

x1/1

-

-

-

-

q9

x3/0

x1/1

x2/1

-

-

-

-

-

-

-

-

-

q10

x4/0

x3/0

x1/1

-

-

-

-

-

-

-

-

-

q11

x2/0

x4/0

x3/0

x1/1

-

-

-

-

-

-

-

-

q12

-

x2/0

x4/0

x3/0

-

-

-

-

-

-

-

-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица №7

q1	q2	q3	q4	q5	q6	q7	q8	q9	q10	q11	q12
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011

Таблица №8

x1	x2	x3	x4
00	01	10	11

Таблица №9

	00	01	10	11
0000	0000/0	0010/0	0100/*	0011/0
0001	0001/0	0011/0	0101/*	0100/*
0010	0010/0	0100/*	0110/*	0101/*
0011	0011/0	0101/*	0111/1	0110/*
0100	0100/*	0110/*	*/1	0111/1
0101	0101/*	0111/1	*/1	*/1
0110	0110/*	*/1	*/1	*/1
0111	0111/1	*/1	*/*	*/1
1000	*/1	*/1	0000/0	*/*
1001	*/1	*/*	0001/0	0000/0
1010	*/1	0000/0	0010/0	0001/0
1011	*/*	0001/0	0011/*	0010/0

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

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

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

T-триггер.

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

Таблица №10

	00	01	10	11
0000	0000	0010	0100	0011
0001	0000	0010	0100	0101
0010	0000	0110	0100	0111
0011	0000	0110	0100	0101
0100	0000	0010	****	0011
0101	0000	0010	****	****
0110	0000	****	****	****
0111	0000	****	****	****
1000	****	****	1000	****
1001	****	****	1000	1001
1010	****	1010	1000	1011
1011	****	1010	1000	1001

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

UT1=vvvvvvvv= vvvvvvv=vvvvvv

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

UT2 = vvv

UT3= vvv

UT4 = vv

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

Таблица №11

xi q[ф]	00	01	10	11
0000	0	0	*	0
0001	0	0	*	*
0010	0	*	*	*
0011	0	*	1	*
0100	*	*	1	1
0101	*	1	1	1
0110	*	1	1	1
0111	1	1	*	1
1000	1	1	0	*
1001	1	*	0	0
1010	1	0	0	0
1011	*	0	*	0

По таблице №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

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