ПТЦА - Прикладная теория цифровых автоматов
Для УА важна последовательность выдачи соответствующих кодов микроопераций в зависимости от логических условий, вырабатываемых ОА и анализируемых УА в нужные моменты времени. Если принят способ кодирования микроопераций, то функции УА задаются кодированной ГСА. Поэтому для различных содержательных ГСА , имеющих одинаковую кодированную ГСА, ОА будут различны, но УА будет одним и тем же.
В дальнейшем будем рассматривать синтез только УА и только кодированной ГСА.
Конечный автомат, интерпретирующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Одну и ту же ГСА можно интерпретировать как автоматом Мили, так и автоматом Мура.
Абстрактный синтез микропрограммного автомата по ГСА осуществляется в два этапа:
1. Получение отмеченной ГСА.
2. Построение графа автомата или таблиц переходов и выходов.
СИНТЕЗ АВТОМАТА МИЛИ
На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a1, a2,.. по следующим правилам:
1) символом а1 отмечают вход вершины, следующей за начальной, а также вход конечной вершины;
2) входы всех вершин следующих за операторными, должны быть отмечены;
3) входы различных вершин, за исключением конечной, отмечаются различными символами;
4) если вход вершины отмечается, то только одним символом.
Ясно, что для проведения отметок потребуется конечное число символов а1,...,am. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.

На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов ai понадобилось при отметке ГСА.
Н
а
плоскости
рисунка отмечаем
все состояния
автомата ai.
Для каждого
из состояний
ai определяем
по отмеченной
ГСА все пути,
ведущие в другие
состояния и
проходящие
обязательно
только через
одну операторную
вершину.
Например, из
состояния
а1(рис.55.) есть
переход в состояние
a2 (путь проходит
через операторную
вершину y1 y2)
и в состояние
a4 (путь проходит
через вершину
y3 y4). Перехода
из a1 в a3 нет,
так как на этом
пути нет ни
одной операторной
вершины. Будем
считать, что
автомат осуществляет
переход, например,
из a1 в a2 при
условии x1 = 0
или x1 (см.ГСА,
рис.55. ) и вырабатывает
на этом переходе
выходные сигналы
у1 у2 (то, что
записано в
проходимой
операторной
вершине ГСА,
рис.55.). Значение
условий х2,
х3, х4 на этом
переходе не
оказывает
влияния на
автомат.
И
сключение
составляет
только путь,
ведущий в конечную
вершину, он
может не содержать
ни одной операторной
вершины (например,
переход из а6
в а1), т.е. не
сопровождается
выработкой
выходных сигналов.
Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата (рис.55. ).

Табл. 27.Прямая таблица переходов- Табл. 28.Обратная таблица перехо-
выходов автомата Мили дов - выходов автомата Мили
|
am |
as |
X | Y |
am |
as |
X | Y | |
|
a |
a2 |
x1 |
y1y2 |
a4 |
a1 |
x2 |
y2 |
|
|
a4 |
x1 |
y3y4 |
a5 |
1 |
y2 |
|||
|
a |
a2 |
x3x2 |
y1y2 |
a6 |
x4 |
- | ||
|
a5 |
x3 |
y2y3 |
a1 |
a2 |
x1 |
y1y2 |
||
|
|
a6 |
x3x2 |
y4 |
a2 |
x3x2 |
y1y2 |
||
|
a3 |
a4 |
1 |
y3y4 |
a6 |
x4 |
y1y2 |
||
|
a4 |
a1 |
x2 |
y2 |
a4 |
a3 |
x2 |
y1y4 |
|
|
a3 |
x2 |
y1y4 |
a1 |
a4 |
x1 |
y3y4 |
||
|
a5 |
a1 |
1 |
y2 |
a3 |
1 |
y3y4 |
||
|
a6 |
a1 |
x4 |
- |
a2 |
a5 |
x3 |
y2y3 |
|
|
a2 |
x4 |
y1y2 |
a2 |
a6 |
x3x2 |
y4 |
В приведенных таблицах am - исходное состояние, aS - состояние перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния am в состояние as, Y - выходной сигнал, вырабатываемый автоматом при переходе из am в aS.
СИНТЕЗ АВТОМАТА МУРА.
Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:
1) символом а1 отмечается начальная и конечная вершины;
2) различные операторные вершины отмечаются различными символами;
3) все операторные вершины должны быть отмечены;
Пример ГСА, отмеченной для автомата Мура, представлен на рис. 56.

