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

Международный институт компьютерных технологий

ПРАКТИКУМ ПО ТЕОРИИ АВТРМАТОВ:

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

Учебное пособие

Воронеж 2004

УДК 519.713 (075)

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

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

Учебное пособие предназначено для студентов технических вузов, обучающихся по специальности 220100 "Вычислительные машины, комплексы, системы и сети".

Табл. 30. Ил. 34. Библиогр.: 14 назв.

Научный редактор д-р техн. наук С.Л. Подвальный

Рецензенты: кафедра автоматизированных систем управления Военного института радиоэлектроники (начальник кафедры канд. техн. наук М.И. Чурсин);

д-р техн. наук Н.И.Баранников

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

Воронежского государственного

технического университета, 2004

ВВЕДЕНИЕ

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

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

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

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

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

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

1 цели и особенности курсового проектирования

1.1 Основные цели курсового проектирования

Задание на курсовое проектирование ориентировано на достижение следующих основных целей:

— получение практических навыков по организации процесса проектирования синхронных управляющих автоматов, содержанию основных этапов проектирования, самостоятельному поиску и анализу соответствующей научно-технической литературы, а также правильному составлению и оформлению текстовой и графической документации в соответствии с Единой Системой Конструкторской Документации (ЕСКД);

— уточнение особенностей модели дискретного преобразователя В.М. Глушкова как совокупности управляющего автомата (УА) и операционного автомата (ОА);

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

— закрепление методов логического синтеза и минимизации комбинационной части (логического преобразователя) проектируемого УА;

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

— осознание способов структурного кодирования синхронных УА и получение практических навыков по их применению;

— более глубокое изучение принципов построения, работы, программирования, минимизации и практического применения двухуровневых программируемых логических матриц при проектировании управляющих автоматов;

—

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

1.2 Специфические особенности объекта проектирования

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

х₁y₁

УА

х_ny_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

Рис.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. Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализовываться логическим преобразователем (ЛП).

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

1.3 Целесообразная последовательность решения задач курсового проектирования

Целесообразной является следующая последовательность решения задач курсового проектирования:

- анализ исходных данных для проектирования;

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

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

- составление структуры и содержания расчетно-пояснительной записки (РПЗ), предъявляемой по окончании курсового проектирования и содержащей задание на курсовое проектирование, текстовые и графические пояснения к курсовому проекту, расчеты и т.п.;

- реализация отдельных этапов курсового проектирования;

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

- изучение требований ЕСКД к структуре и правилам оформления РПЗ;

- изучение требований ЕСКД к правилам оформления и начертания схем электрических функциональных;

- оформление расчетно-пояснительной записки и схемы электрической функциональной синтезированного управляющего автомата в соответствии с требованиями ЕСКД;

- самостоятельная подготовка к защите курсового проекта;

- защита курсового проекта.

2 ЗАДАНИЯ ДЛЯ КУРСОВОГО ПРОЕКТИРОВАНИЯ

Для курсового проектирования задание может быть типовым или специальным. Специальные задания могут выдаваться наиболее подготовленным в данной предметной области студентам. Тематика специальных заданий должна иметь либо практическую, либо, научно-исследовательскую направленность. В зависимости от сложности специальной темы курсового проектирования, а также от уровня начальной подготовки студентов, возможно коллективное (по два и более студента) выполнение курсового проекта. При коллективном проектировании его организация возлагается на самого подготовленного студента в группе проектировщиков, который выбирается группой и распределяет индивидуальные задания по другим участникам группы. К положительным сторонам коллективного учебного курсового проектирования можно отнести [2]:

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

- возможность доброжелательного, свободного и потому творческого обмена мнениями, а также коллективная ответственность за результаты проектирования;

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

Типовое задание на курсовое проектирование (Табл. 2.0) содержит следующие исходные данные:

- тип управляющего автомата;

- тип синхронных триггерных схем;

- способ структурного кодирования внутренних состояний управляющего автомата;

- граф-схему алгоритма (ГСА) функционирования управляющего автомата и состав его микрокоманд.

Для компактного описания вариантов типового задания на курсовое проектирование принят следующий прием: в таблице 2.0 переменные G и H, указывающие исходные данные для курсового проектирования, являются вычисляемыми. Аргументами этих вычислений являются цифровые данные, взятые из номера студенческой зачетной книжки. Для вычисления переменных G и H используются две последние цифры номера зачетной книжки, которые обозначим Ц₀ (последняя цифра номера зачетной книжки) и Ц₁ (предпоследняя цифра номера зачетной книжки). Величина G вычисляется на основании следующего соотношения:

G = Ц₀.

Величина H находится как:

H = 1 +(Ц₁ + Ц₀).

