Информатика и выч. техника \ Цифровые устройства и микропроцессоры

Синтез конечного автомата Мили. Построение графа конечного автомата. Определение количество элементов памяти. Программная реализация автомата

Страницы работы

30 страниц (Word-файл)

Скачать файл

Фрагмент текста работы

Министерство образования Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра радиоприемных и радиопередающих устройств

Курсовая работа по

Цифровым устройствам и микропроцессорам.

Синтез конечного автомата Мили

Выполнил студент группы

РТ5-03 факультета РЭФ: Панарин А.С.

Проверил преподаватель Родников В.В.

Новосибирск – 2003

План

1. Введение

2. Задание

3. Синтез конечного автомата Мили

a. Построение графа конечного автомата

b. Определение количество элементов памяти

c. Составление таблицы переходов и выходов конечного автомата

d. Составление таблицы возбуждения элементов памяти

e. Синтез комбинационной части конечного автомата

i. В базисе элементов И-НЕ

ii. На мультиплексере

iii. Дешифратор (декодер)

f. Реализация конечного автомата на микросхемах.

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

4. Программная реализация автомата

ВВЕДЕНИЕ.

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

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

Построение ЭВМ основано на использовании в качестве элементарных узлов цифровых автоматов. Элементарными автоматами являются автоматы Мура с двумя состояниями , обладающие полными системами переходов и выходов. Также в ЭВМ в качестве элементарных автоматов используется главным образом триггеры.

Особенности построения цифровых автоматов связаны со способом передачи информации между логическими элементами.

Задание на курсовую работу

1. Синтез конечного автомата Мили.

а. Построить граф конечного автомата б. Определить количество элементов памяти в. Составить таблицы переходов и выходов конечного автомата.

г. Составить таблицу возбуждения д. Синтезировать комбинационную часть конечного автомата е. Реализовать конечный автомат на микросхемах одной из серий: К155, К176, К531, К555, К561, К564 или других микросхемах . Составить полную логическую схему автомата.

2. Программная реализация автомата а. Построить граф и таблицу переходов автомата Мура.

б. Составить схему алгоритма в. Составить программу, реализующим автомат Мура на языке ассемблера МП К580.

Задание

Элемент памяти – JK-триггер

Таблица 1

Вершина графа	a₁		a₂		a₃		a₄
Сигнал	z_i	w_j	z_i	w_j	z_i	w_j	z_i	w_j
	1234	1234	1234	1234	1234	1234	1234	1234
	2004	1003	3241	3211	0014	0022	3120	1330

1. Синтез конечного автомата Мили.

а. Построение графа автомата

Рисунок 1 Граф б. Составим таблицу выходов,

Таблица 2

в. составим таблицу переходов,

Таблица 3

г. Выбираем в качестве элемента памяти JK-триггера. Базис логических элементов - произвольный.

д. Определяем недостающие входные данные

Число элементов памяти:

где количество внутренних состояний,

Число разрядов выходной шины:

где количество входных сигналов ,

Число разрядов выходной шины

где количество выходных сигналов .

е. Кодируем автомат. Это означает, что каждому входному и выходному сигналу, а также внутреннему состоянию ставят в соответствие определенный двоичный код.

Таблица 4. Входные сигналы

Состояние входа	Биты кода
Состояние входа
	0	0
	0	1
	1	0
	1	1

Таблица 5 Выходные сигналы

Состояние выхода	Биты кода
Состояние выхода
	0	1
	0	0
	1	1

Таблица 6. Сигналы памяти

Состояние входа	Биты кода
Состояние входа
	0	0
	0	1
	1	0
	1	1

ж. Тогда таблицы перехода и выхода приобретают следующий вид:

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


	00	01	10	11
00		00	00	00
01	00	10		01
10		01		11
11	11	11	01

Таблица 8. Таблицы выходов


	00	01	10	11
00		01	00	11
01	01	00		11
10		11		01
11	11	01	00

з. По таблице выходов составляем логические уравнения для выходных сигналов и . Учитывая, что в каждый левый бит таблицы характеризует сигнал , правый . Записывая уравнение по единицам получаем СДНФ:

и. Произведем минимизацию выходных функций используя метод минимизации карт Карно.

для минимизация по нулям.


1	0	*	0
0	*	1	0
1	0	1	0
*	*	0	*

Рисунок 2 Карта Карно для у₁


1	0	*	1
0	*	1	0
1	1	1	1
*	*	0	*

Рисунок 3. Карта Карно для у₂

остановимся на данном виде реализации выходных сигналов.

к. Преобразуем таблицу преобразуем таблицу переходов автомата в таблицу возбуждения памяти. Для обеспечения каждого отдельного перехода из исходного состояния памяти в последующее нужно подать на входы элементов памяти (синхронных триггеров) определенные сигналы. Именно эти сигналы заносятся в соответствующие клетки таблицы возбуждения памяти.