Граф автомата Мура, соответствующий отмеченной ГСА (рис. ), представлен на рис. . Построение его аналогично построению графа для автомата Мили.
Табл. 29.Прямая таблица переходов Табл. 30.Обратная таблица переходов
автомата Мура. автомата Мура.
|
am(Y) |
as |
X |
am |
as(Y) |
X | |
|
a |
a2 |
x1 |
a |
a1(-) |
x4 |
|
|
a3 |
x1 |
a |
1 | |||
|
a |
a2 |
x3 x2 |
a1 |
a2(y1y2) |
x1 |
|
|
|
a5 |
x3 |
a |
x3 x2 |
||
|
|
a6 |
x3 x2 |
a |
x4 |
||
|
a3(y3y4) |
a4 |
x2 |
a1 |
a3(y3y4) |
x1 |
|
|
a7 |
x2 |
a4 |
1 | |||
|
a4(y1y4) |
a3 |
1 |
a3 |
a4(y1y4) |
x2 |
|
|
a5(y2y3) |
a7 |
1 |
a2 |
a5(y2y3) |
x3 |
|
|
a6(y4) |
a1 |
x4 |
a2 |
a6(y4) |
x3 x2 |
|
|
a2 |
x4 |
a3 |
a7(y2) |
x2 |
||
|
a7(y2) |
a1 |
1 |
a5 |
1 |
Получением графа или таблиц переходов-выходов заканчивается этап абстрактного синтеза микропрограммного автомата. Как и для конечных автоматов, на этапе абстрактного синтеза можно выполнить минимизацию количества внутренних состояний автомата.
СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ
Структурный синтез микропрограммных автоматов после получения графа или таблицы переходов-выходов в принципе аналогичен каноническому методу синтеза цифровых автоматов, рассмотренному ранее. Однако существуют и определенные особенности в первую очередь связанные с тем, что для реальных автоматов количество элементов памяти и входных сигналов может достигать десяти и более. Функции возбуждения и выходных сигналов трудно поддаются минимизации да и практически минимизация не дает существенного упрощения этих функций при большом количестве переменных. Поэтому минимизация практически не используется при синтезе микропрограммных автоматов.
При выполнении структурного синтеза строят так называемые структурные таблицы переходов и выходов, которые также могут быть как прямыми так и обратными.
Рассмотрим этапы структурного синтеза на конкретных примерах.
СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МИЛИ
Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 27 или табл. 28). В качестве примера синтез будем выполнять по прямой таблице (табл. 27).
1. В исходном автомате количество состояний М=6, следовательно, число элементов памяти
m = ] log 2 M [ = ] log 2 6 [ = 3.
Пусть для синтеза используются JK триггеры.
2. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис.57.) и по возможности метод соседнего кодирования. Рекомендуется самостоятельно закодировать состояние с помощью эвристического алгоритма.