Таблица 2.0

Типовое задание для курсового проектирования

ВАРИАНТ (G)	ТИП УА	СПОСОБ КОДИРОВАНИЯ СОСТОЯНИЙ УА	ТИП СИНХРОННЫХ ТРИГГЕРОВ	ГСА
МИЛИ	МУРА	ТРИВ.	ЭФФ. 1	ЭФФ. 2	RS	D	T	JK
	+			+					+	Рис. 2.Н Табл.2.Н
	+		+			+
	+		+						+
	+			+			+
	+			+				+
		+		+			+
		+			+			+
		+	+						+
		+			+		+
		+			+	+

Примечание: В таблице 2.0 новые обозначения означают

ТРИВ. - тривиальный способ структурного кодирования;

ЭФФ.1 - первый эффективный способ структурного кодирования;

ЭФФ.2 - второй эффективный способ структурного кодирования.

Рассмотрим (в качестве примера) определение номера варианта типового задания, состоящего из G-2.H, для конкретного случая. Пусть номер студенческой зачетной книжки есть № 123463. Тогда:

G = Ц₀ = 3;

H = 1 +(Ц₁ + Ц₀) = 1 + (6 + 3) = 10.

Следовательно, вариант задания G = 3, а соответствующая ГСА проектируемого УА и состав его микрокоманд представлены на рисунке 2.Н и в таблице 2.Н, т.е. на рисунке 2.10 и в таблице 2.10.

Рис. 2.2

Рис. 2.1

Рис. 2.4

Рис. 2.3

Рис. 2.6

Рис. 2.5

Рис. 2.8

Рис. 2.7

Рис. 2.10

Рис. 2.9

Рис. 2.12

Рис. 2.11

Рис. 2.14

Рис. 2.13

Рис. 2.16

Рис. 2.15

Рис. 2.18

Рис. 2.17

Таблица 2.1

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.2

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Рис. 2.19

Таблица 2.3

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.4

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.5

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.6

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.7

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.8

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.9

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.10

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.11

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.12

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.13

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.14

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.15

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.16

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.17

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.18

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

Таблица 2.19

Y_i	микрооперации
y₁	y₂	y₃	y₄	y₅	y₆	y₇
Y₁
Y₂
Y₃
Y₄
Y₅
Y₆
Y₇
Y₈
Y₉
Y₁₀

По приведенным на рисунках 2.1 … 2.19 ГСА определяется мощность множества Х входных сигналов синтезируемого УА. По таблицам 2.1 … 2.19 определяются микрооперации y_j, выполняемые одновременно при реализации УА каждой из микрокоманд Y_i. Полагается, что если микрооперация y_j = 1, то она выполняется в данной микрокоманде, а если y_j = 0, то не выполняется. Содержимое таблиц 2.1 … 2.19 может быть представлено более компактно. Например, для таблицы 2.19 ее содержимое можно представить следующим образом:

Y₁ = {y₁, y₅, y₆};

Y₂ = {y₂, y₇};

Y₃ = {y₂, y₅, y₇};

Y₄ = {y₃, y₅};

Y₅ = {y₁, y₂, y₄, y₇};

Y₆ = {y₃, y₄};

Y₇ = {y₁, y₃, y₄, y₆, y₇};

Y₈ = {y₁, y₂, y₅, y₆, y₇};

Y₉ = {y₄, y₇};

Y₁₀ = {y₂, y₃}.

Общее количество микрокоманд, представленных в таблицах, может превосходить число микрокоманд, представленных на ГСА.

3 СОСТАВ И ОБЪЕМ КУРСОВОГО ПРОЕКТА

Курсовой проект должен включать расчетно – пояснительную записку (РПЗ) и схему электрическую функциональную (СЭФ) синтезированного синхронного управляющего автомата.

В расчетно – пояснительной записке, объемом 15…20 страниц формата А4, приводятся поясняющие текстовые, графические, расчетные, иллюстративные и т.п. материалы, размещенные по разделам проекта. Представляемая схема электрическая функциональная оформляется как приложение к РПЗ.

Расчетно – пояснительная записка содержит:

- титульный лист (ПРИЛОЖЕНИЯ А, Б);

- задание на курсовое проектирование (ПРИЛОЖЕНИЯ В, Г);

- отдельный лист "ЗАМЕЧАНИЯ РУКОВОДИТЕЛЯ";

- СОДЕРЖАНИЕ;

- ВВЕДЕНИЕ;

- основной текст РПЗ;

- ЗАКЛЮЧЕНИЕ;

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

- ПРИЛОЖЕНИЯ.

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

Основной текст РПЗ может иметь следующую структуру:

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

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

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: