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

 

 

 

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

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

 

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

 

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

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

 

Номер варианта:

Технические условия: тип управляющего автомата – Мура; способ кодирования внутренних состояний автомата – первый эффективный способ структурного кодирования; тип триггерных схем – комбинированные синхронные двухтактные  D-триггеры; элементная база логического преобразователя – двухуровневая программируемая логическая матрица.

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

 

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

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

 

Задание принял студент              ____________________                                                      Подпись, дата           Инициалы, фамилия

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

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

 

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

 

Содержание

 

Введение

Одной из дисциплин для специальности  ”Вычислительные машины, комплексы, системы и сети” является "Теория автоматов", обязательным минимумом  содержания которой для дипломированного специалиста является [1]:

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

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

Согласно ГОСТ 22487-77 под проектированием  понимается процесс последовательного составления и детализации взаимосогласованных модельных описаний еще не существующего материального объекта. Таким образом, в результате проектирования объект проектирования еще не материализуется, а создается его прообраз на другой материальной основе (чертежи, схемы, текстовые документы и т.п.). Причем этот прообраз может быть необходим для дальнейшего проектирования, а может быть уже достаточным для материализации объекта проектирования.

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

  

 

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

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

 

     Управляющий автомат (УА) генерирует последовательность управляющих сигналов из множества у₁ . . . у_m (сигналы у₁ . . . у_m называются микрооперациями, каждый из сигналов может принимать только одно из значений 1 или 0), предписанную микропрограммой У; и соответствующую значениям логическим условий х₁...х_n. При выполнении процессором пакета  микропрограмм на его входы последовательно подаются коды операции, которые соответствуют той или иной микропрограмме. На входы процессора

могут поступать внешние сигналы логических условий, а с выходов сниматься сигналы для управления внешними устройствами.

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

 

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

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

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

 

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

 

     ГСА удовлетворяет  следующим условиям:

 

1) входы  и выходы вершин  соединяются  друг с другом  с помощью  дуг, направленных  всегда от выхода ко входу;

 

2) каждый выход соединён только  с одним входом;

 

3) любой  вход соединяется, по крайней  мере, с одним выходом;

 

4) любая  вершина ГСА лежит,  по крайней  мере, на одном  пути из начальной вершины  к конечной;

 

5) в  каждой условной вершине  записывается один из элементов  множества Х={ х1...хn } логических условий  (разрешается в различных условных вершинах запись одинаковых элементов множества Х);

 

6) один  из выходов условной  вершины,  помеченный «0» или  « 1 »,  может соединяться с  её входом;

 

7) в  каждой операторной вершине  записывается  оператор (микрокоманда) У; - подмножество множества микроопераций У={ у1...уm } (разрешается запись в различных операторных вершинах одинаковых микрокоманд).

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

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

 

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

ЛП  представляет собой комбинационную схему. БП содержит r элементов памяти, которыми для синхронных автоматов  являются специально разработанные  синхронные элементарные автоматы с памятью, которые стали называть триггерами.

 

     Наибольшее  распространение  получили несколько  разновидностей  синхронных триггеров, которые  получили следующие наименования: RS - триггер, D - триггер, Т - триггер, JK - триггер. Отличаются данные триггеры количеством информационных и управляющих сигналов, а также способами записи в них хранимой информации.

 

     Блок  памяти на  своих выходах d1 . .dr должен формировать  двоичный код, который соответствует  номеру текущего шага алгоритма УА, или текущему внутреннему состоянию автомата. Предварительно все возможные внутренние состояния УА обозначаются некоторыми абстрактными символами, которым затем ставятся в однозначное соответствие двоичные структурные коды. На входы блока памяти должны воздействовать сигналы f1. . . fr, которые формируются ЛП и в совокупности образуют двоичный код, соответствующий структурному коду следующего внутреннего состояния УА. Совокупность одновременно формируемых сигналов f1 . . . fr принято называть функцией возбуждения блока памяти, а каждый отдельный сигнал f1. . . fr - функциями возбуждения элементов памяти.

 

     Задачей логического  преобразователя является формирование  выходных сигналов УА и функций  возбуждения элементов памяти  как некоторой системы логических функций, аргументами которых являются переменные х1, . . .хn, d1...dr. Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализоваться логическим преобразователем.

 

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

 

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

 

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

 

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

 

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