3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл. 31). В данной таблице в столбцах k(am) и k(as) указывается код исходного состояния и состояния перехода соответственно. В столбце функций возбуждения ФВ указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности. Предлагается самостоятельно построить структурную таблицу переходов с указанием всех значений функций возбуждения (в том числе и неопределенных), выполнить минимизацию и сравнить результаты с приведенными ниже.
Табл. 31. Структурная таблица переходов-выходов автомата Мили.
|
Am |
K(am) |
as |
K(as) |
X | Y | ФВ |
|
a |
000 |
a2 |
010 |
x1 |
y1y2 |
J2 |
|
a4 |
001 |
x1 |
y3y4 |
J3 |
||
|
a |
010 |
a2 |
010 |
x3x2 |
y1y2 |
- |
|
|
a5 |
110 |
x3 |
y2y3 |
J1 |
|
|
a6 |
011 |
x3x2 |
y4 |
J3 |
||
|
a3 |
101 |
a4 |
001 | 1 |
y3y4 |
K1 |
|
a |
001 |
a1 |
000 |
x2 |
y2 |
K3 |
|
a3 |
101 |
x2 |
y1y4 |
J1 |
||
|
a5 |
110 |
a1 |
000 | 1 |
y2 |
K1K2 |
|
a6 |
011 |
a1 |
000 |
x4 |
- |
K2K3 |
|
a2 |
010 |
x4 |
y1y2 |
K3 |
4. Для получения функций возбуждения поступаем следующим образом. Выражение для каждой функции получается в виде логической суммы произведений вида aiX, где ai - исходное состояние, X-условие перехода. Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:
J1
= a2x3
+ a4x2
K1
= a3
+ a5
J2
= a1x1
K2
= a5
+ a6x4
![]()
![]()
J3
= a1x1
+ a2x3x2
K3
= a4x2
+ a6x4
+ a6x4
= a6
+ a4x2
5. Для получения функций выходов поступаем аналогично:
![]()
![]()
y1
= a1x1
+ a2x3x2
+ a4x2
+ a6x4
![]()
![]()
![]()
![]()
y2
= a1x1
+ a2x3x2
+ a2x3
+ a4x2
+ a5
+ a6x4
y3
= a2x3
+ a3
+ a1x1
y4 = a1x1 + a2x3x2 + a3 + a4x2
6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить ai его значениями через Q1Q2Q3 либо получить сигнал, соответствующий ai. Обычно используют второй способ и для получения сигнала ai применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q1Q2Q3. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:
A = a2x3x2+J2
; J1
= D + B ; y1
= A + B + E ;
B = a4x2 ; K1 = a3 + a5; y2 = A + D + C + a5 + E ;
![]()
C = a4x2
; J2
= a1x1
; y3
= D + F + a3
;
D = a2x3
; K2
= a5
+ a6x4
; y4
= a3
+ B + J3;
E = a1x1 ; K3 = a6 + C ;
F = a1x1 J3 = F+a2x3x2
Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 58.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МУРА
Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл.29 или табл. 30). В качестве примера синтез будем выполнять по обратной таблице (табл. 32).
1. В исходном автомате количество состояний М=7, следовательно число элементов памяти
m = ] log 2 M [ = ] log 2 7 [ = 3
Пусть для синтеза используется D-триггеры.
2. Кодируем внутренние состояния автомата, используя алгоритм кодирования для D-триггеров. Количество переходов в данное состояние легко определяется из обратной таблицы: a1 ~ 2, a2 ~ 3, a3 ~ 2, a4 ~ 1, a5 ~ 1, a6 ~ 1, a7 ~ 2.
Поэтому коды состояний следующие:
a2-000, a1-001, a3-010, a7-100, a4-011, a5-101, a6-110.
3. Строим структурную таблицу переходов - выходов автомата Мура.
Табл. 32. Структурная таблица переходов - выходов автомата Мура.
|
am |
K(am) |
as(Y) |
K(as) |
X | ФВ |
|
a6 |
110 |
a1(-) |
001 |
x4 |
D3 |
|
a7 |
100 | 1 |
D3 |
||
|
a |
001 |
a2(y1y2) |
000 |
x1 |
- |
|
a |
000 |
x3x2 |
|||
|
a6 |
110 |
x4 |
|||
|
a1 |
001 |
a3(y3y4) |
010 |
x1 |
D2 |
|
a4 |
011 | 1 |
D2 |
||
|
a3 |
010 |
a4(y1y4) |
011 |
x2 |
D2D3 |
|
a2 |
000 |
a5(y2y3) |
101 |
x3 |
D1D3 |
|
a2 |
000 |
a6(y4) |
110 |
x3x2 |
D1D2 |
|
a3 |
010 |
a7(y2) |
100 |
x2 |
D1 |
|
a5 |
101 | 1 |
D1 |
Построение таблицы выполняется аналогично автомату Мили.
4. Выражения для функций возбуждения получаются в виде суммы произведений aiх, где ai-исходное состояние, х - условие перехода.
D![]()
1
= a2x3
+ a2x3x2
+ a3x2
+ a5
D2 = a1x1 + a4 + a3x2 + a2x3x2
D
3
= a6x4
+ a7
+ a3x2
+ a2x3
или
A = a3x2
B = a2x3x2
D![]()
1
= a2x3
+ B + a3x2
+ a5
D2 = a1x1 + a4 + A + B
D
3
= a6x4
+ a7
+ A + a2x3
5. Выражения для выходных сигналов автомата Мура получаем, исходя из того, что эти сигналы определяются только внутренним состоянием автомата.
y1 = a2 + a4
y2 = a2 + a5 + a7
y3 = a3 + a5
y4 = a3 + a4 + a6
6. Для построения функциональной схемы автомата как и в предыдущем случае используем дешифратор состояний. Схема представлена на рис. 61 .
ЗАМЕЧАНИЯ.
1. При синтезе микропрограммных автоматов изложенным методом получаемые выражения для функций возбуждения не всегда являются минимальными и в некоторых случаях могут быть упрощены. В частности, можно доопределить функции возбуждения на некоторых наборах единичным значением (а не нулевым, как было ранее) и выполнить все операции склеивания. Например, в синтезированном ранее автомате Мили таким образом можно получить значение k1=1. Рекомендуется в этом убедиться самостоятельно.
Для упрощения схем автоматов можно также предварительно упростить ГСА, уменьшив количество вершин или узлов методами, изложенными в / /.
Автомат Мили в течении такта сохраняет свое состояние и лишь в конце его переходит в новое. Пока автомат находится в данном состоянии Ai он вырабатывает выходные сигналы y=f(Ai,x), где х - сигналы, подаваемые на вход автомата в течение данного такта. В связи с этим автомат Мили может интерпретировать микропрограмму корректно только в том случае, если для любого перехода выполняется условие независимости логических условий от результатов выполнения микроопераций на данном переходе.
Условие независимости нарушается, если на некотором переходе из аm в аs под действием сигнала х с выработкой уi наблюдается функциональная зависимость х = f(уi). В таком случае выполнение микрооперации уi может привести к изменению значения х и автомат, находясь в состоянии аm, и, реагируя на набор входных сигналов, сформирует набор выходных сигналов, не соответствующий микропрограмме. Чтобы избежать этого, можно использовать следующие способы:
1) запомнить значение сигналов х на промежуток времени, равный длительности такта;
2) ввести в автомат дополнительные состояния;
3) реализовать автомат по схеме Мура.
Запоминание значений сигналов х в течение такта осуществляется операционным автоматом с помощью дополнительных элементов памяти – триггеров. Интерпретация микропрограммы автоматом Мура рассматривалась ранее. Введение дополнительных состояний иллюстрируется рис. 59 .
В исходном автомате (рис. 59.а) есть переходы из аi
