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

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

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

Государственное общеобразовательное учреждение высшего профессионального образования

«Воронежский государственный технический университет»

«Автоматика и электромеханика»

Кафедра: «Автоматизированные и вычислительные системы»

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

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

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

Введение

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

На начальных этапах изучения автоматы в ТА представляются как «чёрные ящики», имеющие только входные и выходные сигналы. Само устройство «чёрного ящика» при этом считается неизвестным. Если это малоизвестный объект, то изучение начинают с выявления его элементов, а затем и его структуры. В дальнейшем анализ устройства автомата подробно детализируют (проводят декомпозицию устройства).

Синтез любого автомата начинается со словесного описания его функций и дельнейшим переходом к его математическому описанию. Математически работа автомата может быть описана законами преобразования букв входного алфавита в буквы выходного алфавита.

Автоматы могут быть реализованы как аппаратно, так и программно. Автоматы, реализуемые чисто аппаратно называют «автоматами с жесткой логикой». Для них характерно максимальное быстродействие, но требуются значительные затраты на разработку и изготовление на производстве, поскольку каждый реализуемый автомат требует нового набора элементов логики и новой схемы. С появлением микропроцессоров (МП) и различных типов запоминающих устройств, появилась возможность программной реализации автоматов. Для этого требуется лишь разработка программы, реализующей заданный алгоритм работы. Такие автоматы получили название «автоматов с гибкой логикой». автомат память триггер

Модификацией конечного автомата «с жесткой логикой» является синхронный управляющий автомат (УА) с памятью, один из вариантов которого предполагается реализовать в настоящем курсовом проекте. Для подобных автоматов характерно то, что моменты времени, в которых фиксируются изменения состояния, задаются внешним генератором синхронизирующих импульсов, а память такого автомата формируется набором комбинированных синхронных триггерных схем.

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

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

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

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

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

Проектируемый управляющий автомат на наивысшем уровне абстракции можно представить как на рисунке 1.

Рисунок 1

Работу синхронного УА можно описать следующим образом: на входы управляющего автомата поступают входные сигналы x1…xn, каждый из которых принимает значение логического нуля или логической единицы.

На каждом шаге работы автомата формируются некоторая совокупность выходных сигналов y1…ym. Их принято называть микрооперациями, а Y - микрокомандами. Каждая микрооперация может принимать одно из двух значений. Новый шаг работы алгоритма начинается с приходом синхронизирующего сигнала S.

В соответствии с моделями Мили и Мура управляющий автомат можно детализировать, как показано на рисунке 2.

Рисунок 2

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

Управляющий автомат можно рассматривать как устройство, реализующее алгоритм функционирования систем управления, задающий последовательность выполнения тех или иных операций по управлению некоторым объектом. Управляющий автомат реализует разнообразные функции: контролирует значения входных/выходных сигналов, выполняет логические/арифметические операции, поддерживает необходимые значения параметров, обеспечивает связь с датчиками и исполнительными устройствами.

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

? выбор типа элементов памяти;

? кодирование состояний автомата, входных и выходных сигналов в структурном алфавите;

? детализация блока памяти;

? составление расширенной структурной таблицы переходов и выходов;

? канонический синтез логического преобразователя;

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

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

Развитие микроэлектроники в начале 60-х гг. прошлого века привело к созданию интегральных микросхем, которые представляют собой функциональные узлы электронной аппаратуры, все компоненты и соединительные проводники которой изготавливаются в объеме или на поверхности полупроводникового кристалла в едином технологическом цикле. В первых интегральных микросхемах (ИМС) на кристалле изготавливались логические элементы, реализующие элементарные логические функции.

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

Сложность ИМС принято оценивать количеством размешенных на кристалле логических элементов. По этому критерию цифровые ИМС подразделяются на следующие уровни:

МИС - малые интегральные схемы, малого уровня сложности (до десяти логических элементов);

СИС - интегральные схемы средней сложности (до ста логических элементов);

БИС - большие интегральные схемы (до тысячи логических элементов);