Таблица 9 Таблица возбуждения памяти


	0	0	0	1	1	0	1	1

00	**	**	0*	*1	*1	0*	*1	*1
01	0*	0*	1*	*1	**	**	*1	*0
10	**	**	0*	*0	**	**	*0	*0
11	1*	1*	1*	*0	*1	1*	**	**

л. Произведем минимизацию функций алгебры логики


1	*	*	0
1	*	*	1
0	*	*	0
*	*	*	*


*	1	*	*
*	*	1	*
*	0	1	*
*	*	1	*

С учетом минимальности цены производим минимизацию или по нулям или по единицам.


*	1	*	0
*	*	*	*
*	*	*	*
*	*	0	1


*	*	*	*
0	*	0	1
0	0	1	1
*	*	*	*

м. По полученной минимальной форме составляем логическую схему комбинационной части автомата на микросхемах выбранной серии.

н. Учтем, что выбирается два JK-триггера независимо в каком базисе будут составляться схемы возбуждения памяти и выходных функций, допустим это будет один корпус микросхемы К564ТВ1

о. Составим схемы возбуждения в базисе функций И-НЕ

Рисунок 4. Реализация ФАЛ в базисе И-НЕ

d. если производить минимизацию по единицам получается следующая форма записи

Рисунок 5. Реализациция ФАЛ К2

п. Составим схемы возбуждения для выходных функций

Рисунок 6. Реализация y₁

b. Инверсия и

Рисунок 7. Инверсия

Рисунок 8. Реализация y₂ в базисе И-НЕ

р. Получаем всего восемь корпусов микросхем, если использовать микросхему К564ЛА7 и К564ТВ1, попробуем использовать другой способ реализации функций, допустим на мультиплексерах.

с. Как видно из реализации ниже получается, что реализовать можно всего на пяти корпусах микросхем серии К155 – это К155КП2(сдвоенный цифровой селектор-мультиплексер 4-1), К155ЛА3, К155ТВ15(два JK-триггера). т. Таблица 10


0		0			0		*			0		0			0		*			0			0		1			0		0			0		1
0		0			1		0			0		0			1		0			0			1		1			0		0			1		1
0		1			0		*			0		1			0		*			1			0		0			0		1			0		0
0		1			1		1			0		1			1		1			1			1		1			0		1			1		0
1		0			0		0			1		0			0		0											1		0			0		1
1		0			1		1			1		0			1		*											1		0			1		0
1		1			0		0			1		1			0		*											1		1			0		0
1		1			1		1			1		1			1		1											1		1			1		*
			0					0					0					0				1					1					1					1
			0					0					1					1				0					0					1					1
			0					1					0					1				0					1					0					1
			*					1					1					0				0					*					1					1
	0			0		0			0		0			0		0			0		1			1		1			1		1			1		1		1
	0			0		0			0		1			1		1			1		0			0		0			0		1			1		1		1
	0			0		1			1		0			0		1			1		0			0		1			1		0			0		1		1
	0			1		0			1		0			1		0			1		0			1		0			1		0			1		0		1
	*			0		0			1		0			*		0			1		*			*		1			0		1			0		0		*

у. Схема (рисунок 9)

ф. Реализация выходных функций на декодере (дешифраторе)

для этого приведем таблицу функций, так как на выходе дешифратора должны стоять объединяющие ИЛИ

Таблица 11. Функции дешифратора


0	0	0	0	*	*	*	*	*	*
0	0	0	1	0	1	0	*	*	1
0	0	1	0	0	0	*	1	0	*
0	0	1	1	1	1	*	1	*	1
0	1	0	0	0	1	0	*	0	*
0	1	0	1	0	0	1	*	*	1
0	1	1	0	*	*	*	*	*	*
0	1	1	1	1	1	*	1	*	0
1	0	0	0	*	*	*	*	*	*
1	0	0	1	1	1	0	*	*	0
1	0	1	0	*	*	*	*	*	*
1	0	1	1	0	1	*	0	*	0
1	1	0	0	1	1	1	*	1	*
1	1	0	1	0	0	1	*	*	0
1	1	1	0	0	0	*	1	*	*
1	1	1	1	*	*	*	*	*	*
Количество единиц				4	7	3	4	2	3
Количество нулей				7	4	3	1	2	3

х. Если 2-ИЛИ (4 вентиля в одной микросхеме К555ЛЛ1) 2х4 единицы – 6 вентилей

2х3 единицы – 4 вентиля

7 единицы – 6 вентилей

2 единицы – 1 вентиль

Получается, что для реализации требуется 6 + 4 + 6 + 1 = 17, отсюда следует 5 корпусов микросхем К555ЛЛ1

В общем случае 7 корпусов ц. Если 3-ИЛИ (3-вентиля в одном корпусе микросхемы 54F11L)

