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

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

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

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

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

Факультет автоматики и электромеханики

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

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

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

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

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

Разработал

А.А. Печенкин

А.В. Маркелов

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

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

Воронеж 2011

ЗАДАНИЕ

на курсовую работу

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

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

Студент группы ВМ09 Печенкин Арсений Анатольевич

Номер варианта 4 - 2.6

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

Сроки выполнения этапов: 1й-этап до _____; 2й-этап до ________

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

Задание принял студент гр. ВМ-091 А.А.Печенкин

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

Подпись, дата

Задание принял студент _______________________________

Подпись, дата

РЕФЕРАТ

Пояснительная записка 26 с., 8 рисунков, 3 источника, 1 приложение.

СИНХРОННЫЙ УПРАВЛЯЮЩИЙ АВТОМАТ, ТЕОРИЯ АВТОМАТОВ.

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

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

Метод исследования и аппаратура - моделирование на ЭВМ.

Полученные результаты - схема электрическая функциональная УА.

Основные конструктивные, технологические и технико-эксплуатационные характеристики персональная ЭВМ с емкостью оперативной памяти не меньше 256Мб, Windows XP.

ВВЕДЕНИЕ

Одной из дисциплин для специальности ”Вычислительные машины, комплексы, системы и сети” является "Теория автоматов", обязательным минимумом содержания которой для дипломированного специалиста является: автоматы и формальные языки; регулярные языки и конечные автоматы; модель дискретного преобразователя В.М. Глушкова; абстрактный синтез; получение не полностью определенного автомата; структурный синтез; состояния элементов памяти; кодирование состояний синхронного и асинхронного автомата; явление риска логических схем; построение комбинационной схемы автомата; микропрограммирование.

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

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

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

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

преобразователь логический матрица кодирование

1 Обобщённая структура и принцип функционирования СУА

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

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

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

Рисунок 1 - Синхронный управляемый автомат на уровне «Черного ящика»

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

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

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

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

Рисунок 2 - Управляющий автомат на первом уровне абстракции

1.1 Функции блока памяти

Блок памяти реализуется из r элементов памяти, которыми для управляющего автомата являются комбинированные синхронные триггеры типов RS, JK, D и T.

Блок памяти на своих выходах d1 … dr формирует двоичный код, который соответствует текущему внутреннему состоянию автомата.

На входы блока памяти поступают сигналы f1…fr, формирующиеся логическим преобразователем. Эти сигналы в совокупности формируют логический код, который соответствует следующему структурному коду внутреннего состояния управляющего автомата.

1.2 Функции логического преобразователя

Задачей логического преобразователя является формирование выходных сигналов управляющих автоматом и функций возбуждения. Эти задачи представляются в виде систем логических функций, аргументы которых являются переменные x1…xn и d1…dr.

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

1.3 Программируемые логические матрицы

Программируемые логические матрицы появились в середине 70-х годов Основой их служит последовательность программируемых матриц элементов И и ИЛИ. В структуру входят также блоки входных и выходных буферных каскадов (БВх и БВых).

Входные буферы, если не выполняют более сложных действий, преобразуют однофазные входные сигналы в парафазные и формируют сигналы необходимой мощности для питания матрицы элементов И.

Выходные буферы обеспечивают необходимую нагрузочную способность выходов, разрешают или запрещают выход ПЛМ на внешние шины с помощью сигнала ОЕ, а иногда выполняют и более сложные действия.

Основными параметрами ПЛМ (Рисунок 3) являются число входов m, число термов l и число выходов n.

Рисунок 3 - ПЛМ

Переменные x1 ... хm подаются через БВх на входы элементов И (конъюнкторов), и в матрице И образуются l термов. Под термом здесь понимается конъюнкция, связывающая входные переменные, представленные в прямой или инверсной форме. Число формируемых термов равно числу коиъюнкторов или, что то же самое, числу выходов матрицы И

Термы подаются далее на входы матрицы ИЛИ, т. е. на входы дизъюнкторов, формирующих выходные функции. Число дизъюнкторов равно числу вырабатываемых функций n.

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

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

Любой автомат может быть реализован в виде автомата на жесткой или гибкой логике. Последовательность синтеза автоматов с жесткой логикой следующая:

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

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

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

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

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

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

