Пример 2.27.
Граф бинарной программы, реализующей булеву фор- мулу
(
)
1 2
3 4
f
x
x x x
=
∨
, приведен на рис. 2.33.
Рис. 2.33. Граф бинарной программы
Рассмотренный метод не гарантирует оптимальность получаемых программ в смысле минимума времени или минимума числа команд.
Существуют и другие методы.
Показатели качества бинарных программ характеризуются следую- щими параметрами:
L
б
(
n) – функция Шеннона для числа команд бинар-
x
1
x
2
x
3 4
x
1
x
2
x
3
x
x
4 0
1 1
0 1
135 ных программ, асимптотически равна
2
n
n
, причем существуют методы синтеза, для которых
t
max
n.
Доля функций (для любого ε>0), для которых б
2
( ) (1
)
n
L f
n
≤ −
ε
и ср
( ) (1
)
t
f
n
≤ − ε ⋅ , стремится к нулю с ростом n.
То есть сложность бинарных программ по числу команд асимптотиче- ски равна сложности операторных программ, но в отличие от оператор- ных программ бинарные имеют два преимущества – это отсутствие про- межуточной памяти и более высокое быстродействие, которое можно охарактеризовать соотношением
(log
2
n+1)≤t
max
(
f)≤n.
Если в программе использовать и операторы и условные переходы, то число команд, асимптотически равное для операторных и бинарных про- грамм
2
n
n
, можно понизить вдвое.
2.6 Общие методы синтеза автоматов
Для проведения синтеза автоматов нужно уметь представлять любой автомат в виде некоторой совокупности более простых автоматов. В раз- деле 4.5 было рассмотрено представление автоматов в виде сетей, то есть в виде соединения элементарных автоматов. Как это сделать практически и не обязательно в виде элементарных автоматов, а в общем случае в ви- де произвольных либо стандартных автоматов? Эти задачи решаются различными методами декомпозиции автоматов.
2.6.1. Декомпозиция абстрактных автоматов
Под декомпозицией в общем случае понимается представление слож- ного автомата работой нескольких более простых (в частном случае эле- ментарных) автоматов, которые на структурном уровне с помощью отождествления входных и выходных полюсов образуют функциональ- ную или структурную схему сложного автомата. Обычно ставится задача оптимальной декомпозиции с точки зрения минимального числа элемен- тарных автоматов. В результате оптимальной декомпозиции осуществля-
136 ется минимизация числа логических элементов, входящих в комбинаци- онную часть.
На абстрактном уровне декомпозиция
сложного автомата соответ- ствует параллельной, последовательной или смешанной работе более простых автоматов, т.е. сводится к задаче разложения автомата по опера- ции умножения, суммирования, суперпозиции или по нескольким опера- циям сразу. Поэтому можно рассматривать декомпозицию параллельную, последовательную или смешанную.
Параллельная декомпозиция соответствует разложению автомата в произведение или сумму двух или большего числа абстрактных автома- тов, каждый из которых проще, чем исходный автомат. Здесь можно го- ворить о параллельной одновременной (умножении) или параллельной поочередной (сумме) декомпозиции автоматов. Последовательная деком- позиция соответствует разложению автомата по операции суперпозиции, а смешанная – одновременно по двум операциям (например умножения и суперпозиции).
Все описанные случаи декомпозиции – это “чистые” случаи декомпо- зиции автоматов. Таких автоматов, которые бы раскладывались только в параллельную или в последовательную или даже в смешанную работу автоматов, довольно мало по сравнению с теми, которые не раскладыва- ются таким образом. Поэтому вводится понятие
общей декомпозиции автомата, которая понимается как совместная работа элементарных авто- матов со связями между ними. Общая декомпозиция соответствует раз- ложению абстрактного автомата в композицию двух или более элемен- тарных автоматов, то есть соответствует представлению сложного авто- мата в виде сети из более простых автоматов. Таким образом, последова- тельная, параллельная или смешанная декомпозиция могут рассматри- ваться как частные случаи общей декомпозиции автоматов.
Необходимо заметить, что при разложении автомата по операции композиции ставится, как правило, задача
оптимальной декомпозиции, то есть представление произвольного автомата совместной работой эле- ментарных автоматов с
минимальным числом связей между ними. Реше- ние задачи оптимальной декомпозиции приводит к минимальной комби- национной части автомата.
Следующий уровень этой же задачи связан с реализацией автомата в однородных вычислительных средах и заключается в декомпозиции ав- томата на
заданные автоматы, например, на элементарные автоматы из некоторого элементного базиса.
Свойство автомата быть представленным параллельной или последо- вательной работой более простых автоматов вытекает из анализа вида
137 матриц, получаемых в результате произведения, суммирования или су- перпозиции автоматов.
Нет
необходимости здесь рассматривать все теоремы, касающиеся данного раздела. Из основных результатов можно назвать следующий: любое параллельное соединение автоматов (параллельное одновремен- ное, с общим входом, не одновременное) можно представить в виде по- следовательного соединения (возможно, других автоматов), то есть в ви- де суперпозиции автоматов.
Если же мы хотим выделить стандартные автоматы из исходного ав- томата, то использование алгебраических операций позволяет на аб- страктном уровне решить задачу декомпозиции сложного автомата на заданные стандартные автоматы путем сведения ее к решению суперпо- зиционных уравнений над автоматами.
Что касается общей декомпозиции автоматов, то здесь можно упомя- нуть следующее утверждение: любой автомат Мили с числом состояний
n>2 можно представить совместной работой (композицией) двух или большего числа простых автоматов, один из которых – автомат Мили, а остальные – автоматы Мура.
2.6.2. Канонический метод синтеза Вначале подведем некоторый итог по поводу функциональной полно- ты элементного базиса синтеза автоматов. Автоматно полный базис со- гласно теоремам о представлении автомата соответствующей сетью (тео- рема 2.5.1) и схемной реализации логических функций (теорема 2.5.2) может представлять собой элемент единичной задержки и какую-либо функциональную полную систему логических элементов. Вместо эле- мента задержки в автоматный базис можно включить любой другой эле- мент памяти (например, триггер). В качестве элемента памяти можно взять и любой автомат Мура с произвольным числом внутренних состоя- ний (два, три, пять и т.д.), лишь бы этот автомат удовлетворял требова- ниям полноты системы переходов и полноты системы выходов.
Требование полноты системы переходов предусматривает для любой упорядоченной пары состояний элементарного автомата наличие некото- рого входного сигнала, который переводит первый элемент этой пары во второй.
Требование полноты системы выходов означает, что для каждого со- стояния элементарного автомата имеется соответствующий ему выход- ной сигнал, который отличается от выходного сигнала, соответствующе- го другим состояниям элементарного автомата.
138
Для тех элементов памяти, которые были рассмотрены, эти требова- ния выполняются.
Доказано утверждение о том, что всякая система элементарных авто- матов, которая содержит автомат Мура с нетривиальной памятью и пол- ной системой переходов и выходов и функционально полную систему логических элементов, является автоматно полным базисом.
Но, к сожалению, в общем случае для произвольного набора элемен- тарных автоматов проблема автоматной полноты оказывается
алгорит-мически неразрешимой (в отличие от подобной проблемы для комбина- ционного автомата).
Весь процесс синтеза можно разбить условно на ряд этапов. Класси- ческой считается схема синтеза, называемая
канонической схемой, или
каноническим методом синтеза, на разных этапах которой производятся следующие действия:
1) по описанию автоматного отображения (например, по регулярному событию)
строится абстрактный автомат;
2) минимизируется число состояний автомата;
3) производится двоичное кодирование входного, внутреннего и вы- ходного алфавитов (с учетом соображений раздела 2.5.6);
4) осуществляется выбор типов элементарных автоматов и определе- ние их функций возбуждения в соответствии с кодированными автомат- ными таблицами переходов элементарных автоматов;
5) находятся минимальные формы для функций возбуждения;
6) получают с дальнейшей минимизацией функции выхода элемен- тарных автоматов;
7) составляются канонические уравнения, описывающие комбинаци- онные блоки автомата;
8) производится реализация системы канонических уравнений систе- мой логических элементов в функционально полном базисе с последую- щей минимизацией.
Эта схема сыграла большую роль в развитии методов синтеза, но в практическом применении не очень удобна. Дело в том, что, во-первых, схемы с
k элементами памяти имеют
2k состояний, поэтому описание сколько-нибудь больших схем в терминах состояний и таблиц переходов получаются очень громоздкими. Во-вторых, на разных этапах решаются разные задачи минимизации, порой не только не связанные между собой, но и противоречащие друг другу. Например, известны примеры, когда уменьшение числа состояний приводит к усложнению комбинационной части. И в-третьих, различное кодирование (а для
k элементов памяти вариантов таких кодов будет ( 2
k)!) приводит, вообще говоря, к разным
139 системам канонических уравнений, сложность которых до начала синтеза предвидеть невозможно. Поэтому получают распространения другие ме- тоды синтеза, например, декомпозиционный.
2.6.3. Декомпозиционный метод синтеза Этот метод основан на общей декомпозиции автоматов (обычно про- водят оптимальную декомпозицию) на элементарные автоматы, в каче- стве которых могут быть выбраны любые
абстрактные автоматы с про- стым числом состояний, например с двумя состояниями.
В результате декомпозиции получают матрицы соединений абстракт- ных элементарных автоматов, совместная работа которых эквивалентна работе исходного автомата. Выбирая конкретные типы элементарных автоматов (триггеры, элементы задержки и т.п.), по найденным матрицам соединения абстрактных элементарных автоматов строят функции воз- буждения и функции выходов конкретных выбранных элементарных автоматов. А это, в свою очередь, определяет структурную схему комби- национной части и, следовательно, всего автомата в целом. Поэтому в этом методе, по сути, синтез на структурном уровне выносится на аб- страктный уровень и сводится он к оптимальной в смысле минимума свя- зей декомпозиции автомата на абстрактные элементарные автоматы (как правило, с двумя состояниями) и записи функций возбуждения и выходов конкретных элементарных автоматов по матрицам соединений абстракт- ных элементарных автоматов.
Преимущества декомпозиционного метода синтеза автоматов по сравнению с каноническим следующие:
1) не требуется строить сложные кодированные таблицы переходов;
2) решается проблема оптимального кодирования внутренних состоя- ний автомата, приводящего к минимальной комбинационной части;
3) декомпозиционный метод позволяет строить оптимальную или близкую к ней функциональную схему автомата при использовании эле- ментарных автоматов со многими устойчивыми состояниями и логиче- скими элементами в недвоичной логике. Таким образом, этот метод поз- воляет осуществлять синтез автоматов при использовании элементного базиса, использующего логику более высокого порядка по сравнению с двоичной.
140
Контрольные вопросы
1. Назовите отличия алфавитного отображения от автоматного.
2. Дайте понятие конечного автомата.
3. Перечислите способы задания автоматов.
4. Назовите виды автоматов.
5. Как интерпретировать автомат второго рода автоматом первого рода?
6. Дайте определение асинхронного автомата.
7. Дайте определение изоморфизма и эквивалентности автоматов.
8. Задание функций перехода и выхода для частичных автоматов.
9. Понятие покрытия и совместимости состояний автоматов.
10. Назовите проблемы минимизации частичных автоматов.
11. Представление событий автоматами.
12. Перечислите регулярные операции над событиями.
13. Дайте понятие регулярного события.
14. Связь регулярных событий и автоматов.
15. Что такое источник?
16. Правила построения источника по регулярному событию.
17. Перечислите основные этапы алгоритма синтеза автомата на аб- страктном уровне.
18. Понятие индексного остатка источника.
19. Основные этапы графического алгоритма анализа автомата на аб- страктном уровне.
20. Перечислите операции над автоматными отображениями.
21. Понятие вероятностного автомата. Как задать вероятностный ав- томат?
22. Что такое комбинационный автомат?
23. Что необходимо для структурного синтеза автомата?
24. Что входит в состав элементного базиса?
25. Понятие правильной синхронной сети.
26. Канонические уравнения сети.
27. Проблемы кодирования состояний в асинхронных автоматах.
28. Какая из программ, предназначенных для реализации комбинаци- онного автомата, лучше – бинарная или операторная?
29. Какие недостатки и преимущества у канонического метода синтеза автоматов по сравнению с декомпозиционным методом синтеза?
141
3. СИСТЕМЫ С НЕПРЕРЫВНЫМИ ВО ВРЕМЕНИ ПЕРЕМЕННЫМИ. В этом разделе полагаем, что функции
r(
t) и
y(
t), интерпретируемые соответственно как входной и выходной сигнал некоторой системы, определены на континуальном множестве моментов времени
t. 3.1 Дифференциальные уравнения динамики систем 3.1.1. Описание систем дифференциальными уравнениями Вообще говоря, связь
между входным сигналом некоторой системы, описываемым функцией
r(
t), и ее выходным сигналом
y(
t) может зада- ваться нелинейным дифференциальным уравнением произвольного по- рядка
n:
(
)
( )
(
1)
( )
(
1)
,
,..., ,
,
,...,
0
nnmmF yyy rrr−
−
= , (3.1.1) где
(
)
1 2
2
, ,...,
n mF z zz+ +
– функция
n+m+2 аргументов. Задав вид функции
r(
t) и
n начальных условий
( )
( )
( )
(
1)
(
1)
0 0
0 0
0 0
,
,...,
nny ty y tyyty−
−
=
=
=
ɺ
ɺ
, можно в принципе решить это уравнение и найти выход (реакцию)
y(
t) данной системы на входной сигнал
r(
t).
Уравнение (3.1.1) является уравнением самого общего вида и описы- вает поведение системы во всех режимах. Один из частных, но весьма распространенных случаев таких режимов – это статический режим, то есть такой режим, при котором ни входные, ни выходные сигналы систе- мы не меняются во времени. Конечно, это определенная идеализация, которая получается из уравнения (3.1.1) формальной подстановкой вме- сто всех производных по времени нулей
( )
(
1)
( )
(
1)
0
nnmmyyy rrr−
−
=
= = =
=
= = =
ɺ
ɺ
Тогда уравнение статики примет вид
(
)
ст ст
0,0,...,
, 0,0,...,
0
Fyr = , (3.1.2)
142 из которого можно установить связь между статическим значением входного сигнала
rcт и статическим значением выходного сигнала
ycт с т с т
( )
yf r=
. (3.1.3)
Уравнение (3.1.3) описывает так называемую
статическую характе-ристику системы.
Решение уравнения (3.1.1) для произвольной функции
F наталкивает- ся на непреодолимые трудности и возможно только в некоторых частных случаях. Одним из таких частных, но весьма важных и распространенных случаев является случай, когда функция
F является
линейной функцией по
своим аргументам, то есть когда уравнение, связывающее входной сигнал
r(
t) с выходным
y(
t), является
линейным дифференциальным урав- нением. Упомянутое уравнение принято записывать так, чтобы выходная величина и её производные располагались бы в левой части, а входная величина и её производные – в правой части уравнения:
( )
( )
( )
( )
( )
( )
(
1)
( )
0 1
0
nnmnma t ya t ya t y b t rb t r−
+
+ +
=
+ +
. (3.1.4)
Коэффициенты этого уравнения
,
ika b в общем случае могут зависеть от времени и тогда уравнение (3.1.4) описывает
нестационарную систе- му. Если такой зависимости от времени нет (или она очень слабая) то приходим к линейному дифференциальному уравнению с постоянными коэффициентами:
( )
(
1)
( )
0 1
0
nnmnma ya ya y b rb r−
+
+ +
=
+ +
. (3.1.5)
3.1.2. Линеаризация В некоторых случаях удается даже нелинейное уравнение типа (3.1.1) свести к линейному уравнению типа (3.1.4) или (3.1.5). Пусть для некото- рого установившегося значения входа
rcт получено уравнение статики
(3.1.2). Тогда разложим левую часть уравнения (3.1.1) в ряд Тейлора
(предполагая, что такое разложение имеет место) около точки устано- вившегося режима и ограничим этот ряд линейными приращениями пе- ременных
143
( )
(
1)
1 2
ст,
ст
1 2
0 0
( )
1 2
2 0
0 0
( ,...
)
(0,...
0,... )
0,
nnn mmnnn mFFF zzFyryyzzFFFyrrzzz−
+ +
+
+
+ +
∂
∂
≈
+
∆
+
∆
+
∂
∂
∂
∂
∂
+
∆ +
∆
+ +
∆ =
∂
∂
∂
(3.1.6) где частные производные
0
iFz
∂
∂
вычисляются при подстановке в них значений
ycт и
rcт и нулевых значениях производных, соответствующих установившемуся режиму.
Первое слагаемое в (3.1.6) равно нулю согласно (3.1.2). Вводя обозна- чения
1 2
0 0
(1 1) и
(n 2 2),
ii niiFFai nbi n mzz+
− −
∂
∂
=
≤ ≤ +
−
=
+ ≤ ≤ + +
∂
∂
и перенося слагаемые с входным воздействием и его производными в пра- вую часть, получим:
( )
(
1)
( )
0 1
0
nnmnma ya ya y b rb r−
∆
+ ∆
+ + ∆ = ∆
+ + ∆
. (3.1.7)
Уравнение (3.1.7) по форме точно такое же, как и (3.1.5), но записано относительно соответствующих отклонений ст ст
( )
,
( )
y y tyr r tr∆ =
−
∆ =
− .
Полученное уравнение (3.1.7) описывает ту же самую систему, что и уравнение (3.1.1), но имеет следующие отличия.
Во-первых, уравнение (3.1.7) приближенное,
причем это приближение тем точнее, чем меньше отклонения переменных от установившихся зна- чений.
Во-вторых, поскольку при выводе уравнения (3.1.7) использовалось разложение в ряд Тейлора, такая операция применима только к непре- рывно-дифференцируемым нелинейностям. Такие нелинейности называ- ются
линеаризуемыми, а нелинейные функции, не удовлетворяющие это- му условию, называются существенно нелинейными.
В-третьих, уравнение (3.1.7) составлено относительно отклонений, а не самих сигналов. Такого рода уравнения называются уравнениями в отклонениях или в вариациях.
И, наконец, в-четвертых (и это основное), уравнение (3.1.7) линейное.
Поскольку форма уравнений (3.1.7) и (3.1.5) совпадает, в дальнейшем можно использовать любое из них, например, (3.1.5) подразумевая, что в качестве переменных могут быть и соответствующие отклонения.
Скачать 2.07 Mb.