2х4 единицы – 4 вентиля

2х3 единицы – 2 вентиля

7 единицы – 3 вентиля

2 единицы – 1 вентиль

Получается, что для реализации требуется 4 + 2 + 3 + 1 = 10, отсюда следует 4 корпуса микросхем 54F11L

В общем случае 6 корпусов ч. Если 3-ИЛИ и 2-ИЛИ

2х4 единицы – 2 вентиля 3ИЛИ и 2 вентиля 2ИЛИ

2х3 единицы – 2 вентиля 3ИЛИ

7 единицы – 3 вентиля

2 единицы – 1 вентиль 2ИЛИ

В общем случае 6 корпусов ш. Самая эффективная схема реализации получается схема реализации на мультиплексерах, если исходить из количества корпусов и места на плате. Цена микросхем при расчетах не учитывалась.

щ. Примерные цены микросхем, которые были использованы, расчетах, цены взяты из прайса за 25 апреля 2002 года без учета инфляции:

для реализации на мультиплексерах.

К155ТВ15 – 1 руб. 60 коп.

К155КП2 – 3 х 1 руб. 40 коп. = 4 руб. 20 коп.

К155ЛА3 – 4 руб 05 коп.

Общая стоимость 9 руб 85 коп.

Реализация в базисе И-НЕ

Реализация на микросхеме К564ЛА7 неэффективна из-за высокой цены на нее – 21 руб. 65 коп.

К176ЛА7 – 7 х 1 руб. 85 коп. = 12 руб 95 коп.

12 руб 95 коп. + 1 руб. 60 коп. = 14 руб 55 коп.

То есть из небольших сопоставлений даже по ценам видно, что реализация на мультиплексерах дешевле. По крайне мере можно сказать цены сопоставимы.

Оценим реализацию на дешифраторе с инверсией результата на выходе (К155ИД3, К555ИД3, КР1533ИД3):

Нам дан дешифратор

Так на выходе инверсный сигнал, то нам нужно осуществить следующую операцию:

Тогда, можно написать , отсюда можно сказать, что на выходе дешифратора нужно использовать элемент И-НЕ. Допустим серия К555:

– К555ЛА2 (1-8И-НЕ) – 1 корпус,

– К555ЛА3 (2-4И-НЕ) – 1 корпус,

– К555ЛА4 (3-3И-НЕ) – 1 корпус.

То есть вывод, что общее количество корпусов получается столько же как и на мультиплексерах, то есть пять. Дешифратор тогда возьмем серии К555 – К555ИД3. Триггеры этой же серии – К555ТВ9.

Схема прилагается ниже. Стоимость обоих схем реализации автомата примерно одинакова.

Схема: Рисунок 10

Рисунок 11

2. Программная реализация автомата.

Переход от исходного автомата Мили к эквивалентному автомату Мура.

Запишем совмещенную таблицу переходов.

Таблица 12. Совмещенная таблица переходов


*
	*
*	*
		*

Находим множество B_s, определяемые числом различных выходных сигналов на дугах, входящие в данное состояние:

Составляем таблицу перехода автомата Мура, на основании таблицы перехода автомата Мили и состояний

Таблица 13. Таблица переходов автомата Мура.



*	*	*
			*		'
*	*	*	*
				*	*

Программная реализация автомата Мура

1. Определяем требуемое число, двоичных разрядов, необходимое для представления кодов внутренних состояний, входных и выходных сигналов:

Количество двоичных разрядов, необходимое для кодирования всех входных сигналов:

и всех внутренних состояний (выходных сигналов):

2. Кодируем автомат

Таблица 14. Коды входных сигналов

Состояние входа	Биты кода
Состояние входа
	0	0
	0	1
	1	0
	1	1

Таблица 15

Внутреннее состояние	Биты кода			Биты кода		Выходной сигнал автомата Мили
Внутреннее состояние						Выходной сигнал автомата Мили
	0	0	0	0	1
	0	0	1	1	0
	0	1	0	1	1
	0	1	1	1	1
	1	0	0	1	0
	1	0	1	1	0
	1	1	0	0	1
	1	1	1	1	1

3. Переводим:

Таблица 16. Таблица переходов (выходов) в двоичной форме



*	*	*	000	000	001	010	010
000	000	000	101	101	*	011	011
*	*	*	011	011	*	110	110
111	111	111	110	110	100	*	*

4. Обозначим внутренне состояния автомата в последующем такте

Информация о работе

ВУЗ:

Новосибирский государственный технический университет (НГТУ)

Предмет:

Цифровые устройства и микропроцессоры

Тип:

Курсовые работы

Категория:

Информатика и выч. техника (Технические предметы)

Размер файла:

1 Mb

Скачали:

Скачать файл


	0	0	0	1	1	0	1	1

