- •1 Introduction (Введение)
- •2 Generalized block diagram of a finite state machine (Обобщенная структурная схема конечного автомата).
- •Push – вталкивать данные в стек;
- •Graphs (Графы)
- •Figure 3: Directed labeled graph for the edge detector Ориентированный помеченный граф для краевого детектора)
- •4 Finite State Machines (Конечные Автоматы)
- •5 Unified Modeling Language (Унифицированный язык моделирования)
- •Uml state machines (конечные автоматы унифицированного языка моделирования).
- •Fsm logic (логическая схема работы конечного автомата).
- •State diagrams versus flowcharts (диаграммы состояний в сравнении с блок-схемами программ)
- •Uml state diagram (диаграмма состояний уям)
- •Defining a State diagram (построение диаграммы состояний)
- •Elements of a State diagram (Элементы диаграммы состояний)
- •Asm Chart (диаграмма алгоритмического конечного автомата)
- •Detailed asm Chart (подробная диаграмма asm).
- •Register transfer level (Условное изображение на уровне rtl).
- •Rtl in the circuit design cycle (описание на уровне rtl для разработки имс).
- •Automata-based programming (программирование с помощью модели конечных автоматов).
- •Example (пример)
- •Traditional (imperative) program (обычная императивная программа).
- •Расшифровка операторов программы на языке с:
- •Automata-based style program (программа на основе модели конечного автомата)
- •A separate function for the automaton step (отдельная функция для этапа конечного автомата)
- •Explicit state transition table (таблица переходов состояний в явном виде)
- •Using object-oriented capabilities (использование объектно-ориентированных возможностей)
- •Other extensions
- •Moore machine
- •Formal definition
- •Mealy machine
- •Formal definition
- •Mathematical model
- •Advantages and disadvantages (преимущества и недостатки).
- •Formal definition (формальное определение).
- •Example (пример)
- •Example (пример)
- •Transformations from/to state diagram (переход от/к диаграмме состояний).
- •Directed graph of a finite state machine (направленный граф конечного автомата).
- •Harel statechart (диаграммы Harel).
- •С. State transition table (таблица смены состояний).
- •Δ and λ aren’t shown in Fig.1. Δ и λ не показаны на схеме для визуального упрощения.
- •The methods to define automata (Способы задания автоматов)
- •Transition and output tables (Таблицы переходов и выходов)
- •Transition and output tables for Mealy automaton (тпв автомата Мили)
- •Transition and output tables for Moore automaton (тпв автомата Мура)
С. State transition table (таблица смены состояний).
Условные обозначения:
Current state – текущее состояние;
State – состояние;
Condition – условие.
An automaton may be represented using the following mathematical description: (Или, если перейти от иллюстрации к математическому описанию автомата): A Symbolic notations (Обозначения):
{A}set is the set of values at the physical inputs of an automaton – the sequence of High and Low levels (“0” and “1”).
Множество {A} – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
{B}set is the set of values at the physical outputs of an automaton.
Множество {B} – представляет собой множество значений на физических выходах автомата.
{C}set is the set of internal states of an automaton - its memory. means the initial state.
Множество {C} – это такое множество, которое представляет внутреннее состояние автомата – память. На будущее будем обозначать начальное состояние автомата.
δ = X × Z → Z – the function of transition (these functions unambiguously define state to which an automaton goes from state.
δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние в которое переходит автомат из состояния .
λ = X × Z → Y is the output functions (they define the output signals of an automaton depending on the input signals and internal state).
λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.
Δ and λ aren’t shown in Fig.1. Δ и λ не показаны на схеме для визуального упрощения.
Mealy automatons are described by the set of equations
(Автоматы Мили описываются системой уравнений): c(t) = T(a(t), c(t-1)); b(t) = G(a(t), c(t-1)).
There are two types of automatons
(Выделяют 2 типа автоматов):
1. A state machine which uses only Input Actions, so that the output depends on the state and also on inputs, is called a Mealy model.
Конечный автомат, который реагирует на входное воздействие таким образом, что выход зависит от состояния, а также от входных воздействий, называется автоматом Мили).
δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние в которое переходит автомат из состояния .
λ = X × Z → Y is the output functions (they define the output signals of an automaton depending on the input signals and internal state).
λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.
Moore automatons are described by the set of equations
Автоматы Мура описываются уравнениями: c(t) = δ(a(t), c(t-1)); b(t) = λ(a(t), c(t)).
As you may see from these equations the state of an automaton at the present time interval is the function of its state at the previous time interval and the input signal.
Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала.
The mentioned automata differ in the output function.
The output signal of Mealy automaton is defined by input signal and the automaton state at the previous time interval .
The output signal of Moore automaton is defined by input signal and the automaton state at the previous time interval .
Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом и состоянием автомата в предыдущий момент времени . Выходной сигнал автомата Мура определяется парой входного сигнала и состояния в данный момент .
Note that is possible to pass on from one type of automata to another and vice versa, at that during the transition from Mealy to Moore automaton the number of internal states will be the same, while during the inverse transition the number of internal states may arise.
Так же можно отметить, что от одного типа можно перейти ко второму и наоборот, причем при переходе от автомата Мили к автомату Мура число внутренних состояний автомата останется прежним, а при обратном переходе число внутренних состояний может возрасти. На этом останавливаться подробно не будем, считая, что синтезировали (нарисовали граф) автомат того типа, который необходим. In other words, Mealy automaton will generate an output signal in the case when its input signal is changing depending on its previous state. At that the duration of an output signal doesn’t depend on the duration of an input signal, but it depends only on the availability of an input signal.
Т.е. автомат типа Мили вырабатывает выходной сигнал, когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия.
The output signal of Moore automaton depends on its state at the present moment, that is this automaton will generate a certain output signal till the change in its state.
В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени, т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.