Структурный этап синтеза конечного автомата

. В качестве элементов памяти структурного автомат используется двоичный элемент – триггер, который может находиться в одном из двух устойчивых состояний "1" или "0".

Элементом памяти будем называть автомат Мура, обладающий полной системой переходов и выходов.

Автомат обладает полной системой переходов, если любой пары состояний s_i и s_j можно указать сигнал, вызывающий переход из s_i в s_j.

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

Триггер обычно имеет два выхода: прямой и инверсный.

Состояние триггера определяется значением на его прямом выходе.

Основные типы триггеров.

Существует четыре основных логических типов триггеров:

два одновходовых: D –триггер и T -триггер;

два двухвходовых: RS –триггер и JK-триггер.

D - триггер или триггер - задержка (delay).

На выходе триггера повторяется значение на его входе

Граф автомат Мура, задающий D – триггер (рис. 4.2). Дуги графа помечены значениями входа D.

0/0

1/1

D

Таблица 4.2

Рис. 4.2

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

Рис. 4.3

D

T

q

Рис. 4.4

Другим способом задания работы триггера является матрица переходов (рис. 4.3), где: q(t) – состояние триггера в текущем такте; q(t+1) – в следующем при подаче на вход соответствующего значения D.

На рис. 4.4 приведено условное обозначение D – триггера.

T- триггер или счетный триггер (тoggle - кувыркаться).

При подаче на вход единицы триггер меняет свое состояние на противоположное.

Граф автомат Мура, задающий T – триггер (рис. 4.5). Дуги графа помечены значениями входа T. Таблица переходов - (табл. 4.3).

Таблица 4.3

T

Рис. 4.5

Матрица переходов T – триггера приведена на рис. 4.6, а условное обозначение на рис. 4.7.

Рис. 4.6

T

T

q

q

Рис. 4.7

RS – триггер.

S – вход установки «1» (set), т.е. при подаче «1» на вход S, триггер переходит в состояние «1» (установка 1).

R – вход установки «0» (reset), т.е. при подаче «1» на вход R, триггер переходит в состояние «0» (сброс в 0).

Подача на входы S и R двух единиц одновременно запрещена.

Подача на входы S и R двух нулей одновременно не меняет состояние триггера.

Граф автомат Мура, задающий RS – триггер (рис. 4.8). Дуги графа помечены значениями входов S R. Таблица переходов - (табл. 4.4).

Таблица 4.4

SR

Рис.4.8

Матрица переходов RS – триггера приведена на рис. 4.9, а условное обозначение на рис. 4.10. Символ «*» определяет любое значение.

Рис. 4.9

T

R

S

q

Рис. 4.10

JK триггер.

J – вход установки «1» (jump), т.е. при подаче «1» на вход J, триггер переходит в состояние «1» (установка 1).

K – вход установки «0» (kill), т.е. при подаче «1» на вход K, триггер переходит в состояние «0» (сброс в 0).

Подача на входы J и K двух единиц одновременно меняет состояние триггера на противоположное.

Подача на входы J и K двух нулей одновременно не меняет состояние триггера.

Граф автомат Мура, задающий JK – триггер (рис. 4.11). Дуги графа помечены значениями входов J K. Таблица переходов - (табл. 4.5).

Таблица 4.5

JK 10,11

01,11

Рис. 4.11

Матрица переходов JK – триггера приведена на рис. 4.12, а условное обозначение на рис. 4.13. Символ «*» определяет любое значение.

Рис. 4.12

T

J

K

Рис. 4.13

4.2. Пример структурного синтеза синхронного автомата

Автомат называется синхронным, если его состояния меняются в строго определенные моменты времени, задаваемые с помощью специальных сигналов синхронизации.

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

s0

0 / 0

s1

1 / 0

s2

1 / 0

0 / 1

0 / 0

1 / 0

s0

0 / 0

s1

1 / 0

s2

1 / 0

0 / 1

0 / 0

1 / 0

Рис. 4.14

Таблица 4.6

Требуется построить функционально логическую схему автомата из логических элементов типа «И» (конъюнкторов) и типа «НЕ» (инверторов). В качестве элемента памяти задан RS – триггер.

Логическая схема автомата должна иметь минимальное число логических элементов.

Исходный абстрактный автомат имеет следующие алфавиты:
P = {0,1}, W = {0,1} и их кодирование проводить не надо т.к. они двоичные.