00	**	**	0*	*1	*1	0*	*1	*1
01	0*	0*	1*	*1	**	**	*1	*0
10	**	**	0*	*0	**	**	*0	*0
11	1*	1*	1*	*0	*1	1*	**	**


0		0			0		*			0		0			0		*			0			0		1			0		0			0		1
0		0			1		0			0		0			1		0			0			1		1			0		0			1		1
0		1			0		*			0		1			0		*			1			0		0			0		1			0		0
0		1			1		1			0		1			1		1			1			1		1			0		1			1		0
1		0			0		0			1		0			0		0											1		0			0		1
1		0			1		1			1		0			1		*											1		0			1		0
1		1			0		0			1		1			0		*											1		1			0		0
1		1			1		1			1		1			1		1											1		1			1		*
			0					0					0					0				1					1					1					1
			0					0					1					1				0					0					1					1
			0					1					0					1				0					1					0					1
			*					1					1					0				0					*					1					1
	0			0		0			0		0			0		0			0		1			1		1			1		1			1		1		1
	0			0		0			0		1			1		1			1		0			0		0			0		1			1		1		1
	0			0		1			1		0			0		1			1		0			0		1			1		0			0		1		1
	0			1		0			1		0			1		0			1		0			1		0			1		0			1		0		1
	*			0		0			1		0			*		0			1		*			*		1			0		1			0		0		*



*	*	*	000	000	001	010	010
000	000	000	101	101	*	011	011
*	*	*	011	011	*	110	110
111	111	111	110	110	100	*	*


	0	0	0	1	1	0	1	1

00	**	**	0*	*1	*1	0*	*1	*1
01	0*	0*	1*	*1	**	**	*1	*0
10	**	**	0*	*0	**	**	*0	*0
11	1*	1*	1*	*0	*1	1*	**	**


0		0			0		*			0		0			0		*			0			0		1			0		0			0		1
0		0			1		0			0		0			1		0			0			1		1			0		0			1		1
0		1			0		*			0		1			0		*			1			0		0			0		1			0		0
0		1			1		1			0		1			1		1			1			1		1			0		1			1		0
1		0			0		0			1		0			0		0											1		0			0		1
1		0			1		1			1		0			1		*											1		0			1		0
1		1			0		0			1		1			0		*											1		1			0		0
1		1			1		1			1		1			1		1											1		1			1		*
			0					0					0					0				1					1					1					1
			0					0					1					1				0					0					1					1
			0					1					0					1				0					1					0					1
			*					1					1					0				0					*					1					1
	0			0		0			0		0			0		0			0		1			1		1			1		1			1		1		1
	0			0		0			0		1			1		1			1		0			0		0			0		1			1		1		1
	0			0		1			1		0			0		1			1		0			0		1			1		0			0		1		1
	0			1		0			1		0			1		0			1		0			1		0			1		0			1		0		1
	*			0		0			1		0			*		0			1		*			*		1			0		1			0		0		*



*	*	*	000	000	001	010	010
000	000	000	101	101	*	011	011
*	*	*	011	011	*	110	110
111	111	111	110	110	100	*	*

Синтез конечного автомата Мили. Построение графа конечного автомата. Определение количество элементов памяти. Программная реализация автомата

Страницы работы

Фрагмент текста работы

Похожие материалы

Информация о работе


	0	0	0	1	1	0	1	1

00	**	**	0*	*1	*1	0*	*1	*1
01	0*	0*	1*	*1	**	**	*1	*0
10	**	**	0*	*0	**	**	*0	*0
11	1*	1*	1*	*0	*1	1*	**	**


0		0			0		*			0		0			0		*			0			0		1			0		0			0		1
0		0			1		0			0		0			1		0			0			1		1			0		0			1		1
0		1			0		*			0		1			0		*			1			0		0			0		1			0		0
0		1			1		1			0		1			1		1			1			1		1			0		1			1		0
1		0			0		0			1		0			0		0											1		0			0		1
1		0			1		1			1		0			1		*											1		0			1		0
1		1			0		0			1		1			0		*											1		1			0		0
1		1			1		1			1		1			1		1											1		1			1		*
			0					0					0					0				1					1					1					1
			0					0					1					1				0					0					1					1
			0					1					0					1				0					1					0					1
			*					1					1					0				0					*					1					1
	0			0		0			0		0			0		0			0		1			1		1			1		1			1		1		1
	0			0		0			0		1			1		1			1		0			0		0			0		1			1		1		1
	0			0		1			1		0			0		1			1		0			0		1			1		0			0		1		1
	0			1		0			1		0			1		0			1		0			1		0			1		0			1		0		1
	*			0		0			1		0			*		0			1		*			*		1			0		1			0		0		*



*	*	*	000	000	001	010	010
000	000	000	101	101	*	011	011
*	*	*	011	011	*	110	110
111	111	111	110	110	100	*	*