Теория автоматов

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

Из начальной вершины  выходит одно ребро.  В конечную вершину ребра только входят.

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

1. входы и выходы вершин соединяются между собой линиями, направленными от входа к выходу;
2. каждый выход любой вершины соединен точно с одним входом другой вершины;
3. для любой вершины графа существует, по крайней мере, один путь  из этой вершины к конечной вершине;
4. один из выходов условной вершины может соединяться с ее входом (что недопустимо для операторной вершины); в этом случае в цепь обратной связи вводится пустая операторная вершина y_e.

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

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

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

Управляющий микропрограммный автомат может быть реализован  аппаратно на основе существующей элементной базы. В этом случае он называется автоматом с жесткой логикой. Если автомат реализован с помощью программы на ЭВМ, он называется автоматом с программируемой логикой.

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

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

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

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

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

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

Алгоритм отметки ГСА и построение автомата Мура

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

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

1. отметить (пронумеровать) все операторные вершины, поставив в соответствие каждой операторной вершине некоторое состояние a_iÎA;
2. если в ГСА имеются одинаковые операторные вершины (в них записана одна и та же микрокоманда), им сопоставляются разные метки, означающие разные состояния автомата;
3. начальной и конечной вершине присваивается метка a₀.

Далее построение таблицы  переходов-выходов включает следующие  этапы:

• просматриваются все пути перехода между смежными операторными вершинами  a_m в a_s вида a_mx_i1^σi1x_i2^σi2…x_ik^σika_s, где σ_i1,σ_i2,…,σ_ik – значения предикатов x_ij, 1≤j ≤k  , проверяемых при переходе из  вершины a_m в вершину a_s;
• каждому пути из вершины a_m и вершину a_s  сопоставляется конъюнкция ранга k всех условий, проверяемых на этом переходе, при этом переменная x_ij входит в конъюнкцию с отрицанием, т.е. если σ_ij=0 (этому пути соответствует выход из условной вершины x_ij, помеченный  значением 0), и без отрицания – в противном случае.  При этом 0≤k ≤M; если в конъюнкцию X(a_m,a_s) какая-либо переменная входит одновременно с отрицанием и без него, то соответствующий переход при проектировании автомата не рассматривается;
• метка a_m соответствует состоянию автомата в момент времени t, а метка a_s - состоянию автомата в момент времени t+1;
• вводится пустой оператор y_e, если в схеме алгоритма имеются петли из логических  условий;
• строится таблица переходов автомата Мура, в которой перечисляются все пути переходов между отметками в ГСА; каждому состоянию автомата a_m сопоставляется выходной сигнал,  вырабатываемый в данном такте автоматного времени.

В таблице 26 представлен  формат таблицы переходов-выходов автомата Мура для случая, когда в качестве элементов памяти выбраны RS триггеры.

Таблица 30 Формат расширенной таблицы переходов-выходов автомата Мура

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

В таблице 26 отображен  тот факт, что в автомате Мура реализуется отображение выходов λ:A®W

Алгоритм отметки ГСА и построение автомата Мили

Алгоритм отметки ГСА для построения автомата Мили состоит в следующем:

• меткой a₀ отмечается вход вершины, следующей за начальной вершиной, и вход конечной вершины;
• метками a₁, a₂, …, a_M отмечаются входы всех вершин, следующих за операторными вершинами;
• Вход вершины отмечается не более одного раза.

Далее строится таблица переходов-выходов, включающая следующие шаги:

• рассматриваются все пути перехода в ГСА вида:
• a_m X(a_m,a_s)Y(a_m,a_s)a_s – условный переход, которому сопоставляется конъюнкция X(a_m,a_s) входных условий, проверяемых при выполнении перехода из метки a_m в метку a_s;
• a_m X(a_m,a₀)a₀; допускается отсутствие выходного сигнала только при переходе из вершины a_m в вершину a₀; пустой выходной сигнал обозначается Y_e;
• a_mY(a_m,a_s)a_{s –} безусловный переход, которому сопоставляется пустая конъюнкция, равная по определению 1;
• если в конъюнкцию X(a_m,a_s) какая-либо переменная входит одновременно с отрицанием и без него, то соответствующий переход при проектировании автомата не рассматривается;
• составляется таблица переходов-выходов, имеющая следующий формат:

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

В качестве элементов памяти выбран RS-триггер.

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

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

Тривиальная реализация цифрового автомата

При решении даже достаточно простых  задач суммарное число внутренних и внешних переменных автомат  оказывается достаточно большим. Существующие алгоритмические и табличные способы минимизации булевых функций позволяют выполнить минимизацию в полном объеме для построения автомата. Однако затраты времени и ресурсов могут оказаться неприемлемыми. Поэтому в некоторых случаях, когда затраты аппаратных средств не очень критичны, используется тривиальная реализация. При такой реализации автомата минимизация функций возбуждения элементов памяти и выходных функций не производится вовсе. Из выходных сигналов элементов памяти с помощью комбинационной схемы, например, дешифратора, формируются сигналы состояний a_i, которые используются для построения ДНФ указанных функций непосредственно по таблице переходов-выходов. Логические слагаемые в ДНФ представляют собой в этом случае конъюнкции внешних переменных, проверяемых при переходе из метки a_m, и метки a_m. Очевидно, в каждом такте именно метка a_m=1, а остальные метки принимают значение 0.

Кодирование состояний. Гонки в  автомате

Задача кодирования состояний  является одной из основных задач  канонического метода структурного синтеза автоматов.  Переход автомата из состояния a_m в состояние a_s сопровождается переключением некоторых (возможно, всех) элементов памяти. Если при переходе автомата из какого-либо состояния в смежное должно произойти переключение более чем одного элемента памяти, то возникает ситуация, называемая состязаниями элементов памяти. При этом из-за технологической не идентичности  триггеров время переключения  их оказывается различным. Под воздействием внешнего сигнала первым переключится триггер, время задержки которого окажется минимальным. Затем произойдет переключение следующего триггера и т.д. Кроме того, различны времена распространения сигналов возбуждения по цепям различной длины.  Тот элемент, который выигрывает состязания, т.е. изменит свое состояние раньше других элементов, может через цепь обратной связи изменить  сигналы на входах некоторых запоминающих элементов до того, как другие участвующие в состязаниях элементы памяти изменят свое состояние.  Это может привести автомат в состояние, не предусмотренное его графом. Поэтому в процессе перехода автомат может оказаться в некотором промежуточном состоянии  a_k или a_j в зависимости от того, какой элемент памяти выиграет состязания. Если затем при том же входном сигнале автомат перейдет в состояние a_s , то такие состязания называются некритическими. Если же автомат перейдет в состояние, не предусмотренное его ГСА, то такие состязания называются критическими или гонками. Если при неизменном входном сигнале из полученных переходных неустойчивых состояний возможен переход в другие состояния, не соответствующие желаемому переключению, возникает неправильная работа автомата, т.е. сбой. Такая ситуация называется критическими состязаниями элементов памяти. В любом случае гонки - явление нежелательное и их следует избегать. Пример критических и некритических состязаний элементов памяти приведен на Рис.7.