Синтез синхронного управляющего автомата

Федеральное агентство  по образованию

 

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

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

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ГОУВПО «ВГТУ»)

 

Факультет информационных технологий и компьютерной безопасности

 

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

Специальность «Вычислительные  машины, комплексы, системы и сети»

 

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

по дисциплине «Теория автоматов»

 

Тема работы «Синтез синхронного управляющего автомата»

 

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

 

Разработал                                        А. П. Замогилин

                                                              Подпись, дата    Инициалы, фамилия

 

Руководитель                                                  Ю. С. Акинина

Подпись, дата    Инициалы, фамилия

 

Нормоконтроль провел                                                  Ю. С. Акинина

Подпись, дата    Инициалы, фамилия

 

 

Защищена _______________   Оценка _______________

          Дата

 

 

 

 

Воронеж 2013

 

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

 

ФАКУЛЬТЕТ  АВТОМАТИКИ И ЭЛЕКТРОМЕХАНИКИ

 

КАФЕДРА Автоматизированные и вычислительные системы 

 

ЗАДАНИЕ

на курсовой проект

по дисциплине " ТЕОРИЯ АВТОМАТОВ"

 

Тема проекта: "Синтез синхронного управляющего автомата"

Студент группы_____________________________________________

                                                       ^{фамилия, имя, отчество}

Номер варианта___G - 3.H-4.______________________________________

Технические условия: тип управляющего автомата – Мили; способ кодирования внутренних состояний автомата – эффективное 1; тип триггерных схем – комбинированные синхронные двухтактные  D триггеры; элементная база логического преобразователя – двухуровневая программируемая логическая матрица; количество входных сигналов УА – 6; количество выходных сигналов (микроопераций) УА – 7; количество микрокоманд УА  – 8; количество микроопераций в каждой микрокоманде – 3-5; количество операторных вершин ГСА – 9; количество условных вершин ГСА – 8; разновидность УА –не инициальный.

Содержание и объем проекта (графические работы, расчеты и прочее): расчетно - пояснительная записка –15…20 страниц формата А4; поясняющие текст, рисунки, расчеты, таблицы и т.п.); схема электрическая функциональная УА.

 

Сроки выполнения этапов: 1^й-этап - _________;  2^й-этап - ___________

Срок защиты курсового  проекта: с ______________по ______________

 

Задание принял студент(ка) гр.                                          /                         /

                                                       ^{подпись,  дата                                           инициалы,  фамилия}             

Руководитель                                                                        /                         /

                                                        ^{подпись,  дата                                           инициалы,  фамилия}     

 

 

 

 

 

 

 

 

 

 

 

ЗАМЕЧАНИЯ РУКОВОДИТЕЛЯ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

Задание......................................................................................................................2

Введение....................................................................................................................5

1 Общие принципы построения  и реализации синхронных управляющих  автоматов (УА)...........................................................................................................................6

1.1 Обобщенная структура и принцип  функционирования синхронных управляющих  автоматов..................................................................................................................9

1.2 Последовательность синтеза  синхронных управляющих автоматов...........12

1.3 Современная элементная база  для реализации логических преобразователей  и блоков памяти УА...................................................................................................14

1.4 Исходные данные для курсового  проектирования........................................15

2 Разработка (или Анализ) ГСА синтезируемого УА и детализация  его структурной схемы........................................................................................................................17

2.1 Разработка (или Анализ) и разметка ГСА.......................................................17

2.2 Структурное кодирование  внутренних состояний УА..................................21

2.3 Детализация блока памяти  УА.........................................................................24

3 Структурный синтез логического  преобразования УА.....................................27

3.1 Разработка расширенной структурной таблицы переходов и выходов УА..............................................................................................................................27

3.2 Составление логических уравнений  для выходных сигналов и функций  возбуждения триггеров...........................................................................................28

3.3 Минимизация логических уравнений..............................................................30

4 Разработка и оформление схемы  электрической функциональной синтезированного синхронного УА.......................................................................33

Заключение...............................................................................................................35

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

 

 

 

 

Введение

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

Основной целью курсового  проектирования является закрепление  знаний по дисциплине «Теория автоматов», путем их практического применения в работе. Курсовой проект требует  применения широкого спектра знаний полученных в ходе обучения.

Объектом курсового  проектирования является синхронный управляющий автомат (УА), реализующий некоторый алгоритм функционирования, который формально задается таким начальным языком описания как граф-схема алгоритма (ГСА).

Результатом работы является электрическая функциональная схема управляемого автомата. Элементным базисом для синтеза являются двухуровневая программируемая логическая матрица (ПЛМ) с требуемыми характеристиками и различные типы комбинированных синхронных триггерных схем.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Общие принципы построения и реализации синхронных управляющих автоматов (УА)

 

Объектом курсового  проектирования является синхронный управляющий автомат (УА), реализующий некоторый алгоритм функционирования, который формально задается таким начальным языком описания как граф-схема алгоритма (ГСА). Синтезируемый УА на наивысшем уровне абстракции (на уровне "черного ящика") представим так, как показано на рисунке 1.1.

