ПТЦА - Прикладная теория цифровых автоматов
Таблицу переходов можно более компактно изобразить в виде (см. табл. 21б) Анализируя табл.21 б,в отмечаем что, например, переход триггера из 0 в 0требует подачи комбинации R=0, S=0 или R=1,S=0, т.е. можно сказать что этот переход будет при R=X (безразличное состояние) , S=0.
Аналогично рассуждая по отношению к другим переходам получим следующую таблицу функций входов.
-
R
S
Q t
Q t+1
R
S
Q t+1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
– 1
0
0
0
б)
1
0
1
0
1
1
0
– 1
1
1
– а)

-
Q t
Q t+1
Rt
S
0
0
X
0
0
1
0
1
1
0
1
0
1
1
0
X
На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS-триггеров. Например, если автомат переходит из состояния ai= 010 в состояние aj=110, то для обеспечения такого перехода функции возбуждения должны быть:
для первого триггера при переходе из 0 в 1 R1 =0, S1 = 1;
для второго триггера при переходе из 1 в 1 R2 =0, S2 = X;
для третьего триггера при переходе из 0 в 0 R3 =X, S3= 0.
Аналогично для любого другого перехода автомата.
В чистом виде синхронный RS - триггер, используемый для синтеза ЦА, промышленностью не выпускается.
JK- триггер – имеет два информационных входа J и K и один выход Q. Вход J – вход установки в 1, вход K – вход установки в 0, т.е. эти входы аналогичны соответствующим входам RS-триггера: J – соответствует S, K – соответствует R. Однако, в отличие от RS-триггера, входная комбинация J = 1, K= 1 не является запрещённой. Условное обозначение и таблица переходов JK-триггера представлены на рис.28. и в табл. 22.
-
J
K
Q t
Q t+1
J
K
Q t+1
0
0
0
0
0
0
Q t
0
0
1
1
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
1
Q t
1
0
0
1
б)
1
0
1
1
1
1
0
1
1
1
1
0
а)

Как следует из таблиц переходов, для комбинаций входных сигналов JK = 0010 триггер ведет себя как RS-триггер, а при комбинации JK = 11 – как T-триггер.
Анализируя таблицу переходов ( табл. 22 а), отмечаем, что переход триггера, например, из 0 в 1 требует подачи входных сигналов J=1, K=0 или J=1, K=1, т.е. J=1, K=Х (безразличное значение). Аналогично рассуждая по отношению к другим переходам, получим следующую таблицу функций входов JK-триггера.
-
Q t
Q t+1
J
K
0
0
X
0
0
1
1
X
1
0
X
1
1
1
0
X
Таблица функций выходов JK-триггера.
На основании последней таблицы можно получить функцию возбуждения элементов памяти при синтезе автомата на JK-триггерах. Например, при переходе автомата из состояния ai=010 в состояние aj=110, функции возбуждения должны быть:
для первого триггера при переходе из 0 в 1 J1 = 1, K1 = X;
для второго триггера при переходе из 1 в 1 J2 = X, K2 = 0;
для третьего триггера при переходе из 0 в 0 J3 = 0, K3 = X.
Пример канонического метода структурного синтеза автомата.
Выполним структурный синтез частичного автомата А, заданного своими таблицами переходов и выходов (табл. 23 и 24.).