Множество состояний S = {s₀, s₁, s₂}. Для кодирования трех состояний достаточно два разряда. Произвольно закодируем состояния следующим образом (табл. 4.7) и заменим в исходной таблице переходов и выхода (табл. 4.6) абстрактные символы состояний на соответствующие им коды. Полученная кодированная таблица переходов и выходов (табл. 4.8).

Таблица 4.7 Таблица 4.8

Структурная схема для исходного автомата представлена на рис. 4.15.

КС

x

z

y1

y2

y’S1

y’S2

T1

S

R

S

R

T2

1

2

y’R1

y’R2

Рис. 4.15

Из структурной схемы автомата на рис. 4.15 видно, что комбинационная схема реализует систему следующих пяти булевых функций: z – функция выхода, y’_S1, y’_R1 - функции возбуждения триггера T₁, y ^’ _S2, y ^’ _R2 - функции возбуждения триггера T_2, зависящих от трех переменных: х, у₁, у₂. Для определения функции выхода z достаточно кодированной таблицы переходов и выходов (табл. 4.8), а для определения функций возбуждения y’_S1, y’_R1, y ^’ _S2, y ^’ _R2 необходима еще матрица переходов используемого триггера (рис. 4.9).

Для упрощения нахождения этих булевых функций удобно использовать таблицу функций возбуждения и выходов (табл. 4.9), которая строится предварительно на основании кодированной таблицы переходов и выходов (табл. 4.8), и матрицы переходов триггера (в рассматриваемом примере рис. 4.9). Для этого в кодированной таблице переходов и выходов анализируются пары кодов состояний триггеров (до перехода и после перехода) и в соответствующей клетке таблицы функций необходимо вместо кодов состояний записать значения функций возбуждения триггера, которые приведут триггер в требуемое состояние. Значение функции выхода переписывается из кодированной таблицы переходов и выходов. Значения этих функций записываются в клетках таблицы функций следующим образом: y’_S1y’_R1, y ^’ _S2y ^’ _R2 / z.

Например, для реализации перехода автомата из состояния с кодом 01 в состояние с кодом 11 по x = 0 необходимо перевести триггер Т₁ из 0 в 1 и сохранить единичное состояние триггера Т_2. Для этого следуя матрице переходов RS - триггера (рис. 4.9) необходимы следующие значения функций возбуждения y’_S1 = 1, y’_R1 = 0, y ^’ _S2 = *, y ^’ _R2 = 0 и если при этом z = 0, то в верхнюю, левую клетку табл. 4.9 записывается: 10, *0 / 0.

Таблица 4.9 Таблица 4.10

Далее для определения системы булевых функций возбуждения и выходов необходимо построить пять карт Карно для трех переменных и, последовательно просматривая по клеткам полученную таблицу функций возбуждения и выходов (табл. 4.9), одновременно заполняются все пять карт Карно. Например, значения из верхней, левой клетки таблицы функций переписываются в верхнюю, правую клетку соответствующих карт Карно. Карта Карно для функции выхода – табл. 4.10, а карты Карно для функций возбуждения – табл. 4.11, 4.12, 4.13, 4.14.

Таблица 4.1

y’R1

y’S1

1 Таблица 4.1

y’R1

y’S1

2

y2 y1

y2 y1

x

Таблица 4.13 Таблица 4.14

y2 y1

y’R2

y2 y1

x

y’S2

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

z = ₂;

y’_S1 = ₁, y’_R1 = ₂;

y ^’ _S2 = ₂, y ^’ _R2 = y₁ y₂.

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

В результате получается следующая функциональная схема автомата (рис. 4.16). Для проверки правильности ее построения необходимо протестировать его работу на конкретном входном слове. На рис. 4.16 показана работа автомата по переработке входного слова 1 0. Это слово перерабатывается в выходное слово 0 0 1. Указывается также последовательность значений на выходе каждого логического элемента, причем на выходе триггеров указано на одно значение больше. Это значение соответствует коду начального состояния автомата s0 = 01, в которое он предварительно должен быть установлен (рис. 4.16).

R

S

T1

&

&

&

&

&

R

S

T2

0 0 1

y1

1

y2

2

c

&

y’R2

y1

y2

2

2

2

1

x

x

c

y’S1

y’R1

y’S2

z

0 0 1

0 1 0

0 0 1

1 0 0

1 0 0

1 0 0

0 1 1

1 1 0

0 0 1

0 0 1

1 0

Рис. 4.16

Для обеспечения устойчивой работы автомата в его схеме используется сигнал синхронизации – с. При с = 0 значения функций возбуждения непосредственно на входах триггеров равны 0. Это соответствует режиму хранения триггеров и следовательно автомат остается в том же состоянии. При с = 1 вычисленные в комбинационной схеме значения функций возбуждения непосредственно поступают на входы триггеров т.е.: S₁ = y’_S1, R₁ = y’_R1, S₂ = y ^’ _S2, R₂ = y ^’ _R2 и триггеры переключаются и таким образом автомат переходит в новое состояние.

Длительность с = 1 должна быть достаточной, чтобы сработал конъюнктор на входе триггера и переключились сами триггеры.

В момент времени, когда переключаются триггеры, значения функций возбуждения не должны меняться иначе триггер может перейти в незапланированное состояние. В это же время меняются значения на выходе триггеров y_1, y₂. и они по линии обратной связи поступают на входы комбинационной схемы и могут привести к изменению значений функций возбуждения и выходов. Следовательно, длительность сигнала
с = 1 должна быть ограничена так, чтобы новые значения y_1, y₂ не успели поступить на входы триггера в этом же автоматном такте.

Пусть: ∆τ – время задержки в срабатывании одного логического элемента и если время срабатывания триггера 2∆τ, то длительность T₁, когда значение с = 1, находится в интервале: 3∆τ < T₁ ≤ 3,5∆τ

Считывать значение функции выхода z можно лишь тогда, когда y_1, y₂ и x не меняются и z имеет установившееся значение после завершения всех переходных процессов в схеме. Это происходит при с = 1,т.е. функции возбуждения и выходов необходимо считывать по фронту сигнала синхронизации.

Входной сигнал x необходимо менять по спаду сигнала синхронизации, т.е. при с = 0, как только автомат перейдет в новое состояние. Длительность T₀, когда значение с = 0, определяется временем формирования значений функций возбуждения и выходов в комбинационной схеме, определяется числом логических элементов в самой длинной цепочке этой схемы.

Построение временной диаграммы работы схемы автомата.

Временн я диаграмма отображает работу схемы во времени и строится одновременно с ее логическим моделированием.

Построение временн й диаграммыначинается с расчета параметров сигнала синхронизации т.е. определения величин T₁, T₀ и построение сигнала синхронизации на первой оси времени в виде последовательности прямоугольных импульсов, высота которых соответствует логической единице, а ширина – величине T₁. Расстояние между импульсами соответствует величине T₀. Импульсы имеют правильную форму, так как формируются генератором синхросигналов.

В момент времени t₀ автомат должен быть установлен в начальное состояние s₀ = 01, т.е. y₁ = 0, y₂ = 1. Линии, определяющие эти значения, можно продолжить на соответствующих осях до момента времени t₁ так как при с = 0 триггер не может изменить свое состояние

Далее задается входная последовательность по x: 1 0, причем изменение сигнала происходит по спаду сигнала синхронизации в момент времени t₄.

После нанесения на диаграмму входных воздействий вычисляются по комбинационной схеме для x = 1, y₁ = 0, y₂ = 1 значения функций возбуждения и выхода в момент времени t₀. Эти значения:
y’_S1 = 1, y’_R1 = 0, y ^’ _S2 = 0, y ^’ _R2 = 0, z = 0 расставляются на схеме (рис. 4.16).

c

x

y1

1

y2

2

y’R2

y’R1c

y’S1c

y’R2c

y’S2c

z

s0

s1

s2

s0

t0

t1

t2

t3

t4

t5

t6

Рис. 4.17

Линии определенные этими значениями наносим на соответствующие оси временной диаграммы (рис. 4.17) до момента времени t₁. Далее по фронту сигнала синхронизации, в момент t₁ функции возбуждения поступают на входы триггеров и так как y’_S1 = 1, то первый триггер y₁ установится в 1, т.е. автомат из начального состояния с кодом 01 перейдет в новое состояние с кодом 11. На диаграмме стрелками указывается последовательность изменения значений сигналов. Одновременно со считыванием значений функций возбуждений считывается значение функции выхода z = 0.

Эти действия повторяются до момента t₆, когда перестают поступать сигналы синхронизации c = 1 на вход схемы, автомат возвращается в начальное состояние s₀ и прекращает работу по переработке слова.

На временной диаграмме (рис. 4.17) не показаны совпадающие сигналы так как: y’_S1 = ₁, y’_R1 = y ^’ _S2 = ₂.

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