2.3. Оптимальные автоматы

Для многотактных автоматов, также, как и для одно-тактных можно ввести понятие оптимальности.

Определение. Рассмотрим некоторый автомат (Х, Z, Q, F, G), в котором множества Q, Х, Z закодированы в двоичной системе.

Если функции выходов и переходов автомата F : Х Q Z, G : Х Q Q являются минимальными нормаль-ными формами алгебры логики, то автомат будем называть оптимальным в классе нормальных форм.

Если же функции выходов и переходов автомата F: Х Q Z, G : Х Q Q являются абсолютно оптимальные фор-

мулы, получаемые из минимальных нормальных форм после применения дистрибутивных законов, то автомат будем называть абсолютно оптимальным.

Смысл введенных определений в том, что соответст-вующие реальные автоматы будут иметь в своей физичес-кой структуре минимальное число элементарных функцио-нальных элементов, а также соединений между ними.

Построение оптимальных автоматов Мили и Мура производится теми же способами, что и у функциональных схем (однотактных автоматов).

Пример 1. Ввести двоичные коды для множеств Q, Х, Z автономного светофора, заданного в Примере 1 п.1.5, и построить для него:

1) таблицу состояний,

309

2) канонические уравнения и

3) схему оптимального автомата.

Решение. Вход у автомата отсутствует, выходной информа-цией устройства являются световые сигналы красного, зеленого и желтого цветов - К,З,Ж. Внутренних состояний четыре - q_к , q_з, q_жк и q_жз. Поэтому для двоичного коди-рования множеств Q, Х, Z автомата необходимы следующие числа разрядов:

n =]log ₂ N[=]log ₂ 0[ = 0,

m=]log ₂ M[=]log ₂ 3[= 2,

p=]log ₂ P[=]log ₂ 4[= 2.

Введем двоичные коды.

1. Выход (z₁,z₂): К00,З01,Ж10.

2. Внутренние состояния (q₁, q₂,): q_к00 , q_з01, q_жк10, q_жз11. В итоге граф переходов принимает вид, пока-занный на Рис.5.15.

Рис.5.15

Таблицу состояний строим по графу переходов.

q1(ti-1)	q2(ti-1)	z1	z2	q1(ti)	q2(ti)
0	0	0	0	1	0
0	1	0	1	1	1
1	0	1	0	0	1
1	1	1	0	0	0

310

Строим СДНФ для выходов и внутренних состояний:

z₁ = q₁(t_i-1)q₂(t_i-1) q₁(t_i-1) q₂(t_i-1) ;

z₂ =q₁(t_i-1) q₂(t_i-1) ;

q₁(t_i) =q₁(t_i-1)q₂(t_i-1) q₁(t_i-1) q₂(t_i-1) ;

q₂(t_i) = q₁(t_i-1) q₂(t_i-1) q₁(t_i-1)q₂(t_i-1) .

Минимизируя формы, получаем соответствующие МДНФ:

z ₁ = q₁(t_i-1) ;

z₂ =q₁(t_i-1) q₂(t_i-1) ;

q₁(t_i) =q₁(t_i-1) ;

q₂(t_i) =q₁(t_i-1) q₂(t_i-1) q₁(t_i-1)q₂(t_i-1) .

Поскольку полученные выражения нельзя минимизи-ровать путем применения дистрибутивных преобразований, то данные выражения будут одновременно оптимальными и в классе нормальных форм и абсолютно оптимальными. Следовательно, они задают канонические выражения соот-ветствующих автоматов.

Схему оптимального автомата дополнительно упро-щаем за счет объединения слагаемогоq₁(t_i-1)q₂(t_i-1), содер-жащегося в z₂ и q₂(t_i) (Рис. 5.16).

Рис.5.16

311

Обычно функции выходов и переходов, получаемые после перевода множеств Q, Х, Z в двоичной системе, являются частично определенными. Поэтому оптимальное доопределение их необходимо искать по правилам для ЧОФ.

Пример 2.

Заданы канонические уравнения автомата Мили:

z = x q₁(t_i-1)q₂(t_i-1) xq₁(t_i-1)q₂(t_i-1) x q₁(t_i-1)q₂(t_i-1);

q₁(t_i)= (x q₁(t_i-1)  q₂(t_i-1)) & (x  q₁(t_i-1) q₂(t_i-1) ) ;

q₂(t_i)=xq₁(t_i-1) q₂(t_i-1)xq₁(t_i-1) q₂(t_i-1)

x q₁(t_i-1) q₂(t_i-1) x q₁(t_i-1) q₂(t_i-1) ;

q₁(t₀) = 0 ;

q₂(t₀) = 0 .

Требуется:

1. оптимизировать канонические уравнения;

2. построить структурную схему оптимального автомата

3. построить таблицу состояний;

4. построить граф переходов.

Решение: 1. Упростим канонические уравнения, ис-пользуя операцию склеивания, удаление дубликатов и дистрибутивные законы:

z = xq₂(t_i-1)  q₁(t_i-1)q₂(t_i-1) = (x  q₁(t_i-1))q₂(t_i-1);

q₁(t_i) = x  q₁(t_i-1)  q₂(t_i-1) ;

q₂(t_i) = q₂(t_i-1);

q₁(t₀) = 0 ;

q₂(t₀) = 0 .

Как следует из упрощенных канонических уравнений, двоичное состояние q₂ неизменно по времени и, следова-тельно, всегда равно начальному значению 0. Подставляя это значение в уравнения для z и q₁(t_i) , исключаем q₂ из уравнений и получаем итоговый вид канонических урав-нений:

312

z = x  q₁(t_i-1);

q₁(t_i) = x  q₁(t_i-1) ;

q₁(t₀) = 0 .

2. Схема оптимального автомата, соответствующего полу-ченным оптимальным каноническим уравнениям, дана на Рис. 5.17.

Рис.5.17

3. Таблица состояний будет следующей:

x	q1(ti-1)	z	q1(ti)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

4. Граф переходов оптимального автомата в двоичной форме имеет вид:

Рис.5.18

313

Задачи.

1. По заданному графу переходов построить канони-ческую таблицу состояний и оптимальную структур-ную схему автомата.

Рис.5.19