1. Выберем в качестве элементов памяти D-триггер, функция входов которого представлена в таблице стр. 33.
2. Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналов L= ]log2F [ = ]log23[ = 2, т.е. х1, х2.
Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log2G[ = ]log24[ = 2, т.е. у1, у2. Количество внутренних состояний абстрактного автомата M = 4, следовательно количество двоичных элементов памяти (триггеров) R = ] log2M [ = ]log24[ = 2.

Кодирование входных, выходных сигналов и внутренних состояний представлена в таблицах:
|
x1 |
x2 |
y1 |
y2 |
Q1 |
Q2 |
|||||||
|
z1 |
0 |
0 |
w1 |
0 |
0 |
a1 |
0 |
0 |
||||
|
z2 |
0 |
1 |
w2 |
0 |
1 |
a2 |
0 |
1 |
||||
|
z3 |
1 |
1 |
w3 |
1 |
1 |
a3 |
1 |
1 |
||||
|
w4 |
1 |
0 |
a4 |
1 |
0 |
|||||||
Кодирование, в общем случае, осуществляется произвольно. Поэтому, например, каждому из сигналов Zi можно поставить в соответствие любую двухразрядную комбинацию х1, х2. Необходимо только, чтобы разные выходные сигналы Zi кодировались разными комбинациями х1, х2. Аналогично для Wi и ai.
Получим кодированные таблицы переходов и выходов структурного автомата. Для этого в таблицах переходов и выходов исходного абстрактного автомата вместо Zi, Wi, ai cтавим соответствующие коды. Получим таблицы:
|
|
a1 |
a2 |
a3 |
a4 |
a1 |
a2 |
a3 |
a4 |
|||||
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
||||||
|
Z1 |
00 |
00 |
10 |
10 |
– |
Z1 |
00 |
01 |
00 |
11 |
– | ||
|
Z2 |
01 |
– |
11 |
00 |
– |
Z2 |
01 |
– |
11 |
00 |
– | ||
|
Z3 |
11 |
01 |
– |
01 |
Q1Q2 |
Z3 |
11 |
00 |
– |
10 |
y1y2 |
В
кодированной
таблице переходов
заданы функции

В кодированной таблице выходов заданны функции:

4. При каноническом методе синтез сводится к получению функций:

и последующем построении комбинационных схем, реализующих данную систему булевых функций.
Функции у1 и у2 могут быть непосредственно получены из таблицы выходов, например, в виде :

Однако выражения для у1 и у2 можно существенно упростить в результате минимизации, например, с помощью карт Карно:
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
1 |
||||
|
00 |
0 |
0 |
1 |
– |
00 |
1 |
0 |
1 |
– | ||
|
01 |
– |
1 |
0 |
– |
01 |
– |
1 |
0 |
– | ||
|
11 |
0 |
– |
1 |
0 |
11 |
0 |
– |
0 |
1 |
||
|
10 |
– | – | – | – |
10 |
– | – | – |
– |

В результате минимизации имеем:

Для получения выражений для D1 и D2 необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код
состояния перехода на основании таблицы входов триггера получаем требуемое значение функции возбуждения, обеспечивающее заданный переход. Однако для D-триггеров, как отмечалось ранее, таблица переходов совпадает с таблицей функции возбуждения. Тогда либо непосредственно из этой таблицы, либо в результате минимизации получаем требуемые значения Di. Обычно используется минимизация с помощью карт Карно:
|
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
|||
|
00 |
0 |
1 |
1 |
– |
00 |
0 |
0 |
0 |
– | ||
|
01 |
– |
1 |
0 |
– |
01 |
– |
1 |
0 |
– | ||
|
11 |
0 |
– |
0 |
1 |
11 |
1 |
– |
1 |
1 |
||
|
10 |
– | – | – | – |
10 |
– | – | – | – |
В результате минимизации получаем:
5. На основании полученных в результате синтеза булевых выражений ((*), (**)) ,строим функциональную схему автомата. Для этого уравнения ((*), (**)) представим в виде:
Функциональная схема автомата представлена на странице 41:
Дополнительно
на функциональной
схеме показан
сигнал
,
устанавливающий
автомат в начальное
состояние (в
данном случае
00).

Особенности синтеза автоматов на базе T, RS, JK триггеров.
Необходимо отметить, что синтез на базе указанных типов триггеров осуществляется аналогично выполненному синтезу на базе D-триггеров. В частности, п. 13 (см. предыдущий параграф) абсолютно аналогичны. Кроме того, как следует из п.4 (см. предыдущий параграф) выходные сигналы не зависят от типа триггеров, поэтому выражение для yi будут одинаковыми для любого типа триггеров. Однако функции возбуждения будут различны для разных типов триггеров и получаются на основании таблицы переходов исходного автомата и функции входов выбранного триггера. Без особых пояснений ниже приведены таблицы функций входов, функций возбуждений и карты Карно для минимизации функций возбуждения при использовании для синтеза автомата предыдущего параграфа T-, RS-, JK-триггеров.
T-триггер.
-
Q t
Q t+1
T t
0
0
0
0
1
1
1
0
1
1
1
0

-
00
01
11
10
00
00
11
01
– 01
– 10
11
– 11
01
– 10
01
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
||||
|
00 |
0 |
1 |
0 |
– |
00 |
0 |
1 |
1 |
– | ||
|
01 |
– |
1 |
1 |
– |
01 |
– |
0 |
1 |
– | ||
|
11 |
0 |
– |
1 |
0 |
11 |
1 |
– |
0 |
1 |
||
|
10 |
– | – | – | – |
10 |
– | – | – |
0 |

RS-триггер.
-
Q t
Q t+1
R
S
0
0
X
0
0
1
0
1
1
0
1
0
1
1
0
X

-
00
01
11
10
R1
S1
R2
S2
R1
S1
R2
S2
R1
S1
R2
S2
R1
S1
R2
S2
00
X
0
X
0
0
1
1
0
0
X
1
0
– – 01
– – 0
1
0
X
1
0
1
0
– – 11
X
0
0
1
– – 1
0
0
X
0
X
0
1
|
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
|||
|
00 |
X |
0 |
0 |
– |
00 |
0 |
1 |
X |
– | ||
|
01 |
– |
0 |
1 |
– |
01 |
– |
1 |
0 |
– | ||
|
11 |
X |
– |
1 |
0 |
11 |
0 |
– |
0 |
X |
||
|
10 |
– | – | – | – |
10 |
– | – | – | – |

|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
||||
|
00 |
X |
1 |
1 |
– |
00 |
0 |
0 |
0 |
– | ||
|
01 |
– |
0 |
1 |
– |
01 |
– |
X |
0 |
– | ||
|
11 |
0 |
– |
0 |
0 |
11 |
1 |
– |
X |
1 |
||
|
10 |
– | – | – | – |
10 |
– | – | – | – |

JK-триггер.
-
Q t
Q t+1
J
K
0
0
0
X
0
1
1
X
1
0
X
1
1
1
X
0
-
00
01
11
10
J1
K1
J2
K2
J1
K1
J2
K2
J1
K1
J2
K2
J1
K1
J2
K2
00
0
X
0
X
1
X
X
1
X
0
X
1
– – 01
– – 1
X
X
0
X
1
X
1
– – 11
0
X
1
X
– – X
1
X
0
X
0
1
X
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
||||
|
00 |
0 |
1 |
X |
– |
00 |
X |
X |
0 |
– | ||
|
|
01 |
– |
1 |
X |
– |
01 |
– |
X |
1 |
– | |
|
11 |
0 |
– |
X |
X |
11 |
X |
– |
1 |
0 |
||
|
10 |
– | – | – | – |
10 |
– | – | – | – |
|
00 |
01 |
11 |
10 |
00 |
01 |
11 |
10 |
||||
|
00 |
0 |
X |
X |
– |
00 |
X |
1 |
1 |
– | ||
|
01 |
– |
X |
X |
– |
01 |
– |
0 |
1 |
– | ||
|
11 |
X |
– |
1 |
0 |
11 |
0 |
– |
0 |
X |
||
|
10 |
– | – | – | – |
10 |
– | – | – | – |


Функциональные схемы автоматов с различными типами триггеров предлагается построить самостоятельно.
Кодирование внутренних состояний ЦА.
Гонки в автомате.
Кодирование
заключается
в сопоставлении
каждому состоянию
автомата набора
(кода) состояний
элементов
памяти. При
этом наборы
для всех состояний
должны иметь
одинаковую
длину, а разным
состояниям
автомата должны
соответствовать
разные наборы.
Если элементы
памяти двоичные,
то их число
.
П
ереход
автомата из
одного состояния
в другое осуществляется
за счет изменения
состояний
элементов
памяти. Если
автомат переходит
из состояния
с кодом 010 в состояние
с кодом 100, то это
означает, что
триггер V1
переходит из
состояния 0 в
состояние 1,
V2 – из 1 в 0, V3
– сохраняет
свое состояние.
П
ри
функционировании
автомата могут
появиться так
называемые
состязания.
Это явление
возникает
вследствие
того, что элементы
памяти имеют
различные, хотя
и достаточно
близкие, времена
срабатывания.
Различны также
задержки сигналов
возбуждения,
поступающих
на входные
каналы элементарных
автоматов по
логическим
цепям неодинаковой
длины.

Если затем при том же входном сигнале Zf автомат из аk и аl перейдет в аs, то такие состязания являются допустимыми или некритическими.
Если же в этом автомате есть переход, например, из аk в аj аs под действием того же сигнала Zf, то автомат может перейти в аj, а не в аs и правильность его работы будет нарушена (рис.37.).

Такие состязания называются критическими состязаниями или гонками и необходимо принимать меры для их устранения.
Устранить гонки можно аппаратными средствами либо используя специальные методы кодирования. Один из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов х1, ..., хl имеется еще канал С от генератора синхроимпульсов, по которому поступает сигнал С = 1 в момент прихода импульса и С = 0 при его отсутствии. В связи с этим входным сигналом на переходе (am, as) будет не Zf, а CZf. Тогда, если длительность импульса tc меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние ak сигнал C = 0, CZf=0, что исключает гонки. Канал С – это фактически синхровход триггера. Недостаток метода – в трудности подбора требуемой длительности импульса, т.к. она зависит от многих факторов, не поддающихся строгому учету.
Другой способ ликвидации гонок заключается во введении двойной памяти. В этом случае каждый элемент памяти дублируется, причем перепись из первого элемента памяти во второй происходит в момент С = 0(рис.38.).

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


Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.
Кодирование состояний и сложность комбинационной схемы автомата.
Анализ канонического метода структурного синтеза автомата показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выходов, в результате чего сложность комбинационной схемы существенно зависит от выбранного кодирования. Среди множества существующих алгоритмов кодирования рассмотрим лишь два наиболее часто встречаемых:
1) алгоритм кодирования для D-триггеров;
2) эвристический алгоритм кодирования.
Алгоритм кодирования для D-триггеров.
Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:
Каждому состоянию автомата аm (m = 1,2,...,M) ставится в соответствие целое число Nm, равное числу переходов в состояние аm (Nm равно числу появлений аm в поле таблицы переходов или числу дуг, входящих в аm при графическом способе задания автомата).
Числа N1, N2, ..., Nm упорядочиваются по убыванию.
Состояние аs с наибольшим Ns кодируется кодом:
,
где R-количество
элементов
памяти.
Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.
Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.
В результате получается такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц в его коде. Т.к. для D-триггеров функции возбуждения однозначно определяются кодом состояния перехода, то очевидно, что выражения для функций возбуждения будут проще. Этот метод особенно эффективен при отсутствии минимизации функций возбуждения, что имеет место в реальных автоматах с большим количеством внутренних состояний и входных переменных.
В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже) при кодировании на базе D-триггеров.
|
a1 |
a2 |
a3 |
a4 |
a5 |
a1 |
a2 |
a3 |
a4 |
a5 |
|||
|
Z1 |
a1 |
a1 |
a5 |
a3 |
a1 |
Z1 |
w1 |
w2 |
w1 |
w1 |
w1 |
|
|
Z2 |
a2 |
a3 |
a2 |
a3 |
a3 |
Z2 |
w1 |
w3 |
w4 |
w2 |
w2 |
|
|
Z3 |
a3 |
a4 |
a2 |
a4 |
a2 |
Z3 |
w2 |
w2 |
w2 |
w1 |
w3 |

