Синтез цифрового автомата с памятью

 

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

  ГОУ ВПО  Уральский Федеральный Университет  имени первого Президента России  Б. Н. Ельцина

Кафедра вычислительной техники

 

 

 

Синтез цифрового  автомата с памятью

 

 

Вариант №  10

 

Курсовой  проект

по дисциплине “Теория Автоматов”

Пояснительная записка

23.01.01 код  ЕСКД 070 ПЗ

 

 

 

Руководитель        Г. Б. Смирнов

д-р  техн. наук, проф.

 

Студент

Группы  Фт-28082       П. С. Манылов

 

 

 

 

 

 

Екатеринбург   2010

Оглавление

Задание на курсовое проектирование 3

Основная часть 5

1. Проектирование автомата Мили 5

1.1 Разметка ГСА 5

1.2 Построение графа переходов-выходов 6

1.3 Составление таблицы переходов-выходов 6

1.4 Кодирование состояний автомата 7

1.5 Составление структурной таблицы переходов-выходов 7

1.6 Построение функций выхода автомата Мили 7

1.7 Построение функций возбуждения автомата Мили на RS-триггерах 8

1.8 Построение логической схемы автомата Мили 8

2. Проектирование автомата Мура 9

2.1 Разметка ГСА 9

2.2 Построение графа переходов-выходов 10

2.3 Составление таблицы переходов-выходов 11

2.4 Кодирование состояний автомата 12

2.5 Составление структурной таблицы переходов-выходов 12

2.6 Построение функций выхода автомата Мура 13

2.7 Построение функций возбуждения автомата Мура на RS-триггерах 13

2.8 Построение логической схемы автомата Мура 15

Заключение 16

Список литературы 17

Приложение 1 18

Приложение 2 19

 

 

 

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

Спроектировать  цифровые автоматы Мили и Мура с  памятью в Булевом базисе по заданной ГСА (рисунок 1). В качестве элемента памяти выбрать RS-триггер.

 

Для каждого автомата:

1. Разметка ГСА;
2. Построение графа переходов-выходов;
3. Составление таблицы переходов-выходов;
4. Кодирование состояний;
5. Составление частично структурированной таблицы переходов-выходов;
6. Построение функций выходов автомата;
7. Построение таблицы функций возбуждения выходов для заданного типа триггера;
8. Построение функций возбуждения;
9. Построение логической схемы автомата;
10. Экспериментальная проверка автомата;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

рис. 1. Исходная ГСА проектируемого автомата

Основная часть

1. Проектирование автомата Мили

1. Разметка ГСА

 

Производим разметку заданной ГСА для автомата Мили:

рис. 2. Разметка ГСА автомата Мили

2. Построение графа переходов-выходов

 

рис. 3. Граф переходов-выходов  для автомата Мили

3.  Составление таблицы переходов-выходов

 

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

Состояние автомата	Входной сигнал
	x1	_ x1	_ x2	x2x3	_ x2x3	x4	_ x4x5	_ _ x4x5
q0	q1/y1	q1/-
q1			q2/y3	q2/y2	q2/-
q2						q0/y4	q0/y5	q0/-

 

 

 

 

4. Кодирование состояний автомата

 

Таблица 2. Кодирование состояний  автомата Мили

Состояние	q0	q1	q2
Код α1α2	00	01	10

5. Составление структурной таблицы переходов-выходов

 

Таблица 3. Структурная таблица переходов-выходов

Состояние автомата α1α2	Входной сигнал
	x1	_ x1	_ x2	x2x3	_ x2x3	x4	_ x4x5	_ _ x4x5
00	01/y1	01/-
01			10/y3	10/y2	10/-
10						00/y4	00/y5	00/-

6. Построение функций выхода автомата Мили

 

Функции выхода автомата Мили:

  _  _

y₁= α₁α₂x₁

       _    

y₂= α₁α₂x₂x₃

        _     _

y₃= α₁α₂x₂

           _

y₄= α₁α₂x₄

           _  _

y₅= α₁α₂x₄x₅

 

 

 

7. Построение функций возбуждения автомата Мили на RS-триггерах

 

Таблица 4. Таблица истинности RS-триггера

состояние	входной сигнал
	00	01	10
0	0	1	0
1	1	1	0

 

Таблица 5. Функции возбуждения  автомата Мили на RS-триггерах

Состояние автомата α1α2	Входной сигнал
	x1	_ x1	_ x2	x2x3	_ x2x3	x4	_ x4x5	_ _ x4x5
00	*0,01	*0,01
01			01,10	01,10	01,10
10						10,*0	10,*0	10,*0

 

Таким образом, получаем входные  сигналы для RS-триггеров:

 

      _            _   _            _  _  _        _

R₁= α₁α₂x₄ + α₁α₂ x₄x₅ + α₁α₂ x₄x₅= α₁α₂

        _     _     _                            _    _

S₁= α₁α₂x₂ + α₁α₂ x₂x₃ + α₁α₂ x₂x₃= α₁α₂

        _     _     _                            _    _

R₂= α₁α₂x₂ + α₁α₂ x₂x₃ + α₁α₂ x₂x₃= α₁α₂

        _  _

S₂= α₁α₂

8. Построение  логической схемы автомата Мили

 

Логическая схема автомата Мили представлена в приложении 1.

 

 

 

 

2. Проектирование автомата Мура

1. Разметка ГСА

 

Производим разметку заданной ГСА для автомата Мура:

рис. 4. Разметка ГСА автомата Мура

2. Построение графа переходов-выходов

 

рис. 5. Граф переходов-выходов для автомата Мура

 

 

 

 

 

 

3. Составление таблицы переходов-выходов

 

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

функции выхода		y1	y2	y3	y4	y5
состояния	q0	q1	q2	q3	q4	q5
входные сигналы
x1	q1
_ x1x2x3	q2
___ x1x2	q3
_     _ x1x2x3x4	q4
_     _  _ x1x2x3x4x5	q5
_     _ _ _ x1x2x3x4x5	q0
x2x3		q2
_ x2		q3
_ x2x3x4		q4
_  _ x2x3x4x5		q5
_     _ x2x3x4x5		q0
x4			q4	q4
_ x4x5			q5	q5
_  _ x4x5			q0	q0
1					q0	q0

 

 

4. Кодирование состояний автомата

 

Таблица 7. Кодирование состояний автомата Мура

Состояние	q0	q1	q2	q3	q4	q5
Код α1α2α3	000	001	010	011	100	101

5. Составление структурной таблицы переходов-выходов

 

Таблица 8. Структурная таблица переходов-выходов

функции выхода		y1	y2	y3	y4	y5
состояния	000	001	010	011	100	101
входные сигналы
x1	001
_ x1x2x3	010
___ x1x2	011
_     _ x1x2x3x4	100
_     _  _ x1x2x3x4x5	101
_     _ _ _ x1x2x3x4x5	110
x2x3		010
_ x2		011
_ x2x3x4		100
_  _ x2x3x4x5		101
_     _ x2x3x4x5		110
x4			100	100
_ x4x5			101	101
_  _ x4x5			000	000
1					000	000