502_KHramova_T._V._Diskretnaja_matematika_proektirovanie_konechnykh_avtomatov_v_primerakh_i_zadachakh_
.pdf
|
x(t) |
0 |
1 |
S |
|
||
|
S0 |
S1 |
S2 |
|
1 |
1 |
|
|
|
||
|
S1 |
S3 |
S4 |
|
0 |
0 |
|
|
|
||
|
S2 |
S5 |
S6 |
|
1 |
1 |
|
|
|
||
|
S3 |
S3 |
S3 |
|
0 |
0 |
|
|
|
||
|
S4 |
S4 |
S4 |
|
0 |
1 |
|
|
|
||
|
S5 |
S5 |
S5 |
|
0 |
0 |
|
|
|
||
|
S6 |
S6 |
S6 |
|
1 |
0 |
|
|
|
В соответствие состояниям поставим последовательности из «0» и «1»:
S |
S1S2S3 |
000, |
S S1S2S3 |
001, |
S |
2 |
S1S2S3 |
010, S |
S1S2S3 |
011, |
|||||||||
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
|
|
2 |
2 |
2 |
3 |
3 |
3 |
3 |
|
|
S |
S1S2S3 |
100, |
S |
S1S2S3 |
101, |
S |
|
S1S2S3 |
110. |
|
|
|
|
||||||
4 |
4 |
4 |
4 |
|
5 |
5 |
5 |
5 |
|
6 |
6 |
6 |
6 |
|
|
|
|
|
|
Составим каноническую таблицу для данного автомата.
Si1(t) |
Si2(t) |
Si3(t) |
x(t) |
y(t) |
Si1(t 1) |
Si2(t 1) |
Si3(t 1) |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
||||
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
||||
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
||||
|
|
|
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
||||
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
||||
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
||||
|
|
|
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
||||
|
|
|
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
||||
|
|
|
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
||||
|
|
|
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
||||
|
|
|
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
||||
|
|
|
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
||||
|
|
|
|
— |
— |
— |
— |
1 |
1 |
1 |
0 |
||||
|
|
|
|
— |
— |
— |
— |
1 |
1 |
1 |
1 |
||||
|
|
|
|
11 |
|
|
|
Составим канонические уравнения. Для y(t) составим и упростим СДНФ:
y(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t).
Для Si1(t 1) используем СКНФ:
Si1(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) &
& Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) & Si1(t) Si2(t) Si3(t) x(t) .
Для Si2(t 1) и Si3(t 1) составим СДНФ:
Si2(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) xt() Si1(t) Si2(t) Si3(t) x(t);
Si3(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) xt() Si1(t) Si2(t) Si3(t) x(t).
Доопределим значения в канонической таблице согласно уравнениям:
Si1(t) |
Si2(t) |
Si3(t) |
x(t) |
y(t) |
Si1(t 1) |
Si2(t 1) |
Si3(t 1) |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
Упростим выражения, используя свойства логических функций и запишем систему канонические уравнений:
|
|
|
1 |
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
1 |
|
2 |
|
3 |
|
1 |
|
3 |
|
|
2 |
|
2 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
(t) x(t) , |
|
|
||||||||||||||||||||||||||||||
y(t) Si (t) Si |
(t) Si (t) Si (t) Si |
(t) Si |
(t) Si (t) Si |
(t) Si |
(t) x(t) Si |
|
|
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Si1(t 1) Si1(t) Si2(t) Si3(t) Si1(t) Si3(t) x(t) Si2(t), |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
2 |
|
|
3 |
|
|
|
3 |
|
|
|
1 |
|
2 |
|
|
|
3 |
|
2 |
|
1 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
Si |
(t 1) Si |
(t) Si |
(t) Si |
(t) x(t) Si (t) x(t) Si |
(t) Si (t) Si (t) x(t) Si |
(t) Si |
(t) |
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(8)
Si3(t) Si1(t) Si3(t)
Автомат можно упростить. Состояния S3 и S5 идентичны по переходам и по выходам, S5 можно исключить из таблицы, заменив на S3:
12
Это вызовет изменение и в канонической таблице:
1 |
S2(t) |
S3(t) |
x(t) |
y(t) |
1 |
(t |
|
1) |
2 |
(t |
|
1) |
3 |
(t |
|
1) |
|
Si |
(t) |
i |
i |
|
|
Si |
|
Si |
|
Si |
|
||||||
|
0 |
0 |
0 |
0 |
1 |
|
0 |
|
|
0 |
|
|
|
1 |
|
||
|
0 |
0 |
0 |
1 |
1 |
|
0 |
|
|
1 |
|
|
|
0 |
|
||
|
0 |
0 |
1 |
0 |
0 |
|
0 |
|
|
1 |
|
|
|
1 |
|
||
|
0 |
0 |
1 |
1 |
0 |
|
1 |
|
|
0 |
|
|
|
0 |
|
||
|
0 |
1 |
0 |
0 |
1 |
|
1 |
|
|
0 |
|
|
|
1 |
|
||
|
0 |
1 |
0 |
1 |
1 |
|
1 |
|
|
1 |
|
|
|
0 |
|
||
|
0 |
1 |
1 |
0 |
0 |
|
0 |
|
|
1 |
|
|
|
1 |
|
||
|
0 |
1 |
1 |
1 |
0 |
|
0 |
|
|
1 |
|
|
|
1 |
|
||
|
1 |
0 |
0 |
0 |
— |
|
— |
|
|
— |
|
|
— |
|
|||
|
1 |
0 |
0 |
1 |
— |
|
— |
|
|
— |
|
|
— |
|
|||
|
1 |
0 |
1 |
0 |
0 |
|
1 |
|
|
0 |
|
|
|
1 |
|
||
|
1 |
0 |
1 |
1 |
0 |
|
1 |
|
|
0 |
|
|
|
1 |
|
||
|
1 |
1 |
0 |
0 |
1 |
|
1 |
|
|
1 |
|
|
|
0 |
|
||
|
1 |
1 |
0 |
1 |
0 |
|
1 |
|
|
1 |
|
|
|
0 |
|
||
|
1 |
1 |
1 |
0 |
— |
|
— |
|
|
— |
|
|
— |
|
|||
|
1 |
1 |
1 |
1 |
— |
|
— |
|
|
— |
|
|
— |
|
|||
Для y(t)составим СДНФ (на одно слагаемое меньше):
y(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t).
Для Si1(t 1) воспользуемся СКНФ (без изменений):
13
Si1(t 1) Si1(t)
Si1(t) Si2(t)
Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) .
Для Si2(t 1) и Si3(t 1) теперь удобнее использовать СКНФ:
Si2(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) ; Si3(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)
Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) ;
y(t) S1(t) S |
3 |
(t) S1(t) S |
2 |
(t) S3(t) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
x(t), |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
i |
|
i |
|
|
i |
i |
(t) |
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
1 |
|
1 |
|
|
2 |
|
|
3 |
|
1 |
|
|
|
|
3 |
|
|
|
|
|
|
2 |
|
|
|
||||||||
Si (t 1) Si |
(t) Si (t) Si |
Si |
(t) Si |
(t) x(t) Si |
(t), |
(9) |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Si1(t) Si3(t) x(t) Si1(t) x(t) Si2(t) Si3(t) , |
|
|||||||||||||||||||||||||||||||
Si2(t 1) |
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(t) , |
|
||
|
3 |
|
1 |
|
|
|
|
2 |
|
3 |
(t) |
|
1 |
|
|
|
|
|
2 |
|
|
3 |
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
Si (t 1) |
Si |
|
(t) x(t) Si |
(t) Si |
|
Si (t) Si (t) Si |
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Доопределим согласно (9) каноническую таблицу: |
|
|||||||||||||||||||||||||||||||||
Si1(t) |
Si2(t) |
|
Si3(t) |
|
x(t) |
|
|
|
y(t) |
|
|
Si1(t 1) |
Si2(t 1) |
Si3(t 1) |
||||||||||||||||||||
|
0 |
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
|
1 |
|
|
|
|
|
|
0 |
|
|
|
0 |
1 |
|||||||
|
0 |
|
0 |
|
|
|
0 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
0 |
|
|
|
1 |
0 |
|||||||
|
0 |
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
1 |
1 |
|||||||
|
0 |
|
0 |
|
|
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
0 |
0 |
|||||||
|
0 |
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
0 |
1 |
|||||||
|
0 |
|
1 |
|
|
|
0 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
1 |
0 |
|||||||
|
0 |
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
1 |
1 |
|||||||
|
0 |
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
1 |
1 |
|||||||
|
1 |
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
1 |
1 |
|||||||
|
1 |
|
0 |
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
1 |
1 |
|||||||
|
1 |
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
0 |
1 |
|||||||
|
1 |
|
0 |
|
|
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
0 |
1 |
|||||||
|
1 |
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
1 |
0 |
|||||||
|
1 |
|
1 |
|
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
1 |
0 |
|||||||
|
1 |
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
1 |
1 |
|||||||
|
1 |
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
1 |
|
|
|
1 |
1 |
|||||||
Пример 4. y(t) x(t) ~ x(t 1), |
|
y(1) 1. |
|
|
|
|
|
|||||||||||||||||||||||||||
Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется символом, введенным на предыдущем такте и символом, вводимым на текущем такте. Следовательно, кроме начального состояния S0 требуются состояния S1 (если x(t 1) 0) и S2 (если x(t 1) 1), определяющие действия устройства после каждого такта.
14
Уточним формулы для вычисления выходного значения в каждом
состоянии: |
S1 : y(t) x(t)~0 x(t),S2 : y(t) x(t) ~1 x(t). |
Построим |
диаграмму Мура (рисунок 4). |
|
|
Рисунок 4.
Следуя диаграмме Мура, составим таблицу переходов-выходов:
|
x(t) |
0 |
1 |
S |
|
||
|
S0 |
S1 |
S2 |
|
1 |
1 |
|
|
|
||
|
S1 |
S1 |
S2 |
|
1 |
0 |
|
|
|
||
|
S2 |
S1 |
S2 |
|
0 |
1 |
|
|
|
В соответствие состояниям поставим последовательности из «0» и «1»:
|
S |
0 |
S1S2 |
00, |
S S1S2 |
01, |
S |
2 |
S1S2 10. |
||||||||
|
|
|
0 |
0 |
|
|
1 |
1 |
1 |
|
|
|
|
2 |
2 |
||
Составим каноническую таблицу: |
|
|
|
|
|
|
|
|
|
||||||||
|
|
Si1(t) |
|
Si2(t) |
|
x(t) |
|
y(t) |
Si1(t 1) |
Si2(t 1) |
|||||||
|
|
|
0 |
|
|
0 |
|
0 |
|
1 |
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
0 |
|
1 |
|
1 |
|
|
1 |
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
0 |
|
1 |
|
|
0 |
|
|
|
1 |
|
|
|
0 |
|
|
0 |
|
1 |
|
0 |
|
|
1 |
|
|
|
0 |
|
|
|
1 |
|
|
1 |
|
0 |
|
0 |
|
|
0 |
|
|
|
1 |
|
|
|
1 |
|
|
1 |
|
1 |
|
1 |
|
|
1 |
|
|
|
0 |
|
|
|
1 |
|
|
1 |
|
0 |
|
— |
|
|
— |
|
|
— |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
— |
|
|
— |
|
|
— |
|
15
Составим канонические уравнения. |
|
|
|
|
|
|
|
|
x(t) . |
|||||||||||||
|
составим СКНФ: y(t) Si1(t) Si2(t) |
|
|
|
|
|
||||||||||||||||
Для y(t) |
|
|
Si1(t) |
Si2(t) |
||||||||||||||||||
x(t) |
||||||||||||||||||||||
Значения S1(t 1) полностью совпадают с x(t) и противоположны S2 |
(t 1): |
|||||||||||||||||||||
|
|
i |
Si1(t 1) x(t), |
Si2(t 1) |
|
|
|
|
|
|
i |
|
||||||||||
|
|
|
|
|
|
. |
|
|
|
|
||||||||||||
|
|
|
|
|
x(t) |
|
|
|
|
|||||||||||||
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
1 |
|
|
2 |
(t) x(t) , |
|
|
|
|
|||||||||||
|
|
|
|
|
||||||||||||||||||
y(t) Si |
(t) Si |
(t) x(t) Si |
(t) Si |
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t 2,3,..., |
y(1) 1. |
(10) |
||||||
Si1(t 1) x(t), |
|
|
|
|
|
|
|
|
|
|||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Si (t 1) x(t), |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Доопределим значения в канонической таблице согласно (10):
|
Si1(t) |
Si2(t) |
x(t) |
y(t) |
Si1(t 1) |
Si2(t 1) |
|
|
0 |
0 |
0 |
1 |
|
0 |
1 |
|
|
|
|
1 |
|
1 |
0 |
|
0 |
0 |
1 |
|
|||
|
|
|
|
1 |
|
0 |
1 |
|
0 |
0 |
0 |
|
|||
|
|
|
|
0 |
|
1 |
0 |
|
0 |
0 |
1 |
|
|||
|
|
|
|
0 |
|
0 |
1 |
|
1 |
1 |
0 |
|
|||
|
|
|
|
1 |
|
1 |
0 |
|
1 |
1 |
1 |
|
|||
|
|
|
|
1 |
|
0 |
1 |
|
1 |
1 |
0 |
|
|||
|
1 |
1 |
1 |
1 |
|
1 |
0 |
Пример 5. y(t) x(t) x(t 1) x(1), |
y(1) 0. |
|
|||||
Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется символом, введенным первом такте, символом, введенным на предыдущем такте и символом, вводимым на текущем такте. Следовательно, кроме начального состояния S0 требуются состояния S1 (если x(1) 0), S2 (если x(1) 1). Эти состояния являются невозвратными, т.е. снова в процессе работы в них попасть невозможно. Из состояния S1 автомат переходит в состояния S3 (если x(1) 0 и x(t 1) 0) или S4 (если x(1) 0 и x(t 1) 1), а из состояния S2 — в состояния S5 (если x(1) 1 и x(t 1) 0) или S6 (если x(1) 1 и x(t 1) 1). В любой момент времени, в зависимости от вводимого символа, автомат может перейти состояния S3 в S4 и наоборот, а из S5 в S6 и наоборот. Уточним формулы для вычисления выходного значения в каждом состоянии:
S3 : y(t) x(t) x(t 1) x(t) x(t) 0 0 x(t),
S4 : y(t) x(t) x(t 1) x(t) x(t) 1 0 x(t),
S5 : y(t) x(t) x(t 1) x(t) x(t) 0 1 1, 16
S6 : y(t) x(t) x(t 1) x(t) x(t) 1 1 1.
Построим диаграмму Мура (рисунок 5).
Рисунок 5.
На диаграмме видно, что независимо от поступающих на втором и далее тактах символов, выходные значения в состояниях S2, S5 и S6 всегда равны 1. Это происходит потому, что после появления на первом такте 1, формула для вычисления выходных значений принимает вид
y(t) x(t) x(t 1) x(1) x(t) x(t 1) 1 1.
И от последующих вводимых в состоянии S2 символов выход не зависит. Следовательно, S5 и S6 можно упразднить и диаграмму упростить (рисунок 6).
17
Рисунок 6.
Следуя диаграмме Мура, составим таблицу переходов-выходов:
Заметим, что состояния S1 и S3 идентичны, поэтому их можно отождествить:
Количество состояний N определяет длину бинарной последовательности, которая вводится в каноническую таблицу и не может быть короче, чем log2N. Для семи или пяти состояний это были бы строки длины 3, причем в
18
случае пяти состояний остается неиспользованными три последовательности. Для четырех состояний достаточно двух позиций:
S |
0 |
S1S2 |
00, |
S S1S2 01, |
S |
2 |
S1S2 |
10, |
S |
4 |
S1S2 |
11. |
|||||||||
|
0 |
0 |
|
1 |
1 |
1 |
|
|
2 |
2 |
|
|
|
4 |
4 |
|
|||||
|
|
|
|
Si1(t) |
Si2(t) |
|
x(t) |
|
y(t) |
|
Si1(t 1) |
|
Si2(t 1) |
|
|
|
|||||
|
|
|
|
0 |
0 |
|
0 |
|
0 |
|
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
0 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
Составим канонические уравнения. Для y(t) составим и упростим СДНФ: y(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t)
Si1(t) Si2(t) Si2(t) x(t) Si2(t) Si1(t) x(t) .
Для Si1(t 1) и Si2(t 1) составим и упростим СКНФ:
Si1(t 1) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t)
Si1(t) x(t) Si1(t) Si2(t) x(t) ,
Si2(t 1) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t)
Si2(t) x(t) Si1(t) Si2(t) x(t) Si2(t) x(t) Si1(t).
Составим систему канонических уравнений:
y(t) Si2(t) Si1(t) x(t) ,
Si1(t 1) Si1(t) x(t) Si1(t) Si2(t) x(t) ,
|
2 |
2 |
|
|
1 |
(t), |
t 2,3,..., |
y(1) 0. |
Si |
(t 1) Si |
(t) x(t) Si |
||||||
|
|
|
|
|
|
|
|
|
19
Пример 6. y(t) x(t) x(t 1) ~ x(t 2), |
y(1) 0, |
y(2) 0. |
Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется символом, введенным два такта назад, символом с предыдущего такта и символом, вводимым на текущем такте. Следовательно, автомат будет иметь четыре состояния, соответствующих всем возможным комбинациям x(t 2) x(t 1), которые определятся после второго такта.
Рисунок 7.
Кроме этого, необходимо начальное состояние и два состояния (невозвратных), в которые автомат переходит на первом такте, пока последовательность x(t 2) x(t 1) сформировать невозможно. В зависимости от вводимого символа, автомат «переключается» между четырьмя состояниями, соответствующими цепочкам x(t 2) x(t 1).
Уточним формулы для вычисления значения в каждом состоянии:
S3 : y(t)
S4 : y(t) S5 : y(t) S6 : y(t)
x(t) x(t 1) ~ x(t 2) x(t) 0 ~ 0 x(t) ~ 0 x(t), x(t) x(t 1) ~ x(t 2) x(t) 1 ~ 0 1~ 0 0, x(t) x(t 1) ~ x(t 2) x(t) 0 ~1 x(t)~1 x(t), x(t) x(t 1) ~ x(t 2) x(t) 1 ~1 1~1 1.
20