a1 ~ N1 = 3 N3 a3 = 000
a2 ~ N2 = 4 N2 a2 = 001
a3 ~ N3 = 5 N1 a1 = 010
a4 ~ N4 = 5 N4 a4 = 100
a5 ~ N5 = 1 N5 a5 = 011
Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал wi, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:
w1 ~ N1 = 6 N1 w1 = 00
w2 ~ N2 = 5 N2 w2 = 01
w3 ~ N3 = 2 N3 w3 = 10
w4 ~ N4 = 2 N4 w4 = 11
Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.
Эвристический алгоритм кодирования.
Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.
Введем некоторые определения.
Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из аi и аj или наоборот.
Обозначим q(i, j) число всевозможных переходов автомата из аi в аj. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).
Введем функцию w(i, j) = р(i, j) d(i, j), где d(i, j) – число компонентов, которыми коды состояний аi в аj отличаются друг от друга (т.е. кодовое расстояние между кодами аi в аj).
Функция w(i ,j) имеет простой физический смысл. Перход автомата из аi в аj (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям аi и аj (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)d(i ,j) =w(i ,j).
Но тогда
функция
показывает,
сколько всего
переключается
триггеров при
прохождении
автомата по
всем возможным
переходам.
Функция w
показывает,
сколько всего
единиц в функции
возбуждения,
т.е. позволяет
оценивать
сложность
комбинационной
схемы автомата.
W можно
рассматривать
как некую целевую
функцию, минимум
которой определит
такое кодирование,
при котором
комбинационная
схема наиболее
простая. Кстати,
миинмальное
кодовое расстояние
между различными
состояниями
равно 1 и если
удается закодировать
все состояния
соседним
кодированием,
то очевидно,
что w будет
минимально
возможным и
равным
,
т.е. суммарному
числу переходов
для автомата.
Из выражения для w следует, что переход из аi в аi, для которого d(i,i)=0, не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).
Рассмотрим применение эвристического алгоритма на конкретном примере автомата, заданного таблицами переходов и выходов (рис.41. ). Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рис.42. На каждом ребре указан его вес.