s

 х₁                                                                                                          y₁

 

                                           

 

   х_n                                                                                                    y_m

        

 

Рисунок 1.1 - Представление синтезируемого УА на уровне "черного ящика"

 

Словесно работу синхронного УА, представленного на уровне "черного ящика", можно описать следующим образом. На входы УА поступают входные сигналы х₁ … х_n, каждый из которых принимает одно из двух различимых значений, например, 1 или 0. На каждом i – ом шаге алгоритма работы, УА формирует некоторую совокупность Y_i выходных сигналов из множества y₁ … y_m, каждый из которых также может принимать одно из значений 1 или 0. Сигналы х₁ … х_n принято называть логическими условиями; сигналы y₁ … y_m – микрооперациями, а Y_i – микрокомандами. Переход на новый шаг алгоритма осуществляется только с приходом специального сигнала синхронизации (s). Выбор следующего шага алгоритма работы УА полностью предопределен его ГСА, а именно текущим шагом алгоритма и значениями одного или нескольких сигналов х₁ … х_n.

Выходные сигналы (микрооперации) y₁ … y_m могут иметь различную длительность: в одном случае они не могут быть больше длительности сигнала синхронизации, в другом – примерно равны интервалу времени  между i-ым  и (i+1)-ым шагами алгоритма работы УА, т.е. примерно равны периоду следования сигналов синхронизации. Иными словами, одни УА формируют выходные (короткие) сигналы непосредственно перед переходом на следующий шаг алгоритма, а другие формируют выходные (длинные) сигналы непосредственно после перехода на текущий  шаг алгоритма и вплоть до перехода на последующий шаг алгоритма. Математической моделью управляющих автоматов, формирующих короткие выходные сигналы, является модель Мили, а для автоматов, формирующих длинные выходные сигналы – модель Мура.

Математические  модели Мили и Мура позволяют провести следующий шаг детализации структуры проектируемого УА, который представляется состоящим из двух взаимосвязанных функциональных частей – логического преобразователя (ЛП) и блока памяти (БП), так, как это показано на рис.1.2.

 

            х₁                                                       y₁

            х_n                                                 y_m

 

 

 

 

 

                   d₁                                      f₁

 

                   d_r                                       f_r

                  s

 

Рис.1.2. Первый уровень структурной  детализации УА в соответствии с моделями Мили и Мура

 

Логический преобразователь (ЛП) представляет собой комбинационную схему (или комбинационный автомат). Блок памяти (БП) содержит r элементов памяти, которыми для синхронных автоматов являются специально разработанные синхронные элементарные автоматы с памятью, которые стали называть триггерами. Наибольшее распространение получили несколько разновидностей синхронных триггеров, которые получили следующие наименования: RS – триггер,  D – триггер, T – триггер, JK – триггер. Отличаются данные триггеры количеством информационных и управляющих сигналов, а также способами записи в них хранимой информации. При использовании различных типов триггеров может существенно меняться сложность проектируемого управляющего автомата как в части сложности ЛП, так и в части сети связи между ЛП и БП. Наиболее эффективным является использование D –  и    T – триггеров,    в которые     легко  модифицируются       RS – и   JK – триггеры. 

Блок памяти на своих выходах d₁ … d_r должен формировать двоичный код, который соответствует  номеру текущего шага алгоритма УА, или, как принято говорить в теории автоматов, соответствует текущему внутреннему состоянию автомата. Предварительно все возможные внутренние состояния  УА обозначаются некоторыми абстрактными символами (чаще всего какой-либо буквой с соответствующим индексом), которым затем ставятся в однозначное соответствие двоичные структурные коды. На входы блока памяти должны воздействовать сигналы f₁ … f_r, которые формируются ЛП и в совокупности образуют двоичный код, соответствующий структурному коду следующего внутреннего состояния УА.  Совокупность одновременно формируемых сигналов f₁ … f_r принято называть функцией возбуждения блока памяти, а каждый отдельный сигнал f₁ … f_r - функциями возбуждения элементов памяти.

Задачей логического  преобразователя является формирование выходных сигналов УА и функций возбуждения элементов памяти как некоторой системы логических функций, аргументами которых являются переменные x₁… x_n , d₁…d_r . Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализовываться логическим преобразователем (ЛП).

В качестве элементного базиса для  реализации ЛП выбрана двухуровневая  программируемая логическая матрица (ПЛМ). Это  обусловлено тем, что в настоящее время ПЛМ являются весьма доступными для широкого круга пользователей, высоко экономичными как для серийного, так и для разового производства изделий вычислительной техники, ориентированы на реализацию системы логических функций, представленных в дизъюнктивных нормальных формах (ДНФ). Весьма существенным является также и то, что при использовании ПЛМ в качестве элементного базиса для ЛП предоставляется возможность реализации в рамках данного курсового проекта УА достаточной сложности при  компактном его графическом изображении в виде схемы электрической функциональной.