Введение

Тема курсовой работы по дисциплине «Прикладная теория цифровых автоматов» – «Микропрограмные автоматы».

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

1. Основные понятия. Принцип микропрограммного управления

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

1) любая операция, реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий, называемых микрооперациями;

2) для управления порядком следования микроопераций используются логические условия х_i, принимающие в зависимости от результатов выполнения микроопераций значения 1 или 0;

3) процесс выполнения операций в устройстве описывается в форме алгоритма, представленного в терминах микроопераций и логических условий и называемого микропрограммой;

4) микропрограмма используется как форма представления функции устройства, на основе которой определяются его структура и порядок функционирования.

Все сказанное можно рассматривать, как содержательное описание принципа микропрограммного управления.

2. Концепция управляющего и операционного автоматов

При использовании описанного принципа принято делить ДУ на две части: операционный автомат (ОА) и управляющий автомат (УА) (рис. 1).

Рисунок 1. Обобщенная структурная схема микропрограммного дискретного устройства

ОА предназначен для хранения поступающей информации D, выдачи результатов выполнения операций R, выполнения заданного набора микроопераций, выработки значений логических условий Х=(x₀, x₁,…, x_m), которые являются оповещающими сигналами для управляющего автомата. УА генерирует последовательность управляющих сигналов Y=(y₁, y₂,…, y_n) в соответствии с заданной микропрограммой и со значениями логических условий X. Каждый управляющий сигнал инициирует выполнение соответствующей микрооперации в ОА.

В общем случае ДУ предназначается для выполнения ряда микропрограмм, и на УА подается внешний сигнал q, в соответствии с которым начинается выполнение той или иной микропрограммы. Если ДУ является частью системы обработки информации, то оно может также обмениваться специальными сигналами логических условий X_B и управления Y_B с другими блоками системы.

В состав ОА входят главным образом типовые функциональные узлы: регистры, счетчики, сумматоры, дешифраторы, шифраторы, арифметико-логические устройства (АЛУ), схемы сравнения, блоки памяти, схемы пересылки данных и т.п. Число элементов памяти (ЭП), содержащихся в ОА, определяется разрядностью обрабатываемых данных n_Д, которая может быть достаточно большой. Однако трудоемкость и сложность проектирования ОА, как правило, слабо зависят от n_Д в силу широкого использования стандартных узлов. Таким образом, ОА является исполнительной частью устройства; его состав и структура могут быть одинаковыми для реализации многих алгоритмов одного класса.

Элементарный неделимый акт обработки информации в операционном автомате, происходящий в течение одного момента автоматного времени (одного такта работы автомата), называется микрооперацией. Примерами микроопераций могут служить «Сдвиг информации», «+1», «Инверсия переменной» и т.д.

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

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

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

3. 3. Управляющие автоматы с жесткой и программируемой логикой

Объем оборудования УА зависит от сложности реализуемого алгоритма и от структуры этого автомата, которую можно выполнить в трех вариантах.

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

2. УА с хранимой в памяти (гибкой, программной) логикой, при которой сигналы У вырабатываются на основе совокупности управляющих слов, хранимых в памяти автомата. В этом случае составленные микропрограммы используются в явной форме и обычно записываются в постоянные запоминающие устройства (ПЗУ), выполненные на основе полупроводниковых БИС большой емкости, что позволяет обеспечить регулярность структуры УА и его компактность; здесь используется аппаратно-программный подход к реализации устройства.

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

Таким образом, использование принципа микропрограммного управления позволяет упорядочить и упростить процедуру логического проектирования ДУ, обеспечить регулярность их структуры, а также открывает возможность широкого применения современных БИС. Принцип микропрограммирования применяется при создании микропроцессоров и устройств на их основе. Это не только позволяет упорядочить управление, но и дает возможность формировать систему команд микропроцессоров по своему усмотрению, исходя из имеющейся системы микрокоманд.

Рассмотрим порядок проектирования микропрограммного ДУ, который состоит из следующих основных этапов:

Запись алгоритма.

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

Построение ОА.

В общем случае ОА может быть построен по канонической схеме автомата и содержит три основные части: блок элементов памяти для хранения операндов, а также промежуточных и конечных результатов; комбинационную схему, реализующую набор микроопераций; комбинационную схему, вырабатывающую значения логических условий. Как уже отмечалось, при построении ОА целесообразно применять типовые узлы, а также стремиться использовать отдельные узлы для выполнения нескольких микроопераций.

Построение УА.

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

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

4. Граф-схемы алгоритмов

ГСА – это ориентированный связный граф, задающий последовательность выполнения операций данного алгоритма и содержащий ряд операторных и условных вершин, а также одну начальную и одну конечную вершины. Операторной называется вершина, – которой сопоставляется одна или несколько микроопераций и отмечается соответствующими управляющими сигналами У, а условной – вершина, которой сопоставляется некоторое логическое условие X.

Любая вершина ГСА, кроме вершины «Начало», имеет по одному входу. Вершина «Начало» входов не имеет. Вершина «Начало» и любая операторная вершина имеют по одному выходу. Вершина «Конец» выходов не имеет. Любая условная вершина имеет два выхода, помечаемых символами «Да» и «Нет»: Вместо этих символов могут быть использованы цифры «1» и «О» соответственно. Изображение вершин «Начало», «Конец», операторной вершины и условной вершины ГСА представлено на рис. 2.

Рисунок 2-Графы схемы алгоритмов

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

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

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

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

2. Каждый выход соединен только с одним входом.

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

4. Любая вершина ГСА лежит, по крайней мере, на одном пути из вершины «Начало» в вершину «Конец».

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

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

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

5. Содержательные граф-схемы алгоритмов

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

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

Соответствующая содержательная ГСА представлена на рис. 3.

Рисунок 3. Содержательная ГСА функции определения знака числа

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

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

1. Запись словесного алгоритма функционирования операционного автомата (выполняемых операций) с учетом структуры операционного автомата.

2. Построение содержательной ГСА функционирования операционного автомата.

3. Построение отмеченной ГСА с учетом типа автомата.

4. Построение графа переходов автомата или таблицы переходов.

5. Проведение структурного синтеза автомата по его графу переходов известными методами, например, с помощью канонического метода структурного синтеза.

Построение отмеченной ГСА производится по содержательной ГСА. Для автоматов Мили и Мура процедура разметки имеет различия.

1. 6.1 Построение отмеченной ГСА автомата Мили

Если необходимо построить микропрограммный автомат Мили, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:

1) символом состояния a₁ отметить вход вершины, следующей за вершиной «Начало», а также вход вершины «Конец»;

2) входы всех вершин, следующих за операторными, должны быть отмечены символами а с последовательными индексами;

3) если выход вершины отмечается, то только одним символом;

4) входы различных вершин, за исключением вершины «Конец», отмечаются различными символами;

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

1. 6.2 Построение отмеченной ГСА автомата Мура

Если необходимо построить микропрограммный автомат Мура, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:

1) символом a₁ отмечаются вершины «Начало» и «Конец»;

2) различные операторные вершины отмечаются различными символами;