Эвристический алгоритм состоит из следующих шагов.
1.
Строим матрицу
,
состоящую из
всех пар номеров
(i, j), для которых
р(i, j)
0 (т.е. в автомате
есть переход
из аi в аj
или наоборот)
и i<j. Для каждой
пары в матрице
указываем ее
вес р(i, j), совпадающий
с весом ребра
соединяющего
аi и аj.
-
i
j
p(i,j)
1 2 2 1 3 1 T = 1 5 1 2 3 3 2 4 1 2 5 1 3 4 2 3 5 2
2.
Упорядочим
строки матрицы
,
для чего построим
матрицу
следующим
образом. В первую
строку матрицы
поместим пару
(,)
с наибольшим
весом р(,).
В нашем случае
(,)
= (2,3), р(2,3) = 3. Из всех
пар, имеющих
общий компонент
с парой (,)
выбирается
пара (,)
с наибольшим
весом и заносится
во вторую строку
матрицы
.
Ясно, что {,}{,}0.
Затем из всех
пар, имеющих
общий компонент
хотя бы с одной
из внесенных
уже в матрицу
пар выбирается
пара с наибольшим
весом и заносится
в матрицу
и т.д.. В случае
равенства весов
пар вычисляются
суммы весов
компонентов
пар (весом р()
компонента
называется
число появлений
в матрице
)
и в матрицу
заносится пара
с наибольшей
суммой весов.
В рассматриваемом
автомате на
второе место
вслед за парой
(2,3) претендуют
пары: (1,2) с р(1,2) = 2;
(3,4) с р(3,4) = 2, (3,5) с