2. Анализ граф схемы алгоритма СУА и детализация БП

2.1 Исходные данные и задание на курсовую работу

Требуется синтезировать управляющий автомат типа Мили. Работа автомата задана его ГСА. При проектировании, которого состояния кодируются первым эффективным способом. Блок памяти реализуется с использованием Т-триггеров.

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



Рисунок 4 - ГСА синтезируемого автомата

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

Выходные сигналы, формирующиеся во время работы автомата имеют вид:

2.2 Разметка граф-схемы алгоритма

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

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

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

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

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

Для циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его допустимое состояние, которое выбирают произвольным образом и отмечают символом а1. Все последующие состояния такого (не инициального) автомата отмечаются символами а2 …аi …аn. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата

Разметка ГСА по указанным правилам показана на Рисунке 5.

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

(1)

Так, для данной ГСА мощность равна .



Рисунок 5 - Размеченная ГСА синтезируемого автомата

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

После разметки ГСА выполняется описание СУА с помощью таблиц переходов и выходов. В процессе проектирования используют два типа таблиц - прямые и обратные. Оба типа таблиц содержат одинаковые переменные [5]:

аm - состояние УА, из которого осуществляется переход за один такт автоматного времени;

аs - состояние УА, в которое осуществляется переход за один такт автоматного времени;

X (аm,аs) - логическое условие перехода из аm в аs;

Y (аm,аs) - микрокоманда (подмножество микроопераций), выполняемая на переходе из аm в аs (для автомата типа Мили);

Y (аm) - микрокоманда (подмножество микроопераций), выполняемая автоматом в состоянии аm (для автомата типа Мура).

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

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

В обратных таблицах указываются все допустимые переходы из каких-либо состояний сначала в первое, потом во второе и т.д. до последнего состояния.

Рассмотрению подлежат все пути переходов от отметок аi к аj

Для автоматов допустимыми являются пути вида:

ai X(аi, aj) Yk aj (2)

ai Yk aj (3)

ai X(ai, aj) aj (4)

Каждому пути на ГСА вида (2) ставится переход УА из состояния аi в состояние аj под действием комбинации входных сигналов X(ai,aj) с выдачей выходного сигнала Yk.

Для пути перехода вида (3) считают, что X(ai,aj) = 1, т.е. реализуется безусловный переход. На переходе вида (4) выходной сигнал полагается равным Yo (пустой оператор).

Для заданного автомата по выполненной разметке построена прямая таблица переходов и выходов (Таблица 1).

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

am	as	x	y		am	as	x	y
a1	a2		y3		a6	a6	x6	y1
	a3	x1	y6			a9		y2
a2	a3 a7	x2	y4 y2		a7	a3	x3	y4
a3	a1	x5	-			a8		y3
	a4		y7		a8	a6	x4	y5
a4	a5		y8			a7		-
	a4	x1	y7		a9	a1	1	y1
a5	a6	x2	y1
	a8		-

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

В настоящее время самым распространенным способом структурного кодирования является двоичное кодирование. Структурное кодирование проводится в два этапа: определяется количество () двоичных разрядов, необходимое и достаточное для двоичного представления некоторого множества абстрактных символов; осуществляется сопоставление каждому отдельному абстрактному символу - разрядного двоичного кода.

В самом простейшем случае величина находится на основе следующего соотношения:

(5)

где |А| - мощность множества кодируемых символов абстрактного алфавита; int - целая часть.

Для исходного СУА величина = 4. Это говорит о том, что для структурного кодирования каждого абстрактного символа потребуется четыре разряда.

Для структурного кодирования состояний синхронного автомата используются специальные методы кодирования, наиболее распространенными из которых являются:

- тривиальное кодирование;

- эффективное кодирование (1-й способ);

- эффективное кодирование (2-й способ).

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

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