СБИС - сверхбольшие интегральные схемы (до десяти тысяч элементов);

УБИС - ультра большие (до ста тысяч элементов).

С увеличением плотности компоновки логических элементов на кристалле обострилась проблема экономической обоснованности того, какие функциональные узлы целесообразно реализовывать в интегральном исполнении с тем, чтобы это было экономически выгодно. Естественным выходом в этих условиях стало изготовление заказных БИС, которые разрабатывались каждый раз специально для конкретного применения. Однако потребление таких ИМС постоянно снижалось, поскольку специализация подобных БИС привела к ограничению их области применения. По этой причине были разработаны БИС, программируемые пользователем, в структуру которых на этапе производства вводят избыточное количество ПП элементов и связей, часть которых в процессе программирования в дальнейшем разрушается.

К числу таких ИМС относят двухуровневые программируемые логические матрицы (ПЛМ). Схема электрическая функциональная незапрограммированной ПЛМ показана на рисунке 3. Каждая из матриц представляет собой систему ортогональных проводников, в местах пересечений которых установлены ПП элементы. В матрице "И" этим элементом является диод (рисунок 4а), а в матрице "ИЛИ" ? триод или транзистор (рисунок 4б). С помощью диодов и резисторов нагрузки Rl...Rq на промежуточных шинах Zl...Zq формируются элементарные конъюнкции над любыми значениями входных переменных. На шинах Y1...Yt формируются элементарные дизъюнкции над сигналами, поступающими по шинам Zl...Zq. Дизъюнкции реализуются с помощью транзисторов и соответствующих резисторов нагрузки Rq+1...Rq+t.

Рисунок 3 - Схема электрическая функциональная двухуровневой ПЛМ

Рисунок 4 - Подключение ПП элемента в узлах ПЛМ:

а) диод, б) триод (транзистор)

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

Cхема электрическая функциональная запрограммированной ППЛМ изображается примерно так же, как представлено на рисунке 3. Отличие состоит в том, что метки () на схеме проставляют только в тех узлах матрицы ППЛМ, в которых должны быть подключены диоды и транзисторы, обеспечивающие реализацию логических уравнений.

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

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

Задание на курсовое проектирование включает в себя следующие исходные данные:

? тип синхронного УА - автомат Мили;

? способ кодирования состояний УА - «тривиальный»;

? тип синхронных триггеров - комбинированный синхронный двухтактный JK-триггер.

Рисунок 5 - ГСА проектируемого УА

На рисунке 5 видно, что количество условных вершин ГСА равно 6, множество соответствующих входных сигналов будет X={x1, x2, x3, x4, x5, x6}, количество микрокоманд равно 8, тогда множество микрокоманд Y определятся как {Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8}. Таблица 1, взятая согласно варианту из учебного пособия, определяет, что множеству микрокоманд Yi соответствуют следующие подмножества микроопераций:

Таблица 1- Состав микрокоманд управляющего автомата

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

2.1 Разработка и разметка ГСА

Граф схема алгоритма - это ориентированный связный граф, содержащий одну начальную вершину, произвольное число условных и операторных вершин и одну конечную вершину. Условная вершина имеет два выхода, которые отмечаются символами 1 (выполнение условия) и 0 (невыполнение условия).

Правило разметки ГСА при реализации автомата по модели Мили:

- символом начального состояния а1 отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

- входы всех вершин, следующих за операторными, отмечаются различными символами а2 …аi …аn;

- входы вершин ГСА, следующих за операторными, должны быть отмечены только одним единственным символом аi.

С учетом этих правил ГСА будет размечена, как показано на рисунке 6.

Рисунок 6 - Размеченная ГСА синхронного УА

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

На основании проведенной разметки ГСА и материалов первого раздела курсовой работы структурное кодирование внутренних состояний УА будет выполнено следующим образом.

Строится прямая таблицу переходов и выходов. Для автомата типа Мили она имеет вид (таблица 2).

Таблица 2 - Прямая таблица переходов и выходов