- •Теория автоматов (часть I) Конспект лекций
- •Оглавление
- •1. Введение
- •2. Задачи анализа и синтеза
- •3. Абстрактный управляющий автомат
- •4. Синтез абстрактных автоматов
- •5. Синхронный автомат
- •6. Асинхронные автоматы
- •7. Автоматы Мили и Мура
- •8. Способы задания автоматов
- •8.1 Табличный способ задания автоматов
- •8.2. Задание автомата с помощью графа
- •8.3. Матричный способ задания автоматов
- •9. Переход от автомата Мили к автомату Мура и обратно
- •10. Этапы синтеза автоматов
- •11. Минимизация числа внутренних состояний автомата
- •12. Минимизация полностью определённых автоматов.
- •13. Совмещённая модель автомата (c-автомата )
- •14. Структурный синтез автомата
- •14.1. Канонический метод структурного синтеза автомата
- •14.2. Структурный синтез с-автомата
- •15. Кодирование состояний автомата
- •15.1. Метод противогоночного кодирования состояний автомата
- •15.2. Соседнее кодирование состояний автомата
- •15.3. Кодирование состояний автомата для минимизации комбинационной схемы
- •16. Элементарные автоматы памяти
- •17. Синтез автоматов на плм и пзу
- •Рекомендуемая литература
14.2. Структурный синтез с-автомата
Канонический метод структурного синтеза С-автомата предполагает составление структурной схемы автомата, состоящей из трех частей: модуля памяти и двух комбинационных схем.
Модуль памяти С-автомата строится из элементарных полных автоматов Мура. Т.о. после выбора элементов памяти, каждое состояние С-автомата представляется (кодируется) в структурном автомате вектором am=(l1……li).
Если все элементы памяти одинаковы, то их число определяется следующим образом
,
Переход абстрактного автомата из состояния amв состояниеasпод действием входного сигналаzfс выдачей выходного сигнала
cоотвествует в структурном автомате переходу из состояния
После выбора типа элементов памяти и кодирования состояния автоматов, следует этап синтеза комбинационной схемы, реализующий следующие функции:
Каноническое уравнение функции возбуждения ЭП
При построении функции возбуждения ЭП необходимо использовать функцию выходов ЭП, ставящую в соответствие каждой паре состояний элементарного автомата памяти входной сигнал, который переводит автомат памяти из состоянияbmв состояниеbs.
-
bm
qi
bs
B1
Q1
B1
B1
Q2
B2
B1
Q3
B3
B2
Q3
B1
B2
Q1
B2
B2
Q2
B3
B3
Q2
B1
B3
Q3
B2
B3
Q1
B3
ПРИМЕР:
Необходимо синтезировать частичный С-автомат, заданный следующей таблицей переходов и выходов.
|
A1 |
A2 |
A3 |
Z1 |
A2 |
- |
A1 |
Z2 |
A3 |
A1 |
- |
Z3 |
A2 |
A3 |
A3 |
|
U1 |
U2 |
U1 |
|
A1 |
A2 |
A3 |
Z1 |
W1 |
- |
W2 |
Z2 |
W1 |
W3 |
- |
Z3 |
W2 |
W1 |
W3 |
Таблица переходов автомата:
|
a1 |
a2 |
a3 |
z1 |
a2 |
- |
a1 |
z2 |
a3 |
a1 |
- |
z3 |
a2 |
a3 |
a3 |
Таблица выходов автомата:
|
u1 |
u2 |
u3 |
a1 |
a2 |
a3 | |
z1 |
w1 |
- |
w2 |
z2 |
w4 |
w3 |
- |
z3 |
w2 |
w1 |
w3 |
В качестве элементарного автомата памяти будем использовать автомат Мура, заданный следующим образом:
Таблица переходов автомата памяти:
|
b1 |
b2 |
q1 |
b1 |
b2 |
q2 |
b2 |
b1 |
Так как в элементарном автомате памяти (ЭАП) два входных сигнала q1 и q2 и два выходных сигнала b1 и b2, то в структурном автомате памяти будут один входной и один выходной сигналы.
Произведем кодирование входных сигналов ЭАП (α- функция возбуждения памяти):
|
α |
q1 |
0 |
q2 |
1 |
Произведем кодирование выходных сигналов с элементов памяти:
|
τ |
b1 |
0 |
b2 |
1 |
Используя данную кодировку, заполним таблицу переходов автомата памяти:
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Поскольку у абстрактного С-автомата имеется три внутренних состояния a1, a2 и a3, то структурный С-автомат должен иметь два элемента памяти для кодирования.
Поскольку абстрактный С-автомат имеет три входных (z1, z2 и z3) и четыре выходных сигнала типа 1 (w1, w2, w3 и w4), то в структурном автомате необходимо иметь два входных и два выходных канала для сигнала типа 1.
Для реализации двух выходных сигналов типа 2 необходим один выходной канал комбинационной схемы 2.
Таким образом, структурный автомат будет содержать:
Два элемента памяти (П1 и П2);
Два входных канала (x1 и x2);
Два выходных канала типа 1 (y1 и y2);
Выходной канал типа 2 (r1).
Тогда структурная схема автомата, реализующего данные функции имеет следующий вид.
Произвольно закодируем набор входных, выходных сигналов и внутреннего состояния:
|
τ1 |
τ2 |
|
|
x1 |
x2 |
|
|
y1 |
y2 |
|
|
r |
а1 |
0 |
0 |
z1 |
0 |
0 |
w1 |
1 |
0 |
u1 |
1 | |||
a2 |
0 |
1 |
z2 |
0 |
1 |
w2 |
0 |
0 |
u2 |
0 | |||
a3 |
1 |
1 |
z3 |
1 |
0 |
w3 |
1 |
1 |
| ||||
|
|
w4 |
0 |
1 |
Заменим теперь таблицы переходов и выходов абстрактного автомата с учетом принятой кодировки.
Таблица переходов структурного С-автомата:
|
00 |
01 |
11 |
00 |
01 |
- |
00 |
01 |
11 |
00 |
- |
10 |
01 |
11 |
11 |
Таблица выходов:
|
1 |
0 |
1 |
00 |
01 |
11 | |
00 |
10 |
- |
00 |
01 |
01 |
11 |
- |
10 |
00 |
10 |
11 |
Таким образом, после выбора элементов памяти и кодирования состояний автомата синтез структурного автомата сводится к синтезу комбинационных схем КС1 и КС2.
Схема КС1 должна реализовать следующие функции:
y1 = y1(τ1,τ2,x1,x2);
y2 = y2(τ1,τ2,x1,x2);
α1 = α1(τ1,τ2,x1,x2);
α2 = α2(τ1,τ2,x1,x2).
Комбинационная схема КС2 должна реализовать функцию r1=r1(τ1,τ2).
Функции у1и у2можно получить непосредственно из отмеченной таблицы выходов структурного С-автомата:
Функции возбуждения элементарных автоматов памяти П1 и П2 будут соответствовать таблице переходов структурного С-автомата с учетом выбранных ЭП.
Таблица переходов элементарного автомата памяти:
|
0 |
1 |
|
τисх |
α |
Τвых |
0 |
0 |
1 |
0 |
0 |
0 | |
1 |
1 |
0 |
0 |
1 |
1 | |
|
1 |
0 |
1 |
Модифицированная таблица переходов:
|
00 |
01 |
11 |
00 |
01 |
- |
11 |
01 |
11 |
01 |
- |
10 |
01 |
10 |
00 |
Строим функциональную схему структурного автомата (базис и, или, не):
Для минимизации полученных канонических уравнений можно использовать наборы переменных, на которых соответствующие функции не определены. Сформулируем правило учета недоопределенности:
1. Если некоторый код не используется для кодирования внутренних состояний автомата, то на всевозможных наборах, получаемых из этого состояния, при всех значениях входных сигналов все компоненты функции возбуждения элементов памяти и функции выхода не определены;
2. Если некоторый код не используется для кодирования входных сигналов, то на всех наборах, полученных из значений этого кода, все компоненты функции возбуждения элементов памяти и функции выхода типа 1 не определены.
3. Если для некоторой пары <ai,zj> функция переходов не определена, то на всех наборах всевозможных значений <ai,zi> все компоненты функции выходов не определены.