При эффективном кодировании по первому количество двоичных разрядов, необходимое и достаточное для структурного кодирования состояний автомата, определяется соотношением (5). Затем по таблице переходов, графу автомата или расширенной таблице переходов определяется количество вхождений в каждое из состояний автомата (например, из графы аs в Таблицах 5.1 и 5.2). Состояния автомата, т.е. соответствующие им символы абстрактного алфавита, упорядочиваются в порядке убывания числа вхождений в каждое состояние. То состояние автомата, в которое имеется максимальное число вхождений, кодируется двоичным кодом, содержащем одну единственную единицу в каком - либо двоичном разряде. Последующие состояния автомата кодируются кодами, также содержащими одну единственную единицу, но отличающимися между собой. По мере исчерпания таких кодов для кодирования используются структурные коды, содержащие по две единицы в каких - либо разрядах. Эти коды также должны быть различны между собой. Затем используются структурные коды, содержащие по 3, 4 … единицы, до тех пор, пока все состояния автомата не окажутся закодированными.

Найденный структурный код начального состояния автомата используется для определения соответствующих асинхронных входов R и S, которые должны быть объединены и подключены к сигналу начальной установки. Закодированные по первому эффективному способу абстрактные символы представлены в Таблице 2.

Таблица 2 - Таблица кодирования состояния при использовании первого эффективного метода

	d3	d2	d1	d0	кол-во вхождений
a3	0	0	0	1	3
a6	0	0	1	0	3
a1	0	1	0	0	2
a4	1	0	0	0	2
a7	0	0	1	1	2
a8	0	1	1	0	2
a2	0	1	0	1	1
a5	1	0	1	0	1
a9	1	1	0	0	1

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

Таблица 3 - Таблица кодирования состояния при тривиальном кодировании

	d3	d2	d1	d0
a1	0	0	0	1
a2	0	0	1	0
a3	0	1	0	0
a4	1	0	0	0
a5	0	0	1	1
a6	0	1	1	0
a7	1	1	0	0
a8	1	0	0	1
a9	1	0	1	0

2.5 Детализация блока памяти

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

Для реализации блока памяти заданы комбинированные JK-триггеры, которые можно преобразовать в D - триггеры или в Т - триггеры. Модификация JK - триггеров позволяет не только уменьшить сложность логического преобразователя, но и повысить надежность синтезируемого автомата, так как устраняются запрещенные входные комбинации на информационных входах триггеров. Реализованная схема БП представлена на Рисунке 6.



Рисунок 6 - Детализация блока памяти при использовании первого эффективного метода кодирования



Рисунок 7 - Детализация блока памяти при тривиальном кодировании

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

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

Исходными данными для составления расширенных структурных таблиц переходов и выходов являются данные Таблицы 1 и Таблицы 2.

Расширенные структурные таблицы переходов и выходов отличаются от таблицы 1 введением дополнительных граф, содержащих информацию о структурном коде состояния автомата в текущий момент времени К(аm), о структурном коде автомата в последующий момент времени К(аs), а также структурный код функции возбуждения блока памяти F(аm,аs), который должен формироваться логическим преобразователем для подготовки перехода автомата из состояния аm в состояние аs. В зависимости от используемых триггерных схем функция возбуждения F(аm,аs) определяется различным образом. При использовании Т - триггеров функция возбуждения блока памяти находится на основании следующего уравнения:

. (6)

Из уравнения (6) следует следующая система уравнений:

(7)

Для исходного синхронного управляющего автомата структурная расширенная таблица переходов и выходов представлена Таблицей 3.

Таблица 4 - Расширенная таблица переходов и выходов при использовании первого эффективного метода кодирования:

am	K(am)	as	K(as)	X (am,as)	Y (am, as)	F(am, as)
	d3	d2	d1	d0		d3	d2	d1	d0			f4	f3	f2	f1
a1	0	1	0	0	a2	0	1	0	1		y3, y2, y4, y7	0	0	0	1
					a3	0	0	0	1	x1	y3, y6	0	1	0	1
a2	0	1	0	1	a3	0	0	0	1	x2	y4, y6	0	1	0	0
					a7	0	0	1	1		y2, y7	0	1	1	0
a3	0	0	0	1	a1	0	1	0	0	x5	-	0	1	0	1
					a4	1	0	0	0		y1, y3, y5, y6, y7	1	0	0	1
a4	1	0	0	0	a5	1	0	1	0		y1, y2, y4, y5, y7	0	0	0	0
					a4	1	0	0	0	x1	y1, y3, y5, y6	0	0	0	0
a5	1	0	1	0	a6	0	0	1	0	x2	y1, y2, y5	1	0	0	0
					a8	0	1	1	0		-	1	1	0	0
a6	0	0	1	0	a6	0	0	1	0	x6	y1, y4, y5	0	0	0	0
					a9	1	1	0	0		y2, y7	1	1	1	0
a7	0	0	1	1	a3	0	0	0	1	x3	y4, y6	0	0	1	0
					a8	0	1	1	0		y2, y4, y7	0	1	0	1
a8	0	1	1	0	a6	0	0	1	0	x4	y2, y3, y5, y6, y7	0	1	0	0
					a7	0	0	1	1		-	0	1	0	1
a9	1	1	0	0	a1	0	1	0	0	1	y1, y4, y5	1	0	0	0

Таблица 5 - Расширенная таблица переходов и выходов при тривиальном кодировании

am	K(am)	as	K(as)	x (am,as)	y (am, as)	F(am, as)
	d3	d2	d1	d0		d3	d2	d1	d0			f4	f3	f2	f1
a1	0	0	0	1	a2	0	0	1	0		y3, y2, y4, y7	0	0	1	1
					a3	0	1	0	0	x1	y3, y6	0	1	0	1
a2	0	0	1	0	a3	0	1	0	0	x2	y4, y6	0	1	1	0
					a7	1	1	0	0		y2, y7	1	1	1	0
a3	0	1	0	0	a1	0	0	0	1	x5	-	0	1	0	1
					a4	1	0	0	0		y1, y3, y5, y6, y7	1	1	0	0
a4	1	0	0	0	a5	0	0	1	1		y1, y2, y4, y5, y7	1	0	1	1
					a4	1	0	0	0	x1	y1, y3, y5, y6	0	0	0	0
a5	0	0	1	1	a6	0	1	1	0	x2	y1, y2, y5	0	1	0	1
					a8	1	0	0	1		-	1	0	1	0
a6	0	1	1	0	a6	0	1	1	0	x6	y1, y4, y5	0	0	0	0
					a9	1	0	1	0		y2, y7	1	1	0	0
a7	1	1	0	0	a3	0	1	0	0	x3	y4, y6	1	0	0	0
					a8	1	0	0	1		y2, y4, y7	0	1	0	1
a8	1	0	0	1	a6	0	1	1	0	x4	y2, y3, y5, y6, y7	1	1	1	1
					a7	1	1	0	0		-	0	1	0	1
a9	1	0	1	0	a1	0	0	0	1	1	y1, y4, y5	1	0	1	1

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

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

Составление логических уравнений для функций возбуждения блока памяти F(аm,аs) сводится к составлению совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f1 … fr). Логические уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K(am) и комбинации входных сигналов X (аm,аs) по тем строкам таблиц, в которых в соответствующем столбце fi присутствует значение, равное 1.

При использовании первого эффективного метода кодирования:

;

;

;

;

;

;

;

;

;

;

При тривиальном кодировании:

;

;

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

Целью минимизации одиночных логических функций является сокращение ранга и числа элементарных конъюнкций, входящих в исходную ДНФ логической функции. В результате минимизации по таким критериям могут быть получены кратчайшие и/или минимальные тупиковые дизъюнктивные нормальные формы, обеспечивающие минимальную структурную сложность при реализации логической функции в элементных базисах И, ИЛИ, НЕ; И-НЕ; ИЛИ-НЕ и прочих.

При реализации системы логических функций на программируемой логической матрице наиболее эффективен метод групповой минимизации, который легко реализуется и гарантирует минимизацию площади ПЛМ, занимаемой на кристалле интегральной схемы. Простейший метод групповой минимизации состоит в следующем: в системе логических уравнений для функций возбуждения и функций выходов отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы одинаковых элементарных конъюнкций вводится фиктивная переменная с каким - либо индексом (например, Z1, … Zs). Далее все исходные логические уравнения переписываются в терминах фиктивных переменных.

Группы одинаковых элементарных конъюнкций, полученные в результате проведенной минимизации, приведены в Таблице 4.

Таблица 6 - Таблица фиктивных переменных при использовании первого эффективного метода кодирования:

Таблица 7 - Таблица фиктивных переменных при тривиальном кодировании

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

При использовании первого эффективного метода кодирования:

f1=Z1+Z2+Z3+Z4

f2=Z5+Z6+Z7+Z8

f3=Z9+Z10+Z11+Z12+Z7+Z3+Z13