2.1 Анализ и разметка ГСА

Задание:

Рисунок 6 - ГСА

 

 

Таблица 1 – Условия

 

Вариант	Тип УА		Способ кодирования			Тип синхронных триггеров				ГСА
	Мили	Мура	Трив.	Эфф. 1	Эфф. 2	RS	D	T	JK
5		+	+						+	2.8

 

 

 

 

 

Таблица 2 - Микрооперации

 

 

Yi	микрооперации
	y1	y2	y3	y4	y5	y6	y7
Y1	1	0	1	0	0	1	0
Y2	0	0	0	0	1	0	1
Y3	0	0	1	0	1	0	1
Y4	0	1	1	0	0	0	0
Y5	1	0	0	1	1	0	1
Y6	0	1	0	1	0	0	0
Y7	1	1	0	1	0	1	1
Y8	1	0	1	0	1	1	1
Y9	0	0	0	1	0	0	1
Y10	0	1	0	0	1	0	0

 

 

Произведем разметку граф - схемы  алгоритма, руководствуясь следующими пунктами:

-символом начального состояния а₁ отмечаются начальная и конечная операторные вершины;

-все операторные вершины отмечаются  различными символами а₂ …а_i …а_n;

-каждая операторная вершина  ГСА должна быть отмечена только  одним индивидуальным символом  а_i.

В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА  А = { а₁, …а_i ,…а_n }, а также мощность этого множества, которая равна IАI = n.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис 7 – Размеченная ГСА

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

По исходным данным граф - схемы  алгоритма сигналов автомата составим таблицу переходов и выходов, которая будет отражать переходы автомата из состояния a_m в a_s под действием входного сигнала X(a_m,a_s).

 

 

Таблица 4 – Структурная таблица переходов

 

am, Y(am)	K(am)				as	K(as)				X(am,as)	F(am,as)
	Q3	Q2	Q1	Q0		Q3	Q2	Q1	Q0		f3	f2	f1	f0
a1 y1y3y6	0	0	1	0	a2	0	0	1	1	x3	0	0	1	1
					a3	0	1	0	0		0	1	0	0
a2 y5y7	0	0	1	1	a4	1	0	1	0	x2	1	0	1	0
					a5	0	1	0	1		0	1	0	1
a3 y3y5y7	0	1	0	0	a8	0	0	0	1	x1	0	0	0	1
					a9	1	0	0	0		1	0	0	0
a4 y2y3	1	0	1	0	a2	0	0	1	1		0	0	1	1
					a3	0	1	0	0		0	1	0	0
					a7	0	1	1	1		0	1	1	1
a5 y1y4y5y7	0	1	0	1	a6	0	1	1	0	1	0	1	1	0
a6 y1y3y5y6y7	0	1	1	0	a1	0	0	1	0	1	0	0	1	0
a7 y1y3y5y6y7	0	1	1	1	a5	0	1	0	1		0	1	0	1
					a6	0	1	1	0	x2	0	1	1	0
					a7	0	1	1	1	x2x5	0	1	1	1
a8 y2y4	0	0	0	1	a8	0	0	0	1	x3	0	0	0	1
					a10	1	0	0	1		1	0	0	1
a9 y1y2y4y6y7	1	0	0	0	a8	0	0	0	1	x6x1	0	0	0	1
					a9	1	0	0	0	x6	1	0	0	0
					a10	1	0	0	1		1	0	0	1
a10 y1y3y6	1	0	0	1	a1	0	0	1	0	1	0	0	1	0