Автор работы: Пользователь скрыл имя, 08 Июня 2013 в 19:42, практическая работа
Синтезировать автомат для преобразования двоично-десятичного кода с весами 5, 2, 2, 1, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код с весами 6, 4, 2, 1, который снимается с выхода в последовательной форме, начиная со старшего разряда. Провести синтез абстрактного автомата Мили и Мура по первой и второй стратегии. Для каждого автомата привести таблицы переходов и выходов, а также графы работы. По автомату с наименьшим числом внутренних состояний построить структурный автомат. Для структурного автомата провести минимизацию. Провести синтез комбинационной схемы автомата.
Граф автомата Мура, синтезированный по первой стратегии:
Разметка автомата Мура по второй стратегии
0 z0 z0 z0 z0 c
1 w0 2 w0 3 w0 4 w0 5 c 1
1 z0 z0 z0 z1 c
1 w0 2 w0 3 w0 4 w1 6 c 1
2 z0 z0 z1 z0 c
1 w0 2 w0 3 w1 7 w0 8 c 1
3 z0 z0 z1 z1 c
1 w0 2 w0 3 w1 7 w1 9 c 1
4 z0 z1 z1 z0 c
1 w0 2 w1 10 w0 11 w0 5 c 1
5 z0 z1 z1 z1 c
1 w0 2 w1 10 w0 11 w1 6 c 1
6 z1 z0 z0 z1 c
1 w1 2 w0 13 w0 14 w0 6 c 1
7 z1 z1 z0 z0 c
1 w1 12 w0 14 w0 4 w1 5 c 1
8 z1 z0 z1 z1 c
1 w1 12 w0 13 w1 7 w1 9 c 1
9 z1 z1 z1 z0 c
1 w1 12 w0 14 w1 7 w1 8 c 1
a(t) |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
a13 |
a14 |
|
z(t) | ||||||||||||||
z0 |
а2 |
а3 |
а4 |
а5 |
a1 |
а1 |
a8 |
a1 |
a1 |
- |
а5 |
a13 |
a4 |
а4 |
|
w0 |
w0 |
w0 |
w0 |
c |
c |
w0 |
c |
c |
- |
w0 |
w0 |
w0 |
w0 | |
|
z1 |
a12 |
a10 |
a7 |
a6 |
a1 |
a1 |
a9 |
а1 |
а1 |
a11 |
a6 |
а14 |
a7 |
a7 |
|
w1 |
w1 |
w1 |
w1 |
c |
c |
w1 |
c |
c |
w0 |
w1 |
w0 |
w1 |
w1 |
Граф автомата Мура, синтезированный по второй стратегии:
В итоге, для автомата Мили из 14 состояний получили 9 , а для автомата Мура из 24 состояний – 14.
Из полученных автоматов выберем автомат Мили (с переходом в начальное состояние), как имеющий наименьшее число состояний.
3.3. Минимизация автомата
На данном рисунке приведена диаграмма пар совместимости состояний:
2 |
2-3 8-6 |
||||||||||||||
3 |
2-4 8-5 |
3-4 6-5 |
|||||||||||||
4 |
2-1 8-1 |
3-1 6-1 |
4-1 5-1 |
||||||||||||
5 |
2-1 8-1 |
3-1 6-1 |
4-1 5-1 |
\/ |
|||||||||||
6 |
X |
X |
X |
X |
X |
||||||||||
7 |
2-1 8-1 |
3-1 6-1 |
1-4 1-5 |
V |
V |
X |
|||||||||
8 |
2-3 |
6-9 |
3-4 |
1-3 |
1-3 |
X |
1-3 |
||||||||
9 |
2-4 8-5 |
3-4 5-6 |
V |
1-4 1-5 |
1-4 1-5 |
X |
1-4 1-5 |
3-4 |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
2 |
X |
||||||||||||||
3 |
X |
X |
|||||||||||||
4 |
X |
X |
X |
||||||||||||
5 |
X |
X |
X |
\/ |
|||||||||||
6 |
X |
X |
X |
X |
X |
||||||||||
7 |
X |
X |
X |
V |
V |
X |
|||||||||
8 |
X |
X |
X |
X |
X |
X |
X |
||||||||
9 |
X |
X |
V |
X |
X |
X |
X |
X |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Все состояния не совместны по выходам.
4. Структурный синтез автомата
z |
x |
z0 |
0 |
z1 |
1 |
Ставим в соответствие каждой букве входного Алфавита совокупность значений двоичных сигналов.
w |
y |
w0 |
0 |
w1 |
1 |
Кодируем выходные сигналы.
Таблица кодирования состояний.
A |
Q1 |
Q2 |
Q3 |
Q4 |
|
a1 |
0 |
0 |
0 |
0 |
a2 |
0 |
0 |
0 |
1 |
a3 |
0 |
0 |
1 |
0 |
a4 |
0 |
0 |
1 |
1 |
a5 |
0 |
1 |
0 |
0 |
a6 |
0 |
1 |
0 |
1 |
a7 |
0 |
1 |
1 |
0 |
a8 |
0 |
1 |
1 |
1 |
a9 |
1 |
0 |
0 |
0 |
a(t) |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
|
z(t) | |||||||||
z0 |
а2 |
а3 |
а4 |
а1 |
а1 |
- |
а1 |
a3 |
a4 |
|
w0 |
w0 |
w0 |
w0 |
w0 |
- |
w0 |
w0 |
w0 | |
|
z1 |
a7 |
a6 |
a5 |
а1 |
а1 |
a7 |
a1 |
a9 |
a5 |
|
w1 |
w1 |
w1 |
w1 |
w1 |
w0 |
w1 |
w0 |
w1 |
Кодированная таблица переходов-выходов
t |
t+1 |
|||||||||||||
X |
Q1 |
Q2 |
Q3 |
Q4 |
Q1 |
Q2 |
Q3 |
Q4 |
Y |
fQ1 |
fQ2 |
fQ3 |
fQ4 | |
|
a1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
A |
a2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
A |
B |
a3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
A |
a4 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
B |
B |
a5 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
B |
0 |
0 |
a6 |
0 |
0 |
1 |
0 |
1 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
a7 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
B |
B |
0 |
a8 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
B |
1 |
B |
a9 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
B |
0 |
A |
A |
a1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
A |
A |
A |
a2 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
A |
0 |
1 |
a3 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
A |
B |
0 |
a4 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
B |
B |
a5 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
B |
0 |
0 |
a6 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
A |
B |
a7 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
B |
B |
0 |
a8 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
A |
B |
B |
B |
a9 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
B |
A |
0 |
0 |