7 Структурный синтез C-автомата

1. Совмещённая модель автомата (C-автомата )

S , , X , U , , 1 , 2 , X 0
ЛП
ЭП
U

2. Совмещённая модель автомата (C-автомат )

Таблица переходов:
X1
X2
Таблица выходов:
X3
U1
U1
U3
U2
X1
X2
X3
X4
1
1
2
1
2
2
2
2
1
2
X4
1
X2
X3
X1
X2
2
X4
X2
X1
X3
u1
u3

3. Структурный синтез С-автомата

1. Цель структурного синтеза – построение схемы
реализующего автомата из логических элементов
заданного типа.
2. В структурном автомате необходимо учитывать структуру
входных и выходных сигналов, а также внутреннее
устройство автомата на уровне структурной или
функциональной (логической) схемы.
3. Основная задача - нахождение общих приёмов и методов
построения структурных схем автомата на основе
композиции элементарных автоматов, принадлежащих
заранее заданному конечному числу типов.

4. Структурный синтез С-автомата

1. Полный Автомат памяти
bm
B1
B1
B1
B2
B2
B2
B3
B3
B3
qi
Q1
Q2
Q3
Q3
Q1
Q2
Q2
Q3
Q1
bs
B1
B2
B3
B1
B2
B3
B1
B2
B3
2. Функционально полный набор
логических элементов
-
И, ИЛИ, НЕ
-
И-НЕ
-
ИЛИ-НЕ
-
И, НЕ
-
ИЛИ, НЕ
-
XOR, НЕ, 1
-
….

5. Структурный синтез С-автомата ПРИМЕР

Таблица переходов
a1
z1
a2
a2
-
Таблица выходов
u1
u2
u1
a1
a2
a3
z1
w1
-
w2
z2
w4
w3
-
z3
w2
w1
w3
a3
a1
z2
a3
a1
-
z3
a2
a3
a3
Zi – структурный входной сигнал
Wi , Ui – структурные выходные сигналы

6. Структурный синтез С-автомата

Таблица переходов абстрактного элементарного автомата памяти (ЭАП)
b1
b2
q1
b1
b2
q2
b2
b1
Произведем кодирование
входных сигналов для ЭАП
(α - функция возбуждения памяти):
Произведем кодирование
внутренних состояний
(выходных сигналов) ЭАП:
α
τ
q1
0
b1
0
q2
1
b2
1

7. Структурный синтез С-автомата

qi
bj
bj
Используя вышеуказанную кодировку,
заполним таблицу переходов автомата памяти
b1
b2
q1
b1
b2
q2
b2
b1
0
1
0
0
1
1
1
0

8. Структурный синтез С-автомата

Структурная схема автомата
r1
x1 x2
КС2
1
Т1
2
КС1
Т2
2
1
y1 y2

9. Структурный синтез С-автомата

Произвольно закодируем
внутренние состояния и
наборы входных, выходных сигналов
τ1
τ2
а1
0
0
a2
0
a3
1
x1
x2
y1
y2
z1
0
0
1
z2
0
1
z3
1
r
w1
1
0
u1
1
1
w2
0
0
u2
0
0
w3
1
1
w4
0
1

10. Структурный синтез С-автомата

Заменим теперь таблицы переходов и выходов абстрактного автомата
с учетом принятой кодировки.
Таблица переходов
структурного С-автомата
a1
00
z1
00
a2
01
a2
01
--
Таблица выходов
структурного С-автомата
u11
u02
u11
00
a1
01
a2
11
a3
00
z1
101
w
--
002
w
01
z2
014
w
113
w
--
10
z3
002
w
101
w
113
w
a3
11
a1
00
z2
01
a3
11
a1
00
--
z3
10
a2
01
a3
11
a3
11

11.

Структурный синтез С-автомата
(Синтез комбинационных схем – КС2 и часть КС1)
Таблица выходов
структурного С-автомата
r
1
1 2
00
0
1
01
11
x1x2
y1y2
00
01
10
01
-
00
11
-
10
00
10
11
Из отмеченной таблицы выходов структурного С-автомата получаем
y1 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 0 5 6 14
y2 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 1 5 14
r 1 2 1 2

12. Структурный синтез С-автомата (Синтез комбинационных схем – 2-я часть КС1)

Таблица переходов элементарного автомата памяти:
0
1
0
1
τисх
α
τ вых
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
Таблица переходов С-автомата:
00
01
Модифицированная таблица переходов:
(для функции α)
1 2
11
00
x1x2
α1α2
01
11
01
00
01
-
00
01
11
00
-
00
01
10
01
11
11
10
01
-
11
11
01
-
10
00

13.

Схема КС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).
Из отмеченной таблицы выходов структурного С-автомата получаем
y1 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 0 5 6 14
y2 1 2 x1 x2 1 2 x1 x2 1 2 x1 x2 1 5 14
r 1 2 1 2
1
2

14.

r
y1
1
&
&
1
2
Т1
Т2
α2
α1
1
1
6
&
&
x1 x2
1
12
&
0
5
2
&
&
&
y2