f4=Z14+Z15+Z16+Z7

y1=Z14+Z18+Z19+Z20+ Z16

y2=Z21+Z5+Z22+Z19+ Z7+Z6+Z3

y3=Z1+Z14+Z23+Z22

y4=Z21+Z24+Z6+Z20+ Z3+ Z16

y5=Z14+Z25+Z22+Z19+ Z20+ Z16

y6=Z9+Z24+Z14+Z25+ Z8+ Z22

y7=Z21+Z5+Z14+Z6+ Z7+ Z3+ Z22

При тривиальном кодировании:

;

;

;

;

;

;

;

;

;

;

3.4 Оценка эффективности методов кодирования

Используем для оценки Эффективности минимизации способ Шеннона.

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

, (8)

где - количество входов у j-ого элемента, i-количество элементов.

При использовании первого эффективного метода кодирования:

Ц=4+6+8*4+16*5+3*4+7+5+4+2*7+3*6=182

При использовании тривиального кодирования:

Ц=4+5*1+7*4+15*5+7*2+8+6+5+2*7+4+3*6=181

Из этого видно что схемы почти равносильны.

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

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

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

На Рисунке 7,а в упрошенном виде (без буферных элементов) показана схемотехника биполярной ПЛМ К556РТ1 с программированием пережиганием перемычек. Показан фрагмент для воспроизведения системы функций

;

;

,

размерностью 4, 7, 3. Параметрами микросхемы К556РТ1 являются 16, 48, 8. Элементами связей в матрице И служат диоды, соединяющие горизонтальные и вертикальные шины, как показано на Рисунке 8,б изображающем цепи выработки терма t1. Совместно с резистором и источником питания цепи выработки термов образуют обычные диодные схемы И. До программирования все перемычки целы, и диоды связи размещены во всех узлах координатной сетки. При любой комбинации аргументов на выходе будет ноль, т.к. на вход схемы подаются одновременно прямые и инверсные значения аргументов, а . При программировании в схеме оставляются только необходимые элементы связи, а ненужные устраняются пережиганием перемычек. В данном случае на вход конъюнктора поданы , и . Высокий уровень выходного напряжения (логическая единица) появится только при наличии высоких напряжении на всех входах, низкое напряжение хотя бы на одном входе фиксирует выходное напряжение на низком уровне, т. к. открывается диод этого входа. Так выполняется операция И, в данном случае вырабатывается терм .

Элементами связи в матрице ИЛИ служат транзисторы (Рисунок 7, в), включенные по схеме эмиттерного повторителя относительно линий термов и образующие схему ИЛИ относительно выхода (горизонтальной линии). На Рисунке 7, в показана выработка функции F1.

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

В схемах на МОП-транзисторах в качестве базовой логической ячейки используют инвертирующие (ИЛИ-НЕ, И-НЕ). Соответственно этому меняются и операции, реализуемые в первой и второй матрицах ПЛМ. В частности, в схемотехнике n-МОП базовой ячейкой обычно служит ячейка ИЛИ-НЕ, а структура ПЛМ имеет вид (Рисунок 7). Такая ПЛМ является последовательностью двух матриц ИЛИ-НЕ, одна из которых служит для выработки термов, другая -- для выработки выходных функций.

Терм t1 в данном случае равен:

а функция:

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

Рисунок 8 - Структура ПЛМ

ЗАКЛЮЧЕНИЕ

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

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

При выполнении данной курсовой работы я,

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

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

- закрепил методы логического синтеза и минимизации комбинационной части проектируемого УА;

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

Способом Шеннона были оценены эффективность методов кодирования. В результате схемы оказались примерны равносильными. Но нужно учитывать, что при синтезировании и минимизации могли быть допущены ошибки и неточности. Исходя из этого делаем вывод, кодирование тривиальным способом вполне может быть таким же эффективным как и кодирование первым эффективным способом.

СПИСОК ЛИТЕРАТУРЫ

1. Тюрин С.В. Практикум по теории автоматов: синтез синхронного управляющего автомата. Учеб. пособие. Воронеж: Воронеж. гос. техн. Ун-т, 2004. 84 с.

2. Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ - Петербург, 2001. - 528 с.

3. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003. - 208 с.

Размещено на Allbest.ur

...