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

 

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

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

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

 

 

 

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

 

 

Вариант №  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. Разметка ГСА автомата Мили

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

 

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

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

 

Таблица 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/-


 

 

 

 

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

 

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

Состояние

q0

q1

q2

Код α1α2

00

01

10


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

 

Таблица 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/-


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

 

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

  _  _

y1= α1α2x1

       _    

y2= α1α2x2x3

        _     _

y3= α1α2x2

           _

y4= α1α2x4

           _  _

y5= α1α2x4x5

 

 

 

    1. Построение функций возбуждения автомата Мили на 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-триггеров:

 

      _            _   _            _  _  _        _

R1= α1α2x4 + α1α2 x4x5 + α1α2 x4x5= α1α2

        _     _     _                            _    _

S1= α1α2x2 + α1α2 x2x3 + α1α2 x2x3= α1α2

        _     _     _                            _    _

R2= α1α2x2 + α1α2 x2x3 + α1α2 x2x3= α1α2

        _  _

S2= α1α2

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

 

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

 

 

 

 

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

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

 

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

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

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

 

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

 

 

 

 

 

 

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

 

Таблица 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


 

 

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

 

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

Состояние

q0

q1

q2

q3

q4

q5

Код α1α2α3

000

001

010

011

100

101


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

 

Таблица 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


 

 

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

 

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

  _  _

y1= α1α2α3

       _    _

y2= α1α2α3

       _     

y3= α1α2α3

           _  _

y4= α1α2α3

           _

y5= α1α2α3

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

 

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

состояние

входной сигнал

00

01

10

0

0

1

0

1

1

1

0


 

 

 

 

 

 

 

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

 

состояния

000

001

010

011

100

101

входные сигналы

            

 

x1

*0,*0,01

          

_

x1x2x3

*0,01,*0

          

___

x1x2

*0,01,01

          

_     _

x1x2x3x4

01,*0,*0

          

_     _  _

x1x2x3x4x5

01,*0,01

          

_     _ _ _

x1x2x3x4x5

*0,*0,*0

          

 

x2x3

  

*0,01,10

        

_

x2

  

*0,01,01

        

    _

x2x3x4

  

01,*0,10

        

   _  _

x2x3x4x5

  

0,*0,0*

        

    _     _

x2x3x4x5

  

*0,*0,10

        

 

x4

    

01,10,*0

01,10,10

    

_

x4x5

    

01,10,01

01,10,0*

    

_  _

x4x5

    

*0,10,*0

*0,10,10

    

1

        

10,*0,*0

10,*0,10


 

 

 

 

 

 

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

      _ _        _            _ 

R1= α1α2α3+ α1α2α3= α1α2

       _ _  _ _     _        _ _  _ _     _ _        _ _        _        _  _       _  _       _            _     _

S1= α1α2α3x1x2x3x4+ α1α2α3x1x2x3x4x5+ α1α2α3x2x3x4+ α1α2α3x2x3x4x5+ α1α2x4+ α1α2x4x5

        _           _    _        _     _ _

R2= α1α2x4+ α1α2x4x5+ α1α2x4x5= α1α2

       _ _  _ _            _ _ _  _ _     _ _               _ _    _  

S2= α1α2α3x1x2x3+ α1α2α3x1x2+ α1α2α3x2x3+ α1α2α3x2

       _ _                _ _        _  _    _ _        _     _    _            _    _ _        _

R3= α1α2α3x2x3+ α1α2α3x2x3x4+ α1α2α3x2x3x4x5+ α1α2x4+ α1α2x4x5+ α1α2α3

       _ _  _        _ _  _ _ _     _ _  _ _     _ _        _    _

S3= α1α2α3x1+ α1α2α3x1x2+ α1α2α3x1x2x3x4x5+ α1α2x4x5

 

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

 

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

 

 

 

 

 

Заключение

 

Построение автоматов  было произведено успешно, моделирование  с помошью компьютера показало правильную работу автоматов.

Автомат Мура, построенный  по данной ГСА, содержит больше элементов, чем автомат Мили, построенный  по той же ГСА. Для кодирования  состояний автоматов Мура требуется  трёхразрядный код, в отличие  от автомата Мили, для которого используется двухразрядный код, а следовательно  и соответствующее количество RS-триггеров.

Таблица 10. Сравнительный анализ элементов автоматов

Логический элемент

Кол-во элементов в автомате

Мили

Мура

Элемент памяти (RS)

2

3

Инвертор (НЕ)

2

5

Двухвходовой конъюнктор (И)

3

2

Трёхвходовой конъюнктор (И)

3

8

Четырехвходовой конъюнктор (И)

2

5

Пятивходовой конъюнктор (И)

-

4

Шестивходовой конъюнктор (И)

-

3

Семивходовой конъюнктор (И)

-

4

Восьмивходовой конъюнктор (И)

-

2

Четырехвходовой дизъюнктор (ИЛИ)

-

2

Шестивходовой дизъюнктор (ИЛИ)

-

2

Всего элементов

12

40


 

 

 

 

 

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

 

 

  1. Савельев А.Я. Прикладная теория цифровых автоматов. – М. Высшая школа. 1987, 272 с.
  2. Самофалов К.Г. Прикладная теория цифровых автоматов. – К. Высшая школа. 1987, 375 с.
  3. Прикладная теория цифровых автоматов. Часть 3. Логические основы и абстрактная теория автоматов: Методические указания к лабораторным работам / Смирнов Г.Б. – Екатеринбург, УГТУ, 1996, 32 с.
  4. Прикладная теория цифровых автоматов. Часть 4. Проектирование цифровых автоматов с памятью: Методические указания к лабораторным работам / Смирнов Г.Б. – Екатеринбург, УГТУ, 1996, 28 с.
  5. Прикладная теория цифровых автоматов. Часть 4. Построение и моделирование логических схем в пакете "LCS": Методические указания к лабораторным работам/ Смирнов Г.Б. – Екатеринбург.

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

Схема автомата Мили

 

 

 

 

 

 

 

 

Приложение 2

Схема автомата Мура: