Материал: Ковригин Теория автоматов Лабораторный практикум 2012
Таблица 3.1 Таблица обозначений состояний автомата
Значение |
Обозначение |
|
состояний |
||
|
||
Начальное состояние |
S0 |
|
Принята 1 |
S1 |
|
Принято 10 |
S2 |
|
Принято 101 |
S3 |
|
Принято 1011 |
S4 |
|
Принято 10110 |
S5 |
Пребывая в каждом следующем состоянии, автомат будет переходить дальше, если на вход поступает «правильный» сигнал, и в случае прихода «неправильного» сигнала возвращаться в то состояние, которое соответствует правильным фрагментам уже поступившей двоичной последовательности. Попав в состояние S5, когда принята требуемая последовательность, автомат выдает 1 на выходе Y. Любые следующие входные сигналы должны оставлять автомат в состоянии S5. Возобновление работы автомата возможно только после приведения его в исходное состояние.
Сказанное проиллюстрировано графом переходов автомата (рис. 3.2). Здесь состояния автомата представлены вершинами графа, а переходы между состояниями дугами между соответствующими вершинами. Каждой дуге графа приписано значение входного сигнала, указывающее, что данный переход автомата осуществляется только при появлении этого входного сигнала. В каждой вершине графа задано значение выходного сигнала Y.
Рис. 3.2. Граф переходов автомата
31
Таблица переходов и выходов автомата, соответствующая приведенному графу переходов, приведена в табл. 3.2.
Таблица 3.2 Таблица переходов и выходов автомата
|
Время t |
Время t+1 |
Время t |
|
X |
|
Текущее |
Следующее |
Y |
|
состояние |
состояние |
||
|
|
|
||
0 |
|
S0 |
S0 |
0 |
1 |
|
S0 |
S1 |
0 |
0 |
|
S1 |
S2 |
0 |
1 |
|
S1 |
S1 |
0 |
0 |
|
S2 |
S0 |
0 |
1 |
|
S2 |
S3 |
0 |
0 |
|
S3 |
S2 |
0 |
1 |
|
S3 |
S4 |
0 |
0 |
|
S4 |
S5 |
0 |
1 |
|
S4 |
S1 |
0 |
0 |
|
S5 |
S5 |
1 |
1 |
|
S5 |
S5 |
1 |
Составление кодированной таблицы переходов и выходов
Перед составлением кодированной таблицы переходов необходимо определить, сколько потребуется двоичных переменных для представления состояний автомата. Число различных состояний автомата равно 6 (см. табл. 3.1). Шесть состояний автомата можно представить тремя двоичными переменными. Число способов установить соответствие между шестью состояниями нашего автомата и комбинациями состояний из трех двоичных переменных огромно.
При выборе разумного способа кодирования следует руководствоваться практическими принципами, изложенными в [1]. Простейший способ назначения кодов состояний из возможных двоичных комбинаций заключается в использовании первых целых двоичных чисел в порядке двоичного счета.
Код начального (исходного) состояния выберем таким образом, чтобы автомат можно было легко установить в это состояние при
32
запуске (в типичных схемах это 0). Тогда кодирование состояний автомата будет следующим: S0=000, S1=001, S2=010, S3=011, S4=100, S5=101.
Теперь составление кодированной таблицы переходов и выходов предельно облегчается. Обозначив двоичные разряды кода состояния через Q2, Q1, Q0 и заменив в табл. 3.2 буквенное обозначение состояний автомата на двоичные коды, получим кодированную таблицу переходов и выходов автомата (табл. 3.3).
Кодированная таблица переходов oпpeделяет зависимость состояний запоминающих элементов Q2(t+l), Q1(t+l) и Q0(t+l) в момент времени t+1 от значения входного сигнала X и состояний запоминающих элементов в предыдущий момент времени t. Выходной сигнал Y определен в зависимости от значения внутренних состояний запоминающих элементов в момент времени t.
|
|
|
|
|
|
|
|
|
|
Таблица 3.3 |
|
Кодированная таблица переходов и выходов |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Время t |
|
|
Время t+1 |
|
|
Время t |
|||
X |
Q2 |
Q1 |
Q0 |
Q2 |
|
Q1 |
|
Q0 |
|
Y |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
1 |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
|
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
|
1 |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
|
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
|
1 |
|
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
|
0 |
|
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
|
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
|
1 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
|
1 |
|
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
|
1 |
|
1 |
1 |
1 |
0 |
1 |
1 |
|
0 |
|
1 |
|
1 |
Составление таблицы возбужд ения автомата
Следующий шаг заключается в составлении таблицы возбуждения, т.е. определения закона функционирования комбинационной схемы КС1 (см. рис. 3.1). В этой таблице для каждой комбинации кода состояния и входного воздействия указываются значения сиг-
33
налов, которые необходимо подать на входы триггеров, чтобы заставить автомат перейти в желаемое следующее состояние с соответствующим кодом. Структура и содержание этой таблицы зависят от типа используемых триггеров (D-, JK-, Т-триггеры).
Внашем случае тип триггера задан в условии задачи – это JK-триггер. В библиотеке базовых элементов ПЛИС XC10PC84 синхронный JK-триггер с асинхронной установкой в 0 имеет имя FJKC. Условное графическое обозначения JK-триггера FJKС приведено на рис. 3.3, а таблица переходов дана в табл 3.4.
Вэтом обозначении: С прямой синхронизирующий вход, CLR (Clear) – асинхронный вход установки триггера в 0, J и K – логические входы триггера. В таблице переходов JK-триггера: – произвольное значение, 0/1 – изменение синхросигнала из 0 в 1.
Рис. 3.3. Условное графическое обозначение JK-триггера FJKC
Таблица 3.4 Таблица переходов JK-триггера FJKC
|
|
Входы |
|
Выход |
|
CLR |
J |
|
K |
C |
Q(t+1) |
1 |
|
|
|
|
0 |
|
|
|
|
|
|
0 |
0 |
|
0 |
0/1 |
Q(t) |
|
|
|
|
|
|
0 |
0 |
|
1 |
0/1 |
0 |
|
|
|
|
|
|
0 |
1 |
|
0 |
0/1 |
1 |
|
|
|
|
|
|
0 |
1 |
|
1 |
0/1 |
Q(t) |
|
|
|
|
|
|
34
С помощью кодированной таблицы переходов можно определить для всех трех JK-триггеров способ формирования входных сигналов J2 и K2, J1 и K1, J0 и K0. Для формирования сигналов, поступающих на логические входы триггеров, используются выходные сигналы триггеров и входной сигнал X в момент времени t
(см. рис. 3.1).
При синтезе конечного автомата удобно функции возбуждения триггеров автомата формировать с использованием кодированной таблицы переходов автомата и матрицы переходов триггера.
Число строк матрицы переходов для любого триггера равно четырем, что определяется числом возможных переходов триггера из одного состояния в другое, а количество столбцов числу логических входов триггера. Матрица переходов JK-триггера (она составлена по таблице переходов JK-триггера) выглядит следующим образом:
Q(t) |
|
Q(t+1) |
|
J |
K |
0 |
- |
0 |
|
0 |
а1 |
|
|||||
0 |
- |
1 |
|
1 |
а2 |
1 |
- |
0 |
|
а3 |
1 |
1 |
- |
1 |
|
а4 |
0 |
Слева от матрицы записаны типы переходов, соответствующие значениям сигналов каждой строки матрицы. Элементы каждой строки матрицы представляют собой значения входных сигналов на логических входах триггера, под воздействием которых триггер переходит из состояния Q(t) в состояние Q(t+1). При этом каждый элемент матрицы может быть равен единице, нулю или являться неопределенным коэффициентом ai, если значение сигнала на входе не влияет на данный переход триггера.
В таблице возбуждения триггеров автомата следует указать значение сигнала, который необходимо подать на J- и K-входы каждого триггера при всех возможных комбинациях вход/код состояния.
Чтобы облегчить последующий процесс занесения функции возбуждения на диаграмму Вейча, целесообразно:
а) образовать десятичный номер каждого двоичного набора текущего состояния автомата, считая двоичную запись состояния автомата как двоичное число с естественными весами разрядов;
35