В том случае, если входные сигналы или структура системы изменяются мгновенно, то такие системы можно описать с помощью дискретных моделей, особенностью которых является присутствие в них дискретного времени, т.е. состояние системы характеризуется только лишь дискретным временем.
Часто в дискретных моделях фиксируется не значение дискретного времени, а лишь номер возникновения таких моментов, причем, как правило, шаг дискретности является постоянной величиной и называется тактом - Тк. В том случае, если такт дискретности носит заранее известный характер или состояние таких систем можно описать по известному закону, то такие модели принято называть дискретно-детерминированными (или F‑cхемами). В том случае, когда в дискретных моделях появляется какой-либо случайный фактор (такт, состояние и т.д.), такие модели называют дискретно-стохастическими (или Р-схемами). Общее между двумя моделями - дискретность и понятие состояния. Для F‑схем в качестве основной теории или математического аппарата используется теория автоматов. Этот раздел относится к теории кибернетики, в которой в частности рассматриваются модели автоматов. На основе этой теории систему можно представить в виде автомата, у которого внутренние состояния изменяются в дискретный момент времени. Автомат, у которого множество внутренних состояний и входных сигналов являются конечным множеством называется конечным автоматом. Конечный автомат и представляет собой F-схему. F-схему можно представить в виде следующей совокупности элементов:
¨ {X} - конечное множество входных сигналов Х или входной алфавит,
¨ {Y} - конечное множество выходных сигналов Y или выходной алфавит,
¨ {Z} - конечное множество состояний Z или внутренний алфавит,
¨ {Z0} - конечное множество начальных состояний,
¨ F(X,Z) - функция переходов,
¨ Y(X,Z) - функция выходов.
F = < X, Y, Z, Z0, F, Y> .
Абстрактный конечный автомат имеет один вход и один выход и если на его вход, установленный в начальное состояние Z0, подать входной набор Х, то на выходе получим в соответствии с входными тактами и выходным алфавитом выходное слово.
Таким образом, конечный автомат преобразует входное слово путем изменения состояний в выходном слове, в результате чего, в каждом такте при входном сигнале Х(Т) фиксируется состояние автомата Z(Т), в результате чего формируется новое состояние Z(Т+1) и на (Т+1) такте формируется выходной сигнал Y(T+1). При описании дискретных моделей с помощью F-схем используют автоматы Мили и Мура ( по-другому, их называют автоматами первого и второго рода).
F1(автомат Мили):
Z(t+1) = F[Z(t), X(t)]
Y(t) = Y[Z(t), X(t)], t=0,1,2, ...
F2(автомат Мура):
Z(t+1) = F[Z(t), X(t)]
Y(t) = Y[Z(t), X(t-1)], t=1,2, ...
Рассмотрим автомат Мили.
| Xi | Z0 | Z1 | Z2 |
| | Z2 | Z0 | Z0 |
| X2 | Z0 | Z2 | Z1 |
| X1 | y1 (1) | y1 (2) | y2 (3) |
| X2 | y1 (4) | y2 (5) | y1 (6) |
с)
Способы задания F-автомата.
1. Табличный.
2. С помощью графа.
3. Матрицей.
Приведем пример задания F2-автомата или автомата Мура.
F => Z(t), X(t)
Y = Z(t)
Рассмотрим схему с пятью состояниями.
а) Универсальная таблица:
| Xi | | | Y | | |
| | Y1 | Y2 | Y3 | Y2 | Y3 |
| | Z0 | Z1 | Z2 | Z3 | Z4 |
| X1 | Z1 | Z4 | Z4 | Z2 | Z2 |
| X2 | Z3 | Z1 | Z1 | Z0 | Z0 |
б) С помощью графа, где вершины графа соответствуют состояниям, а дуги - определяют переходы из одного состояния в другое:
в) Матрицей:
Рассмотрим пример моделирования работы телефонного аппарата, способного запоминать номер и посылать в соответствующем режиме этот номер в телефонную сеть в виде импульсов.
Такой телефонный аппарат будет обладать двумя независимыми состояниями: (N, a). Первое состояние соответствует событию, связанному с памятью автомата и учитывает какой номер находится в памяти. Второе состояние или событие фиксирует работу телефонной трубки в двух режимах: на аппарате и снято. Пара (N, a) связана с совершением этих событий. N может принимать значения 0,1,2, ... n , а a - одно из двух значений: 0 - трубка снята, 1 - трубка лежит на аппарате. Кроме независимых состояний и событий существуют также внешние воздействия, которые можно условно описать так:
Т0 - трубка снимается,
Т1 - трубка опускается,
К - кнопка нажата для набора номера NÎ1,2, ..., n,
С - кнопка стирания номера,
L - не происходит никаких воздействий.
Будем считать, что в каждый выделенный такт времени будет наблюдаться одно из перечисленных воздействий. Таким образом, в качестве входных воздействий можно рассматривать некоторую последовательность, при этом для простоты предположим, что число наборных элементов n=2.
Входной набор воздействий:
v = {Т0, T1, 1, 2, C, L}
Для описания состояния модели к некоторому моменту времени tk+1 можно выделить следующие состояния:
1) v = T0, то при a = 1, модель переходит в новое состояние (N,0), если a = 0, то состояние не изменится,
2) v = T1, при a = 0 - модель переходит в новое состояние, a = 1 - состояние модели не изменится,
3) v = K, в этом случае номер, хранимый в памяти аппарата, остается записанным, так как состояние не изменилось,
4) v = i, где i = 1,2 . Если N = 0 и a = 0, то так как трубка снята и нет номера в памяти, то к моменту времени tk+1 номер i окажется записан в память и новое состояние модели будет (i,0). Если N ¹ 0, а a = 0 или a = 1, то состояние модели останется прежним (N, a),
5) v = C - происходит стирание номера и модель переходит к состоянию (0,a),
6) v = L. В этом режиме состояние модели не изменяются.
Аналогичным образом, перечисляя входные воздействия v, можно определить выходные сигналы или воздействия в телефонную сеть.
1) Если v Î {T0, T1, C, L}, то последовательность импульсов в телефонную сеть не посылается, т.е. w = 0.
2) Если входное воздействие v = {K}, то при a = 0 и N = 0 w = N.
3) Если a = 1, то в любом состоянии N w = 0.
4) v = i, где i - последовательность {1,2, ... , N }, если a = 1, то w = 0, если a = 0, то w = i.
Приведенное описание является достаточно громоздким, поэтому наряду с таким описанием моделей автоматов, используется диаграмма в виде графа, вершинами которого являются состояния. В данном случае таких состояний шесть. Внутри кружка, который является вершиной графа указывается состояние (N, a), а дуги этого графа представляются в виде пары (v, w). (L,0)
Если модель под действием входных сигналов v переходит в новое состояние (N’,a’), то это осуществляется с помощью направленной дуги, каждая из которых помечается парой (v, w). Если несколько различных стрелок идут от одной вершины к той же вершине, то стрелка берется одна и подписывается соответствующими парами (v1,w1), ... , (vk, wk). C помощью таких диаграмм легко проследить всю последовательность перехода из одного состояния в другое (например, из состояния (0,1) в состояние (2,1)). При этом получим:
v = {T0, 1, C, 2, K, L, T1, K}
w= { 0, 1, 0, 2, 2, 0, 0, 0}
0 коммент.:
Отправить комментарий